Code Generation: Target Code, Register Allocation, Instruction Selection

TAKEAWAYS:

• Code generation converts intermediate code into machine-specific instructions using target architecture (e.g., x86, ARM) and instruction set architecture (ISA).
• Register allocation assigns variables to CPU registers to minimize memory access, using techniques like graph coloring or linear scan.
• Instruction selection maps intermediate code to optimal machine instructions, often using dynamic programming or pattern matching.
• Peephole optimization refines generated code by fixing small inefficiencies (e.g., redundant loads, dead code).
• Real-world compilers (e.g., GCC, LLVM) use these techniques to generate high-performance code for apps like WhatsApp (ARM/ARM64) or eSewa (x86/x86_64).

---

1. Introduction to Code Generation

Code generation is the final phase of compilation where intermediate code (e.g., three-address code) is translated into machine code for a specific target architecture. The goal is to produce efficient, correct, and portable code while adhering to hardware constraints.

Key Components:

• Target Architecture: Defines the CPU (e.g., x86, ARM), instruction set, and memory model.
• Instruction Set Architecture (ISA): Rules for valid instructions, registers, and addressing modes.
• Register Allocation: Assigns variables to CPU registers to minimize memory access.
• Instruction Selection: Chooses the best machine instructions for intermediate code operations.
• Peephole Optimization: Fixes small inefficiencies in the generated code.

Why is Code Generation Important?

• Performance: Directly impacts how fast a program runs (e.g., a poorly optimized compiler can make an app like Pathao slower).
• Portability: Generates code for different CPUs (e.g., Ncell’s backend runs on ARM, while NTC’s systems may use x86).
• Resource Efficiency: Optimizes memory and CPU usage (critical for Khalti’s payment processing).

---

2. Target Architectures and Instruction Sets

Compilers must generate code for specific ISAs, which define:

• Registers: Fast storage locations (e.g., eax, rbx in x86; r0-r15 in ARM).
• Instructions: Operations like ADD, LOAD, BRANCH.
• Addressing Modes: How operands are accessed (e.g., immediate, register, memory).

Example ISAs:

IMAGE: "x86 vs ARM register diagram" | Comparison of x86-64 and ARM64 registers

(Shows register names, sizes, and roles like program counter, stack pointer.)

---

3. Register Allocation

Registers are fast but limited, so the compiler must decide which variables to store in them. Poor allocation leads to spilling (using slow memory), hurting performance.

Techniques:

1. Graph Coloring:

   • Models variables as interference graphs (nodes = variables, edges = conflicts if two variables are live at the same time).
   • Colors nodes with k colors (where k = number of registers). If a node can’t be colored, spilling occurs.
   • Example: Assigning int a, b, c to eax, ebx, ecx if they don’t overlap in live ranges.

2. Linear Scan:

   • Scans code left-to-right, assigning registers to variables when they become live.
   • Uses a register pool and spill slots (memory locations) when registers run out.

Example: Graph Coloring for Register Allocation

Consider this intermediate code:

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

Live ranges:

• a, b, t1, c, t2, e, d must not overlap in registers.

Interference Graph:

Coloring:

• Assign a → eax, b → ebx, t1 → ecx (no conflicts).
• c and e can reuse eax/ebx if their live ranges don’t overlap.

IMAGE: "Register allocation graph coloring example" | Step-by-step coloring of the interference graph above, showing register assignments after each step.

(Shows initial graph → coloring → final register assignments.)

---

4. Instruction Selection

Maps intermediate code operations to optimal machine instructions. Approaches:

1. Direct Translation: Simple 1:1 mapping (e.g., + → ADD).
2. Pattern Matching: Uses production rules (e.g., t1 = a + b * c → MUL ebx, ecx; ADD eax, ebx).
3. Dynamic Programming: Finds the cheapest sequence of instructions (e.g., using a DAG of intermediate code).

Example: Instruction Selection for t1 = a + b * c

Intermediate Code (DAG):

Possible Machine Instructions (x86):

1. MUL ebx, ecx (b * c)
2. ADD eax, ebx (a + result)

Selected Code:

MOV eax, [a]   ; Load a into eax
MOV ebx, [b]   ; Load b into ebx
MOV ecx, [c]   ; Load c into ecx
MUL ebx, ecx   ; ebx = b * c
ADD eax, ebx   ; eax = a + (b * c)
MOV [t1], eax  ; Store result

IMAGE: "Instruction selection DAG to x86" | DAG of a + b * c with labeled edges for MUL/ADD operations.

(Shows how the DAG collapses into two instructions.)

---

5. Peephole Optimization

Fixes small inefficiencies in generated code by analyzing short sequences (e.g., 3-5 instructions). Examples:

• Redundant Loads: MOV eax, [x]; MOV ebx, eax → MOV ebx, [x].
• Dead Code: ADD eax, 0 → Remove.
• Strength Reduction: Replace MUL eax, 2 with SHL eax, 1.

Example: Peephole Optimization Trace

Before:

MOV eax, [x]   ; Load x
ADD eax, 0     ; Redundant
MOV ebx, eax   ; Copy

After:

MOV ebx, [x]   ; Optimized

IMAGE: "Peephole optimization before/after" | Side-by-side assembly showing redundant ADD eax, 0 removed.

(Shows original 3 instructions → optimized 1 instruction.)

---

6. Real-World Applications

In the Real World

1. WhatsApp (ARM64 Code Generation):

   • Uses LLVM to generate optimized ARM64 code for iPhones/Android.
   • Register allocation minimizes memory access in real-time message processing.
   • Instruction selection picks efficient ADD/SUB for quick UI updates.

2. eSewa (x86/x86_64 Backend):

   • Compiles payment logic into x86-64 for servers.
   • Peephole optimization reduces redundant checks in transaction validation.

3. Pathao (Mobile App, ARM):

   • Graph coloring assigns registers to GPS coordinates and rider data.
   • Poor allocation could slow down route calculations during peak hours.

4. NEPSE (Stock Market Systems):

   • Uses dynamic programming for instruction selection in high-frequency trading bots.
   • Spilling is avoided to prevent delays in order matching.

---

7. Worked Example: Compiling int y = x * 2 + 3;

Step 1: Intermediate Code (Three-Address)

t1 = x * 2
t2 = t1 + 3
y = t2

Step 2: Register Allocation (Graph Coloring)

• Live ranges:
  • x: Live from start to t1.
  • t1: Live from * to +.
  • t2: Live from + to end.
  • y: Live at end.
• Assign:
  • x → eax
  • t1 → ebx
  • t2 → ecx
  • y → [y] (spilled to memory)

Step 3: Instruction Selection (x86)

MOV eax, [x]   ; Load x
SHL eax, 1     ; eax = x * 2 (faster than MUL)
ADD eax, 3     ; eax = t1 + 3
MOV [y], eax   ; Store y

Step 4: Peephole Optimization

• No redundant operations → already optimal.

IMAGE: "Register allocation for y = x*2 + 3" | Live ranges and register assignments for x, t1, t2, y.

(Shows eax reused for x and t1 since their ranges don’t overlap.)

---

8. Comparison: Code Generation Techniques

---

9. Exam Tip

1. Understand the Flow:

   • Code generation follows: register allocation → instruction selection → peephole optimization.
   • Always show intermediate steps (e.g., live ranges, DAGs) in traces.

2. ISA-Specific Details:

   • Know x86 vs ARM differences (e.g., ARM is load-store, x86 has memory operands).
   • Example: MOV [mem], reg is valid in x86 but not ARM.

3. Common Pitfalls:

   • Spilling: If registers run out, explain how you’d spill to memory.
   • Dead Code: Always check for eliminable instructions in peephole optimization.
   • Aliasing: Assume variables may alias (share memory) unless proven otherwise.

4. Diagrams Are Key:

   • Draw live range graphs, interference graphs, and DAGs for instruction selection.
   • Label every step in register allocation (e.g., "After coloring, eax holds a").

5. Real-World Questions:

   • Expect questions like:
     • "How would you optimize register allocation for a mobile app like Pathao?"
     • "Why does WhatsApp use ARM64 instead of x86?"
   • Answer with trade-offs (e.g., ARM64’s efficiency vs x86’s legacy support).

---

10. Summary Checklist

Before the exam, ensure you can: ✅ Explain the role of target architecture in code generation. ✅ Draw an interference graph and perform graph coloring. ✅ Convert a DAG to machine instructions using dynamic programming. ✅ Identify peephole optimization opportunities in assembly. ✅ Relate compiler techniques to real-world apps (e.g., eSewa, Pathao).