According to Engineering a Compiler Cooper, K. and Torczon, L. the SSA transformation algorithm is divided into two parts

  1. Inserting $\phi$ functions. For each existing definition of a variable compute the iterated dominance frontier and insert $\phi$ functions into those basic blocks.
  2. Renaming. Updating variable names (i.e numerical subscripts) to ensure each variable is only ever updated once.

LLVM's mem2reg pass (the SSA transformation pass) uses alloca, load, and store operations instead of the a = b + c three address like operations. As I understand it, if we wish to apply the SSA transformation algorithm from the textbook above but with LLVM's alloca, load and store instead, we just treat each store instruction as a definition and each load instruction as a use.

Assume we have CFG with Part 1 already completed (still using alloca, load, store), the book says the Part 2 should be done as a DFS walk on the dominator tree. However I'm wondering if we are able to do a "special" DFS on the CFG instead? Essentially we allow revisiting nodes only for the purposes of updating $\phi$ function operands. This way in a DFS search path of the CFG, it can update the $\phi$ of a node that has already been visited (when the CFG contains a loop).

Consider the following algorithm

Let H be a map that maps each alloca to the variable that holds its current value
Rename(Basic Block B, H):

    for each Phi Instruction P in B:
        Find the alloca instruction, I, that P corresponds to
        Use H to get the current variable, V, for alloca, I.
        Insert V into the operand list of P if V is not already in the operand list
        Update H such that H maps I to target variable of P.
    // This is the "special" part, we only check if a node has been visited AFTER inserting Phi Operands.
    If basic block B has been visited: 
        Mark B as visited  
    For each instruction I in B: 
        if I is a (store [alloca A], [source variable V]) instruction: 
            H[A] = V // store instructions change which value the alloca holds, update H accordingly
        else if I is a (load [target variable V], [alloca A]) instruction:
            Replace all uses of V with H[A]
    For each successor, S, of B:
        Save state of H, H'
        Rename (S, H)
        Restore H back to H'

Does this algorithm produce a correct SSA renaming pass?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.