Static Analysis for Program Execution Cost Estimation

Program execution patterns offer valuable insights for software optimization, but accurately estimating these patterns through static analysis poses a significant challenge. While methods like machine learning and architecture simulation achieve high accuracy by utilizing extensive profiling data, they come with their own limitations in applicability and resource usage. This paper systematically evaluates control-flow analysis strategies and their combinations to estimate basic-block execution frequency. These frequency estimates are then combined with per-block cost estimations to estimate total execution cost. The investigated approach focuses on estimating branch probabilities, analyzing intra-procedural basic block frequencies, and examining inter-procedural function calls. Real execution cost is measured from a benchmark suite (cBench) to form a ground-truth profile. Correlation between cost estimates and this ground truth indicates static-method accuracy; to interpret this value, the same correlation is computed for leading simulation tools (llvm-mca, uiCA). Comparing these correlations reveals how close static analysis comes to state-of-the-art simulators. The findings show that simple heuristics achieve a correlation within 4.5% of advanced simulation tools while avoiding architecture-specific details and running in an order of magnitude less time. Additionally, analysis of how different strategies interact yields practical insights toward further improving this adaptable and efficient approach.