Intermediate Code Generation

Intermediate code sits between the front end and the back end, and the reason it exists is economic rather than technical.

Without it, supporting $m$ source languages on $n$ target machines requires $m\times n$ separate translators. With a common intermediate representation, each language needs one front end and each machine one back end, giving $m+n$.

For four languages and five targets that is 20 translators against 9, and the ratio worsens as either number grows.

The second reason is that optimisation belongs in the middle. Optimising the source is impractical because the structure is too rich; optimising the target is impractical because machine detail obscures the intent. An intermediate form is deliberately simple enough to analyse and abstract enough to remain machine-independent.

So every design decision about the representation follows from one question: what does the optimiser need to do to this code? Quadruples exist because optimisers move instructions. Explicit temporaries exist because optimisers track values. Explicit jumps exist because optimisers build control-flow graphs.

1. Three-Address Code

The standard intermediate form allows at most three addresses per instruction and exactly one operator.

$x=y\text{op}z$

Complex expressions are broken into a sequence of such instructions using compiler-generated temporaries. The expression $a+b\times c$ becomes two instructions: one computing $b\times c$ into a temporary, and one adding $a$ to it.

The instruction repertoire is small and is worth knowing exactly.

The number of temporaries needed equals the number of interior nodes in the expression tree, since each operator produces one intermediate value. That count is a standard numerical question.

Three-address code is close to assembly but machine-independent: it has unlimited temporaries, no registers, and no addressing modes.

2. Representations

Three ways of storing three-address code differ in how easily instructions can be moved, which matters entirely because of optimisation.

A quadruple has four fields: operator, first argument, second argument and result. The result is a named temporary, so an instruction can be moved anywhere without disturbing others.

A triple has three fields and no result field. The result is referred to by the instruction's own position, so instruction 3's output is written as "(3)".

That positional reference is the problem. Moving a triple changes its position and therefore invalidates every reference to it, so reordering requires renumbering everything.

An indirect triple adds a separate list of pointers to triples. Reordering means permuting the pointer list while the triples themselves stay put, so references remain valid.

Quadruples also make temporaries explicit, which lets an optimiser reason about a value's lifetime. Triples save the space of naming temporaries and lose exactly that ability.

A directed acyclic graph is a fourth representation used for a basic block. Identical subexpressions share a node, which exposes common subexpressions directly and makes their elimination a matter of reading the graph.

3. Translating Expressions

Expression translation is a syntax-directed definition with a synthesised attribute holding the place where the value lives.

For a production $E\to E_1+E_2$, generate code for both operands, allocate a temporary, and emit an addition into it.

Because every attribute flows upward, the definition is S-attributed and evaluates during a bottom-up parse with no separate tree traversal.

The temporary count can be reduced. Evaluating the more complex operand first minimises the number of temporaries live simultaneously, which is the Sethi-Ullman numbering idea and matters when registers are scarce.

For an expression tree, the minimum number of registers needed with no spilling is computed recursively: a leaf needs one, and an interior node needs the maximum of its children's requirements if they differ, or one more than either if they are equal.

4. Boolean Expressions and Control Flow

Boolean expressions can be translated two ways, and the choice is visible to the programmer.

Full evaluation computes the whole expression and produces a value, treating true and false as 1 and 0.

Short-circuit evaluation generates jumps and never computes a value at all. For A and B, if A is false the code jumps directly to the false target without evaluating B.

Short-circuiting is not merely an optimisation; it changes semantics. An expression such as p != null and p->x > 0 is correct only under short-circuiting, since full evaluation would dereference a null pointer.

Control flow translation uses inherited attributes carrying the true and false targets down the tree.

For if E then S, the true target of $E$ is the start of $S$ and the false target is the code after it. The condition never produces a value; it simply jumps to one of two labels.

For a while loop, the false target is the exit and the code after $S$ jumps back to re-test the condition.

5. Backpatching

The difficulty with generating jumps in one pass is that a jump's target is often not yet known. When translating if E then S, the address following $S$ is unknown until $S$ has been generated.

Backpatching solves this by emitting jumps with blank targets and recording their addresses in a list, then filling the targets in once they become known.

Three operations manage the lists.

Makelist creates a list containing one instruction index. Merge concatenates two lists. Backpatch fills a given label into every instruction in a list.

The mechanism lets a one-pass compiler generate correct jumps without building a tree or making a second pass.

Each Boolean expression carries two lists: the true list of jumps taken when it evaluates true, and the false list for when it evaluates false. A statement carries a next list of jumps to whatever follows it.

For E1 and E2, the false lists merge — either operand being false makes the whole expression false — while $E_1$'s true list is backpatched to the start of $E_2$, since $E_1$ being true means $E_2$ must be tested.

6. Arrays and Records

Array element addressing is arithmetic on the base address.

For a one-dimensional array with base address $b$, element size $w$ and lower bound $\text{low}$:

$\text{addr}(A[i])=b+(i-\text{low})\times w$

For a two-dimensional array in row-major order with $n_2$ columns:

$\text{addr}(A[i][j])=b+((i-l_1)\times n_2+(j-l_2))\times w$

The compiler factors this into a part computable at compile time and a part requiring run-time arithmetic. The constant portion is folded into the base, leaving only the index multiplications for run time.

Column-major order reverses the roles of the two indices, which changes the generated code and, more importantly, the memory access pattern.

For a record, each field sits at a fixed offset from the record's base, computed at compile time from the sizes of preceding fields. Alignment padding may be inserted, so the offset of a field is not simply the sum of the preceding sizes.

7. Type Checking and Conversion

The semantic analyser attaches a type to every expression and verifies that operators receive operands they accept.

Static type checking happens at compile time and dynamic type checking at run time. A statically typed language catches type errors before execution at the cost of rejecting some programs that would have run correctly.

Type conversion is widening when it loses nothing and narrowing when it may. Converting an integer to a floating-point value is widening; the reverse is narrowing and typically requires an explicit cast.

Implicit conversion inserted by the compiler is called coercion. In an expression mixing an integer and a float, the compiler generates a conversion instruction for the integer, and that instruction appears in the intermediate code.

Type equivalence comes in two flavours. Structural equivalence treats two types as the same if they have the same shape; name equivalence treats them as the same only if they have the same name. The distinction decides whether two identically-shaped records with different names are interchangeable.

8. Worked Examples

Example 1. Generate three-address code for $a=b\times c+b\times c+d$, and state how many temporaries a naive translation uses.

A naive left-to-right translation treats each operator independently.

$t_1=b\times c$

$t_2=b\times c$

$t_3=t_1+t_2$

$t_4=t_3+d$

$a=t_4$

Four temporaries, matching the four interior nodes of the expression tree.

Now build the directed acyclic graph for the same expression. The subexpression $b\times c$ appears twice, and in a DAG both occurrences share one node.

Regenerating from the DAG gives:

$t_1=b\times c$

$t_2=t_1+t_1$

$t_3=t_2+d$

$a=t_3$

Three temporaries and one fewer multiplication. The saving is common subexpression elimination, and the DAG is what made it visible without any separate analysis.

Example 2. Convert this three-address code to quadruples and triples: $t_1=a+b$, $t_2=t_1\times c$, $d=t_2$.

Quadruples name the result explicitly in a fourth field.

Triples drop the result field and refer to an instruction by its position.

The triple form is more compact, saving the space of naming two temporaries.

Now suppose the optimiser wants to move instruction 0 later. With quadruples, the instruction moves and nothing else changes, because $t_1$ is a name rather than a position.

With triples, instruction 1 refers to "(0)", so moving instruction 0 to position 2 requires rewriting that reference — and every other reference in the block. Any reordering means renumbering.

Indirect triples fix this by keeping the triples fixed and permuting a separate pointer array, so references stay valid.

Example 3. Translate if (a < b) x = 1; else x = 2; into three-address code with jumps.

Boolean conditions in control flow generate jumps rather than values.

    if a < b goto L1
    goto L2
L1: x = 1
    goto L3
L2: x = 2
L3:

The pattern is standard: test, jump to the true branch, fall through to the false branch, and have the true branch jump over the false one.

A common optimisation inverts the test to remove one jump.

    if a >= b goto L2
    x = 1
    goto L3
L2: x = 2
L3:

This saves an instruction on the true path, which is the more common case in most code.

Note that the condition produces no value anywhere. No temporary holds true or false; the entire meaning of the comparison is expressed in which label control reaches.

Example 4. Explain backpatching using if (a < b) then S.

Translation proceeds left to right in one pass, and the difficulty is that the address following $S$ is unknown when the condition is translated.

Step 1. Translate the condition. Emit two jumps with blank targets.

Instruction 100: if a < b goto ___

Instruction 101: goto ___

Record instruction 100 in the condition's true list and instruction 101 in its false list.

Step 2. The next instruction generated will be the start of $S$, at address 102. Since the condition being true means $S$ executes, backpatch the true list with 102.

Instruction 100 becomes if a < b goto 102.

Step 3. Generate $S$, occupying instructions 102 onward, say through 105.

Step 4. The statement is now complete. Its next list contains instruction 101, the false jump, which must go to whatever follows the whole if.

That address is still unknown, so instruction 101 stays blank and its index is passed upward in the next list of the if statement, to be backpatched by whatever encloses it.

The key insight is that a jump target is filled in as soon as it becomes known and no sooner, and lists carry the pending jumps upward until the enclosing construct can resolve them. This is what makes single-pass code generation possible without building a tree.

Example 5. An array is declared A[10][20] with 4-byte elements, base address 2000, and lower bounds of 1 in both dimensions. Generate the address computation for A[i][j] in row-major order.

The general formula with lower bounds is base plus the offset in elements times the element size.

$\text{addr}=2000+((i-1)\times 20+(j-1))\times 4$

Expand to separate the compile-time constants from the run-time work.

$\text{addr}=2000+(20i-20+j-1)\times 4=2000+80i+4j-84$

$=1916+80i+4j$

The constant 1916 is computed at compile time, so the generated code performs only two multiplications and two additions.

The three-address code is:

$t_1=i\times 80$

$t_2=j\times 4$

$t_3=t_1+t_2$

$t_4=t_3+1916$

$t_5=\ast t_4$

Under column-major order the roles reverse, giving $2000+((j-1)\times 10+(i-1))\times 4$, which folds to $1956+40j+4i$.

The difference matters for more than arithmetic: traversing a row-major array along rows walks contiguous memory, while walking columns strides across it and misses the cache repeatedly.

Example 6. Why does short-circuit evaluation change program meaning rather than merely improving speed?

Under full evaluation, both operands of a Boolean operator are computed before the operator is applied. Under short-circuiting, the second operand is evaluated only if the first does not already determine the answer.

If the second operand has no side effects and cannot fail, the two produce identical results and short-circuiting is purely an optimisation.

The difference appears the moment the second operand can fail or has an effect.

Consider p != null and p->value > 0. Under short-circuiting, a null p makes the first operand false, the answer is determined, and the dereference never happens. Under full evaluation, the dereference happens regardless and the program crashes.

Consider i < n and a[i] > 0. Short-circuiting prevents an out-of-bounds read when i equals n; full evaluation performs it.

Consider flag or increment(counter). Under short-circuiting, a true flag means the counter is never incremented, so the two evaluation strategies produce different program states.

This is why languages specify the behaviour rather than leaving it to the compiler. C, Java and most modern languages mandate short-circuiting for their logical operators and provide separate bitwise operators for the full-evaluation case.

For the compiler writer, the consequence is that the jump-based translation is not an alternative implementation of the value-based one. It is the required implementation, and generating code that evaluates both operands would be a correctness bug.

Summary

An intermediate representation turns $m\times n$ translators into $m+n$, and it is where optimisation belongs because the source is too rich to analyse and the target too detailed.

Three-address code allows one operator and at most three addresses, breaking expressions apart with compiler temporaries. The number of temporaries equals the number of interior nodes in the expression tree.

Quadruples name the result and can be reordered freely. Triples refer to results by position and cannot be reordered without renumbering. Indirect triples permute a pointer list instead, recovering cheap reordering.

A directed acyclic graph shares identical subexpressions, exposing common subexpressions directly and reducing both temporaries and operations.

Expression translation is S-attributed and evaluates during a bottom-up parse. Evaluating the harder operand first minimises simultaneously live temporaries.

Boolean expressions in control flow generate jumps rather than values. Short-circuit evaluation changes semantics, not merely speed, and is mandated by most language specifications.

Backpatching emits jumps with blank targets, records their indices in lists, and fills targets in as soon as they are known. Makelist, merge and backpatch manage the lists, and pending jumps propagate upward until an enclosing construct resolves them.

Array addressing folds the compile-time constant into the base, leaving only index arithmetic at run time. Row-major and column-major differ in both the formula and the cache behaviour.

Type checking may be static or dynamic; widening loses nothing while narrowing may; implicit conversion is coercion and appears explicitly in the intermediate code. Structural and name equivalence differ on whether identically-shaped named types are interchangeable.