This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Look through trivial PHIs.
ClosedPublic

Authored by fhahn on Dec 16 2019, 4:02 AM.

Details

Summary

Now that SCEVExpander can preserve LCSSA form,
we do not have to worry about LCSSA form when
trying to look through PHIs. SCEVExpander will take
care of inserting LCSSA PHI nodes as required.

This increases precision of the analysis in some cases.

Diff Detail

Event Timeline

fhahn created this revision.Dec 16 2019, 4:02 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 16 2019, 4:02 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
fhahn retitled this revision from [SCEV] Look through trivial PHIs (WIP). to [SCEV] Look through trivial PHIs..Jul 14 2020, 5:49 AM
fhahn edited the summary of this revision. (Show Details)
mkazantsev accepted this revision.Jul 28 2020, 7:09 AM

Looks good (with nits).

llvm/lib/Analysis/ScalarEvolution.cpp
3689

Nit

3715

Does this comment need explanation about what do we do for Phis?

5115–5116

assert(LI.replacementPreservesLCSSAForm(PN, V))

This revision is now accepted and ready to land.Jul 28 2020, 7:09 AM

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?

llvm/lib/Analysis/ScalarEvolution.cpp
3719

SimplifyInstruction(V,..) will never return V, so here we are saying do not insert into the map if we have a phi! Did you mean

(!is<PHINode>(V) || SimplifyInstruction(cast<PHINode>(V), {getDataLayout(), &TLI, &DT, &AC}) != nullptr))

meaning if "we have a phi that cannot be simplified" ?

6557

use hasConstantValue() instead?

bmahjour requested changes to this revision.Jul 30 2020, 2:57 PM
This revision now requires changes to proceed.Jul 30 2020, 2:57 PM
fhahn updated this revision to Diff 284848.Aug 11 2020, 12:22 PM

Strip unnecessary checks.

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?

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.

fhahn added inline comments.Aug 11 2020, 12:24 PM
llvm/lib/Analysis/ScalarEvolution.cpp
3719

I think this check got messed with during a previous rebase a while back or covered a problem with earlier versions of the depending patches. This special case should not be necessary with the latest version, none of the tests that I added for this work earlier are impacted and I removed it.

6557

This special case should not be necessary with the latest version, none of the tests that I added for this work earlier are impacted and I removed it.

bmahjour accepted this revision.EditedAug 11 2020, 1:55 PM

This patch only improves things for LCSSA phis, not for other trivial phis (multiple equal incoming values).

It would be good to clarify this in the title then.

I can look into how this fits in now as a follow up.

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.

This revision is now accepted and ready to land.Aug 11 2020, 1:55 PM
This revision was automatically updated to reflect the committed changes.
xbolva00 added a subscriber: xbolva00.EditedAug 12 2020, 3:24 AM

https://llvm-compile-time-tracker.com/compare.php?from=9ceb192e14164ecf8a6f714a770c89765327c722&to=e441b7a7a0a72c28daf5a8e594559c667e5b4534&stat=instructions

@fhahn, Can you look at mafft? Seems like 2-3 % compile time regression? Any data about runtime perf? It is better now?

fhahn added a comment.Aug 12 2020, 4:23 AM

https://llvm-compile-time-tracker.com/compare.php?from=9ceb192e14164ecf8a6f714a770c89765327c722&to=e441b7a7a0a72c28daf5a8e594559c667e5b4534&stat=instructions

@fhahn, Can you look at mafft? Seems like 2-3 % compile time regression? Any data about runtime perf? It is better now?

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.

fhahn added a comment.Sep 27 2021, 1:25 PM

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:
http://llvm-compile-time-tracker.com/compare.php?from=0b61f43b6096a9e98652991cba34e8ad44d35101&to=ffe4cbefc784e6e3c60cdefe5c3925dc77ea77f9&stat=instructions

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

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.

fhahn added a comment.Sep 29 2021, 2:49 AM

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.

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?

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

fhahn added a comment.Sep 29 2021, 5:35 AM

@uabelho that looks like a different cause, as DependenceAnalysis is not involved. Taking a look now

fhahn added a comment.Sep 29 2021, 6:53 AM

@uabelho that looks like a different cause, as DependenceAnalysis is not involved. Taking a look now

Looks like the issue was missing SCEV invalidation after changing the incoming value of a phi in IndVarSimplify. Should be fixed by 0b4a4cc72d81

@uabelho that looks like a different cause, as DependenceAnalysis is not involved. Taking a look now

Looks like the issue was missing SCEV invalidation after changing the incoming value of a phi in IndVarSimplify. Should be fixed by 0b4a4cc72d81

Yep, thanks!

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.
It crashes with:

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

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
[...]

@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.

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.

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.

Yes, it seems that we've assumed LCSSA form for correct functioning of the DA implementation.

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.

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.

Shouldn't we consider AddRecs from sibling loops as invariant?

Please see D110972 and D110973. I suggest we agree on one of these (or another alternative) before recommiting this patch. FYI @fhahn and @Meinersbur .

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?

Herald added a project: Restricted Project. · View Herald TranscriptApr 19 2022, 11:26 PM

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?

@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.

https://reviews.llvm.org/D110973 has landed. This should be safe to re-commit now. Thanks!

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.

Hi,

I wrote
https://github.com/llvm/llvm-project/issues/58007
about a crash

Assertion `EVL->contains(L) && "LCSSA breach detected!"' failed.

that started happening with this patch when it wasw recommited in 20d798b.

bjope added a subscriber: bjope.Sep 26 2022, 11:47 PM

I wrote
https://github.com/llvm/llvm-project/issues/58871
about a crash starting to happen with this patch.