Lesson plan
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). In its original formulation, this algorithm was field-, context-, and array-insensitive. Steensgaard's algorithm is based on equality constraints, 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.
Article summary
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). In its original formulation, this algorithm was field-, context-, and array-insensitive. Steensgaard's algorithm is based on equality constraints, 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.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.