Intermediate Code Generation: Three-Address Code, Stack Machines, DAGs

TAKEAWAYS:

• Intermediate code is a machine-independent, low-level representation that bridges syntax analysis and code generation.
• Three-address code (TAC) uses simple instructions with at most one operator and three operands, making it easy to optimize.
• Stack machines (e.g., Java bytecode) use a stack for operands, reducing register allocation complexity.
• Directed Acyclic Graphs (DAGs) eliminate redundant computations by merging common subexpressions.
• The choice of intermediate representation affects optimization opportunities and code generation efficiency.
• Real-world compilers (e.g., GCC, LLVM) use intermediate code to separate front-end (language-specific) and back-end (machine-specific) phases.

What is Intermediate Code?

Intermediate code (IR) is a low-level, machine-independent representation of a program generated by a compiler after parsing and semantic analysis. It serves as a bridge between:

• High-level source code (e.g., C, Java, Python)
• Machine-specific target code (e.g., x86 assembly, ARM machine code)

IR is designed to:

1. Retain enough structure for optimizations (e.g., constant folding, dead code elimination).
2. Be easy to translate into target code for different architectures.
3. Support portability (write once, compile anywhere).

Why Not Generate Target Code Directly?

Generating target code directly from parse trees is hard because:

• Syntax trees lack low-level details (e.g., memory addresses, register usage).
• Different machines have different instruction sets (e.g., RISC vs. CISC).
• Optimizations (e.g., loop unrolling) are easier on a uniform IR.

IR solves these problems by providing a canonical form that all optimizations and back-ends can work with.

Types of Intermediate Representations

Three common forms are used in modern compilers:

1. Three-Address Code (TAC)

TAC is the most widely used IR in compilers like GCC and LLVM. It consists of quadruples or triples, where each instruction has:

• One operator (e.g., +, -, =).
• Three operands (e.g., t1 = a + b).

Syntax of TAC

A typical TAC instruction looks like:

t = op a b

Where:

• t is a temporary variable (e.g., t1, t2).
• op is an operator (+, -, *, /, =).
• a and b are operands (variables, constants, or temporaries).

Example: TAC for x = (a + b) * (c - d)

Original expression:

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

Step-by-step TAC generation (from parse tree):

1. Evaluate (a + b):

   t1 = a + b
   

2. Evaluate (c - d):

   t2 = c - d
   

3. Multiply results:

   x = t1 * t2
   

Visualizing TAC Generation

flowchart TD
    A["Parse Tree"] --> B["Post-order Traversal"]
    B --> C["Generate TAC"]
    C --> D["t1 = a + b"]
    C --> E["t2 = c - d"]
    C --> F["x = t1 * t2"]
    D --> G["TAC: t1 = a + b"]
    E --> H["TAC: t2 = c - d"]
    F --> I["TAC: x = t1 * t2"]

Advantages of TAC

• Simple: Easy to generate and optimize.
• Structured: Each instruction is straightforward.
• Portable: Can be translated to any target architecture.

Disadvantages of TAC

• Verbose: May generate many temporaries for complex expressions.
• Not always optimal: Some optimizations (e.g., strength reduction) require more advanced IRs.

2. Stack Machines

Stack machines use a stack to hold operands and intermediate results. Instructions typically:

1. Push operands onto the stack.
2. Pop operands for operations.
3. Push results back onto the stack.

Example: Stack Machine Code for x = a + b

Original expression:

x = a + b;

Stack machine instructions:

LOAD a
LOAD b
ADD
STORE x

Stack state after each step:

Visualizing Stack Machine Execution

flowchart LR
    A["LOAD a"] --> B["Stack: [a]"]
    B --> C["LOAD b"] --> D["Stack: [a, b]"]
    D --> E["ADD"] --> F["Stack: [a + b]"]
    F --> G["STORE x"] --> H["Stack: [] (x = a + b)"]

Real-World Example: Java Bytecode

Java compiles source code to bytecode, which runs on the Java Virtual Machine (JVM). The JVM is a stack machine:

int x = a + b;

Compiled to bytecode:

iconst_1  // Push 'a' (assuming a=1 for simplicity)
iconst_2  // Push 'b' (assuming b=2)
iadd      // ADD
istore_0  // STORE x

Stack state:

Advantages of Stack Machines

• No registers: Simplifies register allocation.
• Portable: JVM bytecode runs on any machine with a JVM.
• Efficient for some ops: Stack operations are fast for simple arithmetic.

Disadvantages of Stack Machines

• Harder to optimize: Harder to perform advanced optimizations like loop unrolling.
• Verbose for complex ops: Deep stacks can slow down execution.

3. Directed Acyclic Graphs (DAGs)

A DAG represents computations as a graph where:

• Nodes = operations or variables.
• Edges = dependencies between operations.

DAGs eliminate redundant computations by merging common subexpressions.

Example: DAG for x = a * b + a * b

Original expression:

x = a * b + a * b;

Naive TAC:

t1 = a * b
t2 = a * b
x = t1 + t2

DAG representation:

graph TD
    A["a"] --> B["*"]
    C["b"] --> B
    B --> D["+"]
    A --> E["*"]
    C --> E
    E --> D
    D --> F["x"]

Optimized TAG (Three-Address Code with DAG):

t1 = a * b
x = t1 + t1

Savings: One multiplication is eliminated.

How DAGs Work

1. Build the DAG from the parse tree.
2. Merge common subexpressions (e.g., a * b appears twice).
3. Generate code from the DAG (e.g., compute a * b once, reuse).

Real-World Example: Compiler Optimizations in LLVM

LLVM uses Static Single Assignment (SSA) form, which is a DAG-like representation where:

• Each variable is assigned exactly once.
• Optimizations like constant propagation and dead code elimination are easier.

Example:

int y = x + 5;
int z = y + 10;

SSA form (DAG-like):

%1 = add i32 %x, 5
%2 = add i32 %1, 10

Here, %1 and %2 are temporaries assigned once.

Advantages of DAGs

• Eliminates redundancy: Saves computation time.
• Better optimizations: Enables advanced techniques like common subexpression elimination (CSE).
• Clear dependencies: Makes control flow analysis easier.

Disadvantages of DAGs

• Complex to implement: Requires graph algorithms.
• Overhead: Building and traversing DAGs can be slow for simple programs.

Translation from Parse Trees to Intermediate Code

The process of generating IR from a parse tree involves:

1. Traversing the parse tree (usually post-order).
2. Generating IR instructions for each node.
3. Managing temporaries (e.g., t1, t2).

Example: TAC Generation for if (a > b) x = a; else x = b;

Original code:

if (a > b) x = a; else x = b;

Parse tree:

          IF
         /   \
       (a>b)   ELSE
        / \     / \
       a   b   x=a  x=b

TAC generation:

1. Generate condition:

   t1 = a > b
   

2. Generate then branch (x = a):

   t2 = a
   

3. Generate else branch (x = b):

   t3 = b
   

4. Merge branches:

   x = t1 ? t2 : t3
   

Final TAC:

t1 = a > b
t2 = a
t3 = b
x = t1 ? t2 : t3

Visualizing TAC for Conditional Statements

flowchart LR
    A["Parse Tree: IF"] --> B["Generate t1 = a > b"]
    B --> C["Then: t2 = a"]
    B --> D["Else: t3 = b"]
    C --> E["Merge: x = t1 ? t2 : t3"]

Real-World Applications of Intermediate Code

1. Java Virtual Machine (JVM) and Bytecode

• What it uses: Stack machine (bytecode).
• How it works: Java source code is compiled to bytecode, which runs on any JVM (e.g., Windows, Linux, macOS).
• Example: When you run a Java program, the JVM translates bytecode to machine code on the fly (JIT compilation).

2. LLVM Compiler Infrastructure

• What it uses: Three-address code (LLVM IR) and DAGs (for optimizations).
• How it works: LLVM IR is a low-level, typed intermediate representation that allows optimizations before generating target code (e.g., x86, ARM).
• Example: Clang (the C/C++ frontend for LLVM) compiles source code to LLVM IR, which is then optimized and translated to machine code.

3. Python Bytecode

• What it uses: Stack-based bytecode (similar to JVM).
• How it works: Python source code is compiled to .pyc files (bytecode), which are executed by the Python interpreter.
• Example: When you run python script.py, the interpreter first compiles it to bytecode if not already done.

4. Nepali Context: eSewa and Digital Payments

• What it uses: Intermediate representations in backend services (e.g., Java/Kotlin for Android apps, Python for APIs).
• How it works: Payment processing involves:
  1. Validation: Check if the user has enough balance (IR for conditionals).
  2. Transaction: Deduct amount and update database (IR for arithmetic and I/O).
  3. Confirmation: Send SMS/email (IR for control flow).
• Example: When you pay a bill via eSewa, the backend compiler generates IR to validate your request, process the payment, and update records—all before generating machine code for execution.

5. Ncell and Mobile App Compilation

• What it uses: Intermediate code in Android apps (Java/Kotlin → Dalvik bytecode).
• How it works: Android apps are compiled to Dalvik bytecode, which runs on the Android Runtime (ART). ART uses JIT compilation to translate bytecode to machine code at runtime.
• Example: When you download an app from the Play Store, it’s pre-compiled to bytecode, which runs efficiently on your phone.

6. NEPSE Stock Market Software

• What it uses: High-performance IR (e.g., C++ → LLVM IR).
• How it works: Trading systems use compiled languages (C++, Java) that generate IR for:
  • Real-time calculations (e.g., order matching).
  • Database updates (e.g., portfolio changes).
• Example: When you buy/sell shares on NEPSE’s online platform, the backend compiler optimizes IR to execute trades in milliseconds.

Worked Example: TAC for a Loop

Original code:

int sum = 0;
for (int i = 0; i < 10; i++) {
    sum += i;
}

Step-by-step TAC generation:

1. Initialize sum and i:

   sum = 0
   i = 0
   

2. Loop condition (i < 10):

   t1 = i < 10
   

3. Body of loop (sum += i):

   t2 = sum + i
   sum = t2
   

4. Increment i:

   t3 = i + 1
   i = t3
   

5. Jump back to condition if t1 is true.

Final TAC:

sum = 0
i = 0
L1:
t1 = i < 10
IF t1 GOTO L2
GOTO L3
L2:
t2 = sum + i
sum = t2
t3 = i + 1
i = t3
GOTO L1
L3:

Visualizing Loop TAC

flowchart LR
    A["sum = 0"] --> B["i = 0"]
    B --> C["L1: t1 = i < 10"]
    C --> D["IF t1 GOTO L2"]
    D --> E["GOTO L3"]
    C --> F["L2: t2 = sum + i"]
    F --> G["sum = t2"]
    G --> H["t3 = i + 1"]
    H --> I["i = t3"]
    I --> C
    E --> J["L3: End"]

Comparison of Intermediate Representations

Exam Tip

What to Expect in the Exam

1. Definitions:

   • Explain three-address code, stack machines, and DAGs with examples.
   • Define temporary variables and their role in IR.

2. Generation:

   • Given a parse tree or expression, generate TAC or stack machine code.
   • Example: Convert x = (a + b) * (c - d) to TAC.

3. Optimizations:

   • Identify redundant computations in TAC and rewrite using DAGs.
   • Example: Optimize x = a * b + a * b to x = 2 * (a * b).

4. Real-World Applications:

   • Relate IR to JVM bytecode, LLVM, or Python bytecode.
   • Example: Explain how Java’s + operator is compiled to JVM bytecode.

5. Code Traces:

   • Show stack states for stack machine instructions.
   • Example: Trace the execution of LOAD a; LOAD b; ADD; STORE x.

Common Mistakes to Avoid

• Forgetting temporaries: Always use t1, t2, etc., for intermediate results.
• Incorrect operator precedence: Evaluate expressions in the correct order (e.g., * before +).
• Missing control flow: For if-else, generate both branches and a merge.
• Overlooking optimizations: In DAGs, always merge common subexpressions.

Sample Exam Question and Answer

Question: Generate three-address code for the following expression:

z = (a + b) * (c - d) + e;

Answer:

1. Break down the expression:

   • (a + b) → t1 = a + b
   • (c - d) → t2 = c - d
   • Multiply results → t3 = t1 * t2
   • Add e → z = t3 + e

2. Final TAC:

   t1 = a + b
   t2 = c - d
   t3 = t1 * t2
   z = t3 + e
   

Final Checklist for Full Marks

• Define IR and its purpose.
• Show TAC generation from a parse tree.
• Explain stack machines with stack traces.
• Draw a DAG and explain optimizations.
• Compare the three IR types in a table.
• Relate to real-world compilers (JVM, LLVM).
• Solve a worked example (loop, conditional, arithmetic).