Code generation and register allocation (outside syllabus, used in the journey)

Why it exists

The last phase of a compiler turns the intermediate code into instructions for a real machine. A real machine has few registers, which are much faster than memory, and arithmetic works on registers. So the compiler must decide which values live in which register at each moment, and what to do when the program has more live values than registers. The topic is outside the official GATE syllabus, but it has appeared in questions: how many registers does an expression need, how many registers does this program need without spilling, which optimisation uses live variable analysis. It also completes the story of the compiler: the data flow analysis of the earlier pages finds the live variables that decide the registers.

Prerequisites

You need the three-address code and the basic block of basic blocks and control flow graphs, and the idea of registers and load/store instructions from addressing modes.

Precise definitions

The machine. Registers $R_1, R_2, \ldots$; instructions LD R, x (memory to register), ST x, R (register to memory), and arithmetic OP Rd, a, b where $a$ and $b$ are registers or immediate constants and the result may be put in the register of an operand. Only loads and stores access memory. (Where a machine allows a memory operand in an arithmetic instruction, fewer registers are needed; a question states which.)

Code generation has three jobs: instruction selection (which instructions), register allocation (which values are in registers at each point) and register assignment (which register holds which value).

How many registers does an expression need? The Sethi-Ullman number. For an expression tree, label every node:

• a leaf that is a variable: 1 (it must be loaded into a register); a leaf that is a constant used as an operand: 0 (an immediate operand);
• an operation node with labels $l$ and $r$ of its children: $\max(l, r)$ if $l \ne r$, and $l + 1$ if $l = r$.

The label of the root is the minimum number of registers with which the expression can be evaluated without storing intermediate results in memory, and the algorithm that achieves it is: evaluate the child with the larger label first (its register is then free except for its result), then the other child, using one more register. If the labels are equal, either order needs $l + 1$. The code uses exactly the registers $R_1, \ldots, R_{label}$.

Live variables. A variable is live at a point if its current value may still be used later (before it is redefined). It is found by a backward pass over the code (the liveness analysis): for each instruction, live-in $=$ (live-out $-$ defined) $\cup$ used. Two values that are live at the same time cannot share a register.

Registers needed by a program. For straight-line code the minimum number of registers without spilling is the largest number of values that must be in registers at the same time: for every instruction $\max(|\text{live-in}|, |\text{live-out} \cup \{\text{result}\}|)$ (the result may reuse the register of an operand that dies there). A variable that is never used still needs a register at the moment it is computed.

Interference graph and colouring. The interference graph has one node per variable and an edge between two variables that are live at the same time (more exactly: a variable defined at an instruction is joined to every other variable live just after it, except the source of a plain copy). Register assignment is graph colouring: colours are registers, and adjacent nodes get different colours; the minimum number of colours is the chromatic number, which equals the largest set of mutually interfering variables for the programs of this page. Finding the chromatic number of a general graph is NP-hard; compilers use heuristics (Chaitin's algorithm: remove a node with fewer than $k$ neighbours, colour the rest, put it back).

Spilling. If the graph cannot be coloured with the $k$ available registers, some values are spilled: stored in memory (a ST) and loaded again (LD) when needed. The compiler chooses values with a distant next use or a low use count. The minimum number of spills for a given number of registers and a given program can be found by search; it is 0 when the registers are at least the maximum number of live values.

Code for a basic block. The simple generator keeps two descriptors: the register descriptor (which variables each register holds) and the address descriptor (where the current value of each variable is: memory, a register, or both). For each statement $x = y\ op\ z$:

1. get a register for each operand (use the register that already holds it; otherwise load it into a free register; if none is free, spill a register: store its variable if its only copy is in the register and it is still needed, preferring registers whose values are dead or also in memory, and then the value whose next use is farthest);
2. choose the register for the result: the register of $y$ (or $z$) if that operand is not live afterwards (so the result can overwrite it), else a free register;
3. emit OP, then update the descriptors: the register now holds only $x$, and $x$ is nowhere else;
4. at the end of the block store every live variable whose only copy is in a register.

How it works

Sethi-Ullman. Five expressions; the label (and the minimum over all evaluation orders, found by search) and the size of the generated code.

Live variables of a small straight-line program, instruction by instruction, and the number of values that need registers at each:

Interference graph and a colouring with the minimum number of colours:

Spilling. The minimum number of spills for the same program with fewer registers than the peak:

A block compiled with 3 registers and with 2. With three registers nothing is spilled; with two the generator must store a value and load it back. Descriptors after each statement.

Worked examples

#include <stdio.h>
 
enum kind { VAR, CONST, OP };
struct node { enum kind k; const char *name; int imm; char op; int l, r; };
 
static struct node t[64];
static int nn;
 
static int var(const char *s) { t[nn] = (struct node){VAR, s, 0, 0, -1, -1}; return nn++; }
static int cst(int v) { t[nn] = (struct node){CONST, 0, v, 0, -1, -1}; return nn++; }
static int op(char o, int l, int r) { t[nn] = (struct node){OP, 0, 0, o, l, r}; return nn++; }
 
static int label(int i) {
    if (t[i].k == CONST) return 0;
    if (t[i].k == VAR) return 1;
    int l = label(t[i].l), r = label(t[i].r);
    return l == r ? l + 1 : (l > r ? l : r);
}
 
struct opd { int imm; int v; };
 
static struct opd gen(int i, int k) {
    if (t[i].k == CONST) return (struct opd){1, t[i].imm};
    if (t[i].k == VAR) {
        printf("LD R%d, %s\n", k, t[i].name);
        return (struct opd){0, k};
    }
    struct opd a, b;
    if (label(t[i].l) >= label(t[i].r)) {
        a = gen(t[i].l, k);
        b = gen(t[i].r, k + 1);
    } else {
        b = gen(t[i].r, k);
        a = gen(t[i].l, k + 1);
    }
    const char *name = t[i].op == '+' ? "ADD" : t[i].op == '-' ? "SUB" : t[i].op == '*' ? "MUL" : "DIV";
    printf("%s R%d, ", name, k);
    printf(a.imm ? "#%d, " : "R%d, ", a.v);
    printf(b.imm ? "#%d\n" : "R%d\n", b.v);
    return (struct opd){0, k};
}
 
int main(void) {
    int roots[5];
    /* (a - 1) * (((b + c) / 3) + d) */
    roots[0] = op('*', op('-', var("a"), cst(1)), op('+', op('/', op('+', var("b"), var("c")), cst(3)), var("d")));
    /* (a + b) * (c + d) */
    roots[1] = op('*', op('+', var("a"), var("b")), op('+', var("c"), var("d")));
    /* ((a + b) + c) + d */
    roots[2] = op('+', op('+', op('+', var("a"), var("b")), var("c")), var("d"));
    /* a + (b + (c + d)) */
    roots[3] = op('+', var("a"), op('+', var("b"), op('+', var("c"), var("d"))));
    /* ((a + b) * (c - d)) / ((e + f) * (g - h)) */
    roots[4] = op('/', op('*', op('+', var("a"), var("b")), op('-', var("c"), var("d"))), op('*', op('+', var("e"), var("f")), op('-', var("g"), var("h"))));
    printf("Sethi-Ullman labels:");
    for (int i = 0; i < 5; i++) printf(" %d", label(roots[i]));
    printf("\n");
    gen(roots[0], 1);
    return 0;
}

Sethi-Ullman labels: 2 3 2 2 4
LD R1, b
LD R2, c
ADD R1, R1, R2
DIV R1, R1, #3
LD R2, d
ADD R1, R1, R2
LD R2, a
SUB R2, R2, #1
MUL R1, R2, R1

#include <stdio.h>
 
/* variables u v w x y z are bits 0..5 */
#define U 0
#define V 1
#define W 2
#define X 3
#define Y 4
#define Z 5
 
struct stmt { const char *text; int dst, a, b; };      /* dst, a, b: variable index, or -1 for none / a constant */
 
static int popcount(int m) { int c = 0; while (m) { c += m & 1; m >>= 1; } return c; }
 
static void show(int m) {
    printf("{");
    int first = 1;
    for (int i = 0; i < 6; i++)
        if (m >> i & 1) { printf("%s%c", first ? "" : ",", "uvwxyz"[i]); first = 0; }
    printf("}");
}
 
int main(void) {
    struct stmt p[7] = {
        {"x = 2", X, -1, -1}, {"y = 3", Y, -1, -1}, {"z = x + y", Z, X, Y}, {"w = z * x", W, Z, X},
        {"v = w + y", V, W, Y}, {"u = v - z", U, V, Z}, {"return u + w", -1, U, W}};
    int before[7], after[7], live = 0, peak = 0;
    for (int i = 6; i >= 0; i--) {
        after[i] = live;
        if (p[i].dst >= 0) live &= ~(1 << p[i].dst);
        if (p[i].a >= 0) live |= 1 << p[i].a;
        if (p[i].b >= 0) live |= 1 << p[i].b;
        before[i] = live;
    }
    for (int i = 0; i < 7; i++) {
        int need_after = after[i] | (p[i].dst >= 0 ? 1 << p[i].dst : 0);
        int need = popcount(before[i]) > popcount(need_after) ? popcount(before[i]) : popcount(need_after);
        if (need > peak) peak = need;
        printf("%-13s live before ", p[i].text);
        show(before[i]);
        printf(", after ");
        show(after[i]);
        printf("; registers needed here: %d\n", need);
    }
    printf("maximum number of live values: %d\n", peak);
    return 0;
}

x = 2         live before {}, after {x}; registers needed here: 1
y = 3         live before {x}, after {x,y}; registers needed here: 2
z = x + y     live before {x,y}, after {x,y,z}; registers needed here: 3
w = z * x     live before {x,y,z}, after {w,y,z}; registers needed here: 3
v = w + y     live before {w,y,z}, after {v,w,z}; registers needed here: 3
u = v - z     live before {v,w,z}, after {u,w}; registers needed here: 3
return u + w  live before {u,w}, after {}; registers needed here: 2
maximum number of live values: 3

Cheat box

Traps and GATE patterns

Connections

The live variables come from the liveness analysis of the data flow pages; the code generator works on a basic block of three-address code, which a DAG or local optimisation has already tidied. The instructions it emits are those of the machine described in addressing modes.

PYQs

Which ONE of the following techniques used in
compiler code optimization uses live variable
analysis?

Consider the expression ( a-1)* (((b + c) / 3) + d) . Let
X be the minimum number of registers required by an
optimal code generation (without any register spill)
algorithm for a load/store architecture in which (i)
only loads and store instructions can have memory
operands and (ii) arithmetic instructions can have
only register or immediate operands. The value of X
is _________.

The following code segment is executed on a
processor which allows only register operands in its
instructions. Each instruction can have almost two
source operands and one destination operand.
Assume that all variables are dead after this code
segment.
c = a + b;
d = c *a;
e = c + a;
x = c *c;
 if (x > a){
 y = a*a;
 }
 else {
d = d * d;
e = e*e;
 }

Suppose the instruction set architecture of the
processor has only two registers. The only allowed
compiler optimization is code motion, which
moves statements from one place to another while
preserving correctness. What is the minimum
number of spills to memory in the compiled code?

Consider evaluating the following expression tree on
a machine with load-store architecture in which
memory can be accessed only through load and store
instructions. The variables a, b, c, d and e initially
stored in memory. The binary operators used in this
expression tree can be evaluate by the machine only
when the operands are in registers. The instructions
produce results only in a register. If no intermediate
results can be stored in memory, what is the minimum
number of registers needed to evaluate this
expression?
(b)

COMPILER DESIGN

The program below uses six temporary variables a,
b, c, d, e, f.

a = 1

b = 10

c = 20

d = a+b

e = c+d

f = c+e

b = c+e

e = b+f

d = 5+e

return d+f

Assuming that all operations take their operands
from registers, what is the minimum number of
registers needed to execute this program without
spilling?

Self-check

Revision card

References