SSA notation looks like arbitrary subscripts until the control-flow graph, dominators, join points and renaming order become one construction. Take a six-block program in ordinary three-address style: it needs exactly three phi nodes, and its SSA form executes to a return value of 3. Dominators and dominance frontiers decide where those phis go, and that is the step most aspirants guess at instead of computing. Compiler-design questions in the GATE CS Exam Preparation track lean on exactly this construction.
SSA and control flow: the concept set before the algorithm
A basic block is a maximal straight-line instruction sequence with one entry and no internal branch. A control-flow graph (CFG) has blocks as nodes and directed transfers as edges.
Graph | Nodes | Edges |
|---|---|---|
CFG | Basic blocks | Possible control transfers |
Call graph | Functions or procedures | Possible calls |
Data-flow graph | Values or operations | Data dependencies |
Dominance is defined over CFG paths, so confusing these graphs produces wrong answers.
In static single assignment (SSA) form, each versioned name has exactly one definition that dominates every use. A phi function chooses the version carried by the predecessor edge. It is not a normal run-time call, and its arguments do not both execute.
SSA follows parsing and intermediate-representation construction, before or during optimisation. Syntax-directed translation & code optimization works through the attribute rules and optimisation passes that sit on either side of it.
Control-flow graph worked example: six blocks and every edge
Start with this program:
B0: x = 4
y = 1
goto B1
B1: if x % 2 == 0 goto B2 else B3
B2: y = y + x
goto B4
B3: y = y - x
goto B4
B4: x = x - 1
if x > 0 goto B1 else B5
B5: return yB0 is the entry. Branch targets begin blocks, while jumps end them, giving leaders B0 through B5. The edges are B0 -> B1, B1 -> B2, B1 -> B3, B2 -> B4, B3 -> B4, B4 -> B1 and B4 -> B5.
Therefore, pred(B1)={B0,B4}, pred(B2)={B1}, pred(B3)={B1}, pred(B4)={B2,B3} and pred(B5)={B4}. The diamond is B1 -> {B2,B3} -> B4; B4 -> B1 is the back edge. Parsing in Compiler Design: Top-Down and Bottom-Up Explained works through the top-down and bottom-up methods that build the parse tree these blocks are later generated from.
Dominators and dominance frontiers: compute the table
Start with dom(B0)={B0}. For every other block B, use dom(B)={B} union intersection(dom(P)) over predecessors P. Its immediate dominator idom(B) is the closest strict dominator. DF(A) contains Y when A dominates a predecessor of Y but does not strictly dominate Y.
Block | Dominator set | Immediate dominator | Dominance frontier |
|---|---|---|---|
B0 | {B0} | none | empty |
B1 | {B0, B1} | B0 | {B1} |
B2 | {B0, B1, B2} | B1 | {B4} |
B3 | {B0, B1, B3} | B1 | {B4} |
B4 | {B0, B1, B4} | B1 | {B1} |
B5 | {B0, B1, B4, B5} | B4 | empty |
B1 lies in DF(B1) because B1 dominates the back-edge predecessor B4 but does not strictly dominate itself. B4 lies in both DF(B2) and DF(B3) because the branch paths meet there. Dominance is reflexive unless a question explicitly asks for strict dominance.
Phi-node placement: use iterated dominance frontiers
Definition sites are Def(x)={B0,B4} and Def(y)={B0,B2,B3}. For x, DF(B0) is empty and DF(B4)={B1}, so only B1 needs a phi: x1 = phi(B0:x0, B4:x2).
For y, DF(B0) is again empty while DF(B2) union DF(B3)={B4}, so place a phi at B4. Treating it as a new definition and applying DF(B4)={B1} adds a y phi at B1. The final count is three: x at B1, y at B1, and y at B4. B5 has one predecessor, so it needs none.
"Every join gets a phi" is only a shortcut. Placement depends on reaching definitions and, in pruned SSA, whether the variable is live-in. Omitting y at the loop header would fail to merge initial y=1 with the value returning on B4 -> B1.
SSA renaming: the final versioned program
B0: x0 = 4
y0 = 1
goto B1
B1: x1 = phi(B0:x0, B4:x2)
y1 = phi(B0:y0, B4:y4)
if x1 % 2 == 0 goto B2 else B3
B2: y2 = y1 + x1
goto B4
B3: y3 = y1 - x1
goto B4
B4: y4 = phi(B2:y2, B3:y3)
x2 = x1 - 1
if x2 > 0 goto B1 else B5
B5: return y4Rename by depth-first traversal of the dominator tree, with one stack and counter per variable. Push a fresh version at a definition, rewrite uses to the stack top, fill successor phi operands for the current edge, then pop when leaving the block. Numbering may differ, but definitions, uses and edge choices must be equivalent.
Here x1 dominates its uses in B1, B2, B3 and B4. y2 and y3 flow only into their matching predecessor inputs of y4. Then y4 reaches the back-edge input of y1 and return y4 in B5.
SSA execution trace: follow the incoming edge
The incoming edge determines each phi choice.
Visit to B1 | x1 | y1 | Branch | y4 at B4 | x2 at B4 |
|---|---|---|---|---|---|
1, from B0 | 4 | 1 | B2, even | 5 | 3 |
2, from B4 | 3 | 5 | B3, odd | 2 | 2 |
3, from B4 | 2 | 2 | B2, even | 4 | 1 |
4, from B4 | 1 | 4 | B3, odd | 3 | 0 |
The four updates are 1+4=5, 5-3=2, 2+2=4 and 4-1=3. After the last update, x2=0, so control takes B4 -> B5 and returns y4=3.
Treat phis as parallel assignments at block entry. On B4 -> B1, x1 gets the old x2 and y1 gets the old y4; neither input is overwritten first.
GATE-style SSA questions: recognise the operation
Typical operations are computing dominators or the immediate-dominator tree, finding a frontier, placing phis, counting versions, or tracing an edge-selected value. Four checks are: strict dominators of B5 are {B0,B1,B4}; DF(B4)={B1}; the phi count is 3; and the return is 3.
The official GATE 2026 CS syllabus names intermediate code generation and data-flow analyses such as constant propagation, liveness analysis and common subexpression elimination under Compiler Design. It does not explicitly name SSA there, so SSA is best understood as a useful IR framework connected to those analyses, not a guaranteed standalone question or weightage. The GATE Test Series is the next step for mixed exam-style practice.
Common traps are taking union instead of intersection for dominators, confusing predecessors with dominators, putting a phi at every join, forgetting the loop's iterated frontier, choosing a phi input before finding the incoming edge, and treating subscripts as value-changing operations.
SSA and control flow: the short version and next step
Recall: build blocks and edges; solve dominators, immediate dominators and frontiers; place phis from iterated frontiers; rename down the dominator tree and trace by predecessor edge. This example has three phis and returns 3.
For a structured subject-wise path, continue with GATE Guidance by Sanchit Sir. If the pipeline already feels clear, redraw this six-block CFG and recompute the table without looking.
As a final self-test, change only the initial value to x0=5, keep y0=1, and predict the branch sequence and return value before rebuilding the SSA form.
