Loop Transformations and the Polyhedral Model

Programs spend most of their time in loops, so loops are where an optimising compiler earns its keep. Hoisting invariant code out of a loop was a first taste; the transforms on this page are far more dramatic. They reshape the loop nest itself — swapping which loop is inner, chopping the iteration space into cache-sized blocks, welding two loops into one — to win locality and parallelism, all while computing exactly the same values. The governing question, always, is: which reshapings preserve the program's meaning? The answer is the theory of data dependence, and its most powerful modern expression is the polyhedral model.

The catalogue of loop-nest transforms

A handful of transformations recur throughout every optimising compiler. Each targets a specific enemy — poor cache behaviour, loop overhead, or hidden parallelism:

Transform	What it does	Chiefly buys
Interchange	swaps the order of two loops in a nest	stride-1 access → cache locality; exposes parallelism
Tiling (blocking)	splits a loop into blocks that fit in cache, iterating block-by-block	temporal locality — reuse data before it is evicted
Fusion	merges two adjacent loops into one body	reuse across loops; less loop overhead
Fission (distribution)	splits one loop into two	separates a parallel part from a serial one; helps vectorization
Unrolling	replicates the body u times, stepping by u	less branch/counter overhead; more ILP to schedule
Skewing	reshapes the iteration space (adds one index to another) to make dependences march diagonally	exposes a parallel wavefront in otherwise-serial nests

Tiling deserves a second look because it is the great locality win. Matrix multiply over large N streams a whole row and column per output element; by the time you revisit a cache line it has long been evicted. Tiling restructures the triple loop to work on b\times b sub-blocks that fit in cache, turning O(N^3) cache misses into a small fraction of that — often a several-fold speedup with zero change to the arithmetic.

Data dependence: the law every transform must obey

Two statement instances are dependent if they access the same memory location and at least one writes. Three flavours matter:

Flow (true) dependence — write then read (RAW). The read needs the written value; this is a real data flow you cannot reorder away.
Anti-dependence — read then write (WAR). The write must wait until the read has happened.
Output dependence — write then write (WAW). The final value must be the later write's.

For a loop, we summarise a dependence by a distance vector \vec{d} = \vec{i}_{\text{sink}} - \vec{i}_{\text{source}}: how many iterations apart (per loop level) the two accessing iterations are. In A[i] = A[i-1] + 1, iteration i reads what iteration i-1 wrote, so the distance is d = 1 — a loop-carried dependence. When only the sign matters we write a direction vector with entries (<, =, >). The golden rule:

A reordering transformation is legal if and only if it preserves the relative order of every pair of dependent iterations — i.e. every dependence distance vector stays lexicographically positive (the source still executes before the sink) under the transformed schedule.
Equivalently: no transform may make a sink iteration run before the source it depends on.

Seeing the iteration space

The clearest way to picture all this is to plot the iteration space: one point per loop iteration, arranged on the integer grid, with an arrow drawn for each dependence. Below is the classic stencil A[i][j] = A[i-1][j] + A[i][j-1]: each point depends on its west and south neighbours, giving distance vectors (1,0) and (0,1).

Both distance vectors are lexicographically positive, so the loops could legally be interchanged; but notice that no arrow is purely along one axis in the skewed sense — points on an anti-diagonal i+j = \text{const} have no arrows between them, so an entire anti-diagonal can execute in parallel as a wavefront. Reading legality and parallelism straight off the arrows is the whole art.

The polyhedral model: geometry as the unifying framework

The ad-hoc catalogue above hides a deep unity. In the polyhedral model, a loop nest with affine bounds and affine array subscripts is described exactly by three mathematical objects:

the iteration domain — the set of iteration vectors, a polytope carved out of \mathbb{Z}^n by the loop bounds (e.g. \{(i,j) : 0 \le i < N,\; 0 \le j \le i\});
access functions — affine maps from iteration vector to the array element touched (e.g. (i,j)\mapsto A[i+j]);
a schedule — an affine map assigning each iteration a logical timestamp, which defines the execution order.

The magic: every classical transform — interchange, tiling, fusion, skewing, and arbitrary compositions of them — is just a different choice of affine schedule applied to the same domain. Legality becomes a single question — does the new schedule keep every dependence lexicographically positive? — that reduces to integer linear feasibility. Optimisers such as Pluto and LLVM/GCC's Polly/Graphite search the space of legal affine schedules for one that maximises locality and parallelism, unifying the entire catalogue into one optimisation problem.

\text{transform} \;=\; \text{new affine schedule } \theta \quad\text{legal} \iff \theta(\vec{i}_{\text{sink}}) \succ \theta(\vec{i}_{\text{source}}) \text{ for every dependence.}

Testing legality of interchange, in code

Given the distance vectors of a 2-deep loop nest, loop interchange (swapping the two loops) is legal exactly when swapping the two components of every distance vector keeps it lexicographically positive. The one thing interchange cannot survive is a distance vector like (1,-1): swap it to (-1,1) and it becomes lexicographically negative — the sink would run before its source.

type Vec = [number, number]; // Lexicographically positive: first non-zero component is > 0. function lexPositive(v: Vec): boolean { for (const c of v) { if (c > 0) return true; if (c < 0) return false; } return false; // all zero: not a real cross-iteration dependence } // Interchange swaps the two loop levels, i.e. swaps the two components of every distance vector. function interchangeLegal(deps: Vec[]): boolean { return deps.every((d) => lexPositive([d[1], d[0]])); } // Stencil A[i][j] = A[i-1][j] + A[i][j-1]: distances (1,0) and (0,1). const stencil: Vec[] = [[1, 0], [0, 1]]; console.log("stencil interchange legal? " + interchangeLegal(stencil)); // true // A skewed dependence (1,-1) blocks interchange. const skewed: Vec[] = [[1, -1]]; console.log("(1,-1) interchange legal? " + interchangeLegal(skewed)); // false console.log(" because swapped (-1,1) lex-positive? " + lexPositive([-1, 1]));

The stencil interchanges freely; the skewed nest does not. That single check — "is the reordered distance vector still lexicographically positive?" — is, at heart, the entire legality test the polyhedral model generalises to arbitrary affine schedules.

Because the iteration domain of an affine loop nest is literally a polyhedron — an intersection of half-spaces, each half-space being one loop bound a\cdot\vec{i} \le b. A doubly-nested triangular loop \{0\le i<N,\ 0\le j\le i\} is a triangle; a rectangular nest is a box; tiling literally slices the polytope into smaller polytopes. Because the whole loop nest is captured as geometry, transformations are affine maps of that geometry, and the machinery of integer linear programming (via tools like isl, the integer set library) can reason about them exactly rather than pattern-matching source syntax. Turning a compiler-optimisation question into a computational-geometry question is what makes the model so powerful — and why it can discover transform compositions a human would never hand-code.

The seductive error is to justify a transform by the benefit — "tiling improves locality, so tile" — without checking dependences. Tiling, fusion and interchange are only legal when they respect every dependence; a single loop-carried dependence pointing the wrong way after the transform makes it illegal, and the compiler will silently compute wrong answers. Tiling a loop whose iterations must run strictly in order (a recurrence like x[i] = x[i-1] * a) does not magically become parallel just because the blocks fit in cache — the dependence (1) crosses every tile boundary. Locality is the reward; dependence legality is the gate, and the gate comes first. Skewing exists precisely to make an otherwise-illegal tiling legal by reorienting the dependences first.