Intermediate code generation

Why it exists

A compiler could translate a source program straight into machine code, but it is much better to go through an intermediate representation (IR) between the front end and the back end. The IR is independent of the source language and of the target machine. That makes it possible to build the front end for a language once and attach back ends for several machines ($m + n$ pieces instead of $m \times n$, see phases of a compiler), and it gives the optimiser a simple, uniform form on which to work.

Prerequisites

You need syntax-directed translation, in particular schemes that build code while parsing (translation schemes).

Precise definitions

Kinds of intermediate representation.

Three-address code. Every instruction has at most one operator on the right side, so a compound expression is broken up and the compiler invents temporaries to hold the intermediate values. For $a = b * -c + b * -c$ the code is

t1 = minus c
t2 = b * t1
t3 = minus c
t4 = b * t3
t5 = t2 + t4
a = t5

The name "three-address" refers to the instruction x = y op z, with addresses for $x$, $y$ and $z$. An address is a name of the source program (the compiler uses the symbol-table entry), a constant, or a compiler-generated temporary.

Translation of expressions by a syntax-directed definition. Each expression node $E$ has an attribute $E.addr$ (where the value is held) and, in the non-incremental version, $E.code$ (the code that computes it):

Here || concatenates code and gen makes one instruction. The definition is S-attributed. In practice the code is not stored in attributes: the translator emits the instructions one by one as the parser reduces (the incremental translation, a postfix translation scheme), so the instructions come out in a bottom-up order and operands are always computed before they are used.

Temporaries. Every operator node creates a fresh temporary. A compiler may reuse a temporary after its last use (a stack-like discipline), but the textbook examples give each temporary a new name. In the textbook translation the assignment $S \to \text{id} = E$ ends with a copy id = E.addr, so $a = b + c$ takes two instructions (t1 = b + c; a = t1); optimising translators emit the final operator directly into a.

Arrays. An element address is computed from the base address and the index: for a one-dimensional array with element width $w$, the element A[i] is at $\text{base} + i \times w$ (adjusted for the lower bound); for a two-dimensional array stored row by row with $n_2$ columns, A[i1][i2] is at $\text{base} + (i_1 \times n_2 + i_2) \times w$ (the address formulas). The intermediate code has indexed copies: x = y[i] and x[i] = y (here i is an offset in bytes in the textbook; in this page's examples the index is the element number).

Types and declarations. The translator keeps a type for every name and expression, computed by the semantic rules (type expressions: basic types, arrays, records, pointers, functions). From the types it computes the width (size in bytes) of each name and assigns offsets in the activation record or the static area, which the symbol table stores; the addresses in the generated code are relative to these. Type conversions (inttofloat) are inserted when the types of operands differ.

How it works

The animation generates the code for $a = b * -c + b * -c$ one instruction at a time, in the order a bottom-up translator emits them (the rows are the instructions, the right-hand column says which production caused each). Note that the same product b * -c is computed twice.

A DAG for the same expression has one node for -c and one for b * -c, and the sum has both its children pointing to the same node. Built from the code above instruction by instruction: when t3 = minus c asks for the node (minus, c0) it already exists, so t3 is just attached to it, and likewise t4. The code regenerated from the DAG computes each subexpression once.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The code is produced by translation schemes during parsing. Its concrete storage formats are on three-address code, quadruples and triples, the translation of conditions and loops on control-flow translation and backpatching, and the sharing of subexpressions on DAG representation of basic blocks. The code is then cut into basic blocks for optimisation. Array offsets use the formulas of multidimensional array addressing.

PYQs

In the context of compilers, which of the following
is/are NOT an intermediate representation of the
source program?

Consider the following code segment.

x = u - t;

y = x * v;

x = y + w;

y = t - z;

y = x * y;

The minimum number of  variables required to
convert the above code segment to static single
assignment form is ________.

In the context of abstract-syntax-tree (AST) and
control-flow-graph (CFG), which one of the
following is TRUE?

COMPILER DESIGN

One of the purposes of using intermediate code in
compilers is to:-

Some code optimizations are carried out on the
intermediate code because

Self-check

Revision card

References