[llvm-bugs] [Bug 51981] New: Missing SCEV update in LoopRotate results in `isAvailableAtLoopEntry(OrigStartMinusStride, L) && "Must be!"' assertion failures
via llvm-bugs
llvm-bugs at lists.llvm.org
Thu Oct 7 11:25:52 PDT 2021
https://bugs.llvm.org/show_bug.cgi?id=51981
Bug ID: 51981
Summary: Missing SCEV update in LoopRotate results in
`isAvailableAtLoopEntry(OrigStartMinusStride, L) &&
"Must be!"' assertion failures
Product: libraries
Version: trunk
Hardware: PC
OS: Linux
Status: RESOLVED
Severity: enhancement
Priority: P
Component: Loop Optimizer
Assignee: unassignedbugs at nondot.org
Reporter: mikael.holmen at ericsson.com
CC: bjorn.a.pettersson at ericsson.com,
florian_hahn at apple.com, llvm-bugs at lists.llvm.org,
mikael.holmen at ericsson.com
CC: bjorn.a.pettersson at ericsson.com
CC: mikael.holmen at ericsson.com
CC: florian_hahn at apple.com
Resolution: FIXED
Fixed By rG7f93bb4a5827ffce67a469da3ac0e23194538441
Commit(s):
Status: RESOLVED
Summary: Missing SCEV update in LoopRotate results in
`isAvailableAtLoopEntry(OrigStartMinusStride, L) &&
"Must be!"' assertion failures
Created attachment 25297
--> https://bugs.llvm.org/attachment.cgi?id=25297&action=edit
bbi-60782.ll reproducer
llvm commit: 33031545bf
Reproduce with:
opt -passes='loop-mssa(canon-freeze,loop-rotate),function(bounds-checking)' -o
/dev/null bbi-60782.ll
Result:
opt: ../lib/Analysis/ScalarEvolution.cpp:11839: ScalarEvolution::ExitLimit
llvm::ScalarEvolution::howManyLessThans(const llvm::SCEV *, const llvm::SCEV *,
const llvm::Loop *, bool, bool, bool): Assertion
`isAvailableAtLoopEntry(OrigStartMinusStride, L) && "Must be!"' failed.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash
backtrace.
Stack dump:
0. Program arguments: ../../master-github/llvm/build-all/bin/opt
-passes=loop-mssa(canon-freeze,loop-rotate),function(bounds-checking) -o
/dev/null bbi-60782.ll
#0 0x0000000002b58ee3 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int)
(../../master-github/llvm/build-all/bin/opt+0x2b58ee3)
#1 0x0000000002b56b5e llvm::sys::RunSignalHandlers()
(../../master-github/llvm/build-all/bin/opt+0x2b56b5e)
#2 0x0000000002b59266 SignalHandler(int) Signals.cpp:0:0
#3 0x00007fc1dea3c630 __restore_rt sigaction.c:0:0
#4 0x00007fc1dc16f387 raise (/lib64/libc.so.6+0x36387)
#5 0x00007fc1dc170a78 abort (/lib64/libc.so.6+0x37a78)
#6 0x00007fc1dc1681a6 __assert_fail_base (/lib64/libc.so.6+0x2f1a6)
#7 0x00007fc1dc168252 (/lib64/libc.so.6+0x2f252)
#8 0x0000000001bda813 llvm::ScalarEvolution::howManyLessThans(llvm::SCEV
const*, llvm::SCEV const*, llvm::Loop const*, bool, bool, bool)
(../../master-github/llvm/build-all/bin/opt+0x1bda813)
#9 0x0000000001bd433f
llvm::ScalarEvolution::computeExitLimitFromICmp(llvm::Loop const*,
llvm::ICmpInst*, bool, bool, bool)
(../../master-github/llvm/build-all/bin/opt+0x1bd433f)
#10 0x0000000001bd38a8
llvm::ScalarEvolution::computeExitLimitFromCondImpl(llvm::ScalarEvolution::ExitLimitCache&,
llvm::Loop const*, llvm::Value*, bool, bool, bool)
(../../master-github/llvm/build-all/bin/opt+0x1bd38a8)
#11 0x0000000001bd33e7
llvm::ScalarEvolution::computeExitLimitFromCondCached(llvm::ScalarEvolution::ExitLimitCache&,
llvm::Loop const*, llvm::Value*, bool, bool, bool)
(../../master-github/llvm/build-all/bin/opt+0x1bd33e7)
#12 0x0000000001bd2bf0 llvm::ScalarEvolution::computeExitLimit(llvm::Loop
const*, llvm::BasicBlock*, bool)
(../../master-github/llvm/build-all/bin/opt+0x1bd2bf0)
#13 0x0000000001bcf2c0
llvm::ScalarEvolution::computeBackedgeTakenCount(llvm::Loop const*, bool)
(../../master-github/llvm/build-all/bin/opt+0x1bcf2c0)
#14 0x0000000001bcdbd8 llvm::ScalarEvolution::getBackedgeTakenInfo(llvm::Loop
const*) (../../master-github/llvm/build-all/bin/opt+0x1bcdbd8)
#15 0x0000000001bc8d78 llvm::ScalarEvolution::getRangeRef(llvm::SCEV const*,
llvm::ScalarEvolution::RangeSignHint)
(../../master-github/llvm/build-all/bin/opt+0x1bc8d78)
#16 0x0000000001baf687
llvm::ScalarEvolution::proveNoWrapViaConstantRanges(llvm::SCEVAddRecExpr
const*) (../../master-github/llvm/build-all/bin/opt+0x1baf687)
#17 0x0000000001badf63 llvm::ScalarEvolution::getZeroExtendExpr(llvm::SCEV
const*, llvm::Type*, unsigned int)
(../../master-github/llvm/build-all/bin/opt+0x1badf63)
#18 0x0000000001bbcc58 llvm::ScalarEvolution::createSCEV(llvm::Value*)
(../../master-github/llvm/build-all/bin/opt+0x1bbcc58)
#19 0x0000000001bb56a7 llvm::ScalarEvolution::getSCEV(llvm::Value*)
(../../master-github/llvm/build-all/bin/opt+0x1bb56a7)
#20 0x0000000001bbcd87 llvm::ScalarEvolution::createSCEV(llvm::Value*)
(../../master-github/llvm/build-all/bin/opt+0x1bbcd87)
#21 0x0000000001bb56a7 llvm::ScalarEvolution::getSCEV(llvm::Value*)
(../../master-github/llvm/build-all/bin/opt+0x1bb56a7)
#22 0x0000000001bbba5d llvm::ScalarEvolution::createSCEV(llvm::Value*)
(../../master-github/llvm/build-all/bin/opt+0x1bbba5d)
#23 0x0000000001bb56a7 llvm::ScalarEvolution::getSCEV(llvm::Value*)
(../../master-github/llvm/build-all/bin/opt+0x1bb56a7)
#24 0x0000000001bbb316 llvm::ScalarEvolution::createSCEV(llvm::Value*)
(../../master-github/llvm/build-all/bin/opt+0x1bbb316)
#25 0x0000000001bb56a7 llvm::ScalarEvolution::getSCEV(llvm::Value*)
(../../master-github/llvm/build-all/bin/opt+0x1bb56a7)
#26 0x000000000267c432 getBoundsCheckCond(llvm::Value*, llvm::Value*,
llvm::DataLayout const&, llvm::TargetLibraryInfo&,
llvm::ObjectSizeOffsetEvaluator&, llvm::IRBuilder<llvm::TargetFolder,
llvm::IRBuilderDefaultInserter>&, llvm::ScalarEvolution&)
BoundsChecking.cpp:0:0
#27 0x000000000267b5f1 addBoundsChecking(llvm::Function&,
llvm::TargetLibraryInfo&, llvm::ScalarEvolution&) BoundsChecking.cpp:0:0
#28 0x000000000267b2a5 llvm::BoundsCheckingPass::run(llvm::Function&,
llvm::AnalysisManager<llvm::Function>&)
(../../master-github/llvm/build-all/bin/opt+0x267b2a5)
#29 0x0000000002e4117d llvm::detail::PassModel<llvm::Function,
llvm::BoundsCheckingPass, llvm::PreservedAnalyses,
llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&,
llvm::AnalysisManager<llvm::Function>&) crtstuff.c:0:0
#30 0x000000000230d3e5 llvm::PassManager<llvm::Function,
llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&,
llvm::AnalysisManager<llvm::Function>&)
(../../master-github/llvm/build-all/bin/opt+0x230d3e5)
#31 0x0000000000ae684d llvm::detail::PassModel<llvm::Function,
llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >,
llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>
>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) crtstuff.c:0:0
#32 0x0000000002311766 llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&,
llvm::AnalysisManager<llvm::Module>&)
(../../master-github/llvm/build-all/bin/opt+0x2311766)
#33 0x00000000007a47ad llvm::detail::PassModel<llvm::Module,
llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses,
llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&,
llvm::AnalysisManager<llvm::Module>&) crtstuff.c:0:0
#34 0x000000000230c528 llvm::PassManager<llvm::Module,
llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&,
llvm::AnalysisManager<llvm::Module>&)
(../../master-github/llvm/build-all/bin/opt+0x230c528)
#35 0x000000000079bfec llvm::runPassPipeline(llvm::StringRef, llvm::Module&,
llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*,
llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef,
llvm::ArrayRef<llvm::StringRef>, llvm::opt_tool::OutputKind,
llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool)
(../../master-github/llvm/build-all/bin/opt+0x79bfec)
#36 0x00000000007af3d6 main
(../../master-github/llvm/build-all/bin/opt+0x7af3d6)
#37 0x00007fc1dc15b555 __libc_start_main (/lib64/libc.so.6+0x22555)
#38 0x000000000079742c _start
(../../master-github/llvm/build-all/bin/opt+0x79742c)
Abort
--- Comment #1 from bjorn.a.pettersson at ericsson.com ---
Just some additional info.
It also fails when using different loop pass managers like this:
-passes='loop-mssa(canon-freeze),loop-mssa(loop-rotate),function(bounds-checking)'
If we invalidate scalar-evolution after canon-freeze like this
-passes='loop-mssa(canon-freeze),invalidate<scalar-evolution>,loop-mssa(loop-rotate),function(bounds-checking)'
then it works fine (and also if we split this into running opt twice with
canon-freeze in the first run and the rest of the pipeline in a subsequent
run). So maybe it is canon-freeze that isn't updating scalar-evolution analysis
correctly.
--- Comment #2 from bjorn.a.pettersson at ericsson.com ---
Created attachment 25305
--> https://bugs.llvm.org/attachment.cgi?id=25305&action=edit
slightly simplified reproducer
Given the bbi-60782-mod.ll reproducer I can see some problems when comparing
the SCEV expressions printed after LoopRotate for
opt
-passes='print<scalar-evolution>,loop(loop-rotate),print<scalar-evolution>' -o
/dev/null bbi-60782-mod.ll
and
opt
-passes='print<scalar-evolution>,loop(loop-rotate),invalidate<scalar-evolution>,print<scalar-evolution>'
-o /dev/null bbi-60782-mod.ll
I see diffs like these
32c32
< --> (trunc i32 %div210 to i16) U: full-set S: full-set Exits:
<<Unknown>> LoopDispositions: { %for.body215.lr.ph: Variant,
%for.body215: Invariant }
---
> --> (trunc i32 %div2102 to i16) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.body215.lr.ph: Variant, %for.body215: Invariant }
34c34
< --> {(trunc i32 %div210 to i16),+,1}<%for.body215> U: full-set S: full-set
Exits: (-1 + (700 umax (1 + (trunc i32 %div210 to i16))))
LoopDispositions: { %for.body215: Computable, %for.body215.lr.ph: Variant }
---
> --> {(trunc i32 %div2102 to i16),+,1}<%for.body215> U: full-set S: full-set Exits: (-1 + (700 umax (1 + (trunc i32 %div2102 to i16)))) LoopDispositions: { %for.body215: Computable, %for.body215.lr.ph: Variant }
My interpretation of this is that we get a different result if invalidating and
recalculating SCEV, so we either got a stale SCEV analysis outside the Loop
Pass Manager, or LoopRotate isn't updating SCEV properly.
Hacking into LoopRotatePass::run and adding a line such as
AR.SE.print(dbgs());
before the return shows the same expressions as when not recalculating SCEV
after LoopRotate. So I believe that indicates that it is LoopRotate (or rather
LoopRotateUtils) that isn't updating SCEV properly.
--- Comment #3 from bjorn.a.pettersson at ericsson.com ---
After some more experiments it seems like replacing
SE->forgetTopmostLoop(L);
by
SE->forgetAllLoops();
in LoopRotate::rotateLoop makes a difference. So is it perhaps something that
isn't cleaned up properly when only using forgetTopmostLoop?
I also tried to just do some additional cleanups in forgetTopmostLoop that
normally is done by fogetAllLoops. And it looks like adding
ValueExprMap.clear();
in the beginning of ScalarEvolution::forgetLoop would be enough to get the same
result as when forgetting all loops.
Here I feel a bit lost however, so would be nice if someone with knowledge
about ScalarEvolution internals could give some hints, or take a look at this.
--- Comment #4 from bjorn.a.pettersson at ericsson.com ---
Looking at legacy PM implemenation of LoopRotate it looks like it did not
preserve ScalarEvolution. So I wonder if anyone actually verified that letting
the new PM version preserve ScalarEvolution was OK when porting the pass to the
new PM.
And there are comments in LoopRotationUtils.cpp indicating that there might be
more problems lingering related to missing SCEV updates:
...
/// I don't believe this invalidates SCEV.
bool LoopRotate::simplifyLoopLatch(Loop *L) {
...
And this bug indicates that the current attempt to forget SCEV for the
currently rotated loop nest isn't enough.
All this makes me think that a first step might be to make sure ScalarEvolution
analysis is invalidated if the pass made any changes. And then someone would
need to sit down and ensure that the pass actually is preserving
ScalarEvolution properly to avoid this kind of bugs.
--- Comment #5 from bjorn.a.pettersson at ericsson.com ---
(In reply to bjorn.a.pettersson from comment #4)
> Looking at legacy PM implemenation of LoopRotate it looks like it did not
> preserve ScalarEvolution. So I wonder if anyone actually verified that
> letting the new PM version preserve ScalarEvolution was OK when porting the
> pass to the new PM.
This was not true, legacy PM do preserve ScalarEvolution through the
getLoopAnalysisUsage helper.
--- Comment #6 from bjorn.a.pettersson at ericsson.com ---
So the crash can be seen also with legacy PM by running:
opt -enable-new-pm=0 -canon-freeze -loop-rotate -bounds-checking -o -
bbi-60782-mod.ll -S
--- Comment #7 from bjorn.a.pettersson at ericsson.com ---
Not sure if it really makes sense, but today LoopRotate::rotateLoop is doing
if (SE)
SE->forgetTopmostLoop(L);
to drop SCEV knowledge about the loop nest before doing the actual rotation.
If I also add another
if (SE)
SE->forgetTopmostLoop(L);
after having done the rotation (L is updated to point to the rotate loop during
the transform), then some additional values are forgotten and the reproducer no
longer crashes.
No idea if that just happens to work for these reproducers, or if that is
exactly what is missing. My reasoning for testing such a thing was that I
figured that the rotation could end up making some values previously not
belonging to the loop L being part of the loop after the rotation (thus only
forgetting things before the rotation wouldn't be enough).
Given my lack of real motivation for the above, I guess it still would be safer
to forget all loops at the end of LoopRotate in case any loops were rotated
(possibly with a slightly higher compiler time cost).
--- Comment #8 from bjorn.a.pettersson at ericsson.com ---
An attempt to fix this: https://reviews.llvm.org/D110813
--- Comment #9 from bjorn.a.pettersson at ericsson.com ---
Should be fixed by rG7f93bb4a5827ffce67a469da3ac0e23194538441
(https://reviews.llvm.org/D110813).
--
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20211007/e9e51dc1/attachment-0001.html>
More information about the llvm-bugs
mailing list