[LoopRotate] Use SCEV exit counts to improve rotation profitability#187483
Merged
Conversation
Member
|
@llvm/pr-subscribers-llvm-transforms Author: Florian Hahn (fhahn) ChangesMost loop transformations, like unrolling and vectorization, expect the This use SCEV to check for countable exits, if CheckExitCount set. With that compile-time impact is mostly neutral ClamAV is consistently slower ( Across a large test set based on C/C++ workloads, this rotates ~0.8% For the test set, ~2.7% more loops are runtime-unrolled and +6.36% more This fixes a regression where std::ranges::find_last loops stopped Based on #162654. Patch is 24.26 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/187483.diff 9 Files Affected:
diff --git a/llvm/include/llvm/Transforms/Scalar/LoopRotation.h b/llvm/include/llvm/Transforms/Scalar/LoopRotation.h
index cd108f7383e4c..256345b26d57c 100644
--- a/llvm/include/llvm/Transforms/Scalar/LoopRotation.h
+++ b/llvm/include/llvm/Transforms/Scalar/LoopRotation.h
@@ -24,7 +24,7 @@ class Loop;
class LoopRotatePass : public PassInfoMixin<LoopRotatePass> {
public:
LoopRotatePass(bool EnableHeaderDuplication = true,
- bool PrepareForLTO = false);
+ bool PrepareForLTO = false, bool CheckExitCount = false);
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
LoopStandardAnalysisResults &AR, LPMUpdater &U);
@@ -34,6 +34,7 @@ class LoopRotatePass : public PassInfoMixin<LoopRotatePass> {
private:
const bool EnableHeaderDuplication;
const bool PrepareForLTO;
+ const bool CheckExitCount;
};
}
diff --git a/llvm/include/llvm/Transforms/Utils/LoopRotationUtils.h b/llvm/include/llvm/Transforms/Utils/LoopRotationUtils.h
index c3643e0f27f94..18a1c4efcaab2 100644
--- a/llvm/include/llvm/Transforms/Utils/LoopRotationUtils.h
+++ b/llvm/include/llvm/Transforms/Utils/LoopRotationUtils.h
@@ -37,7 +37,8 @@ LLVM_ABI bool LoopRotation(Loop *L, LoopInfo *LI,
DominatorTree *DT, ScalarEvolution *SE,
MemorySSAUpdater *MSSAU, const SimplifyQuery &SQ,
bool RotationOnly, unsigned Threshold,
- bool IsUtilMode, bool PrepareForLTO = false);
+ bool IsUtilMode, bool PrepareForLTO = false,
+ bool CheckExitCount = false);
} // namespace llvm
diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp
index ea2380448c06f..a23d64b491a79 100644
--- a/llvm/lib/Passes/PassBuilder.cpp
+++ b/llvm/lib/Passes/PassBuilder.cpp
@@ -1274,17 +1274,25 @@ Expected<LICMOptions> parseLICMOptions(StringRef Params) {
return Result;
}
-Expected<std::pair<bool, bool>> parseLoopRotateOptions(StringRef Params) {
- std::pair<bool, bool> Result = {true, false};
+struct LoopRotateOptions {
+ bool EnableHeaderDuplication = true;
+ bool PrepareForLTO = false;
+ bool CheckExitCount = false;
+};
+
+Expected<LoopRotateOptions> parseLoopRotateOptions(StringRef Params) {
+ LoopRotateOptions Result;
while (!Params.empty()) {
StringRef ParamName;
std::tie(ParamName, Params) = Params.split(';');
bool Enable = !ParamName.consume_front("no-");
if (ParamName == "header-duplication") {
- Result.first = Enable;
+ Result.EnableHeaderDuplication = Enable;
} else if (ParamName == "prepare-for-lto") {
- Result.second = Enable;
+ Result.PrepareForLTO = Enable;
+ } else if (ParamName == "check-exit-count") {
+ Result.CheckExitCount = Enable;
} else {
return make_error<StringError>(
formatv("invalid LoopRotate pass parameter '{}'", ParamName).str(),
diff --git a/llvm/lib/Passes/PassBuilderPipelines.cpp b/llvm/lib/Passes/PassBuilderPipelines.cpp
index 123541a985454..5e4688f4dd7ef 100644
--- a/llvm/lib/Passes/PassBuilderPipelines.cpp
+++ b/llvm/lib/Passes/PassBuilderPipelines.cpp
@@ -1579,7 +1579,7 @@ PassBuilder::buildModuleOptimizationPipeline(OptimizationLevel Level,
// Disable header duplication at -Oz.
LPM.addPass(LoopRotatePass(EnableLoopHeaderDuplication ||
Level != OptimizationLevel::Oz,
- LTOPreLink));
+ LTOPreLink, /*CheckExitCount=*/true));
// Some loops may have become dead by now. Try to delete them.
// FIXME: see discussion in https://reviews.llvm.org/D112851,
// this may need to be revisited once we run GVN before loop deletion
diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def
index ad696861e556c..47c998a78d7c3 100644
--- a/llvm/lib/Passes/PassRegistry.def
+++ b/llvm/lib/Passes/PassRegistry.def
@@ -800,12 +800,14 @@ LOOP_PASS_WITH_PARAMS(
parseLICMOptions, "allowspeculation;no-allowspeculation")
LOOP_PASS_WITH_PARAMS(
"loop-rotate", "LoopRotatePass",
- [](std::pair<bool, bool> Params) {
- return LoopRotatePass(Params.first, Params.second);
+ [](LoopRotateOptions Params) {
+ return LoopRotatePass(Params.EnableHeaderDuplication, Params.PrepareForLTO,
+ Params.CheckExitCount);
},
parseLoopRotateOptions,
"no-header-duplication;header-duplication;"
- "no-prepare-for-lto;prepare-for-lto")
+ "no-prepare-for-lto;prepare-for-lto;"
+ "no-check-exit-count;check-exit-count")
LOOP_PASS_WITH_PARAMS(
"simple-loop-unswitch", "SimpleLoopUnswitchPass",
[](std::pair<bool, bool> Params) {
diff --git a/llvm/lib/Transforms/Scalar/LoopRotation.cpp b/llvm/lib/Transforms/Scalar/LoopRotation.cpp
index 112761f81016f..50d44369a40d0 100644
--- a/llvm/lib/Transforms/Scalar/LoopRotation.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopRotation.cpp
@@ -38,9 +38,10 @@ static cl::opt<bool> PrepareForLTOOption(
cl::desc("Run loop-rotation in the prepare-for-lto stage. This option "
"should be used for testing only."));
-LoopRotatePass::LoopRotatePass(bool EnableHeaderDuplication, bool PrepareForLTO)
+LoopRotatePass::LoopRotatePass(bool EnableHeaderDuplication, bool PrepareForLTO,
+ bool CheckExitCount)
: EnableHeaderDuplication(EnableHeaderDuplication),
- PrepareForLTO(PrepareForLTO) {}
+ PrepareForLTO(PrepareForLTO), CheckExitCount(CheckExitCount) {}
void LoopRotatePass::printPipeline(
raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
@@ -53,7 +54,11 @@ void LoopRotatePass::printPipeline(
if (!PrepareForLTO)
OS << "no-";
- OS << "prepare-for-lto";
+ OS << "prepare-for-lto;";
+
+ if (!CheckExitCount)
+ OS << "no-";
+ OS << "check-exit-count";
OS << ">";
}
@@ -74,9 +79,10 @@ PreservedAnalyses LoopRotatePass::run(Loop &L, LoopAnalysisManager &AM,
std::optional<MemorySSAUpdater> MSSAU;
if (AR.MSSA)
MSSAU = MemorySSAUpdater(AR.MSSA);
- bool Changed = LoopRotation(&L, &AR.LI, &AR.TTI, &AR.AC, &AR.DT, &AR.SE,
- MSSAU ? &*MSSAU : nullptr, SQ, false, Threshold,
- false, PrepareForLTO || PrepareForLTOOption);
+ bool Changed =
+ LoopRotation(&L, &AR.LI, &AR.TTI, &AR.AC, &AR.DT, &AR.SE,
+ MSSAU ? &*MSSAU : nullptr, SQ, false, Threshold, false,
+ PrepareForLTO || PrepareForLTOOption, CheckExitCount);
if (!Changed)
return PreservedAnalyses::all();
diff --git a/llvm/lib/Transforms/Utils/LoopRotationUtils.cpp b/llvm/lib/Transforms/Utils/LoopRotationUtils.cpp
index bf236d48f58f9..c8bc5e4daeff3 100644
--- a/llvm/lib/Transforms/Utils/LoopRotationUtils.cpp
+++ b/llvm/lib/Transforms/Utils/LoopRotationUtils.cpp
@@ -63,16 +63,18 @@ class LoopRotate {
bool RotationOnly;
bool IsUtilMode;
bool PrepareForLTO;
+ bool CheckExitCount;
public:
LoopRotate(unsigned MaxHeaderSize, LoopInfo *LI,
const TargetTransformInfo *TTI, AssumptionCache *AC,
DominatorTree *DT, ScalarEvolution *SE, MemorySSAUpdater *MSSAU,
const SimplifyQuery &SQ, bool RotationOnly, bool IsUtilMode,
- bool PrepareForLTO)
+ bool PrepareForLTO, bool CheckExitCount)
: MaxHeaderSize(MaxHeaderSize), LI(LI), TTI(TTI), AC(AC), DT(DT), SE(SE),
MSSAU(MSSAU), SQ(SQ), RotationOnly(RotationOnly),
- IsUtilMode(IsUtilMode), PrepareForLTO(PrepareForLTO) {}
+ IsUtilMode(IsUtilMode), PrepareForLTO(PrepareForLTO),
+ CheckExitCount(CheckExitCount) {}
bool processLoop(Loop *L);
private:
@@ -178,11 +180,12 @@ static void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader,
}
}
-// Assuming both header and latch are exiting, look for a phi which is only
-// used outside the loop (via a LCSSA phi) in the exit from the header.
-// This means that rotating the loop can remove the phi.
-static bool profitableToRotateLoopExitingLatch(Loop *L) {
+// Assuming both header and latch are exiting, check if rotating is profitable:
+// either a header phi becomes dead, or rotating makes the latch exit count
+// computable (enabling downstream optimizations like unrolling/vectorization).
+static bool profitableToRotateLoopExitingLatch(Loop *L, ScalarEvolution *SE) {
BasicBlock *Header = L->getHeader();
+ BasicBlock *Latch = L->getLoopLatch();
CondBrInst *BI = dyn_cast<CondBrInst>(Header->getTerminator());
BasicBlock *HeaderExit = BI->getSuccessor(0);
if (L->contains(HeaderExit))
@@ -196,6 +199,13 @@ static bool profitableToRotateLoopExitingLatch(Loop *L) {
continue;
return true;
}
+
+ // Check if rotating would make the latch exit count computable, enabling
+ // optimizations like runtime unrolling and vectorization.
+ if (SE && isa<SCEVCouldNotCompute>(SE->getExitCount(L, Latch)) &&
+ !isa<SCEVCouldNotCompute>(SE->getExitCount(L, Header)))
+ return true;
+
return false;
}
@@ -363,7 +373,7 @@ bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) {
// Rotate if the loop latch was just simplified. Or if it makes the loop exit
// count computable. Or if we think it will be profitable.
if (L->isLoopExiting(OrigLatch) && !SimplifiedLatch && IsUtilMode == false &&
- !profitableToRotateLoopExitingLatch(L))
+ !profitableToRotateLoopExitingLatch(L, CheckExitCount ? SE : nullptr))
return Rotated;
// Check size of original header and reject loop if it is very big or we can't
@@ -965,8 +975,9 @@ bool llvm::LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI,
ScalarEvolution *SE, MemorySSAUpdater *MSSAU,
const SimplifyQuery &SQ, bool RotationOnly = true,
unsigned Threshold = unsigned(-1),
- bool IsUtilMode = true, bool PrepareForLTO) {
+ bool IsUtilMode = true, bool PrepareForLTO,
+ bool CheckExitCount) {
LoopRotate LR(Threshold, LI, TTI, AC, DT, SE, MSSAU, SQ, RotationOnly,
- IsUtilMode, PrepareForLTO);
+ IsUtilMode, PrepareForLTO, CheckExitCount);
return LR.processLoop(L);
}
diff --git a/llvm/test/Transforms/LoopRotate/rotate-exitcount.ll b/llvm/test/Transforms/LoopRotate/rotate-exitcount.ll
new file mode 100644
index 0000000000000..9acff66150664
--- /dev/null
+++ b/llvm/test/Transforms/LoopRotate/rotate-exitcount.ll
@@ -0,0 +1,124 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -passes='loop(loop-rotate<header-duplication>)' %s | FileCheck %s --check-prefix=CHECK
+
+; Computable header exit, data-dependent latch exit. Rotated with check-exit-count.
+define ptr @search_loop(ptr %begin, ptr %end, i8 %val) {
+; CHECK-LABEL: @search_loop(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: [[CMP_ENTRY:%.*]] = icmp eq ptr [[BEGIN:%.*]], [[END:%.*]]
+; CHECK-NEXT: br i1 [[CMP_ENTRY]], label [[EXIT:%.*]], label [[FOR_COND_PREHEADER:%.*]]
+; CHECK: for.cond.preheader:
+; CHECK-NEXT: br label [[FOR_COND:%.*]]
+; CHECK: for.cond:
+; CHECK-NEXT: [[PTR:%.*]] = phi ptr [ [[PTR_DEC:%.*]], [[FOR_BODY:%.*]] ], [ [[END]], [[FOR_COND_PREHEADER]] ]
+; CHECK-NEXT: [[PTR_DEC]] = getelementptr inbounds i8, ptr [[PTR]], i64 -1
+; CHECK-NEXT: [[CMP_END:%.*]] = icmp eq ptr [[PTR_DEC]], [[BEGIN]]
+; CHECK-NEXT: br i1 [[CMP_END]], label [[NOT_FOUND:%.*]], label [[FOR_BODY]]
+; CHECK: for.body:
+; CHECK-NEXT: [[LOAD:%.*]] = load i8, ptr [[PTR_DEC]], align 1
+; CHECK-NEXT: [[CMP_VAL:%.*]] = icmp eq i8 [[LOAD]], [[VAL:%.*]]
+; CHECK-NEXT: br i1 [[CMP_VAL]], label [[FOUND:%.*]], label [[FOR_COND]]
+; CHECK: found:
+; CHECK-NEXT: [[PTR_DEC_LCSSA1:%.*]] = phi ptr [ [[PTR_DEC]], [[FOR_BODY]] ]
+; CHECK-NEXT: ret ptr [[PTR_DEC_LCSSA1]]
+; CHECK: not.found:
+; CHECK-NEXT: br label [[EXIT]]
+; CHECK: exit:
+; CHECK-NEXT: ret ptr [[END]]
+;
+entry:
+ %cmp.entry = icmp eq ptr %begin, %end
+ br i1 %cmp.entry, label %exit, label %for.cond
+
+for.cond:
+ %ptr = phi ptr [ %end, %entry ], [ %ptr.dec, %for.body ]
+ %ptr.dec = getelementptr inbounds i8, ptr %ptr, i64 -1
+ %cmp.end = icmp eq ptr %ptr.dec, %begin
+ br i1 %cmp.end, label %not.found, label %for.body
+
+for.body:
+ %load = load i8, ptr %ptr.dec, align 1
+ %cmp.val = icmp eq i8 %load, %val
+ br i1 %cmp.val, label %found, label %for.cond
+
+found:
+ ret ptr %ptr.dec
+
+not.found:
+ br label %exit
+
+exit:
+ ret ptr %end
+}
+
+; Both exits are memory-dependent (not computable). Not rotated.
+define i32 @both_mem_dependent(ptr %p, ptr %q, i32 %n) {
+; CHECK-LABEL: @both_mem_dependent(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: br label [[LOOP:%.*]]
+; CHECK: loop:
+; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BODY:%.*]] ]
+; CHECK-NEXT: [[LOAD1:%.*]] = load i32, ptr [[P:%.*]], align 4
+; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i32 [[LOAD1]], 0
+; CHECK-NEXT: br i1 [[CMP1]], label [[EXIT1:%.*]], label [[BODY]]
+; CHECK: body:
+; CHECK-NEXT: [[LOAD2:%.*]] = load i32, ptr [[Q:%.*]], align 4
+; CHECK-NEXT: [[CMP2:%.*]] = icmp eq i32 [[LOAD2]], 0
+; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], 1
+; CHECK-NEXT: br i1 [[CMP2]], label [[EXIT2:%.*]], label [[LOOP]]
+; CHECK: exit1:
+; CHECK-NEXT: [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[LOOP]] ]
+; CHECK-NEXT: ret i32 [[IV_LCSSA]]
+; CHECK: exit2:
+; CHECK-NEXT: [[IV_LCSSA1:%.*]] = phi i32 [ [[IV]], [[BODY]] ]
+; CHECK-NEXT: ret i32 [[IV_LCSSA1]]
+;
+entry:
+ br label %loop
+
+loop:
+ %iv = phi i32 [ 0, %entry ], [ %iv.next, %body ]
+ %load1 = load i32, ptr %p, align 4
+ %cmp1 = icmp eq i32 %load1, 0
+ br i1 %cmp1, label %exit1, label %body
+
+body:
+ %load2 = load i32, ptr %q, align 4
+ %cmp2 = icmp eq i32 %load2, 0
+ %iv.next = add i32 %iv, 1
+ br i1 %cmp2, label %exit2, label %loop
+
+exit1:
+ ret i32 %iv
+
+exit2:
+ ret i32 %iv
+}
+
+; Latch is unconditional, already properly structured.
+define void @already_rotated(ptr %p, i32 %n) {
+; CHECK-LABEL: @already_rotated(
+; CHECK-NEXT: entry:
+; CHECK-NEXT: br label [[LOOP:%.*]]
+; CHECK: loop:
+; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT: store i32 [[IV]], ptr [[P:%.*]], align 4
+; CHECK-NEXT: [[IV_NEXT]] = add nuw i32 [[IV]], 1
+; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[IV_NEXT]], [[N:%.*]]
+; CHECK-NEXT: br i1 [[CMP]], label [[EXIT:%.*]], label [[LOOP]]
+; CHECK: exit:
+; CHECK-NEXT: ret void
+;
+entry:
+ br label %loop
+
+loop:
+ %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
+ store i32 %iv, ptr %p, align 4
+ %iv.next = add nuw i32 %iv, 1
+ %cmp = icmp eq i32 %iv.next, %n
+ br i1 %cmp, label %exit, label %loop
+
+exit:
+ ret void
+}
diff --git a/llvm/test/Transforms/PhaseOrdering/AArch64/loop-rotate-to-enable-unrolling-and-vectorization.ll b/llvm/test/Transforms/PhaseOrdering/AArch64/loop-rotate-to-enable-unrolling-and-vectorization.ll
new file mode 100644
index 0000000000000..e23d1426d7363
--- /dev/null
+++ b/llvm/test/Transforms/PhaseOrdering/AArch64/loop-rotate-to-enable-unrolling-and-vectorization.ll
@@ -0,0 +1,164 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 6
+; RUN: opt -S -O3 %s | FileCheck %s
+
+target triple = "aarch64-unknown-linux-gnu"
+
+; Test that a search loop with computable header exit gets rotated and
+; runtime-unrolled at -O3.
+define ptr @search_loop_unrolled(ptr %begin, ptr %end, i8 %val) {
+; CHECK-LABEL: define ptr @search_loop_unrolled(
+; CHECK-SAME: ptr readnone captures(address) [[BEGIN:%.*]], ptr readonly captures(address, ret: address, provenance) [[END:%.*]], i8 [[VAL:%.*]]) local_unnamed_addr #[[ATTR0:[0-9]+]] {
+; CHECK-NEXT: [[ENTRY:.*]]:
+; CHECK-NEXT: [[CMP_ENTRY:%.*]] = icmp eq ptr [[BEGIN]], [[END]]
+; CHECK-NEXT: [[PTR_DEC1:%.*]] = getelementptr inbounds i8, ptr [[END]], i64 -1
+; CHECK-NEXT: [[CMP_END2:%.*]] = icmp eq ptr [[PTR_DEC1]], [[BEGIN]]
+; CHECK-NEXT: [[OR_COND:%.*]] = select i1 [[CMP_ENTRY]], i1 true, i1 [[CMP_END2]]
+; CHECK-NEXT: br i1 [[OR_COND]], label %[[COMMON_RET:.*]], label %[[FOR_COND:.*]]
+; CHECK: [[FOR_COND]]:
+; CHECK-NEXT: [[END5:%.*]] = ptrtoint ptr [[END]] to i64
+; CHECK-NEXT: [[BEGIN6:%.*]] = ptrtoint ptr [[BEGIN]] to i64
+; CHECK-NEXT: [[TMP0:%.*]] = xor i64 [[BEGIN6]], -1
+; CHECK-NEXT: [[TMP1:%.*]] = add i64 [[TMP0]], [[END5]]
+; CHECK-NEXT: [[TMP2:%.*]] = freeze i64 [[TMP1]]
+; CHECK-NEXT: [[TMP3:%.*]] = add i64 [[TMP2]], -1
+; CHECK-NEXT: [[XTRAITER:%.*]] = and i64 [[TMP2]], 3
+; CHECK-NEXT: [[LCMP_MOD_NOT:%.*]] = icmp eq i64 [[XTRAITER]], 0
+; CHECK-NEXT: br i1 [[LCMP_MOD_NOT]], label %[[FOR_BODY_PROL_LOOPEXIT:.*]], label %[[FOR_BODY_PROL:.*]]
+; CHECK: [[FOR_BODY_PROL]]:
+; CHECK-NEXT: [[PTR_DEC5:%.*]] = phi ptr [ [[PTR_DEC4:%.*]], %[[FOR_COND_PROL:.*]] ], [ [[PTR_DEC1]], %[[FOR_COND]] ]
+; CHECK-NEXT: [[PROL_ITER:%.*]] = phi i64 [ [[PROL_ITER_NEXT:%.*]], %[[FOR_COND_PROL]] ], [ 0, %[[FOR_COND]] ]
+; CHECK-NEXT: [[LOAD_PROL:%.*]] = load i8, ptr [[PTR_DEC5]], align 1
+; CHECK-NEXT: [[CMP_VAL_PROL:%.*]] = icmp eq i8 [[LOAD_PROL]], [[VAL]]
+; CHECK-NEXT: br i1 [[CMP_VAL_PROL]], label %[[COMMON_RET]], label %[[FOR_COND_PROL]]
+; CHECK: [[FOR_COND_PROL]]:
+; CHECK-NEXT: [[PTR_DEC4]] = getelementptr inbounds i8, ptr [[PTR_DEC5]], i64 -1
+; CHECK-NEXT: [[PROL_ITER_NEXT]] = add i64 [[PROL_ITER]], 1
+; CHECK-NEXT: [[PROL_ITER_CMP_NOT:%.*]] = icmp eq i64 [[PROL_ITER_NEXT]], [[XTRAITER]]
+; CHECK-NEXT: br i1 [[PROL_ITER_CMP_NOT]], label %[[FOR_BODY_PROL_LOOPEXIT]], label %[[FOR_BODY_PROL]], !llvm.loop [[LOOP0:![0-9]+]]
+; CHECK: [[FOR_BODY_PROL_LOOPEXIT]]:
+; CHECK-NEXT: [[PTR_DEC3_UNR:%.*]] = phi ptr [ [[PTR_DEC1]], %[[FOR_COND]] ], [ [[PTR_DEC4]], %[[FOR_COND_PROL]] ]
+; CHECK-NEXT: [[TMP4:%.*]] = icmp ult i64 [[TMP3]], 3
+; CHECK-NEXT: br i1 [[TMP4]], label %[[COMMON_RET]], label %[[FOR_BODY:.*]]
+; CHECK: [[FOR_COND1:.*]]:
+; CHECK-NEXT: [[PTR_DEC:%.*]] = getelementptr inbounds i8, ptr [[PTR_DEC3:%.*]], i64 -1
+; CHECK-NEXT: [[LOAD_1:%.*]] = load i8, ptr [[PTR_DEC]], align 1
+; CHECK-NEXT: [[CMP_VAL_1:%.*]] = icmp eq i8 [[LOAD_1]], [[VAL]]
+; CHECK-NEXT: br i1 [[CMP_VAL_1]], label %[[COMMON_RET_LOOPEXIT_UNR_LCSSA_LOOPEXIT_SPLIT_LOOP_EXIT14:.*]], label %[[FOR_COND_1:.*]]
+; CHECK: [[FOR_COND_1]]:
+; CHECK-NEXT: [[PTR_DEC_1:%.*]] = getelementptr inbounds i8, ptr [[PTR_DEC3]], i64 -2
+; CHECK-NEXT: [[LOAD_2:%.*]] = load i8, ptr [[PTR_DEC_1]], align 1
+; CHECK-NEXT: [[CMP_VAL_2:%.*]] = icmp eq i8 [[LOAD_2]], [[VAL]]
+; CHECK-NEXT: br i1 [[CMP_VAL_2]], label %[[COMMON_RET_LOOPEXIT_UNR_LCSSA_LOOPEXIT_SPLIT_LOOP_EXIT12:.*]], label %[[FOR_COND_2:.*]]
+; CHECK: [[FOR_COND_2]]:
+; CHECK-NEXT: [[PTR_DEC_2:%.*]] = getelementptr inbounds i8, ptr [[PTR_DEC3]], i64 -3
+; CHECK-NEXT: [[LOAD_3:%.*]] = load i8, ptr [[PTR_DEC_2]], align 1
+; CHECK-NEXT: [[CMP_VAL_3:%.*]] = icmp eq i8 [[LOAD_3]], [[VAL]]
+; CHECK-NEXT: br i1 [[CMP_VAL_3]], label %[[COMMON_RET_LOOPEXIT_UNR_LCSSA_LOOPEXIT_SPLIT_LOOP_EXIT10:.*]], label %[[FOR_COND_3:.*]]
+; CHECK: [[FOR_COND_3]]:
+; CHECK-NEXT: [[PTR_DEC_3:%.*]] = getelementptr inbounds i8, ptr [[PTR_DEC3]], i64 -4
+; CHECK-NEXT: [[CMP_END:%.*]] = icmp eq ptr [[PTR_DEC_3]], [[BEGIN]]
+; CHECK-NEXT: br i1 [[CMP_END]], label %[[COMMON_RET]], label %[[FOR_BODY]]
+; CHECK: [[FOR_BODY]]:
+; CHECK-NEXT: [[PTR_DEC3]] = phi ptr [ [[PTR_DEC_3]], %[[FOR_COND_3]] ], [ [[PTR_DEC3_UNR]], %[[FOR_BODY_PROL_LOOPEXIT]] ]
+; CHECK-NEXT: [[LOAD:%.*]] = load i8, ptr [[PTR_DEC3]], align 1
+; CHECK-NEXT: [[CMP_VAL:%.*]] = icmp eq i8 [[LOAD]], [[VAL]]
+; CHECK-NEXT: br i1 [[CMP_VAL]], label %[[COMMON_RET]], label %[[FOR_COND1]]
+; CHECK: [[COMMON_RET_LOOPEXIT_UNR_LCSSA_LOOPEXIT_SPLIT_LOOP_EXIT10]]:
+; CHECK-NEXT: [[PTR_DEC_2_LE:%.*]] = getelementptr inbounds i8, ptr [[PTR_DEC3]], i64 -3
+; CHECK-NEXT: br label %[[COMMON_RET]]
+; CHECK: [[COMMON_RET_LOOPEXIT_UNR_LCSSA_LOOPEXIT_SPLIT_LOOP_EXIT12]]:
+; CHECK-NEXT: [[PTR_DEC_1_LE:%.*]] = getelemen...
[truncated]
|
nikic
reviewed
Mar 19, 2026
| @@ -0,0 +1,124 @@ | |||
| ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py | |||
| ; RUN: opt -S -passes='loop(loop-rotate<header-duplication>)' %s | FileCheck %s --check-prefix=CHECK | |||
Contributor
There was a problem hiding this comment.
Missing the check-exit-count pass option?
Contributor
Author
There was a problem hiding this comment.
should be fixed now, thanks
🐧 Linux x64 Test Results
✅ The build succeeded and all tests passed. |
🪟 Windows x64 Test Results
✅ The build succeeded and all tests passed. |
Most loop transformations, like unrolling and vectorization, expect the latch branch to be countable. Allow rotation, if it turns the latch from uncountable to countable. This use SCEV to check for countable exits, if CheckExitCount set. Currently it is not set for the LPM1 run (where SCEV is not used by other passes), only in LPM. With that compile-time impact is mostly neutral https://llvm-compile-time-tracker.com/compare.php?from=eba342d0ba930a404a026c80aada51c43974f0db&to=2e676337b45fae63ce9498116d8e6e43772363c5&stat=instructions:u ClamAV is consistently slower (~+0.15%) and 7zip faster in most cases (~-0.13%) Across a large test set based on C/C++ workloads, this rotates ~0.8% more loops with ~2.68M rotated loops. For the test set, ~2.7% more loops are runtime-unrolled and +6.36% more early exit loops vectorized on ARM64 macOS. This fixes a regression where std::ranges::find_last loops stopped being runtime-unrolled after 5f648c3 which changed the loop structure so we stopped rotating. https://clang.godbolt.org/z/6baeE1av6 Based on llvm#162654.
fhahn
force-pushed
the
loop-rotate-countable
branch
from
March 19, 2026 12:46
249ac02 to
adc04f9
Compare
nikic
approved these changes
Mar 19, 2026
nikic
left a comment
nikic
left a comment
Contributor
There was a problem hiding this comment.
LGTM
It's unfortunate that this rotation happens late, but I guess this is the best we can easily do.
fhahn
enabled auto-merge (squash)
March 20, 2026 09:55
llvm-sync Bot
pushed a commit
to arm/arm-toolchain
that referenced
this pull request
Mar 20, 2026
…itability (#187483) Most loop transformations, like unrolling and vectorization, expect the latch branch to be countable. Allow rotation, if it turns the latch from uncountable to countable. This use SCEV to check for countable exits, if CheckExitCount set. Currently it is not set for the LPM1 run (where SCEV is not used by other passes), only in LPM. With that compile-time impact is mostly neutral https://llvm-compile-time-tracker.com/compare.php?from=eba342d0ba930a404a026c80aada51c43974f0db&to=2e676337b45fae63ce9498116d8e6e43772363c5&stat=instructions:u ClamAV is consistently slower (~+0.15%) and 7zip faster in most cases (~-0.13%) Across a large test set based on C/C++ workloads, this rotates ~0.8% more loops with ~2.68M rotated loops. For the test set, ~2.7% more loops are runtime-unrolled and +6.36% more early exit loops vectorized on ARM64 macOS. This fixes a regression where std::ranges::find_last loops stopped being runtime-unrolled after llvm/llvm-project@5f648c3 which changed the loop structure so we stopped rotating. https://clang.godbolt.org/z/6baeE1av6 Based on llvm/llvm-project#162654. Co-authored-by: Marek Sedláček <[email protected]> PR: llvm/llvm-project#187483
fhahn
added a commit
to fhahn/llvm-project
that referenced
this pull request
Mar 28, 2026
…lvm#187483) Most loop transformations, like unrolling and vectorization, expect the latch branch to be countable. Allow rotation, if it turns the latch from uncountable to countable. This use SCEV to check for countable exits, if CheckExitCount set. Currently it is not set for the LPM1 run (where SCEV is not used by other passes), only in LPM. With that compile-time impact is mostly neutral https://llvm-compile-time-tracker.com/compare.php?from=eba342d0ba930a404a026c80aada51c43974f0db&to=2e676337b45fae63ce9498116d8e6e43772363c5&stat=instructions:u ClamAV is consistently slower (~+0.15%) and 7zip faster in most cases (~-0.13%) Across a large test set based on C/C++ workloads, this rotates ~0.8% more loops with ~2.68M rotated loops. For the test set, ~2.7% more loops are runtime-unrolled and +6.36% more early exit loops vectorized on ARM64 macOS. This fixes a regression where std::ranges::find_last loops stopped being runtime-unrolled after llvm@5f648c3 which changed the loop structure so we stopped rotating. https://clang.godbolt.org/z/6baeE1av6 Based on llvm#162654. Co-authored-by: Marek Sedláček <[email protected]> PR: llvm#187483 (cherry-picked from 21f439f)
Aadarsh-Keshri
pushed a commit
to Aadarsh-Keshri/llvm-project
that referenced
this pull request
Apr 1, 2026
…lvm#187483) Most loop transformations, like unrolling and vectorization, expect the latch branch to be countable. Allow rotation, if it turns the latch from uncountable to countable. This use SCEV to check for countable exits, if CheckExitCount set. Currently it is not set for the LPM1 run (where SCEV is not used by other passes), only in LPM. With that compile-time impact is mostly neutral https://llvm-compile-time-tracker.com/compare.php?from=eba342d0ba930a404a026c80aada51c43974f0db&to=2e676337b45fae63ce9498116d8e6e43772363c5&stat=instructions:u ClamAV is consistently slower (~+0.15%) and 7zip faster in most cases (~-0.13%) Across a large test set based on C/C++ workloads, this rotates ~0.8% more loops with ~2.68M rotated loops. For the test set, ~2.7% more loops are runtime-unrolled and +6.36% more early exit loops vectorized on ARM64 macOS. This fixes a regression where std::ranges::find_last loops stopped being runtime-unrolled after llvm@5f648c3 which changed the loop structure so we stopped rotating. https://clang.godbolt.org/z/6baeE1av6 Based on llvm#162654. Co-authored-by: Marek Sedláček <[email protected]> PR: llvm#187483
Contributor
|
we've bisected a non-trivial size increase in -Os builds to this commit, is that expected? |
fhahn
commented
Apr 7, 2026
fhahn
left a comment
fhahn
left a comment
Contributor
Author
There was a problem hiding this comment.
we've bisected a non-trivial size increase in -Os builds to this commit, is that expected?
We should still only rotate if the size heuristics allow it. So the increase from rotation itself should be minor, but there could be downstream effects of rotation enabling additional transformations, which do not properly account for size increase?
Contributor
|
We've encountered what appears to be an infinite runtime with our downstream Arm compiler that we've bisected to this commit. It happens in SolidSands ACE test suite (stress/tcrc8itut.c), and unfortunately it'll be difficult to get a reproducer. As it's a stress test anyway, we can note if this is pathological or showing up in other places. Presently we time out. |
Contributor
|
I've bisected a LoopVectorizer crash (perhaps pre-existing but unlocked after the loop rotation?) to this PR. Minimized reproducer showing the crash at trunk: https://godbolt.org/z/soqMM53T8 Crashes with Symbolized crash at this PR: The setOperand() assertion is failing on an extractvalue instruction. ExtractValueInst only has one operand according to getNumOperands() (the subsequent "operands" - indices - are handled separately), thus it has a bad time with: |
Contributor
I reduced my test case further (https://godbolt.org/z/qGx86MnT7) into an input that fails even prior to this PR. I'll bisect further to find the true root cause. |
markrvmurray
pushed a commit
to markrvmurray/llvm-mc6809
that referenced
this pull request
Jun 14, 2026
…#187483) Most loop transformations, like unrolling and vectorization, expect the latch branch to be countable. Allow rotation, if it turns the latch from uncountable to countable. This use SCEV to check for countable exits, if CheckExitCount set. Currently it is not set for the LPM1 run (where SCEV is not used by other passes), only in LPM. With that compile-time impact is mostly neutral https://llvm-compile-time-tracker.com/compare.php?from=eba342d0ba930a404a026c80aada51c43974f0db&to=2e676337b45fae63ce9498116d8e6e43772363c5&stat=instructions:u ClamAV is consistently slower (~+0.15%) and 7zip faster in most cases (~-0.13%) Across a large test set based on C/C++ workloads, this rotates ~0.8% more loops with ~2.68M rotated loops. For the test set, ~2.7% more loops are runtime-unrolled and +6.36% more early exit loops vectorized on ARM64 macOS. This fixes a regression where std::ranges::find_last loops stopped being runtime-unrolled after llvm/llvm-project@5f648c3 which changed the loop structure so we stopped rotating. https://clang.godbolt.org/z/6baeE1av6 Based on llvm/llvm-project#162654. Co-authored-by: Marek Sedláček <[email protected]> PR: llvm/llvm-project#187483
delcypher
added a commit
to delcypher/apple-llvm-project
that referenced
this pull request
Jun 24, 2026
…s-structs(|-no-bringup-missing-checks.c) failures The CHECK lines for the `access_struct_1_checks_needed` function in these two tests expected an un-rotated loop shape. After cherry-picking `b272c36f15b0` (*[LoopRotate] Use SCEV exit counts to improve rotation profitability (llvm#187483)*), this loop now gets rotated, and the previous CHECK lines no longer match. This was verified by capturing the canonical `default<O2>` pipeline string from `opt --print-pipeline-passes` and re-running it after flipping the LPM `loop-rotate<...;check-exit-count>` parameter to `no-check-exit-count`. With the new behavior disabled the un-rotated shape comes back; with it enabled (the post-cherry-pick default) the rotated shape is produced. CHECK lines were regenerated with `llvm/utils/update_cc_test_checks.py` using the in-tree clang, after picking up `c35b15eef009` (*[UTC] Fix bounds safety default checks in update_cc_test_checks.py*) so the script no longer clobbers tests that explicitly pass `-fno-bounds-safety-bringup-missing-checks=all`. Assisted-by: Claude Code rdar://179378974
This was referenced Jun 24, 2026
devincoughlin
pushed a commit
to swiftlang/llvm-project
that referenced
this pull request
Jun 25, 2026
…s-structs(|-no-bringup-missing-checks.c) failures The CHECK lines for the `access_struct_1_checks_needed` function in these two tests expected an un-rotated loop shape. After cherry-picking `b272c36f15b0` (*[LoopRotate] Use SCEV exit counts to improve rotation profitability (llvm#187483)*), this loop now gets rotated, and the previous CHECK lines no longer match. This was verified by capturing the canonical `default<O2>` pipeline string from `opt --print-pipeline-passes` and re-running it after flipping the LPM `loop-rotate<...;check-exit-count>` parameter to `no-check-exit-count`. With the new behavior disabled the un-rotated shape comes back; with it enabled (the post-cherry-pick default) the rotated shape is produced. CHECK lines were regenerated with `llvm/utils/update_cc_test_checks.py` using the in-tree clang, after picking up `c35b15eef009` (*[UTC] Fix bounds safety default checks in update_cc_test_checks.py*) so the script no longer clobbers tests that explicitly pass `-fno-bounds-safety-bringup-missing-checks=all`. Assisted-by: Claude Code rdar://179378974
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
6 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Most loop transformations, like unrolling and vectorization, expect the
latch branch to be countable. Allow rotation, if it turns the latch from
uncountable to countable.
This use SCEV to check for countable exits, if CheckExitCount set.
Currently it is not set for the LPM1 run (where SCEV is not used by
other passes), only in LPM.
With that compile-time impact is mostly neutral
https://llvm-compile-time-tracker.com/compare.php?from=eba342d0ba930a404a026c80aada51c43974f0db&to=2e676337b45fae63ce9498116d8e6e43772363c5&stat=instructions:u
ClamAV is consistently slower (
+0.15%) and 7zip faster in most cases-0.13%)(
Across a large test set based on C/C++ workloads, this rotates ~0.8%
more loops with ~2.68M rotated loops.
For the test set, ~2.7% more loops are runtime-unrolled and +6.36% more
early exit loops vectorized on ARM64 macOS.
This fixes a regression where std::ranges::find_last loops stopped
being runtime-unrolled after 5f648c3 which changed the loop
structure so we stopped rotating.
https://clang.godbolt.org/z/6baeE1av6
Based on #162654.