From 8963650cfa04a60dbb51e4bd27b9fefeb51ab71b Mon Sep 17 00:00:00 2001 From: Sanjoy Das Date: Sun, 21 May 2017 05:02:12 +0000 Subject: [PATCH] Revert "[SCEV] Clarify behavior around max backedge taken count" This reverts commit r303497 since it breaks the msan bootstrap bot: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap/builds/1379/ llvm-svn: 303498 --- llvm/include/llvm/Analysis/ScalarEvolution.h | 26 +++++------- llvm/lib/Analysis/ScalarEvolution.cpp | 47 +++++----------------- llvm/test/Analysis/ScalarEvolution/nsw.ll | 2 +- .../Analysis/ScalarEvolution/trip-count-pow2.ll | 10 ++--- 4 files changed, 27 insertions(+), 58 deletions(-) diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h index ac54bd4..ceca6cb 100644 --- a/llvm/include/llvm/Analysis/ScalarEvolution.h +++ b/llvm/include/llvm/Analysis/ScalarEvolution.h @@ -656,12 +656,10 @@ private: /// Test whether this BackedgeTakenInfo contains complete information. bool hasFullInfo() const { return isComplete(); } - /// Return an expression indicating the exact *backedge-taken* - /// count of the loop if it is known or SCEVCouldNotCompute - /// otherwise. If execution makes it to the backedge on every - /// iteration (i.e. there are no abnormal exists like exception - /// throws and thread exits) then this is the number of times the - /// loop header will execute minus one. + /// Return an expression indicating the exact backedge-taken count of the + /// loop if it is known or SCEVCouldNotCompute otherwise. This is the + /// number of times the loop header can be guaranteed to execute, minus + /// one. /// /// If the SCEV predicate associated with the answer can be different /// from AlwaysTrue, we must add a (non null) Predicates argument. @@ -1400,11 +1398,11 @@ public: const SCEV *getExitCount(const Loop *L, BasicBlock *ExitingBlock); /// If the specified loop has a predictable backedge-taken count, return it, - /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count is - /// the number of times the loop header will be branched to from within the - /// loop, assuming there are no abnormal exists like exception throws. This is - /// one less than the trip count of the loop, since it doesn't count the first - /// iteration, when the header is branched to from outside the loop. + /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count + /// is the number of times the loop header will be branched to from within + /// the loop. This is one less than the trip count of the loop, since it + /// doesn't count the first iteration, when the header is branched to from + /// outside the loop. /// /// Note that it is not valid to call this method on a loop without a /// loop-invariant backedge-taken count (see @@ -1419,10 +1417,8 @@ public: const SCEV *getPredicatedBackedgeTakenCount(const Loop *L, SCEVUnionPredicate &Predicates); - /// When successful, this returns a SCEVConstant that is greater than or equal - /// to (i.e. a "conservative over-approximation") of the value returend by - /// getBackedgeTakenCount. If such a value cannot be computed, it returns the - /// SCEVCouldNotCompute object. + /// Similar to getBackedgeTakenCount, except return the least SCEV value + /// that is known never to be less than the actual backedge taken count. const SCEV *getMaxBackedgeTakenCount(const Loop *L); /// Return true if the backedge taken count is either the value returned by diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 78ded81..3f3e8ce 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -5947,8 +5947,6 @@ ScalarEvolution::BackedgeTakenInfo::getMax(ScalarEvolution *SE) const { if (any_of(ExitNotTaken, PredicateNotAlwaysTrue) || !getMax()) return SE->getCouldNotCompute(); - assert((isa(getMax()) || isa(getMax())) && - "No point in having a non-constant max backedge taken count!"); return getMax(); } @@ -5974,11 +5972,7 @@ bool ScalarEvolution::BackedgeTakenInfo::hasOperand(const SCEV *S, } ScalarEvolution::ExitLimit::ExitLimit(const SCEV *E) - : ExactNotTaken(E), MaxNotTaken(E), MaxOrZero(false) { - assert((isa(MaxNotTaken) || - isa(MaxNotTaken)) && - "No point in having a non-constant max backedge taken count!"); -} + : ExactNotTaken(E), MaxNotTaken(E), MaxOrZero(false) {} ScalarEvolution::ExitLimit::ExitLimit( const SCEV *E, const SCEV *M, bool MaxOrZero, @@ -5987,9 +5981,6 @@ ScalarEvolution::ExitLimit::ExitLimit( assert((isa(ExactNotTaken) || !isa(MaxNotTaken)) && "Exact is not allowed to be less precise than Max"); - assert((isa(MaxNotTaken) || - isa(MaxNotTaken)) && - "No point in having a non-constant max backedge taken count!"); for (auto *PredSet : PredSetList) for (auto *P : *PredSet) addPredicate(P); @@ -5998,19 +5989,11 @@ ScalarEvolution::ExitLimit::ExitLimit( ScalarEvolution::ExitLimit::ExitLimit( const SCEV *E, const SCEV *M, bool MaxOrZero, const SmallPtrSetImpl &PredSet) - : ExitLimit(E, M, MaxOrZero, {&PredSet}) { - assert((isa(MaxNotTaken) || - isa(MaxNotTaken)) && - "No point in having a non-constant max backedge taken count!"); -} + : ExitLimit(E, M, MaxOrZero, {&PredSet}) {} ScalarEvolution::ExitLimit::ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero) - : ExitLimit(E, M, MaxOrZero, None) { - assert((isa(MaxNotTaken) || - isa(MaxNotTaken)) && - "No point in having a non-constant max backedge taken count!"); -} + : ExitLimit(E, M, MaxOrZero, None) {} /// Allocate memory for BackedgeTakenInfo and copy the not-taken count of each /// computable exit into a persistent ExitNotTakenInfo array. @@ -6035,8 +6018,6 @@ ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo( return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken, std::move(Predicate)); }); - assert((isa(MaxCount) || isa(MaxCount)) && - "No point in having a non-constant max backedge taken count!"); } /// Invalidate this result and free the ExitNotTakenInfo array. @@ -6298,7 +6279,7 @@ ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl( // to not. if (isa(MaxBECount) && !isa(BECount)) - MaxBECount = getConstant(getUnsignedRange(BECount).getUnsignedMax()); + MaxBECount = BECount; return ExitLimit(BECount, MaxBECount, false, {&EL0.Predicates, &EL1.Predicates}); @@ -7602,20 +7583,13 @@ ScalarEvolution::howFarToZero(const SCEV *V, const Loop *L, bool ControlsExit, loopHasNoAbnormalExits(AddRec->getLoop())) { const SCEV *Exact = getUDivExpr(Distance, CountDown ? getNegativeSCEV(Step) : Step); - const SCEV *Max = - Exact == getCouldNotCompute() - ? Exact - : getConstant(getUnsignedRange(Exact).getUnsignedMax()); - return ExitLimit(Exact, Max, false, Predicates); + return ExitLimit(Exact, Exact, false, Predicates); } // Solve the general equation. - const SCEV *E = SolveLinEquationWithOverflow(StepC->getAPInt(), - getNegativeSCEV(Start), *this); - const SCEV *M = E == getCouldNotCompute() - ? E - : getConstant(getUnsignedRange(E).getUnsignedMax()); - return ExitLimit(E, M, false, Predicates); + const SCEV *E = SolveLinEquationWithOverflow( + StepC->getAPInt(), getNegativeSCEV(Start), *this); + return ExitLimit(E, E, false, Predicates); } ScalarEvolution::ExitLimit @@ -9244,9 +9218,8 @@ ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS, getConstant(StrideForMaxBECount), false); } - if (isa(MaxBECount) && - !isa(BECount)) - MaxBECount = getConstant(getUnsignedRange(BECount).getUnsignedMax()); + if (isa(MaxBECount)) + MaxBECount = BECount; return ExitLimit(BECount, MaxBECount, MaxOrZero, Predicates); } diff --git a/llvm/test/Analysis/ScalarEvolution/nsw.ll b/llvm/test/Analysis/ScalarEvolution/nsw.ll index 39b958d..a375291 100644 --- a/llvm/test/Analysis/ScalarEvolution/nsw.ll +++ b/llvm/test/Analysis/ScalarEvolution/nsw.ll @@ -102,7 +102,7 @@ for.body.i.i: ; preds = %entry, %for.body.i. %cmp.i.i = icmp eq i32* %ptrincdec.i.i, %end br i1 %cmp.i.i, label %_ZSt4fillIPiiEvT_S1_RKT0_.exit, label %for.body.i.i ; CHECK: Loop %for.body.i.i: backedge-taken count is ((-4 + (-1 * %begin) + %end) /u 4) -; CHECK: Loop %for.body.i.i: max backedge-taken count is 4611686018427387903 +; CHECK: Loop %for.body.i.i: max backedge-taken count is ((-4 + (-1 * %begin) + %end) /u 4) _ZSt4fillIPiiEvT_S1_RKT0_.exit: ; preds = %for.body.i.i, %entry ret void } diff --git a/llvm/test/Analysis/ScalarEvolution/trip-count-pow2.ll b/llvm/test/Analysis/ScalarEvolution/trip-count-pow2.ll index 04d1b95..8d05306 100644 --- a/llvm/test/Analysis/ScalarEvolution/trip-count-pow2.ll +++ b/llvm/test/Analysis/ScalarEvolution/trip-count-pow2.ll @@ -14,7 +14,7 @@ exit: ; CHECK-LABEL: @test1 ; CHECK: Loop %loop: backedge-taken count is ((-32 + (96 * %n)) /u 32) -; CHECK: Loop %loop: max backedge-taken count is 134217727 +; CHECK: Loop %loop: max backedge-taken count is ((-32 + (96 * %n)) /u 32) } ; PR19183 @@ -32,7 +32,7 @@ exit: ; CHECK-LABEL: @test2 ; CHECK: Loop %loop: backedge-taken count is ((-32 + (32 * (%n /u 32))) /u 32) -; CHECK: Loop %loop: max backedge-taken count is 134217727 +; CHECK: Loop %loop: max backedge-taken count is ((-32 + (32 * (%n /u 32))) /u 32) } define void @test3(i32 %n) { @@ -49,7 +49,7 @@ exit: ; CHECK-LABEL: @test3 ; CHECK: Loop %loop: backedge-taken count is ((-32 + (32 * %n)) /u 32) -; CHECK: Loop %loop: max backedge-taken count is 134217727 +; CHECK: Loop %loop: max backedge-taken count is ((-32 + (32 * %n)) /u 32) } define void @test4(i32 %n) { @@ -66,7 +66,7 @@ exit: ; CHECK-LABEL: @test4 ; CHECK: Loop %loop: backedge-taken count is ((-4 + (-1431655764 * %n)) /u 4) -; CHECK: Loop %loop: max backedge-taken count is 1073741823 +; CHECK: Loop %loop: max backedge-taken count is ((-4 + (-1431655764 * %n)) /u 4) } define void @test5(i32 %n) { @@ -83,5 +83,5 @@ exit: ; CHECK-LABEL: @test5 ; CHECK: Loop %loop: backedge-taken count is ((-4 + (4 * %n)) /u 4) -; CHECK: Loop %loop: max backedge-taken count is 1073741823 +; CHECK: Loop %loop: max backedge-taken count is ((-4 + (4 * %n)) /u 4) } -- 2.7.4