7.1 Intermediate Representations: Three-Address Code, Quadruples & Triples

Back to DBMS Notes

📚Module 01Intermediate Representations: TAC, Quadruples & Triples⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Universal Esperanto of Compilers

Imagine a global diplomatic summit where delegates speak $M = 10$ different languages, and listeners require translations into $N = 10$ regional dialects:

• Without an Intermediate Language: You would need $M \times N = 100$ direct bilingual translators. If an 11th language is introduced, you must construct 10 brand-new translation channels from scratch!
• With a Universal Intermediate Language (IR): Every speaker translates their speech into one shared bridge language (Esperanto / Universal IR). Then, a backend interpreter translates from Esperanto into each listener's dialect.
• Complexity Drops from $M \times N$ to $M + N$: Adding a new source programming language (e.g. Rust) requires only 1 new frontend. Adding a new CPU architecture (e.g. RISC-V) requires only 1 new backend. All machine-independent code optimizations take place directly on the shared intermediate representation!

💻 Bridging to Computer Science: Linearizing Syntax Trees into 3-Address Instructions

In compiler architecture, Intermediate Code Generation (ICG) acts as the universal pivot between analysis (front-end) and synthesis (back-end):

• It flattens tree-structured Abstract Syntax Trees into a linearized sequence of atomic instructions called Three-Address Code (TAC).
• Each three-address instruction contains at most one operator on the right-hand side, decomposing complex nested expressions using compiler-generated temporary variables.
• This uniform representation is implemented in memory using Quadruples, Triples, or Indirect Triples.

📑Table of Contents

• 🏗️ Architectural Foundations: The Retargeting Pipeline
• 📐 Formal Foundations: Three-Address Code (TAC)
  • 📋 The 8 Standard Forms of Three-Address Statements
• 🏗️ Data Structures: Quadruples, Triples & Indirect Triples
  • 1️⃣ Quadruples (Quads)
  • 2️⃣ Triples
  • 3️⃣ Indirect Triples
• 🏭 Real-World Production Context: How Industry Builds This
• 📐 Numerical Applications & Worked Examples
  • Example 1: Full Decomposition into Quads, Triples & Indirect Triples
  • Example 2: Array Address Dereference TAC Translation
• 🎯 Exam & Interview Pitfall Check

---

🏗️ Architectural Foundations: The Retargeting Pipeline

The Compiler Retargeting Architecture via Universal IR

Decoupling M source frontends from N target backends

Frontends (M)

Language-Specific Frontends

🌐

C, C++, Rust, Swift, Go, Python frontends parse source code into AST.

LexingParsingSemantic Type Check

↓emits shared

Bridge (Universal)

Intermediate Representation (IR / TAC)

⚖️

Canonical machine-independent instruction stream.

Three-Address CodeQuadruplesSSA FormControl Flow Graphs

↓optimized by

Optimizer

Target-Independent Optimizer

⚡

Dead code elimination, loop unrolling, constant propagation.

Common Subexpression EliminationInliningDataflow Analysis

↓lowered to

Backends (N)

Target Hardware Backends

🖥️

x86-64, ARM64, RISC-V, WebAssembly machine code generators.

Instruction SelectionRegister AllocationPeephole Tuning

---

📐 Formal Foundations: Three-Address Code (TAC)

Three-Address Code (TAC) is an abstract linearized instruction set where every instruction has at most one operator on the right-hand side. Consequently, no operation can reference more than three memory locations or registers (two operands and one result).

A complex nested expression like:

$$x = a + b \times c - d$$

is decomposed into a linear sequence of atomic instructions using compiler-generated temporary variables ($t_1, t_2, \dots$):

$$\begin{aligned} t_1 &= b \times c \\ t_2 &= a + t_1 \\ t_3 &= t_2 - d \\ x &= t_3 \end{aligned}$$

📋 The 8 Standard Forms of Three-Address Statements

1. Binary Assignments:

   $$x = y \text{ op } z \quad (\text{where op is } +, -, \times, /, \land, \lor)$$

2. Unary Assignments:

   $$x = \text{op } y \quad (\text{where op is unary minus } -, \text{bitwise NOT } \sim, \text{logical NOT } !)$$

3. Copy Statements:

   $$x = y$$

4. Unconditional Jumps:

   $$\textbf{goto } L$$

5. Conditional Jumps:

   $$\textbf{if } x \text{ relop } y \textbf{ goto } L \quad (\text{where relop is } <, \le, ==, \ne, >, \ge)$$

6. Procedure Calls & Parameters:

   $$\begin{aligned} &\textbf{param } x_1 \\ &\textbf{param } x_2 \\ &\textbf{call } p, n \quad (n \text{ is argument count}) \\ &y = \textbf{call } p, n \\ &\textbf{return } y \end{aligned}$$

7. Indexed Copy Statements (Array Operations):

   $$\begin{aligned} x &= y[i] \quad (\text{R-value array read: load from address } y + i) \\ x[i] &= y \quad (\text{L-value array write: store to address } x + i) \end{aligned}$$

8. Address & Pointer Operations:

   $$\begin{aligned} x &= \&y \quad (\text{Address-of operator}) \\ x &= *y \quad (\text{Pointer dereference read}) \\ *x &= y \quad (\text{Pointer dereference write}) \end{aligned}$$

---

🏗️ Data Structures: Quadruples, Triples & Indirect Triples

In an actual compiler, TAC instructions are represented in memory using specialized record structures:

Quadruples vs Triples: Structural Tradeoffs

Comparing explicit temporary naming against implicit positional referencing

Quadruples

Quadruples Representation

4️⃣

Dominant Architecture / DomainProduction Compilers (GCC Gimple, LLVM IR)

• •Record with 4 fields: (op, arg1, arg2, result).
• •Explicit temporary variable names (t1, t2) placed in result field.
• •Optimization friendly: instructions can be moved, sorted, and reordered freely without rewriting operands.
• •Requires extra symbol table overhead to store temporary names.

"Explicit names grant complete freedom of instruction rescheduling."

Triples

Triples Representation

3️⃣

Dominant Architecture / DomainMemory-Constrained Compilers, AST DAGs

• •Record with 3 fields: (op, arg1, arg2).
• •Zero explicit temporaries: results are referred to by instruction index (i).
• •Saves memory and eliminates symbol table clutter.
• •Optimization nightmare: moving instruction (i) requires updating every downstream reference to (i).

"Compact storage at the cost of high instruction reordering friction."

1️⃣ Quadruples (Quads)

A quadruple is a record with four fields: (op, arg1, arg2, result).

• For unary operators (e.g. $x = -y$), arg2 is blank or nil.
• For unconditional jumps goto L, op = goto and result = L.
• For relational branches if x < y goto L, arg1 = x, arg2 = y, result = L.

2️⃣ Triples

To eliminate the space overhead of creating explicit temporary variable entries in the symbol table, Triples use only three fields: (op, arg1, arg2).

• Any reference to the value computed by line (i) is made using the integer index (i) in arg1 or arg2.
• Ternary array stores like $x[i] = y$ require two triple steps:
  1. (0) [ ] x i (computes address)
  2. (1) = (0) y (stores value into address)

3️⃣ Indirect Triples

Indirect triples decouple the physical list of triple records from their execution order.

• The compiler maintains an array of pointers statement[] that point to triple records.
• When an optimization pass (e.g. loop-invariant code motion) needs to move an instruction, it only swaps the pointers in statement[] without changing the internal triple indices!

Architecture Flow

Indirect Triples Execution Architecture

Permuting instruction order by reordering the pointer array

📑Step Array

Order Array: statement[]

statement[0] -> (35), statement[1] -> (12), statement[2] -> (13).

→

Pointers

📦Triple Pool

Physical Triples Table

Fixed storage pool where triple locations never physically move.

→

Evaluates

⚡Execution

Hardware Code Emitter

Traverses statement[] in order, emitting native machine instructions.

---

🏭 Real-World Production Context: How Industry Builds This

In modern industrial production compilers:

LLVM IR is a universal, strongly-typed, three-address language in Static Single Assignment (SSA) form with an infinite virtual register file (%1, %2, %var):

%3 = add nsw i32 %1, %2
%cmp = icmp slt i32 %3, 100
br i1 %cmp, label %if.then, label %if.else

GCC translates high-level Abstract Syntax Trees into Gimple, an internal three-address representation where:

• Complex nested expressions are unnested into at most three operands per statement.
• Control flow is represented as explicit basic blocks with conditional and unconditional gotos.
• High-level control loops (for, while) are lowered into conditional branches.

---

📐 Numerical Applications & Worked Examples

Example 1: Full Decomposition into Quads, Triples & Indirect Triples

Consider the high-level assignment statement:

$$a = b \times -c + b \times -c$$

Generate:

1. Three-Address Code with minimum temporaries.
2. Quadruples table.
3. Triples table.
4. Indirect Triples table.

Step-by-Step Analytical Solution:

Step 1: Three-Address Code (TAC) Generation Applying common subexpression elimination to avoid recomputing $-c$ and $b \times -c$:

$$\begin{aligned} (0) \quad t_1 &= \text{uminus } c \\ (1) \quad t_2 &= b \times t_1 \\ (2) \quad t_3 &= t_2 + t_2 \\ (3) \quad a &= t_3 \end{aligned}$$

(Without optimization, a naive generator generates 5 temporary variables for the repeated subexpressions).

Step 2: Quadruples Table (Unoptimized Form)

Index	op	arg1	arg2	result
(0)	uminus	c	—	t1
(1)	*	b	t1	t2
(2)	uminus	c	—	t3
(3)	*	b	t3	t4
(4)	+	t2	t4	t5
(5)	=	t5	—	a

Step 3: Triples Table In the triples representation, no temporary names (t1, t2...) appear. Instead, the row index in parentheses represents the computed result:

Index	op	arg1	arg2
(0)	uminus	c	—
(1)	*	b	(0)
(2)	uminus	c	—
(3)	*	b	(2)
(4)	+	(1)	(3)
(5)	=	a	(4)

Step 4: Indirect Triples Table The indirect triples structure maintains a pointer list statement[] pointing to entries in the triples table:

Array statement[]:
statement[0] -> (0)
statement[1] -> (1)
statement[2] -> (2)
statement[3] -> (3)
statement[4] -> (4)
statement[5] -> (5)

If instruction (2) and (3) are hoisted out of a loop, the compiler simply permutes statement[] without modifying any operand references in the physical Triples table.

---

Example 2: Array Address Dereference TAC Translation

Given the array assignment statement in a C program:

$$x = A[i, j]$$

where $A$ is a 2D integer array of size $10 \times 20$ stored in row-major order with 4-byte integers. Base address is stored in identifier $A$, and indices are 0-based ($0 \le i < 10, 0 \le j < 20$).

Write the exact sequence of Three-Address Code instructions generated by the compiler.

Step-by-Step Analytical Derivation:

1. Address Formulation:

   • Row-major offset formula:

     $$\text{Offset}(i, j) = (i \times 20 + j) \times 4 = 80i + 4j$$

2. Three-Address Code Generation:

   $$\begin{aligned} (1) \quad t_1 &= i \times 20 && (\text{Multiply row index by row width } 20) \\ (2) \quad t_2 &= t_1 + j && (\text{Add column index } j) \\ (3) \quad t_3 &= t_2 \times 4 && (\text{Scale by element size } 4 \text{ bytes}) \\ (4) \quad t_4 &= A[t_3] && (\text{Indexed load: Base address } A + \text{byte offset } t_3) \\ (5) \quad x &= t_4 && (\text{Assign value to destination } x) \end{aligned}$$

Total: 5 three-address instructions and 4 temporary variables.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: "Why are Quadruples preferred over Triples in optimizing compilers?"
Key Focus Points:

• Optimization Freedom: Quadruples explicitly record temporary variable names in the result field.
• Code Reordering: When optimization passes (such as loop-invariant code motion or instruction scheduling) move an instruction, quadruple references remain valid without modification. In Triples, moving instruction (i) alters all downstream positional references, requiring a costly full-table update.

Question 2: "What is the maximum number of operators permitted on the right-hand side of a Three-Address Code statement?"
Key Focus Points:

• Exactly one operator (either one binary operator $x = y \text{ op } z$ or one unary operator $x = \text{op } y$).
• Statements like $t = a + b + c$ are strictly illegal in TAC and must be split into two atomic operations.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Confusing array load with array store in Triples.
Answer: Subtle semantic difference. An array load $x = A[i]$ produces an evaluatable value and is referenced by downstream instructions. An array store $A[i] = x$ produces no value; it performs a memory mutation and cannot be referenced as an operand.

Trap 2: Assuming SSA form requires infinite hardware registers.
Answer: Conceptual confusion. SSA uses an unbounded number of virtual registers during intermediate optimization. Later, during the Target Code Generation phase, the Register Allocator maps these virtual registers down to the CPU's small fixed physical register file using Graph Coloring.

---

🗺️View Complete Compiler Design Roadmap & Syllabus

← Previous Topic6.3 Type Systems, Type Checking, Expressions & CoercionsNext Topic →7.2 Syntax Trees, Directed Acyclic Graphs & Value Numbering