Intermediate Representation: SSA, CFG, and IR Design in Compilers

When you write code in a high-level language like C++, the compiler doesn't directly translate it to machine code. Instead, it uses an intermediate representation (IR) — a structured, platform-independent form that captures the program's semantics. This IR is the heart of modern compilers, enabling powerful optimizations and portability across architectures.

Two foundational concepts in IR design are Static Single Assignment (SSA) form and Control Flow Graphs (CFG). SSA ensures every variable is assigned exactly once, which simplifies data-flow analysis and enables optimizations like constant propagation and dead code elimination. CFGs model the program's control flow as a directed graph, where nodes represent basic blocks and edges represent jumps. Together, they form the backbone of compiler optimization passes.

In this tutorial, you'll learn how to design and work with IRs, understand SSA and CFG in depth, and see real-world examples from LLVM and GCC. We'll also cover common pitfalls and production debugging techniques. By the end, you'll have a solid grasp of how compilers represent and transform code internally.

What is Intermediate Representation?

Intermediate Representation (IR) is a data structure used internally by a compiler to represent source code. It is designed to be independent of the source language and target machine, facilitating analysis and transformation. Common IR forms include abstract syntax trees (ASTs), three-address code (TAC), and static single assignment (SSA) form. IRs can be high-level (close to source) or low-level (close to machine). The choice of IR affects compiler performance, optimization opportunities, and portability.

For example, LLVM uses a low-level IR that is SSA-based, while GCC uses a series of IRs (GIMPLE, RTL). The IR must be expressive enough to capture all source constructs while being simple enough for efficient analysis. Key properties of a good IR include: unambiguous semantics, compact representation, and support for control flow and data dependencies.

// Example of a simple three-address code IR
// Representing: int x = a + b * c;
1: t1 = b * c
2: x = a + t1

Control Flow Graph (CFG)

A Control Flow Graph (CFG) is a directed graph where nodes represent basic blocks (straight-line code sequences with no jumps) and edges represent control flow (branches, loops, function calls). CFGs are fundamental for optimizations like dead code elimination, loop invariant code motion, and register allocation.

A basic block ends with a terminator instruction (e.g., branch, return). The CFG has a unique entry block and may have multiple exit blocks. Edges can be conditional or unconditional. Dominance relationships (e.g., dominator tree) are derived from CFG and used for SSA construction.

Example: A simple if-else statement produces a CFG with three blocks: entry, then, else, and merge.

// C++ code
int max(int a, int b) {
    int result;
    if (a > b)
        result = a;
    else
        result = b;
    return result;
}

// Corresponding CFG (basic blocks)
// Entry: a, b parameters
// Block1: if a > b goto Block2 else goto Block3
// Block2: result = a; goto Block4
// Block3: result = b; goto Block4
// Block4: return result

Static Single Assignment (SSA) Form

SSA form is an IR property where each variable is assigned exactly once, and every use is reached by exactly one definition. This simplifies data-flow analysis because variable names are unique. To handle multiple definitions (e.g., from if-else), special phi (φ) functions are inserted at join points. Phi functions select a value based on which incoming path was taken.

SSA construction involves two steps: inserting phi nodes at dominance frontiers and renaming variables. The dominance frontier of a block is the set of blocks where the block's dominance ends. Phi nodes are placed at the dominance frontiers of each variable's definition.

Example: In the max function, the variable 'result' has two definitions (in Block2 and Block3). At the merge block (Block4), a phi node is inserted: result = phi(Block2: a, Block3: b).

// SSA form of max function (pseudo-IR)
entry:
    a0 = param
    b0 = param
    if a0 > b0 goto then else goto else

then:
    result1 = a0
    goto merge

else:
    result2 = b0
    goto merge

merge:
    result3 = phi(result1, result2)
    return result3

IR Design Principles and Trade-offs

Designing an IR involves balancing expressiveness, simplicity, and efficiency. Key considerations: - Level of abstraction: High-level IRs (e.g., AST) preserve source structure but are harder to optimize. Low-level IRs (e.g., LLVM IR) expose machine details but require more lowering. - SSA vs. non-SSA: SSA simplifies many optimizations but adds phi nodes. Non-SSA (e.g., three-address code) is simpler but requires reaching definitions analysis. - Graph vs. linear: Graph-based IRs (e.g., CFG) are natural for control flow; linear IRs (e.g., bytecode) are compact and easy to interpret. - Typed vs. untyped: Typed IRs (e.g., LLVM IR) catch errors early but add complexity. Untyped IRs are simpler but require type inference.

Modern compilers often use multiple IRs. For example, GCC uses GENERIC (high-level), GIMPLE (SSA-based), and RTL (low-level). LLVM uses a single SSA-based IR throughout.

// LLVM IR example (typed, SSA)
define i32 @max(i32 %a, i32 %b) {
entry:
  %cmp = icmp sgt i32 %a, %b
  br i1 %cmp, label %then, label %else

then:
  br label %merge

else:
  br label %merge

merge:
  %result = phi i32 [ %a, %then ], [ %b, %else ]
  ret i32 %result
}

Optimizations Using SSA and CFG

Example: Constant propagation in SSA: if a variable is defined as a constant, all uses can be replaced by that constant. This may enable further simplifications.

// Before constant propagation
%x = add i32 5, 3
%y = mul i32 %x, 2

// After constant propagation
%x = add i32 5, 3  // could be folded to 8
%y = mul i32 8, 2  // folded to 16

Implementing a Simple IR in C++

To understand IR deeply, let's implement a minimal IR in C++. We'll define classes for basic blocks, instructions, and a function. This IR will be linear (list of instructions) with SSA-like properties.

We'll support a few opcodes: ADD, SUB, MUL, DIV, CONST, PHI, BR, RET. Each instruction has an opcode, operands (as indices), and a result index. We'll also maintain a symbol table for variable names.

This simple IR can be used to build a toy compiler or educational tool.

#include <vector>
#include <string>
#include <unordered_map>

enum Opcode { ADD, SUB, MUL, DIV, CONST, PHI, BR, RET };

struct Instruction {
    Opcode op;
    std::vector<int> operands; // indices into value table
    int result; // index of result value
};

struct BasicBlock {
    std::vector<Instruction> instructions;
    std::string label;
};

struct Function {
    std::vector<BasicBlock> blocks;
    std::unordered_map<std::string, int> symbolTable;
    int nextValue = 0;
};

// Example: create a constant instruction
Instruction createConst(int value) {
    return {CONST, {}, value};
}

Common Pitfalls in IR Design and Use

1. Ignoring dominance: Without proper dominance analysis, SSA construction may produce incorrect phi placements.
2. Overcomplicating IR: Adding too many opcodes early makes analysis and optimization harder.
3. Not handling critical edges: Critical edges (from a block with multiple successors to a block with multiple predecessors) can cause issues in SSA; splitting them is often necessary.
4. Forgetting to update SSA after transformations: Any pass that modifies control flow must update phi nodes and dominance information.
5. Mixing levels of abstraction: Using high-level constructs in low-level IR can hinder optimizations.

// Example of a critical edge
// Block A has two successors B and C; B has two predecessors A and D.
// Edge A->B is critical. Splitting it by inserting a new block helps SSA.

// Before splitting:
// A: br cond, B, C
// B: phi [val1, A], [val2, D]

// After splitting:
// A: br cond, E, C
// E: br B
// B: phi [val1, E], [val2, D]