Static single-assignment form: Difference between revisions

Revision as of 20:26, 16 January 2024

Revision as of 08:20, 20 January 2024

Line 4:

One can expect to find SSA in a compiler for [[Fortran]], [[C (programming language)|C]], [[C++]],{{r|Kelsey}} or [[Java (programming language)|Java]] (Android Runtime);<ref>{{cite arXiv |eprint=2011.05608 |last1=Rogers |first1=Ian |title=Efficient global register allocation |year=2020 |class=cs.PL }}</ref><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> whereas 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, which does not occur when CPS is used as intermediate representation.<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 |date=1995 |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> So optimizations and transformations formulated in terms of one immediately apply to the other.

Line 82:

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.

There is an efficient algorithm for finding dominance frontiers of each node. This algorithm was originally described in “Efficiently"Efficiently Computing Static Single Assignment Form and the Control Graph”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>

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 journal

Line 135:

==Compilers using SSA form==

{{exampleexcessive farmexamples|section|date=August 2018}}

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

Line 142:

* 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 [[Open64]] compiler uses SSA form in its global scalar optimizer, though the code is brought into SSA form before and taken out of SSA form afterwards. Open64 uses extensions to SSA form to represent memory in SSA form as well as scalar values.

* Since the version 4 (released in April 2005) [[GNU Compiler Collection | GCC]], the [[GNU Compiler Collection]], makes extensive use of SSA. 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]].

* [[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.

* 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.