# Steensgaard's algorithm

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Steensgaard's_algorithm
> Markdown URL: https://mediated.wiki/source/Steensgaard's_algorithm.md
> Source: https://en.wikipedia.org/wiki/Steensgaard's_algorithm
> Source revision: 1289731029
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [computer science](/source/Computer_Science), '''Steensgaard's algorithm''' is a scalable, flow-insensitive, algorithm for [pointer analysis](/source/pointer_analysis). It is often used in [compiler](/source/compiler)s, due to its speed (for example, an implementation is available in the [LLVM](/source/LLVM) compiler framework).<ref>{{Cite web |title=LLVM Alias Analysis Infrastructure — LLVM 8 documentation |url=https://releases.llvm.org/8.0.0/docs/AliasAnalysis.html#the-steens-aa-pass |access-date=2022-04-22 |website=releases.llvm.org}}</ref> In its original formulation, this algorithm was field-, context-, and array-insensitive.

Steensgaard's algorithm is based on ''equality constraints'',<ref>{{harv|Smaragdakis|Balatsouras|2015|p=14}}</ref> as opposed to [Andersen's algorithm](/source/Andersen's_algorithm), which is based on ''subset constraints''. This allows points-to information to be tracked using a [union-find data structure](/source/Disjoint-set_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](/source/type_inference) and [type checking](/source/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](/source/C_(programming_language)). The language semantics and typing rules constitute the analysis.

==References==
{{Reflist}}
*{{cite conference
| url           =https://www.cs.cornell.edu/courses/cs711/2005fa/papers/steensgaard-popl96.pdf
| title         =Points-to analysis in almost linear time
| last = Steensgaard | first = Bjarne
| year          =1996
| book-title     =POPL '96: Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages
| pages         =32–41
| doi = 10.1145/237721.237727
| isbn          =0-89791-769-3
| location = New York, NY, USA
| publisher     =ACM
}}
*{{cite journal
 |last1=Smaragdakis
 |first1=Yannis
 |last2=Balatsouras
 |first2=George
 |date=2015
 |title=Pointer Analysis
 |url=https://yanniss.github.io/points-to-tutorial15.pdf
 |journal=Foundations and Trends in Programming Languages
 |volume=2
 |issue=1
 |pages=1–69
 |access-date=May 30, 2019
|doi=10.1561/2500000014
 }}

Category:Static program analysis

{{algorithm-stub}}

---
Adapted from the Wikipedia article [Steensgaard's algorithm](https://en.wikipedia.org/wiki/Steensgaard's_algorithm) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Steensgaard's_algorithm?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.