Dependence Analysis and Polyhedral Loop Transformations

Reordering a loop is legal when the reordering does not change which value each memory access reads. That is a precise statement and it is decidable only for restricted classes of loops. Dependence analysis is the discipline of deciding it, and the polyhedral model is the formulation that makes the decision a solvable integer program rather than a collection of ad hoc tests.

The practical stakes are large. Vectorization, tiling, fusion, distribution, and software pipelining all require a dependence answer, and the answer is usually “unknown” unless the loop is affine — that is, unless every subscript is an affine function of the loop indices. The whole apparatus exists because “unknown” costs the transformation, and the difference between a good test and a weak one is the difference between a vectorized kernel and a scalar one.

The dependence relation

For a loop nest with iteration vectors i and j, there is a dependence from i to j if some statement at i writes a location that a statement at j reads or writes, and i precedes j in the original execution order. The direction is what matters for legality: a transformation that reverses or interchanges loops is legal if no dependence goes in the direction the transformation would reverse.

Three categories are distinguished by the distance vector d = j - i.

A flow dependence (read-after-write) carries a value forward, so it is a real dependence and cannot be broken without changing semantics. An anti-dependence (write-after-read) and an output dependence (write-after-write) are artifacts of storage reuse: if the compiler renames the storage, they disappear. This is why register renaming and array expansion change so much — they convert anti-dependences into nothing, and a loop that appeared to have a carried dependence turns out to be parallel.

The distinction matters concretely. A loop that computes b[i] = a[i] + a[i+1] and then writes back into a has an anti-dependence from the read of a[i+1] to the write of a[i], at distance one. Splitting the loop into a read phase into a temporary and a write phase removes it. A compiler that reports the anti-dependence as a barrier and stops has missed the transformation.

Affine subscripts and the test

A subscript is affine if it has the form c0 + c1*i1 + c2*i2 + ... with integer coefficients, where the ik are loop indices and c0 may involve loop-invariant values. Almost all array code in numerical computing is affine, which is why the polyhedral model is worth building.

For a pair of accesses A[f(i)] and A[g(j)], a dependence exists if there is an integer solution to

f(i) = g(j),   with  Lk <= ik, jk <= Uk   for each loop k,   and  i < j lexicographically

The bounds come from the loop limits, the equality from the subscript expressions, and the ordering constraint from the execution order. That is a system of linear Diophantine equations and inequalities, and solving it exactly is the Omega test’s job. Pugh’s algorithm decides the existence of integer solutions and can also produce a description of the solution set, which is what a transformation needs in order to know the dependence distance rather than merely its presence.

The older tests are cheaper and incomplete. The greatest common divisor test asks whether the difference of the two subscripts is divisible by the gcd of the coefficients; if not, no dependence exists, and because it ignores the loop bounds entirely it applies to any number of indices at once. The Banerjee test computes a range of possible differences from the bounds and checks whether zero is in the range, which does account for the bounds and is exact for a single subscript, but loses precision as soon as one subscript couples two or more loop indices. Both are linear-time. A production compiler runs the cheap tests first and only invokes the exact solver when they are inconclusive, which is why the expensive machinery is affordable.

/* Necessary condition only: a*i - b*j = c has an integer solution iff gcd(a,b) divides c.
   Bounds are ignored, so a "true" answer means "cannot rule out", not "depends". */
static long gcd(long x, long y) {
    while (y != 0) { long t = x % y; x = y; y = t; }
    return x < 0 ? -x : x;
}

static bool gcd_may_depend(long a, long b, long c) {
    long g = gcd(a, b);
    if (g == 0) return c == 0;   /* both subscripts constant: same element only if c is zero */
    return c % g == 0;
}
/* Bounds enter through the Banerjee or Omega test; this test only rules dependences out. */

The iteration space as a polyhedron

The polyhedral formulation collects everything into one object: the set of iteration vectors that satisfy the loop bounds and the enclosing conditional tests is a convex polyhedron in Z^d, called the iteration domain. Each statement has such a domain, and each memory access is an affine function from the domain to an address.

A schedule is an affine function from iteration vectors to a new ordering — typically a multi-dimensional time, one coordinate per loop level in the transformed nest. Legality is then a condition on the schedule: for every dependence, the schedule must map the source iteration to a lexicographically earlier time than the target. Writing that as a set of linear constraints over the schedule coefficients gives an integer linear program, and solving it produces a transformation that is legal by construction rather than by case analysis.

The benefit of this formulation is compositionality. Tiling, skewing, fusion, and interchange are all affine schedules, so a single legality check covers all of them, and the search over transformations becomes a search over schedule coefficients. The cost is that the formulation only covers affine code: a subscript involving a data-dependent index, a pointer-chasing loop, or an indirect array reference falls outside the model entirely, and the compiler must fall back to conservative reasoning.

Tiling and the locality argument

Tiling (blocking) splits a loop nest into an outer nest over tiles and an inner nest over the elements of a tile. The purpose is locality: a tile small enough that its working set fits in cache is processed to completion before moving to the next tile, so the data loaded into cache is reused by every iteration of the inner nest rather than evicted between them.

Legality requires the tile walk order to respect every dependence. With the tile loops placed outside the point loops, tiles are visited in the order in which the original nest would visit their first iterations, so if every component of every dependence distance vector is non-negative, each dimension’s tile index is non-decreasing along a dependence and any rectangular tile shape is legal. A dependence with a negative component breaks that argument: its target tile can be visited before its source tile, so the nest cannot be tiled as written, and the standard fix is to skew the iteration space — shearing it so the dependence becomes forward in the transformed coordinates — before blocking. Tile shape is then a locality choice rather than a legality one: a dependence whose distance is larger than the tile means the reuse it carries crosses tile boundaries, where the blocking cannot capture it.

The locality argument has numbers behind it. A cache line is 64 bytes on common x86-64 and AArch64 cores, so a tile that walks a row of a double matrix touches one line per eight elements. A tile whose inner dimension is a multiple of eight avoids touching partial lines at the boundary, and a tile whose working set is a few hundred kilobytes fits in the second-level cache typically sized at 256 KiB to 1 MiB per core. These are the figures that tile-size heuristics are built around, and they are approximate because the actual cache geometry varies by model.

Vectorization as a dependence question

A loop can be vectorized when every dependence it carries in the vectorized dimension has a distance at least as large as the vector width, so that no lane of a vector depends on another lane of the same vector. A loop-independent dependence, at distance zero, is no obstacle: each lane performs its own iteration in full, so the dependence is satisfied within every lane. The dependence analysis answers this question, and the vector width follows from the target: 128-bit registers hold four 32-bit integers or two 64-bit doubles, 256-bit and 512-bit extensions scale that accordingly.

The interesting cases are the ones where the dependence exists but can be removed. A reduction — sum += a[i] — has a loop-carried dependence on sum, but the dependence is associative and the reduction can be split into partial sums, one per vector lane, combined at the end. Recognising it requires knowing both that the operation is associative and that the floating-point semantics permit reassociation, which is a language question rather than an analysis question: strict IEEE 754 semantics forbid reassociating floating-point additions, and a compiler that vectorizes a floating-point reduction is changing the result.

A read of a[i-1] inside a loop writing a[i] has a genuine distance-one flow dependence and cannot be vectorized as written. It can be handled by keeping the previous iteration’s value in a register and shifting the vector, which is a transformation that the dependence test enables but does not perform. The distinction between “cannot vectorize” and “cannot vectorize without a shift” is exactly the information a distance vector provides and a yes/no dependence answer does not. Vectorization and Loop Unrolling, Trip Counts, and the Cost of Code Growth compete for the same budget: a vector body is already wide, so unrolling it multiplies register pressure without adding instruction-level parallelism.

Where the model breaks

Three failure modes recur.

Non-affine subscripts. a[b[i]] is a gather, and no affine function describes it. The compiler either treats it as an unknown dependence, blocking everything, or uses a runtime check — comparing the indices before executing the vectorized version and falling back if they conflict — which is the standard resolution for vectorization of indirect accesses.

Aliasing between arrays. Two pointers may point into the same buffer, so a write through one may affect a read through the other. The polyhedral model handles this by adding the alias possibility as a constraint, which usually destroys the transformation. The practical fix is a runtime alias check: test whether the ranges overlap, take the fast path if not, and fall back if they do. Compilers expose this as a promise the programmer can make, and the promise is unchecked in most languages, which makes it a correctness hazard rather than an optimization.

Integer overflow and undefined behaviour. The affine model assumes index arithmetic does not overflow; if it does, the iteration domain computed by the model is not the domain the program actually executes. Languages with wrapping integer arithmetic force the compiler to model the wrap, which breaks the polyhedron’s convexity. This is one of the reasons the model works best on loop bounds that are provably small and on code written with explicit range assumptions.

The last limitation is economic rather than theoretical. Building the polyhedron, solving the scheduling problem, and generating the transformed code is expensive at compile time, and the payoff is concentrated in a small fraction of loops. Production use therefore restricts the model to nests that pass a cheap eligibility screen — affine bounds, no calls, no pointer arithmetic, a minimum depth — and applies the full machinery only there. The screening is what keeps the compile-time cost proportional to the opportunity, and it is why the polyhedral optimizer in a general-purpose compiler runs on a minority of functions rather than on all of them.

The dependence result also constrains the cheaper transformations. A hoist out of the loop, as Loop-Invariant Code Motion and the Conditions It Needs describes, needs the load’s address to be unmodified by any store in the loop, which is a dependence question asked at the granularity of one access rather than a whole nest. The polyhedral machinery answers it exactly for affine code and the alias analysis answers it approximately for everything else, and most compilers run both rather than choosing between them.