Hi all,
We keep running into a gap in LLVM: there is no fair reusable mechanism to split a single counted loop’s iteration space into N caller-chosen contiguous partitions, with correct guards and live-out/reduction reconstruction. The existing splitters are all policy passes: they discover their own opportunities from in-body patterns and decide when to fire, so a caller can’t simply say “split this loop into the partitions I choose.” Today any transform that needs that re-implements a narrow, special-cased version of it.
The partition boundaries often come from outside the loop body (profile-guided hot-range isolation, a higher-level transform that already knows the ranges, language/region information), where there is no single in-body condition for a pass to pattern-match.
As a quick illustration, an N-way partition makes IV-dependent conditions loop-invariant per partition so later passes drop them:
// Three IV-dependent regions: needs partitioning at K1 AND K2 (N = 3 sub-loops).
for (int i = 0; i < n; i++) {
if (i < K1) a[i] = f(i);
else if (i < K2) a[i] = g(i);
else a[i] = h(i);
}
Prior art. This optimization, “index set splitting” (a.k.a. loop index splitting), is well established: GCC implements it as -fsplit-loops (tree-ssa-loop-split), and LLVM itself once had a dedicated LoopIndexSplit pass (still credited in CREDITS.TXT), removed in 2010 as “neither maintained nor used by anyone.” Since then the only in-tree form is IRCE’s range-check-specific, 3-way LoopConstrainer. LoopSplitUtils restores the general capability, but as a reusable, N-way, caller-driven utility.
What already exists (and why none is a general splitter):
- peelLoop: peels a fixed number of iterations off the front/back as straight-line copies. Not sub-loops, not arbitrary partitions.
- LoopConstrainer (used by IRCE): the closest thing; clones a loop into pre/main/post. But it’s hard-wired to 3 segments, the ranges are chosen internally for range-check elimination, and there’s no public N-way / caller-driven API.
- LoopBoundSplit: splits into 2 loops at a single IV-dependent condition it discovers itself (diamond CFG, fixed preconditions); a policy pass, not a caller-specified, N-way mechanism.
The gap: none of these lets a caller say “split this loop into these N partitions” and get back correct, guarded sub-loops. So passes that want index-set splitting either bolt it onto an unrelated utility or duplicate the cloning + guard + SSA-rebuild logic.
Proposal: a standalone LoopSplitUtils that:
- takes a counted loop plus an explicit, ascending list of contiguous partitions (inclusive [Start, End] ranges added via addPartition),
- emits one guarded sub-loop per partition (empty partitions skipped, leading/middle/trailing handled uniformly),
- clamps each partition to the true trip count (bottom-test safe), and
- rebuilds reductions/live-outs across partitions via SSAUpdater.
Intended consumer. This follows the direction laid out in the EuroLLVM 2024 quick talk “Loop Iteration Space Splitting” (slides): a test pass that specializes IV-dependent conditions / isolates iteration ranges drives the utility with its own partition list. The test driver (-loop-split-points) exercises the same path in lit tests.
The pattern already lives in the tree several times over, each welded to its own pass. Instead of adding another copy, we’d like to land one reusable splitter that any pass can call.
If the community would rather extend one of the existing splitters (`LoopConstrainer`, `LoopBoundSplit`, …) into this general mechanism, we are open to doing that. Our preference, though, is to land `LoopSplitUtils` as a separate utility first — so the N-way, caller-driven interface and its test coverage can be reviewed on their own — and then converge the existing implementations onto it one by one (re-pointing each such pass at the shared utility and removing its duplicated cloning/guard/SSA-rebuild logic). That keeps each step small and independently reviewable and avoids destabilizing IRCE or `LoopBoundSplit` while the common mechanism is still settling.
Happy to iterate on the interface and the limitations based on review. We have kept the first patch simple just focusing on trivial loops. If the direction looks right, we’ll follow this with the incremental update & migration outlined above.
Thanks!
Ashutosh