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

The abstract syntax tree (AST) is too closely tied to the source language's syntax, making it difficult to track values and control flow. To achieve stable analysis, compilers require a more robust intermediate representation.

While ASTs effectively 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 following a conditional or unconditional jump.

Each leader to the next leader defines a basic block. 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, data flow analysis will incorrectly merge paths that cannot occur simultaneously.

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. If instructions cannot be directly inserted onto the edges, the critical edge must be split. 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, the defining block must dominate the use block. φ inputs are used along predecessor edges, with a slight exception to this rule.

The classic SSA construction process:

1. Compute the control flow graph (CFG) and dominance tree;
2. Place φ nodes for multiple definitions based on the dominance frontier;
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.

Function calls, atomic operations, volatile accesses, memory reads and writes, and exceptions all have side effects. Dead code elimination cannot simply remove an instruction because "its result is unused" if that instruction has observable effects.

7. Problems with Multi-Layer IR Services

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. IR Validator is a Necessary Gatekeeper

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 definition occurs before its use;
• SSA definitions dominate their uses;
• φ-function inputs correspond one-to-one with CFG predecessors;
• 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 not a linear, unstructured 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.
• φ functions are not CPU conditional instruction equivalents: 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.