CFGtypical

Natural Loops

The `while` was destroyed by lowering, so the optimizer has to find the loop again in the graph. A back edge `n -> h` where `h` dominates `n` is a loop; the body is `h` plus everything that reaches `n` without going through `h`. That is a definition, not a heuristic.

The question

How does a compiler find the loops in a graph after the while and for have been lowered away?

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

What the program is here

The CFG plus its dominance relation, being searched for a specific structural pattern. A natural loop is a set of blocks with a single entry — the header — such that every block in the set can reach a designated back edge and is reachable from the header. It exists to answer the question every loop optimization needs first: which blocks execute repeatedly, and which single block do they all enter through.

What this phase may assume or do

Loop detection is an analysis and changes nothing, so its legality condition is what it may assume: that the graph is *reducible*, meaning every cycle has a single entry block. Reducible graphs are what structured control flow produces, and for them the natural-loop definition finds every loop. An irreducible graph — a cycle with two entries, which goto or a machine-generated dispatch can produce — has cycles that are not natural loops, and any pass assuming otherwise will simply not optimize them, or worse, will treat one of the entries as a header and be wrong about which blocks execute repeatedly.

Key points

An edge n -> h is a back edge when h dominates n; h is the header and n is the latch.
The natural loop of a back edge is the header plus every block that reaches the latch without passing through the header — found by a backwards walk that stops at the header.
Dominance must be computed first: cycle detection finds cycles, but only dominance identifies which block is the single entry.
Nesting is recovered as set inclusion between loop bodies, so the source nesting reappears without the compiler remembering the source.
The header is where "before the loop" is, and where loop-carried phi nodes live — which is why every loop optimization needs it.
A cycle with two entries is irreducible and is not a natural loop; structured control flow cannot produce one.

The definition, and why it is a definition

An edge n -> h is a back edge when h dominates n — that is, when every path from the entry to n already passes through h. The block h is the loop header, n is the latch, and the natural loop of that back edge is h together with every block that can reach n without passing through h.

Read that last clause as a backwards search: start at the latch, walk predecessors, and stop whenever you arrive at the header. Everything you touched is in the loop. That works precisely because the header dominates the latch — any path into the loop had to come through the header, so a backwards walk that refuses to pass the header cannot escape the loop.

This is the whole reason dominance is computed before loops rather than after. Without dominance you can find cycles — that is [[cycle-detection]], and it is easy — but a cycle does not tell you which block is the entry, and every loop optimization needs the entry. Hoisting a loop-invariant computation means putting it *before the header*; that instruction has nowhere to go if you do not know which block the header is.

The loop findLoops() actually returns for while (n < 3) { ... }

b0entryentry
```
store @n, 0
store @s, 0
jump b1
```
Outside the loop. This is where a hoisted loop-invariant computation would go — the pre-header, in the standard terminology.
b1while.cond↺ loop header
```
%0 = load @n
%1 = bool %0 < 3
branch %1 ? b2 : b3
```
The header. It dominates the latch, and every entry to the loop passes through it.
b2while.bodylatch
```
... 
jump b1
```
The latch: the source of the back edge.
b3while.exit
```
%7 = load @s
print %7
ret
```
Outside. Reached from the header, not from the latch.

Edges

b0→b1
b1→b2true
b1→b3false
b2→b1back edge: b1 dominates b2

Immediate dominator

b0idomb0(entry)
b1idomb0
b2idomb1
b3idomb1

Read it asThe engine returns { header: "b1", latch: "b2", body: ["b1", "b2"] } for this function. Check the definition against the idom map: the immediate dominator of b2 is b1, so b1 dominates b2, so b2 -> b1 is a back edge. The body is b1 plus everything reaching b2 without passing b1, which is b2 itself.

Nested loops fall out for free

Run the same definition over a doubly nested loop and you get two loops, each from its own back edge, and the containment relation is simply set inclusion: the inner loop's body is a subset of the outer's.

For while (i < 3) { while (j < 3) { ... } i = i + 1; }, AtlasLang produces { header: b4, latch: b5, body: [b4, b5] } for the inner loop and { header: b1, latch: b6, body: [b1, b6, b4, b5, b2] } for the outer. The outer body contains the inner body, so the nesting the source had is recovered exactly — from the graph, with no memory of the source construct at all.

That recovery is why loop optimizations work identically on a for, a while, a goto loop, and a loop a previous pass created by unrolling something else. The optimizer never knew what the author wrote, and it does not need to.

Two loops from one nested source, as the engine reports themsimplified

Loop	Header	Latch	Body
Inner	b4 (`while.cond`)	b5 (`while.body`)	b4, b5
Outer	b1 (`while.cond`)	b6 (`while.exit` of the inner loop)	b1, b6, b4, b5, b2

What the loop is for

Nearly every loop optimization is stated in terms this analysis provides. [[loop-invariant-code-motion]] needs the header, so it knows where "before the loop" is, and it needs the body, so it can check that an operand is not redefined inside. [[loop-unrolling]] needs the latch and the exit condition. [[compiler-vectorization]] needs the body and the memory accesses inside it, and gives up on anything whose control flow it cannot flatten.

The header also matters for a reason that is easy to miss: it is where a loop-carried phi node lives. In SSA form, a variable modified in a loop needs a phi at the header merging the initial value from outside with the updated value from the latch. AtlasLang's SSA output for the loop above has exactly two: %8 = phi s [0 from b0, %4 from b2] and %9 = phi n [0 from b0, %6 from b2]. The header is the loop's single entry, which is why one phi per loop-carried variable is enough — and that is the same fact the natural-loop definition is built on.

Loop depth — how many loops a block is inside — is the standard proxy for execution frequency in cost models. A block at depth two is assumed to execute far more often than one at depth zero, which is why register allocators weight spill costs by loop depth and why inliners are more willing to inline into a loop body. That is a heuristic built directly on this analysis, and it is wrong exactly when the loop does not actually iterate — one reason [[profile-guided-optimization]] beats static heuristics when a real profile is available.

Irreducible graphs, and why they are rare

typicalMost real code is reducible, because structured control flow cannot produce anything else, and mainstream compilers handle irreducible regions by declining to optimize them rather than by miscompiling them. The exceptions are generated code — some coroutine and async lowerings, interpreter dispatch loops, and decompiler output — where irreducible graphs do occur and where the missing optimization is real. LLVM will not treat an irreducible cycle as a loop; whether a given optimization degrades gracefully or simply does nothing varies by pass.

A cycle with two entry points is irreducible: neither entry dominates the other, so neither edge into the cycle is a back edge, and the cycle is not a natural loop. Structured control flow — if, while, for, break, continue — cannot produce one. It takes a goto into the middle of a loop, a state machine written as a dispatch switch, or a machine-generated program.

Compilers handle this in one of three ways: ignore it and simply do not optimize those cycles, transform it into a reducible graph by duplicating blocks (node splitting, which can blow up code size), or use a more general loop-nesting analysis such as Havlak's that handles irreducible regions. Which one a compiler chooses is a real engineering decision and is usually invisible until somebody generates code that hits it.

For a reader, the practical consequence is small but worth knowing: if a hand-written state machine or a generated dispatch loop is unexpectedly slow, irreducibility is a candidate explanation, and restructuring it into a single-entry loop can unlock optimizations that were silently skipped.

How it works

The steps, in the order the compiler takes them.

Compute dominance over the CFG first.
For every block n and every successor h of n, test whether h dominates n. If so, n -> h is a back edge.
For each back edge, seed a set with the header, then walk backwards from the latch through predecessors, adding each block and stopping at any block already in the set.
The resulting set is the natural loop: header, latch and everything in between.
Group loops sharing a header into one loop, and order loops by body inclusion to recover the nesting.
Insert a pre-header — a block with the header as its only successor — before running any transformation that needs somewhere to place hoisted code.

How it breaks

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

Cycles are found by traversal instead of by the dominance test, and a block that is not the loop entry is treated as the header. Loop-invariant code is hoisted to a place that does not dominate all uses, and a value is read before it is computed on some path.
An irreducible region is treated as a natural loop, and the compiler reasons about "every iteration" for a cycle that can be entered at two points. Optimizations based on that reasoning are wrong on the second entry path.
Loop information is not invalidated after a transformation changes the graph, and a later pass hoists into a pre-header that no longer dominates the loop. The symptom is a wrong value in one path, appearing only at the optimization level where both passes run.
Loop depth is used as a frequency estimate for a loop that runs zero or one times, and the register allocator spends its best registers on a body that barely executes — a performance bug with no correctness symptom and no obvious cause in a profile.

When it helps

Any loop optimization at all: hoisting, unrolling, vectorization, strength reduction and induction-variable analysis all need the header, the body and the latch before they can start.
Cost modelling. Loop depth is the standard static proxy for execution frequency, and it drives inlining, spill placement and block layout decisions throughout the backend.
Explaining why an optimization did not fire on generated code. Irreducibility is a real and under-diagnosed cause of "the same loop optimizes in the hand-written version and not the generated one".

When it hurts

On irreducible graphs, where the analysis simply finds nothing and every dependent optimization silently declines. Nothing reports this; the code is just slower.
When loop depth is used as a frequency estimate and the estimate is wrong. Static heuristics assume loops iterate many times, and a loop that runs once gets optimization effort it does not repay.

What it costs

Every one of these is paid by something.

The natural-loop definition buys an exact, checkable notion of a loop that works on any reducible graph regardless of source construct, and pays by requiring a full dominance computation first.
Handling irreducible graphs by node splitting buys optimization coverage and pays in code size, since blocks are duplicated — sometimes substantially.
Caching loop information buys the many passes that need it and pays a real invalidation obligation: every transformation that changes the graph must either update or discard it, and the failure mode of forgetting is a wrong answer rather than a slow one.

What else you could do

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

Keep the source loop construct through to the optimizer, as a high-level IR does, and never need to rediscover it. rustc can reason about loops at MIR level with the loop structure still present, which is one reason a high-level IR is worth having — [[ir-levels]].
Havlak's or Steensgaard's loop-nesting algorithms, which handle irreducible regions and produce a full loop forest rather than a set of natural loops, at greater implementation cost.
Interval analysis, the older technique that partitions the graph into single-entry regions. Largely superseded by dominance-based loop finding, but still the conceptual basis for structural analysis in some tools.
Do not find loops at all: a compiler with no loop optimizations does not need this, which is a defensible choice for a fast development-build compiler where compile time is the constraint.

See it for yourself

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

opt -passes='print<loops>' file.ll prints LLVM's loop information — header, latch, exiting blocks and nesting depth — for each function.
opt -passes=loop-simplify -S file.ll shows the canonical form LLVM puts loops into before optimizing them: a dedicated pre-header, a single latch, and dedicated exit blocks.
gcc -fdump-tree-lim-details reports which computations loop-invariant motion hoisted and which it declined, which is loop detection made visible by its consequences.
GOSSAFUNC=Fname go build writes ssa.html, where the Go loop analysis results appear alongside the graph.
Our CFG viewer at /compilers/cfg highlights the back edge and shades the loop body, using findLoops() output directly.

Plausible wrong readings

Stated the way a confident engineer states them.

"A back edge is one that goes upward in the listing." It is an edge whose target dominates its source. Listing order is a printing convention and can be permuted freely without changing a single loop.
"Every cycle is a loop." Only cycles with a single entry are natural loops. An irreducible cycle is a cycle and is not a loop by this definition, which is exactly why compilers decline to optimize it.
"The loop body is everything between the header and the latch in the listing." It is everything that reaches the latch without passing the header, which is a graph property. Blocks printed in between may not be in the loop at all.
"Finding loops requires knowing the source had a loop." It requires dominance and nothing else. A loop built by a previous optimization pass is found identically to one the author wrote.

Misconceptions

The claim, and what is actually true.

The compiler knows the loop is a loop because it was a while.

By the time any optimization runs, the while is three blocks and an edge. The loop is rediscovered from the graph, which is why a goto loop optimizes identically.

Two loops sharing a header are two loops.

They are one loop with two back edges — a loop body with two continue paths, for example. Production implementations merge them; treating them separately means reasoning about "the loop" twice with two different bodies.

Loop depth tells you how often a block runs.

It is a static guess that assumes every loop iterates. It is wrong for loops that run zero or one times, which is one of the strongest arguments for using a real profile instead.

Go deeper

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

overview

After lowering there is no while left, so the compiler finds loops by looking for an edge that points back to a block guaranteed to have run first. That block is the loop entry; everything that can reach the edge without leaving through the entry is the loop body. Every loop optimization starts from those two facts.

practical

If a loop is not being optimized the way you expect, check three things in order. Is it reducible — does it have a single entry, or did a goto or a generated dispatch give it two? Does it have a clean pre-header, or is there code on the entry path that a hoist would have to move past? And is the body something the pass can handle at all, since vectorizers in particular give up on control flow inside the body. All three are visible in a CFG dump and none of them are visible in the source.

advanced

The dependence of loop detection on dominance is the reason the whole analysis order in a middle-end is what it is: dominance, then loops, then everything loop-shaped. It also means that every transformation which changes the graph invalidates both, and the cost of recomputing them is a real fraction of compile time — which is why production compilers maintain incrementally-updatable dominator trees and loop info rather than recomputing from scratch, and why the bugs in that machinery are so hard to find. A stale dominator tree does not crash; it answers a question about a graph that no longer exists, and the pass that consulted it does something subtly wrong.

How much this depends on

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

typicalThe back-edge definition of a natural loop is standard and is what LLVM, GCC and Go all use for reducible graphs. What differs between compilers is the handling of irreducible regions — decline, split, or use a more general loop forest — and the canonical form each requires before optimizing, such as LLVM's insistence on a dedicated pre-header and dedicated exit blocks.

simplifiedAtlasLang's findLoops() returns one entry per back edge and does not merge loops that share a header, nor does it build a loop forest with explicit parent links. A production implementation does both, because passes need to ask "what is the innermost loop containing this block" and set inclusion is an expensive way to answer that repeatedly.

If you were asked this in an interview

Define a back edge without using the word "backwards", then define a natural loop from it.
Why must dominance be computed before loops, rather than just detecting cycles?
What is an irreducible graph, what produces one, and what does a compiler do about it?

Connections

DSAdirected-graph cycle-detection dfs adjacency-list

Computer Architecturebranch-prediction

Performancecpu-profiling flame-graphs

Domains that do not exist yet

Testing & Reliability Engineering — Loop coverage and the difficulty of exercising zero-iteration paths
The zero-iteration case is both the most common lowering bug and the least covered path in most test suites, and the general practice of finding untested paths belongs there.