[SCEV] Fold (C1 * A /u C2) -> A /u (C2 /u C1), if C2 > C1. #157656
Merged
Conversation
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
llvmbot
added
llvm:analysis
|
@llvm/pr-subscribers-llvm-analysis @llvm/pr-subscribers-llvm-transforms Author: Florian Hahn (fhahn) ChangesIf C2 >u C1 and C1 >u 1, fold to A /u (C2 /u C1). Depends on #157555. (included in PR) Alive2 Proof: https://alive2.llvm.org/ce/z/BWvQYN Full diff: https://github.com/llvm/llvm-project/pull/157656.diff 3 Files Affected:
diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index 34e497d9ea3cb..9f5b33f50cc0b 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -3217,15 +3217,25 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
}
// Try to fold (C1 * D /u C2) -> C1/C2 * D, if C1 and C2 are powers-of-2,
- // D is a multiple of C2, and C1 is a multiple of C1.
+ // D is a multiple of C2, and C1 is a multiple of C2. If C2 is a multiple
+ // of C1, fold to (D /u (C2 /u C1)).
const SCEV *D;
+ APInt C1V = LHSC->getAPInt();
+ // If C1 is negative, try (-1 * abs(C1)) instead.
+ if (C1V.isNegative() && !C1V.isMinSignedValue())
+ C1V = C1V.abs();
const SCEVConstant *C2;
- const APInt &LHSV = LHSC->getAPInt();
- if (LHSV.isPowerOf2() &&
+ if (C1V.isPowerOf2() &&
match(Ops[1], m_scev_UDiv(m_SCEV(D), m_SCEVConstant(C2))) &&
- C2->getAPInt().isPowerOf2() && LHSV.uge(C2->getAPInt()) &&
- LHSV.logBase2() <= getMinTrailingZeros(D)) {
- return getMulExpr(getUDivExpr(LHSC, C2), D);
+ C2->getAPInt().isPowerOf2() &&
+ C1V.logBase2() <= getMinTrailingZeros(D)) {
+ const SCEV *NewMul = nullptr;
+ if (C1V.uge(C2->getAPInt()))
+ NewMul = getMulExpr(getUDivExpr(getConstant(C1V), C2), D);
+ else if (C1V.ugt(1))
+ NewMul = getUDivExpr(D, getUDivExpr(C2, getConstant(C1V)));
+ if (NewMul)
+ return C1V == LHSC->getAPInt() ? NewMul : getNegativeSCEV(NewMul);
}
}
}
diff --git a/llvm/test/Analysis/ScalarEvolution/mul-udiv-folds.ll b/llvm/test/Analysis/ScalarEvolution/mul-udiv-folds.ll
index dfaf0c95bc2f8..1d34706baadeb 100644
--- a/llvm/test/Analysis/ScalarEvolution/mul-udiv-folds.ll
+++ b/llvm/test/Analysis/ScalarEvolution/mul-udiv-folds.ll
@@ -21,9 +21,9 @@ define void @udiv4_and_udiv2(i1 %c, ptr %A) {
; CHECK-NEXT: %gep.8 = getelementptr i8, ptr %A, i64 %iv
; CHECK-NEXT: --> {(((zext i32 %start to i64) /u 4) + %A),+,1}<%loop> U: full-set S: full-set Exits: (((zext i32 %start to i64) /u 2) + %A) LoopDispositions: { %loop: Computable }
; CHECK-NEXT: %gep.16 = getelementptr i16, ptr %A, i64 %iv
-; CHECK-NEXT: --> {((2 * ((zext i32 %start to i64) /u 4))<nuw><nsw> + %A),+,2}<%loop> U: full-set S: full-set Exits: ((zext i32 %start to i64) + %A) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT: --> {(((zext i32 %start to i64) /u 2) + %A),+,2}<%loop> U: full-set S: full-set Exits: ((zext i32 %start to i64) + %A) LoopDispositions: { %loop: Computable }
; CHECK-NEXT: %gep.32 = getelementptr i32, ptr %A, i64 %iv
-; CHECK-NEXT: --> {((zext i32 %start to i64) + %A),+,4}<%loop> U: full-set S: full-set Exits: ((3 * (zext i32 %start to i64))<nuw><nsw> + (-4 * ((zext i32 %start to i64) /u 4))<nsw> + %A) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT: --> {((zext i32 %start to i64) + %A),+,4}<%loop> U: full-set S: full-set Exits: ((2 * (zext i32 %start to i64))<nuw><nsw> + %A) LoopDispositions: { %loop: Computable }
; CHECK-NEXT: %gep.40 = getelementptr <{ i32, i8 }>, ptr %A, i64 %iv
; CHECK-NEXT: --> {((5 * ((zext i32 %start to i64) /u 4))<nuw><nsw> + %A),+,5}<%loop> U: full-set S: full-set Exits: ((5 * ((zext i32 %start to i64) /u 2))<nuw><nsw> + %A) LoopDispositions: { %loop: Computable }
; CHECK-NEXT: %gep.48 = getelementptr <{ i32, i16 }>, ptr %A, i64 %iv
diff --git a/llvm/test/Transforms/LoopStrengthReduce/duplicated-phis.ll b/llvm/test/Transforms/LoopStrengthReduce/duplicated-phis.ll
index cee8c8abdb450..c59f7d9c2a41a 100644
--- a/llvm/test/Transforms/LoopStrengthReduce/duplicated-phis.ll
+++ b/llvm/test/Transforms/LoopStrengthReduce/duplicated-phis.ll
@@ -18,8 +18,7 @@ define i64 @test_duplicated_phis(i64 noundef %N) {
; CHECK: [[FOR_BODY_PREHEADER_NEW]]:
; CHECK-NEXT: [[UNROLL_ITER:%.*]] = and i64 [[MUL]], -4
; CHECK-NEXT: [[TMP4:%.*]] = add i64 [[UNROLL_ITER]], -4
-; CHECK-NEXT: [[TMP5:%.*]] = lshr i64 [[TMP4]], 2
-; CHECK-NEXT: [[TMP3:%.*]] = shl nuw nsw i64 [[TMP5]], 1
+; CHECK-NEXT: [[TMP3:%.*]] = lshr i64 [[TMP4]], 1
; CHECK-NEXT: [[LSR_IV_NEXT:%.*]] = sub i64 -3, [[TMP3]]
; CHECK-NEXT: br label %[[FOR_BODY:.*]]
; CHECK: [[FOR_BODY]]:
|
fhahn
force-pushed
the
scev-div-larger-than-mul
branch
from
9881292 to
86bb7d6
Compare
nikic
approved these changes
Sep 10, 2025
There was a problem hiding this comment.
Could assert this, as C1 == 0, and C1 == 1 must be folded away earlier.
There was a problem hiding this comment.
Done. This required excluding C1 = -1 above, otherwise we would end up with -1 * 1, triggering the assert
If C2 >u C1 and C1 >u 1, fold to A /u (C2 /u C1). Depends on llvm#157555. Alive2 Proof: https://alive2.llvm.org/ce/z/BWvQYN
fhahn
force-pushed
the
scev-div-larger-than-mul
branch
from
86bb7d6 to
5764262
Compare
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/162/builds/30895 Here is the relevant piece of the build log for the reference |
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/59/builds/24048 Here is the relevant piece of the build log for the reference |
llvm-sync bot
pushed a commit
to arm/arm-toolchain
that referenced
this pull request
Sep 11, 2025
… (#157656) If C2 >u C1 and C1 >u 1, fold to A /u (C2 /u C1). Depends on llvm/llvm-project#157555. Alive2 Proof: https://alive2.llvm.org/ce/z/BWvQYN PR: llvm/llvm-project#157656
|
I'm seeing some segfaults in Rust that root-cause to this change, I'll try and figure out more later. |
|
We've started seeing crashes in the rust compiler when using head LLVM, and it bisected to this commit. Unfortunately I'm not sure how to put together a useful reproducer. It's possible there's a bug here or that it simply revealed one elsewhere. |
|
Crashes in LLVM directly or a mis-compile that is causing the crash? |
|
We're seeing one of the msan tests fail after this patch: MemorySanitizer-AARCH64 :: preinit_array.cpp, and I've bisected the failure to this patch. I'm guessing the other failures are somewhat related. This is a normal aarch64 linux build of the toolchain and runtimes using the Fuchsia.cmake cache file. Its a pretty vanilla build otherwise. The CMake can be found here: https://logs.chromium.org/logs/fuchsia/buildbucket/cr-buildbucket/8704035006372869713/+/u/clang/configure/l_execution_details |
Looks like rustc crashing in non-LLVM code, so likely a miscompile rather than LLVM crash |
Yeah I think the bisect logic failed and it's a different patch. Sorry for the noise. The Rust problem may be unrelated. Thanks @aeubanks for pointing this out. |
|
Was the talk about miscompiles above here false alarm or real problems? We're seeing a runtime failure downstream with this patch that I think is a miscompile but we haven't been able to pinpoint what's happening, so wondering what the status really is about these other previous reports. |
|
@mikaelholmen I think it sounds like there may be a potential mis-compile when bootstrapping the Rust compiler IIUC. We can revert the PR, but without reproducer it is impossible to figure out exactly where the issue is. |
|
Yes I understand. I think something breaks in LSR in llc for our out-of-tree target with the patch, but I'm not sure what and even with the reduced C reproducer I have it's hard to understand. And the code diff I see after LSR in llc does not appear if I run LSR alone in opt so there apparently must be some state present from earlier passes for the difference to appear. We'll continue digging next week but unfortunately the whole team is off Monday-Tuesday so progress from us (if any) will probably not happen until second half of next week. Hopefully someone else can beat us to it and come up with a reproducer earlier. |
|
Sorry, life got in the way and I'm just back to this. Yes, it looks like it's probably a miscompile leading to a segfault in rustc: it only happens in a stage2 compiler, and the tracebacks don't seem to have any LLVM frames in them. I'm not really sure what to do in terms of reducing the failure tho. rustc is pretty big. |
|
We're crashing in That comes from rustc_ty_utils-c1870303faf57b40.rustc_ty_utils.4038986b86944b28-cgu.15.rcgu.bc.gz and the function has a large diff after this change. It's still not entirely clear what's going wrong though; we'll keep looking. |
llvm-sync bot
pushed a commit
to arm/arm-toolchain
that referenced
this pull request
Sep 16, 2025
…C2 > C1." (#158328) Reverts llvm/llvm-project#157656 There are multiple reports that this is causing miscompiles in the MSan test suite after bootstrapping and that this is causing miscompiles in rustc. Let's revert for now, and work to capture a reproducer next week.
|
A reduced test case: After this change, loop-reduce will remove the which is not valid (consider for example |
llvm-sync bot
pushed a commit
to arm/arm-toolchain
that referenced
this pull request
Sep 17, 2025
Add additional test coverage for llvm/llvm-project#157656 covering cases where the dividend is not a multiple of the divisor, causing the revert of 70012fd.
fhahn
added a commit
that referenced
this pull request
Sep 17, 2025
…158328) This reverts commit fd58f23. The recommit contains an extra check to make sure that D is a multiple of C2, if C2 > C1. This fixes the issue causing the revert fd58f23. Tests have been added in 6a726e9. Original message: If C2 >u C1 and C1 >u 1, fold to A /u (C2 /u C1). Depends on #157555. Alive2 Proof: https://alive2.llvm.org/ce/z/BWvQYN PR: #157656
llvm-sync bot
pushed a commit
to arm/arm-toolchain
that referenced
this pull request
Sep 17, 2025
… C2 > C1." (#158328) This reverts commit fd58f23. The recommit contains an extra check to make sure that D is a multiple of C2, if C2 > C1. This fixes the issue causing the revert fd58f23. Tests have been added in 6a726e9. Original message: If C2 >u C1 and C1 >u 1, fold to A /u (C2 /u C1). Depends on llvm/llvm-project#157555. Alive2 Proof: https://alive2.llvm.org/ce/z/BWvQYN PR: llvm/llvm-project#157656
|
I've verified that the testcase previously failing for us with the original patch still works after the reapplied patch including the fix. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
10 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.
If C2 >u C1 and C1 >u 1, fold to A /u (C2 /u C1).
Depends on #157555.
Alive2 Proof: https://alive2.llvm.org/ce/z/BWvQYN