Static single-assignment form: Difference between revisions

Revision as of 10:56, 30 May 2023

Revision as of 20:56, 15 June 2023

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 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=httphttps://www1www.csecs.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 Symposium on Principles of Programming 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