#224804 |
3524fcccffa51d87c6223e5cf8db1bf788ef626d runtime versioning
Context: Improving SPECfp2000/SWIM2000 performance for Flang.
Background: #224196 added outer-epilogue fission, a transformation distributing the trailing code of each outer iteration into its own loop so that the remaining nest can be interchanged. Its walkthrough documents its legality: recovery of a row stride W from exact byte offsets, and a dependence proof across the two loops created by distribution, holding while the outer loop's trip count T satisfies T <= W. A plan is the complete, non-mutating record of a single candidate decision. LoopInterchange builds the plan first and applies it later. The change in #224196 applies a plan only when LLVM proves that bound at compile time.
The stride W is an address property, while the trip count T is an independent loop property. Canonical lowered code therefore routinely supplies a constant W and a runtime T. The motivating shape is:
for i in [0, T):
for j in [0, T):
check += A(j,i) // N: strided column reduction
A(i,i) = f(A(i,i)) // E: ordered post-inner epilogue
A denotes one of 171.swim's REAL*8 work arrays, check is a scalar reduction, and T is the shared runtime trip count. The labels N and E name the two partitions created by fission: N(i,*) is the inner loop's full trip for outer iteration i, and E(i) is that iteration's epilogue. The nest label N is unrelated to the Fortran grid extent N in the illustrative example below. The pass selects the outer i loop containing N and E for interchange, and this document calls it the selected outer loop.
The declarations behind A and T, abridged and collected from several program units, have this shape:
! Illustrative example corresponding to 171.swim; not verbatim benchmark source.
PARAMETER (N1=1335, N2=1335) ! leading dimension of the work arrays
REAL*8 U(N1,N2), V(N1,N2), P(N1,N2)
READ (5,*) M, N ! grid extents, read at run time
MNMIN = MIN0(M,N) ! trip count of the checksum loopsThe parameter N1 fixes the leading dimension at 1335, and Fortran stores the first subscript contiguously, so advancing the second subscript steps over 1335 eight-byte elements. Flang flattens that step to the byte coefficient 8*1335 = 10680, and outer-epilogue fission divides by the element size to recover the element stride W = 1335. T instead comes from MNMIN = MIN0(M,N), where M and N are grid extents read at run time rather than array bounds. The illustrative example explains provenance only. The pass derives W from ordinary address arithmetic, without matching source names or special-casing any value.
During Flang's LoopInterchange enablement, sebpop reported that swim had "not enough data to infer number of iterations" and proposed adding a frontend assume (N < 1335) as a follow-on. Outer-epilogue fission recovers W at compile time, and this patch guards the independent runtime T instead of asking the frontend for a fact.
@bound_runtime_canonical showed what the pass missed before this patch: With outer-epilogue fission enabled, the pass built a complete plan, printed bound=runtime-bound Wmin=1335, emitted a missed-optimization remark, and left the module unchanged. Wmin is the smallest stride recovered by the proof. The dependence proof held only over T <= W, with T unknown at compile time.
This patch therefore keeps two copies of the loop and selects between them at run time: Executions with T <= W run the versioned loop, the original loop object with its epilogue extracted and its nest interchanged, and the rest run the fallback, an untouched clone keeping the original N(i,*), E(i) order and every ordered effect. LoopVersioning uses the same names: getVersionedLoop for the original object and getNonVersionedLoop for the clone.
Related upstream work: #217884 added Loop::isSafeToCloneConditionally, a prerequisite used by this patch. A separate open PR, #157749, proposes versioning a two-dimensional nest behind trip-count guards with markers. That work is adjacent to this patch rather than another fix for the missing trip bound.
The change is entirely in LLVM IR scalar transforms: the LoopInterchange pass, the LoopVersioning utility, SCEVExpander, and Loop Access Analysis. Flang, like any other frontend, reaches these transforms through its emitted LLVM IR, and the decision depends only on that IR.
The pass prepares a plan without mutating IR, validates it, and then applies it. Runtime versioning extends that sequence at three points. prepareRuntimeVersioning runs the runtime versioning checks at the end of preparation, before a RuntimeBound plan's final validation. The RuntimeBound case of validatePreparedPlan calls isRuntimeVersioningStateCurrent. A branch of run calls applyPreparedRuntimeInterchange. The guard is the runtime comparison selecting between the two copies. applyPreparedRuntimeInterchange expands the guard, versions the loop, and runs applyPreparedInterchange, shared with the static path, on the versioned loop alone.
Every legality and cost check precedes mutation. The runtime versioning checks run during preparation, and the apply routine repeats the plan validation and checks the Loop Access predicate union before it mutates anything. That union holds the runtime SCEV conditions reported by Loop Access Analysis for the loop.
The fallback must preserve the original interleaving N(i,*), E(i), so the order is: prove and prepare, version the complete outer loop, then extract and interchange the versioned loop only. Guard expansion is the first mutation, and every fallible decision precedes it. The pass therefore never returns success after producing only a guard, a version split, a distributed epilogue, or an interchange.
Cloning after extraction is rejected because the clone would already carry the reordered body and could not serve as the fallback. Cloning only the reduction nest is rejected because it would separate the fallback from the ordered epilogue whose dependence makes the guard necessary. Mutating first and rolling back on failure is rejected because LoopInfo, the dominator tree, LCSSA, and ScalarEvolution would already have observed a partially changed CFG, making the rollback another transformation with its own failure modes.
Preparation leaves one or more dependence requirements for run time. Each names two things: a SCEV for the selected outer loop's exact trip count and a constant limit. That count is distinct from the loop's backedge-taken count. Wmin is the unsigned minimum of those limits, and it equals W when one requirement resolves the bound. Every requirement left for run time must refer to the same exact-trip-count SCEV. runtimeRequirementsAreConsistent rejects a plan whose requirements name two different SCEVs for that count, recomputes the minimum of the limits, and requires it to equal the stored Wmin. The guard is the single comparison exact_selected_outer_trip u> Wmin. A true result selects the fallback, and a false result selects the versioned loop. A trip count of W+1 deliberately runs the fallback, because the proof establishes only T <= W.
Comparing the backedge-taken count directly is rejected: A backedge-taken count of W denotes W+1 iterations, so that comparison accepts the trip count excluded by the proof. General alias checks and a disjunction of unrelated trip predicates are rejected because they would turn a narrow bound recovery into a general dependence versioner with a different cost model.
The compare width is the maximum of the trip count's width and Wmin's width, reached by zero extension only. The extra bit matters: ScalarEvolution materializes an i64 bottom-tested loop's exact trip as an i65 expression, because a loop whose latch compares an incremented i64 induction variable against a zero limit runs 2^64 iterations, and a 64-bit computation would wrap that count to zero and select the versioned loop.
The pass reuses LoopVersioning rather than adding a second loop-cloning implementation, a duplicate of preheader splitting, exit repair, LCSSA join construction, and debug-record handling.
Because the pass replaces the utility's generated condition instead of composing with it, the pass accepts only an empty, always-true predicate union. The pass requires the union to be empty, not merely always true. The two differ: A union can hold an always-true wrap predicate, because its AddRec already carries the no-signed-wrap flag, and that union stays nonempty. The unit test AlwaysTrueWrapPredicateKeepsUnionNonempty shows this case. Such a union has nothing to check at run time, yet the pass would reject it, because LoopVersioning does not specify how it would expand a nonempty union. In the current implementation the requirement always holds: Loop Access Analysis rejects a non-innermost loop before recording any predicate, and the selected outer loop always contains the inner loop. The check therefore cannot fail: It enforces a precondition of the LoopVersioning contract.
#51768 reports an assertion in LoopVersioning::versionLoop when the caller does not need a runtime check. The current SCEVExpander returns a constant false for an empty union, so versionLoop receives a non-null condition here, and the pass replaces that constant with its guard.
LoopVersioning normally emits runtime pointer-overlap checks, the alias checks selecting which of its two loops runs. The pass gives it an empty list of those checks, so it emits none. The pass never calls annotateLoopWithNoAlias, so it does not add alias metadata to either loop: the guard proves only T <= W, not pointer disjointness. The regression tests check the absence of !alias.scope and !noalias in every applied function.
prepareRuntimeVersioning runs the runtime versioning checks inside preparation, before the plan can be retained for apply. When any check fails, it bails out and preparation returns without a plan. The legality conditions reject a loop unsafe to clone conditionally, a loop outside canonical single-exit recursive LCSSA form or carrying irreducible control, unsafe versioning control, a trip not safely expandable by the pass at the preheader terminator, and a live-out lacking the exit PHI needed by versionLoop (explained in §3.6). The cost limits reject an exceeded block or instruction count, a trip whose expansion exceeds the budget, and a size-optimized function. Preparation also returns without a plan on a disabled option and on a loop already carrying the loop-metadata marker described in §3.8.
The control scan is not a list of permitted opcodes. Instead, hasSafeRuntimeVersioningControl requires every terminator to be a branch, rejects any token-like value, requires simple loads and stores, and requires every call to be a CallInst duplicable, non-convergent, free of deopt state, non-throwing, guaranteed to return, memory-free, and side-effect-free. It accepts every other instruction unless that instruction reads or writes memory or may throw, so ordinary arithmetic passes.
With fission enabled and runtime versioning left off, a runtime-bound candidate reports reason=runtime outer-epilogue versioning is disabled and omits the prepared-plan line. Before this patch, the pass printed the plan and then declined it. Neither behavior changes the module.
Leaving that rejection in the candidate selector and running the runtime versioning checks from run is rejected for two reasons: It would print a complete plan subsequently declined by the pass (giving one candidate two contradictory diagnostics), and it would let a plan failing the versioning checks take the single slot for a retained runtime-bound plan ahead of a later passing candidate.
The Loop Access check is in the apply routine. prepareRuntimeVersioning is a free function over ScalarEvolution, LoopInfo, the dominator tree, and TargetTransformInfo, while LoopAccessInfoManager needs the pass's alias analysis, assumption cache, and library info. The check therefore lives in the member function owning them, still ahead of guard expansion.
A runtime plan records loop structure not recorded by a static plan: the check point, the parent loop, the sub-loop list, the selected loop's blocks, instructions, and edges, and its live-out set (PreparedRuntimeVersioning). That structure is valid only against the current dominator tree and LoopInfo, so validatePreparedPlan takes both and holds the revalidation in its RuntimeBound case. Its other case rejects a plan carrying runtime state at all.
Calling that revalidation separately beside each of the five validation sites is rejected, because it duplicates the contract and lets validatePreparedPlan return true for a stale plan at any site omitting the second call. The revalidation compares blocks, instructions, and edges by pointer identity in enumeration order, then recomputes the live-out set and requires LCSSA conformance and equality with the recorded vector. A looser "the loop still looks canonical" test is rejected because the dependence matrices and live-out vector recorded in the plan are valid for one precise CFG.
versionLoop receives the vector from findDefsUsedOutsideOfLoop. That helper records a definition as live-out when any user lies outside the loop. Loop::isLCSSAForm attributes uses through loopContainsUser. A PHI use belongs to its incoming block, and blocks unreachable from entry are ignored, because "uses in them don't need to go through PHIs". LCSSA may therefore omit the exit PHI for a definition used only on such paths. Without the live-out check, LoopVersioning::addPHINodes can synthesize a join PHI whose incoming value does not dominate the exiting block. When that occurs, an assertions build aborts after mutation.
The patch applies LCSSA's own attribution rather than a list of known divergences. liveOutsMatchLCSSA reproduces loopContainsUser over every recorded definition and rejects the candidate when any definition keeps an outside use not attributed by LCSSA to an exit PHI. It runs in both the runtime versioning checks and the revalidation. Five regression cases cover the distinct shapes, running from a token live-out to an ordinary value reaching a live PHI along an unreachable edge. Three reject on conditional clone safety or the control scan, and two reject on the live-out rule itself.
Two alternatives are rejected. Filtering the vector to the LCSSA-guarded subset would hand the utility a set different from the set recomputed by findDefsUsedOutsideOfLoop, breaking the revalidation's equality check. Running formLCSSA first is mutation before the runtime versioning checks run, forbidden by the prepare-then-apply sequence of §2. These inputs stay unchanged without versioning, so the rejection preserves current behavior.
versionLoop appends the fallback to LoopInfo and the epilogue then becomes another sibling. Leaving both merely registered would produce a live order differing from a fresh LoopInfo analysis. The relocation rebuilds top-level storage as fallback, epilogue, versioned (because top-level loops are stored in reverse program order) and nested storage as versioned, epilogue, fallback. Relying on LoopInfo::verify is rejected, because it checks membership and parentage but not sibling order. The APPLY-LOOPS check instead runs print<loops> on the live analysis and on the re-parsed output, requiring both to agree on the order fallback, epilogue, versioned.
The loop-pass updater accepts only new top-level siblings, so the sibling-registration step registers the fallback and the epilogue for a top-level candidate only. A nested pair relies on the next loop-nest walk after run reports the change.
markRuntimeVersionedLoop gives each version the loop metadata llvm.loop.interchange.runtime_versioned, and both isFissionEligibleChain and discovery skip a marked loop, so a second pass instance leaves both versions alone.
The generic addStringMetadataToLoop helper is rejected as the writer, because it merges into existing loop metadata and leaves the metadata unchanged when the requested string is already present. markRuntimeVersionedLoop instead asserts that the loop does not yet have a loop ID, a precondition already established by preparation when it rejected loops with input metadata.
The running example is @cand_canonical: a typed [1335 x i64] row, a strided column reduction nest, a diagonal update epilogue, and one shared runtime trip %n. Corresponding Fortran snippet (the inner loop steps the second subscript, so consecutive iterations are 1335 elements apart in column-major storage):
INTEGER*8 A(1335,1335), CHECK
DO I = 1, N
DO J = 1, N
CHECK = CHECK + A(I,J) ! N: strided column reduction
END DO
A(I,I) = A(I,I) + I ! E: epilogue after the inner loop
END DOThe IR names the same accesses in row-major reading order: A[j][i] for the reduction, A[i][i] for the epilogue, and %n for N.
The complete test case (llvm/test/Transforms/LoopInterchange/outer-epilogue-fission-guarded-runtime.ll, lines 741 to 780)
define void @cand_canonical(ptr noalias dereferenceable(14257800) %A, i64 %n,
ptr noalias %sumout) {
entry:
%pos = icmp sgt i64 %n, 0
br i1 %pos, label %outer.ph, label %ret
outer.ph:
br label %outer.header
outer.header:
%i = phi i64 [ 0, %outer.ph ], [ %i.next, %outer.latch ]
%s.i = phi i64 [ 0, %outer.ph ], [ %s.next, %outer.latch ]
%col = getelementptr inbounds [1335 x i64], ptr %A, i64 0, i64 %i
br label %inner.header
inner.header:
%j = phi i64 [ 0, %outer.header ], [ %j.next, %inner.header ]
%s.j = phi i64 [ %s.i, %outer.header ], [ %s.next.j, %inner.header ]
%addr = getelementptr inbounds [1335 x i64], ptr %col, i64 %j, i64 0
%x = load i64, ptr %addr, align 8
%s.next.j = add i64 %s.j, %x
%j.next = add i64 %j, 1
%j.ec = icmp eq i64 %j.next, %n
br i1 %j.ec, label %epilogue, label %inner.header
epilogue:
%s.next = phi i64 [ %s.next.j, %inner.header ]
%dp = getelementptr inbounds [1335 x i64], ptr %A, i64 %i, i64 %i
%dv = load i64, ptr %dp, align 8
%ii1 = add i64 %i, 1
%dn = add i64 %dv, %ii1
store i64 %dn, ptr %dp, align 8
br label %outer.latch
outer.latch:
%i.next = add i64 %i, 1
%i.ec = icmp eq i64 %i.next, %n
br i1 %i.ec, label %exit, label %outer.header
exit:
%s.res = phi i64 [ %s.next, %outer.latch ]
store i64 %s.res, ptr %sumout, align 8
br label %ret
ret:
ret void
}-
Discovery and preparation.
isFissionEligibleChainaccepts the pair because neither loop carries the recursion marker of §3.8, and preparation recoversW=1335from the exact byte coefficients, asserted by thePREPcheck asrequirements=2 bound=runtime-bound Wmin=1335. -
Runtime versioning checks and routing.
prepareRuntimeVersioningruns the runtime versioning checks of §3.4 and the live-out rule of §3.6. The single live-out%s.nexthas one use outside the loop, the exit PHI%s.res, whose incoming block%outer.latchlies inside the loop, soliveOutsMatchLCSSAaccepts.tryPrepareOuterEpilogueFissionthen, lacking a statically bounded plan, retains the runtime plan and returns it, andruntakes the runtime branch. -
Apply.
applyPreparedRuntimeInterchangeruns this order, and only the first two steps can reject:check the Loop Access predicate union empty and always true, no convergent operation; holds for every non-innermost loop in the current implementation validatePreparedPlan asserted, release build rejects unchanged IR expandComparePredicate exact trip ule Wmin (first mutation) retire the prepared SCEVs and recorded structure versionLoop(live-outs) original remains the versioned loop, clone becomes the fallback setCondition(bad) replace the utility's false condition mark both versions llvm.loop.interchange.runtime_versioned assert dedicated exits feed one shared join forgetAffectedTopmostLoops({versioned, fallback}) applyPreparedInterchange(plan, updater, fallback)After apply, the CFG has this shape:
selected outer preheader | check T u> Wmin | true | false fallback (the clone): versioned loop (the original object): original N(i,*), E(i) order interchanged N | | | extracted E loop | | +---------- shared live-out join ----+ -
The expanded guard, and both copies. The
APPLIEDcheck asserts the shape of §3.2: The backedge-taken count%n - 1is zero-extended to i65, incremented withnuw, and comparedugt 1335. The true edge selects%outer.header.ph.lver.orig. The fallback keeps the original body order, with the diagonal update inside it, while the versioned loop ends interchanged, its extracted epilogue runs over a fresh induction variable, and the shared join merges the reduction from both.
The structural suite outer-epilogue-fission-versioning.ll versions five candidates and leaves thirteen unchanged, for the reasons of §3.4. @version_outer_header_freeze is the only exception, rejected by the existing interchange legality check before any versioning work begins. @version_toplevel_dynamic and @version_nested_dynamic cover both storage paths, while @version_blocks_16 and @version_insts_128 are versioned at the default limits and rejected one step below them. TopLevelSelectedOuterEmptyChecks carries the utility contract: the two roles, the branch condition and successor order, dedicated exits, three live-out joins with their exact incoming blocks, and SCEV repair.
With -loop-interchange-outer-epilogue-fission and -loop-interchange-outer-epilogue-runtime-versioning both enabled, and with reassociation allowed for the floating-point sums of the 171.swim checksum nest, that nest is versioned behind an unsigned trip > 1335 guard. 1335 is the leading dimension of its arrays. Without reassociation permission, the pass leaves the nest unchanged, because reordering the reduction requires that permission.
- Runtime outer-epilogue versioning is opt-in and hidden.
-loop-interchange-outer-epilogue-runtime-versioningdefaults to off and takes effect only when outer-epilogue fission is also enabled, and outer-epilogue fission stays available when runtime versioning is off. Default enablement waits for broad-corpus compile-time, code-size, and profitability results (suggestions welcome), not supplied by this patch. - The size and expansion limits bound cloning and expansion at 16 blocks, 128 non-debug instructions, and expansion cost 8. They are governance limits rather than a calibrated profitability model, and larger values wait for the same broad-corpus evidence (suggestions welcome). The pass leaves
Wminout of profitability, becauseWminbounds legality rather than benefit, and a proxy built on it would reject a hot small-outer, large-inner loop. - The deep operand chain test builds a 300,000-link outer-induction-variable operand chain, walked iteratively by the epilogue operand classifier under an 8 MiB stack, and it asserts the resulting rematerialized definition count only in an assertions build, since its runtime-off run rejects the candidate before a released diagnostic carries that count.
The implementation relies on these invariants:
- Every retention and apply site calls
validatePreparedPlan(Plan, DT, LI), and a new site must call the validator rather than the revalidation alone. - In
applyPreparedRuntimeInterchange, every fallible check precedes guard expansion and only assertions follow it. A new fallible operation belongs in preparation, since the design lacks a rollback path. - The recorded live-out vector equals
findDefsUsedOutsideOfLoop(Outer)at apply time, and every definition in it has an exit PHI for each reachable outside use.liveOutsMatchLCSSAstates that property and must trackLoop::isLCSSAForm. versionLoopkeeps the supplied loop as the versioned loop and returns the clone, and the guard's true edge selects that clone. A change to the utility's branch polarity, roles, preheader splitting, or join construction updates the unit tests first.- Two independent checks reject a convergent call here: the control scan (
hasSafeRuntimeVersioningControl) andLoop::isSafeToCloneConditionally. If one check is relaxed, the other still rejects such a call. The apply-time Loop Access check scans only innermost loops for convergent calls, so it adds a third rejection only if Loop Access Analysis gains outer-loop support.
- Asserted invariant: The revalidation compares by pointer identity and assumes that the IR stays unchanged between preparation and apply.
applyPreparedRuntimeInterchangeasserts that revalidation directly, so a violation would be a compiler bug. - Asserted invariant:
versionLoopwith empty checks and an empty always-true union emits afalsecondition and orders the successors with the fallback loop first. The unit tests state that contract, and #51768 tracks the utility's assertion when the caller does not need a runtime check. - TODO, valid but unhandled: A plan whose runtime requirements name two different exact-trip-count SCEVs is rejected. Emitting several guards would first need a policy and cost model.
- TODO, valid but unhandled: The pass rejects a nontrivial predicate union, and it rejects a nonempty always-true union as well. Accepting either needs an explicit contract for the utility's expansion form.
- TODO, valid but unhandled: The live-out rule rejects a loop with a definition whose outside use is in unreachable code. Running
opt -passes=lcssaon such a reproducer leaves that use in place, so LCSSA formation leaves the shape unrepaired, and the rejection is conservative. Those inputs are untransformed today, so the rejection preserves current behavior. - TODO, policy: Outer-epilogue fission under
optsizestays disabled together with runtime cloning, because the current rule skips the whole outer-epilogue path for a size-optimized function. - To validate: The code lacks a direct assertion that
addPHINodesnever synthesizes a join PHI. The property rests on recursive LCSSA form, the token-like rejection,liveOutsMatchLCSSA, and single-exit dedicated form, and the post-version LCSSA assertion catches a violation only indirectly. - To validate: When ScalarEvolution represents the exact trip count as an AddRec, guard expansion can introduce an
i65induction variable in the enclosing loop. That cost is unmeasured, and it is not a correctness question. - To validate: Moving the Loop Access check into preparation was not evaluated, and it would mean threading the pass-owned analyses into a free function.
- To validate: Guard expansion may reuse a dominating instruction and drop its poison-generating annotations on shared pre-version computation. Dropping them is safe and covered by the tests here, and whether
SCEVExpandershould preserve those annotations is open. - To validate: Profitability beyond one program and input remains unknown. The legality argument is silent on profitability.