Differential D71539
[SCEV] Look through trivial PHIs. Authored by fhahn on Dec 16 2019, 4:02 AM.
Details Now that SCEVExpander can preserve LCSSA form, This increases precision of the analysis in some cases.
Diff Detail
Event TimelineComment Actions Some of the tests added in llvm/test/Analysis/ScalarEvolution/trivial-phis.ll come from https://reviews.llvm.org/D71492 but don't have the same expected results. @fhahn do you plan to improve those in this patch or a subsequent patch, or were you planning to leave those to me in D71492?
Comment Actions Strip unnecessary checks. Yes I added some of the tests from D71492. This patch only improves things for LCSSA phis, not for other trivial phis (multiple equal incoming values). I can look into how this fits in now as a follow up.
Comment Actions
It would be good to clarify this in the title then.
That would be appreciated. Are there any particular concerns with the proposed fix under D71492? I'd suppose there would be no SCEVExpander concerns (unlike LCSSA phis) since "multiple equal incoming value phis" are not really a form that have to be preserved. Comment Actions @fhahn, Can you look at mafft? Seems like 2-3 % compile time regression? Any data about runtime perf? It is better now? Comment Actions Yes it seems like we hit the worst case here. By looking through phis we have to spend more time making sure LCSSA form is preserved during expansion. This causes some passes that use the expander to take significantly longer than previously. I'll revert shortly and see how we can avoid most of the extra work. Comment Actions This dropped off my radar and I realized that I fixed the cause of the crash which was the reason for the latest revert in 60b852092c98dbdc6248d60109d90ae6f8ad841c. But I never recommitted the patch. I am planning on doing so tomorrow. Compile-time impact seems much less than when it was committed originally now: Comment Actions https://github.com/llvm/llvm-project/commit/764d9aa97905f202385b4f25f8d234630b4feef3 is exposing an issue in DependenceAnalysis: > cat bugpoint-reduced-simplified.ll
; ModuleID = 'bugpoint-reduced-simplified.bc'
target datalayout = "e-m:e-i64:64-n32:64-S128-v256:256:256-v512:512:512"
target triple = "powerpc64le-unknown-linux-gnu"
define dso_local void @hotspotKernel([512 x double]* %temp) local_unnamed_addr #0 {
entry:
br label %for.cond1.preheader
for.cond1.preheader: ; preds = %for.body272, %entry
br label %for.body6
for.body6: ; preds = %for.body6, %for.cond1.preheader
%c.2594 = phi i32 [ 1, %for.cond1.preheader ], [ %add27, %for.body6 ]
%add27 = add nuw nsw i32 %c.2594, 1
br i1 undef, label %for.body6, label %for.end63
for.end63: ; preds = %for.body6
%c.1.lcssa = phi i32 [ %add27, %for.body6 ]
%sub96 = add nsw i32 %c.1.lcssa, -1
%0 = zext i32 %sub96 to i64
%arrayidx98 = getelementptr inbounds [512 x double], [512 x double]* %temp, i64 0, i64 %0
%1 = load double, double* %arrayidx98, align 8
br label %for.body272
for.body272: ; preds = %for.body272, %for.end63
%r.1597 = phi i32 [ 1, %for.end63 ], [ %add277, %for.body272 ]
%idxprom274 = zext i32 %r.1597 to i64
%add277 = add nuw nsw i32 %r.1597, 1
%arrayidx295 = getelementptr inbounds [512 x double], [512 x double]* %temp, i64 %idxprom274, i64 510
%2 = load double, double* %arrayidx295, align 8
br i1 undef, label %for.body272, label %for.cond1.preheader, !llvm.loop !1
}
attributes #0 = { "target-features"="+altivec,+bpermd,+crypto,+direct-move,+extdiv,+htm,+isa-v207-instructions,+power8-vector,+vsx,-isa-v30-instructions,-power9-vector,-privileged,-rop-protect,-spe" }
!llvm.ident = !{!0}
!0 = !{!"version 14.0.0"}
!1 = distinct !{!1, !2}
!2 = !{!"llvm.loop.mustprogress"}opt -passes='print<da>' -disable-output bugpoint-reduced-simplified.ll 'Dependence Analysis' for function 'hotspotKernel': Src: %1 = load double, double* %arrayidx98, align 8 --> Dst: %1 = load double, double* %arrayidx98, align 8 da analyze - consistent input [S]! Src: %1 = load double, double* %arrayidx98, align 8 --> Dst: %2 = load double, double* %arrayidx295, align 8 da analyze - opt: /home/bmahjour/workspaces/_all/upstream-fork/llvm-project/llvm/lib/Analysis/DependenceAnalysis.cpp:2161: bool llvm::DependenceInfo::testSIV(const llvm::SCEV *, const llvm::SCEV *, unsigned $ PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace. Stack dump: 0. Program arguments: /home/bmahjour/workspaces/_all/upstream-fork/build/bin/opt -passes=print<da> -disable-output bugpoint-reduced-simplified.ll #0 0x0000000012c87154 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/home/bmahjour/workspaces/_all/upstream-fork/build/bin/opt+0x12c87154) #1 0x0000000012c87554 PrintStackTraceSignalHandler(void*) Signals.cpp:0:0 #2 0x0000000012c842b8 llvm::sys::RunSignalHandlers() (/home/bmahjour/workspaces/_all/upstream-fork/build/bin/opt+0x12c842b8) #3 0x0000000012c8781c SignalHandler(int) Signals.cpp:0:0 #4 0x00002000000604d8 (linux-vdso64.so.1+0x4d8) #5 0x00002000005fea0c __libc_signal_restore_set /build/glibc-dBVPtL/glibc-2.27/signal/../sysdeps/unix/sysv/linux/nptl-signals.h:80:0 #6 0x00002000005fea0c raise /build/glibc-dBVPtL/glibc-2.27/signal/../sysdeps/unix/sysv/linux/raise.c:48:0 #7 0x0000200000600c60 abort /build/glibc-dBVPtL/glibc-2.27/stdlib/abort.c:79:0 #8 0x00002000005ebbb8 __assert_fail_base /build/glibc-dBVPtL/glibc-2.27/assert/assert.c:92:0 #9 0x00002000005ebc64 __assert_fail /build/glibc-dBVPtL/glibc-2.27/assert/assert.c:101:0 #10 0x0000000011847ba4 llvm::DependenceInfo::testSIV(llvm::SCEV const*, llvm::SCEV const*, unsigned int&, llvm::FullDependence&, llvm::DependenceInfo::Constraint&, llvm::SCEV const*&) const (/home/bmahjour/wor$ #11 0x0000000011854070 llvm::DependenceInfo::depends(llvm::Instruction*, llvm::Instruction*, bool) (/home/bmahjour/workspaces/_all/upstream-fork/build/bin/opt+0x11854070) #12 0x0000000011833f9c dumpExampleDependence(llvm::raw_ostream&, llvm::DependenceInfo*) DependenceAnalysis.cpp:0:0 #13 0x0000000011834594 llvm::DependenceAnalysisPrinterPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/home/bmahjour/workspaces/_all/upstream-fork/build/bin/opt+0x11834594) #14 0x0000000012fff0fc llvm::detail::PassModel<llvm::Function, llvm::DependenceAnalysisPrinterPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<$ #15 0x00000000122e4b6c llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/home/bmahjour/workspaces/_all/upstream-fork/buil$ #16 0x000000001074aedc llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(l$ #17 0x00000000122ea58c llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/bmahjour/workspaces/_all/upstream-fork/build/bin/opt+0x122ea58c) #18 0x000000001039e95c llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Mo$ #19 0x00000000122e3840 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/bmahjour/workspaces/_all/upstream-fork/build/bin/op$ #20 0x0000000010392d60 llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::Strin$ #21 0x00000000103ac0cc main (/home/bmahjour/workspaces/_all/upstream-fork/build/bin/opt+0x103ac0cc) #22 0x00002000005d449c generic_start_main /build/glibc-dBVPtL/glibc-2.27/csu/../csu/libc-start.c:310:0 #23 0x00002000005d469c __libc_start_main /build/glibc-dBVPtL/glibc-2.27/csu/../sysdeps/unix/sysv/linux/powerpc/libc-start.c:116:0 Comment Actions DependenceInfo::classifyPair in DA incorrectly classifies the subscripts in the above test case as SIV, where it used to classify them as non-linear (because one of the subscripts was not an AddRec). In theory we should be able to threat them as MIV I think. Comment Actions Thanks for the test-case. Note that the same issue already exists without the patch if uses of the LCSSA phi node %c.1.lcssa are replace by its incoming value in the shared test case. The issue seems to be that DependenceInfo::classifyPair does not properly account for the fact that we could have AddRecs from sibling loops. It only checks the depth of the the loop of the AddRec, which means we incorrectly determine that 2 AddRecs are linear induction variables for the same loop AFAICT. Shouldn't we consider AddRecs from sibling loops as invariant? Comment Actions Hi, Not sure if this is the same problem as already described but after recommit the following fails for me: opt -passes='loop(indvars,loop-deletion)' -o /dev/null bbi-60874.ll Result: opt: ../include/llvm/Analysis/LoopInfo.h:172: ArrayRef<BlockT *> llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getBlocks() const [BlockT = llvm::BasicBlock, LoopT = llvm::Loop]: Assertion `!isInvalid() && "Loop not in a valid state!"' failed. PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace. Stack dump: 0. Program arguments: build-all/bin/opt -passes=loop(indvars,loop-deletion) -o /dev/null bbi-60874.ll #0 0x0000000002b60583 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (build-all/bin/opt+0x2b60583) #1 0x0000000002b5e1fe llvm::sys::RunSignalHandlers() (build-all/bin/opt+0x2b5e1fe) #2 0x0000000002b60906 SignalHandler(int) Signals.cpp:0:0 #3 0x00007f06f293f630 __restore_rt sigaction.c:0:0 #4 0x00007f06f0072387 raise (/lib64/libc.so.6+0x36387) #5 0x00007f06f0073a78 abort (/lib64/libc.so.6+0x37a78) #6 0x00007f06f006b1a6 __assert_fail_base (/lib64/libc.so.6+0x2f1a6) #7 0x00007f06f006b252 (/lib64/libc.so.6+0x2f252) #8 0x0000000001bed754 llvm::ScalarEvolution::computeLoopDisposition(llvm::SCEV const*, llvm::Loop const*) (build-all/bin/opt+0x1bed754) #9 0x0000000001bec4f1 llvm::ScalarEvolution::getLoopDisposition(llvm::SCEV const*, llvm::Loop const*) (build-all/bin/opt+0x1bec4f1) #10 0x0000000001bb8986 llvm::ScalarEvolution::isLoopInvariant(llvm::SCEV const*, llvm::Loop const*) (build-all/bin/opt+0x1bb8986) #11 0x0000000002cb93f6 llvm::simplifyUsersOfIV(llvm::PHINode*, llvm::ScalarEvolution*, llvm::DominatorTree*, llvm::LoopInfo*, llvm::TargetTransformInfo const*, llvm::SmallVectorImpl<llvm::WeakTrackingVH>&, llvm::SCEVExpander&, llvm::IVVisitor*) (build-all/bin/opt+0x2cb93f6) #12 0x00000000028930f5 (anonymous namespace)::IndVarSimplify::run(llvm::Loop*) IndVarSimplify.cpp:0:0 #13 0x00000000028918dc llvm::IndVarSimplifyPass::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (build-all/bin/opt+0x28918dc) #14 0x0000000002e522ad llvm::detail::PassModel<llvm::Loop, llvm::IndVarSimplifyPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) crtstuff.c:0:0 #15 0x000000000339085f llvm::Optional<llvm::PreservedAnalyses> llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runSinglePass<llvm::Loop, std::unique_ptr<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&> > > >(llvm::Loop&, std::unique_ptr<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&> > >&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&, llvm::PassInstrumentation&) (build-all/bin/opt+0x339085f) #16 0x0000000003390543 llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runWithoutLoopNestPasses(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (build-all/bin/opt+0x3390543) #17 0x000000000338fc08 llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (build-all/bin/opt+0x338fc08) #18 0x0000000002e2992d llvm::detail::PassModel<llvm::Loop, llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) crtstuff.c:0:0 #19 0x0000000003391a68 llvm::FunctionToLoopPassAdaptor::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (build-all/bin/opt+0x3391a68) #20 0x0000000002e518cd llvm::detail::PassModel<llvm::Function, llvm::FunctionToLoopPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) crtstuff.c:0:0 #21 0x0000000002311005 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (build-all/bin/opt+0x2311005) #22 0x0000000000ae6c5d 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 #23 0x0000000002315386 llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (build-all/bin/opt+0x2315386) #24 0x00000000007a4bcd llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) crtstuff.c:0:0 #25 0x0000000002310148 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (build-all/bin/opt+0x2310148) #26 0x000000000079c40c 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) (build-all/bin/opt+0x79c40c) #27 0x00000000007af7f6 main (build-all/bin/opt+0x7af7f6) #28 0x00007f06f005e555 __libc_start_main (/lib64/libc.so.6+0x22555) #29 0x000000000079784c _start (build-all/bin/opt+0x79784c) Abort Comment Actions @uabelho that looks like a different cause, as DependenceAnalysis is not involved. Taking a look now Comment Actions Looks like the issue was missing SCEV invalidation after changing the incoming value of a phi in IndVarSimplify. Should be fixed by 0b4a4cc72d81 Comment Actions Another case that also starts crashing with this patch, and it crashes also after the fix in 0b4a4cc72d81a: opt -passes='loop-mssa(licm,loop-instsimplify,indvars),loop(indvars,simple-loop-unswitch<nontrivial>,loop-unroll-full)' -o /dev/null bbi-60925.ll I've really tried to reduce the command line but can't seem to manage. opt: ../include/llvm/Support/Casting.h:104: static bool llvm::isa_impl_cl<llvm::Instruction, const llvm::Value *>::doit(const From *) [To = llvm::Instruction, From = const llvm::Value *]: Assertion `Val && "isa<> used on a null pointer"' 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(licm,loop-instsimplify,indvars),loop(indvars,simple-loop-unswitch<nontrivial>,loop-unroll-full) -o /dev/null bbi-60925.ll #0 0x0000000002b60f03 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (../../master-github/llvm/build-all/bin/opt+0x2b60f03) #1 0x0000000002b5eb7e llvm::sys::RunSignalHandlers() (../../master-github/llvm/build-all/bin/opt+0x2b5eb7e) #2 0x0000000002b61286 SignalHandler(int) Signals.cpp:0:0 #3 0x00007f634fe4b630 __restore_rt sigaction.c:0:0 #4 0x00007f634d57e387 raise (/lib64/libc.so.6+0x36387) #5 0x00007f634d57fa78 abort (/lib64/libc.so.6+0x37a78) #6 0x00007f634d5771a6 __assert_fail_base (/lib64/libc.so.6+0x2f1a6) #7 0x00007f634d577252 (/lib64/libc.so.6+0x2f252) #8 0x0000000001bee8f5 llvm::ScalarEvolution::computeLoopDisposition(llvm::SCEV const*, llvm::Loop const*) (../../master-github/llvm/build-all/bin/opt+0x1bee8f5) #9 0x0000000001bed6b1 llvm::ScalarEvolution::getLoopDisposition(llvm::SCEV const*, llvm::Loop const*) (../../master-github/llvm/build-all/bin/opt+0x1bed6b1) #10 0x0000000001bb9b46 llvm::ScalarEvolution::isLoopInvariant(llvm::SCEV const*, llvm::Loop const*) (../../master-github/llvm/build-all/bin/opt+0x1bb9b46) #11 0x0000000002c31126 llvm::rewriteLoopExitValues(llvm::Loop*, llvm::LoopInfo*, llvm::TargetLibraryInfo*, llvm::ScalarEvolution*, llvm::TargetTransformInfo const*, llvm::SCEVExpander&, llvm::DominatorTree*, llvm::ReplaceExitVal, llvm::SmallVector<llvm::WeakTrackingVH, 16u>&) (../../master-github/llvm/build-all/bin/opt+0x2c31126) #12 0x0000000002893599 (anonymous namespace)::IndVarSimplify::run(llvm::Loop*) IndVarSimplify.cpp:0:0 #13 0x0000000002891aec llvm::IndVarSimplifyPass::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (../../master-github/llvm/build-all/bin/opt+0x2891aec) #14 0x0000000002e52c2d llvm::detail::PassModel<llvm::Loop, llvm::IndVarSimplifyPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) crtstuff.c:0:0 #15 0x000000000339168f llvm::Optional<llvm::PreservedAnalyses> llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runSinglePass<llvm::Loop, std::unique_ptr<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&> > > >(llvm::Loop&, std::unique_ptr<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&> > >&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&, llvm::PassInstrumentation&) (../../master-github/llvm/build-all/bin/opt+0x339168f) #16 0x0000000003391373 llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runWithoutLoopNestPasses(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (../../master-github/llvm/build-all/bin/opt+0x3391373) #17 0x0000000003390a38 llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (../../master-github/llvm/build-all/bin/opt+0x3390a38) #18 0x0000000002e2a2ad llvm::detail::PassModel<llvm::Loop, llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) crtstuff.c:0:0 #19 0x0000000003392898 llvm::FunctionToLoopPassAdaptor::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../master-github/llvm/build-all/bin/opt+0x3392898) #20 0x0000000002e5224d llvm::detail::PassModel<llvm::Function, llvm::FunctionToLoopPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) crtstuff.c:0:0 #21 0x0000000002311915 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../master-github/llvm/build-all/bin/opt+0x2311915) #22 0x0000000000ae8c6d 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 #23 0x0000000002315c96 llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (../../master-github/llvm/build-all/bin/opt+0x2315c96) #24 0x00000000007a4b2d llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) crtstuff.c:0:0 #25 0x0000000002310a58 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (../../master-github/llvm/build-all/bin/opt+0x2310a58) #26 0x000000000079c36c 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+0x79c36c) #27 0x00000000007af756 main (../../master-github/llvm/build-all/bin/opt+0x7af756) #28 0x00007f634d56a555 __libc_start_main (/lib64/libc.so.6+0x22555) #29 0x00000000007977ac _start (../../master-github/llvm/build-all/bin/opt+0x7977ac) Abort Comment Actions Hi, I saw a similar crash in chrome windows pgo builds that was caused by this change repro: $ cat bugpoint-reduced-simplified.ll ; ModuleID = 'bugpoint-reduced-simplified.bc' source_filename = "t.cpp" target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" define dso_local void @_Z1tv() local_unnamed_addr { entry: br label %for.cond.i.i.preheader for.cond.i.i.preheader: ; preds = %"_ZN1gILm5EZ1tvE3$_0E1hppEv.exit", %entry %__begin1.sroa.3.021 = phi i8 [ %storemerge.i.lcssa, %"_ZN1gILm5EZ1tvE3$_0E1hppEv.exit" ], [ undef, %entry ] br label %for.cond.i.i for.cond.cleanup: ; preds = %"_ZN1gILm5EZ1tvE3$_0E1hppEv.exit" ret void for.cond.i.i: ; preds = %for.body.i.i, %for.cond.i.i.preheader %__begin1.sroa.3.1 = phi i8 [ %storemerge.i, %for.body.i.i ], [ %__begin1.sroa.3.021, %for.cond.i.i.preheader ] %storemerge.i = add i8 %__begin1.sroa.3.1, 1 br i1 undef, label %"_ZN1gILm5EZ1tvE3$_0E1hppEv.exit", label %for.body.i.i for.body.i.i: ; preds = %for.cond.i.i br i1 undef, label %"_ZN1gILm5EZ1tvE3$_0E1hppEv.exit", label %for.cond.i.i "_ZN1gILm5EZ1tvE3$_0E1hppEv.exit": ; preds = %for.body.i.i, %for.cond.i.i %storemerge.i.lcssa = phi i8 [ %storemerge.i, %for.cond.i.i ], [ %storemerge.i, %for.body.i.i ] %tobool.i.not = icmp eq i8 %storemerge.i.lcssa, 0 br i1 %tobool.i.not, label %for.cond.cleanup, label %for.cond.i.i.preheader } $ opt --passes='loop(indvars,loop-deletion)' --disable-output bugpoint-reduced-simplified.ll opt: ../llvm-project/llvm/include/llvm/Analysis/LoopInfo.h:123: bool llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::contains(const LoopT *) const [BlockT = llvm::BasicBlock, LoopT = llvm::Loop]: Assertion `!isInvalid() && "Loop not in a valid state!"' failed. PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace. Stack dump: 0. Program arguments: opt --passes=loop(indvars,loop-deletion) --disable-output bugpoint-reduced-simplified.ll [...] #10 0x0000000002c278db llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::contains(llvm::Loop const*) const /usr/local/google/home/akhuang/llvm-build/../llvm-project/llvm/include/llvm/Analysis/LoopInfo.h:0:5 #11 0x0000000002dae92c llvm::ScalarEvolution::computeSCEVAtScope(llvm::SCEV const*, llvm::Loop const*) /usr/local/google/home/akhuang/llvm-build/../llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:9046:9 #12 0x0000000002da8bd0 llvm::ScalarEvolution::getSCEVAtScope(llvm::SCEV const*, llvm::Loop const*) /usr/local/google/home/akhuang/llvm-build/../llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:8733:19 #13 0x0000000002da77c5 llvm::ScalarEvolution::computeExitLimitFromICmp(llvm::Loop const*, llvm::ICmpInst*, bool, bool, bool) /usr/local/google/home/akhuang/llvm-build/../llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:8059:9 #14 0x0000000002da6cc5 llvm::ScalarEvolution::computeExitLimitFromCondImpl(llvm::ScalarEvolution::ExitLimitCache&, llvm::Loop const*, llvm::Value*, bool, bool, bool) /usr/local/google/home/akhuang/llvm-build/../llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:7918:12 [...] Comment Actions @akhuang thanks for the reproducer. Looks like there are a few additional cases where SCEV expressions are not invalidated properly which are exposed by this patch. I reverted it for now while I investigate. Comment Actions Yes, it seems that we've assumed LCSSA form for correct functioning of the DA implementation.
It does account for sibling loops, but the situation here is that one of the memory access instructions appears outside of the sibling loops while the subscript of that access has a recurrence with one of the sibling loops. The implementation uses a numbering scheme to distinguish the loop for the src of the dependence from the loop for the dest, but that numbering scheme gets messed up when we have a recurrence with a loop that does not contain the access instruction. I've explained the issue and proposed two possible ways to address it under D110972 and D110973.
Please see D110972 and D110973. I suggest we agree on one of these (or another alternative) before recommiting this patch. FYI @fhahn and @Meinersbur . Comment Actions The last known crash has been fixed by now and I plan to re-commit this soon. AFAIK the only remaining issue is with DependenceAnalysis. @bmahjour do you know if there has been any progress on the fixes you shared a while ago? Comment Actions @fhahn I'm still awaiting feedback on D110972 and D110973. Honestly neither of them are good solutions but they should be useful in understanding the problem and getting some conversation started on how to proceed. I do think that the damage to DA would easily outweigh the benefit of this change, so I'd strongly suggest we hold off on recommitting this until a solution for the DA problem is found. This would be a good topic to discuss further in future #loopoptwg calls if need be. Comment Actions https://reviews.llvm.org/D110973 has landed. This should be safe to re-commit now. Thanks! Comment Actions This commit (recommitted in the final form in 20d798bd47ec5191de1b2a8a031da06a04e612e1) seems to be triggering failed asserts - see https://github.com/llvm/llvm-project/issues/57825 for details. Reposting the essential details here too: $ cat repro.c double *a; double b, c; int d, e; long f; void g() { d = 1; for (; d >= 0; d--) { e = 0; for (; e < f; e++) { c = *(&b + e); *a = *(&b + d + e) = c; a++; } } } $ clang -target aarch64-windows-msvc -c repro.c -O2 clang: ../lib/Analysis/ScalarEvolution.cpp:768: llvm::Optional<int> CompareSCEVComplexity(llvm::EquivalenceClasses<const llvm::SCEV*>&, llvm::EquivalenceClasses<const llvm::Value*>&, const llvm::LoopInfo*, const llvm::SCEV*, const llvm::SCEV*, llvm::DominatorTree&, unsigned int): Assertion `DT.dominates(RHead, LHead) && "No dominance between recurrences used by one SCEV?"' failed. Comment Actions Hi, I wrote Assertion `EVL->contains(L) && "LCSSA breach detected!"' failed. that started happening with this patch when it wasw recommited in 20d798b. Comment Actions I wrote | ||||||||||||||||||
Nit