Translating Expressions and Control Flow

Intermediate-code generation turns the syntax tree into three-address code with syntax-directed rules. Arithmetic expressions become sequences of temporaries; array references become address arithmetic; Boolean conditions become jumping code, in which the value of a condition is represented by where control goes rather than by a stored 0 or 1. Statements such as if, if-else and while are built from labels and jumps around that code.

Jumps forward to code not yet generated create a problem for a one-pass translator: the target is not known when the jump is emitted. Backpatching solves it by emitting jumps with empty targets, keeping lists of them, and filling them when the target becomes known. Examination questions ask for array addresses, the number of instructions in short-circuit code, and the true and false lists produced by backpatching.

The SDD for assignments is

This is a postfix SDT: every instruction is emitted when its production is reduced, so instructions appear in postorder, one per operator.

For a one-dimensional array with element width $w$ and lower bound 0, A[i] is at $base + i \times w$. For a two-dimensional array A[n1][n2] in row-major order with lower bounds 0,

With lower bounds $low_1$ and $low_2$, replace $i_1$ by $i_1 - low_1$ and $i_2$ by $i_2 - low_2$. In general the offset is built by Horner's rule: $((i_1 n_2 + i_2) n_3 + i_3) \cdots$, times $w$. Column-major order (Fortran) reverses the roles: $base + (i_2 \times n_1 + i_1) \times w$ for two dimensions.

Example 1. int A[10][20] with $w = 4$ at base 1000. Row-major: $A[3][5]$ is at $1000 + (3 \times 20 + 5) \times 4 = 1260$. Column-major: $1000 + (5 \times 10 + 3) \times 4 = 1212$.

Example 2. B[1..6][-2..2] with $w = 8$ at base 2000 (so $n_2 = 5$). Then $B[4][1]$ is at $2000 + ((4 - 1) \times 5 + (1 - (-2))) \times 8 = 2000 + 18 \times 8 = 2144$.

Example 3: three dimensions. int A[4][5][6] with $w = 4$ at base 1000. By Horner's rule the row-major offset of $A[2][3][4]$ in elements is $(2 \times 5 + 3) \times 6 + 4 = 82$, so the address is $1000 + 82 \times 4 = 1328$. The first dimension's size, 4, never enters the formula. If the same array is declared with lower bounds 1, as A[1..4][1..5][1..6], the subscripts become $1, 2, 3$: $(1 \times 5 + 2) \times 6 + 3 = 45$, and the address of $A[2][3][4]$ is $1000 + 180 = 1180$.

The three-address code for x = A[i][j] with int A[10][20] (row width $20 \times 4 = 80$) is

Here A[t3] uses the byte offset t3 from the base of A. Lower bounds other than 0 can be folded into a compile-time constant subtracted once, since $base - (low_1 n_2 + low_2) w$ does not depend on the subscripts.

The control-flow SDD gives each $B$ the inherited labels $B.true$ and $B.false$:

Negation generates no code: it swaps the labels.

For statements, with $S.next$ the label after $S$:

Example 4. if (x < 100 || x > 200 && x != y) x = 0; with $S.next = L_1$ (&& binds tighter than ||):

Short-circuiting is visible in the trace. With $y = 0$, $x = 50$ needs one comparison, $x = 150$ two, and $x = 250$ three. The goto L3 jumps to the next instruction; a peephole pass, or the fall-through variant of the rules, removes such redundant jumps.

In one pass, a jump's target may lie ahead. The backpatching scheme gives $B$ synthesized lists $B.truelist$ and $B.falselist$ of instruction numbers whose targets are still empty, and uses a marker $M \to \varepsilon\ \{M.instr = nextinstr\}$ to record where code for the next part starts:

Example 5. The same condition, x < 100 || x > 200 && x != y, with instructions numbered from 100. The three comparisons emit six instructions, 100 to 105. Reducing $x > 200 \mathbin{\&\&} x \ne y$ backpatches its first truelist $\{102\}$ with $M.instr = 104$. Reducing the || backpatches $\{101\}$ with $M.instr = 102$. The result is

with $B.truelist = \{100, 104\}$ and $B.falselist = \{103, 105\}$. The enclosing statement fills these later: for if (B) M S1, backpatch($B.truelist, M.instr$) points them at the start of $S_1$, and $S.nextlist$ = merge($B.falselist, S_1.nextlist$) is passed upward.

Example 6: while with backpatching. For while (a < b) a = a + 1 starting at 100, with $S \to \textbf{while}\ M_1\ (B)\ M_2\ S_1$: the condition emits 100 and 101; the body emits 102 and 103; then goto $M_1.instr$ is emitted. Backpatching $B.truelist = \{100\}$ with $M_2.instr = 102$ gives

and $S.nextlist = B.falselist = \{101\}$, to be filled with whatever instruction follows the loop.

Example 7: if-else with backpatching. The scheme uses two markers and a marker $N$ that emits the jump over the else part:

with backpatch($B.truelist, M_1.instr$), backpatch($B.falselist, M_2.instr$) and $S.nextlist$ = merge($S_1.nextlist, N.nextlist, S_2.nextlist$); $N \to \varepsilon$ sets $N.nextlist$ = makelist(nextinstr) and emits goto _. For if (a < b) x = 1; else x = 2; starting at 100:

Five instructions. $B.truelist = \{100\}$ is patched with $M_1.instr = 102$ and $B.falselist = \{101\}$ with $M_2.instr = 104$. The assignments leave no jumps, so $S.nextlist = N.nextlist = \{103\}$: only the jump at the end of the then-part waits for the instruction after the statement. The else-part simply falls through to it.

Common misconceptions.