Static Single Assignment.

Each definition has a different version and the def dominates the uses. Such representation of SSA is strict and conventional. The non-conventional SSA is the representation where the different versions of the same variable is live at the same time. If the different version of the same variable does not interfere the SSA representation is conventional. The out of ssa translation for conventional SSA representation makes all the variables as same and the phi nodes are eliminated.

The optimization like copy propagation makes the SSA unconventional and out of SSA translation becomes different. The Sreedhar has proposed the out of SSA translation for such non-conventional SSA representation by making the representation as conventional.

The SSA representation is created based on the dominance frontier and for each def the dominance frontier is calculated, and the phi nodes are placed in the dominance frontiers of the nodes with def.

The dominance frontier for a given node x is the set of nodes of y where x dominates the predecessor of the node Y. The dominance frontier is calculated as follows.

For each predecessor of the given node in CFG

P = the predecessor of each node n belongs to CFG.

While(node(n) not belongs to idom(p)){

    DF(p) = DF(p) union {n};

}

For each predecessor of the given node n is if the p is not the immediate dominator of n the n becomes the dominator frontier of P.

The Algorithm of the construction of SSA representation is as follows

Calculate the dominance frontier of each basic block in the dominator tree

Placing of phi nodes.(Algorithm)

Renaming. (Algorithm)

Rename (x, B)

{

       ve = Top(V);

       Replace all the uses of x in the RHS with Top(V);

       If there is a definition v = v+1;

       Assign v to the def of x ;

       Push(v)

       For each s belongs to successor(B)

            J = predecessor index of s;

            For phi in S for the jth index replace with Top(V);

     }

     For all children c belongs to B in dominator tree

        Rename (x, c);

   }

  Repeat Pop(V) till Top(V) = ve;

Main ()

{

V=phi; v = 0

Rename (x, Start);

}

The pruned SSA makes the efficient way of placing the phi nodes. If the destination of the phi node is live at the point of dominance frontier than phi is retained otherwise its been removed.

The SSA representation makes the data flow analysis easier because of placing of phi nodes. The point of phi nodes makes a confluence operator and the transfer function for the phi nodes is the confluence operator of the phi operands. The data flow analysis needs to be performed for each program points and the SSA representation makes the graph sparse. Data flow analysis is the sparse data flow analysis as it uses the CFG and SSA Graph.

The control flow analysis is based on forming the regions and intervals. The regions are formed from interval by performing the T1 and T2 transformation on the intervals formed. The nodes in the intervals and regions where the entry dominates all other nodes in the intervals and region and the exit node post dominates all the nodes in the interval and region.

The data flow analysis is performed on the DFS numbering for the control flow graph and the ordering of data flow analysis and the traversal of the CFG for data flow analysis is based on DFS numbering. The iteration of the data flow operation which converges is based on the number of iterating edges +1. This is the important analysis found by control flow analysis.

The control flow analysis is also performed to find out the natural loops where natural loops are the loops where the back edges are reiteration edges and are the reducible loops. The irreducible loops where the back edges are not reiterating edges. The irreducible loops where the edges looks like the back edges but they are not back edges. The irreducible loops are converted to reducible loops by node splitting the nodes. The nodes are split based on the predecessor and for each predecessor the new nodes are created and the edges are being added to form the reducible graphs and loops.

Out of SSA Translation 

The out of ssa translation for conventional SSA is simpler as the live ranges for each of the phi operands doesn’t interfere.  Out of ssa is just assigning the different version of the variables the same and phi node is eliminated. For non-conventional SSA the Sreedhar etal makes the non-conventional SSA as the conventional by performing the following Algorithm

For each of the predecessor of the phi node block the copy is generated for each of the phi operands and given the different version name. The phi node is changed with operands as the new version created due to copy instruction in the predecessor and assigned with a different version.

Then there is copy instruction from the destination of the phi node to a new version. After conversion to conventional SSA the out of ssa becomes simpler.