Static single-assignment form: Difference between revisions

Revision as of 01:13, 14 July 2023

Revision as of 04:37, 9 August 2023

Line 2:

In [[compiler]] design, '''static single assignment form''' (often abbreviated as '''SSA form''' or simply '''SSA''') is a property of an [[intermediate representation]] (IR) that requires each [[Variable (computer science)|variable]] to be [[Assignment (computer science)|assigned]] exactly once and defined before it is used. Existing variables in the original IR are split into ''versions'', new variables typically indicated by the original name with a subscript in textbooks, so that every definition gets its own version. In SSA form, [[use-define chain|use-def chains]] are explicit and each contains a single element.

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 journalbook

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

|first1=Richard A. |last1=Kelsey

|year=1995 |journaltitle=Papers from the 1995 ACM SIGPLAN Workshopworkshop on Intermediate Representationsrepresentations |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.

== History ==

SSA was developed in the 1980s by several researchers at [[International Business Machines|IBM]] and Kenneth Zadeck of Brown University.{{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 journal |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 Symposium on Principles of Programming Languages - POPL '86 |date=1986 |pages=70–85 |doi=10.1145/512644.512651|s2cid=9099471 }}</ref> A subsequent 1987 paper<ref>Cytron, Ronald Kaplan, and Jeanne Ferrante. What's in a name? Or, the value of renaming for parallelism detection and storage allocation. IBM TJ Watson Research Center, 1987.</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 journal|author1 = Barry Rosen| author2 = Mark N. Wegman|author3 = F. Kenneth Zadeck| url=https://www.cs.wustl.edu/~cytron/cs531/Resources/Papers/valnum.pdf|title=Global value numbers and redundant computations|year=1988|journal=Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages}}</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 "single static assignment".<ref>{{cite journalbook |last1=Alpern |first1=B. |last2=Wegman |first2=M. N. |last3=Zadeck |first3=F. K. |title=Detecting equality of variables in programs |journal=Proceedings of the 15th ACM SIGPLAN-SIGACT Symposiumsymposium on Principles of Programmingprogramming Languageslanguages - 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, and Zadeck and (independently) Cytron and Ferrante worked on methods of computing SSA form. A few days before the submission deadline, the researchers realized they had substantially the same algorithm,<ref name=Zadeck/> and a 5-author paper was the result.<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