Static single-assignment form: Difference between revisions

Revision as of 06:12, 29 March 2023

Revision as of 10:05, 9 April 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.

SSA was proposed by [[Barry Rosen (computer scientist)|Barry K. Rosen]], [[Mark N. Wegman]], and [[F. Kenneth Zadeck]] in 1988.<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>. Zadeck shared a brief history of how SSA came into being in his presentation [https://compilers.cs.uni-saarland.de/ssasem/talks/Kenneth.Zadeck.pdf The Development of Static Single Assignment Form] at the "Static Single-Assignment Form Seminar"<ref>{{cite journal|title=Static Single-Assignment Form Seminar|author=Kenneth Zadeck|url=https://compilers.cs.uni-saarland.de/ssasem/}}</ref> conducted at the Saarland University. [[Ron Cytron]], [[Jeanne Ferrante]] and the previous three researchers at [[International Business Machines|IBM]] developed an algorithm that can compute the SSA form efficiently.<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