Loop Unrolling, Trip Counts, and the Cost of Code Growth

Unrolling duplicates the loop body k times and advances the induction variable by k, reducing the number of backward branches and loop-counter updates by a factor of k. That accounting is the least interesting part of the transformation. The reason unrolling appears in every optimizing compiler is that a larger body gives the scheduler independent instructions to interleave, and gives the instruction selector more opportunity to keep the machine’s execution units busy across what were previously iteration boundaries.

The cost is code size and register pressure, both of which scale with k. The transformation is therefore a search for the largest k that does not spill, subject to knowing how many iterations the loop actually runs.

The trip count question

Unrolling by k requires the loop to be rewritten so that the number of iterations is a multiple of k, with the leftover handled separately. There are three standard arrangements.

Unroll with a remainder loop. The main loop runs floor(n/k) iterations of the unrolled body, then a second loop runs n mod k iterations of the original body. This is correct for any n and any k, and it costs a second copy of the body plus the code that computes the remainder. For small bodies the remainder loop can be larger than the main loop, which is a real size cost for a loop that runs twice.

Unroll with a runtime guard and a prologue. Instead of a trailing loop, the prologue executes up to k-1 iterations before entering the unrolled loop. The two are equivalent in effect; the prologue form avoids a second backward branch but duplicates the body anyway.

Unroll fully. If n is known at compile time and small, the loop can be replaced by straight-line code with no loop at all. This is the best outcome — the entire body becomes a scheduling region — and it applies to loops over small constant bounds, which in practice means loops whose bounds come from array sizes or template parameters rather than from data.

The compile-time knowledge matters more than the factor. A loop with an unknown trip count forces the remainder machinery; a loop with a known trip count that is a multiple of k needs none. This is why loop unrolling benefits so much from the constant propagation and range analysis described in Constant Propagation over a Flat Lattice: proving n is 16 does not merely enable unrolling, it enables the cheapest form of it.

A rotated loop is a prerequisite in most optimizing compilers. Rotation moves the loop test to the bottom, creating a preheader and a single back edge, and it establishes that the body executes at least once — which is what licenses speculative motion inside the unrolled body, as noted in Loop-Invariant Code Motion and the Conditions It Needs.

What the larger body enables

Three effects, in increasing order of importance.

Loop overhead amortization. The induction variable increment, the comparison, and the conditional branch cost a few instructions per iteration. Unrolling by four reduces that to roughly one set per four bodies. For a body of ten instructions this is a visible fraction; for a body of a hundred it is noise.

Scheduling across iterations. Without unrolling, the scheduler cannot move an instruction from iteration i+1 before the branch at the end of iteration i, because the branch is a control-flow boundary. After unrolling, iteration i+1’s body is straight-line code in the same block, so a load from the next iteration can be issued while the current iteration’s arithmetic is still in flight. On an out-of-order core the hardware may find that parallelism anyway; on an in-order core, or when the loop body has a long dependency chain, the compiler’s scheduling is what exposes it. This is the main reason unrolling helps on targets without dynamic reordering.

Enabling other transformations. A constant index after unrolling turns an indexed load into a displacement load, removing address arithmetic. A conditional inside the body that becomes constant after unrolling by a factor matching its period disappears. A loop that carries a dependency at distance two becomes two independent chains after unrolling by two, which is the classic software-pipelining prerequisite.

/* Unroll by 4 with a remainder loop. The compiler emits the equivalent IR. */
for (i = 0; i + 4 <= n; i += 4) {
    acc += a[i]; acc += a[i+1]; acc += a[i+2]; acc += a[i+3];
}
for (; i < n; i++) acc += a[i];

Register pressure is the binding constraint

Each unrolled copy of the body brings its own live values. A body with four simultaneously live temporaries, unrolled by four, has sixteen — more than the sixteen general-purpose registers available on x86-64 before any address or loop-control values are counted. The allocator then spills, and each spill is a store and a reload per iteration, which can cost more than the loop overhead the unrolling removed.

The standard mitigation is to unroll only as far as the pressure budget allows. Implementations estimate the number of live values in the unrolled body, compare against the register file size minus a reserve for the loop counter and addresses, and reduce k if the estimate exceeds the budget. The estimate is necessarily approximate because allocation happens later, which is why unrolling is usually placed before allocation but with a conservative estimate rather than an exact one.

A second mitigation is to unroll without increasing the live set: if the copies of the body write different array elements rather than accumulating into one variable, their live ranges do not overlap and the pressure does not grow. Recognising that case requires knowing the memory dependence structure, which is the same analysis that vectorization needs and that Dependence Analysis and Polyhedral Loop Transformations formalizes.

Partial unrolling versus full unrolling, and the size budget

Full unrolling of a large loop is a size disaster. A loop with a thousand iterations unrolled fully produces a thousand copies, which will not fit in any instruction cache and may exceed the compiler’s patience. Implementations cap full unrolling at a small trip count — on the order of a few dozen iterations for a small body, fewer for a large one — and use partial unrolling otherwise.

The two decisions interact with inlining. A callee that is fully unrolled after inlining may grow past the size threshold that would have prevented the inlining, so the pass order determines the outcome. Compilers that inline first and unroll second sometimes produce larger code than the reverse order for the same source, and the global size budget described in Inlining Decisions and the Cost Model Behind Them is what keeps the combination bounded.

Unrolling and the memory system

Unrolling changes the pattern of memory accesses, not just the instruction stream. Four consecutive loads from adjacent addresses can be combined by the hardware into fewer cache transactions if they fall in the same line; a 64-byte line holds sixteen consecutive 4-byte elements, so unrolling by four usually keeps all accesses within one or two lines. That reduces the number of distinct lines touched per iteration, which matters for the load-store unit’s throughput even when the data is in cache.

Unrolling also makes prefetching easier for the compiler: with a known stride and a known unroll factor, it can issue a prefetch for the address k iterations ahead, and the prefetch distance becomes an explicit constant rather than an inferred one. Hardware prefetchers detect strides on their own, so the compiler-side benefit is mostly on targets with weak or absent stride detection, and on access patterns that the hardware prefetcher cannot follow — multiple streams with interleaved strides, for example.

The counter-case is a loop whose body has a branch that is unpredictable. Unrolling multiplies the number of branches, and if each is mispredicted a fraction of the time, the total misprediction cost grows with k. Branch prediction is per-branch-site, so four copies of an unpredictable branch occupy four predictor entries instead of one; whether that helps or hurts depends on the predictor’s capacity and replacement policy, and it is not predictable from the source alone.

When not to unroll

A loop that is executed once should not be unrolled: the remainder machinery and the duplicated body cost code size and the main loop never runs. Profile data is what distinguishes this case, and the frequency estimate described in Profile-Guided Optimization and Hot-Cold Code Splitting is the input that suppresses unrolling for cold loops.

A loop whose body contains a call that cannot be inlined should not be unrolled aggressively, because each copy contains the call and the call overhead dominates whatever was saved. A loop with a carried dependency of distance one — each iteration reading what the previous wrote — gains nothing from unrolling, since the dependency chain is unchanged and the scheduler still cannot overlap the bodies. And a loop that is already vectorized should usually not be unrolled further: the vector body is already wide, and unrolling it multiplies the vector register pressure rather than the scalar instruction-level parallelism.