Loopstypical

Loop Unrolling

Duplicate the body so one iteration of the new loop does the work of several. It removes branches and exposes instruction-level parallelism, and it pays for both in code size and instruction-cache pressure — a trade whose sign depends on the trip count and the machine.

The question

Does unrolling a loop still help on a processor that predicts branches almost perfectly?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

A natural loop with a known or estimated trip count, and an induction variable whose step the compiler can see. The trip count is what the transformation needs and what decides its shape: a compile-time-constant count permits full unrolling with no residual loop, and an unknown count requires a remainder loop or a prologue to handle the iterations that do not fill a complete unrolled block.

What this phase may assume or do

Unrolling is almost always legal, because duplicating a body preserves every dependence: iteration i+1 still follows iteration i in the same order. The precondition is arithmetic rather than semantic — the induction variable must be advanced correctly for the unrolled step, and the remaining iterations when the trip count is not a multiple of the factor must be executed exactly once each. Where it stops being legal is where the loop can exit from the middle: an early exit inside the body must still be checked at each duplicated copy, or an iteration runs that should not have.

Key points

The branch-removal benefit is small on cores with good loop prediction; the instruction-level-parallelism benefit is the modern reason unrolling still matters.
Multiple accumulators break a dependence chain — legal for integers, and for floats only with reassociation permission.
A trip count that is not a multiple of the factor requires a remainder loop, whose cost dominates at small trip counts.
The costs are code size, instruction-cache pressure and register pressure, all measurable and all capable of making the unrolled loop slower.
Unrolling is often a precondition for vectorization, and hand-unrolling can defeat the vectorizer by hiding the shape it recognises.
The factor depends on the microarchitecture, so hand-picking one fixes a decision that should follow the target.

What unrolling actually removes

Unrolling by four turns four increments, four condition tests and four branches into one increment, one test and one branch. That is the loop-overhead story, and on a 1990s in-order machine it was most of the benefit.

On a current out-of-order core with a good branch predictor, the loop-back branch is predicted correctly almost every iteration and costs close to nothing — the predictor learns a loop. So if reducing branches were the only benefit, unrolling would have quietly stopped mattering, and the honest version of this lesson would say so.

It has not stopped mattering, for a different reason: the duplicated bodies are independent, and independence is what an out-of-order core needs to keep its execution units busy. A loop whose body is a single dependent chain — accumulate into one variable — is limited by the latency of that chain, and unrolling with multiple accumulators breaks the chain into several that proceed in parallel. That is the modern argument for unrolling, and it is about [[instruction-level-parallelism]] rather than about branches.

Unrolling is also an enabler. A vectorizer needs several iterations' worth of work visible at once; unrolling is often the step that exposes it. And with the body duplicated, the scheduler has a larger window of independent instructions to interleave, and CSE can share address computations across the copies.

Unrolling by four, with the remainder handled explicitly

Before

for (int i = 0; i < n; i++)
    sum += a[i];

After

int i = 0;
// four independent accumulators break the dependence chain
int s0 = 0, s1 = 0, s2 = 0, s3 = 0;
for (; i + 3 < n; i += 4) {
    s0 += a[i];   s1 += a[i+1];
    s2 += a[i+2]; s3 += a[i+3];
}
sum += s0 + s1 + s2 + s3;
for (; i < n; i++)      // remainder
    sum += a[i];

Legal only when

The four accumulators are only valid because integer addition is associative, so regrouping the additions gives the identical result for every input. The remainder loop is required whenever n is not a multiple of four, and it must run exactly the leftover iterations, in order.

Illegal when

The accumulator is a floating-point value. Floating-point addition is not associative, so splitting one accumulator into four and summing them at the end can produce a different result — which is why a compiler will not do this to a double reduction without -ffast-math, and why the same loop vectorizes in C with the flag and not without it. See [[strength-reduction]] for the same restriction in its smallest form.

The costs, and the shape of the trade

targetHow much unrolling pays depends on the microarchitecture: the size of the L1 instruction cache, the number of execution ports, the latency of the operation in the dependence chain, and whether the core has a loop-stream buffer that already eliminates fetch cost for small loops. A factor that is optimal on one x86-64 core can be a regression on another, which is the strongest argument against hand-picking one.

Every unroll multiplies the body's code size by the factor and adds a remainder loop. Instruction cache is a small shared resource, and a hot loop that stops fitting in it converts a compute-bound loop into a fetch-bound one — which shows up as a benchmark that gets slower as the unroll factor increases, with no change in the work being done.

On very small trip counts the remainder loop dominates. A loop that usually runs three times, unrolled by eight, spends its life in the remainder path plus a wasted trip-count test. This is why compilers unroll far less aggressively without profile data than with it: the trip count is exactly the thing they are guessing about, and [[profile-guided-optimization]] is exactly the thing that stops them guessing.

There is also a register cost. Four accumulators need four registers, and unrolled address computations need more. Past the register file, the allocator spills and the unrolled loop performs memory traffic the rolled one did not — the same failure mode as an over-aggressive hoist.

When to unroll, and what decides ittypical

Situation	Unrolling helps because	Or hurts because
Long trip count, short dependent body	Multiple accumulators break the latency chain and fill execution units	Only if register pressure rises past the file
Compile-time constant, small trip count	Full unroll removes the loop entirely, and the index becomes a literal	Nothing much — this is the clean case
Unknown, usually small trip count	Rarely helps	The remainder loop plus the entry test dominate; the unrolled body is never reached
Large body already at cache limitstarget	Rarely helps	The duplicated body evicts the hot working set; the loop becomes fetch-bound
Loop that could vectorize	Exposes several iterations at once, which the vectorizer needs	Unrolling by the wrong factor can defeat the vectorizer's own unrolling
Floating-point reductionspec	Helps only if reassociation is permitted	Without `-ffast-math` the accumulators cannot be split, and unrolling buys only branch removal

Who should choose the factor

The compiler has the target cost model and, with a profile, the trip-count distribution. A programmer usually has neither. Hand-unrolling in source is one of the more reliably counterproductive optimizations: it fixes a factor that was tuned for one machine, it obscures the loop's structure, and it frequently *prevents* the compiler from vectorizing because the vectorizer no longer recognises the shape.

The pragmas exist for the cases where you have measured and the compiler is wrong: #pragma unroll(4), #pragma clang loop unroll_count(4), #pragma GCC unroll 4. They are a directive, not a hint, and the right way to use them is with a before-and-after measurement on the target hardware rather than a belief about branch costs.

The one hand-written form that still earns its place is the multiple-accumulator restructuring for a floating-point reduction, precisely because the compiler is *forbidden* from doing it without permission. Writing four accumulators yourself is you taking responsibility for the reassociation, which is a defensible engineering decision made explicitly in the source rather than globally by a flag.

How it works

The steps, in the order the compiler takes them.

Identify the loop, its induction variable and its step, and estimate or read the trip count.
Choose a factor from the target cost model, the body size, the estimated trip count, and profile data where available.
Duplicate the body the chosen number of times, renaming values and adjusting each copy's index expression by its offset within the unrolled block.
Advance the induction variable once per unrolled block rather than once per copy, and adjust the exit test to leave room for a full block.
Emit a remainder loop, or a prologue, to execute the iterations that do not fill a block. A constant trip count divisible by the factor needs neither.
Where the loop carries a reduction and reassociation is permitted, split the accumulator into one per copy and combine them after the loop.
Re-run simplification: address computations across the copies are now common subexpressions, and the scheduler has a larger window.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

A benchmark gets slower as the unroll factor rises, with identical instruction counts per element. The hot loop no longer fits in the instruction cache and the core is stalled on fetch.
A loop that usually runs twice is unrolled by eight, and essentially all execution goes through the remainder loop plus a pointless entry test. The profile shows overhead with no unrolled body ever entered.
A hand-unrolled loop stops being vectorized after a compiler upgrade improved the vectorizer, because the vectorizer recognises the simple shape and not the unrolled one. The measured regression is attributed to the compiler.
A floating-point sum changes value after an unroll with multiple accumulators is enabled by a flag, and a regression test comparing exact bit patterns fails. Nothing is wrong; the reassociation was permitted.
Register pressure rises past the register file in the unrolled body, the allocator spills the accumulators, and the loop does four stores and four loads per block that the rolled version did not.

When it helps

Reduction loops with a short dependent chain and a long trip count, where multiple accumulators are the whole win.
Small compile-time-constant trip counts, where full unrolling removes the loop and makes every index a literal, enabling constant folding through the body.
As a preparation for vectorization and for better scheduling, where the value is entirely in what it exposes rather than in the branches removed.

When it hurts

Loops with small or highly variable trip counts, where the remainder loop and the entry test dominate.
Large bodies on any target where the instruction cache is a limiting resource — which includes essentially every embedded target and many hot server loops.
Anywhere the loop was already memory-bound: unrolling adds no memory parallelism the out-of-order core was not already extracting, and adds code size for nothing.

What it costs

Every one of these is paid by something.

Unrolling buys fewer branches and more independent instructions, and pays in code size multiplied by the factor plus a remainder loop — which converts directly into instruction-cache pressure on the hottest code in the program.
Multiple accumulators buy the removal of a latency chain and cost registers; when the count exceeds what the target has free, the allocator spills and the loop becomes memory-bound.
Unrolling more aggressively without profile data buys speed on the loops whose trip counts happen to be large and costs it on the ones that are not, which is why compilers unroll conservatively by default and why a profile changes the answer so much.

What else you could do

What a different compiler or language does instead, and when that is better.

Let the vectorizer do it: [[compiler-vectorization]] unrolls implicitly by the vector width and does so with the target's register and port counts in hand.
Software pipelining overlaps iterations rather than duplicating them, keeping code size roughly constant while still hiding latency. It is standard on VLIW and DSP targets and much harder to implement.
Restructure the algorithm so the dependence chain is not there — a tree reduction rather than a linear accumulation, for instance, which is unrolling's benefit expressed in the source.
Do nothing. On a modern core with a well-predicted loop branch and a memory-bound body, unrolling changes nothing measurable, and the honest answer is often that the loop is not where the time is — [[measure-before-optimizing]].

See it for yourself

The flag, dump or tool that shows you this directly.

Clang: -Rpass=loop-unroll and -Rpass-missed=loop-unroll report the factor chosen and the reason for each refusal.
GCC: -fopt-info-loop plus -funroll-loops to force it; -fdump-tree-cunroll-details for the complete-unroll decisions.
Measure the size cost: size on the object before and after, and perf stat -e L1-icache-load-misses to see whether the unrolled version is paying for it.
Pin the factor with #pragma clang loop unroll_count(N) and sweep N with a benchmark on the actual target — the only reliable way to choose one.
perf stat -e cycles,instructions before and after: if instructions per cycle rose, the win was instruction-level parallelism; if instruction count fell and IPC did not move, it was branch overhead.

Plausible wrong readings

Stated the way a confident engineer states them.

"Unrolling removes branches, and branches are expensive." A loop-back branch is predicted correctly nearly every iteration. The benefit that survives on modern cores is independence between the duplicated bodies, not the branches.
"More unrolling is more speed." Every factor is a code-size multiplier. There is a maximum past which the instruction cache decides the outcome, and it is reached sooner than most people expect.
"Unrolling by hand gives the compiler less to do." It usually gives the compiler a shape it recognises less well, and freezes a factor tuned for one machine into portable source.
"The compiler unrolled it, so it must be faster." It unrolled it against a cost model with an estimated trip count. Without a profile that estimate is a guess, and measuring is the only check.

Misconceptions

The claim, and what is actually true.

Unrolling is obsolete because branch predictors got good.

The branch-overhead argument is largely obsolete. The instruction-level-parallelism argument is not, and it is why unrolling a reduction with multiple accumulators still produces large speedups.

Hand-unrolling helps the compiler.

It usually hides the loop shape the vectorizer looks for and freezes a target-specific factor. Where you genuinely need it, a pragma expresses the same thing without destroying the shape.

Unrolling does not change results.

It does not, unless the compiler also splits a reduction accumulator — which changes floating-point results and is exactly why it requires permission.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

The compiler copies the loop body several times so that each pass through the loop does several iterations' worth of work. Fewer trips means fewer index updates and fewer branches, and the copies can run alongside each other on a processor that executes several instructions at once. The price is a bigger program.

practical

Do not unroll by hand and do not assume the compiler got the factor right. Check with -Rpass=loop-unroll, measure with perf stat, and if you need a specific factor use a pragma so the shape stays recognisable. For floating-point reductions, decide deliberately whether you are willing to change the result — if you are, say so locally rather than turning on fast math globally.

advanced

Unrolling is one point on a spectrum of loop restructuring that includes software pipelining and modulo scheduling. Unrolling exposes independence by duplication and pays in code size; software pipelining exposes it by overlapping the stages of consecutive iterations and pays in prologue, epilogue and register pressure instead. Which one a compiler reaches for is largely an artifact of the target: VLIW and DSP backends, which must find the parallelism statically because the hardware will not, invest heavily in modulo scheduling, while out-of-order targets get most of the same effect from the hardware's own reorder window and need only enough unrolling to fill it.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

typicalGCC and Clang unroll conservatively at -O2 and more aggressively at -O3 or with -funroll-loops, using an estimated trip count. With profile data the estimate becomes a measurement and the decisions change substantially — which is one of the largest single effects PGO has.

targetThe right factor depends on L1 instruction cache size, execution port count, operation latency and whether the core has a loop buffer that removes fetch cost for small loops. A factor tuned on a desktop x86-64 core is not transferable to a mobile AArch64 core or to an embedded target with kilobytes of instruction memory.

specSplitting a floating-point accumulator into several requires reassociation, which IEEE-754 arithmetic does not permit, so a conforming compiler will not do it without explicit permission. The integer version needs no permission because integer addition is associative — including, in C, only because the compiler is entitled to assume signed overflow does not occur.

If you were asked this in an interview

Why does unrolling still help on a core whose branch predictor gets the loop branch right every time?
Why will a compiler not split a floating-point accumulator into four when it unrolls, and what would let it?
How would you decide an unroll factor for a specific loop on specific hardware?

Connections

Computer Architectureinstruction-level-parallelism branch-prediction instruction-cache out-of-order-execution pipelining registers

Performancebenchmarking measure-before-optimizing cpu-profiling