Points-to analysis

Points-to analysis computes a points-to set for each pointer, representing all possible targets. The two classic algorithms are Andersen's (subset-based, flow-insensitive) and Steensgaard's (unification-based). Andersen's is more precise but has cubic worst-case time, while Steensgaard's is near-linear but less precise. Modern implementations use context sensitivity and field sensitivity to improve precision, often via binary decision diagrams (BDDs) or sparse representations.

Compilers use points-to information for alias analysis, enabling optimizations like load/store elimination and automatic parallelization. In security, points-to analysis helps detect memory corruption vulnerabilities, such as use-after-free and double-free, by tracking pointer targets across program paths.² It is also used in program slicing and refactoring tools.

Scalability is a major challenge for whole-program points-to analysis, especially in large object-oriented programs with dynamic dispatch. Techniques like pointer abstraction, heap cloning, and on-the-fly call graph construction mitigate this. Recent work uses machine learning to predict points-to sets, but traditional algorithms remain the standard.³

Points-to analysis has roots in dataflow analysis from the 1970s, with early work by Hecht and others. A niche variant, 'may-point-to' vs 'must-point-to', distinguishes possible from definite targets. In hardware description languages like Verilog, points-to analysis is used for pointer-like constructs in simulation. Also, some analyses handle 'unknown' pointers from external calls conservatively, affecting precision.

Alias analysis

Determines when two pointers may refer to the same memory location.

Flow-insensitive

Ignores control flow order, treating the program as a set of statements.

Context-sensitive

Distinguishes calling contexts to improve precision.