Intermediate code generation

Intermediate representations

Definition. An intermediate representation (IR) is a compiler form between source syntax and target machine code. It supports analysis and optimization while reducing dependence on a particular source or target language. Common forms include syntax trees, directed acyclic graphs, three-address code, and control-flow graphs.

Example. x = a+b*c can be represented as a tree with + at the root and * as its right child.

Exam point. IR preserves source semantics while exposing operations and dependencies for later passes.

Solved examples

Example 1 — expression tree. Draw the operator structure of a+b*c in words and list evaluation order.

1. Multiplication has higher precedence, so b*c is a subtree.
2. Addition combines a with that subtree.
3. Evaluate multiplication before addition.
4. Tree: +(a, *(b,c)).

Example 2 — tree versus DAG. In a*b + a*b, what can a DAG share?

1. Parse the two multiplication subexpressions.
2. Both have identical operands and operation.
3. A DAG can use one multiply node with two outgoing uses.
4. The repeated subexpression is represented once if its operands are unchanged.

Three-address code

Definition. Three-address code (TAC) uses simple instructions with at most one operator and a small number of operands, often an assignment, unary/binary operation, branch, or procedure action. Temporaries name intermediate results.

Example. t1=b*c; t2=a+t1; x=t2 translates x=a+b*c.

Exam point. TAC has more instructions than a source expression but makes data dependencies explicit.

Solved examples

Example 1 — operator precedence. Generate TAC for x=a+b*c-d.

1. Compute the higher-precedence product: t1=b*c.
2. Add a: t2=a+t1.
3. Subtract d: t3=t2-d.
4. Assign: x=t3.
5. Four TAC statements are produced.

Example 2 — parentheses. Translate x=(a+b)*(c-d).

1. t1=a+b.
2. t2=c-d.
3. t3=t1*t2.
4. x=t3.
5. The parenthesized subexpressions are evaluated before multiplication.

Example 3 — unary operation. Translate y=-(a+b).

1. t1=a+b.
2. t2=uminus t1.
3. y=t2.
4. Unary negation is a separate TAC operation.

Quadruples, triples, and indirect triples

Definition. A quadruple stores (op,arg1,arg2,result); a triple stores (op,arg1,arg2) and identifies results by instruction position; indirect triples use a separate pointer list to allow instruction reordering without changing triple references.

Example. t1=a+b is quadruple (+,a,b,t1) and triple (+ ,a,b) at an instruction index.

Exam point. Triples save explicit temporary names but make code motion harder because references use positions.

Solved examples

Example 1 — represent TAC. For t1=a+b; t2=t1*c write quadruples.

Index	op	arg1	arg2	result
0	+	a	b	t1
1	*	t1	c	t2

1. First operation adds a and b.
2. Second multiplies the first result by c.
3. The result column names each temporary.

Example 2 — triples. Represent the same computation with triples.

Index	op	arg1	arg2
0	+	a	b
1	*	(0)	c

1. Triple 0's value is referenced by index 0.
2. Triple 1 uses (0) as its first operand.
3. Moving triple 0 would require updating positional references.

Boolean expressions and short-circuit code

Definition. Short-circuit evaluation computes the right operand only when its value can affect the whole Boolean result. Control-flow TAC uses conditional and unconditional jumps to encode this behavior without eagerly evaluating both sides.

Example. For A && B, if A is false, jump directly to the false result without evaluating B.

Exam point. Boolean operators may be translated into control flow rather than numeric temporary values.

Solved examples

Example 1 — short-circuit AND. Generate labels for if (a<b && c!=0) x=1 else x=0.

1. if a<b goto L1; otherwise goto Lelse.
2. At L1, if c!=0 goto Lthen; otherwise goto Lelse.
3. Lthen: x=1; goto Lend.
4. Lelse: x=0.
5. Lend continues after the statement.
6. The second condition is evaluated only if the first is true.

Label	TAC
entry	if a<b goto L1
next	goto Lelse
L1	if c!=0 goto Lthen
next	goto Lelse
Lthen	x=1; goto Lend
Lelse	x=0
Lend	—

Example 2 — short-circuit OR. For A || B, when should B be evaluated?

1. If A is true, the whole disjunction is true.
2. Jump to the true label without evaluating B.
3. Evaluate B only after A is false.
4. This preserves short-circuit semantics.

Backpatching

Definition. Backpatching handles forward branches whose target labels are not yet known. A list of unresolved jump instructions is maintained; makelist creates a list, merge combines lists, and backpatch fills target labels once they are known.

Example. An if condition's true-list can be patched to the then-block label when that block is emitted.