Intermediate Languages

An intermediate language (or intermediate representation, IR) is a program form that sits between the source language and the target machine, designed to depend on neither.

The front end of a compiler does not emit machine code directly. Instead it translates the source program into an IR — a neutral, "halfway" notation. The back end then turns that IR into code for a specific machine.

Because the IR is independent of any one source language and any one machine, it becomes a clean meeting point: every front end produces it, every back end consumes it.

The one running example

Throughout this chapter we translate a single assignment statement.

We will see this same statement as a syntax tree, as three-address code, and as postfix — different IRs describing the same computation.

1. Retargeting — turning N×M into N+M.

Suppose you must support N source languages on M target machines. Writing one compiler for every pair means N × M separate compilers. With a shared IR you instead write:

• one front end per source language (source → IR) — N of them, and
• one back end per machine (IR → target) — M of them.

That is N + M pieces instead of N × M. Adding a new language costs one front end (it reaches every machine for free); adding a new machine costs one back end (every language targets it for free).

2. Machine-independent optimization.

The IR is the natural place to optimize. Transformations like constant folding, common subexpression elimination, and dead-code removal can be done once, on the IR, without knowing the target — so every back end benefits.

The pipeline

The optimizer takes IR in and gives IR out — it never leaves the neutral middle.

IRs fall into two broad families: tree-like (high-level, closer to the source) and linear (low-level, closer to the machine).

High-level (tree-like)

• Syntax tree — operators are internal nodes, operands are leaves; the tree shape captures the grouping.
• DAG — a syntax tree that shares identical subexpressions (one node, many parents) instead of duplicating them.

Here is the syntax tree for x = (a + b) \* (c - d) — root = with children x and the \* subtree:

Linear (low-level)

• Postfix (Polish) notation — operands first, operator after; needs no parentheses and no precedence rules.
• Three-address code — a flat sequence of simple instructions, each with at most one operator and up to three addresses (two operands, one result), using temporaries (t1, t2, …) to hold intermediate results.

The same statement as three-address code:

Each temporary names exactly one subtree of the syntax tree above: t1 is the + node, t2 is the - node, t3 is the \* node.

Tree-like vs. linear at a glance

The rest of this chapter zooms in on the two linear IRs. Most of it covers three-address code and its concrete implementations — quadruples, triples, and indirect triples — and we also look at postfix (Polish) notation. The syntax tree and DAG from the previous chapter remain the high-level starting point we translate from.

• An intermediate language / IR sits between source and target and depends on neither — the front end produces it, the back end consumes it.
• A shared IR turns the N × M compiler problem into N + M components: one front end per language, one back end per machine.
• The IR is the natural home for machine-independent optimization: source → front end → IR → optimizer → IR → back end → target.
• High-level / tree-like IRs (syntax tree, DAG) stay close to the source; linear / low-level IRs (postfix, three-address code) stay close to the machine.
• For x = (a + b) \* (c - d), three-address code uses temporaries — t1 = a + b, t2 = c - d, t3 = t1 \* t2, x = t3 — one per operator node of the syntax tree.