Static single-assignment form: Difference between revisions

Revision as of 02:42, 19 March 2005

Latest revision as of 03:34, 11 August 2025

(418 intermediate revisions by more than 100 users not shown)

Line 1:

{{Short description|Property of an intermediate representation in a compiler}}

In [[compilers]], '''static single assignment form''', more often abbreviated '''SSA form''' or just '''SSA''', is an [[intermediate representation]] in which every variable is assigned exactly once. Existing variables in the original IR are split into <i>versions</i>, new variables typically indicated by the original name with a subscript, so that every definition gets its own version. In SSA form, [[use-def chains]] are explicit and each contain a single element.

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 was developed by researchers at [[International Business Machines|IBM]] in the 80's.

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.

== Benefits of SSA ==

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://bernsteinbear.com/assets/img/kelsey-ssa-cps.pdf}}</ref>

== History ==

SSA was developed in the 1980s by several researchers at [[International Business Machines|IBM]]. Kenneth Zadeck, a key member of the team, moved to Brown University as development continued.{{sfn|Rastello|Tichadou|2022|loc=sec. 1.4}}<ref name=Zadeck>{{cite conference|title=The Development of Static Single Assignment Form|url=https://compilers.cs.uni-saarland.de/ssasem/talks/Kenneth.Zadeck.pdf|conference=Static Single-Assignment Form Seminar|first=Kenneth|last=Zadeck|conference-url=https://compilers.cs.uni-saarland.de/ssasem/|___location=Autrans, France|date=April 2009}}</ref> A 1986 paper introduced birthpoints, identity assignments, and variable renaming such that variables had a single static assignment.<ref>{{cite book |last1=Cytron |first1=Ron |last2=Lowry |first2=Andy |last3=Zadeck |first3=F. Kenneth |title=Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '86 |chapter=Code motion of control structures in high-level languages |date=1986 |pages=70–85 |doi=10.1145/512644.512651|s2cid=9099471 }}</ref> A subsequent 1987 paper by [[Jeanne Ferrante]] and Ronald Cytron<ref>{{cite conference |last1=Cytron |first1=Ronald Kaplan |first2=Jeanne |last2=Ferrante |title=What's in a name? Or, the value of renaming for parallelism detection and storage allocation |conference=International Conference on Parallel Processing, ICPP'87 1987 |pages=19–27}}</ref> proved that the renaming done in the previous paper removes all false dependencies for scalars.<ref name=Zadeck/> In 1988, Barry Rosen, [[Mark N. Wegman]], and Kenneth Zadeck replaced the identity assignments with Φ-functions, introduced the name "static single-assignment form", and demonstrated a now-common SSA optimization.<ref name="original">{{cite book|author1 = Barry Rosen| author2 = Mark N. Wegman|author3 = F. Kenneth Zadeck| title = Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '88| chapter = Global value numbers and redundant computations| chapter-url=https://www.cs.wustl.edu/~cytron/cs531/Resources/Papers/valnum.pdf|year=1988| pages = 12–27| doi = 10.1145/73560.73562| isbn = 0-89791-252-7}}</ref> The name Φ-function was chosen by Rosen to be a more publishable version of "phony function".<ref name=Zadeck/> Alpern, Wegman, and Zadeck presented another optimization, but using the name "static single assignment".<ref>{{cite book |last1=Alpern |first1=B. |last2=Wegman |first2=M. N. |last3=Zadeck |first3=F. K. |title=Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '88 |chapter=Detecting equality of variables in programs |date=1988 |pages=1–11 |doi=10.1145/73560.73561|isbn=0897912527 |s2cid=18384941 }}</ref> Finally, in 1989, Rosen, Wegman, Zadeck, Cytron, and Ferrante found an efficient means of converting programs to SSA form.<ref name="Cytron_1991">{{cite journal

|title=Efficiently computing static single assignment form and the control dependence graph

|author1=Cytron, Ron |author2=Ferrante, Jeanne |author3=Rosen, Barry K. |author4=Wegman, Mark N. |author5=Zadeck, F. Kenneth |name-list-style=amp |journal=ACM Transactions on Programming Languages and Systems |volume=13 |year=1991 |pages=451&ndash;490 |url=http://www.cs.utexas.edu/~pingali/CS380C/2010/papers/ssaCytron.pdf |issue=4

|doi=10.1145/115372.115320 |citeseerx=10.1.1.100.6361 |s2cid=13243943 }}</ref>

==Benefits==

The primary usefulness of SSA comes from how it simultaneously simplifies and improves the results of a variety of [[compiler optimization]]s, by simplifying the properties of variables. For example, consider this piece of code:

y := 1<br>

y := 2<br>

x := y<br>

Humans can see that the first assignment is not necessary, and that the value of <code>y</code> being used in the third line comes from the second assignment of <code>y</code>. A program would have to perform [[reaching definition|reaching definition analysis]] to determine this. But if the program is in SSA form, both of these are immediate:

y₁ := 1

y₂ := 2

x₁ := y₂

[[Compiler optimization]] algorithms that are either enabled or strongly enhanced by the use of SSA include:

* [[Constant folding]] – conversion of computations from runtime to compile time, e.g. treat the instruction <code>a=3*4+5;</code> as if it were <code>a=17;</code>

* [[Value range propagation]]<ref>[http://llvm.org/devmtg/2007-05/05-Lewycky-Predsimplify.pdf value range propagation]</ref> – precompute the potential ranges a calculation could be, allowing for the creation of branch predictions in advance

* [[Sparse conditional constant propagation]] – range-check some values, allowing tests to predict the most likely branch

* [[Dead-code elimination]] – remove code that will have no effect on the results

* [[Global value numbering]] – replace duplicate calculations producing the same result

* [[Partial-redundancy elimination]] – removing duplicate calculations previously performed in some branches of the program

* [[Strength reduction]] – replacing expensive operations by less expensive but equivalent ones, e.g. replace integer multiply or divide by powers of 2 with the potentially less expensive shift left (for multiply) or shift right (for divide).

* [[Register allocation]] – optimize how the limited number of machine registers may be used for calculations

==Converting to SSA==

Converting ordinary code into SSA form is primarily a matter of replacing the target of each assignment with a new variable, and replacing each use of a variable with the "version" of the variable [[reaching definition|reaching]] that point. For example, consider the following [[control-flow graph]]:

[[Image:SSA example1.1.png|An example control-flow graph, before conversion to SSA|center]]

Changing the name on the left hand side of "x <math>\leftarrow</math> x - 3" and changing the following uses of <var>x</var> to that new name would leave the program unaltered. This can be exploited in SSA by creating two new variables: <var>x</var>₁ and <var>x</var>₂, each of which is assigned only once. Likewise, giving distinguishing subscripts to all the other variables yields:

[[Image:SSA example1.2.png|An example control-flow graph, partially converted to SSA|center]]

It is clear which definition each use is referring to, except for one case: both uses of <var>y</var> in the bottom block could be referring to either <var>y</var>₁ or <var>y</var>₂, depending on which path the control flow took.

To resolve this, a special statement is inserted in the last block, called a ''Φ (Phi) function''. This statement will generate a new definition of ''y'' called <var>y</var>₃ by "choosing" either <var>y</var>₁ or <var>y</var>₂, depending on the control flow in the past.

[[Image:SSA example1.3.png|An example control-flow graph, fully converted to SSA|center]]

Now, the last block can simply use <var>y</var>₃, and the correct value will be obtained either way. A Φ function for ''x'' is not needed: only one version of <var>x</var>, namely <var>x</var>₂ is reaching this place, so there is no problem (in other words, Φ(<var>x</var>₂,<var>x</var>₂)=<var>x</var>₂).

Given an arbitrary control-flow graph, it can be difficult to tell where to insert Φ functions, and for which variables. This general question has an efficient solution that can be computed using a concept called ''dominance frontiers'' (see below).

Φ functions are not implemented as machine operations on most machines. A compiler can implement a Φ function by inserting "move" operations at the end of every predecessor block. In the example above, the compiler might insert a move from <var>y</var>₁ to <var>y</var>₃ at the end of the middle-left block and a move from <var>y</var>₂ to <var>y</var>₃ at the end of the middle-right block. These move operations might not end up in the final code based on the compiler's [[register allocation]] procedure. However, this approach may not work when simultaneous operations are speculatively producing inputs to a Φ function, as can happen on [[wide-issue]] machines. Typically, a wide-issue machine has a selection instruction used in such situations by the compiler to implement the Φ function.

===Computing minimal SSA using dominance frontiers===

In a control-flow graph, a node A is said to ''{{dfn|strictly [[dominator (graph theory)|dominate]]}}'' a different node B if it is impossible to reach B without passing through A first. In other words, if node B is reached, then it can be assumed that A has run. A is said to ''dominate'' B (or B to ''be dominated by'' A) if either A strictly dominates B or A = B.

A node which transfers control to a node A is called an ''{{dfn|immediate predecessor}}'' of A.

The ''{{dfn|dominance frontier}}'' of node A is the set of nodes B where A {{em|does not}} strictly dominate B, but does dominate some immediate predecessor of B. These are the points at which multiple control paths merge back together into a single path.

For example, in the following code:

As humans, we can see that the first assignment is not necessary, and that the value of <code>y</code> being used in the third line comes from the second assignment of <code>y</code>. A program would have to perform [[reaching definition|reaching definition analysis]] to determine this. But if the program is in SSA form, both of these are immediate:

<pre>

y₁ := 1<br>

[1] x = random()

y₂ := 2<br>

if x < 0.5

x₁ := y₂<br>

[2] result = "heads"

else

[3] result = "tails"

end

[4] print(result)

</pre>

Node 1 strictly dominates 2, 3, and 4 and the immediate predecessors of node 4 are nodes 2 and 3.

[[Compiler optimization]] algorithms which are either permitted or strongly enhanced by the use of SSA include:

*[[constant propagation]]

*[[sparse conditional constant propagation]]

*[[dead code elimination]]

*[[global value numbering]]

*[[partial redundancy elimination]]

*[[register allocation]]

Dominance frontiers define the points at which Φ functions are needed. In the above example, when control is passed to node 4, the definition of <code>result</code> used depends on whether control was passed from node 2 or 3. Φ functions are not needed for variables defined in a dominator, as there is only one possible definition that can apply.

== Converting to SSA ==

There is an efficient algorithm for finding dominance frontiers of each node. This algorithm was originally described in "Efficiently Computing Static Single Assignment Form and the Control Graph" by Ron Cytron, Jeanne Ferrante, et al. in 1991.<ref>{{cite journal |last1=Cytron |first1=Ron |last2=Ferrante |first2=Jeanne |last3=Rosen |first3=Barry K. |last4=Wegman |first4=Mark N. |last5=Zadeck |first5=F. Kenneth |title=Efficiently computing static single assignment form and the control dependence graph |journal=ACM Transactions on Programming Languages and Systems |date=1 October 1991 |volume=13 |issue=4 |pages=451–490 |doi=10.1145/115372.115320|s2cid=13243943 |doi-access=free }}</ref>

=== Introduction ===

Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy of [[Rice University]] describe an algorithm in their paper titled ''A Simple, Fast Dominance Algorithm'':<ref name="Cooper_2001">{{cite tech report

Converting ordinary code into SSA form is primarily a simple matter of replacing the target of each assignment with a new variable, and replacing each use of a variable with the "version" of the variable [[reaching definition|reaching]] that point. For example, consider the following [[control flow graph]]:

|title=A Simple, Fast Dominance Algorithm |id=Rice University, CS Technical Report 06-33870

|last1=Cooper |first1=Keith D. |last2=Harvey |first2=Timothy J. |last3=Kennedy |first3=Ken |year=2001 |url=https://www.cs.rice.edu/~keith/EMBED/dom.pdf |archive-url=https://web.archive.org/web/20220326234549/https://www.cs.rice.edu/~keith/EMBED/dom.pdf |archive-date=2022-03-26 |url-status=dead}}</ref>

'''for each''' node b

<center>

dominance_frontier(b) := {}

[[Image:SSA_example1.1.png|An example control flow graph, before conversion to SSA]]

'''for each''' node b

</center>

'''if''' the number of immediate predecessors of b ≥ 2

'''for each''' p '''in''' immediate predecessors of b

runner := p

'''while''' runner ≠ idom(b)

dominance_frontier(runner) := dominance_frontier(runner) ∪ { b }

runner := idom(runner)

In the code above, <code>idom(b)</code> is the ''{{dfn|immediate dominator}}'' of b, the unique node that strictly dominates b but does not strictly dominate any other node that strictly dominates b.

Notice that we could change the name on the left side of "x <math>\leftarrow</math> x - 3", and change the following uses of <var>x</var> to use that new name, and the program would still do the same thing. We exploit this in SSA by create two new variables, <var>x</var>₁ and <var>x</var>₂, each of which is assigned only once. We likewise give distinguishing subscripts to all the other variables, and we get this:

==Variations that reduce the number of Φ functions==

<center>

"Minimal" SSA inserts the minimal number of Φ functions required to ensure that each name is assigned a value exactly once and that each reference (use) of a name in the original program can still refer to a unique name. (The latter requirement is needed to ensure that the compiler can write down a name for each operand in each operation.)

[[Image:SSA_example1.2.png|An example control flow graph, partially converted to SSA]]

</center>

However, some of these Φ functions could be ''[[dead code elimination|dead]]''. For this reason, minimal SSA does not necessarily produce the fewest Φ functions that are needed by a specific procedure. For some types of analysis, these Φ functions are superfluous and can cause the analysis to run less efficiently.

We've figured out which definition each use is referring to, except for one thing: the uses of <var>y</var> in the bottom block could be referring to <i>either</i> <var>y</var>₁ or <var>y</var>₂, depending on which way the control flow came from. So how do we know which one to use?

===Pruned SSA===

The answer is that we add a special statement, called a <i>&phi; (phi) function</i>, to the beginning of the last block. This statement will generate a new definition of <var>y</var>, <var>y</var>₃, by "choosing" either <var>y</var>₁ or <var>y</var>₂, depending on which arrow control arrived from:

Pruned SSA form is based on a simple observation: Φ functions are only needed for variables that are "live" after the Φ function. (Here, "live" means that the value is used along some path that begins at the Φ function in question.) If a variable is not live, the result of the Φ function cannot be used and the assignment by the Φ function is dead.

Construction of pruned SSA form uses [[live-variable analysis|live-variable information]] in the Φ function insertion phase to decide whether a given Φ function is needed. If the original variable name isn't live at the Φ function insertion point, the Φ function isn't inserted.

<center>

[[Image:SSA_example1.3.png|An example control flow graph, fully converted to SSA]]

</center>

Another possibility is to treat pruning as a [[dead-code elimination]] problem. Then, a Φ function is live only if any use in the input program will be rewritten to it, or if it will be used as an argument in another Φ function. When entering SSA form, each use is rewritten to the nearest definition that dominates it. A Φ function will then be considered live as long as it is the nearest definition that dominates at least one use, or at least one argument of a live Φ.

Now, the uses of <var>y</var> in the last block can simply use <var>y</var>₃, and they'll obtain the correct value either way. You might ask at this point, do we need to add a &phi; function for <var>x</var> too? The answer is no; only one version of <var>x</var>, namely <var>x</var>₂ is reaching this place, so there's no problem.

===Semi-pruned SSA===

A more general question along the same lines is, given an arbitrary control flow graph, how can I tell where to insert &phi; functions, and for what variables? This is a difficult question, but one that has an efficient solution that can be computed using a concept called <i>dominance frontiers</i>.

Semi-pruned SSA form<ref>{{cite tech report |title=Practical Improvements to the Construction and Destruction of Static Single Assignment Form |year=1998 |last1=Briggs |first1=Preston |last2=Cooper |first2=Keith D. |last3=Harvey |first3=Timothy J. |last4=Simpson |first4=L. Taylor |url=http://www.cs.rice.edu/~harv/my_papers/ssa.pdf |url-status=dead |archive-url=https://web.archive.org/web/20100607003509/http://www.cs.rice.edu/~harv/my_papers/ssa.pdf |archive-date=2010-06-07 }}</ref> is an attempt to reduce the number of Φ functions without incurring the relatively high cost of computing live-variable information. It is based on the following observation: if a variable is never live upon entry into a basic block, it never needs a Φ function. During SSA construction, Φ functions for any "block-local" variables are omitted.

Computing the set of block-local variables is a simpler and faster procedure than full live-variable analysis, making semi-pruned SSA form more efficient to compute than pruned SSA form. On the other hand, semi-pruned SSA form will contain more Φ functions.

=== Computing minimal SSA using dominance frontiers ===

===Block arguments===

First, we need the concept of a ''dominator'': we say that a node A ''strictly dominates'' a different node B in the control flow graph if it's impossible to reach B without passing through A first. This is useful, because if we ever reach B we know that any code in A has run. We say that A ''dominates'' B if either A strictly dominates B or A = B.

Block arguments are an alternative to Φ functions that is representationally identical but in practice can be more convenient during optimization. Blocks are named and take a list of block arguments, notated as function parameters. When calling a block the block arguments are bound to specified values. [[MLton]], [[Swift (programming language)|Swift]] SIL, and LLVM [[MLIR (software)|MLIR]] use block arguments.<ref>{{cite web |title=Block Arguments vs PHI nodes - MLIR Rationale |url=https://mlir.llvm.org/docs/Rationale/Rationale/#block-arguments-vs-phi-nodes |website=mlir.llvm.org |access-date=4 March 2022}}</ref>

Now we can define the ''dominance frontier'': the dominance frontier of a node A is the set of nodes that A does ''not'' strictly dominate, but does dominate some immediate precessor of. From A's point of view, these are the nodes at which other control paths that don't go through A make their earliest appearance.

==Converting out of SSA form==

<!-- Need an example -->

SSA form is not normally used for direct execution (although it is possible to interpret SSA<ref>{{cite book

|chapter=Interpreting programs in static single assignment form |year=2004 |last=von Ronne |first=Jeffery |author2=Ning Wang |author3=Michael Franz |title=Proceedings of the 2004 workshop on Interpreters, virtual machines and emulators - IVME '04 |page=23 |doi=10.1145/1059579.1059585 |isbn=1581139098 |s2cid=451410 |url=https://escholarship.org/uc/item/98n3s5r5 |chapter-url=http://dl.acm.org/citation.cfm?doid=1059579.1059585 }}</ref>), and it is frequently used "on top of" another IR with which it remains in direct correspondence. This can be accomplished by "constructing" SSA as a set of functions that map between parts of the existing IR (basic blocks, instructions, operands, ''etc.'') and its SSA counterpart. When the SSA form is no longer needed, these mapping functions may be discarded, leaving only the now-optimized IR.

Performing optimizations on SSA form usually leads to entangled SSA-Webs, meaning there are Φ instructions whose operands do not all have the same root operand. In such cases [[graph coloring|color-out]] algorithms are used to come out of SSA. Naive algorithms introduce a copy along each predecessor path that caused a source of different root symbol to be put in Φ than the destination of Φ. There are multiple algorithms for coming out of SSA with fewer copies, most use interference graphs or some approximation of it to do copy coalescing.<ref>{{cite journal |last1=Boissinot |first1=Benoit |last2=Darte |first2=Alain |last3=Rastello |first3=Fabrice |last4=Dinechin |first4=Benoît Dupont de |last5=Guillon |first5=Christophe |title=Revisiting Out-of-SSA Translation for Correctness, Code Quality, and Efficiency |journal=HAL-Inria Cs.DS |date=2008 |pages=14 |url=https://hal.inria.fr/inria-00349925 |language=en}}</ref>

Dominance frontiers capture the precise places at which we need &phi; functions: if the node A defines a certain variable, then that definition and that definition alone will reach every node A dominates. Only when we leave these nodes and enter the dominance frontier must be account for other flows bringing in other definitions of the same variable. Moreover, no other &phi; functions are needed in the control flow graph to deal with A's definitions, and we can do with no less.

==Extensions==

<!-- Describe the algorithm for finding dominance frontiers in the future -->

Extensions to SSA form can be divided into two categories.

''Renaming scheme'' extensions alter the renaming criterion. Recall that SSA form renames each variable when it is assigned a value. Alternative schemes include static single use form (which renames each variable at each statement when it is used) and static single information form (which renames each variable when it is assigned a value, and at the post-dominance frontier).

There is an efficient algorithm for finding dominance frontiers of each node. This algorithm was originally described in the paper "Efficiently computing static single assignment form and the

control dependence graph", by R. Cytron, J. Ferrante, B. Rosen, M. Wegman and F. Zadek,

<i>ACM Trans. on Programming Languages and Systems</i> 13(4) 1991 pp.451&ndash;490. Also useful is

chapter 19 of the book "Modern compiler implementation in Java" by Andrew Appel

(Cambridge University Press, 2002). See the paper for more details.

''Feature-specific'' extensions retain the single assignment property for variables, but incorporate new semantics to model additional features. Some feature-specific extensions model high-level programming language features like arrays, objects and aliased pointers. Other feature-specific extensions model low-level architectural features like speculation and predication.

== Converting out of SSA form ==

==Compilers using SSA form==

<i>Simple copy insertion, algorithms to reduce copies, etc. If overlapping lifetimes are allowed (which is critical to SSA form) simply dropping the subscripts doesn't work. Pure SSA form doesn't really use subscripts anyway.</i>

{{excessive examples|section|date=August 2018}}

=== Open-source ===

== Extensions to SSA form ==

* [[Mono (software)|Mono]] uses SSA in its JIT compiler called Mini

<i>Many possible extensions to talk about. Probably the most important are ones involving memory, gated SSA form, and array SSA form.</i>

* [[WebKit]] uses SSA in its JIT compilers.<ref>{{Cite web|url=https://webkit.org/blog/3362/introducing-the-webkit-ftl-jit/|title=Introducing the WebKit FTL JIT|date=13 May 2014}}</ref><ref>{{Cite web|url=https://webkit.org/blog/5852/introducing-the-b3-jit-compiler/|title=Introducing the B3 JIT Compiler|date=15 February 2016}}</ref>

* [[Swift (programming language)|Swift]] defines its own SSA form above LLVM IR, called SIL (Swift Intermediate Language).<ref>{{Cite web|url=https://github.com/swiftlang/swift/blob/main/docs/SIL/SIL.md|title=Swift Intermediate Language (GitHub)|website=[[GitHub]]|date=30 October 2021}}</ref><ref>{{Cite web|url=https://www.youtube.com/watch?v=Ntj8ab-5cvE |archive-url=https://ghostarchive.org/varchive/youtube/20211221/Ntj8ab-5cvE |archive-date=2021-12-21 |url-status=live|title=Swift's High-Level IR: A Case Study of Complementing LLVM IR with Language-Specific Optimization, LLVM Developers Meetup 10/2015|website=[[YouTube]]|date=9 November 2015 }}{{cbignore}}</ref>

* The [[Erlang (programming language)|Erlang]] compiler was rewritten in OTP 22.0 to "internally use an intermediate representation based on Static Single Assignment (SSA)", with plans for further optimizations built on top of SSA in future releases.<ref>{{Cite web|url=http://www.erlang.org/news/132|title=OTP 22.0 Release Notes}}</ref>

* The [[LLVM]] Compiler Infrastructure uses SSA form for all scalar register values (everything except memory) in its primary code representation. SSA form is only eliminated once register allocation occurs, late in the compile process (often at link time).

* The [[GNU Compiler Collection]] (GCC) makes extensive use of SSA since version 4 (released in April 2005). The [[front and back ends|frontends]] generate "[[GIMPLE#GENERIC and GIMPLE|GENERIC]]" code that is then converted into "[[GIMPLE#GENERIC and GIMPLE|GIMPLE]]" code by the "gimplifier". High-level optimizations are then applied on the SSA form of "GIMPLE". The resulting optimized intermediate code is then translated into [[Register Transfer Language|RTL]], on which low-level optimizations are applied. The architecture-specific [[Front and back ends|backend]]s finally turn RTL into [[assembly language]].

* [[Go (programming language)|Go]] (1.7: for x86-64 architecture only; 1.8: for all supported architectures).<ref>{{Cite web|url=https://golang.org/doc/go1.7#compiler|title=Go 1.7 Release Notes - The Go Programming Language|website=golang.org|access-date=2016-08-17}}</ref><ref>{{Cite web|url=https://golang.org/doc/go1.8#compiler|title=Go 1.8 Release Notes - The Go Programming Language|website=golang.org|access-date=2017-02-17}}</ref>

* [[IBM]]'s open source adaptive [[Java virtual machine]], [[Jikes RVM]], uses extended Array SSA, an extension of SSA that allows analysis of scalars, arrays, and object fields in a unified framework. Extended Array SSA analysis is only enabled at the maximum optimization level, which is applied to the most frequently executed portions of code.

* The [[Mozilla]] [[Firefox]] [[SpiderMonkey]] JavaScript engine uses SSA-based IR.<ref>{{cite web|url=https://wiki.mozilla.org/IonMonkey/Overview|title=IonMonkey Overview}},</ref>

* The [[Chromium (web browser)|Chromium]] [[V8 JavaScript engine]] implements SSA in its Crankshaft compiler infrastructure as [https://blog.chromium.org/2010/12/new-crankshaft-for-v8.html announced in December 2010]

* [[PyPy]] uses a linear SSA representation for traces in its JIT compiler.

* The [[Android Runtime]]<ref>{{cite video |title=The Evolution of ART - Google I/O 2016 |time=3m47s |url=https://www.youtube.com/watch?v=fwMM6g7wpQ8 |date=25 May 2016 |work=Google}}</ref> and the [[Dalvik (software)|Dalvik Virtual Machine]] use SSA.<ref>{{cite web |title=JIT through the ages |url=http://www.cs.columbia.edu/~aho/cs6998/reports/12-12-11_Ramanan_JIT.pdf |last=Ramanan |first=Neeraja | date=12 Dec 2011 }}</ref>

* The Standard ML compiler [[MLton]] uses SSA in one of its intermediate languages.

* [[LuaJIT]] makes heavy use of SSA-based optimizations.<ref>{{cite web|url=http://wiki.luajit.org/Optimizations|title=Bytecode Optimizations|publisher=the LuaJIT project}}</ref>

* The [[PHP]] and [[Hack (programming language)|Hack]] compiler [[HHVM]] uses SSA in its IR.<ref>{{cite web|url=https://github.com/facebook/hhvm/blob/master/hphp/doc/ir.specification|title=HipHop Intermediate Representation (HHIR)|website=[[GitHub]]|date=30 October 2021}}</ref>

* The [[OCaml]] compiler uses SSA in its CMM IR (which stands for C--).<ref>{{Cite web |last1=Chambart |first1=Pierre |last2=Laviron |first2=Vincent |last3=Pinto |first3=Dario |date=2024-03-18 |title=Behind the Scenes of the OCaml Optimising Compiler |url=https://ocamlpro.com/blog/2024_03_18_the_flambda2_snippets_0/ |website=OCaml Pro}}</ref>

* libFirm, a library for use as the [[Compiler#Three-stage compiler structure|middle and back ends of a compiler]], uses SSA form for all scalar register values until code generation by use of an SSA-aware register allocator.<ref>{{cite web|url=http://pp.ipd.kit.edu/firm/|title=Firm - Optimization and Machine Code Generation}}</ref>

* Various [[Mesa (computer graphics)|Mesa]] drivers via NIR, an SSA representation for shading languages.<ref>{{Cite web|url=https://lists.freedesktop.org/archives/mesa-dev/2014-December/072761.html|title=Reintroducing NIR, a new IR for mesa|last=Ekstrand|first=Jason|date=16 December 2014 }}</ref>

=== Commercial ===

== Compilers using SSA form ==

* [[Oracle Corporation|Oracle]]'s [[HotSpot (virtual machine)|HotSpot Java Virtual Machine]] uses an SSA-based intermediate language in its JIT compiler.<ref>{{cite web|url=https://www.oracle.com/java/technologies/whitepaper.html|publisher=Oracle Corporation|title=The Java HotSpot Performance Engine Architecture}}</ref>

SSA form is a relatively recent development in the compiler community. As such, many older compilers only use SSA form for some part of compilation or optimization process, but most do not rely on it. Examples of compilers that rely heavily on SSA form include:

* Microsoft [[Visual C++]] compiler backend available in [[Microsoft Visual Studio]] 2015 Update 3 uses SSA<ref>{{cite web|url=https://blogs.msdn.microsoft.com/vcblog/2016/05/04/new-code-optimizer|title=Introducing a new, advanced Visual C++ code optimizer|date=4 May 2016}}</ref>

* [[SPIR-V]], the shading language standard for the [[Vulkan (API)|Vulkan graphics API]] and [[compute kernel|kernel language]] for [[OpenCL]] compute API, is an SSA representation.<ref>{{cite web|url=https://www.khronos.org/registry/spir-v/specs/1.0/SPIRV.pdf|title=SPIR-V spec}}</ref>

* The IBM family of XL compilers, which include [[IBM XL C/C++ Compilers|C, C++]] and Fortran.<ref>{{cite journal|url=https://www.cs.rice.edu/~vs3/PDF/ibmjrd97.pdf|title=Automatic selection of high-order transformations in the IBM XL FORTRAN compilers|first=V.|last=Sarkar|journal=[[IBM Journal of Research and Development]]|volume=41|issue=3|pages=233–264|date=May 1997|publisher=IBM|doi=10.1147/rd.413.0233 }}</ref>

* NVIDIA [[CUDA]]<ref>{{cite journal|url=https://www.researchgate.net/publication/235605681|title=CUDA: Compiling and optimizing for a GPU platform|date=2012 |doi=10.1016/j.procs.2012.04.209 |last1=Chakrabarti |first1=Gautam |last2=Grover |first2=Vinod |last3=Aarts |first3=Bastiaan |last4=Kong |first4=Xiangyun |last5=Kudlur |first5=Manjunath |last6=Lin |first6=Yuan |last7=Marathe |first7=Jaydeep |last8=Murphy |first8=Mike |last9=Wang |first9=Jian-Zhong |journal=Procedia Computer Science |volume=9 |pages=1910–1919 |doi-access=free }}</ref>

=== Research and abandoned ===

* [http://llvm.org/ The LLVM Compiler Infrastructure] uses SSA form for all scalar register values (everything except memory) in its primary code representation. SSA form is only eliminated once register allocation occurs, late in the compile process (often at link time).

* The openETH source SGI[[Oberon-2]] compiler [http://ipf-orc.sourceforgewas one of the first public projects to incorporate "GSA", a variant of SSA.net/
* ORCThe [[Open64]] compiler usesused SSA form in its global scalar optimizer, though the code is brought into SSA form before and taken out of SSA form afterwards. ORCOpen64 uses extensions to SSA form to represent memory in SSA form as well as scalar values.

* In 2002, [http://citeseer.ist.psu.edu/721276.html researchers modified] IBM's JikesRVM (named Jalapeño at the time) to run both standard Java [[bytecode]] and a typesafe SSA ([[SafeTSA]]) bytecode class files, and demonstrated significant performance benefits to using the SSA bytecode.

* [http://jackcc.sf.net jackcc] is an open-source compiler for the academic instruction set Jackal 3.0. It uses a simple 3-operand code with SSA for its intermediate representation. As an interesting variant, it replaces Φ functions with a so-called SAME instruction, which instructs the register allocator to place the two live ranges into the same physical register.

* The Illinois Concert Compiler circa 1994<ref>{{cite web|url=http://www-csag.ucsd.edu/projects/concert.html|title=Illinois Concert Project|archive-url=https://web.archive.org/web/20140313140417/http://www-csag.ucsd.edu/projects/concert.html|archive-date=2014-03-13|url-status=dead}}</ref> used a variant of SSA called SSU (Static Single Use) which renames each variable when it is assigned a value, and in each conditional context in which that variable is used; essentially the static single information form mentioned above. The SSU form is documented in [http://www-csag.ucsd.edu/papers/jplevyak-thesis.ps John Plevyak's Ph.D Thesis].

* The COINS compiler uses SSA form optimizations as explained [https://web.archive.org/web/20040531024854/http://www.is.titech.ac.jp/~sassa/coins-www-ssa/english/ here].

* Reservoir Labs' R-Stream compiler supports non-SSA (quad list), SSA and SSI (Static Single Information<ref>{{cite tech report |url=https://cscott.net/Publications/ssi.pdf |title=Static Single Information Form |last1=Ananian |first1=C. Scott |last2=Rinard |first2=Martin |year=1999|citeseerx = 10.1.1.1.9976}}</ref>) forms.<ref>{{cite book|url=https://www.springer.com/us/book/9780387097657|title=Encyclopedia of Parallel Computing}}</ref>

* Although not a compiler, the [https://boomerang.sourceforge.net/ Boomerang] decompiler uses SSA form in its internal representation. SSA is used to simplify expression propagation, identifying parameters and returns, preservation analysis, and more.

* [[DotGNU]] Portable.NET used SSA in its JIT compiler.

==References==

* As of summer [[2004]] the [[GNU Compiler Collection]] is being updated to use SSA form. The [[frontend|frontends]] generate [[GENERIC]] code which is then converted into SSA form by the "[[gimplifier]]" and optimized by the "[[middle-end]]". The [[backend]] eventually translates the optimized intermediate code into [[Register Transfer Language|RTL]], executes some more low-level optimizations and finally turns RTL into [[assembly language]]. The first official release supporting SSA will be 4.0, tentatively scheduled for early [[2005]].

===Notes===

* [[IBM]]'s open source adaptive [[Java virtual machine]], [http://jikesrvm.sourceforge.net/ Jikes RVM], uses Heap Array SSA, an extension of SSA that allows analysis of scalars, arrays, and object fields in a unified framework. Heap Array SSA analysis is only enabled at the maximum optimization level, which is applied to the most frequently executed portions of code.

{{Reflist|30em}}

===General references===

* Although not a compiler, [http://boomerang.sourceforge.net/ Boomerang] (a [[decompiler]]) uses SSA form in its internal representation. Applicability of various SSA algorithms to [[decompilation]] is an active area of SSA research.

* {{cite book |title=SSA-based compiler design |date=2022 |___location=Cham |isbn=978-3-030-80515-9 |doi=10.1007/978-3-030-80515-9 |s2cid=63274602 |language=en|editor-first1=Fabrice|editor-last1=Rastello|editor-first2=Florent Bouchez|editor-last2=Tichadou|url=https://pfalcon.github.io/ssabook/latest/book-full.pdf}}

* {{cite book |author=Appel, Andrew W.

|title=Modern Compiler Implementation in ML

|publisher=Cambridge University Press |year=1999 |isbn=978-0-521-58274-2 }} Also available in [[Java (programming language)|Java]] ({{ISBN|0-521-82060-X}}, 2002) and [[C (programming language)|C]] ({{ISBN|0-521-60765-5}}, 1998) versions.

* {{cite book |author1=Cooper, Keith D. |author2=Torczon, Linda |name-list-style=amp |title=Engineering a Compiler

|publisher=Morgan Kaufmann |year=2003 |isbn=978-1-55860-698-2 }}

* {{cite book |author=Muchnick, Steven S. |title=Advanced Compiler Design and Implementation |publisher=Morgan Kaufmann |year=1997 |isbn=978-1-55860-320-2 |url-access=registration |url=https://archive.org/details/advancedcompiler00much }}

* {{cite journal |author=Kelsey, Richard A.

|title=A Correspondence between Continuation Passing Style and Static Single Assignment Form

|journal=ACM SIGPLAN Notices |date=March 1995 |volume=30 |issue=3 |pages=13–22 |doi=10.1145/202530.202532 |doi-access=free }}

* {{cite journal |author=Appel, Andrew W.

|title=SSA is Functional Programming

|journal=ACM SIGPLAN Notices |date=April 1998 |volume=33 |issue=4 |pages=17–20 |doi=10.1145/278283.278285 |s2cid=207227209

|doi-access=free }}

* {{cite journal |author=Pop, Sebastian

|title=The SSA Representation Framework: Semantics, Analyses and GCC Implementation

|year=2006 |url=http://cri.ensmp.fr/people/pop/papers/2006-12-thesis.pdf }}

* {{citation |author1=Matthias Braun |title=Compiler Construction |author2=Sebastian Buchwald |author3=Sebastian Hack |author4=Roland Leißa |author5=Christoph Mallon |author6=Andreas Zwinkau | chapter=Simple and Efficient Construction of Static Single Assignment Form| year=2013| volume=7791| pages=102–122| publisher=Springer Berlin Heidelberg| series=Lecture Notes in Computer Science| doi=10.1007/978-3-642-37051-9_6| chapter-url=http://www.cdl.uni-saarland.de/projects/ssaconstr| accessdate=24 March 2013|isbn=978-3-642-37050-2 | doi-access=free}}

==External See also links==

* Bosscher, Steven; and Novillo, Diego. [https://lwn.net/Articles/84888/ GCC gets a new Optimizer Framework]. An article about GCC's use of SSA and how it improves over older IRs.

*[http://www.dcs.gla.ac.uk/~jsinger/ssa.html The SSA Bibliography]. Extensive catalogue of SSA research papers.

* Zadeck, F. Kenneth. [http://webcast.rice.edu/webcast.php?action=details&event=1346 "The Development of Static Single Assignment Form"], December 2007 talk on the origins of SSA.

* [[Category:Compiler optimizationoptimizations]]