Design walkthrough for llvm/llvm-project PR #224196: LoopInterchange, extract statically bounded outer epilogues

pr224196-design-walkthrough.md

LoopInterchange: extract statically bounded outer epilogues

#224196 | 35703509 NFC helpers | 11bcd2fa preparation | c0ec2d79 apply

Context: Improving the SPECfp2000/SWIM2000 benchmark performance for Flang.

Background: SPEC CPU2000 171.swim does not interchange under Flang/LLVM (related earlier work & comment: sebpop reported that it did not interchange under Flang because LLVM could not infer the number of iterations). #199511 ("[LoopInterchange] Supported partially-perfect Loop Nests") then landed the candidate-chain routing that lets the pass reach a parent loop and its leaf child inside a larger loop tree, the blocker that #214920 had targeted.

This patch addresses the next blocker in the same benchmark: the checksum nest ends each outer iteration with a small epilogue after the inner loop, so it is not tightly nested. The patch distributes such an epilogue into its own loop and interchanges the remaining nest when the outer trip bound is proved at compile time. The benchmark's own nest has a runtime bound and stays unchanged here. The runtime-versioning follow-up handles it. Section 5 states what remains.

Patch symbols live in LoopInterchange.cpp and LoopInterchangeUtils.h. Named test cases are checksum_diagonal_epilogue, flattened_byte_gep_latch, checksum_kernel_rect, bound_runtime_canonical, and issue47457_guarded_epilogue.

1. Problem

LoopInterchange rejects an otherwise profitable reduction nest when each outer iteration ends with a small, ordered epilogue, even when distributing that epilogue would leave a legal perfect nest.

The motivating shape is the SWIM checksum:

for i:
  for j:
    check += A[j][i]       // N: reduction nest, 10,680-byte inner stride
  A[i][i] = f(A[i][i])     // E: one post-inner epilogue update

The epilogue makes the nest imperfect, so the existing pass cannot reach the interchange that makes the first Fortran subscript unit stride. A source-level experiment that distributes E and interchanges N cuts the runtime by 37.7% without reassociation flags and by 41.2% with them: Flang from LLVM main at 943d6498fabf (LLVM 24 development, 2026-07-25) went from 14.14 s to 8.81 s strict and 8.32 s reassociated on AMD EPYC 9654 (Zen 4). These are within-workload mechanism measurements, not reportable SPEC results. The rewrite changes the reduction order, so the compiler path requires reassociation permission. Strict -O3 stays unchanged.

The patch does not teach LLVM a Fortran or SWIM pattern. It adds a narrow, dependence-proved outer-epilogue capability to LoopInterchange, off by default.

Two separate obstructions block the motivating interchange on the landed base. The existing legality analysis cannot prove one of the nest's dependences, and this series does not change that analysis. The nest is also not tightly nested. This series removes the second obstruction for epilogues whose bounds can be proved statically. "Static" means the pass implements both the analysis and the CFG transformation when LLVM can prove at compile time that the selected outer trip count does not exceed the recovered row stride W. For the 171.swim checksum nest as Flang lowers it (flattened byte GEPs), the series recovers the row stride W=1335, proves the dependence, and passes the ordinary legality and profitability checks. It cannot prove at compile time that the runtime outer trip count is at most 1335, so preparation produces a complete RuntimeBound plan, the pass emits a missed remark, and the loop stays unchanged. Runtime versioning of that nest is a follow-up patch, whose pre-#199511 implementation still has to be ported onto this series.

Relation to upstream work: #199511 (landed, base of this series) is adjacent work that supplies the candidate-chain routing the preparation reuses; #47457 is the outer-epilogue miscompile shape from 2020 and is covered by a regression test that expects its rejection (§5); #214920 is the still-open, superseded broader candidate-routing PR, to be reduced to its independent 64-bit memory-ratio overflow correction.

2. Position in the compilation pipeline

The production change is in LLVM's scalar LoopInterchange implementation. Checked arithmetic lives in the new private LoopInterchangeUtils.h, with direct LoopInterchangeTest.cpp coverage: INT64_MIN absolute value, wide zero-extension, and containment overflow cannot be reached from IR without undefined behaviour or an earlier rejection. Flang contributes only ordinary LLVM IR and schedules LoopInterchange through its existing driver option. There is no Fortran semantic, FIR, HLFIR, MLIR, SelectionDAG, or target-backend change.

The series lands as three commits so that each is reviewable on its own: the NFC helpers and their unit tests; the analysis-only preparation behind -loop-interchange-outer-epilogue-fission (off by default), with the hidden candidate budget and the plan printer, whose option-on IR is identical to the option-off IR for every test case; and the apply step.

The architecture has two deliberately separate stages:

1. prepareInterchangeWithOuterEpilogue discovers E, proves distribution and interchange legality, resolves the array-bound requirements, and records a complete plan without mutating IR or analyses.
2. applyPreparedInterchange consumes only a StaticBound plan, materializes E as a sibling loop, and performs the already-decided interchange as one infallible transaction.

Everything else is wiring. LoopInterchange::run(LoopNest &, LPMUpdater &) is small: correctness is established before the first CFG edit. It runs fission over the same direct parent/leaf-child candidates that #199511's collectPerfectNests hands to the standard path, re-validates the selected plan, applies it, and otherwise falls through to the existing routing unchanged.

3. Design rationale

3.1 Extend LoopInterchange, not a general distribution pass

The selected shape needs both distribution and interchange, but the reviewable unit is not a new general fission framework. LoopInterchange already owns the reduction legality, dependence matrix, flag dropping, profitability, and LoopInfo/SCEV update contracts needed after E is removed.

The rejected alternative was to broaden LoopDistribute or add a source/FIR transform. General distribution would have to define a much larger profitability and legality surface, while a source-specific transform would lose the IR-level generality needed upstream. The patch instead accepts only a direct parent and leaf child with one dominated, acyclic, unconditional path from the inner exit to the outer latch (discoverDistributableOuterEpilogue).

3.2 Prove virtually, validate before printing and before mutating, mutate once

DistributableOuterEpilogue records the exact E slice, its outer-IV-derived rematerializations, and the outer control needed by a sibling loop. PreparedInterchangePlan adds the two dependence matrices (§3.3), the existing interchange legality and profitability decisions, and the recovered bound classification.

The rejected alternative was mutation followed by rollback. Once blocks, sibling loops, LCSSA, and SCEV state have changed, rollback is another compiler transformation with its own failure modes. A fission-only success would also be wrong for this patch: the performance case requires the interchange. Therefore preparation is complete and non-mutating, while apply is void and asserts that every supposedly impossible state was excluded.

Preparation ends in a pure validation step, validatePreparedPlan, which re-derives every recorded structural field from the loops without an analysis query, requires the recorded legality and profitability decisions to be set, checks the stored matrices and requirements for internal consistency, and rejects a mismatch. It runs before a plan is printed or selected, so a printed prepared-plan line describes a plan that has already passed, and again immediately before the first mutation. A failure at the second call is an internal inconsistency: an assertions build asserts, and a release build bails out before any mutation, leaving the function unchanged and emitting the missed-optimization remark with a fixed reason string. The validator checks the convergence property (§3.6) with the predicate used in preparation, not a second implementation, so the two checks stay identical. The recheck is unreachable by any IR input: every committed negative already stops at the preparation-time predicate, and the IR is unchanged between preparation and validation. It is a defensive consistency check, not a rejection path.

3.3 Two dependence matrices after #199511's candidate-chain routing

On the pre-#199511 base a candidate was a linear loop list, and one dependence matrix served both fission and interchange. The landed routing collects candidate chains whose interchange legality is judged over a projected selected subnest (DependenceColumns::SelectedSubnest), while the fission proof needs the absolute ancestry of the selected outer, including ancestors outside the current LoopNest root (buildCandidateAncestorChain). Preparation therefore builds two matrices over the same ExtractedEpilogueView that hides E (construction): the fission context matrix over AbsoluteAncestors, which must satisfy hasDecisiveOrEqualAncestorPrefix (every enclosing dimension decides a row forward or leaves it equal before the selected outer), and the routing matrix over the collected chain's projected subnest, which feeds the unchanged canInterchangeLoops and profitability.

The rejected alternative was to project one matrix into the other. The source comment records the reason: "Ordinary legality and profitability need the collected chain's row domain and suffix projection, not a projection of the fission matrix." A projection of the absolute matrix drops rows the routing domain must see, and a projection of the routing matrix has no column for an ancestor outside the nest root, so a surrounding dependence that forbids moving E could go unexamined. The cross-partition proof (§3.4) uses neither matrix.

3.4 Never accept an unknown dependence by name

DependenceAnalysis reports the column read and the diagonal write as anti [*|<]. Treating * as loop independent would be unsound. For sufficiently large trips, an E iteration can alias a later N iteration.

The patch first rejects unordered, confused, reversed, runtime-assumed, or wrongly directed dependences in proveNestToEpilogueDependences. It queries the raw nest-to-epilogue dependences and keeps their unnormalized direction, because normalization can reverse the endpoints and cannot establish the required nest-then-epilogue order. An ALL direction at the selected outer level is accepted only if one exact byte-offset proof establishes same-outer aliasing. It collects each GEP chain into checked signed 64-bit affine byte coefficients (collectExactGEPByteOffset), normalizes them by element size exactly once, recovers W from N's normalized inner coefficient, requires N's unit outer and +/-W inner coefficients, and then checks the modular relation plus a separately bounded storage range. Typed [W x T] GEPs and flattened getelementptr i8 are only two spellings of the same address arithmetic.

The rejected alternative recovered W from ArrayType and required a particular two-index GEP shape. Current InstCombine already rewrites that shape, and upstream delinearization has moved away from source-element-type reasoning. Keeping two proofs would make legality depend on when canonicalization ran. A test that runs InstCombine before LoopInterchange requires the same byte proof to accept both forms.

The relation the proof rests on is:

i_N - i_E = W * (i_E - j)

With the selected-outer trip count at most W, an in-range alias can only have i_N == i_E. This does not reinterpret a wildcard direction or relax DependenceAnalysis. The candidate is accepted only when the independent address proof establishes that every possible alias in the bounded domain is same-outer. Otherwise it rejects. More generally, the byte-offset proof accepts a pair only when N's selected-outer coefficient is +/-1 and its selected-inner coefficient is +/-W, E has no selected-inner coefficient, and E's outer coefficient and constant agree with N's modulo W. Because N's outer coefficient is a unit, the alias equation reduces modulo W to i_N == i_E (mod W). Congruence of non-unit outer coefficients would not suffice: it could constrain the iteration difference only modulo W/gcd, allowing a cross-outer alias inside the accepted domain.

3.5 Recover the bound independently of the trip

W is an address property, not a loop-trip property. Recovering it from the trip count would be unsound, as Flang's flattened IR shows: the row stride is the compile-time constant 1335, while the selected outer trip is the runtime expression min(M,N), and the IR contains no predicate proving min(M,N) <= 1335. Source declarations that no longer survive lowering, metadata names, and benchmark-specific input assumptions cannot replace an LLVM IR legality proof.

resolvePreparedTripBound tries a constant maximum trip, then an exact trip plus dominating predicate, and only then records a runtime requirement. Every backedge count is converted to a trip count first; comparing a raw maximum backedge count to W would admit the forbidden trip W+1. Runtime requirements must name the selected outer's exact uniqued SCEV and fold their limits to one Wmin; a second runtime trip rejects.

Each accepted address proof records two requirements, one PreparedBoundRequirement of each BoundRequirementKind, resolved together into the plan's PreparedTripBound. ModularOuterSpan is the selected-outer lemma outer trip <= W that the same-outer conclusion depends on. ObjectContainment separately bounds the inner extent and verifies that every checked signed byte offset stays within an accessible-byte lower bound (getKnownAccessibleBytes): an exact base object, a sized non-extern_weak global's documented minimum size, or a non-null dereferenceable(N) fact. If only the inner containment requirement is dynamic, its distinct trip SCEV rejects the plan rather than becoming a runtime guard. The 171.swim nest is RuntimeBound because both requirements resolve to the same selected-outer trip SCEV.

This series materializes only StaticBound. A RuntimeBound plan emits the missed remark (rejectPreparedEpilogue) and is destroyed before ordinary routing can mutate the collected chains (selection). Whole-loop runtime versioning is deferred to the follow-on rather than hiding a guard, clone, live-out repair, and fallback-path transaction inside this already large correctness change.

3.6 Reject convergent retained nests, without an operand-bundle test

Distributing E out of the nest and then interchanging the nest changes the loop structure around any convergent call in the retained region, so the set of threads (in the sense of LLVM's convergence model) arriving at it can differ from the original program's. Without the check, preparation admits a nest carrying convergence-control tokens, and the interchange then violates the ConvergenceVerifier's cycle-heart dominance rule. Preparation therefore rejects a retained nest containing a convergent call (hasConvergentOperationInRetainedNest). The rejected alternative was to also scan operand bundles for convergence tokens. The source comment states why the scan is complete without it: "Convergence is a CallBase property, and every convergence-token producer is itself a convergent call inside this region." The three convergence intrinsics are the only token producers and all are convergent, so the call scan already rejects every producer.

3.7 Bounded operand classification

The epilogue operand classifier decides which outer-IV-derived values E must rematerialize. A recursive walk uses one stack frame per operand link and overflows an 8 MiB stack on a valid 300,000-link chain. EpilogueOperandClassifier instead walks an explicit stack of frames on the heap and reproduces the recursive walk exactly: leaf classification, cache lookups, the instruction's own operand order, the stop at the first Invalid operand, and post-order finalization.

Two alternatives fail. A maximum operand-chain depth rejects valid input. A larger stack moves the failure point without removing it. The deep-chain test runs the 300,000-link case under an explicit 8 MiB RLIMIT_STACK.

The prepared-plan line reports the rematerialization count, and the applied-IR checks assert the clone order for every applied case. The line has no hash of the ordered names: the applied-IR checks already cover the order, and no in-tree diagnostic hashes an internal ordering.

3.8 Preserve analysis state and debug records, not only executable semantics

Top-level LoopInfo siblings are stored in reverse program order, while nested subloops use forward order. Apply therefore has two insertion paths. addSiblingLoops cannot register a nested E because the loop-pass updater accepts only new top-level siblings (updater note).

After E instructions and intermediate path blocks are erased, forgetLoop is insufficient: cached block/loop dispositions can still name deleted blocks. Apply drops both loop expressions and dispositions before the first SCEV-aware query and again after interchange (invalidation sequence).

DbgRecords attach to source positions, not to the SSA definition they describe. Cloning records by instruction anchor would move N locations into E and miss records attached to omitted terminators. The implementation completes the value map first, maps source positions including path terminators, transfers only locations meaningful in E, and salvages unmatched users in reverse dependency order (debug transfer; salvageDebugInfo).

4. Implementation walkthrough

Use the constant-trip checksum_diagonal_epilogue test case as the running example. It preserves the benchmark's three reassociated column reductions and diagonal U update, but fixes the trip at 1335 so this series can apply the transformation.

The complete test case (llvm/test/Transforms/LoopInterchange/outer-epilogue-fission.ll, lines 664 to 723)

define void @checksum_diagonal_epilogue(
    ptr noalias %PNEW, ptr noalias dereferenceable(14257800) %UNEW,
    ptr noalias %VNEW, ptr noalias %R) {
entry:
  br label %outer.header

outer.header:
  %i = phi i64 [ 0, %entry ], [ %i.next, %outer.latch ]
  %pchk.i = phi double [ 0.000000e+00, %entry ], [ %pchk.next, %outer.latch ]
  %uchk.i = phi double [ 0.000000e+00, %entry ], [ %uchk.next, %outer.latch ]
  %vchk.i = phi double [ 0.000000e+00, %entry ], [ %vchk.next, %outer.latch ]
  %pcol = getelementptr inbounds [1335 x double], ptr %PNEW, i64 0, i64 %i
  %ucol = getelementptr inbounds [1335 x double], ptr %UNEW, i64 0, i64 %i
  %vcol = getelementptr inbounds [1335 x double], ptr %VNEW, i64 0, i64 %i
  br label %inner.header

inner.header:
  %j = phi i64 [ 0, %outer.header ], [ %j.next, %inner.header ]
  %pchk.j = phi double [ %pchk.i, %outer.header ], [ %pchk.next.j, %inner.header ]
  %uchk.j = phi double [ %uchk.i, %outer.header ], [ %uchk.next.j, %inner.header ]
  %vchk.j = phi double [ %vchk.i, %outer.header ], [ %vchk.next.j, %inner.header ]
  %pidx = getelementptr inbounds [1335 x double], ptr %pcol, i64 %j, i64 0
  %pv = load double, ptr %pidx, align 8
  %pchk.next.j = fadd reassoc double %pchk.j, %pv
  %uidx = getelementptr inbounds [1335 x double], ptr %ucol, i64 %j, i64 0
  %uv = load double, ptr %uidx, align 8
  %uchk.next.j = fadd reassoc double %uchk.j, %uv
  %vidx = getelementptr inbounds [1335 x double], ptr %vcol, i64 %j, i64 0
  %vv = load double, ptr %vidx, align 8
  %vchk.next.j = fadd reassoc double %vchk.j, %vv
  %j.next = add i64 %j, 1
  %j.ec = icmp eq i64 %j.next, 1335
  br i1 %j.ec, label %epilogue, label %inner.header

epilogue:
  %pchk.next = phi double [ %pchk.next.j, %inner.header ]
  %uchk.next = phi double [ %uchk.next.j, %inner.header ]
  %vchk.next = phi double [ %vchk.next.j, %inner.header ]
  %ddiag = getelementptr inbounds [1335 x double], ptr %UNEW, i64 %i, i64 %i
  %dval = load double, ptr %ddiag, align 8
  %dnew = fmul double %dval, 1.500000e+00
  store double %dnew, ptr %ddiag, align 8
  br label %outer.latch

outer.latch:
  %i.next = add i64 %i, 1
  %i.ec = icmp eq i64 %i.next, 1335
  br i1 %i.ec, label %exit, label %outer.header, !prof !0

exit:
  %pchk.res = phi double [ %pchk.next, %outer.latch ]
  %uchk.res = phi double [ %uchk.next, %outer.latch ]
  %vchk.res = phi double [ %vchk.next, %outer.latch ]
  %r1 = getelementptr inbounds double, ptr %R, i64 1
  %r2 = getelementptr inbounds double, ptr %R, i64 2
  store double %pchk.res, ptr %R, align 8
  store double %uchk.res, ptr %r1, align 8
  store double %vchk.res, ptr %r2, align 8
  ret void
}

1. Candidate routing (landed base). collectPerfectNests yields the chain [outer.header, inner.header]. The wiring in run(LoopNest &, LPMUpdater &) hands every fission-eligible chain to preparation within the MaxOuterEpilogueFissionCandidates budget. A size-optimized function skips fission and goes straight to the ordinary routing.
2. Discovery. discoverDistributableOuterEpilogue proves the pair is canonical, walks the unique inner-exit to outer-latch path (here the single block epilogue), keeps the three forwarding PHIs with N, records %ddiag, %dval, %dnew, and the store as E (epilogue-insts=4), and records separately the exact outer control the sibling loop needs. The classifier (§3.7) finds nothing to rematerialize: E's only loop-carried input is the outer IV itself, which the epilogue loop's own induction variable replaces. Any inner/reduction operand or escaping E definition rejects before analysis proceeds. Preparation then runs the memory budget and the convergence scan (§3.6) before the dependence proof.
3. Cross-partition proof. The U column read %uidx and the diagonal store %ddiag are anti [*|<], so proveNestToEpilogueDependences routes the pair to the byte-offset proof (§3.4). N's coefficients are outer 8 and inner 10,680 bytes, E's are outer 10,688 and inner 0; after normalization by 8, W=1335 and E's outer coefficient 1336 is congruent to 1 modulo W. The dereferenceable(14257800) fact supplies the containment bound (1335 rows of 10,680 bytes).
4. Two matrices, existing legality. Over the extracted view that hides E, preparation builds the fission context matrix over the absolute ancestry [outer, inner] and the routing matrix over the same chain (§3.3); the column selection itself lives in populateDependencyMatrix. For this example both are empty (fission-rows=0 routing-rows=0), so the ancestor-prefix check passes vacuously and the routing matrix feeds the unchanged canInterchangeLoops and profitability with no rows. The three reassoc reductions satisfy the existing recurrence-reordering rule; strict recurrences reject. This is why the series does not duplicate LoopInterchange's recurrence or cache-cost policy.
5. Bound resolution. Both requirements discharge on the constant maximum trip 1335 against W=1335 (§3.5, the resolver's first strategy, tagged by-constant-max on the prepared line), so the plan is StaticBound; validatePreparedPlan passes and the plan prints as prepared function=checksum_diagonal_epilogue ... path-blocks=1 epilogue-insts=4 rematerialized=0 ... cross-deps=1 reductions=6 byte-offset-proofs=1 requirements=2 bound=static-bound W=1335.
6. Apply. The plan is re-validated, then applyPreparedInterchange splits exit after its three LCSSA PHIs (SplitBlock, the first mutation), builds epilogue.preheader, epilogue.header, and epilogue.latch with a fresh induction variable over [0, 1335), clones the E slice (%ddiag.epil, %dval.epil, %dnew.epil, the store) through complete value maps, rewires exit into the new loop and the continuation exit.cont, updates the dominator tree, transfers debug records, registers the epilogue loop as a top-level sibling, and erases the original slice. epilogue stays as an empty forwarding block: the collapse merges only path blocks after the first, and this path has one. It then invalidates SCEV, forms LCSSA for the epilogue loop, performs the interchange recorded in the plan, reforms the nest's LCSSA, forgets the resulting outermost loops in SCEV, and emits the Interchanged and OuterEpilogueDistributed remarks. The test's APPLIED lines check every instruction of the new loop, the emptied original block, and the block that joins the nest exit to the epilogue loop. The test fails if an epilogue instruction stays in the nest or appears beside its clone.
7. Result. The loop tree has an epilogue sibling plus the former inner header as the new outer reduction loop. Both Interchanged and OuterEpilogueDistributed remarks are required, so no fission-only result can satisfy the test.

Line-by-line version of this section, with the excerpt of the test for each step.

Flang's byte-GEP form is flattened_byte_gep_latch (path-blocks=0: the slice lives in the latch). A runtime trip alone does not make a plan RuntimeBound: checksum_kernel_rect has disjoint N and E storage, so it needs no bound requirement and applies (cross-deps=0 requirements=0 bound=static-bound). The committed RuntimeBound Wmin=1335 case is bound_runtime_canonical, whose prepared line is followed by the runtime-bound rejection and whose IR is unchanged with the option on. The 171.swim nest is the out-of-tree instance of the same shape.

5. Scope boundary

This series deliberately does not handle:

• Runtime bounds: the 171.swim nest reports RuntimeBound Wmin=1335 and is unchanged. The follow-up patch supplies guarded versioning.
• General loop distribution: E must be one closed, straight-line, unconditional path on a direct parent/leaf-child pair.
• Calls inside E, non-simple (atomic or volatile) memory operations, unsupported E or control metadata, address-taken intermediate path blocks that the collapse would have to merge, loop-local outer control, and E values that escape. Calls retained in the nest stay subject to the existing safety checks plus the convergence scan (§3.6).
• Unknown, reversed, confused, non-affine, or E-to-N dependences (examples).
• Invariant-address 1-D surviving nests that fail existing interchange legality (example). The #47457 shape, an epilogue that increments a global and, under a condition, loads through an external pointer and stores to another global, is rejected during discovery, and a regression test checks that rejection (issue47457_guarded_epilogue).
• Strict floating-point recurrences. The transform requires existing reassociation permission before changing reduction order.
• optsize and minsize, where CFG and code-size growth are forbidden.
• Default enablement. The feature is off unless -loop-interchange-outer-epilogue-fission is given; preparation is independently bounded by -loop-interchange-max-outer-epilogue-fission-candidates (default 10).
• The existing transform's debug-info loss when it duplicates the latch: LoopInterchangeTransform::transform clones the latch computations without cloning their DbgRecords or assigning new key-instruction atoms. The loss predates this patch, and the fission debug test does not depend on it. An independent fix exists in an earlier local series (d7253ea). A separate small patch keeps this one focused, so the fix belongs in a follow-up.
• Pointer-argument bases without a known accessible-byte lower bound when a generalized N/E dependence requires the byte-offset proof. They reject rather than relying on typed GEP structure; disjoint bases that raise no cross-dependence need no bound at all.

6. Maintenance invariants

The implementation relies on these invariants:

• Address parsing, W recovery, and the trip resolver stay separate. Never infer W from the trip or divide a normalized byte coefficient twice.
• The byte-offset modular proof remains coupled to exact signed arithmetic and its accessible-byte range check. Extending plain heap or dummy-argument bases requires a replacement range argument, not dimensions recovered from GEP source types.
• LLVM main has no distinct ptradd opcode. Ptradd-shaped IR is an i8 GEP handled by collectExactGEPByteOffset. The walker rejects pointer arithmetic that is not a GEPOperator. Keep that rejection until the walker applies its exact-offset checks to the new opcode.
• The load/store dependence proof is sound only together with the existing whole-outer-loop unsafe-instruction scan and the convergence scan. Relaxing one requires reviewing all three.
• The fission context matrix and the routing matrix stay separate. A change to #199511's chain collection or projection must re-derive both RoutingChain and AbsoluteAncestors in validatePreparedPlan.
• validatePreparedPlan is the single predicate behind both the printed prepared-plan line and the check before apply. A new plan field must be re-derived or explicitly consistency-checked there, or the printed line stops meaning what the check before apply means.
• Preparation remains mutation-free, and apply remains infallible after the first SplitBlock. A new post-mutation rejection requires a design change, not a boolean return.
• The extracted-view instruction set is valid only before E is erased. No transform-time code may consult it afterward.
• Debug source positions, DbgAssign policy, mixed-location invariance, and atom remapping evolve together whenever the clone set changes.
• The lazy DomTreeUpdater window is exactly construct, merge loop, flush, with no dominator query inside it. The flush precedes E's LCSSA formation.
• The apply step clones OuterIVDerivedInstructions in their recorded order, and the applied-IR checks assert that order.
• LoopInterchangeUtils.h and its unit tests stay coupled to the production helpers.
• Top-level and nested sibling order, same-manager LoopNest rebuilding, and block/loop disposition invalidation keep independent tests.

7. Known gaps and uncertainties

• Handled by the follow-up: runtime versioning of RuntimeBound plans behind one predicate (its pre-#199511 implementation must be ported onto this series). This static series leaves the motivating loop unchanged by design.
• Follow-up PR: the latch debug-info fix (§5). The interchange recorded in the plan runs the existing transform, so this path inherits the loss like every ordinary interchange.
• TODO, valid but unhandled: plain pointer bases with neither a known object nor a non-null accessible-byte lower bound. They reject conservatively.
• TODO, valid but unhandled: the invariant-address 1-D flow/output forms. They are distribution-safe but fail an earlier existing interchange rule.
• Validate upstream: adapt the exact byte-offset walker if a real non-GEPOperator ptradd instruction lands. Current unsupported forms are rejected.
• Validate: compile-time behavior with the option on over a broad corpus. The feature is off by default, so a default pipeline pays only one disabled-option branch. One known limit: collapsing the emptied path blocks calls MergeBlockIntoPredecessor once per block, whose LoopInfo::removeBlock is linear per enclosing loop, so a path of tens of thousands of single-successor blocks costs quadratic time (about 1.2 s at 128,000 blocks). Default pipelines simplify such chains before LoopInterchange runs, so only IR fed unsimplified to -passes=loop-interchange reaches it.
• Validate outside the tree: end-to-end execution of the transformed kernels. The lit tests check the transformed IR, LoopInfo, SCEV, and debug records. Running a transformed module under lli has no precedent in llvm/test/Transforms, so the series has no execution test. During development the transformed test modules were executed under lli and passed. Those runs are not part of the patch.
• Validate: performance outside the measured Zen 4 workload. The legality proof is target-independent, but the measured 37.7% to 41.2% benefit is not a universal profitability claim.
• Asserted invariant: the prepared legality object contains pointers to the extracted E view, but no method reachable from apply consults that view after erasure. Violating this is a compiler bug, not a recoverable TODO.
• Asserted invariant: a plan that passed validatePreparedPlan at selection passes it again at apply, since the IR is unchanged in between. The release-build bail-out is defensive, not an expected path.

pr224196-implementation-walkthrough-literate.md

Implementation walkthrough, line by line (#224196)

Companion to section 4 of the design walkthrough in this gist: the same seven steps, with the excerpt of the test for each step.

Use the constant-trip checksum_diagonal_epilogue test case as the running example. It preserves the benchmark's three reassociated column reductions and diagonal U update, but fixes the trip at 1335 so this series can apply the transformation.

The complete test case (llvm/test/Transforms/LoopInterchange/outer-epilogue-fission.ll, lines 664 to 723)

define void @checksum_diagonal_epilogue(
    ptr noalias %PNEW, ptr noalias dereferenceable(14257800) %UNEW,
    ptr noalias %VNEW, ptr noalias %R) {
entry:
  br label %outer.header

outer.header:
  %i = phi i64 [ 0, %entry ], [ %i.next, %outer.latch ]
  %pchk.i = phi double [ 0.000000e+00, %entry ], [ %pchk.next, %outer.latch ]
  %uchk.i = phi double [ 0.000000e+00, %entry ], [ %uchk.next, %outer.latch ]
  %vchk.i = phi double [ 0.000000e+00, %entry ], [ %vchk.next, %outer.latch ]
  %pcol = getelementptr inbounds [1335 x double], ptr %PNEW, i64 0, i64 %i
  %ucol = getelementptr inbounds [1335 x double], ptr %UNEW, i64 0, i64 %i
  %vcol = getelementptr inbounds [1335 x double], ptr %VNEW, i64 0, i64 %i
  br label %inner.header

inner.header:
  %j = phi i64 [ 0, %outer.header ], [ %j.next, %inner.header ]
  %pchk.j = phi double [ %pchk.i, %outer.header ], [ %pchk.next.j, %inner.header ]
  %uchk.j = phi double [ %uchk.i, %outer.header ], [ %uchk.next.j, %inner.header ]
  %vchk.j = phi double [ %vchk.i, %outer.header ], [ %vchk.next.j, %inner.header ]
  %pidx = getelementptr inbounds [1335 x double], ptr %pcol, i64 %j, i64 0
  %pv = load double, ptr %pidx, align 8
  %pchk.next.j = fadd reassoc double %pchk.j, %pv
  %uidx = getelementptr inbounds [1335 x double], ptr %ucol, i64 %j, i64 0
  %uv = load double, ptr %uidx, align 8
  %uchk.next.j = fadd reassoc double %uchk.j, %uv
  %vidx = getelementptr inbounds [1335 x double], ptr %vcol, i64 %j, i64 0
  %vv = load double, ptr %vidx, align 8
  %vchk.next.j = fadd reassoc double %vchk.j, %vv
  %j.next = add i64 %j, 1
  %j.ec = icmp eq i64 %j.next, 1335
  br i1 %j.ec, label %epilogue, label %inner.header

epilogue:
  %pchk.next = phi double [ %pchk.next.j, %inner.header ]
  %uchk.next = phi double [ %uchk.next.j, %inner.header ]
  %vchk.next = phi double [ %vchk.next.j, %inner.header ]
  %ddiag = getelementptr inbounds [1335 x double], ptr %UNEW, i64 %i, i64 %i
  %dval = load double, ptr %ddiag, align 8
  %dnew = fmul double %dval, 1.500000e+00
  store double %dnew, ptr %ddiag, align 8
  br label %outer.latch

outer.latch:
  %i.next = add i64 %i, 1
  %i.ec = icmp eq i64 %i.next, 1335
  br i1 %i.ec, label %exit, label %outer.header, !prof !0

exit:
  %pchk.res = phi double [ %pchk.next, %outer.latch ]
  %uchk.res = phi double [ %uchk.next, %outer.latch ]
  %vchk.res = phi double [ %vchk.next, %outer.latch ]
  %r1 = getelementptr inbounds double, ptr %R, i64 1
  %r2 = getelementptr inbounds double, ptr %R, i64 2
  store double %pchk.res, ptr %R, align 8
  store double %uchk.res, ptr %r1, align 8
  store double %vchk.res, ptr %r2, align 8
  ret void
}

Line numbers below refer to llvm/test/Transforms/LoopInterchange/outer-epilogue-fission.ll at c0ec2d79: the function spans lines 664 to 723, its prepared-plan checks lines 80 to 86, and its transformed-IR checks lines 237 to 264.

4.1 Candidate routing on the landed base

One outer loop, one inner loop, a single post-inner block, and the outer latch:

L670: outer.header:
       ...
L680: inner.header:
       ...
L696:   br i1 %j.ec, label %epilogue, label %inner.header
L698: epilogue:
       ...
L706:   br label %outer.latch
L708: outer.latch:
       ...
L711:   br i1 %i.ec, label %exit, label %outer.header, !prof !0

collectPerfectNests yields the chain [outer.header, inner.header]. run(LoopNest &, LPMUpdater &) hands every fission-eligible chain to preparation within the MaxOuterEpilogueFissionCandidates budget. A size-optimized function skips fission and goes straight to the ordinary routing.

4.2 Discovery

The post-inner block holds three forwarding PHIs and the four epilogue instructions. The latch holds only the outer control:

L698: epilogue:
L699:   %pchk.next = phi double [ %pchk.next.j, %inner.header ]
L700:   %uchk.next = phi double [ %uchk.next.j, %inner.header ]
L701:   %vchk.next = phi double [ %vchk.next.j, %inner.header ]
L702:   %ddiag = getelementptr inbounds [1335 x double], ptr %UNEW, i64 %i, i64 %i
L703:   %dval = load double, ptr %ddiag, align 8
L704:   %dnew = fmul double %dval, 1.500000e+00
L705:   store double %dnew, ptr %ddiag, align 8
L706:   br label %outer.latch
L708: outer.latch:
L709:   %i.next = add i64 %i, 1
L710:   %i.ec = icmp eq i64 %i.next, 1335

discoverDistributableOuterEpilogue proves the pair is canonical, walks the unique inner-exit to outer-latch path (the single block epilogue), keeps the three forwarding PHIs with N, records %ddiag, %dval, %dnew, and the store as E (epilogue-insts=4), and records separately the outer control %i.next and %i.ec that the sibling loop needs. The classifier (§3.7) finds nothing to rematerialize: E's only loop-carried input is the outer IV %i, which the epilogue loop's own induction variable replaces. Any inner or reduction operand and any escaping E definition rejects before analysis proceeds. Preparation then runs the memory budget and the convergence scan (§3.6) before the dependence proof.

4.3 Cross-partition proof

The nest reads column %i of %UNEW, and the epilogue updates that column's diagonal element:

L676:   %ucol = getelementptr inbounds [1335 x double], ptr %UNEW, i64 0, i64 %i
       ...
L688:   %uidx = getelementptr inbounds [1335 x double], ptr %ucol, i64 %j, i64 0
L689:   %uv = load double, ptr %uidx, align 8
       ...
L702:   %ddiag = getelementptr inbounds [1335 x double], ptr %UNEW, i64 %i, i64 %i
       ...
L705:   store double %dnew, ptr %ddiag, align 8

The pair %uidx and %ddiag is anti [*|<], so proveNestToEpilogueDependences routes it to the byte-offset proof (§3.4). N's coefficients are outer 8 and inner 10,680 bytes, E's are outer 10,688 and inner 0. After normalization by 8, W=1335 and E's outer coefficient 1336 is congruent to 1 modulo W. The dereferenceable(14257800) fact on %UNEW (L665) supplies the containment bound: 1335 rows of 10,680 bytes.

4.4 Two matrices, existing legality

L82: ; PREP-SAME:  absolute-depth=2 routing-depth=2 fission-rows=0 routing-rows=0 cross-deps=1 reductions=6

Over the extracted view that hides E, preparation builds the fission context matrix over the absolute ancestry [outer, inner] and the routing matrix over the same chain (§3.3). The column selection lives in populateDependencyMatrix. Both matrices are empty here (fission-rows=0 routing-rows=0), so the ancestor-prefix check passes vacuously and the routing matrix feeds the unchanged canInterchangeLoops and profitability with no rows. The three reassoc reductions satisfy the existing recurrence-reordering rule, and strict recurrences reject. The series therefore does not duplicate LoopInterchange's recurrence or cache-cost policy.

4.5 Bound resolution

L83: ; PREP-SAME:  byte-offset-proofs=1 requirements=2 bound=static-bound W=1335
L84: ; PREP-SAME:  requirement-ids=[[CHECKSUM_ID:[0-9]+]]:modular-outer-span/static/by-constant-max,[[CHECKSUM_ID]]:object-containment/static/by-constant-max{{$}}

Both requirements discharge on the constant maximum trip 1335 against W=1335 (§3.5, the resolver's first strategy, tagged by-constant-max), so the plan is StaticBound. validatePreparedPlan passes, and the printed plan (L80 to L84) reports path-blocks=1 epilogue-insts=4 rematerialized=0, cross-deps=1 reductions=6, and byte-offset-proofs=1 requirements=2.

4.6 Apply

The transformed function, as the test checks it:

L238: ; APPLIED:         epilogue:
L239: ; APPLIED-NEXT:      br label %outer.latch
L240: ; APPLIED:         exit:
L241: ; APPLIED-NEXT:      %pchk.res = phi double [ %pchk.next, %inner.header.split ]
       ...
L244: ; APPLIED-NEXT:      br label %epilogue.preheader
L247: ; APPLIED:         epilogue.header:
L248: ; APPLIED-NEXT:      %epilogue.iv = phi i64 [ 0, %epilogue.preheader ], [ %i.next.epil, %epilogue.latch ]
L249: ; APPLIED-NEXT:      %ddiag.epil = getelementptr inbounds [1335 x double], ptr %UNEW, i64 %epilogue.iv, i64 %epilogue.iv
L250: ; APPLIED-NEXT:      %dval.epil = load double, ptr %ddiag.epil, align 8
L251: ; APPLIED-NEXT:      %dnew.epil = fmul double %dval.epil, 1.500000e+00
L252: ; APPLIED-NEXT:      store double %dnew.epil, ptr %ddiag.epil, align 8
L254: ; APPLIED:         epilogue.latch:
L255: ; APPLIED-NEXT:      %i.next.epil = add i64 %epilogue.iv, 1
L256: ; APPLIED-NEXT:      %i.ec.epil = icmp eq i64 %i.next.epil, 1335
L257: ; APPLIED-NEXT:      br i1 %i.ec.epil, label %exit.cont, label %epilogue.header, !prof !0
L258: ; APPLIED:         exit.cont:
       ...
L264: ; APPLIED-NEXT:      ret void

The plan is re-validated, then applyPreparedInterchange splits exit after its three LCSSA PHIs (SplitBlock, the first mutation), builds epilogue.preheader, epilogue.header, and epilogue.latch with a fresh induction variable %epilogue.iv over [0, 1335), clones the E slice (%ddiag.epil, %dval.epil, %dnew.epil, the store) through complete value maps, rewires exit into the new loop and the continuation exit.cont, updates the dominator tree, transfers debug records, registers the epilogue loop as a top-level sibling, and erases the original slice. epilogue stays as an empty forwarding block (L238 to L239): the collapse merges only path blocks after the first, and this path has one. It then invalidates SCEV, forms LCSSA for the epilogue loop, performs the interchange recorded in the plan (the LCSSA PHIs in exit now come from %inner.header.split, L241), reforms the nest's LCSSA, forgets the resulting outermost loops in SCEV, and emits the Interchanged and OuterEpilogueDistributed remarks. The test fails if an epilogue instruction stays in the nest or appears beside its clone.

4.7 Result

L85: ; PREP-NEXT:  remark: <unknown>:0:0: Loop interchanged with enclosing loop.
L86: ; PREP-NEXT:  remark: <unknown>:0:0: Distributed a proven outer-loop epilogue into its own loop before interchanging the reduction nest; bound=static-bound, W=1335.

The loop tree has an epilogue sibling plus the former inner header as the new outer reduction loop. Both remarks are required, so no fission-only result satisfies the test.