Intermediate Representations: Syntax Trees, DAGs and Three-Address Code: short notes (Compiler Design)

Revision mode

Introduction

Between the parser and the code generator, a compiler represents the program in one or more intermediate representations (IRs). A high-level IR such as a syntax tree keeps the source structure and suits type checking. A low-level IR such as three-address code is close to machine instructions but still independent of any particular machine, and suits optimisation and code generation. Using an IR lets one front end serve many targets and one optimiser serve many source languages.

This note covers the IRs that examination questions ask about: syntax trees, DAGs for expressions, postfix notation, three-address code and its three record layouts (quadruples, triples, indirect triples), and static single-assignment (SSA) form. Typical questions count DAG nodes, write three-address code, convert between quadruples and triples, or count variables after conversion to SSA.

Prerequisites

Syntax-Directed Definitions: building syntax trees as synthesized attributes, $E.node = \text{new Node}(\ldots)$ .
Operator precedence and associativity, which fix the shape of an expression tree (see the note Bottom-Up Parsing and Shift-Reduce).

Core concepts

Syntax tree (abstract syntax tree). Interior nodes are operators, children are operands; punctuation and chain productions are dropped. Each occurrence of a subexpression has its own subtree.
DAG for an expression. A syntax tree in which identical subexpressions are shared: a node has one copy and possibly several parents. Leaves are distinct identifiers and constants.
Postfix notation. The postorder listing of the syntax tree, operators after their operands.
Three-address code (TAC). A sequence of instructions, each with at most one operator on the right side and at most three addresses: $x = y \mathbin{op} z$ . Compiler-generated temporaries $t_1, t_2, \ldots$ hold intermediate values. An address is a name, a constant or a temporary.
Quadruple. A record (op, arg1, arg2, result).
Triple. A record (op, arg1, arg2) with no result field; a result is referred to by the triple's position, written $(i)$ .
Indirect triples. Triples plus a separate list of pointers to them giving the execution order.
SSA form. Every assignment targets a distinct name, and $\phi$ -functions merge values at points where control paths join.

How it works

Syntax tree versus DAG

Take $a + a * (b - c) + (b - c) * d$ . By precedence and left associativity it is $\big(a + (a * (b - c))\big) + \big((b - c) * d\big)$ .

The syntax tree has 13 nodes: 7 leaves ( $a, a, b, c, b, c, d$ ) and 6 operator nodes.
The DAG has 9 nodes: 4 leaves ( $a, b, c, d$ ) and 5 operator nodes, because the leaf $a$ and the subexpression $b - c$ are shared. It has 10 edges, two from each binary operator node.

Value-number method. Keep the nodes in an array, each identified by its index (its value number) and its signature $\langle op, l, r\rangle$ where $l$ and $r$ are value numbers of the children. Before creating a node, look the signature up in a hash table; if it is present, return the existing number. Leaves use signatures $\langle \textbf{id}, \text{entry}\rangle$ or $\langle \textbf{num}, \text{value}\rangle$ . A DAG is obtained by running the ordinary syntax-tree SDD with this lookup in the node constructors.

The postfix form is the postorder of the tree: a a b c - * + b c - d * +.

A second count, with a unary operator. For a = b * - c + b * - c, treating = as an operator node with children a and the right side, the syntax tree has 11 nodes (=, a, +, two *, two b, two minus, two c). The DAG has 7: leaves a, b, c, one minus, one *, the + (both of whose operands are the same * node), and =. The code from the DAG is 4 instructions instead of 6: t1 = minus c, t2 = b * t1, t3 = t2 + t2, a = t3.

Three-address instruction forms

Form	Example
Binary assignment	`x = y op z`
Unary assignment	`x = minus y`, `x = (float) y`
Copy	`x = y`
Unconditional jump	`goto L`
Conditional jump	`if x goto L`, `ifFalse x goto L`, `if x relop y goto L`
Procedure call	`param x1` ... `param xn`, then `call p, n` or `y = call p, n`; `return y`
Indexed copy	`x = y[i]`, `x[i] = y`
Address and pointer	`x = &y`, `x = y`, `x = y`

In call p, n the integer $n$ is the number of actual parameters, needed because calls can nest.

Generating TAC from a tree. Walk the tree in postorder; for each operator node emit one instruction into a new temporary. From the syntax tree of the example this gives 6 instructions. Generating from the DAG instead emits one instruction per operator node, 5 in all:

Text

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

Temporaries can be reused. The five instructions use five temporary names, but at most two temporaries hold live values at any point: $t_1$ is needed until t4 = t1 * d, and while it waits only one other temporary is live. Trying every order of the five instructions that respects the dependences (the operands of each instruction computed before it) confirms that 2 is the minimum. With names reused, the block is u1 = b - c, u2 = a * u1, u2 = a + u2, u1 = u1 * d, u1 = u2 + u1. One temporary cannot suffice, because $b - c$ has two uses and one of them must wait while another temporary is computed.

Quadruples, triples and indirect triples

For a = b * - c + b * - c the TAC from the syntax tree is

Text

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

#	Quadruple (op, arg1, arg2, result)	Triple (op, arg1, arg2)
0	(minus, c, , t1)	(minus, c, )
1	(*, b, t1, t2)	(*, b, (0))
2	(minus, c, , t3)	(minus, c, )
3	(*, b, t3, t4)	(*, b, (2))
4	(+, t2, t4, t5)	(+, (1), (3))
5	(=, t5, , a)	(=, a, (4))

In triples the assignment a = t5 becomes (=, a, (4)): the name being assigned sits in arg1 and the value is the result of triple 4. An indexed assignment x[i] = y needs two triples, one computing the address from $x$ and $i$ and one storing $y$ . The indexed copy x = y[i] also needs two: (0) (=[], y, i) fetches the element and (1) (=, x, (0)) stores it, because a triple has room for only two operands.

Indirect triples add an instruction list, for example positions 35 to 40 holding pointers to triples (0) to (5). An optimiser can reorder the program by permuting the list without touching the triples.

Quadruples, triples and indirect triples for a = b \* - c + b \* - c — Figure 1. The six instructions for a = b * - c + b * - c as quadruples with an explicit result field t1 to t5, as triples that refer to earlier results by position (0) to (4), and as indirect triples, where a separate instruction list points into the triple table.

Trade-offs.

Quadruples need a result field and many temporaries in the symbol table, but an instruction can be moved without changing others, since results are named.
Triples save the result field, but moving a triple changes every position reference to it.
Indirect triples keep the space saving and allow reordering; the cost is the extra list.

Static single-assignment form

In SSA every definition creates a new version of the variable. For a straight-line block, rename each target and make every use refer to the latest version:

Original	SSA
`p = a + b`	`p1 = a + b`
`q = p - c`	`q1 = p1 - c`
`p = q * d`	`p2 = q1 * d`
`p = e - p`	`p3 = e - p2`
`q = p + q`	`q2 = p3 + q1`

The SSA block uses 10 distinct names (inputs $a, b, c, d, e$ and versions $p_1, p_2, p_3, q_1, q_2$ ) and computes the same final value of $q$ .

Where control paths join, a $\phi$ -function selects the version from the path actually taken:

Text

if (flag) x1 = -1; else x2 = 1;
x3 = phi(x1, x2);
y  = x3 * a;

$\phi$ is not a machine instruction; it is removed before code generation by copies on the incoming edges. SSA makes each use have exactly one reaching definition, which simplifies constant propagation and similar analyses.

Choosing an IR

Syntax trees and DAGs: high level, for semantic analysis and for detecting common subexpressions within an expression.
TAC: low level and linear, for flow graphs, data-flow analysis and code generation; it maps closely onto load/store and register-to-register machine instructions.
SSA: a property of TAC that simplifies many optimisations.
Postfix: compact and evaluable by a stack machine; used for stack-based virtual machines.

Important properties and observations

DAG nodes = distinct leaves + distinct operator signatures. Count the leaves once each, then each distinct $\langle op, \text{children}\rangle$ .
Commutativity is not assumed by the basic value-number method: $b + c$ and $c + b$ are different nodes unless the question says operands may be reordered.
A syntax tree with $n$ binary operators has $n + 1$ leaves; unary operators add a node without a leaf.
TAC from a tree uses one temporary per operator; from a DAG, one per distinct operator node.
Triples cannot be reordered freely; quadruples and indirect triples can.
Temporaries versus temporary names. Code from a DAG names one temporary per operator node, but the number of registers or temporaries needed at once is the maximum number of live temporaries, which an evaluation order can reduce.
SSA needs as many names as there are definitions (plus the inputs), not as many as there are original variables.

Common misconceptions.

"A DAG removes repeated variables only." It shares repeated subexpressions at every level, such as $b - c$ above.
"Three-address code means exactly three addresses." At most three; copies and jumps use fewer.
"Triples have no temporaries, so they need fewer instructions." They need the same number of instructions; only the result field is gone.

GATE examination perspective

Count DAG nodes and edges. Apply this to a given expression or block; watch for repeated subexpressions and repeated leaves.
Write or count TAC. One instruction per operator node, plus copies; know minus as a unary operator.
Quadruples versus triples. Convert one to the other; know which supports reordering.
SSA conversion. Count the total number of variables (versions plus inputs) or write the renamed block.
Identical operands share one node. In a = b * - c + b * - c (counting the assignment node and destination a) both operands of + are the same DAG node: 7 DAG nodes against 11 tree nodes.
Minimum temporaries. Apply this to a given DAG: choose the evaluation order so that a shared value waits alongside as few others as possible; the running example needs 2.
Postfix and prefix. Use a tree, consistent with the expression's precedence.

Summary

Sources

A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman, Compilers, Principles, Techniques, and Tools, 2nd ed., Pearson Addison-Wesley, 2007: Section 5.3.1 (construction of syntax trees), Section 6.1 (directed acyclic graphs for expressions; the value-number method for constructing DAGs), Section 6.2 (addresses and instructions, quadruples, triples, static single-assignment form).

Introduction

Prerequisites

Core concepts

How it works

Syntax tree versus DAG

Three-address instruction forms

Quadruples, triples and indirect triples

Static single-assignment form

Choosing an IR

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps