<p>According to Engineering a Compiler Cooper, K. and Torczon, L. the SSA transformation algorithm is divided into two parts</p>
<ol>
<li>Inserting <span class="math-container">$\phi$</span> functions. For each existing definition of a variable compute the iterated dominance frontier and insert <span class="math-container">$\phi$</span> functions into those basic blocks.</li>
<li>Renaming. Updating variable names (i.e numerical subscripts) to ensure each variable is only ever updated once.</li>
</ol>
<p>LLVM's mem2reg pass (the SSA transformation pass) uses <code>alloca</code>, <code>load</code>, and <code>store</code> operations instead of the <code>a = b + c</code> 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 <code>alloca</code>, <code>load</code> and <code>store</code> instead, we just treat each <code>store</code> instruction as a definition and each <code>load</code> instruction as a use.</p>
<p>Assume we have CFG with Part 1 already completed (still using <code>alloca</code>, <code>load</code>, <code>store</code>), 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 &quot;special&quot; DFS on the CFG instead? Essentially we allow revisiting nodes only for the purposes of updating <span class="math-container">$\phi$</span> function operands. This way in a DFS search path of the CFG, it can update the <span class="math-container">$\phi$</span> of a node that has already been visited (when the CFG contains a loop).</p>
<p>Consider the following algorithm</p>
<pre><code>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 &quot;special&quot; 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'
         
</code></pre>
<p>Does this algorithm produce a correct SSA renaming pass?</p>

<compilers>
SSA Construction: DFS of CFG vs Traversal of Dominator Tree
# SSA Construction: DFS of CFG vs Traversal of Dominator Tree
Posted by: username_0 on 2024-07-01
According to Engineering a Compiler Cooper, K. and Torczon, L. the SSA transformation algorithm is divided into two parts

Inserting $\phi$ functions. For each existing definition of a variable compute the iterated dominance frontier and insert $\phi$ functions into those basic blocks.
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?
**Tags:** compilers
---
## 0 answers
