Lesson 15.7 — Canonical loop forms¶

Techniques: loop-simplify form (a preheader, a single latch, dedicated exits), loop-closed SSA (LCSSA) · Pebble implements: neither as a pass (they are LLVM's loop-simplify and lcssa, which Ch 18 runs before your loop passes); you compute what they would do with the loop-forms drill and check the result with opt · Lab: tests/ch15/lit/loop-forms.ll runs LLVM's passes on the running example · Prerequisites: Lesson 15.5 (natural loops), Ch 16 for the phi details of LCSSA (read it first if phis are new to you) · Time: 2–3 hours

A natural loop (Lesson 15.5) can have many shapes: several edges entering its header from outside, several latches, exits shared with code outside the loop. Loop optimizations would each need special cases for every shape. Instead, LLVM first puts every loop into a canonical form and every transformation assumes it. In the running example, the inner loop E is entered from both B and D, so there is no single block where LICM could hoist an invariant computation; and its exit H is also reached from C, so code sunk "after the loop" into H would also run on the C → H path. The outer loop B is already canonical.

flowchart TD
  A([A]) --> B[B]
  B --> C[C]
  B --> EP[E.preheader]
  C --> D[D]
  C --> H[H]
  D --> EP
  EP --> E[E]
  E --> F[F]
  E --> HX[H.loopexit]
  F --> G[G]
  G --> HX
  G --> E
  HX --> H
  H --> I[I]
  H --> B
  classDef hl fill:#fde68a,stroke:#b45309;
  class EP,HX hl;

(The running example after loop-simplify; the two new blocks are highlighted.)

1. Problem and motivation¶

The problem. Transform the CFG, without changing its behavior, so that every natural loop \(L\) has (1) a preheader: a block outside \(L\) whose only successor is the header and which is the header's only predecessor outside \(L\); (2) a single latch (one back edge); (3) dedicated exits: every exit block has only predecessors inside \(L\). Then (4), in SSA form, rewrite every value defined inside \(L\) and used outside it so that it flows through a phi in an exit block (LCSSA). LICM, loop unrolling, unswitching, vectorization and SCEV-based rewriting in LLVM all require (1)–(3), and most require (4); Ch 18's pebble-licm does too.

Loop-simplify form¶

The preheader is the classical landing pad for code motion: code hoisted out of a loop needs a block that runs once, just before the loop, on every entry path. FORTRAN H's optimizer already moved invariant code into such a block [LM69], and the dragon book formalizes preheaders together with natural loops [Dragon2 §9.6.6]. A single latch gives one place to put the increment and one back edge to reason about; dedicated exits give one place for code that must run after the loop and only then. LLVM bundles the three into "loop-simplify form" and enforces it with the LoopSimplify pass [LLVM-LoopTerm, LLVM-LoopSimplify].

LCSSA¶

In SSA form, a value defined in a loop can be used anywhere it dominates, including far after the loop. A transformation that changes the loop (unrolling duplicates the definition; unswitching clones the loop) must then find and fix every such use. Loop-closed SSA requires that every such use go through a phi in an exit block, so all uses outside the loop are those phis. The form appeared in GCC's tree-SSA loop optimizer (rewrite_into_loop_closed_ssa) [GCC-LCSSA] and in LLVM's LCSSA pass [LLVM-LCSSA]; it has no single origin paper, and the definitive descriptions are LLVM's loop terminology document [LLVM-LoopTerm] and GCC's internals manual [GCC-LoopDoc].

2. Definitions and algorithms¶

\(L\) is a natural loop with header \(h\) (Definition 15.5.4).

Definition 15.7.1 (Entering block, preheader)

An entering block of \(L\) is a predecessor of \(h\) outside \(L\). The preheader is the unique entering block, if there is exactly one and its only successor is \(h\) (Loop::getLoopPreheader).

Definition 15.7.2 (Latch, exiting block, exit block, dedicated exit)

A latch is a predecessor of \(h\) inside \(L\); latch \(\to h\) is a back edge. An exiting block is a block of \(L\) with a successor outside \(L\); that successor is an exit block. An exit block is dedicated if all its predecessors are in \(L\) (Loop::hasDedicatedExits).

Definition 15.7.3 (Loop-simplify form)

\(L\) is in loop-simplify form if it has a preheader, exactly one latch, and dedicated exits (Loop::isLoopSimplifyForm) [LLVM-LoopInfoCpp].

Definition 15.7.4 (LCSSA)

\(L\) is in loop-closed SSA form if for every instruction \(I\) in \(L\), every use of \(I\) outside \(L\) is a phi in an exit block of \(L\). A phi's use of a value counts as a use at the end of the incoming block (LangRef semantics), so phi [%v, %latch] in the header is a use inside the loop.

Lemma 15.7.5 (Splitting edges preserves behavior and loops)

Redirect a set \(Q\) of edges \(p \to s\) (all with the same target \(s\)) to a fresh block \(s'\) with the single edge \(s' \to s\), moving the phi operands of \(s\) for the predecessors in \(Q\) into a phi in \(s'\) (or keeping them, if \(\lvert Q \rvert = 1\)). Then every execution of the old function corresponds to exactly one execution of the new one with the same computations, and every natural loop of the old CFG corresponds to a natural loop of the new CFG with the same header and the same old blocks, plus \(s'\) exactly when \(s'\) reaches one of its latches without passing its header.

Proof

A path of the old CFG using an edge \(p \to s\) with \(p \in Q\) maps to the path using \(p \to s' \to s\), and conversely every new path through \(s'\) comes from such a path; paths not using \(Q\) are unchanged. \(s'\) computes nothing except, possibly, a phi that selects the same operand the old phi in \(s\) would have selected for the incoming edge, and the phi in \(s\) now receives that value from \(s'\); so every execution computes the same values. For loops: paths correspond one-to-one, so an old node reaches a latch avoiding the header in the new CFG iff it did in the old one (a latch \(p \in Q\) of header \(s\) is replaced by the latch \(s'\), which every redirected path passes), and dominance between old nodes is unchanged; \(s'\) belongs to a loop exactly under the stated condition.

Loop-simplify form¶

Algorithm 15.7.6 (LoopSimplify)

Input: a function with LoopInfo and DominatorTree.
Output: every loop in loop-simplify form, with the analyses updated.
Precondition: no indirectbr edge has to be split (such loops are left alone).
Postcondition: every loop satisfies Definition 15.7.3, and the function's behavior is unchanged (Lemma 15.7.5).
Invariant: when SimplifyOneLoop(L) starts, every loop nested inside \(L\) is already in loop-simplify form, and splits made for \(L\) put the new blocks in the loops that contain them (Theorem 15.7.9).

function SimplifyLoop(L):
    worklist ← L and all its subloops in breadth-first order
    while worklist not empty:
        SimplifyOneLoop(pop the last loop of worklist)   # innermost loops first

function SimplifyOneLoop(L):
    for each block b ≠ header(L) of L with a predecessor outside L:
        # only possible if that predecessor is unreachable: delete those edges
        replace the predecessor's terminator by `unreachable`
    if L has no preheader:
        InsertPreheader(L)
    FormDedicatedExits(L)
    if L has more than one latch:
        if fewer than 8 back edges and SeparateNestedLoop(L) succeeds:
            restart with the new outer loop
        else:
            InsertUniqueBackedgeBlock(L)
    simplify header phis that became trivial

function InsertPreheader(L):
    P ← new block "h.preheader"
    redirect every entering edge p → h to p → P      # SplitBlockPredecessors
    for each phi of h: move the entering incoming values into a new phi in P
    add P → h; P joins the parent loop of L (if any)

function FormDedicatedExits(L):
    for each exit block X of L with a predecessor outside L:
        X′ ← new block "X.loopexit"
        redirect every edge from inside L to X through X′
        move the corresponding incoming values of X's phis into phis of X′

function InsertUniqueBackedgeBlock(L):
    B ← new block "h.backedge"
    redirect every latch → h to latch → B; add B → h
    for each phi of h: merge the latch incoming values into a phi in B

function SeparateNestedLoop(L):
    # if a header phi shows that some back edges really form an inner loop
    # (FindPHIToPartitionLoops), split the header: those latches keep the
    # old header, which becomes an inner loop's header, and a new outer
    # header receives the entering edges and the other latches

This mirrors simplifyLoop and simplifyOneLoop in llvm/lib/Transforms/Utils/LoopSimplify.cpp (LLVM 23.1.2) [LLVM-LoopSimplify]. The Python oracle loop_simplify_report computes what the steps would do.

LCSSA¶

Lemma 15.7.7 (An exit phi is always valid)

Let \(L\) have dedicated exits, \(I\) an instruction in block \(d \in L\), and \(X\) an exit block with \(d \mathrel{\mathrm{dom}} X\). Then \(d\) dominates every predecessor of \(X\), so phi [I, P] for all predecessors \(P\) of \(X\) is valid SSA.

Proof

Let \(P\) be a predecessor of \(X\) (in \(L\), by dedicated exits). Every path \(r \leadsto P\) extended by \(P \to X\) is a path to \(X\), so it contains \(d\), and not as its last node \(X\) (\(d \in L\), \(X \notin L\)): \(d \mathrel{\mathrm{dom}} P\). So \(I\) is available at the end of \(P\) (if \(d = P\), \(I\) precedes the terminator), which is where a phi operand is used (Definition 15.7.4).

Algorithm 15.7.8 (FormLCSSA)

Input: a loop \(L\) with dedicated exits, DominatorTree, LoopInfo.
Output: \(L\) in LCSSA (and, with formLCSSARecursively, its subloops).
Precondition: \(L\) has dedicated exits (loop-simplify form provides them); the function is in valid SSA.
Postcondition: Definition 15.7.4 holds for \(L\), and the function computes the same values (Theorem 15.7.10).
Invariant: every phi inserted so far is valid (Lemma 15.7.7) and has \(I\) as its incoming value on every edge.

function FormLCSSA(L):
    exits ← the exit blocks of L
    for each instruction I in L:
        outside ← the uses U of I whose block is outside L, where a phi use counts in
                  its incoming block; uses in unreachable blocks are ignored
        if outside is empty: continue
        phis ← {}
        for X in exits:
            if block(I) does not dominate X: continue    # I is not available at X
            PN ← new phi "I.lcssa" at the start of X
            for each predecessor P of X: add incoming (I, P)   # all P are in L
            phis[X] ← PN
        for U in outside:
            if U is in an exit block X with phis[X]: rewrite U to use phis[X]
            else: rewrite U with SSAUpdater, using phis as the available definitions
                  (this may create further phis where exit paths merge)

This mirrors formLCSSAForInstructions in llvm/lib/Transforms/Utils/LCSSA.cpp [LLVM-LCSSA]. The Python oracle is lcssa_phi_blocks.

3. Worked example¶

The running example as IR, with an outer induction variable %i and an inner one %j (tests/ch15/lit/loop-forms.ll):

define i32 @running(i1 %c, i32 %n) {
A:
  br label %B
B:
  %i = phi i32 [ 0, %A ], [ %i.next, %H ]
  br i1 %c, label %C, label %E
C:
  br i1 %c, label %D, label %H
D:
  br label %E
E:
  %j = phi i32 [ 0, %B ], [ 1, %D ], [ %j.next, %G ]
  br i1 %c, label %F, label %H
F:
  br label %G
G:
  %j.next = add i32 %j, 1
  %more = icmp slt i32 %j.next, %n
  br i1 %more, label %H, label %E
H:
  %i.next = add i32 %i, 1
  br i1 %c, label %I, label %B
I:
  ret i32 %i.next
}

Loop-simplify form on the running example¶

The loops, innermost first:

loop	entering blocks	preheader?	latches	exit blocks (preds)	dedicated?
E =	B, D	no (two entering blocks)	G	H (C, E, G)	no (C is outside)
B =	A	yes: A (A → B only)	H	I (H)	yes

simplifyOneLoop(E), then simplifyOneLoop(B):

step	loop	action	CFG change	phis
1	E	no dead out-of-loop predecessors	—	—
2	E	no preheader → `InsertPreheaderForLoop`	new block E.preheader; B → E.preheader, D → E.preheader, E.preheader → E	`%j.ph = phi [1, %D], [0, %B]` in E.preheader; `%j = phi [%j.next, %G], [%j.ph, %E.preheader]`
3	E	exit H has predecessor C outside → `formDedicatedExitBlocks`	new block H.loopexit; E → H.loopexit, G → H.loopexit, H.loopexit → H	(no phis in H)
4	E	one latch (G): nothing to do	—	—
5	B	preheader A exists; exit I dedicated; one latch H: nothing to do	—	—

This is exactly what opt -passes=loop-simplify prints for the function (the lit test checks the block names and the new phi).

LCSSA on the running example¶

After loop-simplify, scan every instruction for uses outside its loop:

instruction	defined in (loop)	uses outside that loop	exit blocks dominated by the definition	LCSSA phis inserted	uses rewritten
%i	B (loop B)	— (used in H, inside)	—	—	—
%j.ph	E.preheader (loop B)	—	—	—	—
%j	E (loop E)	— (used in G, inside)	—	—	—
%j.next	G (loop E)	— (its phi use in E counts as a use in G)	—	—	—
%more	G (loop E)	—	—	—	—
%i.next	H (loop B)	`ret` in I	I (H dominates I)	`%i.next.lcssa = phi [%i.next, %H]` in I	`ret i32 %i.next.lcssa`

Only one LCSSA phi is needed. If instead a value defined in C were used after the loop, no phi could go into I, because C does not dominate I: such a use would already have been invalid SSA.

Try it

./course drill loop-forms --seed 6 --difficulty hard --solution asks for preheaders, latches, non-dedicated exits and LCSSA phi blocks of a random CFG, and prints what LoopSimplify and formLCSSA would do.

4. Invariants and correctness¶

Loop-simplify form¶

Theorem 15.7.9 (Correctness of LoopSimplify)

Algorithm 15.7.6 terminates; afterwards every loop is in loop-simplify form, and the function computes the same values.

Proof

Behavior: every step is an edge split of Lemma 15.7.5 (or the deletion of edges from unreachable blocks, which no execution takes), so behavior is preserved. Each step establishes its property. InsertPreheader redirects all entering edges to \(P\), whose only successor is \(h\): \(P\) is the unique entering block with \(h\) as its only successor, a preheader (Definition 15.7.1). FormDedicatedExits gives each shared exit \(X\) a new block \(X'\) whose predecessors are exactly the in-loop predecessors of \(X\): \(X'\) is a dedicated exit, and \(X\) is no longer an exit of \(L\). InsertUniqueBackedgeBlock makes \(B\) the only in-loop predecessor of \(h\): one latch. SeparateNestedLoop turns a subset of the back edges into the back edges of a new inner loop, so both loops have fewer latches than before. Earlier properties survive. The new blocks are inserted into the loops that contain them (Lemma 15.7.5): a preheader of \(L\) joins \(L\)'s parent, where it is an ordinary body block; a dedicated exit of \(L\) joins the loops containing both its predecessors and its successor. Inner loops are processed first. A split made for an outer loop redirects only edges that enter, leave or close the outer loop; such an edge can also be an exit edge of an inner loop (when both share an exit), and then the new block lies outside the inner loop, whose exits stay dedicated; it is never an entering or back edge of an inner loop, whose header is inside the outer loop. Termination: each step removes one violation (entering edges, a non-dedicated exit, extra latches) and creates no new one in the same loop; SeparateNestedLoop increases the number of loops, which is bounded by the number of back edges.

Why innermost first: a preheader for an inner loop becomes part of the outer loop's body; handling the outer loop first could require re-splitting. When it breaks: indirectbr edges cannot be split, so LoopSimplify leaves such loops non-canonical (the LCSSA code comments on this case); passes must check L->isLoopSimplifyForm().

LCSSA¶

Theorem 15.7.10 (Correctness of FormLCSSA)

After Algorithm 15.7.8, \(L\) is in LCSSA, the SSA form is valid, and the function computes the same values.

Proof sketch (the SSA-reconstruction step is Ch 16's algorithm; full proof: [SSAB, Ch. 3])

Valid phis: Lemma 15.7.7. Same values: every inserted phi has \(I\) on every incoming edge, so it evaluates to \(I\)'s current value. Every outside use is reached through an exit phi: a use \(U\) outside \(L\) is dominated by \(I\)'s block \(d\) (valid SSA). Take any path \(\pi : r \leadsto U\) and the first exit block \(X\) on \(\pi\) after the last occurrence of \(d\). If some path \(r \leadsto X\) avoided \(d\), it followed by the suffix of \(\pi\) from \(X\) (which contains no \(d\)) would reach \(U\) avoiding \(d\). So \(d \mathrel{\mathrm{dom}} X\), and \(X\) received a phi; between \(X\) and \(U\) the path does not pass \(d\) again. Rewriting \(U\) is therefore an SSA reconstruction with the phis as the definitions of one variable: SSAUpdater inserts the merge phis where two exits' paths meet, exactly as phi placement does for a variable with those definition blocks (Theorem 15.3.10). Termination: finitely many instructions and uses; SSAUpdater inserts at most one phi per block.

When it breaks: without dedicated exits, an exit block could be entered from outside \(L\), where \(I\) is undefined (LLVM then feeds that edge from a different LCSSA phi or poison); tokens cannot be phi-ed (the IgnoreTokens option of isLCSSAForm).

5. Complexity¶

\(n\) = blocks, \(m\) = edges, \(\ell\) = number of loops, \(e\) = exit blocks of a loop, \(u\) = uses outside loops, \(v\) = values live out of a loop.

Technique	Time (worst)	Time (typical)	Space	Notes
Loop-simplify form	\(O(\ell \cdot (n + m))\) plus DomTree/LoopInfo updates	near-linear	\(O(n)\) new blocks	each split updates DominatorTree incrementally (Lesson 15.2)
LCSSA	\(O(u \cdot e + \text{SSAUpdater})\)	linear in outside uses	one phi per (value, dominated exit)	SSAUpdater is \(O(n)\) per value in the worst case

Proposition 15.7.11 (Cost and blow-up of the canonical forms)

(a) One call of SimplifyOneLoop creates at most \(e + 2\) blocks and touches \(O(n + m)\) edges. (b) LCSSA inserts at most \(v \cdot e\) exit phis before SSAUpdater, and this bound is attained.

Proof

(a) At most one preheader, one backedge block, and one new block per exit; each step scans the loop's blocks and edges once. (b) Each live-out value gets at most one phi per exit block (Algorithm 15.7.8). Attained: a loop computing \(v\) values with a switch to \(e\) distinct exit blocks, each of which uses all \(v\) values and is dominated by the loop's header block where the values are computed, gets exactly \(v \cdot e\) phis; for \(v = e = 32\) that is 1 024 phis.

Pathological input: the switch loop of Proposition 15.7.11(b). LoopSimplify's worst case is a header with many back edges: separateNestedLoop is attempted only below 8 back edges; above that, a single backedge block merges them all.

At scale: LoopSimplify and LCSSA run many times per function in LLVM's -O2 pipeline (every loop pass manager invocation requires them), which is why both update DominatorTree, LoopInfo, ScalarEvolution and MemorySSA incrementally instead of invalidating them (the DT, LI, SE, MSSAU parameters of simplifyLoop and formLCSSA).

Loop-simplify form¶

Loop rotation (LLVM LoopRotate, llvm/lib/Transforms/Utils/LoopRotationUtils.cpp, LoopRotate::rotateLoop) [LLVM-LoopRotate]: turns while (c) body into if (c) do body while (c) by copying the header into the preheader — trade-off: the latch becomes the only exiting block (ideal for trip-count analysis and LICM), at the cost of duplicating the header's instructions.
Separating nested loops vs a backedge block (separateNestedLoop vs insertUniqueBackedgeBlock) — trade-off: exposing a real inner loop gives better optimization, but only works when a header phi reveals the nesting.
GCC's loops state (gcc/cfgloop.h, flags such as LOOPS_HAVE_PREHEADERS) — trade-off: passes request only the properties they need and GCC creates them on demand (create_preheaders), instead of one canonical form for everyone.

LCSSA¶

GCC's loop-closed SSA (gcc/tree-ssa-loop-manip.cc, rewrite_into_loop_closed_ssa) [GCC-LCSSA] — trade-off: the same form, created with GCC's generic SSA renamer.
LCSSA for a subset of instructions (formLCSSAForInstructions with a worklist) — trade-off: cheaper when a transform only needs some values closed.
Block arguments instead of phis (MLIR, Swift SIL): region or loop results are explicit, so "loop-closed" is built into the IR — trade-off: no separate pass, but every transformation must thread results explicitly.

7. In real compilers¶

Loop-simplify form¶

LLVM

llvm/lib/Transforms/Utils/LoopSimplify.cpp — simplifyLoop, simplifyOneLoop, llvm::InsertPreheaderForLoop, insertUniqueBackedgeBlock, separateNestedLoop [LLVM-LoopSimplify]; llvm/lib/Transforms/Utils/LoopUtils.cpp — llvm::formDedicatedExitBlocks; llvm/lib/Analysis/LoopInfo.cpp — Loop::isLoopSimplifyForm (preheader, latch and dedicated exits) [LLVM-LoopInfoCpp]. Documented in llvm/docs/LoopTerminology.md, "Loop Simplify Form" (LLVM 23.1.2) [LLVM-LoopTerm].

GCC 15 gcc/cfgloopmanip.cc — create_preheader/create_preheaders and force_single_succ_latches; gcc/cfgloop.h records which canonical properties currently hold in the loops state (LOOPS_HAVE_PREHEADERS, LOOPS_HAVE_SIMPLE_LATCHES, combined in LOOPS_NORMAL).

Two latches become two loops: separateNestedLoop at work

Reproduce (clang 23.1.2, opt 23.1.2):

cat > skip.c <<'EOF'
int skip(int *a, int n) {
  int i = 0, s = 0;
  while (i < n) {
    if (a[i] < 0) {
      i++;
      continue;
    }
    s += a[i];
    i++;
  }
  return s;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm skip.c -o skip.ll
opt -passes='sroa,print<loops>,loop-simplify,print<loops>' -disable-output skip.ll
opt -passes='sroa,loop-simplify' -S skip.ll | grep -E '^[a-z.]+:|= phi|^  br'

Output (complete; the two print<loops> blocks come first, then the IR filtered by the grep):

Loop info for function 'skip':
Loop at depth 1 containing: %while.cond<header><exiting>,%while.body,%if.end<latch>,%if.then<latch>
Loop info for function 'skip':
Loop at depth 1 containing: %while.cond.outer<header>,%while.body,%if.end<latch>,%if.then,%while.cond<exiting>
    Loop at depth 2 containing: %while.cond<header><exiting>,%while.body<exiting>,%if.then<latch>
entry:
  br label %while.cond.outer
while.cond.outer:                                 ; preds = %if.end, %entry
  %i.0.ph = phi i32 [ %inc4, %if.end ], [ 0, %entry ]
  %s.0.ph = phi i32 [ %add, %if.end ], [ 0, %entry ]
  br label %while.cond
while.cond:                                       ; preds = %while.cond.outer, %if.then
  %i.0 = phi i32 [ %inc, %if.then ], [ %i.0.ph, %while.cond.outer ]
  br i1 %cmp, label %while.body, label %while.end
while.body:                                       ; preds = %while.cond
  br i1 %cmp1, label %if.then, label %if.end
if.then:                                          ; preds = %while.body
  br label %while.cond, !llvm.loop !5
if.end:                                           ; preds = %while.body
  br label %while.cond.outer, !llvm.loop !5
while.end:                                        ; preds = %while.cond

What to notice: before loop-simplify the while loop has two latches (if.then from continue, and if.end), so it is not in loop-simplify form (Definition 15.7.3). Instead of merging them in a while.cond.backedge block, simplifyOneLoop found a header phi (s) whose value is unchanged along the continue edge — FindPHIToPartitionLoops — and called separateNestedLoop: the new outer header while.cond.outer takes the entry edge and the if.end latch (with the phis %i.0.ph, %s.0.ph), and the old header becomes an inner loop with the single latch if.then. Both loops now have one latch; entry is the outer preheader, while.cond.outer the inner one, and while.end is a dedicated exit of both.

LCSSA¶

LLVM

llvm/lib/Transforms/Utils/LCSSA.cpp — llvm::formLCSSAForInstructions (the per-instruction exit-phi insertion, DT.dominates(DomNode, DT.getNode(ExitBB)), then SSAUpdater), llvm::formLCSSA, llvm::formLCSSARecursively [LLVM-LCSSA]; llvm/lib/Analysis/LoopInfo.cpp — Loop::isLCSSAForm, Loop::isRecursivelyLCSSAForm (LLVM 23.1.2) [LLVM-LoopInfoCpp].

GCC 15 gcc/tree-ssa-loop-manip.cc — rewrite_into_loop_closed_ssa and rewrite_into_loop_closed_ssa_1 [GCC-LCSSA].

An exit phi for a value used after the loop

Reproduce (clang 23.1.2, opt 23.1.2):

cat > last.c <<'EOF'
int last_neg(int *a, int n) {
  int pos = -1;
  for (int i = 0; i < n; i++)
    if (a[i] < 0)
      pos = i;
  return pos + 1;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm last.c -o last.ll
opt -passes='sroa,loop-simplify' -S last.ll | sed -n '/^for.end:/,/^}/p'
opt -passes='sroa,loop-simplify,lcssa' -S last.ll | sed -n '/^for.end:/,/^}/p'

Output (complete; the exit block before and after lcssa):

for.end:                                          ; preds = %for.cond
  %add = add nsw i32 %pos.0, 1
  ret i32 %add
}
for.end:                                          ; preds = %for.cond
  %pos.0.lcssa = phi i32 [ %pos.0, %for.cond ]
  %add = add nsw i32 %pos.0.lcssa, 1
  ret i32 %add
}

What to notice: %pos.0 is the header phi of the loop and is used after it by the add. LCSSA inserts %pos.0.lcssa = phi [ %pos.0, %for.cond ] in the dedicated exit for.end — one operand per predecessor, all equal to the value (Algorithm 15.7.8) — and rewrites the outside use. The phi is valid because for.cond dominates for.end (Lemma 15.7.7). A pass that later clones or unrolls the loop only has to patch this phi, not every use after the loop.

Find where LLVM does it. Open llvm/lib/Transforms/Utils/LCSSA.cpp (LLVM 23.1.2) and find the function that inserts the exit-block phis for a worklist of instructions. Question: what is its name? (Quiz llvm-where-lcssa.) Then open llvm/lib/Analysis/LoopInfo.cpp and read Loop::isLoopSimplifyForm: which three properties does it check?

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Loop-simplify form	canonical shape for every natural loop	O(n + m) per loop, plus DomTree/LoopInfo updates	new preheader / latch / exit blocks	`LoopSimplify.cpp` is ~900 lines	before LICM, unrolling, vectorization
LCSSA	every loop-defined value used outside flows through an exit phi	O(uses · exits)	`.lcssa` phis in exit blocks	`LCSSA.cpp` is ~550 lines (plus `SSAUpdater`)	before loop transforms, SCEV rewriting

Choose loop-simplify form when a transformation moves code into or out of a loop, or needs one back edge (every LLVM loop pass declares it as a requirement). Choose LCSSA when a transformation rewrites or duplicates a loop's definitions: with LCSSA, fixing all outside uses means fixing the exit phis only. Rotation is the next step when trip counts and hoisting matter.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch15.yaml`)	Drill	Flashcard tag	Exercises
Loop-simplify form	`loop-simplify-shape`, `lcssa-phis`, `llvm-where-lcssa`	`./course drill loop-forms --difficulty medium`	`loop-simplify`	lit test `tests/ch15/lit/loop-forms.ll` (read it; no code to write)
LCSSA	`lcssa-phis`, `llvm-where-lcssa`	`./course drill loop-forms --difficulty hard`	`lcssa`	same lit test

A phi uses its operand in the incoming block

A phi's use of a value happens in the incoming block, not in the phi's own block. %j = phi [%j.next, %G], … in the header E uses %j.next in G, inside the loop, so it needs no LCSSA phi; forgetting this rule makes LCSSA insert phis for every loop-carried value.

References¶

See the chapter references.

Lesson 15.7 — Canonical loop forms¶

1. Problem and motivation¶

Loop-simplify form¶

LCSSA¶

2. Definitions and algorithms¶

Loop-simplify form¶

LCSSA¶

3. Worked example¶

Loop-simplify form on the running example¶

LCSSA on the running example¶

4. Invariants and correctness¶

Loop-simplify form¶

LCSSA¶

5. Complexity¶

6. Variants and refinements¶

Loop-simplify form¶

LCSSA¶

7. In real compilers¶

Loop-simplify form¶

LCSSA¶

8. Comparison¶

9. Assessment¶

References¶