Translating Control Flow

Expressions were the calm part. The moment a source program contains an if, a while, or a for, the compiler faces a genuine translation problem: the target three-address code has no structured control — no braces, no loop keyword. It has only labels and jumps: goto L, and the conditional if x relop y goto L. So the entire richness of structured programming must be lowered into a flat tangle of gotos that behaves identically. This is "jumping code", and getting the labels in the right places is the whole craft.

The good news is that each control construct has a fixed template. Once you internalise the shape for if, if-else, and while, every program is just those shapes nested inside one another. We build the templates, draw the control-flow graph they induce, and then generate one in code.

The three templates

Write B for a boolean condition and S for a statement body. Each template introduces one or two fresh labels (the analogue of \textit{newtemp}() is \textit{newlabel}()) and arranges a conditional jump so that control reaches the right place. Here they are as TAC skeletons:

// if (B) S // if (B) S1 else S2 ifFalse B goto Lend ifFalse B goto Lelse ... code for S ... ... code for S1 ... Lend: goto Lend Lelse: ... code for S2 ... Lend: // while (B) S Lbegin: ifFalse B goto Lend ... code for S ... goto Lbegin // the back-edge that makes it a loop Lend:

Three things repay attention. The condition is tested with ifFalse … goto so that failure skips the body — you jump when the guard is false, and fall through when it is true. The if-else needs the extra goto Lend after S_1 so that the "then" branch does not fall straight into the "else" branch. And the while's distinguishing feature is the back-edge goto Lbegin, the single jump that turns a straight line into a loop.

The shape of the jumps: a control-flow graph

A picture makes the templates click. A control-flow graph (CFG) has one node per basic block — a maximal run of straight-line code with a single entry and single exit — and an edge wherever control can pass from one block to another. Below is the CFG of a while loop. Reveal it block by block and watch the back-edge form the cycle.

The header node has two out-edges — the essence of a conditional — one to the body (guard true) and one to the exit (guard false). The body's out-edge points back to the header, closing the loop. Every loop in every program, however it was written in the source, has exactly this silhouette in the CFG: a header that dominates a body that jumps back to it.

Generating a loop in code

Here the templates become an emitter. We represent a tiny AST — assignments, a while, and a relational condition — and lower it to TAC with fresh labels from newlabel(). The program is i = 1; while (i <= n) { s = s + i; i = i + 1; }.

type Cond = { l: string; rel: string; r: string }; // l rel r type Stmt = | { kind: "assign"; x: string; rhs: string } // x = rhs (rhs is a raw TAC expression) | { kind: "while"; cond: Cond; body: Stmt[] } | { kind: "seq"; stmts: Stmt[] }; const code: string[] = []; let labelN = 0; const newlabel = () => `L${++labelN}`; const emit = (s: string) => code.push(s); // The negation of a relation, so we can jump-on-false to skip the body. const negate = (rel: string) => ({ "<=": ">", ">=": "<", "<": ">=", ">": "<=", "==": "!=", "!=": "==" } as Record<string, string>)[rel]; function genStmt(s: Stmt): void { switch (s.kind) { case "assign": emit(`${s.x} = ${s.rhs}`); break; case "seq": s.stmts.forEach(genStmt); break; case "while": { const begin = newlabel(), end = newlabel(); emit(`${begin}:`); // Jump OUT when the condition is false: use the negated relation. emit(`ifFalse ${s.cond.l} ${s.cond.rel} ${s.cond.r} goto ${end}`); s.body.forEach(genStmt); emit(`goto ${begin}`); // the back-edge emit(`${end}:`); break; } } } const program: Stmt = { kind: "seq", stmts: [ { kind: "assign", x: "s", rhs: "0" }, { kind: "assign", x: "i", rhs: "1" }, { kind: "while", cond: { l: "i", rel: "<=", r: "n" }, body: [ { kind: "assign", x: "s", rhs: "s + i" }, { kind: "assign", x: "i", rhs: "i + 1" }, ], }, ], }; genStmt(program); code.forEach((line) => console.log(line));

The output is textbook jumping code: L1:, an ifFalse i <= n goto L2 guarding the body, the two body assignments, a goto L1 back-edge, and finally L2:. Notice the emitter used ifFalse … <= directly rather than negate; either works — what matters is that the false case leaves the loop.

Nesting, break, and continue

Nothing new is needed for nested loops: because each while mints its own Lbegin/Lend, an inner loop's labels are simply distinct from the outer's, and the templates compose. The two jump statements slot in naturally:

break becomes goto Lend of the nearest enclosing loop — it leaves the loop entirely.
continue becomes goto Lbegin (or to the increment step, in a for) of the nearest enclosing loop — it skips the rest of this iteration and re-tests the guard.

The compiler keeps a stack of the enclosing loops' begin/end labels; break and continue read the top of that stack. A for (init; cond; step) S is pure sugar: emit init, then a while (cond) { S; step; } — with the wrinkle that a continue must jump to step, not skip it. A switch lowers to a cascade of if x == c_i goto L_i tests (or, for dense integer cases, a jump table indexed by the value).

You could translate if (B) S as "if B goto Lbody; goto Lend; Lbody: S; Lend:" — jumping in when true. But that spends an extra label and an extra unconditional jump for no benefit. Testing the negation and jumping out when false lets the true case simply fall through into the body, which is both shorter and the natural order the instructions already sit in. Falling through is free; a jump costs a cycle and, on a real pipeline, risks a branch misprediction. Good jumping code minimises taken branches, so "arrange the common path to fall through" is a rule that echoes all the way down to the silicon.

Two errors dominate hand-written control-flow lowering. First, fall-through: forget the goto Lend at the end of the "then" branch of an if-else, and control tumbles straight from S_1 into S_2 — both branches run. The unconditional jump over the "else" arm is not optional. Second, the loop guard's polarity: because you test the guard's negation to jump out, mixing up <= with < (or > with >=) produces the classic off-by-one — the loop runs one iteration too many or too few. When in doubt, write the condition under which you want to stay in the loop, then negate it exactly once for the exit jump.