Boolean Expressions and Backpatching

Booleans live a double life. Sometimes a program wants a boolean's value — flag = (a < b) stores a 1 or a 0. But far more often a boolean is used only to steer control: if (a < b && c < d) … never needs the number, only the branch it decides. A good compiler translates these two uses differently, and the second — the jumping-code translation — is where the deep and delightful technique of backpatching lives. This page is about generating short-circuit boolean code in a single pass, even though, at the moment you emit a jump, you do not yet know where it should go.

Two representations of a boolean

Short-circuit semantics are the reason control-flow code is more than an optimisation — it is often required. In B_1 \;\&\&\; B_2, if B_1 is false the whole thing is false and B_2 must not be evaluated (it might dereference a null pointer that B_1 was guarding against). Dually, in B_1 \;\Vert\; B_2, if B_1 is true we skip B_2. Jumping code expresses this directly: each operand jumps away the instant its outcome settles the result.

The one-pass problem

Here is the bind. Generating code in a single forward pass, consider if (a < b) goto ???. At the moment the parser reduces the condition a < b, it must emit a conditional jump — but the target of that jump is code that has not been generated yet (the "then" branch, or whatever follows the if). We know a jump is needed; we do not yet know its label. Two escapes exist: make a second pass (wasteful), or emit the jump with the target field left blank and remember to fill it in later, once the target's address is known. That deferred filling-in is backpatching.

Truelists, falselists, and three little functions

Every boolean sub-expression B synthesizes two lists of incomplete jumps:

The semantic rules wire these together. For B \to B_1 \;\&\&\; B_2: once we see the && we know that if B_1 is true we must go on to test B_2, so we \textit{backpatch}(B_1.\textit{truelist}, M) where M is the label at the start of B_2's code. Then B.\textit{truelist} = B_2.\textit{truelist} (both must be true) and B.\textit{falselist} = \textit{merge}(B_1.\textit{falselist}, B_2.\textit{falselist}) (either being false makes B false). The rule for || is the exact mirror: backpatch B_1.\textit{falselist}, merge the truelists.

A worked example: if (a < b || c < d) then S

Trace the lists as the code is emitted top to bottom. Instructions are numbered; _ marks an as-yet-unknown target waiting to be backpatched.

#emittedon the listaction
100if a < b goto _B1.truelist = {100}true ⇒ whole OR is true
101goto _B1.falselist = {101}false ⇒ must test B2
—label M = 102backpatch B1.falselist→102
102if c < d goto _B2.truelist = {102}true ⇒ whole OR is true
103goto _B2.falselist = {103}false ⇒ OR is false

After the || rule: B.\textit{truelist} = \textit{merge}(\{100\},\{102\}) = \{100,102\} and B.\textit{falselist} = \{103\}. When the parser later sees the then S, it backpatches the whole truelist \{100,102\} to the label at the start of S, and the falselist \{103\} to whatever follows the if. Every blank _ is now filled — in a single forward pass.

Backpatching, in code

We model the machine directly: an array of instructions with mutable target fields, and the three operations. We build the code for a < b || c < d guarding a statement S, then backpatch and print the finished, fully-targeted TAC.

type Instr = { text: string; target: number | null }; // target null = blank, to be patched const code: Instr[] = []; const emit = (text: string, hasTarget: boolean): number => { code.push({ text, target: hasTarget ? null : -1 }); return code.length - 1; // its instruction index }; // The three list operations. const makelist = (i: number): number[] => [i]; const merge = (p: number[], q: number[]): number[] => [...p, ...q]; const backpatch = (list: number[], label: number): void => { for (const i of list) code[i].target = label; }; // --- Generate: a < b || c < d --- const i100 = emit("if a < b goto", true); // B1: true-jump const b1true = makelist(i100); const i101 = emit("goto", true); // B1: false-jump const b1false = makelist(i101); // We hit '||': B1 false means "go test B2", which starts at the NEXT instruction. const M = code.length; // label at start of B2 backpatch(b1false, M); const i102 = emit("if c < d goto", true); // B2: true-jump const b2true = makelist(i102); const i103 = emit("goto", true); // B2: false-jump const b2false = makelist(i103); // '||' combining rule: truelists merge, falselist = B2's falselist. const B_true = merge(b1true, b2true); const B_false = b2false; // --- The enclosing 'if B then S': emit S, then patch. --- const Sstart = code.length; emit("S: ... then-branch ...", false); const after = code.length; // where control goes when B is false backpatch(B_true, Sstart); // true -> run S backpatch(B_false, after); // false -> skip S code.forEach((ins, i) => console.log(`${100 + i}: ${ins.text}${ins.target !== null && ins.target >= 0 ? " " + (100 + ins.target) : ""}`) ); console.log(`truelist = {${B_true.map((i) => 100 + i).join(",")}} falselist = {${B_false.map((i) => 100 + i).join(",")}}`);

Run it: the two if … goto jumps (100 and 102) end up patched to the start of S, the first goto (101) points into the test of the second operand, and the last goto (103) skips past S. No second pass, no placeholder left blank.

It predates high-level compilers — it comes from assemblers and early linkers coping with forward references. When an assembler met JMP done before it had seen the label done:, it could not know the address, so it left the operand as a hole and kept a list of such holes. When done: finally appeared, the assembler walked back and "patched" every hole with the now-known address — literally writing back into instructions it had already emitted. Compilers inherited the trick wholesale for short-circuit booleans and jumping code. It is the same idea a modern linker uses when it resolves relocations: emit now, record the hole, fill it when the address is known.

The whole point of jumping code for && and || is preserving short-circuit semantics, and the classic bug is to break them by evaluating both operands unconditionally (as a numerical translation of t = (B1 & B2) would). Consider if (p != null && p.x > 0). If you evaluate p.x whenever you compute the boolean, you dereference null exactly when the guard was meant to protect you — crash. Correct jumping code emits B2's test only on the path where B1 was true, so p.x is never touched when p is null. When you hand-lower &&, always route B1's false-exit around B2's code, never through it.