Intermediate representations and control-flow graphs

The abstract syntax tree is ideal for checking a program but awkward for optimizing it or generating code. Trees nest arbitrarily deep, control flow is implicit in the structure of if and while nodes, and the order of evaluation is left unstated. After semantic analysis, compilers therefore lower the AST into an intermediate representation, IR, that makes evaluation order, temporaries and control flow explicit, while staying independent of any particular machine. Most optimizing compilers use a control-flow graph whose nodes are basic blocks of simple instructions, often in static single assignment form (lesson 8). This lesson builds that representation for Tern: three-address code, then basic blocks and the control-flow graph.

Kinds of intermediate representation

IRs range from high to low level, and many compilers use several in succession. High-level IRs, close to the AST, keep loops, array indexing and types, which suits optimizations such as loop interchange; rustc's MIR and Swift's SIL are examples, as are MLIR's higher-level dialects. Mid-level IRs, such as LLVM IR and GCC's GIMPLE, use simple instructions on typed values but no particular machine registers, and are where most optimization happens. Low-level IRs, such as GCC's RTL and LLVM's MachineIR, are close to assembly, with machine instructions and eventually physical registers. IRs also differ in form. Graph-based IRs represent programs as trees, directed acyclic graphs or data-dependence graphs; linear IRs list instructions for an abstract machine, either a stack machine as in JVM and WebAssembly bytecode (and lesson 1's toy) or a register machine with unlimited registers, as in three-address code.

Three-address code

Three-address code (TAC) is a linear IR in which each instruction has at most one operator and at most three operands, usually two sources and a destination: t1 = b * c. Complex expressions are broken into sequences of such instructions using fresh temporaries, which makes the order of evaluation explicit and gives every intermediate value a name that later phases can analyze. Control flow uses labels and jumps: goto L, and conditional jumps such as if x < y goto L1 else L2. Some textbooks use a one-target form, if x < y goto L, that falls through to the next instruction when the test fails; naming both targets, as LLVM's br instruction does, keeps every block's successors explicit. Function calls are spelled out with param instructions followed by call f, n. Array accesses become t = a[i] and a[i] = t at this level; a lower level would compute the address explicitly as a base plus i times the element size.

Generating TAC from an AST is syntax-directed translation: a recursive walk in which each node type has a translation scheme. For an expression, the generator translates the operands, obtaining the names that hold their values, emits one instruction combining them into a new temporary, and returns that temporary. For statements, it emits code in order. For control flow, the key idea is to translate boolean expressions in conditions not as values but as jumps: cond(e, Ltrue, Lfalse) emits code that jumps to Ltrue if e is true and to Lfalse otherwise. Short-circuit evaluation then falls out naturally: for a && b, the code evaluates a, jumping to Lfalse if it is false and otherwise to code that evaluates b. A while loop becomes a test at a top label, a jump into the body or out of the loop, and a jump back to the top at the end of the body.

# Lowering a Tern AST to three-address code. Each instruction has at most one
# operator; temporaries t1, t2, ... hold intermediate values; control flow
# becomes labels and (conditional) jumps. Short-circuit && is compiled to jumps.
class Gen:
    def __init__(g): g.code, g.ntemp, g.nlabel = [], 0, 0
    def temp(g): g.ntemp += 1; return f"t{g.ntemp}"
    def label(g): g.nlabel += 1; return f"L{g.nlabel}"
    def emit(g, s): g.code.append(s)
    def expr(g, e):                                  # returns the name holding the value
        tag = e[0]
        if tag == "num": return str(e[1])
        if tag == "name": return e[1]
        if tag == "index":
            a, i = g.expr(e[1]), g.expr(e[2]); t = g.temp()
            g.emit(f"{t} = {a}[{i}]"); return t
        if tag == "call":
            args = [g.expr(a) for a in e[2]]
            for a in args: g.emit(f"param {a}")
            t = g.temp(); g.emit(f"{t} = call {e[1]}, {len(args)}"); return t
        op, l, r = e
        if op in ("&&", "||"):                       # a boolean value: jump, then set 1 or 0
            t, lt, lf, done = g.temp(), g.label(), g.label(), g.label()
            g.cond(e, lt, lf)
            for s in (f"{lt}:", f"{t} = 1", f"goto {done}", f"{lf}:", f"{t} = 0", f"{done}:"): g.emit(s)
            return t
        a, b = g.expr(l), g.expr(r); t = g.temp()
        g.emit(f"{t} = {a} {op} {b}"); return t
    def cond(g, e, ltrue, lfalse):                   # jump to ltrue or lfalse
        op = e[0]
        if op == "&&":
            mid = g.label(); g.cond(e[1], mid, lfalse); g.emit(f"{mid}:"); g.cond(e[2], ltrue, lfalse)
        elif op == "||":
            mid = g.label(); g.cond(e[1], ltrue, mid); g.emit(f"{mid}:"); g.cond(e[2], ltrue, lfalse)
        elif op in ("<", "<=", ">", ">=", "==", "!="):
            a, b = g.expr(e[1]), g.expr(e[2])
            g.emit(f"if {a} {op} {b} goto {ltrue} else {lfalse}")
        else:
            v = g.expr(e); g.emit(f"if {v} != 0 goto {ltrue} else {lfalse}")
    def stmt(g, s):
        tag = s[0]
        if tag in ("var", "assign"):
            target, value = s[1], s[2]
            if isinstance(target, tuple):            # a[i] = v
                a, i = g.expr(target[1]), g.expr(target[2]); v = g.expr(value)
                g.emit(f"{a}[{i}] = {v}")
            else: g.emit(f"{target} = {g.expr(value)}")
        elif tag == "while":
            top, body, out = g.label(), g.label(), g.label()
            g.emit(f"{top}:"); g.cond(s[1], body, out); g.emit(f"{body}:")
            for x in s[2]: g.stmt(x)
            g.emit(f"goto {top}"); g.emit(f"{out}:")
        elif tag == "if":
            lt, lf = g.label(), g.label()
            g.cond(s[1], lt, lf); g.emit(f"{lt}:")
            for x in s[2]: g.stmt(x)
            if s[3]:                                  # an else part needs a join label
                end = g.label()
                if not g.code[-1].startswith("return"): g.emit(f"goto {end}")
                g.emit(f"{lf}:")
                for x in s[3]: g.stmt(x)
                g.emit(f"{end}:")
            else: g.emit(f"{lf}:")
        elif tag == "return": g.emit(f"return {g.expr(s[1])}")
# fn find(a: [int], n: int, k: int) -> int: index of the first k in a[0..n), or -1
FIND = [("var", "i", ("num", 0)),
        ("while", ("&&", ("<", ("name", "i"), ("name", "n")), ("!=", ("index", ("name", "a"), ("name", "i")), ("name", "k"))),
            [("assign", "i", ("+", ("name", "i"), ("num", 1)))]),
        ("if", ("==", ("name", "i"), ("name", "n")), [("return", ("num", -1))], None),
        ("return", ("name", "i"))]
g = Gen()
for s in FIND: g.stmt(s)
for line in g.code: print(line if line.endswith(":") else "    " + line)
print(len([l for l in g.code if not l.endswith(":")]), "instructions,", g.ntemp, "temporaries")

    i = 0
L1:
    if i < n goto L4 else L3
L4:
    t1 = a[i]
    if t1 != k goto L2 else L3
L2:
    t2 = i + 1
    i = t2
    goto L1
L3:
    if i == n goto L5 else L6
L5:
    return -1
L6:
    return i
10 instructions, 2 temporaries

The condition i < n && a[i] != k has become two separate tests: if i < n fails, control goes straight to L3 without evaluating a[i], which matters because a[i] would be out of bounds. This short-circuit behavior is required by the language, not an optimization, and compiling conditions to jumps implements it directly. The output has some obvious inefficiencies, such as the temporary t2 that is immediately copied into i; we leave them for the optimizer (lesson 11), following the standard practice of generating simple, correct code and improving it later rather than complicating the translator.

Basic blocks

A basic block is a maximal sequence of instructions with a single entry and a single exit: control enters only at the first instruction and leaves only after the last, with no jumps into the middle and no jumps out except at the end. Within a block, instructions execute in order, all or none, which makes blocks the natural unit for local analysis and optimization. Partitioning code into blocks uses leaders, the instructions that start blocks: the first instruction of the function, every instruction that is the target of a jump, and every instruction that immediately follows a jump or return. Each block runs from one leader up to, but not including, the next.

Control-flow graphs

A control-flow graph (CFG) has a node for each basic block and an edge from block A to block B if control can pass directly from the end of A to the start of B: either A ends with a jump to B, or A ends with a conditional jump or no jump and B is the next block in order. Compilers often add distinguished entry and exit nodes. The CFG captures every possible order of execution while abstracting from data: it says which paths exist, not which are taken. Frances Allen's 1970 paper Control Flow Analysis introduced CFGs together with the dominator and interval concepts that the next lessons use.

# Partitioning three-address code into basic blocks and building the
# control-flow graph. Leaders: the first instruction, every label target,
# and every instruction that follows a jump or return. A two-way branch
# 'if c goto A else B' names both successors, as LLVM's br does.
CODE = """    i = 0
L1:
    if i < n goto L4 else L3
L4:
    t1 = a[i]
    if t1 != k goto L2 else L3
L2:
    t2 = i + 1
    i = t2
    goto L1
L3:
    if i == n goto L5 else L6
L5:
    return -1
L6:
    return i""".splitlines()
instrs, label_at = [], {}
for line in CODE:
    line = line.strip()
    if line.endswith(":"): label_at[line[:-1]] = len(instrs)
    else: instrs.append(line)
leaders = {0} | set(label_at.values())
for k, ins in enumerate(instrs):
    if (ins.startswith(("goto", "if", "return"))) and k + 1 < len(instrs): leaders.add(k + 1)
starts = sorted(leaders)
blocks = [instrs[s:e] for s, e in zip(starts, starts[1:] + [len(instrs)])]
block_of = {s: f"B{n}" for n, s in enumerate(starts)}
name_of_label = {lab: block_of[pos] for lab, pos in label_at.items()}
succ = {}
for n, (s, body) in enumerate(zip(starts, blocks)):
    last, b = body[-1], f"B{n}"; out = []
    if last.startswith("goto"): out = [name_of_label[last.split()[1]]]
    elif last.startswith("if"):                                  # two-way branch
        w = last.split(); out = [name_of_label[w[-3]], name_of_label[w[-1]]]
    elif not last.startswith("return") and n + 1 < len(blocks): out = [f"B{n + 1}"]
    succ[b] = out
pred = {b: [a for a in succ if b in succ[a]] for b in succ}
for n, body in enumerate(blocks):
    b = f"B{n}"
    print(f"{b}: preds={pred[b] or ['entry']}  succs={succ[b] or ['exit']}")
    for ins in body: print("      " + ins)
# A back edge goes to a block that dominates its source; here B3 -> B1 closes the loop.
print("back edges:", [(a, b) for a in succ for b in succ[a] if int(b[1:]) <= int(a[1:])])

B0: preds=['entry']  succs=['B1']
      i = 0
B1: preds=['B0', 'B3']  succs=['B2', 'B4']
      if i < n goto L4 else L3
B2: preds=['B1']  succs=['B3', 'B4']
      t1 = a[i]
      if t1 != k goto L2 else L3
B3: preds=['B2']  succs=['B1']
      t2 = i + 1
      i = t2
      goto L1
B4: preds=['B1', 'B2']  succs=['B5', 'B6']
      if i == n goto L5 else L6
B5: preds=['B4']  succs=['exit']
      return -1
B6: preds=['B4']  succs=['exit']
      return i
back edges: [('B3', 'B1')]

Read with the figure, the output shows the structure clearly. The loop is the cycle B1 to B2 to B3 and back to B1; the edge B3 to B1 is a back edge, the edge that closes the loop. Both loop tests have an edge to B4, the block after the loop, reflecting the two ways the loop can end. Loops are found in CFGs, not in source syntax, so the optimizer handles while, for, do-while and even goto-built loops uniformly. Formally, a back edge is an edge whose target dominates its source, a notion lesson 8 defines precisely; the simple test in the code, an edge to an earlier or equal block, coincides with that definition for code generated from structured programs like Tern's.

Other graphs compilers build

The CFG is the backbone, but it is not the only graph. A call graph has a node per function and an edge for each possible call, which interprocedural analyses such as inlining decisions use. A data-dependence graph records which instructions produce values used by which others, and constrains instruction scheduling and loop parallelization. Directed acyclic graphs (DAGs) for basic blocks represent each computed value once, exposing common subexpressions: in a block computing a + b twice, the DAG has a single + node used twice. The program dependence graph combines control and data dependences. The sea-of-nodes IR, designed by Cliff Click for Java's HotSpot server compiler in the 1990s, goes furthest, dropping the fixed instruction order entirely and keeping only dependences, which gives the optimizer maximal freedom.

LLVM IR: a real example

LLVM IR is the most widely used IR today, and it is worth seeing one. It is a typed, linear IR organized into functions of basic blocks, each ending in a terminator instruction such as br or ret. Values have explicit types, such as i32 for 32-bit integers and ptr for pointers. At -O0, Clang generates naive IR in which every local variable lives in stack memory, allocated with alloca and accessed with load and store; this is easy to generate, and lesson 8's SSA construction (LLVM's mem2reg pass) then promotes these variables to registers. Below is real Clang output for the search function written in C.

cat find.c
clang -O0 -Xclang -disable-O0-optnone -S -emit-llvm -fno-discard-value-names find.c -o - | sed -n "/^define/,/^.$/p" | sed "s/, align [0-9]*//; s/ #[0-9]*//; s/, !llvm.loop !.*//"

$ cat find.c
int find(int *a, int n, int k) {
    int i = 0;
    while (i < n && a[i] != k)
        i = i + 1;
    if (i == n) return -1;
    return i;
}
$ clang -O0 -Xclang -disable-O0-optnone -S -emit-llvm -fno-discard-value-names find.c -o - | sed -n "/^define/,/^.$/p" | sed "s/, align [0-9]*//; s/ #[0-9]*//; s/, !llvm.loop !.*//"
define dso_local i32 @find(ptr noundef %a, i32 noundef %n, i32 noundef %k) {
entry:
  %retval = alloca i32
  %a.addr = alloca ptr
  %n.addr = alloca i32
  %k.addr = alloca i32
  %i = alloca i32
  store ptr %a, ptr %a.addr
  store i32 %n, ptr %n.addr
  store i32 %k, ptr %k.addr
  store i32 0, ptr %i
  br label %while.cond
while.cond:                                       ; preds = %while.body, %entry
  %0 = load i32, ptr %i
  %1 = load i32, ptr %n.addr
  %cmp = icmp slt i32 %0, %1
  br i1 %cmp, label %land.rhs, label %land.end
land.rhs:                                         ; preds = %while.cond
  %2 = load ptr, ptr %a.addr
  %3 = load i32, ptr %i
  %idxprom = sext i32 %3 to i64
  %arrayidx = getelementptr inbounds i32, ptr %2, i64 %idxprom
  %4 = load i32, ptr %arrayidx
  %5 = load i32, ptr %k.addr
  %cmp1 = icmp ne i32 %4, %5
  br label %land.end
land.end:                                         ; preds = %land.rhs, %while.cond
  %6 = phi i1 [ false, %while.cond ], [ %cmp1, %land.rhs ]
  br i1 %6, label %while.body, label %while.end
while.body:                                       ; preds = %land.end
  %7 = load i32, ptr %i
  %add = add nsw i32 %7, 1
  store i32 %add, ptr %i
  br label %while.cond
while.end:                                        ; preds = %land.end
  %8 = load i32, ptr %i
  %9 = load i32, ptr %n.addr
  %cmp2 = icmp eq i32 %8, %9
  br i1 %cmp2, label %if.then, label %if.end
if.then:                                          ; preds = %while.end
  store i32 -1, ptr %retval
  br label %return
if.end:                                           ; preds = %while.end
  %10 = load i32, ptr %i
  store i32 %10, ptr %retval
  br label %return
return:                                           ; preds = %if.end, %if.then
  %11 = load i32, ptr %retval
  ret i32 %11
}

The structure matches our hand-built CFG closely: a block for the loop test, a block for the second half of the short-circuit condition, the body, the exit test and the two returns. The phi instruction that Clang uses to merge the result of the && condition is a preview of SSA form. Every variable, including the parameters, has been copied into a stack slot by alloca, store and load, a deliberately simple translation that lets the front end ignore register allocation and data flow entirely and leave both to later passes.

Worked examples