# SSA Construction: DFS of CFG vs Traversal of Dominator Tree

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:
Return
Else:
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?