Compiler Design

Advanced Register Allocation

Registers are the fastest memory in a computer (access takes ~1 cycle, compared to ~100+ cycles for RAM). The goal of register allocation is to keep as many frequently-used variables as possible in registers. This involves two sub-problems: Allocation (which variables) and Assignment (which physical registers).

This algorithm computes the minimum number of registers needed to evaluate an expression tree bottom-up.

Leaves: Left child = 1, Right child = 0.
Interior Nodes: If labels L ≠ R, parent label = max(L, R).
Interior Nodes: If labels L = R, parent label = L + 1.

Solved Example: x = (a + b) − (e − (c + d))

Step 1 — Build tree & Label:
Leaves: a=1, b=0, e=1, c=1, d=0
(c+d)    : L=1, R=0  -> max(1,0) = 1
(e-(c+d)): L=1, R=1  -> equal -> 1+1 = 2
(a+b)    : L=1, R=0  -> max(1,0) = 1
Root (-) : L=1, R=2  -> max(1,2) = 2

Result: Minimum 2 registers required.

For complex control flows, register allocation is formulated as a graph colouring problem:

Interference Graph: Nodes are variables. An edge is drawn between two variables if they are live simultaneously.
Graph Colouring: Assign colours (registers) such that no two adjacent nodes share the same colour.
If the graph requires k colours and we have k registers, it is feasible. Otherwise, some variables must be spilled (stored in memory).

Architecture Dependent Code Improvement Target Code Generator Design