09 November 2016

SSA serves as one universal analysis for multiple transformations.

Maximal SSA Form

  1. Inserting \(\phi-functions\) at joints

  2. Renaming such that only one definition reaches any use

However, too many extra \(phi\)-functions waste space and slow down the traversal.

Semipruned SSA Form

Dominance Frontier

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.

Strict Dominance

a strictly dominates b iff \(a \in DOM(b) - \{ b \}\)

Dominance Frontier

\(DF(n)\) is the set of join block m such tha

  • \(n \in DOM(q) | q \in preds(m)\)

  • n does not strictly dominate m

Immediate Dominator

\(IDOM(n)\) is the closest dominator that strictly dominates n.

Dominator Tree

If m is \(IDOM(n)\), then the dominator tree has an edge from m to n.

Renaming

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)\)

  1. Build global names and their definition block lists

  2. 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.

Translation Out of SSA Form

Lost-Copy Problem

Splitting critical edges is the way to implement \(phi\)-functions.

Critical Edge

An edge in a CFG whose source has multiple successors and whose sink has multiple predecessors may be split by the compiler by inserting a block in between. A critical edge is usually a back edge.

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

    • regional scheduling,

    • register allocation,

    • 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.

Swap Problem

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.

Using SSA Form

Sparse Simple Constant Propagation (SSCP)

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.

Interprocedural Constant Propagation

  1. Discovering an Initial Set of Constants

    • Identify which actual parameters have known constant values

    • Literal constant values

    • Global constant propagation

  2. Propagation Known Constant Values around the Call Graph

  3. Modeling Transmission of Values through Procedures

Structural Data-Flow Algorithms and Reducibility

  • Reduce phase: each time a subgraph is transformed into a node

    • \(T_1(n)\): self-loop

    • \(T_2(a, b)\): b has only one predecessor a

  • Expansion phase: each time a node is expanded with computed data-flow sets

  • Irreducible graphs

    • 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

Speed up the Iterative DOM Framework

  • 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