Compiler Design

Register Allocation & Ershov Numbers

CPU Registers are the fastest memory locations. Because there are a limited number of them, the compiler must carefully decide which variables reside in registers and which are stored in memory.

Register Allocation: Deciding which variables should be kept in registers at each point in the program.
Register Assignment: Deciding which specific physical register to use for each allocated variable.

Heuristics Used:

Graph Coloring: Builds an interference graph (nodes = variables, edges = variables that are live at the same time). Allocating registers is equivalent to coloring the graph with k colors.
Linear Scan: Scans variables in order of their live range start; assigns a register or spills to memory if full. Fast and used in JIT compilers.

Ershov Numbers Algorithm

The Ershov numbering algorithm assigns a label to each node in an AST. This label determines the MINIMUM number of registers needed to evaluate the expression without spilling intermediate results to memory.

Leaf Node: label = 1
Interior Node with TWO DIFFERENT child labels:
If children have labels l1 and l2 (where l1 > l2), the parent's label = l1 (use the larger).
Interior Node with TWO EQUAL child labels:
If children have labels l1 = l2, the parent's label = l1 + 1 (need one more register to hold the first child's result while computing the second).
Unary Node: label = child's label (unchanged).

Code Generation Strategy (Sethi-Ullman):

Always evaluate the child subtree with the LARGER Ershov number first. This minimizes the total number of registers held hostage during computation.

Leaf c = 1, Leaf d = 1 → Node '+' = 2
Leaf e = 1, Leaf f = 1 → Node '+' = 2
Root '+' = 3 (since both children require 2 registers)

Minimum registers required: 3

Target Code Generation Architecture Dependent Code Improvement