Advanced Compilation: Code Generation, Optimization & Runtime Systems

TAKEAWAYS:

• Advanced code generation converts intermediate representations (IR) into efficient machine code using peephole optimization, instruction scheduling, and register allocation heuristics.
• Loop optimizations like unrolling, tiling, and strength reduction drastically improve performance in numerical computations (e.g., matrix multiplication).
• Garbage collection (mark-and-sweep, generational) manages memory automatically, critical for languages like Java and Python.
• Runtime systems use activation records to track function calls, local variables, and return addresses—visible in stack traces.
• Profile-guided optimization (PGO) leverages execution data (e.g., from Google’s V8 engine) to prioritize hot code paths.
• Advanced error recovery in compilers ensures graceful handling of syntax/semantic errors without halting translation (e.g., eSewa’s API validation).

---

1. Advanced Code Generation Techniques

Code generation transforms intermediate representations (IR) like three-address code (TAC) or control-flow graphs (CFG) into machine-specific assembly. Key methods:

A. Tree-to-Code Conversion

• How it works: Recursively traverse an Abstract Syntax Tree (AST) or DAG (Directed Acyclic Graph) to emit instructions.
• Example: Convert a = b + c * d (AST below) to x86 assembly.

Output Assembly:

mov eax, [c]    ; Load c into eax
imul eax, [d]   ; Multiply by d
add eax, [b]    ; Add b
mov [a], eax    ; Store result

B. Instruction Selection

• Goal: Map IR operations to the most efficient machine instructions (e.g., IMUL vs. ADD loops for multiplication).
• Example: Replace a = a * 2 with LEA eax, [eax+eax] (faster on x86).

  flowchart TD
    A["IR: a = a * 2"] --> B["Option 1: IMUL eax, 2"]
    A --> C["Option 2: LEA eax, [eax+eax]"]
    C --> D["Faster (no flags set)"]

C. Register Allocation

• Problem: Limited registers vs. many variables → spill code (store to memory) when needed.
• Heuristics:
  • Graph Coloring: Model variables as nodes; edges = live-range overlaps. Color nodes with registers (no adjacent nodes share colors).
  • Linear Scan: Assign registers to variables in order, reusing freed registers.
• Example: Allocate registers for int a, b, c; a = b + c; (x86 has 8 general-purpose registers).

  graph LR
    A["Live Range: b (R1)"] --> B["Live Range: c (R2)"]
    B --> C["Live Range: a (R3)"]
    C --> D["R1/R2 freed after use"]

REAL WORLD:

• Google’s V8 Engine (used in Chrome) uses SSA (Static Single Assignment) + register allocation to optimize JavaScript. For example, when you scroll a YouTube video, V8’s register allocator ensures critical variables (like currentFrame) stay in CPU registers for speed.
• LLVM’s opt tool applies peephole optimizations (e.g., replacing x + 0 with x) during compilation of apps like WhatsApp’s backend services.

---

2. Loop Optimizations

Loops are performance bottlenecks. Advanced techniques:

A. Loop Unrolling

• Idea: Reduce loop overhead by executing multiple iterations per loop.
• Example: Unroll for (i=0; i<4; i++) a[i] = b[i] * 2; →

  a[0] = b[0] * 2;
  a[1] = b[1] * 2;
  a[2] = b[2] * 2;
  a[3] = b[3] * 2;
  

• Tradeoff: Increases code size but reduces branch mispredictions.

  flowchart TD
    A["Original Loop"] --> B["4 Branches"]
    C["Unrolled Loop"] --> D["0 Branches"]

B. Loop Tiling (Blocking)

• Idea: Divide large arrays into smaller tiles to improve cache locality.
• Example: Matrix multiplication C[i][j] = sum(A[i][k] * B[k][j]):

• Real Use: Used in Ncell’s network traffic routing algorithms to optimize packet forwarding tables.

C. Strength Reduction

• Idea: Replace expensive operations with cheaper ones.
• Example: Replace a = a * 2 with a += a (same result, fewer cycles).

  flowchart TD
    A["Original: IMUL eax, 2"] --> B["3 cycles"]
    C["Optimized: ADD eax, eax"] --> D["1 cycle"]

WORKED EXAMPLE: Optimize this loop for a Daraz order-processing system (where orders is a queue of customer requests):

for (i = 0; i < N; i++) {
    total += orders[i].price * (1 - orders[i].discount);
}

Optimized Version (Loop Unrolling + Strength Reduction):

// Unroll by 4
for (i = 0; i < N; i += 4) {
    total += orders[i].price * (1 - orders[i].discount);
    total += orders[i+1].price * (1 - orders[i+1].discount);
    total += orders[i+2].price * (1 - orders[i+2].discount);
    total += orders[i+3].price * (1 - orders[i+3].discount);
}
// Replace multiplication by 1-x with subtraction
// e.g., a*(1-b) → a - a*b

---

3. Garbage Collection (GC)

Automatically reclaims memory for languages like Java/Python. Key algorithms:

A. Mark-and-Sweep

1. Mark: Start from root objects (e.g., global variables, stack frames) and recursively mark reachable objects.
2. Sweep: Free unmarked objects.

B. Generational GC

• Idea: Most objects die young → divide heap into young generation (short-lived) and old generation.
• Example: Java’s GC promotes surviving objects to the old generation after a few collections.

  graph LR
    A["Young Gen"] -->|"Survive"| B["Old Gen"]
    C["Short-lived objects"] -->|"Die"| D["Collected"]

REAL WORLD:

• WhatsApp’s backend uses concurrent mark-sweep GC to handle millions of messages without pauses.
• Python’s CPython uses reference counting + generational GC to manage memory for scripts like those in eSewa’s payment processing.

---

4. Runtime Environments and Activation Records

When a function calls another, the runtime stack manages:

• Activation records (stack frames): Store local variables, return addresses, and saved registers.
• Example: Call stack for main() → foo() → bar():

Activation Record Structure:

REAL WORLD:

• NEPSE’s trading system uses activation records to track nested function calls in real-time price updates. A crash in updatePortfolio() would show a stack trace like:

  updatePortfolio() → validateOrder() → checkMargin() → [SEGMENTATION FAULT]
  

---

5. Profile-Guided Optimization (PGO)

• Idea: Use execution profiles (e.g., from testing) to optimize hot code paths.
• Steps:
  1. Instrument code to collect execution counts (e.g., if (x > 0) { ... } → count how often x > 0 is true).
  2. Recompile with profile data to favor likely branches.
• Example: In Khalti’s payment API, the path processPayment() → validateCard() is hot → PGO inlines validateCard to avoid function call overhead.

Comparison Table:

---

6. Advanced Error Handling

Compilers must recover from errors without crashing. Strategies:

• Panic Mode: Skip to next sync point (e.g., ;, }) after a syntax error.
• Phrase-Level Recovery: Use a finite-state automaton to find the next valid token.

• Example: Recover from if (x = 5 (missing )) by inserting a dummy ) and continuing.

REAL WORLD:

• eSewa’s API validator uses error recovery to handle malformed JSON requests (e.g., missing }) by logging the error but processing valid fields.

---

Exam Tip

1. Diagrams are worth 20% of marks: Draw block diagrams of compiler phases, activation records, and CFGs with labeled edges.
2. Code traces: For questions like "Show the stack after calling foo()", list each activation record’s contents in order. Example:

   Function	Return Address	Local x
   main	0x400123	-
   foo	0x4000AA	10

3. Real-world ties: Relate optimizations to Ncell’s billing loops, Daraz’s order queues, or Khalti’s transaction validation.
4. GC algorithms: Compare mark-and-sweep vs. generational in terms of pause time and memory overhead.
5. PGO: Explain how profile data changes code generation (e.g., inlining hot functions).

---

Past Exam Question Analysis:

• Q: "Draw the compiler block diagram with symbol table/error handler interactions." Answer: Show 9 phases (lexer → parser → semantic analyzer → ...) with symbol table feeding into semantic analysis and error handler receiving inputs from lexer, parser, and code generator.