Intermediate Code Generation: Representations, Flow Graphs & Optimizations

TAKEAWAYS:

• Intermediate code is a portable, machine-independent representation (e.g., three-address code) that bridges source and target code.
• Basic blocks are linear sequences of instructions with a single entry and exit point, forming the foundation of flow graphs.
• Three-address code (quadruples, triples) simplifies parsing and optimization by limiting operations to three operands.
• Optimizations (constant folding, dead code elimination, copy propagation) reduce redundant computations and improve runtime efficiency.
• Flow graphs visualize control flow, helping identify loops, branches, and optimization opportunities.
• Activation records manage function calls, storing local variables, parameters, and return addresses in a stack-like structure.

1. Why Intermediate Code?

Compilers don’t generate machine code directly from source code. Instead, they produce an intermediate representation (IR) that:

• Is portable (can be translated to multiple target machines).
• Simplifies optimizations (e.g., loop unrolling, dead code removal).
• Makes target code generation easier (e.g., for x86, ARM, or RISC-V).

Real-world analogy: Think of intermediate code like eSewa’s payment processing system. When you pay an electricity bill:

1. You enter details (source: your phone).
2. eSewa processes it in a neutral format (intermediate: their backend system).
3. The payment is sent to NTC (target: the utility company). Without this middle step, every payment would need a direct link to every utility—impossible!

2. Intermediate Code Representations

Three common formats:

A. Three-Address Code (TAC)

Each instruction has at most three operands (e.g., t1 = a + b). Advantages:

• Easy to parse and optimize.
• Directly maps to assembly/machine code.

Example: For x = (a + b) * (c - d), the TAC is:

t1 = a + b
t2 = c - d
t3 = t1 * t2
x = t3

B. Quadruples

A 4-tuple: (op, arg1, arg2, result). Example: For a = b * (c + d), the quadruples are:

(+, c, d, t1)
(*, b, t1, a)

C. Triples

A 3-tuple: (op, arg1, arg2) or (op, arg1, result). Example: For x = a + b * c, the triples are:

(*, b, c, t1)
(+, a, t1, x)

Comparison Table:

3. Basic Blocks and Flow Graphs

A. Basic Blocks

A sequence of instructions with:

• One entry point (no jumps into the middle).
• One exit point (no jumps out except at the end).

How to identify:

1. Start at the first instruction.
2. Keep adding instructions until you hit a jump, branch, or function call.
3. The next instruction after the jump starts a new block.

Example: For the code:

1. read x
2. i = 1
3. sum = 0
4. prod = 1
5. if i > x goto 13
6. square = i * i
7. sum = sum + square
8. prod = prod * i
9. i = i + 1
10. goto 5
11. print sum
12. print prod

Basic blocks:

1. Lines 1–4 (initialization).
2. Lines 5–10 (loop body).
3. Lines 11–12 (final output).

B. Control Flow Graph (CFG)

A directed graph where:

• Nodes = basic blocks.
• Edges = control flow (e.g., jumps, branches).

Example CFG for the above code:

graph TD
    A["Block 1: Lines 1-4"] --> B["Block 2: Lines 5-10"]
    B -->|"i > x?"| C["Block 3: Lines 11-12"]
    B -->|"else"| B

Real-world tie-in: This is like Kathmandu’s traffic light system:

• Each block is a signalized intersection (basic block).
• Edges are green lights (control flow).
• Loops are roundabouts (repeated paths).

4. Generating Three-Address Code

Step-by-step for n = (a + b) * (c - d):

1. Parse the expression into a syntax tree.
2. Convert to postfix notation (Reverse Polish Notation): a b + c d - * n =
3. Generate TAC:

   t1 = a + b
   t2 = c - d
   t3 = t1 * t2
   n = t3
   

Figure: Syntax Tree → TAC

      *
     / \
    +   -
   / \ / \
  a b c d

Postfix: a b + c d - * TAC:

t1 = a + b
t2 = c - d
t3 = t1 * t2
n = t3

5. Code Optimization Techniques

Optimizations reduce redundant computations and improve performance.

A. Constant Folding

Replace computations with constants at compile time. Example: Before: x = 3 + 5; y = x * 2; After: x = 8; y = 16;

B. Dead Code Elimination

Remove unreachable or unused code. Example:

x = 3;
y = x;    // Dead code if 'y' is never used
z = x + 5;

After optimization:

x = 3;
z = x + 5;

C. Copy Propagation

Replace variables with their copied values. Example: Before: x = 3; y = x; z = x + 5; After: x = 3; y = 3; z = 8;

D. Strength Reduction

Replace expensive operations with cheaper ones. Example: Replace x = y * 2 with x = y + y (if * is slower than +).

Worked Example: Optimize x = 3; y = x; z = x + 5;:

1. Copy propagation: Replace y = x with y = 3.
2. Constant folding: Replace z = x + 5 with z = 8. Final optimized code:

x = 3;
y = 3;
z = 8;

6. Activation Records (Runtime Stack)

When a function is called, an activation record (stack frame) is created to store:

• Return address (where to go after the function ends).
• Actual parameters (arguments passed to the function).
• Local variables (temporary variables inside the function).
• Saved machine status (registers, flags).

Example: For factorial(n):

Real-world tie-in: This is like Pathao’s order processing:

• Each order is a stack frame.
• n = order ID.
• return_addr = where to send the delivery confirmation.
• locals = delivery status, driver assignment.

7. Factors Affecting Target Code Generation

1. Target Machine Architecture:
   • RISC vs. CISC affects instruction selection.
2. Intermediate Code Quality:
   • Better IR (e.g., SSA form) enables more optimizations.
3. Compiler Time vs. Runtime Tradeoff:
   • Aggressive optimizations take longer to compile but run faster.
4. Portability Needs:
   • If the compiler targets multiple platforms, IR must be generic.

In the Real World

1. eSewa’s Payment Processing:

   • Uses intermediate code-like systems to validate transactions before sending them to banks/NTC.
   • Optimization: Dead code elimination removes failed transactions early.

2. Khalti’s Loan Approval:

   • Control flow graphs model decision trees (e.g., "If credit score > 600, approve loan").
   • Basic blocks represent steps like "Check income → Verify ID → Calculate EMI."

3. Daraz’s Order Queue:

   • Activation records track each order’s status (e.g., "Processing," "Shipped," "Delivered").
   • Strength reduction: Replaces expensive database queries with cached results.

Exam Tip

1. For TAC/Quadruples:

   • Always show intermediate steps (e.g., temporary variables t1, t2).
   • Label each operation clearly (e.g., (+, a, b, t1)).

2. For Basic Blocks/CFGs:

   • Draw the flow graph and label blocks numerically.
   • Highlight loops and branches explicitly.

3. For Optimizations:

   • Apply all possible optimizations (constant folding, dead code elimination, copy propagation).
   • Show before/after code snippets.

4. For Activation Records:

   • Draw the stack frame with all components (return address, parameters, locals).
   • Explain recursion using nested frames.

Practice Question: Convert x = (a + b) * (c - d) + e to quadruples and optimize it using constant folding if a = 2, b = 3, c = 5, d = 1, e = 10.

Answer:

Quadruples:
(+, a, b, t1)
(-, c, d, t2)
(*, t1, t2, t3)
(+, t3, e, x)
Optimized (with constants):
(+, 2, 3, t1)   → t1 = 5
(-, 5, 1, t2)   → t2 = 4
(*, 5, 4, t3)   → t3 = 20
(+, 20, 10, x)  → x = 30