Static single-assignment form: Difference between revisions

Revision as of 05:03, 22 February 2024

Revision as of 05:07, 22 February 2024

Line 84:

There is an efficient algorithm for finding dominance frontiers of each node. This algorithm was originally described in "Efficiently Computing Static Single Assignment Form and the Control Graph" by Ron Cytron, Jeanne Ferrante, et al. in 1991.<ref>{{cite journal |last1=Cytron |first1=Ron |last2=Ferrante |first2=Jeanne |last3=Rosen |first3=Barry K. |last4=Wegman |first4=Mark N. |last5=Zadeck |first5=F. Kenneth |title=Efficiently computing static single assignment form and the control dependence graph |journal=ACM Transactions on Programming Languages and Systems |date=1 October 1991 |volume=13 |issue=4 |pages=451–490 |doi=10.1145/115372.115320|s2cid=13243943 |doi-access=free }}</ref>

Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy of [[Rice University]] describe an algorithm in their paper titled ''A Simple, Fast Dominance Algorithm'':<ref name="Cooper_2001">{{cite technicaltech report

|title=A Simple, Fast Dominance Algorithm |id=Rice University, CS Technical Report 06-33870

|last1=Cooper |first1=Keith D. |last2=Harvey |first2=Timothy J. |last3=Kennedy |first3=Ken |year=2001 |url=https://www.cs.rice.edu/~keith/EMBED/dom.pdf |archive-url=https://web.archive.org/web/20220326234549/https://www.cs.rice.edu/~keith/EMBED/dom.pdf |archive-date=2022-03-26 |url-status=dead}}</ref>

Line 113:

===Semi-pruned SSA===

Semi-pruned SSA form<ref>{{cite technicaltech report |title=Practical Improvements to the Construction and Destruction of Static Single Assignment Form |year=1998 |last1=Briggs |first1=Preston |last2=Cooper |first2=Keith D. |last3=Harvey |first3=Timothy J. |last4=Simpson |first4=L. Taylor |url=http://www.cs.rice.edu/~harv/my_papers/ssa.pdf |url-status=dead |archive-url=https://web.archive.org/web/20100607003509/http://www.cs.rice.edu/~harv/my_papers/ssa.pdf |archive-date=2010-06-07 }}</ref> is an attempt to reduce the number of Φ functions without incurring the relatively high cost of computing live-variable information. It is based on the following observation: if a variable is never live upon entry into a basic block, it never needs a Φ function. During SSA construction, Φ functions for any "block-local" variables are omitted.

Computing the set of block-local variables is a simpler and faster procedure than full live-variable analysis, making semi-pruned SSA form more efficient to compute than pruned SSA form. On the other hand, semi-pruned SSA form will contain more Φ functions.

Line 162:

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

* Reservoir Labs' R-Stream compiler supports non-SSA (quad list), SSA and SSI (Static Single Information<ref>{{cite technicaltech 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>

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