Editing Static single-assignment form (section)

{{Short description|Property of an intermediate representation in a compiler}}
In [[compiler]] design, '''static single assignment form''' (often abbreviated as '''SSA form''' or simply '''SSA''') is a type of [[intermediate representation]] (IR) where each [[Variable (computer science)|variable]] is [[Assignment (computer science)|assigned]] exactly once. SSA is used in most high-quality optimizing compilers for imperative languages, including [[LLVM]], the [[GNU Compiler Collection]], and many commercial compilers.

There are efficient algorithms for converting programs into SSA form. To convert to SSA, existing variables in the original IR are split into versions, new variables typically indicated by the original name with a subscript, so that every definition gets its own version. Additional statements that assign to new versions of variables may also need to be introduced at the join point of two control flow paths. Converting from SSA form to machine code is also efficient.

SSA makes numerous analyses needed for optimizations easier to perform, such as determining [[use-define chain]]s, because when looking at a use of a variable there is only one place where that variable may have received a value. Most optimizations can be adapted to preserve SSA form, so that one optimization can be performed after another with no additional analysis. The SSA based optimizations are usually more efficient and more powerful than their non-SSA form prior equivalents.

In [[functional language]] compilers, such as those for [[Scheme (programming language)|Scheme]] and [[ML programming language|ML]], [[continuation-passing style]] (CPS) is generally used. SSA is formally equivalent to a well-behaved subset of CPS excluding non-local control flow, so optimizations and transformations formulated in terms of one generally apply to the other. Using CPS as the intermediate representation is more natural for higher-order functions and interprocedural analysis. CPS also easily encodes [[call/cc]], whereas SSA does not.<ref name="Kelsey">{{cite book
|first1=Richard A. |last1=Kelsey
|title=Papers from the 1995 ACM SIGPLAN workshop on Intermediate representations |chapter=A correspondence between continuation passing style and static single assignment form |year=1995 |pages=13–22
|isbn=0897917545 |doi=10.1145/202529.202532 |s2cid=6207179 |chapter-url=https://www.cs.purdue.edu/homes/suresh/502-Fall2008/papers/kelsey-ssa-cps.pdf
}}</ref>