09 November 2016
SSA serves as one universal analysis for multiple transformations.
Inserting \(\phi-functions\) at joints
Renaming such that only one definition reaches any use
However, too many extra \(phi\)-functions waste space and slow down the traversal.
For each block i, compute the set of blocks that will need a \(phi\)-function for any definition in block i. Block \(n \in DOM(m)\) does not force the presence of a \(\phi\)-function if there is a redefinition in some node p between n and m.
A definition in block n forces a corresponding \(phi\)-function at any join point \(m \in DF(n)\). Only insert \(phi\)-functions for global names that are live across multiple blocks.
Global Names \(= \bigcup_b UEVar(b)\)
Build global names and their definition block lists
For each name x, iteratively insert \(phi\)-function into the dominator frontier b of definition blocks of x
If \(x \in LiveOut(b) \), the SSA is pruned.
Splitting critical edges is the way to implement \(phi\)-functions.
Sometimes, the compiler avoids splitting critical edges:
The closing branch of a heavily executed loop may have an adverse performance impact
Adding blocks and edges in the late stages of compilation can interfere with
code placement and so on
However unsplit critical edges with copy folding causes the lost-copy problem. The compiler preserves the live value in a temporary name and rewrite usbsequent uses to refer to the temporary name if the liveness of the target name is outside the block for each copy inserted during the out-of-SSA translation.
The \(phi\)-functions are executed concurrently by reading parameters and defining the target values simultaneously. However, the translation of SSA from into sequential executable code may misinterpret the semantics. The swap problem can be detected when \(phi\)-functions reference the targets of other \(phi\)-functions in the same block.
Each SSA name is annotated with a value ranging from \(\top, \bot\), or \(c_i\). The set of possible values forms a semilattice. SSCP determines if a SSA name is constant in a block. First, SSCP initializes SSA names as follows.
\(\top\) from a \(phi\)-function
\(c_i\) from some known constant
\(\bot\) from some external input
Next, SSCP iterates by propagating SSA names defined to be some constant \(c_i\) and checking its uses. The target SSA names may be defined from \(\top\) to constant \(c_i\) or from constant \(c_i\) to \(\bot\) but no more. Interpreting a \(phi\)-function to to define a SSA name follows the rules below.
\(\top \wedge x = x, \forall x\)
\(\bot \wedge x = \bot, \forall x\)
\(c_i \wedge c_j = c_i\) if \(c_i = c_j\)
\(c_i \wedge c_j = \bot\) if \(c_i \not= c_j\)
Those SSA names end up with some constant \(c_i\) are propogated.
Discovering an Initial Set of Constants
Identify which actual parameters have known constant values
Literal constant values
Global constant propagation
Propagation Known Constant Values around the Call Graph
Modeling Transmission of Values through Procedures
Reduce phase: each time a subgraph is transformed into a node
\(T_2(a, b)\): b has only one predecessor a
Expansion phase: each time a node is expanded with computed data-flow sets
Failed to be reduced to a single node with \(T_1\) and \(T_2\)
More than two iterations required by iterative DOM framework using an RPO traversal order
There exists a loop or cycle that has edges entering it at different nodes
Node splitting to form cycles with one single entry
Structured programming without goto or break prevents irreducible graphs
Mutually recursive subroutines in recursive-descent parser is likely to have irreducible subgraphs
Build the dominator tree and find the DOM on demand
Traverse CFG upward by comparing RPO numbers until reaching a common prefix node as IDOM