8.4 Target Code Generation, Register Allocation & Peephole Optimization

Back to DBMS Notes

📚Module 01Target Code Generation & Register Allocation⏱️5 min read

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

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Master Carpenter and the Finite Toolbelt

Imagine a master carpenter building custom furniture:

• In the design studio (Frontend & ICG), the architect sketches plans using an unlimited assortment of specialized virtual tools.
• On the actual construction job site (Backend Hardware Silicon), the carpenter has a toolbelt with only 4 leather pockets (Physical Registers).
• Register Allocation via Graph Coloring: If the hammer and the screwdriver are needed at the exact same second, they cannot share the same pocket; they interfere. The carpenter creates a conflict chart: if two tools conflict, they must be assigned different colored pockets.
• Spilling to Memory: If 6 critical tools are needed simultaneously, but the toolbelt holds only 4, the carpenter must place the least urgent tool in the chest across the room (Spill to RAM). Walking across the room to fetch it costs 100 times more effort!
• Peephole Optimization: A senior foreman standing beside the bench observing every motion through a narrow 3-step window. If the worker puts the hammer down and picks it right back up a split second later, the foreman corrects them: "Keep it in your hand; eliminate unnecessary motion!"

💻 Bridging to Computer Science: Lowering IR to Hardware Silicon

Target code generation is the final phase of compilation:

• Instruction Selection: Mapping abstract three-address quadruples into target-machine assembly instructions.
• Register Allocation vs. Register Assignment:
  • Allocation: Selecting which subset of variables and temporaries reside in high-speed hardware registers at each execution point.
  • Assignment: Deciding the specific physical hardware register (RAX, RBX, RCX, etc.) bound to each selected variable.
• Graph Coloring Formulation: Formulating global register allocation as an NP-complete $K$-vertex coloring problem over an Interference Graph.
• Peephole Optimization: A local target-level optimization that slides a small window across generated machine code, replacing redundant sequences with optimal hardware instructions.

📑Table of Contents

• 🏗️ Architectural Foundations: The Challenges of Code Generation
• 📐 Formal Foundations: Register & Address Descriptors
  • 1️⃣ Register Descriptor (reg_desc)
  • 2️⃣ Address Descriptor (addr_desc)
• 🎨 Register Allocation via Graph Coloring (Chaitin-Briggs & Kempe Heuristic)
  • 🕸️ Constructing the Interference Graph
• 🔍 Peephole Optimization Techniques
  • 1️⃣ Redundant Load/Store Elimination
  • 2️⃣ Unreachable Code Elimination
  • 3️⃣ Flow of Control Optimization (Jump Threading)
  • 4️⃣ Algebraic Simplification & Strength Reduction
  • 5️⃣ Machine Idioms
• 🏭 Real-World Production Context: Graph Coloring (AOT) vs Linear Scan (JIT)
• 📐 Numerical Applications & Worked Examples
  • Example 1: Interference Graph Construction & K-Coloring Trace
  • Example 2: Multi-Pass Peephole Optimization on Raw Assembly
  • Example 3: getReg() Register Allocation & Spill Trace
• 🎯 Exam & Interview Pitfall Check

---

🏗️ Architectural Foundations: The Challenges of Code Generation

Register Allocation vs Instruction Scheduling

The two foundational challenges of target code generation

Register Allocation

Register Allocation & Assignment

🎯

Dominant Architecture / DomainResource Management, Graph Coloring

• •Maps infinite virtual variables to a small, fixed set of K physical registers.
• •Formulated as NP-Complete K-Vertex Coloring on an Interference Graph.
• •Minimizes catastrophic memory spill traffic between CPU and RAM.
• •Governed by Kempe's heuristic (Simplify, Spill, Select).

"Registers are the fastest real estate in computing: allocate them wisely."

Instruction Scheduling

Instruction Scheduling

⏱️

Dominant Architecture / DomainPipeline Hazards, Superscalar Execution

• •Reorders legal machine instructions to prevent CPU pipeline stalls.
• •Hides memory load latencies and floating-point execution delays.
• •Must preserve all true (RAW), anti (WAR), and output (WAW) dependencies.
• •Frequently competes with register allocation: scheduling increases live ranges!

"Keep the execution pipeline fed without stalling execution units."

---

📐 Formal Foundations: Register & Address Descriptors

In a basic code generator operating on basic blocks, the compiler maintains two dynamic runtime data structures to track variable locations:

1️⃣ Register Descriptor (reg_desc)

Tracks what variables or temporaries are currently held in each physical CPU register.

• $\text{reg\_desc}[R] = \{ x, y \}$ denotes that physical register $R$ contains the current, valid value of variables $x$ and $y$.
• At the start of a basic block, all registers are initially empty: $\text{reg\_desc}[R] = \emptyset$.

2️⃣ Address Descriptor (addr_desc)

Tracks the current location(s) where the value of a named variable can be found (in memory, in register R1, in register R2, etc.).

• $\text{addr\_desc}[x] = \{ \text{memory}_x, R_1 \}$ indicates variable $x$ currently resides both in its assigned RAM memory location and inside CPU register $R_1$.

The getReg() Register Allocation Decision Stack

Priority cascade for acquiring a register for instruction x = y op z

Priority 1

1. Reuse Register of Operand y

♻️

If y is currently in register Ry, and y has no further uses (dead), reuse Ry for x.

Zero Register SpillIn-place Mutation

↓fallback to

Priority 2

2. Allocate Any Free Register

📦

If an unused physical register R is currently empty, allocate R directly to x.

No Memory OverheadInstant Assignment

↓fallback to

Priority 3

3. Spill an Occupied Register (Lowest Eviction Cost)

⚠️

Select an occupied register R to spill. Emit ST (store) to memory if value is dirty, then reuse R.

Calculates Spill CostMemory Store Incurred

---

🎨 Register Allocation via Graph Coloring (Chaitin-Briggs & Kempe Heuristic)

Modern optimizing compilers formulate register allocation as the Graph Coloring Problem: Given an Interference Graph $G = (V, E)$ and $K$ physical registers, can we assign one of the $K$ colors to each vertex such that no two adjacent vertices share the same color?

🕸️ Constructing the Interference Graph

1. Vertices ($V$): Every variable, temporary, or virtual register.
2. Edges ($E$): An undirected edge exists between $u$ and $v$ if $u$ and $v$ are simultaneously live at some program point. If $u$ and $v$ are live at the same time, they cannot occupy the same physical register!

Architecture Flow

Kempe's Heuristic for K-Register Allocation

The Simplify - Spill - Select algorithmic pipeline

✂️Step 1

Simplify

Find node v with degree < K. Push v onto stack; remove v and its incident edges from graph.

→

Repeat

⚖️Step 2

Spill Decision

If all nodes have degree >= K, pick a node to spill to RAM and remove it.

→

Stack Full

🎨Step 3

Select (Coloring)

Pop nodes from stack in reverse order; assign each node a free color != its neighbors.

Kempe's Theorem (1879):

If an undirected graph contains a vertex $v$ with degree $\text{deg}(v) < K$:

• The graph $G$ is $K$-colorable if and only if the reduced graph $G \setminus \{v\}$ is $K$-colorable!
• Proof Intuition: When we pop $v$ back off the stack, its neighbors occupy at most $(\text{deg}(v))$ colors. Since $\text{deg}(v) \le K - 1$, there is guaranteed to be at least one color free among the $K$ colors for vertex $v$!

---

🔍 Peephole Optimization Techniques

Peephole Optimization is a local target-code optimization technique that slides a small window (typically 2 to 4 instructions) over the generated assembly, replacing inefficient instruction sequences with faster or smaller equivalents.

1️⃣ Redundant Load/Store Elimination

; Before:
ST  x, R0       ; Store R0 into memory variable x
LD  R0, x       ; Redundant! R0 already contains x!

; After:
ST  x, R0       ; Second instruction completely erased!

2️⃣ Unreachable Code Elimination

Instructions immediately following an unconditional branch that have no incoming label can never be reached:

; Before:
JMP L2
ADD R1, R2, R3  ; Dead code: unreachable!
L2: ...

; After:
JMP L2
L2: ...

3️⃣ Flow of Control Optimization (Jump Threading)

; Before:
JMP L1
...
L1: JMP L2      ; Jump to a jump!

; After:
JMP L2          ; Direct branch!

4️⃣ Algebraic Simplification & Strength Reduction

• Replace $x = x + 0$ or $x = x \times 1$ with nothing (no-op elimination).
• Replace integer multiplication by powers of 2 with arithmetic left shifts:

$$x = x \times 8 \implies \text{SHL } x, 3$$

• Replace integer division by powers of 2 with arithmetic right shifts:

$$x = x / 4 \implies \text{SAR } x, 2$$

5️⃣ Machine Idioms

Leveraging target-specific hardware instructions:

• Clearing a register: MOV R0, 0 ($5$ bytes on x86) is replaced by XOR R0, R0 ($2$ bytes, zero memory access, executes in 0 cycles on modern register alias tables).
• Incrementing a counter: ADD R0, 1 is replaced with INC R0.

---

🏭 Real-World Production Context: Graph Coloring (AOT) vs Linear Scan (JIT)

In production runtimes, register allocation strategies balance code quality against compilation speed:

1. Chaitin-Briggs Graph Coloring Allocator (AOT Compilers: GCC, Clang, Rustc):

   • Builds global interference graphs and applies iterative Kempe coloring with optimistic spilling.
   • Generates high-efficiency machine code with minimal memory spills.
   • High time complexity ($O(V^2)$ to $O(V^3)$), making it ideal for Ahead-Of-Time (AOT) compilation where optimization quality outweighs compilation latency.

2. Linear Scan Register Allocation (JIT Compilers: V8, JVM HotSpot, .NET Core):

   • In Just-In-Time (JIT) engines running in real time inside web browsers or interactive servers, graph coloring introduces prohibitive compilation stalls.
   • JITs employ Linear Scan: they sort variable live intervals linearly by start point and allocate registers in a single forward pass in $O(V \log V)$ time.
   • Delivers roughly 90% of the performance of graph coloring at a tiny fraction of the compilation time.

---

📐 Numerical Applications & Worked Examples

Example 1: Interference Graph Construction & K-Coloring Trace

Consider the following straight-line code with 6 variables $\{a, b, c, d, e, f\}$:

(1) a = 1
(2) b = 2
(3) c = a + b
(4) d = b + c
(5) e = c + d
(6) f = d + e

Assume $a, b, c, d, e$ are dead immediately after their last uses, and only $f$ is live at the end of the block.

1. Determine the live range of each variable.
2. Construct the Interference Graph.
3. Apply Kempe's heuristic to find the minimum number of physical registers ($K$) required to execute this block without spilling.

Step-by-Step Analytical Trace:

1. Live Range Analysis:

   • $a$: Defined at (1), last used at (3). Live during: $(1) \to (3)$.
   • $b$: Defined at (2), last used at (4). Live during: $(2) \to (4)$.
   • $c$: Defined at (3), last used at (5). Live during: $(3) \to (5)$.
   • $d$: Defined at (4), last used at (6). Live during: $(4) \to (6)$.
   • $e$: Defined at (5), last used at (6). Live during: $(5) \to (6)$.
   • $f$: Defined at (6), live at exit.

2. Interference (Simultaneous Liveness):

   • At line (2): $a$ is live, $b$ is defined $\implies a$ interferes with $b$. Edge $(a, b)$.
   • At line (3): $a$ and $b$ are live, $c$ is defined. After (3), $a$ is dead. Live set $= \{b, c\} \implies b$ interferes with $c$. Edge $(b, c)$.
   • At line (4): $b$ and $c$ are live, $d$ is defined. After (4), $b$ is dead. Live set $= \{c, d\} \implies c$ interferes with $d$. Edge $(c, d)$.
   • At line (5): $c$ and $d$ are live, $e$ is defined. After (5), $c$ is dead. Live set $= \{d, e\} \implies d$ interferes with $e$. Edge $(d, e)$.
   • At line (6): $d$ and $e$ are live, $f$ is defined. After (6), $d$ and $e$ are dead. Live set $= \{f\} \implies e$ interferes with $f$. Edge $(e, f)$.

   The interference graph forms a linear chain:

$$a - b - c - d - e - f$$

3. Graph Coloring with Kempe's Heuristic:
   • Maximum degree of any node in the chain is $2$ (internal nodes $b, c, d, e$ have degree 2; endpoints $a, f$ have degree 1).
   • Test $K = 2$ registers (R1, R2):
     • Node $a$ has degree $1 < 2$. Push $a$ to stack. Graph becomes $b - c - d - e - f$.
     • Node $b$ now has degree $1 < 2$. Push $b$ to stack.
     • Node $c$ now has degree $1 < 2$. Push $c$ to stack.
     • Push $d, e, f$.
     • Stack: $[a, b, c, d, e, f]$ (top to bottom).
   • Pop and assign colors:
     • Color $f \to \text{R1}$.
     • Color $e \to \text{R2}$ (adjacent to $f$).
     • Color $d \to \text{R1}$ (adjacent to $e$).
     • Color $c \to \text{R2}$ (adjacent to $d$).
     • Color $b \to \text{R1}$ (adjacent to $c$).
     • Color $a \to \text{R2}$ (adjacent to $b$).
   • Conclusion: Minimum registers required $= \mathbf{2 \text{ registers}}$ (R1, R2). Zero spilling required!

---

Example 2: Multi-Pass Peephole Optimization on Raw Assembly

A code generator produces the following raw assembly sequence:

(1)  MOV  R0, a
(2)  ADD  R0, 0
(3)  MOV  b, R0
(4)  MOV  R0, b
(5)  MUL  R0, 4
(6)  MOV  c, R0
(7)  JMP  L1
(8)  ADD  R1, R2, R3
(9)  L1: JMP L2
(10) L2: RET

Apply peephole optimizations to reduce the instruction count. List each transformation applied.

Step-by-Step Analytical Trace:

1. Algebraic Identity:
   • Line (2) ADD R0, 0 adds zero to R0.
   • Action: Delete line (2).
2. Redundant Store/Load Elimination:
   • Line (3) writes R0 to memory variable b. Line (4) immediately loads memory variable b into R0.
   • R0 already holds the value of b!
   • Action: Delete line (4).
3. Strength Reduction:
   • Line (5) MUL R0, 4 multiplies R0 by constant $4 = 2^2$.
   • Action: Replace with arithmetic left shift: SHL R0, 2.
4. Unreachable Dead Code Elimination:
   • Line (7) is an unconditional branch JMP L1. Line (8) ADD R1, R2, R3 has no label and immediately follows JMP L1. It can never execute.
   • Action: Delete line (8).
5. Jump-to-Jump Elimination (Jump Threading):
   • Line (7) jumps to L1. At L1, line (9) immediately jumps to L2.
   • Action: Retarget line (7) directly to L2: JMP L2.
   • Label L1 now has zero incoming edges and can be deleted.

Final Optimized Assembly Stream:

(1) MOV  R0, a
(2) MOV  b, R0
(3) SHL  R0, 2
(4) MOV  c, R0
(5) JMP  L2
(6) L2: RET

Instruction count reduced from 10 to 6 (40% instruction reduction).

---

Example 3: getReg() Register Allocation & Spill Trace

Consider the three-address statement:

$$x = y + z$$

Given the machine status:

• Two physical registers: $R_0, R_1$.
• reg_desc[R0] = { y }
• reg_desc[R1] = { z }
• addr_desc[y] = { R0 } (not in memory; dirty)
• addr_desc[z] = { R1, memory_z } (in memory)
• Variable $y$ is dead after this statement; variable $z$ is live after this statement.

Determine the register allocated for $x$ by getReg() and describe the emitted assembly instructions.

Step-by-Step Analytical Trace:

1. Evaluate getReg() Priorities:
   • Priority 1: Can we reuse the register holding $y$?
     • $y$ is held in $R_0$.
     • $y$ is dead after this statement.
     • $y$ is not used by any other variable in $R_0$.
     • Decision: $R_0$ can be safely allocated for result $x$ without spilling!
2. Instruction Generation:
   • Since $y$ is in $R_0$ and $z$ is in $R_1$, the compiler emits:

ADD R0, R1      ; Computes y + z, storing result x into R0

3. Descriptor Updates:
   • reg_desc[R0] = { x } ($y$ is removed).
   • addr_desc[x] = { R0 }
   • addr_desc[y] = { } ($y$ is dead).
   • reg_desc[R1] = { z } (remains unchanged).

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: "What is the formal difference between Register Allocation and Register Assignment?"
Key Focus Points:

• Register Allocation: The decision of which values and variables should reside in registers at each execution point (selecting the working set).
• Register Assignment: The mapping of a specific allocated variable to a specific hardware register (e.g., binding variable $a$ to register RAX vs RBX).

Question 2: "Why is Kempe's graph coloring heuristic guaranteed to find a valid color when popping a node with degree $< K$?"
Key Focus Points:

• A node $v$ with degree $< K$ has at most $K - 1$ neighbors in the interference graph.
• When $v$ is popped from the stack during the Select phase, its neighbors have been assigned at most $K - 1$ distinct colors.
• Because the architecture provides $K$ distinct colors (registers), at least one color is guaranteed to remain unassigned and available for node $v$.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Assuming variables in the same basic block always interfere.
Answer: Misconception. Two variables interfere if and only if their live ranges overlap simultaneously. If variable $a$ is defined and dies before variable $b$ is created, their live ranges are disjoint. They do not interfere and can share the exact same physical register.

Trap 2: Spilling variables based purely on high graph degree.
Answer: Performance pitfall. When choosing which variable to spill, spilling an inner-loop variable with high degree causes catastrophic memory thrashing because memory loads and stores are inserted inside the loop. Compilers weight spill costs by loop depth ($10^d$), prioritizing spilling variables used outside loops even if their degree is lower.

Trap 3: Unsafe peephole elimination on memory-mapped I/O registers.
Answer: Hardware bug. In low-level systems programming, writing twice to a memory address (e.g. *dev_ctrl = 1; *dev_ctrl = 2;) might appear redundant to a naive peephole optimizer. However, hardware registers have read/write side effects (e.g. sending commands or pulsing pins). Compilers must respect the volatile keyword and prohibit dead store elimination on device registers.

---

🗺️View Complete Compiler Design Roadmap & Syllabus

← Previous Topic8.3 Runtime Environments, Activation Records & Storage AllocationNext Topic →Course Curriculum & Overview