Chapter 23 of 33

Intermediate Code & Three-Address Code

Imagine translating books between 5 languages. Translating directly between every pair needs 5 × 4 = 20 translators. If everyone translates into one shared language first, and from it into the target, you need only 5 translators into the shared language plus 5 out of it: 10 in total, and adding a sixth language costs 2 more translators, not 10.

Compilers face the same problem with many source languages (C, C++, Rust, Swift, ...) and many target machines (x86-64, ARM, RISC-V, ...). Their solution is the same: translate the source into a shared, simple, machine-independent language first. That language is the intermediate representation.

Intermediate code (an intermediate representation, IR) is a representation of the program produced by the front end of a compiler, after analysis, and consumed by the back end. It is independent of the source language's syntax and, ideally, of the target machine. Three-address code is the most widely used form of intermediate code in textbooks and exams.

In this chapter we will see why compilers use an IR, compare the main IR forms (syntax trees, DAGs, postfix, three-address code, SSA), learn every kind of three-address instruction, and generate three-address code for expressions, assignments and array references with a syntax-directed translation. We will also look at the real three-address IR that GCC produces. The generated code in this chapter was checked by a script that runs the three-address code and compares its results with direct evaluation, and array offsets were measured in C.


Why Use Intermediate Code?

  C ──────┐                              ┌────→ x86-64
  C++ ────┤    front ends       back ends├────→ ARM
  Rust ───┼──→       IR      ──→         ├────→ RISC-V
  Swift ──┘   (analysis)    (synthesis)  └────→ WebAssembly

  m languages + n targets  →  m front ends + n back ends   (not m × n compilers)
  • Retargeting: to support a new processor, write only a new back end. The front ends are reused. LLVM and GCC are built exactly this way.

  • Machine-independent optimization: optimizations such as removing common subexpressions or moving code out of loops are written once, on the IR, and help every language and every target.

  • Simplicity: the IR has a few simple instructions with explicit temporaries and explicit jumps. A source construct like x = a[i] * (b + c) or a for loop is broken into small steps that are easy to analyse and easy to map to machine instructions.

The cost is an extra translation step, which is tiny compared with the benefits.


Forms of Intermediate Representation

IRs are often described as high-level (close to the source, e.g. syntax trees) or low-level (close to the machine, e.g. three-address code with explicit addresses). Real compilers often use several, lowering the program step by step. We will use one expression throughout:

x = (a + b) * (a - c) / -d

1. Syntax Tree

The abstract syntax tree built by the parser's actions (see Syntax-Directed Definitions): operators at interior nodes, operands at leaves.

            =
          /   \
         x     /
             /    \
            *      minus
          /   \      |
         +     -     d
        / \   / \
       a   b a   c

2. DAG (Directed Acyclic Graph)

A syntax tree in which identical subexpressions are shared instead of repeated. A DAG node has one node for each distinct value, so it directly shows common subexpressions. Take (x + y) * (x + y) - z / (x + y):

Syntax tree (13 nodes):

               -
            /     \
          *          /
        /   \      /   \
       +     +    z     +
      / \   / \        / \
     x   y x   y      x   y

DAG (7 nodes):

               -
             /   \
            *     /
            ‖    / \
            ‖   z   │
            ‖       │
            + ◄─────┘        (‖ : both operands of * are this same + node)
           / \
          x   y

In the DAG, the single + node is used three times: twice by * (both operands) and once by /. The DAG is built with the same SDD as the syntax tree, except that before creating a node, the constructor checks whether an identical node (same operator, same children) already exists and returns it if so. This check is called value numbering. Here is the order in which the nodes are created:

Node

Label

Children

1

x (leaf)

-

2

y (leaf)

-

3

+

1, 2

4

*

3, 3

5

z (leaf)

-

6

/

5, 3

7

-

4, 6

The second and third x + y each find node 3 already present, so no new nodes are made for them. (DAGs for whole basic blocks, with assignments and dead values, are covered in DAG Representation of Basic Blocks.)

3. Postfix Notation

Operators written after their operands, with no parentheses needed. It is a linear form and is natural for stack machines:

x a b + a c - * d uminus / =

Java bytecode and Python bytecode are stack-based, so they are close relatives of postfix notation.

4. Three-Address Code

A sequence of simple instructions, each with at most one operator on the right side:

t1 = a + b
t2 = a - c
t3 = t1 * t2
t4 = minus d
t5 = t3 / t4
x  = t5

This is the form we study in detail below.

5. Static Single Assignment (SSA)

A refinement of three-address code in which every variable is assigned exactly once in the program text. When a variable is assigned again, it gets a new version number. Where two control paths meet with different versions, a special φ (phi) function selects the right one. LLVM IR and GCC's internal optimizer both use SSA, because "each name has exactly one definition" makes many optimizations much simpler.

Ordinary TAC          SSA form
x = a + b             x1 = a + b
y = x * c             y1 = x1 * c
x = y - a             x2 = y1 - a
z = x + y             z1 = x2 + y1
y = z * 2             y2 = z1 * 2

if (p) x = 1; else x = 2;      →   if p goto L1
y = x + 5;                          x1 = 2;  goto L2
                               L1:  x2 = 1
                               L2:  x3 = φ(x1, x2)
                                    y1 = x3 + 5

In the first example, SSA uses 8 distinct variable names in total: the inputs a, b and c, plus x1, y1, x2, z1 and y2. Questions of the form "how many variables does the SSA form need?" are answered by counting exactly like this.

Comparison

Form

Shape

Level

Strengths

Used in

Syntax tree

Tree

High

Keeps source structure; good for type checking

Front ends of all compilers

DAG

Graph

High/medium

Exposes common subexpressions

Local optimization

Postfix

Linear

Medium

Compact; easy to interpret with a stack

Stack VMs (JVM, Python)

Three-address code

Linear

Low

Explicit temporaries and jumps; close to machine code

Textbooks; GCC's GIMPLE

SSA

Linear + φ

Low

One definition per name; simplifies data-flow analysis

LLVM IR, GCC's optimizer


Three-Address Code

Three-address code (TAC) is a sequence of instructions of the general form x = y op z, where x, y and z are addresses (names, constants or compiler-generated temporaries) and op is a single operator. Each instruction has at most three addresses and at most one operator on its right side.

"Address" here means any of three things:

  • A name from the source program (in a real compiler, a pointer to its symbol-table entry).

  • A constant.

  • A temporary created by the compiler, usually written t1, t2, .... Temporaries hold intermediate results; the code generator later keeps them in registers where possible.

Why "at most one operator"? Because that is roughly what one machine instruction does. A source expression with many operators is broken into a sequence of steps, and the evaluation order is made explicit. The name "three-address" comes from the most common form, which mentions three addresses: two operands and a result.

The Instruction Set

Form

Instruction

Meaning

Binary assignment

x = y op z

Arithmetic or logical operation: +, −, *, /, &&, ||, ...

Unary assignment

x = op y

Unary minus, logical not, type conversion (e.g. x = (float) y)

Copy

x = y

Copy the value of y into x

Unconditional jump

goto L

The next instruction executed is the one labelled L

Conditional jump

if x goto L
ifFalse x goto L

Jump to L if x is true (or false); otherwise continue

Relational jump

if x relop y goto L

Compare with <, ≤, ==, ≠, >, ≥ and jump if true

Procedure call

param x1 ... param xn
call p, n
y = call p, n

Pass n parameters, then call p (optionally keeping the result); return y returns a value

Indexed copy

x = y[i]
x[i] = y

Read or write the location i memory units past the start of y (or x)

Address and pointer

x = &y
x = *y
*x = y

Take an address; read through a pointer; write through a pointer

A function call y = f(a, b + 1) becomes:

t1 = b + 1
param a
param t1
y = call f, 2

The 2 is the number of parameters, which matters when calls are nested, like f(a, g(b)): the param instructions of the inner call come between those of the outer one, and the count tells each call how many to take.

Note that the index in x = y[i] is in memory units (bytes), not elements. Converting an element index into a byte offset is the compiler's job, as we will see with arrays.


Translating Expressions into TAC

We now write a syntax-directed translation that produces TAC. Each expression E gets two synthesized attributes:

  • E.addr: the address (name, constant or temporary) that will hold E's value.

  • E.code: the TAC that computes it.

Helpers: newtemp() returns a fresh temporary each time it is called; gen(...) builds one TAC instruction; || concatenates code; top.get(id.lexeme) looks the name up in the symbol table.

Production

Semantic rules

S → id = E ;

S.code = E.code || gen(top.get(id.lexeme) '=' E.addr)

E → E1 + E2

E.addr = newtemp()
E.code = E1.code || E2.code || gen(E.addr '=' E1.addr '+' E2.addr)

E → E1 * E2

(same as +, with *)

E → − E1

E.addr = newtemp()
E.code = E1.code || gen(E.addr '=' 'minus' E1.addr)

E → ( E1 )

E.addr = E1.addr
E.code = E1.code

E → id

E.addr = top.get(id.lexeme)
E.code = '' (empty)

Two details are worth noticing. A plain identifier generates no code: its address is simply the variable itself, so a + b becomes t1 = a + b, not t1 = a; t2 = b; t3 = t1 + t2. And parentheses generate no code either: they only affect the shape of the tree.

Incremental Translation

Building long code strings and concatenating them is wasteful. Since the code for E1 and E2 always comes before the instruction for E itself, a translator can instead emit each instruction into one growing output as soon as it is created. The code attribute disappears:

E → E1 + E2   { E.addr = newtemp(); gen(E.addr '=' E1.addr '+' E2.addr); }
E → - E1      { E.addr = newtemp(); gen(E.addr '=' 'minus' E1.addr); }
E → ( E1 )    { E.addr = E1.addr; }
E → id        { E.addr = top.get(id.lexeme); }
S → id = E ;  { gen(top.get(id.lexeme) '=' E.addr); }

This is a postfix SDT, so it runs directly in a bottom-up parser (see Syntax-Directed Translation Schemes).

Worked Example 1

Translate x = (a + b) * (a - c) / -d. The actions run in postorder of the syntax tree, left operand first:

Reduction

Instruction emitted

E.addr

E → E1 + E2 (a + b)

t1 = a + b

t1

E → E1 − E2 (a − c)

t2 = a - c

t2

E → E1 * E2

t3 = t1 * t2

t3

E → − E1 (−d)

t4 = minus d

t4

E → E1 / E2

t5 = t3 / t4

t5

S → id = E

x = t5

-

Notice that minus d is computed only after t3, because the division's left operand is translated before its right operand. Our checking script ran this TAC with random values of a, b, c and d and compared it with direct evaluation: they always agreed.

Worked Example 2: Repeated Subexpressions

Translate y = a * -b + a * -b:

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

The tree-based translation computes a * -b twice. Generating code from the DAG instead would compute it once (t1 = minus b; t2 = a * t1; t3 = t2 + t2; y = t3). Removing such repeated work is common subexpression elimination, discussed in Code Optimization Techniques.


What a Real Compiler Produces

GCC's main mid-level IR, GIMPLE, is a three-address code. You can see it with gcc -fdump-tree-gimple. For this C code:

int f(int a, int b, int c, int d)
{
    return (a + b) * (a - c) / -d;
}

int sumsq(int n)
{
    int s = 0;
    for (int i = 0; i < n; i++)
        s = s + i * i;
    return s;
}

GCC 15.2 printed (in the file g.c.007t.gimple):

int f (int a, int b, int c, int d)
{
  int D.2847;

  _1 = a + b;
  _2 = a - c;
  _3 = _1 * _2;
  _4 = -d;
  D.2847 = _3 / _4;
  return D.2847;
}


int sumsq (int n)
{
  int D.2849;
  int s;

  s = 0;
  {
    int i;

    i = 0;
    goto <D.2845>;
    <D.2844>:
    _1 = i * i;
    s = s + _1;
    i = i + 1;
    <D.2845>:
    if (i < n) goto <D.2844>; else goto <D.2842>;
    <D.2842>:
  }
  D.2849 = s;
  return D.2849;
}

The first function is our worked example 1, instruction for instruction: _1 to _4 are GCC's temporaries, and D.2847 is a temporary for the return value. (The D.nnnn numbers are GCC's internal identifiers; your build may print different numbers, but the instructions are the same.) The loop shows the other half of TAC: the for statement has completely disappeared, replaced by labels (<D.2844> and so on), a goto and a conditional jump. GCC also placed the loop test at the bottom of the loop, a common layout that executes one jump per iteration instead of two.

A Loop in Textbook TAC

The same loop, written as numbered textbook TAC with the test at the top (the systematic way of producing such code from if and while statements is the subject of Translating Control Flow & Backpatching):

 1:  i = 0
 2:  s = 0
 3:  if i >= n goto 10
 4:  t1 = i * i
 5:  t2 = s + t1
 6:  s = t2
 7:  t3 = i + 1
 8:  i = t3
 9:  goto 3
10:  result = s

A classic slip is to write goto 9 on line 3. Line 9 is goto 3, so the loop could never exit: when we ran that version through a small TAC interpreter, it never finished. Jump targets are the most error-prone part of hand-written TAC, so always check where each jump lands. The code above gives the sums 0, 0, 1, 5, 14, 30, 55 for n = 0 to 6, which match 02 + 12 + ... + (n−1)2.


Addressing Array Elements

Array references are where TAC becomes truly low level, because the compiler must turn subscripts into byte offsets.

One Dimension

If array A starts at address base, each element is w bytes wide and indexes start at 0, then:

address of A[i] = base + i × w

If the lower bound is low instead of 0, the element is i − low positions from the start:

address of A[i] = base + (i − low) × w  =  i × w + (base − low × w)

The part in parentheses, base − low × w, does not depend on i, so the compiler computes it once at compile time; only i × w is computed at run time.

Two Dimensions

Memory is one-dimensional, so a 2-D array must be laid out in a line. C, C++ and Java store arrays in row-major order (row 0 first, then row 1, ...). Fortran, MATLAB and Julia use column-major order.

A[r][c] with n1 rows, n2 columns, element width w, lower bounds low1, low2:

row-major:     base + ((i − low1) × n2 + (j − low2)) × w
column-major:  base + ((j − low2) × n1 + (i − low1)) × w

In row-major order, to reach row i you skip i − low1 complete rows of n2 elements each, then move j − low2 more elements along the row.

Worked Example 3: TAC for an Array Reference

In C, int A[10][20]; with 4-byte ints. Translate x = A[i][j] + 1.

A row has 20 elements of 4 bytes = 80 bytes. So the offset of A[i][j] is i × 80 + j × 4:

t1 = i * 80
t2 = j * 4
t3 = t1 + t2
t4 = A [ t3 ]
t5 = t4 + 1
x  = t5

The type expression of A, array(10, array(20, integer)), is what tells the translator these numbers: the width of A[i] is the width of array(20, integer), which is 80, and the width of A[i][j] is the width of integer, 4 (see Semantic Analysis & Type Checking). We checked the formula in C by measuring (char *)&A[3][5] − (char *)&A[0][0]: it printed 260, and 3 × 80 + 5 × 4 = 260.

Worked Example 4: Exam-Style Address Calculation

An array A[1..10, 1..20] of 4-byte integers starts at address 1000. Find the address of A[5][7] in row-major and in column-major order.

n1 = 10 rows, n2 = 20 columns, w = 4, low1 = low2 = 1

Row-major:    1000 + ((5 − 1) × 20 + (7 − 1)) × 4
            = 1000 + (80 + 6) × 4
            = 1000 + 344            = 1344

Column-major: 1000 + ((7 − 1) × 10 + (5 − 1)) × 4
            = 1000 + (60 + 4) × 4
            = 1000 + 256            = 1256

For row-major order, the compile-time constant part is 1000 − (1 × 20 + 1) × 4 = 916, so the run-time address is 916 + (i × 20 + j) × 4. Check: 916 + (100 + 7) × 4 = 916 + 428 = 1344.


Solved Problems

Problem 1: Count the Temporaries

How many temporaries does the tree-based translation scheme above use for z = a * b + a * b * c, and how many would code from the DAG use?

Solution. The tree translation emits one temporary per operator node: t1 = a * b, t2 = a * b, t3 = t2 * c, t4 = t1 + t3, then z = t4. That is 4 temporaries (the multiplications are left associative, so a * b * c is (a * b) * c). In the DAG, a * b is one node, used twice, so there are only 3 operator nodes (6 nodes in all, versus 9 in the tree): t1 = a * b, t2 = t1 * c, t3 = t1 + t2, i.e. 3 temporaries.

Problem 2: TAC for a Call with an Array Argument

With int B[50] (4-byte ints), write TAC for y = f(B[k], k + 1).

t1 = k * 4
t2 = B [ t1 ]
t3 = k + 1
param t2
param t3
t4 = call f, 2
y  = t4

Arguments are fully evaluated before the param instructions (a common convention; the order of evaluating arguments is in fact unspecified in C).

Problem 3: SSA Conversion

Convert to SSA and count the total number of variables used:

p = q + r
q = p * 2
p = q - r
r = p + q

Solution. Give each assignment a new version, and make each use refer to the latest version:

p1 = q + r
q1 = p1 * 2
p2 = q1 - r
r1 = p2 + q1

The inputs q and r (their initial values) are still needed. Variables: q, r, p1, q1, p2, r1 = 6.


Common Mistakes

  • Putting two operators in one TAC instruction, like t1 = a + b * c. Each instruction has at most one operator.

  • Generating a temporary for every identifier. Names are already addresses; only operators need new temporaries.

  • Using the element index directly in x = A[i]. In TAC, the index is a byte offset: multiply by the element width.

  • Mixing up row-major and column-major formulas, or forgetting to subtract the lower bounds.

  • Wrong jump targets in hand-written loops. Trace every jump once.

  • Confusing SSA with "no copies". SSA means each variable is assigned once in the text; inside a loop, that single assignment can still execute many times.


Interview and Exam Questions

Q1. Why do compilers use intermediate code instead of generating machine code directly?

It separates the front end from the back end, so m languages and n targets need m + n components instead of m × n compilers, and it lets machine-independent optimizations be written once on a simple representation.

Q2. What is three-address code?

A linear IR whose instructions have at most one operator and at most three addresses, typically x = y op z, plus copies, jumps, conditional jumps, calls, indexed and pointer assignments.

Q3. Give the postfix form and the TAC for a * (b + c) - d.

Postfix: a b c + * d -. TAC: t1 = b + c; t2 = a * t1; t3 = t2 - d.

Q4. What is the advantage of a DAG over a syntax tree as an IR?

Identical subexpressions are represented by a single node, so common subexpressions are visible and computed only once in the generated code.

Q5. What is SSA form and why is it useful?

A form of IR in which every variable is assigned exactly once, with φ functions where control paths merge. Each use has exactly one reaching definition, which simplifies optimizations such as constant propagation and dead-code elimination. LLVM IR is in SSA form.

Q6. For char M[0..15][0..31] stored column-major at base 2000, what is the address of M[3][4]?

w = 1, n1 = 16 rows. Address = 2000 + (4 × 16 + 3) × 1 = 2000 + 67 = 2067.

Q7. Why does a call instruction carry the number of parameters?

Because param instructions of nested calls can be interleaved; the count tells each call how many of the most recent params belong to it.


Summary

  • An intermediate representation decouples front ends from back ends (m + n instead of m × n) and is where machine-independent optimization happens.

  • Main forms: syntax tree, DAG (shares common subexpressions), postfix, three-address code and SSA (one assignment per name, φ at merges).

  • TAC instructions have at most one operator: binary and unary assignments, copies, goto, conditional jumps, param/call/return, indexed copies, and address/pointer assignments.

  • Expressions are translated by an SDT with E.addr and newtemp(); identifiers and parentheses generate no code. Real compilers (GCC's GIMPLE) produce essentially the same code.

  • Array references become byte offsets: row-major base + ((i − low1) × n2 + (j − low2)) × w, with the constant part folded at compile time.

TAC is an abstract idea; to store it, a compiler needs concrete data structures. The next chapter, Quadruples, Triples & Indirect Triples, shows the three standard ways of representing three-address code in memory.