This is an archive of the discontinued LLVM Phabricator instance.

Differential D108833

[LoopDeletion] Use max trip count to break backedge in addition to exact one
ClosedPublic

Authored by reames on Aug 27 2021, 10:53 AM.

Details

Reviewers
fhahn
nikic
mkazantsev
lebedev.ri
Commits
rGc7b25e435996: [LoopDeletion] Use max trip count to break backedge in addition to exact one
Summary

We'd added support a while back from breaking the backedge if SCEV can prove the trip count is zero. However, we used the exact trip count which requires *all* exits be analyzeable. I noticed while writing test cases for another patch that this disallows cases where one exit is provably taken paired with another which is unknown. This patch adds the upper bound case.

We could use a symbolic max trip count here instead, but we use an isKnownNonZero filter (presumably for compile time?) for the first-iteration reasoning. I decided this was a more obvious incremental step, and we could go back and untangle the schemes separately.

Diff Detail

Event Timeline

reames created this revision.Aug 27 2021, 10:53 AM
Herald added subscribers: javed.absar, bollu, hiraditya, mcrosier. · View Herald TranscriptAug 27 2021, 10:53 AM
reames requested review of this revision.Aug 27 2021, 10:53 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 27 2021, 10:53 AM
reames edited the summary of this revision. (Show Details)Aug 27 2021, 10:59 AM
Harbormaster completed remote builds in B121524: Diff 369139.Aug 27 2021, 11:41 AM
nikic accepted this revision.Aug 27 2021, 1:53 PM

LGTM

llvm/lib/Transforms/Scalar/LoopDeletion.cpp
399

I find this extra BTC->isZero() check a bit confusing -- unless I'm missing something, the check against getConstantMaxBackedgeTakenCount() should be strictly more powerful, right? For the exact count to return zero all exits must have a constant BECount of zero, so the constant max BE count must also be zero.

(We might also want to drop the isKnownNonZero optimization, as IIRC it had no real impact in practice, but that's a different matter.)

This revision is now accepted and ready to land.Aug 27 2021, 1:53 PM
reames added inline comments.Aug 27 2021, 2:17 PM
llvm/lib/Transforms/Scalar/LoopDeletion.cpp
399

You're correct - in theory. I'm very hesitant to introduce an assumption of max=0 ==> exact=0 though as I don't see that properly asserted anywhere in the existing code. We could today compute somewhere in the TC logic a zero max with a non-zero exact, and nothing would care.

Closed by commit rGc7b25e435996: [LoopDeletion] Use max trip count to break backedge in addition to exact one (authored by reames). · Explain WhyAug 27 2021, 2:24 PM
This revision was automatically updated to reflect the committed changes.
reames added a commit: rGc7b25e435996: [LoopDeletion] Use max trip count to break backedge in addition to exact one.
reames mentioned this in D108848: [LoopDeletion] Separate logic in breakBackedgeIfNotTaken using symboic max trip count [nfc].Aug 27 2021, 2:40 PM
reames mentioned this in rG3af8a11bc66b: [LoopDeletion] Separate logic in breakBackedgeIfNotTaken using symboic max trip….Sep 1 2021, 1:31 PM
uabelho added a subscriber: uabelho.Nov 29 2021, 9:06 AM

Hi,

The following starts crashing with this patch:

opt -passes='function(loop-mssa(licm,loop-rotate,loop-deletion,lnicm))' -o /dev/null bbi-63573.ll

We get

opt: ../lib/Transforms/Scalar/LICM.cpp:1639: void splitPredecessorsOfLoopExit(llvm::PHINode *, llvm::DominatorTree *, llvm::LoopInfo *, const llvm::Loop *, llvm::LoopSafetyInfo *, llvm::MemorySSAUpdater *): Assertion `CurLoop->contains(PredBB) && "Expect all predecessors are in the loop"' 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=function(loop-mssa(licm,loop-rotate,loop-deletion,lnicm)) -o /dev/null bbi-63573.ll
 #0 0x0000000002bc80c3 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (../../master-github/llvm/build-all/bin/opt+0x2bc80c3)
 #1 0x0000000002bc5d3e llvm::sys::RunSignalHandlers() (../../master-github/llvm/build-all/bin/opt+0x2bc5d3e)
 #2 0x0000000002bc8446 SignalHandler(int) Signals.cpp:0:0
 #3 0x00007fe912719630 __restore_rt sigaction.c:0:0
 #4 0x00007fe90fe4c387 raise (/lib64/libc.so.6+0x36387)
 #5 0x00007fe90fe4da78 abort (/lib64/libc.so.6+0x37a78)
 #6 0x00007fe90fe451a6 __assert_fail_base (/lib64/libc.so.6+0x2f1a6)
 #7 0x00007fe90fe45252 (/lib64/libc.so.6+0x2f252)
 #8 0x000000000291ab08 llvm::sinkRegion(llvm::DomTreeNodeBase<llvm::BasicBlock>*, llvm::AAResults*, llvm::LoopInfo*, llvm::DominatorTree*, llvm::BlockFrequencyInfo*, llvm::TargetLibraryInfo*, llvm::TargetTransformInfo*, llvm::Loop*, llvm::MemorySSAUpdater*, llvm::ICFLoopSafetyInfo*, llvm::SinkAndHoistLICMFlags&, llvm::OptimizationRemarkEmitter*, llvm::Loop*) (../../master-github/llvm/build-all/bin/opt+0x291ab08)
 #9 0x000000000291c6f8 llvm::sinkRegionForLoopNest(llvm::DomTreeNodeBase<llvm::BasicBlock>*, llvm::AAResults*, llvm::LoopInfo*, llvm::DominatorTree*, llvm::BlockFrequencyInfo*, llvm::TargetLibraryInfo*, llvm::TargetTransformInfo*, llvm::Loop*, llvm::MemorySSAUpdater*, llvm::ICFLoopSafetyInfo*, llvm::SinkAndHoistLICMFlags&, llvm::OptimizationRemarkEmitter*) (../../master-github/llvm/build-all/bin/opt+0x291c6f8)
#10 0x000000000291637e (anonymous namespace)::LoopInvariantCodeMotion::runOnLoop(llvm::Loop*, llvm::AAResults*, llvm::LoopInfo*, llvm::DominatorTree*, llvm::BlockFrequencyInfo*, llvm::TargetLibraryInfo*, llvm::TargetTransformInfo*, llvm::ScalarEvolution*, llvm::MemorySSA*, llvm::OptimizationRemarkEmitter*, bool) LICM.cpp:0:0
#11 0x0000000002917502 llvm::LNICMPass::run(llvm::LoopNest&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (../../master-github/llvm/build-all/bin/opt+0x2917502)
#12 0x0000000002ed6b8d llvm::detail::PassModel<llvm::LoopNest, llvm::LNICMPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::LoopNest&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) crtstuff.c:0:0
#13 0x000000000341163c llvm::Optional<llvm::PreservedAnalyses> llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runSinglePass<llvm::LoopNest, std::unique_ptr<llvm::detail::PassConcept<llvm::LoopNest, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::LoopNest, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&> > > >(llvm::LoopNest&, std::unique_ptr<llvm::detail::PassConcept<llvm::LoopNest, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::LoopNest, 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+0x341163c)
#14 0x0000000003410a83 llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runWithLoopNestPasses(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (../../master-github/llvm/build-all/bin/opt+0x3410a83)
#15 0x0000000003410661 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+0x3410661)
#16 0x0000000002eaa25d 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
#17 0x000000000341255b llvm::FunctionToLoopPassAdaptor::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../master-github/llvm/build-all/bin/opt+0x341255b)
#18 0x0000000002ec593d llvm::detail::PassModel<llvm::Function, llvm::FunctionToLoopPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) crtstuff.c:0:0
#19 0x00000000023562a5 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../master-github/llvm/build-all/bin/opt+0x23562a5)
#20 0x0000000000ae88fd 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
#21 0x000000000235a6ca llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (../../master-github/llvm/build-all/bin/opt+0x235a6ca)
#22 0x0000000000793f0d llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) crtstuff.c:0:0
#23 0x00000000023553e8 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (../../master-github/llvm/build-all/bin/opt+0x23553e8)
#24 0x000000000078bc82 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+0x78bc82)
#25 0x000000000079e8ad main (../../master-github/llvm/build-all/bin/opt+0x79e8ad)
#26 0x00007fe90fe38555 __libc_start_main (/lib64/libc.so.6+0x22555)
#27 0x00000000007870cc _start (../../master-github/llvm/build-all/bin/opt+0x7870cc)
Abort

bbi-63573.ll1 KBDownload

reames added a comment.Nov 29 2021, 1:55 PM
In D108833#3158617, @uabelho wrote:

Hi,

The following starts crashing with this patch:

Please file a bug. This does not appear to be a regression with this patch. I've done some analysis and will provide it in the bug report.

uabelho added a comment.Nov 30 2021, 12:51 AM
In D108833#3159454, @reames wrote:
In D108833#3158617, @uabelho wrote:

Hi,

The following starts crashing with this patch:

Please file a bug. This does not appear to be a regression with this patch. I've done some analysis and will provide it in the bug report.

Sure, will do (as soon as we have a bug reporting system again and I realize how to use it :) .
Thanks!

uabelho added a comment.Dec 14 2021, 12:57 AM
In D108833#3159454, @reames wrote:
In D108833#3158617, @uabelho wrote:

Hi,

The following starts crashing with this patch:

Please file a bug. This does not appear to be a regression with this patch. I've done some analysis and will provide it in the bug report.

There:
https://github.com/llvm/llvm-project/issues/52688

fhahn added a comment.Dec 14 2021, 3:58 AM
In D108833#3191589, @uabelho wrote:
In D108833#3159454, @reames wrote:
In D108833#3158617, @uabelho wrote:

Hi,

The following starts crashing with this patch:

Please file a bug. This does not appear to be a regression with this patch. I've done some analysis and will provide it in the bug report.

There:
https://github.com/llvm/llvm-project/issues/52688

I suspect this may be a problem in the code added in D107219. I added a comment there.

Revision Contents

PathSize
llvm/
lib/
Transforms/
Scalar/
15 lines
test/
Transforms/
LoopDeletion/
35 lines
36 lines

Diff 369187

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

Show First 20 Lines • Show All 387 Lines • ▼ Show 20 Lines
breakBackedgeIfNotTaken(Loop *L, DominatorTree &DT, ScalarEvolution &SE, breakBackedgeIfNotTaken(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
LoopInfo &LI, MemorySSA *MSSA, LoopInfo &LI, MemorySSA *MSSA,
OptimizationRemarkEmitter &ORE) { OptimizationRemarkEmitter &ORE) {
assert(L->isLCSSAForm(DT) && "Expected LCSSA!"); assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
if (!L->getLoopLatch()) if (!L->getLoopLatch())
return LoopDeletionResult::Unmodified; return LoopDeletionResult::Unmodified;
auto *BTCMax = SE.getConstantMaxBackedgeTakenCount(L);
if (!BTCMax->isZero()) {
auto *BTC = SE.getBackedgeTakenCount(L); auto *BTC = SE.getBackedgeTakenCount(L);
if (!BTC->isZero()) {
nikicUnsubmitted
Not Done
ReplyInline Actions

I find this extra BTC->isZero() check a bit confusing -- unless I'm missing something, the check against getConstantMaxBackedgeTakenCount() should be strictly more powerful, right? For the exact count to return zero all exits must have a constant BECount of zero, so the constant max BE count must also be zero.

(We might also want to drop the isKnownNonZero optimization, as IIRC it had no real impact in practice, but that's a different matter.)

nikic: I find this extra BTC->isZero() check a bit confusing -- unless I'm missing something, the…
reamesAuthorUnsubmitted
Done
ReplyInline Actions

You're correct - in theory. I'm very hesitant to introduce an assumption of max=0 ==> exact=0 though as I don't see that properly asserted anywhere in the existing code. We could today compute somewhere in the TC logic a zero max with a non-zero exact, and nothing would care.

reames: You're correct - in theory. I'm very hesitant to introduce an assumption of max=0 ==> exact=0…
if (!isa<SCEVCouldNotCompute>(BTC) && SE.isKnownNonZero(BTC)) if (!isa<SCEVCouldNotCompute>(BTC) && SE.isKnownNonZero(BTC))
return LoopDeletionResult::Unmodified; return LoopDeletionResult::Unmodified;
if (!BTC->isZero() && !canProveExitOnFirstIteration(L, DT, LI)) if (!canProveExitOnFirstIteration(L, DT, LI))
return LoopDeletionResult::Unmodified; return LoopDeletionResult::Unmodified;
}
}
breakLoopBackedge(L, DT, SE, LI, MSSA); breakLoopBackedge(L, DT, SE, LI, MSSA);
return LoopDeletionResult::Deleted; return LoopDeletionResult::Deleted;
} }
/// Remove a loop if it is dead. /// Remove a loop if it is dead.
/// ///
/// A loop is considered dead either if it does not impact the observable /// A loop is considered dead either if it does not impact the observable
▲ Show 20 Lines • Show All 174 Lines • Show Last 20 Lines

llvm/test/Transforms/LoopDeletion/switch.ll

Show All 35 Linescleanup967:
] ]
cleanup1169: cleanup1169:
ret void ret void
unreachable: unreachable:
unreachable unreachable
} }
define void @func_2() {
; CHECK-LABEL: @func_2(
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[LBL_2368:%.*]]
; CHECK: lbl_2368:
; CHECK-NEXT: br i1 false, label [[CLEANUP967:%.*]], label [[UNREACHABLE:%.*]]
; CHECK: cleanup967:
; CHECK-NEXT: switch i32 undef, label [[CLEANUP1169:%.*]] [
; CHECK-NEXT: i32 20, label [[CLEANUP967_LBL_2368_CRIT_EDGE:%.*]]
; CHECK-NEXT: ]
; CHECK: cleanup967.lbl_2368_crit_edge:
; CHECK-NEXT: unreachable
; CHECK: cleanup1169:
; CHECK-NEXT: ret void
; CHECK: unreachable:
; CHECK-NEXT: unreachable
;
entry:
br label %lbl_2368
lbl_2368:
br i1 false, label %cleanup967, label %unreachable
cleanup967:
switch i32 undef, label %cleanup1169 [
i32 20, label %lbl_2368
]
cleanup1169:
ret void
unreachable:
unreachable
}

llvm/test/Transforms/LoopDeletion/zero-btc.ll

Show First 20 Lines • Show All 233 Lines • ▼ Show 20 Lineslatch:
br i1 false, label %loop, label %exit2 br i1 false, label %loop, label %exit2
exit1: exit1:
ret void ret void
exit2: exit2:
ret void ret void
} }
declare i1 @unknown()
; We can't compute an exit count for the latch, but we know the upper
; bound on the trip count is zero anyways.
define void @test_dead_latch1() {
; CHECK-LABEL: @test_dead_latch1(
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop:
; CHECK-NEXT: store i32 0, i32* @G, align 4
; CHECK-NEXT: br i1 false, label [[LATCH:%.*]], label [[EXIT1:%.*]]
; CHECK: latch:
; CHECK-NEXT: [[LATCHCOND:%.*]] = call i1 @unknown()
; CHECK-NEXT: br label [[EXIT2:%.*]]
; CHECK: exit1:
; CHECK-NEXT: ret void
; CHECK: exit2:
; CHECK-NEXT: ret void
;
entry:
br label %loop
loop:
store i32 0, i32* @G
br i1 false, label %latch, label %exit1
latch:
%latchcond = call i1 @unknown()
br i1 %latchcond, label %loop, label %exit2
exit1:
ret void
exit2:
ret void
}
define void @test_live_inner() { define void @test_live_inner() {
; CHECK-LABEL: @test_live_inner( ; CHECK-LABEL: @test_live_inner(
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: store i32 0, i32* @G, align 4 ; CHECK-NEXT: store i32 0, i32* @G, align 4
; CHECK-NEXT: br label [[INNER:%.*]] ; CHECK-NEXT: br label [[INNER:%.*]]
; CHECK: inner: ; CHECK: inner:
▲ Show 20 Lines • Show All 112 Lines • Show Last 20 Lines