7.3 IR, Control Flow Graphs, and SSA: Enabling Data Dependency Analysis

While ASTs capture the structure of the source language, they are not well-suited for answering questions like "where did this value come from?" or "which control flow path contains this instruction." Intermediate representations reduce syntactic sugar, explicitly model control flow, and normalize operations, providing a smaller, more stable semantic surface for optimization and code generation.

Learning Objectives

• Distinguish between tree-shaped ASTs, linear three-address code, and control flow graphs;
• Construct basic blocks and control flow graphs;
• Understand SSA definition uniqueness, dominance, and φ-nodes;
• Explain why compilers typically use a multi-layer intermediate representation.

1. Lowering Goes Beyond "Flattening"

Expression:

(a + b) * c

Three-address form:

t1 = add a, b
t2 = mul t1, c

But statements, short-circuit logic, exceptions, and loops require control flow. Intermediate representations (IR) are typically structured as functions, basic blocks, and instructions:

entry:
    br cond, then, else
then:
    x1 = const 1
    jump merge
else:
    x2 = const 2
    jump merge
merge:
    ...

A basic block has a single entry point and no jumps within its body except at the terminator; the nodes in a control flow graph (CFG) are basic blocks, and the edges represent possible control transfers.

2. Find Basic Block Boundaries

In linear TAC, leaders typically include:

• The first instruction of a function;
• The target of a jump;
• The instruction after a conditional or unconditional jump, return, or other terminator, if one exists.

Each leader begins a block that ends immediately before the next leader. Edges are then established from the end of each block based on its terminator: two edges for conditional branches, one for unconditional jumps, and no successor for returns.

Implicit exception edges, finally blocks, coroutine suspensions, and unrecoverable traps make the control flow graph more complex. The IR must explicitly identify which operations may transfer control; otherwise, analysis can miss reachable paths or incorrectly assume that later instructions must execute.

3. The core of SSA is that each name has a single definition

Non-SSA:

x = 0
x = x + 1

SSA-renamed version:

x0 = 0
x1 = add x0, 1

Each SSA value has exactly one definition point, with a direct pointer to that definition. This simplifies def-use chains, constant propagation, and dead value analysis. However, memory locations do not automatically become single-assignment; alias analysis and memory SSA techniques are still required to handle load/store dependencies.

4. φ Node Value Selection by Predecessor Edge

Control flow convergence:

then:
    x1 = 1
    jump merge
else:
    x2 = 2
    jump merge
merge:
    x3 = phi [x1, then], [x2, else]

The semantics of a φ node is that the value taken corresponds to the predecessor edge through which control enters, specifically, the value associated with that edge. It is not a regular runtime function call, nor does it evaluate all parameters upfront before making a selection.

When lowering SSA form, a φ node is typically transformed into parallel copies along the predecessor edges. A critical edge runs from a block with multiple successors to a block with multiple predecessors. Placing a copy at either endpoint can execute it on the wrong path, so it is commonly split before inserting the copies. Parallel copies also require handling of value swaps that introduce cycles, which may necessitate temporary storage locations.

5. Dominance Relations Determine φ Placement

If every path from a function entry point to block $B$ passes through block $A$, then $A$ dominates $B$. In general, for a definition to be safely reachable at a use site, a definition must dominate each ordinary use; within one block, the defining instruction must also precede the use. A φ input is used on its corresponding predecessor edge, so a loop backedge may refer to a definition written later in the text. These statements concern entry-reachable blocks; unreachable blocks follow the IR’s own rules.

This teaching IR returns 3. The definition of next appears after the φ in the text, but dominates the body → header backedge, making it valid as that edge’s input:

entry:
    jump header
header:
    i = phi [0, entry], [next, body]
    keep_going = lt i, 3
    br keep_going, body, exit
body:
    next = add i, 1
    jump header
exit:
    return i

The classic SSA construction process:

1. Compute the control flow graph (CFG) and dominance tree;
2. Place φ nodes using the iterated dominance frontier of definition blocks; pruned SSA also uses liveness to avoid unnecessary φ nodes;
3. Rename variables along the dominance tree;
4. Establish def-use chains and verify SSA invariants.

In practice, incremental methods such as sealed-blocks are also used. Regardless of the algorithm employed, it is essential to maintain or recompute the relevant analyses after any CFG transformation.

6. IR Requires Explicit Types and Effects

An add instruction must explicitly specify:

• Whether it operates on an integer or a floating-point value;
• Its bit width and overflow semantics;
• Whether it may trigger a trap;
• Whether reordering is permitted;
• The types of its operands and result.

Calls, atomics, volatile accesses, memory operations, and exceptions need an effect model. Not every call or ordinary load has observable side effects; removability depends on purity, traps, synchronization, and the language’s memory rules. Dead code elimination cannot simply remove an instruction because "its result is unused" if that instruction has observable effects.

7. Multiple IR Levels Serve Different Tasks

Common layers:

AST / typed tree
  ↓ Remove syntactic sugar, names bound
High-level IR
  ↓ Explicit control flow and operations
SSA / optimizer IR
  ↓ Type and operation legalization
Machine IR
  ↓ Physical registers and instruction encoding
Machine code

There is no fixed number of layers. High-level IR preserves semantics like arrays, closures, or async behavior, enabling domain-specific optimizations. Low-level IR exposes memory addresses, calling conventions, and target instruction constraints. Lowering too early risks losing essential information, while lowering too late causes each backend to redundantly handle high-level constructs.

8. Validate IR After Every Pass

After each pass, the validator can check:

• Each basic block contains exactly one valid terminator;
• The control flow graph (CFG) predecessors and successors are symmetric;
• Every value reference resolves to a valid definition; file order alone does not determine validity;
• SSA definitions dominate their uses;
• Each incoming edge has a valid φ input; repeated edges from one predecessor follow the IR’s rules;
• Instruction operand types are consistent;
• Block and value IDs referenced are valid.

The closer the validator is placed to the pass that introduces an error, the easier it is to pinpoint the root cause. Reporting an "internal error" only at the final assembly generation stage has already lost the most critical context.

Common Misconceptions

• TAC is only an unstructured linear list: Cross-branch analysis must reconstruct basic blocks and control flow graphs (CFGs).
• SSA makes all memory assignments single-assignment: Regular memory can still be written to multiple times; aliasing and memory dependency models are still required.
• A φ node is a CPU conditional-select instruction: They merge values from CFG predecessors, and are subsequently eliminated or mapped away.
• A single general-purpose IR works for all optimization phases: Different abstraction layers require preserving distinct information and invariants.

Exercise

1. Partition an if/else TAC into basic blocks and draw the control flow graph.
2. Construct SSA for the loop variable and identify the two inputs to the loop header φ.
3. Explain why removing unused function calls might alter the program's behavior.
4. Write five invariant assertions for your designed IR to use in a verifier.

Summary

IR reduces source language constructs down to explicit operations and control flow, CFG provides the path skeleton, and SSA assigns a unique identity to each computation result. Together, they make analysis more direct, yet they do not eliminate the complexity introduced by memory, side effects, and exceptions.

The final chapter will perform optimizations based on these invariants, then map virtual operations to concrete target machine instructions, ensuring all observable behavior adheres to the rules of the source language.

References

• LLVM Language Reference: phi