Translating expressions and control flow, backpatching

Why it exists

Boolean expressions are used in two ways: to compute a value (x = a < b), or, far more often, to decide where control goes (if (a < b) ...). In the second case there is no need to compute a boolean at all: the translator can emit jumps. This makes conditions cheap, and it allows short-circuit evaluation: in B1 || B2, once B1 is true the code never evaluates B2 (a semantic requirement in C). The two main techniques are jumping code with labels and backpatching for one-pass translation.

Prerequisites

You need the three-address instructions, in particular the jumps (goto L, if x relop y goto L, ifFalse) (three-address code).

Precise definitions

Short-circuit (jumping) code for conditions. The grammar $B \to B_1 \mid\mid B_2 \mid B_1 \,\&\&\, B_2 \mid ! B_1 \mid ( B_1 ) \mid E_1 \,\text{rel}\, E_2 \mid \text{true} \mid \text{false}$. Each $B$ gets two labels: B.true, where control goes if $B$ is true, and B.false, where it goes if $B$ is false. The code of $B$ jumps to one of them. Rules:

Fall-through (the label fall). If one of the targets is the instruction that comes right after the test, no jump is needed. The special label fall means "continue with the next instruction". For $E_1 \,\text{rel}\, E_2$ the code is then: if both labels are real, if test goto B.true followed by goto B.false; if only B.true is real, just if test goto B.true; if only B.false is real, ifFalse test goto B.false; if both are fall, nothing. The ifFalse instruction is the three-address form of "jump if the test fails". This removes most of the redundant gotos.

Statements. Every statement $S$ has an inherited label S.next for the instruction that follows it.

Boolean values. When a boolean value is needed, as in x = a < b, the translator produces code that sets a temporary to 1 or 0 using the jumping code: if a < b goto L1, t = 0, goto L2, L1: t = 1, L2: x = t.

Backpatching. In the label method a statement must know S.next before its code is generated (an inherited attribute), which forces either two passes or symbolic labels that a later pass resolves. Backpatching generates the jump instructions with empty targets and fills them in later, in one pass with an LR parser. The attributes are lists of instruction numbers:

• B.truelist: the jumps in the code of $B$ that must go to the code that follows when $B$ is true; B.falselist likewise for false;
• S.nextlist: the jumps that must go to the instruction after $S$.

Three functions work on lists: makelist(i) creates a list holding the instruction number i; merge(p1, p2) concatenates two lists; backpatch(p, i) sets the target of every jump on list p to i. A global counter nextinstr is the number of the next instruction to be emitted. Marker nonterminals record nextinstr at the right moment: $M \to \varepsilon\ \{M.instr = nextinstr\}$, and $N \to \varepsilon\ \{N.nextlist = makelist(nextinstr);\ gen(\text{goto \_})\}$ emits an unconditional jump with an empty target.

At the end the nextlist of the whole program is backpatched to the first instruction after the code.

How it works

Jumping code for the condition $x < 100 \mid\mid x > 200 \;\&\&\; x \ne y$ in an if. Because the then-part follows the test, B.true is fall, and the code is shown instruction by instruction with the rule that produced it. The first test jumps forward to the body (L2) when true; the other two tests jump to the end (L1) when false.

A while loop: the label L1 marks the test, the test jumps out when false, and the body ends with goto L1. (The textbook translation of s = s + i includes the copy from a temporary.)

The same if statement by backpatching. Instructions are numbered from 100. Every comparison emits two jumps, if ... goto _ and goto _, whose indices go into the truelist and falselist. When the parser reaches || it patches the falselist of the first condition to the start of the second (the marker), and so on. Watch the _ become numbers.

And the loop by backpatching. The test is at 100; its false exit stays open until the whole loop is complete; the back jump at the end is patched to the start.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The instructions used here are those of three-address code; the translation rules are a translation scheme built on the expression translation of intermediate code generation. The jump instructions create the leaders from which basic blocks and the flow graph are built.

PYQs

Consider the following statements about the use of
backpatching in a compiler for intermediate code
generation:

(I) Backpatching can be used to generate code for
Boolean expressions in one pass.

(II) Backpatching can be used to generate code for
flow-of-control statements in one pass.

Which ONE of the following options is CORRECT?

Self-check

Revision card

References