Loop Dependences and What Blocks Vectorisation

Vectorising a loop means executing several iterations’ operations in one instruction, which means the iterations must be independent in a precise sense: the value each iteration reads must not depend on a value another concurrent iteration writes. A compiler establishes this by constructing a dependence graph over the loop, one node per operation per iteration, and checking whether any cycle exists that would be violated by reordering. If a cycle exists across iterations, the iterations cannot be combined.

The difficulty is that the check must be sound for every possible input. A compiler that vectorises a loop that occasionally has a dependence produces wrong answers, so the analysis is conservative by construction, and every construct it cannot reason about becomes a reason to refuse.

The four kinds of dependence

A flow dependence exists when one statement writes a location and a later statement reads it. An anti-dependence exists when a statement reads a location and a later statement writes it, because reordering would let the write happen first. An output dependence exists when two statements write the same location, because the order of writes determines the final value. These three are all subsumed by asking whether the memory locations the two statements touch may overlap; when they do, the pair must stay ordered in the original sequence.

The fourth kind is what makes vectorisation interesting. A loop-carried dependence is one where the conflicting accesses are in different iterations of the same statement. For a[i] = a[i-1] + b[i], the read of a[i-1] in iteration i conflicts with the write of a[i] in iteration i-1. The compiler can see this directly because both addresses are expressed in terms of the same index variable with constant offsets.

A dependence has a distance, the number of iterations between the two accesses, and a direction. Distance zero means the two accesses are in the same iteration, which is harmless for vectorisation because the operations remain in order within the vector. Distance greater than zero means a real loop-carried dependence.

The distance matters. A distance-one flow dependence through a single element serialises the loop. A distance that is larger than the vector length does not prevent vectorising the loop, because the iterations being combined are far enough apart in time to be safe. A distance of n, where n is the trip count, would be odd, but a distance of 64 with a vector length of 16 means iterations 0–15 and 64–79 can be combined without conflict, which is enough for a valid vectorised loop so long as the compiler handles the boundaries.

Distance, direction, and the shifting test

For affine subscripts, meaning addresses of the form a + i*d, the dependence question reduces to a Diophantine problem: does the equation a1 + i*d1 = a2 + j*d2 have a solution with i and j in range and i < j? The classic dependence tests answer this for integer coefficients. Banerjee’s inequality test is exact for a single subscript and conservative once several subscripts interact; the Omega test decides more cases exactly, at a higher cost. Both can be expensive, which is why compilers run cheaper tests first and fall back to the exact ones only when the cheap test is inconclusive.

The cheap test is the gcd test: a dependence exists only if the difference of the base addresses is divisible by the gcd of the coefficients. It is necessary but not sufficient, so passing it means “maybe” and failing it means “never”. Failing it is common in loops where the bases are distinct arrays and the strides are simple, which is why array-based numeric loops are the easiest to vectorise.

Aliasing as the practical wall

For pointers rather than arrays, the affine form is unavailable and the compiler must reason about whether two pointers may point into overlapping memory. In C, this question is almost always answerable only as “maybe”. A function taking float *restrict gives the compiler a guarantee and the loop vectorises; the same function without restrict does not, because the caller could legally pass two pointers into one array with an overlap of one element, and the vectorised version would produce a different result.

/* Compiler sees two possibly-aliased pointers: no vectorisation. */
void scale(float *a, float *b, float k, int n)
{
    for (int i = 0; i < n; i++)
        a[i] = a[i] * k + b[i];
}

/* restrict promises the objects do not overlap: vectorisable. */
void scale_ok(float *restrict a, float *restrict b, float k, int n)
{
    for (int i = 0; i < n; i++)
        a[i] = a[i] * k + b[i];
}

This is not a compiler deficiency. Where the language permits aliasing, a vectorised loop is wrong on some legal inputs, and soundness wins. Languages with stronger aliasing or ownership rules give the compiler more to work with at the cost of expressiveness; languages with unrestricted pointers require the programmer or the standard library to assert non-aliasing.

Two mechanisms recover some of the lost ground. Versioning emits a runtime check comparing the pointer ranges before entering the vector loop, and falls back to the scalar loop if they overlap. The check costs a compare and a branch, which is negligible for long loops and significant for short ones. Loop distribution splits a loop into separate loops over each array when doing so breaks the dependence; the split helps only if the parts are individually vectorisable.

Reductions, scans, and the independence the hardware assumes

A reduction is a loop-carried dependence through an associative operator: s += a[i]. Vectorising it requires changing the order of operations, which is legal for integers and for floating point only if the language allows reassociation. Compilers under strict floating-point semantics will not vectorise a floating-point sum, and this is a semantic restriction rather than a performance one; the flag that enables it changes the results.

The vectorised reduction uses several partial sums, one per lane, and combines them at the end. That is the same transformation described for software pipelining in Software Pipelining and Loop-Carried Dependences, applied at the element level instead of the instruction level. The cost is that the intermediate order differs from the source, so the result can differ in the last bits.

A scan, where each output depends on the prefix of all previous elements, is a genuine loop-carried dependence with distance one, and no permutation of a simple loop removes it. It is vectorised by a different structure: a log-step algorithm computes the prefix sums within a vector with a sequence of shifts and adds, then broadcasts the block total to the next vector. The number of steps is logarithmic in the vector length, so a length-16 scan takes four shift-add steps rather than one. The hardware cost is the shift network, which is a crossbar; the compiler cost is the recognition that the loop is a scan at all.

Histogram updates and conflict detection

Any loop that writes to a location computed by its own body is a dependence the compiler cannot resolve unless it understands the address computation. A histogram update h[a[i]]++ reads and writes an address derived from data, so two iterations may touch the same bucket. The compiler must keep them ordered, and the loop runs at scalar speed.

The vector-friendly restructuring is to detect the conflict. A conflict-detection instruction compares a vector of indices against itself for equal pairs and produces a mask of lanes that must be serialised; the loop then does the vector update where no conflict exists and a scalar update where one does. The cost is the comparison plus a branch for the rare conflicting case. Hardware support for this exists in some ISAs as a gather-then-compare sequence rather than as a single instruction, and its performance depends on the conflict rate, which is high for a small histogram and low for a hash table with a large table.

The decision a compiler makes

The vectoriser’s sequence is roughly: analyse the loop nest for dependence, test whether the innermost loop’s dependences permit combining its iterations, estimate the benefit from trip count and element type, consider the cost of the prologue and epilogue, and choose a vector length or a factor. Each step can reject the loop, and the rejection is sound rather than optimistic.

This is why the practical advice on vectorisation reduces to making the analysis easy: use array indexing rather than pointer arithmetic where possible, assert non-aliasing where the language allows it, keep the inner loop’s trip count large and its stride unit, avoid data-dependent control flow inside the loop, and let reductions be expressed in a form the compiler recognises. None of these changes the algorithm, and all of them change what the compiler can prove.

The hardware’s contribution is the mask and length machinery described in Mask Registers, Tail Handling, and the Cost of the Last Iteration, and the memory addressing modes described in Strided, Indexed, and Gather Memory Access. Those features remove the mechanical obstacles to vectorising a loop once the dependence analysis has cleared it. They do not remove the dependence itself, and no instruction set feature can, because a true dependence is a property of the computation rather than of the machine that runs it.