Anonymous

Compiler Design: Difference between revisions

From dankwiki
427 bytes added ,  06:31, 29 April 2009
Line 30: Line 30:


===Intermediate Representations===
===Intermediate Representations===
* SSA (Single Static Assignment) and CPS (Continuation-Passing Style) are equivalent (Kelsey 1995, Appel 1998 '''FIXME full citations!''')
* Code is in ''Three-operand'' form iff instructions have no more than 1 destination and no more than 2 sources
* Three-operand code is in ''Single Static Assignment'' form iff for each variable, that variable is defined at most once, and that definition dominates every use of said variable.
** This requires the introduction of Φ-nodes, unions of possible values used in definitions ('''FIXME''' describe dominance frontiers etc, develop all of this)
* SSA and CPS (Continuation-Passing Style) are equivalent (Kelsey 1995, Appel 1998 '''FIXME full citations!''')
* SSA makes use-def chains explicit, and restricts them to a single element each
* SSA makes use-def chains explicit, and restricts them to a single element each
* It's much easier to perform global value numbering optimizations in this representation (see Muchnick, p378-396)
* It's much easier to perform global value numbering optimizations in this representation (see Muchnick, p378-396)