Static single-assignment form: Difference between revisions

Revision as of 11:02, 22 April 2005

Revision as of 23:59, 3 May 2005

Line 2:

SSA was developed by researchers at [[International Business Machines|IBM]] in the [[1980s]].

In [[functional language]] compilers, such as those for [[Scheme]], [[ML]] and [[Haskell]], [[continuation passing style]] (CPS) is generally used where one might expect to find SSA in a compiler for [[Fortran]] or [[C]].

== Benefits of SSA ==

Line 84 ⟶ 86:

Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy of [[Rice University]] describe an algorithm in their paper titled [http://www.hipersoft.rice.edu/grads/publications/dom14.pdf ''A Simple, Fast Dominance Algorithm'']. The algorithm uses well engineered data structures to improve performance.

== Pruned SSA ==

Pruned SSA removes even more phi functions by also considering variable liveness at phi function insertion points. For instance, if a phi function would be assigning to a dead (never used) variable, the phi function is unnecessary.

== Converting out of SSA form ==

As SSA form is no longer useful for direction execution, it is frequently used "on top of" another IR with which it remains in direct correspondence. This can be accomplished by "constructing" SSA as a set of functions which map between parts of the existing IR (basic blocks, instructions, operands, <i>etc.</i>) and its SSA counterpart. When the SSA form is no longer needed, these mapping functions may be discarded, leaving only the now-optimized IR.

If one absolutely needed to execute a program in SSA form, phi functions could be moved to the bottom of each of their predecessor blocks and then turned into simple move operations.

<i>Simple copy insertion, algorithms to reduce copies, etc. If overlapping lifetimes are allowed simply dropping the subscripts doesn't work. Pure SSA form doesn't really use subscripts anyway.</i>

Line 108 ⟶ 118:

* Although not a compiler, [http://boomerang.sourceforge.net/ Boomerang] (a [[decompiler]]) uses SSA form in its internal representation. Applicability of various SSA algorithms to [[decompilation]] is an active area of SSA research.

== Further Reading ==

Muchnick, Steven S. <i>Advanced Compiler Design and Implementation</i>. Morgan Kaufmann. 1997.

Cooper, Keith D. and Torczon, Linda. <i>Engineering a Compiler</i>. Morgan Kaufmann. 2005.

== See also ==