Steensgaard's algorithm
In computer science, Steensgaard's algorithm is a scalable, flow-insensitive, algorithm for pointer analysis. It is often used in compilers, due to its speed (for example, an implementation is available in the LLVM compiler framework).[1] In its original formulation, this algorithm was field-, context-, and array-insensitive.
Steensgaard's algorithm is based on equality constraints,[2] as opposed to Andersen's algorithm, which is based on subset constraints. This allows points-to information to be tracked using a union-find data structure. This choice gives the algorithm its characteristic speed; when implemented using a union-find data structure it is linear space and almost linear time in the size of the input program.
Bjarne Steensgaard's formulation of the algorithm was in terms of type inference and type checking. Steensgaard proposed the points-to analysis for a small imperative but generic pointer language which captures the essential properties of other common languages with pointers, like C. The language semantics and typing rules constitute the analysis.
References
[edit]- ^ "LLVM Alias Analysis Infrastructure — LLVM 8 documentation". releases.llvm.org. Retrieved 2022-04-22.
- ^ (Smaragdakis & Balatsouras 2015, p. 14)
- Steensgaard, Bjarne (1996). "Points-to analysis in almost linear time" (PDF). POPL '96: Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages. New York, NY, USA: ACM. pp. 32–41. doi:10.1145/237721.237727. ISBN 0-89791-769-3.
- Smaragdakis, Yannis; Balatsouras, George (2015). "Pointer Analysis" (PDF). Foundations and Trends in Programming Languages. 2 (1): 1–69. doi:10.1561/2500000014. Retrieved May 30, 2019.