470 lines · python
1import sys2import argparse3import subprocess4import tempfile5import json6import os7from datetime import datetime8import numpy as np9from scipy.optimize import curve_fit10from scipy.stats import t11 12 13def generate_cpp_cycle_test(n: int) -> str:14 """15 Generates a C++ code snippet with a specified number of pointers in a cycle.16 Creates a while loop that rotates N pointers.17 This pattern tests the convergence speed of the dataflow analysis when18 reaching its fixed point.19 20 Example:21 struct MyObj { int id; ~MyObj() {} };22 23 void long_cycle_4(bool condition) {24 MyObj v1{1};25 MyObj v2{1};26 MyObj v3{1};27 MyObj v4{1};28 29 MyObj* p1 = &v1;30 MyObj* p2 = &v2;31 MyObj* p3 = &v3;32 MyObj* p4 = &v4;33 34 while (condition) {35 MyObj* temp = p1;36 p1 = p2;37 p2 = p3;38 p3 = p4;39 p4 = temp;40 }41 }42 """43 if n <= 0:44 return "// Number of variables must be positive."45 46 cpp_code = "struct MyObj { int id; ~MyObj() {} };\n\n"47 cpp_code += f"void long_cycle_{n}(bool condition) {{\n"48 for i in range(1, n + 1):49 cpp_code += f" MyObj v{i}{{1}};\n"50 cpp_code += "\n"51 for i in range(1, n + 1):52 cpp_code += f" MyObj* p{i} = &v{i};\n"53 54 cpp_code += "\n while (condition) {\n"55 if n > 0:56 cpp_code += f" MyObj* temp = p1;\n"57 for i in range(1, n):58 cpp_code += f" p{i} = p{i+1};\n"59 cpp_code += f" p{n} = temp;\n"60 cpp_code += " }\n}\n"61 cpp_code += f"\nint main() {{ long_cycle_{n}(false); return 0; }}\n"62 return cpp_code63 64 65def generate_cpp_merge_test(n: int) -> str:66 """67 Creates N independent if statements that merge at a single point.68 This pattern specifically stresses the performance of the69 'LifetimeLattice::join' operation.70 71 Example:72 struct MyObj { int id; ~MyObj() {} };73 74 void conditional_merges_4(bool condition) {75 MyObj v1, v2, v3, v4;76 MyObj *p1 = nullptr, *p2 = nullptr, *p3 = nullptr, *p4 = nullptr;77 78 if(condition) { p1 = &v1; }79 if(condition) { p2 = &v2; }80 if(condition) { p3 = &v3; }81 if(condition) { p4 = &v4; }82 }83 """84 if n <= 0:85 return "// Number of variables must be positive."86 87 cpp_code = "struct MyObj { int id; ~MyObj() {} };\n\n"88 cpp_code += f"void conditional_merges_{n}(bool condition) {{\n"89 decls = [f"v{i}" for i in range(1, n + 1)]90 cpp_code += f" MyObj {', '.join(decls)};\n"91 ptr_decls = [f"*p{i} = nullptr" for i in range(1, n + 1)]92 cpp_code += f" MyObj {', '.join(ptr_decls)};\n\n"93 94 for i in range(1, n + 1):95 cpp_code += f" if(condition) {{ p{i} = &v{i}; }}\n"96 97 cpp_code += "}\n"98 cpp_code += f"\nint main() {{ conditional_merges_{n}(false); return 0; }}\n"99 return cpp_code100 101 102def generate_cpp_nested_loop_test(n: int) -> str:103 """104 Generates C++ code with N levels of nested loops.105 This pattern tests how analysis performance scales with loop nesting depth,106 which is a key factor in the complexity of dataflow analyses on structured107 control flow.108 109 Example (n=3):110 struct MyObj { int id; ~MyObj() {} };111 void nested_loops_3() {112 MyObj* p = nullptr;113 for(int i0=0; i0<2; ++i0) {114 MyObj s0;115 p = &s0;116 for(int i1=0; i1<2; ++i1) {117 MyObj s1;118 p = &s1;119 for(int i2=0; i2<2; ++i2) {120 MyObj s2;121 p = &s2;122 }123 }124 }125 }126 """127 if n <= 0:128 return "// Nesting depth must be positive."129 130 cpp_code = "struct MyObj { int id; ~MyObj() {} };\n\n"131 cpp_code += f"void nested_loops_{n}() {{\n"132 cpp_code += " MyObj* p = nullptr;\n"133 134 for i in range(n):135 indent = " " * (i + 1)136 cpp_code += f"{indent}for(int i{i}=0; i{i}<2; ++i{i}) {{\n"137 cpp_code += f"{indent} MyObj s{i}; p = &s{i};\n"138 139 for i in range(n - 1, -1, -1):140 indent = " " * (i + 1)141 cpp_code += f"{indent}}}\n"142 143 cpp_code += "}\n"144 cpp_code += f"\nint main() {{ nested_loops_{n}(); return 0; }}\n"145 return cpp_code146 147 148def generate_cpp_switch_fan_out_test(n: int) -> str:149 """150 Generates C++ code with a switch statement with N branches.151 Each branch 'i' 'uses' (reads) a single, unique pointer 'pi'.152 This pattern creates a "fan-in" join point for the backward153 liveness analysis, stressing the LivenessMap::join operation154 by forcing it to merge N disjoint, single-element sets of live origins.155 The resulting complexity for LiveOrigins should be O(n log n) or higher.156 157 Example (n=3):158 struct MyObj { int id; ~MyObj() {} };159 160 void switch_fan_out_3(int condition) {161 MyObj v1{1}; MyObj v2{1}; MyObj v3{1};162 MyObj* p1 = &v1; MyObj* p2 = &v2; MyObj* p3 = &v3;163 164 switch (condition % 3) {165 case 0:166 p1->id = 1;167 break;168 case 1:169 p2->id = 1;170 break;171 case 2:172 p3->id = 1;173 break;174 }175 }176 """177 if n <= 0:178 return "// Number of variables must be positive."179 180 cpp_code = "struct MyObj { int id; ~MyObj() {} };\n\n"181 cpp_code += f"void switch_fan_out{n}(int condition) {{\n"182 # Generate N distinct objects183 for i in range(1, n + 1):184 cpp_code += f" MyObj v{i}{{1}};\n"185 cpp_code += "\n"186 # Generate N distinct pointers, each as a separate variable187 for i in range(1, n + 1):188 cpp_code += f" MyObj* p{i} = &v{i};\n"189 cpp_code += "\n"190 191 cpp_code += f" switch (condition % {n}) {{\n"192 for case_num in range(n):193 cpp_code += f" case {case_num}:\n"194 cpp_code += f" p{case_num + 1}->id = 1;\n"195 cpp_code += " break;\n"196 197 cpp_code += " }\n}\n"198 cpp_code += f"\nint main() {{ switch_fan_out{n}(0); return 0; }}\n"199 return cpp_code200 201 202def analyze_trace_file(trace_path: str) -> dict:203 """204 Parses the -ftime-trace JSON output to find durations for the lifetime205 analysis and its sub-phases.206 Returns a dictionary of durations in microseconds.207 """208 durations = {209 "lifetime_us": 0.0,210 "total_us": 0.0,211 "fact_gen_us": 0.0,212 "loan_prop_us": 0.0,213 "live_origins_us": 0.0,214 }215 event_name_map = {216 "LifetimeSafetyAnalysis": "lifetime_us",217 "ExecuteCompiler": "total_us",218 "FactGenerator": "fact_gen_us",219 "LoanPropagation": "loan_prop_us",220 "LiveOrigins": "live_origins_us",221 }222 try:223 with open(trace_path, "r") as f:224 trace_data = json.load(f)225 for event in trace_data.get("traceEvents", []):226 event_name = event.get("name")227 if event_name in event_name_map:228 key = event_name_map[event_name]229 durations[key] += float(event.get("dur", 0))230 except (IOError, json.JSONDecodeError) as e:231 print(f"Error reading or parsing trace file {trace_path}: {e}", file=sys.stderr)232 return {key: 0.0 for key in durations}233 return durations234 235 236def power_law(n, c, k):237 """Represents the power law function: y = c * n^k"""238 return c * np.power(n, k)239 240 241def human_readable_time(ms: float) -> str:242 """Converts milliseconds to a human-readable string (ms or s)."""243 if ms >= 1000:244 return f"{ms / 1000:.2f} s"245 return f"{ms:.2f} ms"246 247 248def calculate_complexity(n_data, y_data) -> tuple[float | None, float | None]:249 """250 Calculates the exponent 'k' for the power law fit y = c * n^k.251 Returns a tuple of (k, k_standard_error).252 """253 try:254 if len(n_data) < 3 or np.all(y_data < 1e-6) or np.var(y_data) < 1e-6:255 return None, None256 257 non_zero_indices = y_data > 0258 if np.sum(non_zero_indices) < 3:259 return None, None260 261 n_fit, y_fit = n_data[non_zero_indices], y_data[non_zero_indices]262 popt, pcov = curve_fit(power_law, n_fit, y_fit, p0=[0, 1], maxfev=5000)263 k_stderr = np.sqrt(np.diag(pcov))[1]264 return popt[1], k_stderr265 except (RuntimeError, ValueError):266 return None, None267 268 269def generate_markdown_report(results: dict) -> str:270 """Generates a concise, Markdown-formatted report from the benchmark results."""271 report = []272 timestamp = datetime.now().strftime("%Y-%m-%d %H:%M:%S %Z")273 report.append(f"# Lifetime Analysis Performance Report")274 report.append(f"> Generated on: {timestamp}")275 report.append("\n---\n")276 277 for test_name, data in results.items():278 title = data["title"]279 report.append(f"## Test Case: {title}")280 report.append("\n**Timing Results:**\n")281 282 # Table header283 report.append(284 "| N (Input Size) | Total Time | Analysis Time (%) | Fact Generator (%) | Loan Propagation (%) | Live Origins (%) |"285 )286 report.append(287 "|:---------------|-----------:|------------------:|-------------------:|---------------------:|------------------:|"288 )289 290 # Table rows291 n_data = np.array(data["n"])292 total_ms_data = np.array(data["total_ms"])293 for i in range(len(n_data)):294 total_t = total_ms_data[i]295 if total_t < 1e-6:296 total_t = 1.0 # Avoid division by zero297 298 row = [299 f"| {n_data[i]:<14} |",300 f"{human_readable_time(total_t):>10} |",301 f"{data['lifetime_ms'][i] / total_t * 100:>17.2f}% |",302 f"{data['fact_gen_ms'][i] / total_t * 100:>18.2f}% |",303 f"{data['loan_prop_ms'][i] / total_t * 100:>20.2f}% |",304 f"{data['live_origins_ms'][i] / total_t * 100:>17.2f}% |",305 ]306 report.append(" ".join(row))307 308 report.append("\n**Complexity Analysis:**\n")309 report.append("| Analysis Phase | Complexity O(n<sup>k</sup>) | ")310 report.append("|:------------------|:--------------------------|")311 312 analysis_phases = {313 "Total Analysis": data["lifetime_ms"],314 "FactGenerator": data["fact_gen_ms"],315 "LoanPropagation": data["loan_prop_ms"],316 "LiveOrigins": data["live_origins_ms"],317 }318 319 for phase_name, y_data in analysis_phases.items():320 k, delta = calculate_complexity(n_data, np.array(y_data))321 if k is not None and delta is not None:322 complexity_str = f"O(n<sup>{k:.2f}</sup> ± {delta:.2f})"323 else:324 complexity_str = "(Negligible)"325 report.append(f"| {phase_name:<17} | {complexity_str:<25} |")326 327 report.append("\n---\n")328 329 return "\n".join(report)330 331 332def run_single_test(333 clang_binary: str, output_dir: str, test_name: str, generator_func, n: int334) -> dict:335 """Generates, compiles, and benchmarks a single test case."""336 print(f"--- Running Test: {test_name.capitalize()} with N={n} ---")337 338 generated_code = generator_func(n)339 340 base_name = f"test_{test_name}_{n}"341 source_file = os.path.join(output_dir, f"{base_name}.cpp")342 trace_file = os.path.join(output_dir, f"{base_name}.json")343 344 with open(source_file, "w") as f:345 f.write(generated_code)346 347 clang_command = [348 clang_binary,349 "-c",350 "-o",351 "/dev/null",352 "-ftime-trace=" + trace_file,353 "-Xclang",354 "-fexperimental-lifetime-safety",355 "-std=c++17",356 source_file,357 ]358 359 try:360 result = subprocess.run(361 clang_command, capture_output=True, text=True, timeout=60362 )363 except subprocess.TimeoutExpired:364 print(f"Compilation timed out for N={n}!", file=sys.stderr)365 return {}366 367 if result.returncode != 0:368 print(f"Compilation failed for N={n}!", file=sys.stderr)369 print(result.stderr, file=sys.stderr)370 return {}371 372 durations_us = analyze_trace_file(trace_file)373 return {374 key.replace("_us", "_ms"): value / 1000.0 for key, value in durations_us.items()375 }376 377 378if __name__ == "__main__":379 parser = argparse.ArgumentParser(380 description="Generate, compile, and benchmark C++ test cases for Clang's lifetime analysis."381 )382 parser.add_argument(383 "--clang-binary", type=str, required=True, help="Path to the Clang executable."384 )385 parser.add_argument(386 "--output-dir",387 type=str,388 default="benchmark_results",389 help="Directory to save persistent benchmark files. (Default: ./benchmark_results)",390 )391 392 args = parser.parse_args()393 394 os.makedirs(args.output_dir, exist_ok=True)395 print(f"Benchmark files will be saved in: {os.path.abspath(args.output_dir)}\n")396 397 # Maximize 'n' values while keeping execution time under 10s.398 test_configurations = [399 {400 "name": "cycle",401 "title": "Pointer Cycle in Loop",402 "generator_func": generate_cpp_cycle_test,403 "n_values": [50, 75, 100, 200, 300],404 },405 {406 "name": "merge",407 "title": "CFG Merges",408 "generator_func": generate_cpp_merge_test,409 "n_values": [400, 1000, 2000, 5000],410 },411 {412 "name": "nested_loops",413 "title": "Deeply Nested Loops",414 "generator_func": generate_cpp_nested_loop_test,415 "n_values": [50, 100, 150, 200],416 },417 {418 "name": "switch_fan_out",419 "title": "Switch Fan-out",420 "generator_func": generate_cpp_switch_fan_out_test,421 "n_values": [500, 1000, 2000, 4000],422 },423 ]424 425 results = {}426 427 print("Running performance benchmarks...")428 for config in test_configurations:429 test_name = config["name"]430 results[test_name] = {431 "title": config["title"],432 "n": [],433 "lifetime_ms": [],434 "total_ms": [],435 "fact_gen_ms": [],436 "loan_prop_ms": [],437 "live_origins_ms": [],438 }439 for n in config["n_values"]:440 durations_ms = run_single_test(441 args.clang_binary,442 args.output_dir,443 test_name,444 config["generator_func"],445 n,446 )447 if durations_ms:448 results[test_name]["n"].append(n)449 for key, value in durations_ms.items():450 results[test_name][key].append(value)451 452 print(453 f" Total Analysis: {human_readable_time(durations_ms['lifetime_ms'])} | "454 f"FactGen: {human_readable_time(durations_ms['fact_gen_ms'])} | "455 f"LoanProp: {human_readable_time(durations_ms['loan_prop_ms'])} | "456 f"LiveOrigins: {human_readable_time(durations_ms['live_origins_ms'])}"457 )458 459 print("\n\n" + "=" * 80)460 print("Generating Markdown Report...")461 print("=" * 80 + "\n")462 463 markdown_report = generate_markdown_report(results)464 print(markdown_report)465 466 report_filename = os.path.join(args.output_dir, "performance_report.md")467 with open(report_filename, "w") as f:468 f.write(markdown_report)469 print(f"Report saved to: {report_filename}")470