Imagine writing directions for a friend on a single sheet of paper, top to bottom, without ever going back: "At the crossing, if the shop is open, go to step ?; otherwise go to step ?". You do not know the step numbers yet, because you have not written those steps. The obvious trick is to leave a blank, remember where the blank is, and fill it in once you know the number.
A compiler generating code for if, while and boolean conditions has exactly this problem. Three-address code, as we saw in Quadruples, Triples & Indirect Triples, has jumps like if a < b goto 105, but when the compiler emits that jump it usually has not yet generated instruction 105. This chapter shows how control-flow constructs are translated into jumps, why short-circuit code is used for boolean expressions, and how the "leave a blank and fill it later" trick, called backpatching, lets the whole job be done in a single pass.
Backpatching is the technique of generating jump instructions with their targets left unspecified, keeping lists of such incomplete jumps, and filling in (patching) the target of every jump on a list as soon as that target becomes known.
All code listings in this chapter were produced by a small one-pass translator written in Python that implements exactly the rules given below. The generated code was then executed on thousands of random inputs and compared with the meaning of the source program.
Two Ways to Represent a Boolean
A boolean expression such as a < b can be translated in two ways.
1. Numerical Representation
Compute the value as a number, 1 for true and 0 for false, and store it in a temporary, exactly like arithmetic:
t = a < b is translated as
100: if a < b goto 103
101: t = 0
102: goto 104
103: t = 1
104: ...This is what you need when the value is actually stored, as in flag = a < b;.
2. Flow-of-Control (Jumping) Representation
Most booleans are only used to decide where to go next, as in if (a < b) .... Then storing 0 or 1 is wasted effort. Instead, the value is represented by the position reached: the code jumps to one place if the condition is true and to another place if it is false.
if a < b goto B.true
goto B.falseThis form also gives short-circuit evaluation for free, which C, C++, Java and Python require: in B1 && B2, if B1 is false, B2 is never evaluated; in B1 || B2, if B1 is true, B2 is never evaluated. That is not just an optimization. In C, p != NULL && p->x > 0 is only safe because the second test is skipped when p is NULL.
Translation With Symbolic Labels
First let us see the idea with symbolic labels (L1, L2, ...), which is easiest to understand. Every boolean expression B gets two inherited attributes:
B.true: the label to jump to if B is true.
B.false: the label to jump to if B is false.
Every statement S gets an inherited attribute S.next: the label of the code that follows S. The function newlabel() creates a fresh label, and label(L) attaches L to the next instruction.
Boolean Expressions
Production | Semantic rules |
|---|---|
B → B1 || B2 | B1.true = B.true; B1.false = newlabel(); B2.true = B.true; B2.false = B.false; |
B → B1 && B2 | B1.true = newlabel(); B1.false = B.false; B2.true = B.true; B2.false = B.false; |
B → ! B1 | B1.true = B.false; B1.false = B.true; B.code = B1.code |
B → E1 relop E2 | B.code = E1.code || E2.code || gen('if' E1.addr relop E2.addr 'goto' B.true) || gen('goto' B.false) |
B → true / false | B.code = gen('goto' B.true) / gen('goto' B.false) |
(Here || in the rules means "concatenate code", not "or".) Read the || rule aloud: "if B1 is true, the whole thing is true, so go where B goes when true; if B1 is false, fall into a new label where B2 is tested, and B2 decides the final answer." Negation needs no code at all: it just swaps the two targets.
Statements
The code layouts are easiest to remember as pictures:
if (B) S1 if (B) S1 else S2 while (B) S1
B.code B.code begin: B.code
(to B.true / B.false) (to B.true / B.false) (to B.true / B.false)
B.true: B.true: B.true:
S1.code S1.code S1.code
B.false = S.next: goto S.next goto begin
... B.false: B.false = S.next:
S2.code ...
S.next:
...Production | Semantic rules |
|---|---|
S → if ( B ) S1 | B.true = newlabel(); B.false = S1.next = S.next; |
S → if ( B ) S1 else S2 | B.true = newlabel(); B.false = newlabel(); S1.next = S2.next = S.next; |
S → while ( B ) S1 | begin = newlabel(); B.true = newlabel(); B.false = S.next; S1.next = begin; |
S → S1 S2 | S1.next = newlabel(); S2.next = S.next; |
Example With Labels
Translate if (x < y && y < z) m = y; else m = x; with S.next = Lnext. The if-else rule creates B.true = L1 and B.false = L2; the && rule then creates B1.true = L3:
if x < y goto L3 // B1: true -> L3 (test B2), false -> L2
goto L2
L3: if y < z goto L1 // B2: true -> L1, false -> L2
goto L2
L1: m = y
goto Lnext
L2: m = x
Lnext:When x < y is false, the second comparison is never executed: that is short-circuit evaluation.
Why Labels Are Not Enough
Look at the rules again: B.true and B.false are inherited attributes, and they must be known before B's code is generated. That works if we first build a syntax tree and then walk it. But in a one-pass compiler that emits numbered quads during a bottom-up parse, the code for x < y is emitted when x < y is reduced, long before the parser has seen else, so it cannot know the instruction number of the else branch. Symbolic labels push the problem to a later pass (or to the assembler). Backpatching solves it directly.
Backpatching
The idea: emit every jump with an empty target (written _) and put the jump's instruction number on a list. All jumps on one list will eventually go to the same place. When that place is generated, walk the list and fill in its number. Three helper functions are used:
Function | What it does |
|---|---|
makelist(i) | Creates a new list containing only instruction number i, and returns it. |
merge(p1, p2) | Concatenates two lists and returns the result. |
backpatch(p, i) | Writes i as the target of every jump whose number is on list p. |
Instead of B.true and B.false (inherited labels), every boolean B now has two synthesized attributes:
B.truelist: numbers of the jumps that must go to the "true" place, once it is known.
B.falselist: numbers of the jumps that must go to the "false" place.
Every statement S has S.nextlist: jumps that must go to whatever follows S. Because all attributes are now synthesized, the translation fits a bottom-up parser perfectly. nextinstr is the number of the next instruction to be emitted.
The Marker Nonterminal M
We often need to remember "the instruction number where B2's code starts". For this we use the marker trick from Syntax-Directed Translation Schemes:
M → ε { M.instr = nextinstr; }The parser reduces M → ε exactly when it reaches M's position, so M.instr records the number of the first instruction generated after that point.
Backpatching Rules for Boolean Expressions
B → B1 || M B2 { backpatch(B1.falselist, M.instr);
B.truelist = merge(B1.truelist, B2.truelist);
B.falselist = B2.falselist; }
B → B1 && M B2 { backpatch(B1.truelist, M.instr);
B.truelist = B2.truelist;
B.falselist = merge(B1.falselist, B2.falselist); }
B → ! B1 { B.truelist = B1.falselist; B.falselist = B1.truelist; }
B → ( B1 ) { B.truelist = B1.truelist; B.falselist = B1.falselist; }
B → E1 rel E2 { B.truelist = makelist(nextinstr);
B.falselist = makelist(nextinstr + 1);
emit('if' E1.addr rel.op E2.addr 'goto _');
emit('goto _'); }
B → true { B.truelist = makelist(nextinstr); emit('goto _'); }
B → false { B.falselist = makelist(nextinstr); emit('goto _'); }
M → ε { M.instr = nextinstr; }Why backpatch(B1.falselist, M.instr) for ||? If B1 is false we must go on and test B2, and B2's code starts at M.instr. That target is known right now, so we patch immediately. The jumps for "true" are not known yet, so they stay on the merged truelist and travel upward.
Worked Example 1: A Boolean Expression
Translate a == b && (c < d || e > f), numbering instructions from 100. Here is the order in which the bottom-up parser performs the reductions, with the actions they run:
Step | Reduction | Effect |
|---|---|---|
1 | B → a == b | emit 100, 101; truelist = {100}, falselist = {101} |
2 | M → ε (after &&) | M.instr = 102 |
3 | B → c < d | emit 102, 103; truelist = {102}, falselist = {103} |
4 | M → ε (after ||) | M.instr = 104 |
5 | B → e > f | emit 104, 105; truelist = {104}, falselist = {105} |
6 | B → B || M B | backpatch({103}, 104); truelist = {102, 104}, falselist = {105} |
7 | B → ( B ) | lists unchanged |
8 | B → B && M B | backpatch({100}, 102); truelist = {102, 104}, falselist = {101, 105} |
The generated code:
100: if a == b goto 102
101: goto _
102: if c < d goto _
103: goto 104
104: if e > f goto _
105: goto _The whole expression has truelist = {102, 104} and falselist = {101, 105}. Those four blanks will be filled by whatever statement uses this condition. Check the logic: if a == b is false we reach 101, a false exit, without testing anything else (short circuit). If it is true we test c < d; true means the whole thing is true (102); false goes to 104 to test e > f.
Backpatching Rules for Statements
S → if ( B ) M S1
{ backpatch(B.truelist, M.instr);
S.nextlist = merge(B.falselist, S1.nextlist); }
S → if ( B ) M1 S1 N else M2 S2
{ backpatch(B.truelist, M1.instr);
backpatch(B.falselist, M2.instr);
S.nextlist = merge(merge(S1.nextlist, N.nextlist), S2.nextlist); }
S → while M1 ( B ) M2 S1
{ backpatch(S1.nextlist, M1.instr);
backpatch(B.truelist, M2.instr);
S.nextlist = B.falselist;
emit('goto' M1.instr); }
S → { L } { S.nextlist = L.nextlist; }
S → A ; { S.nextlist = null; } // assignment: falls through
L → L1 M S { backpatch(L1.nextlist, M.instr); L.nextlist = S.nextlist; }
L → S { L.nextlist = S.nextlist; }
N → ε { N.nextlist = makelist(nextinstr); emit('goto _'); }Two details deserve a comment:
N generates the jump that skips the else part at the end of the then part. Its target (the statement after the whole if-else) is unknown, so it goes on the nextlist.
In the while rule, the target for the backward jump, M1.instr, is already known (it is the start of the condition), so the
gotois emitted complete. Only the exit (B.falselist) is left open.
Worked Example 2: A Loop With an If Inside
Translate this fragment, numbering from 100:
while (i <= n) {
if (i > 5 || f == 1) s = s + i;
i = i + 1;
}The reductions, in the order the parser performs them:
i <= nemits 100, 101: truelist {100}, falselist {101}.i > 5emits 102, 103;f == 1emits 104, 105.The
||reduction runs backpatch({103}, 104), giving truelist {102, 104}, falselist {105}.s = s + iemits 106t1 = s + iand 107s = t1. Thenif (B) M Sis reduced with M.instr = 106: backpatch({102, 104}, 106) and the if's nextlist = {105}.i = i + 1emits 108, 109. The reduction L → L M S has M.instr = 108, so it runs backpatch({105}, 108): when the if-condition is false, continue withi = i + 1.The while is reduced with M1.instr = 100 and M2.instr = 102: the body's nextlist is empty, backpatch({100}, 102), emit 110
goto 100, and the while's nextlist = {101}.At the end of the program, the remaining list {101} is patched with the next instruction, 111.
100: if i <= n goto 102
101: goto 111
102: if i > 5 goto 106
103: goto 104
104: if f == 1 goto 106
105: goto 108
106: t1 = s + i
107: s = t1
108: t2 = i + 1
109: i = t2
110: goto 100
111: ...Notice 103: goto 104, a jump to the very next instruction. Backpatching does not care about elegance; such jumps are removed later by the optimizer (see Peephole Optimization). We executed this code for 2,000 random starting values of i, n, f and s, and it always produced the same final values as the source loop.
Worked Example 3: If-Else With Backpatching
The same if-else we translated with labels, if (x < y && y < z) m = y; else m = x;:
100: if x < y goto 102 // B1.truelist patched by the && rule
101: goto 106 // B.falselist {101, 103} patched to M2.instr = 106
102: if y < z goto 104 // B.truelist {102} patched to M1.instr = 104
103: goto 106
104: m = y
105: goto 107 // N.nextlist, patched when the next statement starts
106: m = x
107: ...Compare it with the label version: it is the same code, with L3 = 102, L1 = 104, L2 = 106 and Lnext = 107. Backpatching produces the code that the label scheme describes, but in one pass and with numeric targets.
Labels vs Backpatching
Point | Symbolic labels (B.true / B.false) | Backpatching (truelist / falselist) |
|---|---|---|
Attributes | Inherited (targets passed down) | Synthesized (lists passed up) |
Best suited to | Tree walk after parsing, or top-down parsing | Bottom-up parsing, one pass |
Jump targets | Labels, resolved later | Instruction numbers, filled in as soon as known |
Extra machinery | newlabel(), label() | makelist, merge, backpatch, markers M and N |
Code produced | Same jumping code | Same jumping code |
Other Control-Flow Constructs (Briefly)
do S while (B): code for S first, then B; B.truelist is patched back to the start of S, and B.falselist becomes the statement's nextlist.
break: emit
goto _and add it to a "break list" belonging to the innermost loop; the loop merges that list into its own nextlist. continue is similar, but its list is patched to the loop's condition (or increment, in afor).switch: either a sequence of conditional jumps (fine for a few cases), or, for many dense case values, a jump table indexed by the switch value, so the right case is reached in constant time.
for (init; B; incr) S: equivalent to
init; while (B) { S; incr; }and translated that way.
Common Mistakes
Patching the wrong list in
&&and||. For&&, B1's truelist goes to B2; for||, B1's falselist goes to B2. Ask yourself: "in which case do I still need to test B2?"Generating code for
!. Negation emits nothing; it only swaps truelist and falselist.Forgetting the N marker in if-else. Without the
gotoafter S1, the then part falls through into the else part.Leaving the while loop's exit to the body. The loop exits through B.falselist only; the body's nextlist is patched back to the condition.
Evaluating both operands of
&&/||. Jumping code must short-circuit; the language semantics demand it.Thinking backpatching needs two passes. Its whole purpose is to allow one-pass generation of jumps.
Interview and Exam Questions
Q1. What is backpatching and why is it needed?
Generating jumps with blank targets, recording them in lists, and filling the targets in when they become known. It is needed because in a one-pass (bottom-up) translation, the target of a forward jump has not been generated when the jump is emitted.
Q2. What do makelist, merge and backpatch do?
makelist(i) creates a list holding instruction number i; merge(p1, p2) concatenates two lists; backpatch(p, i) sets the target of every jump on list p to i.
Q3. For B → B1 || M B2, which list is backpatched and to what?
B1.falselist is backpatched to M.instr, the start of B2, because when B1 is false we must evaluate B2. B.truelist = merge(B1.truelist, B2.truelist) and B.falselist = B2.falselist.
Q4. How many instructions are generated for the condition a < b || c < d || e < f using the jumping-code scheme, and how many targets remain unfilled?
Each relational test emits two instructions, so 6 in all (100 to 105). The || reductions patch 101 to 102 and 103 to 104. Unfilled: truelist {100, 102, 104} and falselist {105}, so 4 targets remain until the enclosing statement is reduced.
Q5. In if (p && q || r) S, with short-circuit code, which conditions are evaluated when p is false?
p is false, so p && q is false without testing q. Then r must be tested. So p and r are evaluated, q is not.
Q6. Why are B.truelist and B.falselist synthesized, while B.true and B.false are inherited?
Labels must be known before B's code is generated, so they are passed down (inherited). Lists record jumps already generated inside B and are passed up to the construct that will eventually know the target (synthesized). Synthesized attributes suit bottom-up parsers.
Q7. What is the role of the marker nonterminals M and N?
M → ε records nextinstr, the number of the next instruction, at a point inside a production (for example the start of B2 or of a loop). N → ε emits an unconditional jump with a blank target (used after the then part of if-else) and returns it on N.nextlist.
Summary
Booleans can be translated numerically (0/1 in a temporary) or as jumping code, where the value is the place control reaches. Jumping code gives short-circuit evaluation.
With labels, B.true, B.false and S.next are inherited attributes that tell each piece of code where to jump.
Backpatching uses synthesized lists (truelist, falselist, nextlist) of incomplete jumps, the functions makelist, merge and backpatch, and the markers M (remember nextinstr) and N (emit a jump that skips the else part).
Key rules:
||patches B1.falselist to B2;&&patches B1.truelist to B2;!swaps lists;whilepatches the body's nextlist and B.truelist, emitsgotoback, and exits via B.falselist.Backpatching produces the same code as the label scheme, but in a single pass with numeric targets.
The code we generate will eventually call functions, and calls need memory for parameters, local variables and return addresses. The next chapter, Runtime Environment & Activation Records, explains how that memory is organised while the program runs.