Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 61 ยท Intermediate Code and Optimization

Backpatching and Code for Control Flow

Generate jump code for boolean expressions, if, if-else and while with backpatching: truelists, falselists, markers, short-circuit evaluation and a runnable generator.

When the compiler translates if (a < b) x = 1; else x = 2; into three-address code, it has to write jumps: "if a < b goto the code for x = 1, otherwise goto the code for x = 2". But at the moment it writes the first jump, the code for x = 1 has not been generated yet, so the target address does not exist. A jump to the future is a classic problem for one-pass compilers.

There are two ways out. A compiler with a separate pass can first build the whole tree and assign labels later. A compiler that wants to emit code in one pass, while it parses, uses backpatching: it writes the jump with a blank target, remembers where the blank is, and fills it in as soon as the target becomes known. This lesson explains the technique, which is also used by assemblers and by the code generators of many small compilers, shows how it compiles boolean expressions with short-circuit evaluation, and gives you a working generator.

Holes and lists of holes

Backpatching uses three small operations on lists of instruction numbers, where every number is an instruction that still has an unfilled jump target:

Operation Meaning
makelist(i) A new list containing only the instruction number i
merge(p1, p2) The union of two lists (just concatenation)
backpatch(p, target) Fill in target as the jump destination of every instruction in list p

A fourth helper, nextquad, returns the number of the next instruction to be emitted. It is the address you will jump to if you want to continue "right here". In the grammar, a tiny empty rule, the marker M -> ฮต, records nextquad at the right moment.

Boolean expressions as jumps

In a program, a boolean expression such as a < b || c < d has two uses: as a value stored in a variable, or as a condition that steers control flow. For conditions, it is wasteful to compute true or false and then test it. Instead, the compiler translates the expression into jumps, so that the position in the code encodes the result. This is called control-flow translation.

Every boolean expression B gets two synthesized attributes:

  • B.truelist: the jump instructions that must go to the code to run when B is true.
  • B.falselist: the jump instructions that must go to the code to run when B is false.

None of these targets are known while the expression is being translated, which is exactly why they are lists of holes.

A comparison x < y emits two instructions and creates the lists straight away:

TEXT
100: if x < y goto _      ; truelist = {100}
101: goto _               ; falselist = {101}

B1 || B2: if B1 is false, evaluation continues with B2, so the false exits of B1 can be filled in right now with the address where B2 begins, which a marker M provides. The result is true if either one is true:

TEXT
backpatch(B1.falselist, M.quad)
B.truelist  = merge(B1.truelist, B2.truelist)
B.falselist = B2.falselist

B1 && B2 is the mirror image: if B1 is true, go on to B2.

TEXT
backpatch(B1.truelist, M.quad)
B.truelist  = B2.truelist
B.falselist = merge(B1.falselist, B2.falselist)

! B1 costs no code at all: just swap the two lists. ( B1 ) passes both lists through.

Work through a < b || c < d with the first instruction numbered 0:

TEXT
0: if a < b goto _        B1.truelist = {0}   B1.falselist = {1}
1: goto _
   M.quad = 2
2: if c < d goto _        B2.truelist = {2}   B2.falselist = {3}
3: goto _
backpatch({1}, 2)         instruction 1 becomes "goto 2"
B.truelist = {0, 2}       B.falselist = {3}

Instruction 1 is now goto 2, a jump straight to the next instruction, a little wasteful but correct. Real compilers remove such jumps in a later pass (see local optimizations).

Short-circuit evaluation falls out for free

Because the right operand's code is entered only through the jump of the left operand, the right operand is never executed if the left one already decides the result. This is short-circuit evaluation: in p != 0 && 10 / p > 2, the division is guarded by the first test. The language rule that "&& and || don't evaluate their right operand needlessly" is not an extra feature in this scheme, it is a direct consequence of translating to jumps.

flowchart TD
    S["Start of condition"] --> A{"a < b?"}
    A -- "true" --> T["then-part"]
    A -- "false" --> C{"c < d?"}
    C -- "true" --> E{"e < f?"}
    C -- "false" --> F["else-part"]
    E -- "true" --> T
    E -- "false" --> F

The condition a < b || c < d && e < f: every test jumps straight to the then-part or the else-part.

Statements: the nextlist

Statements need a third kind of list. A statement S has the attribute S.nextlist: the jumps that leave S and should go to whatever comes after S. Which instruction that is cannot be known until the enclosing construct has finished.

Construct Translation
S -> if (B) M S1 backpatch(B.truelist, M.quad); S.nextlist = merge(B.falselist, S1.nextlist)
S -> if (B) M1 S1 N else M2 S2 backpatch(B.truelist, M1.quad); backpatch(B.falselist, M2.quad); S.nextlist = merge(S1.nextlist, N.nextlist, S2.nextlist) where N emits a goto _ that skips the else part
S -> while M1 (B) M2 S1 backpatch(S1.nextlist, M1.quad); backpatch(B.truelist, M2.quad); S.nextlist = B.falselist; emit goto M1.quad
S -> S1 M S2 backpatch(S1.nextlist, M.quad); S.nextlist = S2.nextlist
assignment emit the instruction; S.nextlist is empty

When the whole program has been translated, the last step is backpatch(S.nextlist, nextquad), so any remaining holes jump to the end.

The marker M -> ฮต can look scary in an LR grammar because it introduces conflicts, but in a recursive-descent generator it is simply a call to nextquad() at the right moment, which is how the program below handles it.

A complete generator

The program implements everything above in a recursive-descent parser. It compiles if, if/else, while, blocks, assignments and boolean conditions with ||, &&, !, parentheses and the relations < > <= >= == !=. It prints the generated code, and then runs the code in a small interpreter to check it against Python's own evaluation of the same condition for 729 different inputs.

Python A backpatching code generator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the output of the first program, instruction 1 is goto 2 (the filled-in false exit of a < b), and the instructions 3 and 5 both jump to the else part at 8, which is the merged falselist. The two statements x = 1 and x = 2 are separated by instruction 7, the goto 9 that skips the else part. Every goto _ hole has been replaced, and the interpreter agrees with Python on all 729 combinations.

The while example shows the loop structure: instruction 6 jumps back to the test at 0, and the exits at instructions 1 and 2 both go to 7, the halt. When i reaches 3 the !(i == 3) test fails and the loop stops, which is why the run ends with i = 3 and s = 3 (0 + 1 + 2).

Backpatching beyond expressions

The same idea appears in many places:

  • break and continue are jumps whose targets are the end or the start of the loop. A break adds its jump to a list owned by the enclosing loop, which is patched when the loop ends.
  • switch statements collect a jump per case and patch them when the labels are known.
  • Function calls to a function defined later in the file are patched when the function's address becomes known. A linker does the same across files, which is the topic of assemblers, linkers and loaders.
  • Assemblers use "forward references" to labels in the same way: the label's address is filled in during a second pass or by a patch list.

The price of backpatching is that the code generator must keep these lists around, and the code can be changed only through the lists afterwards. The benefit is a single pass and very little memory: a few integers per pending jump.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does backpatching solve?

    A forward jump is emitted with a blank target, its instruction number is remembered in a list, and the target is filled in as soon as it is known.
  2. 2. In the translation of B1 && B2, what is done with B1.truelist?

    If B1 is true, the answer depends on B2, so B1's true exits go to the start of B2's code.
  3. 3. How is the logical not, !B, translated?

    Because the lists describe where to go on true and on false, negation is just exchanging them.
  4. 4. What is the nextlist of a statement?

    The following instruction is not known until the enclosing statement has been completed, so those exits are collected in a list and patched later.
  5. 5. Why does p != 0 && 10 / p > 2 not divide by zero when p is 0?

    In control-flow translation the right operand's code can only be reached when the left operand's jump says it is needed.

Summary

  • Backpatching generates jumps in one pass: emit the jump with a blank target, remember its number in a list, and fill the blank when the target is known.
  • Three operations do all the work: makelist, merge and backpatch, plus nextquad and the empty marker M that records an address.
  • Boolean expressions carry a truelist and a falselist of unresolved jumps. ||, && and ! combine them, and short-circuit evaluation is a free consequence.
  • Statements carry a nextlist. if, if-else, while and sequences patch their sub-statements' lists, and the whole program patches the rest to the end.
  • The same mechanism handles break, switch, forward function calls and assembler labels.

Next, look at how the generated code is split into pieces for optimization in Control-Flow Graphs.