Static single-assignment form: Difference between revisions

Revision as of 06:34, 21 March 2025

Latest revision as of 03:34, 11 August 2025

(6 intermediate revisions by 4 users not shown)

Line 9:

|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://wwwbernsteinbear.cs.purdue.educom/homesassets/suresh/502-Fall2008/papersimg/kelsey-ssa-cps.pdf}}</ref>

}}</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 journalbook |last1=Cytron |first1=Ron |last2=Lowry |first2=Andy |last3=Zadeck |first3=F. Kenneth |title=Code motion of control structures in high-level languages |journal=Proceedings of the 13th ACM SIGACT-SIGPLAN Symposiumsymposium on Principles of Programmingprogramming Languageslanguages - 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 journalbook|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|title=Global value numbers and redundant computations|year=1988|journal=Proceedings ofpages the= 15th12–27| ACMdoi SIGPLAN-SIGACT= Symposium10.1145/73560.73562| onisbn Principles= of Programming Languages0-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

Line 33 ⟶ 32:

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

* [[Constant propagationfolding]] – 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

Line 158 ⟶ 157:

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

Line 178:

* 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 [httphttps://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.