HORIZON: Estimating Alias Analysis Precision Bounds and Their Impact on Performance

Abstract

Alias analysis is a technique to identify whether a memory location can be accessed in more than one way. An ideal alias analysis implementation should be both precise and scalable. However, in practice, implementations of alias analysis have to make a trade-off between precision and scalability. The alias analysis implementations that perform inter-procedural analysis are more precise (answer a higher number of alias queries with certainty), but expensive, making them infeasible for practical use. Most compiler developers opt for intra-procedural analysis over inter-procedural, thereby compromising the precision of alias analysis implementations to achieve scalability. For compilers, this compromise leads to a loss in optimization opportunities, limiting the performance achievable by the compiled program.

In this work, we present HORIZON, a tool that estimates the upper bound on alias analysis precision improvement and its impact on program performance, enabling an understanding of how compromised precision affects execution. HORIZON implements a profiling-based approach to gather precise alias information (must- and no-alias) missed by existing alias implementations and provides this information to the compiler to estimate potential performance gains. Integrated with LLVM, we applied HORIZON to evaluate the default LLVM alias analysis on standard benchmarks, demonstrating that precision improvement could range from 0% to 33%, with corresponding performance impact between 0% and 53%, indicating the effectiveness of our approach and tool.