Chapter 25 of 33

Translating Control Flow & Backpatching

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.false

This 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.code = B1.code || label(B1.false) || B2.code

B → B1 && B2

B1.true = newlabel(); B1.false = B.false; B2.true = B.true; B2.false = B.false;
B.code = B1.code || label(B1.true) || B2.code

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.code = B.code || label(B.true) || S1.code

S → if ( B ) S1 else S2

B.true = newlabel(); B.false = newlabel(); S1.next = S2.next = S.next;
S.code = B.code || label(B.true) || S1.code || gen('goto' S.next) || label(B.false) || S2.code

S → while ( B ) S1

begin = newlabel(); B.true = newlabel(); B.false = S.next; S1.next = begin;
S.code = label(begin) || B.code || label(B.true) || S1.code || gen('goto' begin)

S → S1 S2

S1.next = newlabel(); S2.next = S.next;
S.code = S1.code || label(S1.next) || S2.code

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 goto is 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:

  1. i <= n emits 100, 101: truelist {100}, falselist {101}.

  2. i > 5 emits 102, 103; f == 1 emits 104, 105.

  3. The || reduction runs backpatch({103}, 104), giving truelist {102, 104}, falselist {105}.

  4. s = s + i emits 106 t1 = s + i and 107 s = t1. Then if (B) M S is reduced with M.instr = 106: backpatch({102, 104}, 106) and the if's nextlist = {105}.

  5. i = i + 1 emits 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 with i = i + 1.

  6. 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}.

  7. 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 a for).

  • 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 goto after 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; while patches the body's nextlist and B.truelist, emits goto back, 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.