Compiler Design

Cache locality

A cache is a small, fast memory between the CPU and main memory. Data moves in blocks called cache lines (typically 64 bytes). A program runs faster when most of its memory accesses are hits. Cache locality is the tendency of a program to access data that is already in, or close to, the data in the cache.

Two kinds of locality

Type	Meaning	Example
Temporal locality	A location that was just used is likely to be used again soon	A loop variable or a running sum accessed in every iteration
Spatial locality	Locations near a recently used one are likely to be used soon	Walking through consecutive array elements

When one element is fetched, the whole line comes with it (for example 16 consecutive 4-byte ints), so sequential access gives about 1 miss per 16 accesses, while a large stride can give a miss on every access.

Why it matters in loop optimization

Loops execute most of a program's instructions and memory accesses. A cache miss costs on the order of 100 cycles against 1-4 for a hit, so the order in which a loop nest touches memory often matters more than the arithmetic it does.

Example (C arrays are stored row by row)

// Poor spatial locality: column-wise walk, stride = N elements
for (j = 0; j < N; j++)
    for (i = 0; i < N; i++)
        sum += a[i][j];

// After loop interchange: row-wise walk, stride = 1
for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        sum += a[i][j];

Both loops compute the same result, but the second uses every element of each fetched cache line before it is evicted.

Loop transformations that improve locality

Transformation	Effect
Loop interchange	Reorders nested loops so the innermost loop has stride 1
Loop tiling (blocking)	Splits the iteration space into small blocks that fit in the cache so data is reused (key for matrix multiplication)
Loop fusion (jamming)	Merges loops that use the same data so it is used while still in cache
Loop fission (distribution)	Splits a loop whose body touches too much data for the cache
Array padding / data layout change	Avoids conflict misses; structure-of-arrays vs array-of-structures

The compiler applies these only after a dependence analysis shows that the new order gives the same results.

Target code generation

The code generator takes the (optimized) intermediate representation and the symbol-table information and produces target machine code that is correct and efficient.

Major stages

1. Instruction selection - choose target instructions for each IR operation.
2. Register allocation and assignment - decide which values live in registers.
3. Instruction scheduling (ordering) - choose the order of instructions.
4. Final clean-up such as peephole optimization, then emit the code.

1. Instruction selection

Maps IR operations to machine instructions, choosing the cheapest sequence that implements them. The choice depends on the instruction set and addressing modes. Techniques: tree-pattern matching, dynamic programming over expression trees.

For a = b + c a naive translation is

LD  R0, b
LD  R1, c
ADD R0, R0, R1
ST  a, R0

and for x = x + 1 a good selector uses a single INC x (or an add with an immediate) instead of load, add and store.

Contribution: decides the number and cost of instructions, so the code is small and fast, and uses special instructions where available.

2. Register allocation

Registers are far faster than memory but very few. Allocation decides which variables/temporaries to keep in registers; assignment picks the specific register. Methods: usage counts, graph colouring (variables that are live at the same time interfere and get different registers). If there are not enough registers, a value is spilled to memory.

Contribution: reduces loads and stores, which dominate execution time.

3. Instruction scheduling

Reorders independent instructions to avoid pipeline stalls and to use all functional units, without changing the program's result (data dependences must be respected).

Assume a load takes one extra cycle before its result can be used:

Unscheduled	Scheduled
LD R1, a	LD R1, a
ADD R2, R1, R3 (stall)	LD R4, b
LD R4, b	ADD R2, R1, R3
ADD R5, R4, R6 (stall)	ADD R5, R4, R6

The scheduled version has no stalls.

Contribution: hides latency and increases instruction-level parallelism, so the program runs faster on the pipeline.

Interaction: the stages influence each other. Scheduling more instructions in parallel needs more registers, and heavy register reuse creates dependences that limit scheduling. Compilers therefore balance the two.

Summary

Stage	Goal	Result
Instruction selection	Correct, low-cost instruction sequence	Fewer, cheaper instructions
Register allocation	Keep hot values in registers	Fewer memory accesses
Instruction scheduling	Avoid stalls, fill pipeline	Fewer cycles