Pointsto

Pointsto, short for points-to analysis, is a static program analysis technique used to determine the set of objects that a pointer may reference during program execution. The main output is a points-to relation that maps each pointer variable or field to the allocation sites or heap objects it may point to. This information supports alias analysis, memory-safety checks, and various compiler optimizations.

Analyses are characterized by precision versus performance along several dimensions: flow-sensitivity, context-sensitivity, and field-sensitivity. Flow-insensitive analyses disregard the order of statements, trading precision for speed. Context-insensitive analyses merge call sites, simplifying interprocedural reasoning. Field-insensitive analyses ignore the memory layout of composite data structures, while field-sensitive analyses distinguish between different fields. More precise variants that are flow-, context-, and field-sensitive offer better results but incur higher computational cost.

Two widely cited approaches are Andersen’s inclusion-based algorithm and Steensgaard’s unification-based algorithm. Andersen’s algorithm solves a system of inclusion constraints to build a points-to graph and is relatively scalable and precise for many languages. Steensgaard’s algorithm uses unifications to achieve high speed at the expense of significant precision loss. Real-world tools often mix ideas from these families and add selective sensitivity (e.g., context and field), sometimes using demand-driven or modular analysis to manage scalability.

Applications of pointsto analysis include improving indirect call resolution, enabling more effective dead code and alias-based optimizations, guiding garbage collection, and supporting memory-safety checks. Limitations arise from the inherent complexity of language features, interaction with dynamic memory, and the typical trade-off between analysis precision and performance. Allocation sites (such as new or malloc) serve as the canonical sources of heap objects in most models, with null and field selections commonly represented in the points-to relation.