Static single-assignment form: Difference between revisions

Revision as of 03:50, 5 May 2023

Revision as of 10:56, 30 May 2023

Line 1:

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 webarXiv |titleeprint=Efficient global register allocation2011.05608 |archive-urllast1=https://archive.is/APaLCRogers |archive-datefirst1=20 Feb 2023Ian |access-datetitle=19Efficient Janglobal 2023register |url=https://www.arxiv-vanity.com/papers/2011.05608/allocation |lastyear=Rodgers2020 |firstclass=Iancs.PL |work=Google}}</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 journal

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

|first1=Richard A. |last1=Kelsey

Line 10:

== 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 presentationconference|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 symposiumSymposium on Principles of programming languagesProgramming 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=http://www1.cse.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 journal |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 programming languagesProgramming Languages - POPL '88 |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

Line 165:

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

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

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

* [[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/apple/swift/blob/master/docs/SIL.rst|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]]}}{{cbignore}}</ref>

Line 176:

===General references===

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