Heuristics for stateful flow-sensitive alias analysis in LLVMAlias analysis in compilers is used in several compiler optimizations to reason about which addresses point to which memory locations during the life cycle of a program. Leveraging this information enables “standard” compiler optimizations like the loop hoisting transformation to move potentially costly operations out of a loop if alias analysis can determine that a memory location is not being written into. While alias analysis is a very useful tool in compiler optimizations, it is, in general, a NP-hard problem and can thus only be resolved by heuristics. A host of optimizations and transformations like global value numbering, loop hoisting/ sinking and constant propagation can be benefit from alias analysis.
The primary interface for alias analysis in LLVM is the Basic alias analysis tool that is stateless and replies to simple queries like “do these two pointers point to the same location?”. This stateless analysis uses broad, but simple rules like establishing that a global and an auto variable can never alias each other, nor can two fields of a struct and so on. While this analysis is undoubtedly effective as it captures all important rules, it is not flow sensitive and can thus miss several important facts that flow sensitivity can provide. In this talk, we discuss several techniques and heuristics to use flow sensitive information via the control flow graph and data flow information to sharpen alias analysis that provide more opportunities for optimizations to emit potentially better bitcode.