computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...

, Steensgaard's algorithm is a scalable, flow-insensitive, algorithm for

pointer analysis In computer science, pointer analysis, or points-to analysis, is a static code analysis technique that establishes which pointers, or heap references, can point to which variables, or storage locations. It is often a component of more complex ana ...

. It is often used in

compiler In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...

s, due to its speed (for example, an implementation is available in the

LLVM LLVM is a set of compiler and toolchain technologies that can be used to develop a front end for any programming language and a back end for any instruction set architecture. LLVM is designed around a language-independent intermediate repre ...

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 In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set ...

. 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 Type inference refers to the automatic detection of the type of an expression in a formal language. These include programming languages and mathematical type systems, but also natural languages in some branches of computer science and linguistics. ...

and

type checking In computer programming, a type system is a logical system comprising a set of rules that assigns a property called a type to every "term" (a word, phrase, or other set of symbols). Usually the terms are various constructs of a computer program ...

. 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

* *{{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 Static program analysis