From 59cff12f8880797518c8c37f068fe75cfdc54536 Mon Sep 17 00:00:00 2001 From: Nick Lewycky Date: Sat, 12 Jul 2008 07:41:32 +0000 Subject: [PATCH] Stop creating extraneous smax/umax in SCEV. This removes a regression where we started complicating many loops ('for' loops, in fact). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53508 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/ScalarEvolution.cpp | 85 +++++++++++++++++-- .../ScalarEvolution/2007-08-06-Unsigned.ll | 2 +- .../2008-07-12-UnneededSelect1.ll | 36 ++++++++ .../2008-07-12-UnneededSelect2.ll | 30 +++++++ 4 files changed, 146 insertions(+), 7 deletions(-) create mode 100644 test/Analysis/ScalarEvolution/2008-07-12-UnneededSelect1.ll create mode 100644 test/Analysis/ScalarEvolution/2008-07-12-UnneededSelect2.ll diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index ab0de275b04..d3ff2a5afbb 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -1431,6 +1431,10 @@ namespace { SCEVHandle HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, bool isSigned); + /// executesAtLeastOnce - Test whether entry to the loop is protected by + /// a conditional between LHS and RHS. + bool executesAtLeastOnce(const Loop *L, bool isSigned, SCEV *LHS, SCEV *RHS); + /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is /// in the header of its containing loop, we know the loop executes a /// constant number of times, and the PHI node is just a recurrence @@ -2612,6 +2616,70 @@ SCEVHandle ScalarEvolutionsImpl::HowFarToNonZero(SCEV *V, const Loop *L) { return UnknownValue; } +/// executesAtLeastOnce - Test whether entry to the loop is protected by +/// a conditional between LHS and RHS. +bool ScalarEvolutionsImpl::executesAtLeastOnce(const Loop *L, bool isSigned, + SCEV *LHS, SCEV *RHS) { + BasicBlock *Preheader = L->getLoopPreheader(); + BasicBlock *PreheaderDest = L->getHeader(); + if (Preheader == 0) return false; + + BranchInst *LoopEntryPredicate = + dyn_cast(Preheader->getTerminator()); + if (!LoopEntryPredicate) return false; + + // This might be a critical edge broken out. If the loop preheader ends in + // an unconditional branch to the loop, check to see if the preheader has a + // single predecessor, and if so, look for its terminator. + while (LoopEntryPredicate->isUnconditional()) { + PreheaderDest = Preheader; + Preheader = Preheader->getSinglePredecessor(); + if (!Preheader) return false; // Multiple preds. + + LoopEntryPredicate = + dyn_cast(Preheader->getTerminator()); + if (!LoopEntryPredicate) return false; + } + + ICmpInst *ICI = dyn_cast(LoopEntryPredicate->getCondition()); + if (!ICI) return false; + + // Now that we found a conditional branch that dominates the loop, check to + // see if it is the comparison we are looking for. + Value *PreCondLHS = ICI->getOperand(0); + Value *PreCondRHS = ICI->getOperand(1); + ICmpInst::Predicate Cond; + if (LoopEntryPredicate->getSuccessor(0) == PreheaderDest) + Cond = ICI->getPredicate(); + else + Cond = ICI->getInversePredicate(); + + switch (Cond) { + case ICmpInst::ICMP_UGT: + if (isSigned) return false; + std::swap(PreCondLHS, PreCondRHS); + Cond = ICmpInst::ICMP_ULT; + break; + case ICmpInst::ICMP_SGT: + if (!isSigned) return false; + std::swap(PreCondLHS, PreCondRHS); + Cond = ICmpInst::ICMP_SLT; + break; + case ICmpInst::ICMP_ULT: + if (isSigned) return false; + break; + case ICmpInst::ICMP_SLT: + if (!isSigned) return false; + break; + default: + return false; + } + + if (!PreCondLHS->getType()->isInteger()) return false; + + return LHS == getSCEV(PreCondLHS) && RHS == getSCEV(PreCondRHS); +} + /// HowManyLessThans - Return the number of times a backedge containing the /// specified less-than comparison will execute. If not computable, return /// UnknownValue. @@ -2640,12 +2708,17 @@ HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, bool isSigned) { // Then, we get the value of the LHS in the first iteration in which the // above condition doesn't hold. This equals to max(m,n). - SCEVHandle End = isSigned ? SE.getSMaxExpr(RHS, Start) - : SE.getUMaxExpr(RHS, Start); - - // Finally, we subtract these two values to get the number of times the - // backedge is executed: max(m,n)-n. - return SE.getMinusSCEV(End, Start); + if (executesAtLeastOnce(L, isSigned, + SE.getMinusSCEV(AddRec->getOperand(0), One), RHS)) + return SE.getMinusSCEV(RHS, Start); + else { + SCEVHandle End = isSigned ? SE.getSMaxExpr(RHS, Start) + : SE.getUMaxExpr(RHS, Start); + + // Finally, we subtract these two values to get the number of times the + // backedge is executed: max(m,n)-n. + return SE.getMinusSCEV(End, Start); + } } return UnknownValue; diff --git a/test/Analysis/ScalarEvolution/2007-08-06-Unsigned.ll b/test/Analysis/ScalarEvolution/2007-08-06-Unsigned.ll index 23ffc650b0d..e725852cea1 100644 --- a/test/Analysis/ScalarEvolution/2007-08-06-Unsigned.ll +++ b/test/Analysis/ScalarEvolution/2007-08-06-Unsigned.ll @@ -1,4 +1,4 @@ -; RUN: llvm-as < %s | opt -scalar-evolution -analyze | grep {Loop bb: ( -1 + ( -1 \\* %x) + (( 1 + %x) umax %y)) iterations!} +; RUN: llvm-as < %s | opt -scalar-evolution -analyze | grep {Loop bb: ( -1 + ( -1 \\* %x) + %y) iterations!} ; PR1597 define i32 @f(i32 %x, i32 %y) { diff --git a/test/Analysis/ScalarEvolution/2008-07-12-UnneededSelect1.ll b/test/Analysis/ScalarEvolution/2008-07-12-UnneededSelect1.ll new file mode 100644 index 00000000000..a0fcad71314 --- /dev/null +++ b/test/Analysis/ScalarEvolution/2008-07-12-UnneededSelect1.ll @@ -0,0 +1,36 @@ +; RUN: llvm-as < %s | opt -analyze -scalar-evolution |& not grep smax +; PR2261 + +@lut = common global [256 x i8] zeroinitializer, align 32 ; <[256 x i8]*> [#uses=1] + +define void @foo(i32 %count, i32* %srcptr, i32* %dstptr) nounwind { +entry: + icmp sgt i32 %count, 0 ; :0 [#uses=1] + br i1 %0, label %bb.nph, label %return + +bb.nph: ; preds = %entry + br label %bb + +bb: ; preds = %bb1, %bb.nph + %j.01 = phi i32 [ %8, %bb1 ], [ 0, %bb.nph ] ; [#uses=1] + load i32* %srcptr, align 4 ; :1 [#uses=2] + and i32 %1, 255 ; :2 [#uses=1] + and i32 %1, -256 ; :3 [#uses=1] + getelementptr [256 x i8]* @lut, i32 0, i32 %2 ; :4 [#uses=1] + load i8* %4, align 1 ; :5 [#uses=1] + zext i8 %5 to i32 ; :6 [#uses=1] + or i32 %6, %3 ; :7 [#uses=1] + store i32 %7, i32* %dstptr, align 4 + add i32 %j.01, 1 ; :8 [#uses=2] + br label %bb1 + +bb1: ; preds = %bb + icmp slt i32 %8, %count ; :9 [#uses=1] + br i1 %9, label %bb, label %bb1.return_crit_edge + +bb1.return_crit_edge: ; preds = %bb1 + br label %return + +return: ; preds = %bb1.return_crit_edge, %entry + ret void +} diff --git a/test/Analysis/ScalarEvolution/2008-07-12-UnneededSelect2.ll b/test/Analysis/ScalarEvolution/2008-07-12-UnneededSelect2.ll new file mode 100644 index 00000000000..5501ee28869 --- /dev/null +++ b/test/Analysis/ScalarEvolution/2008-07-12-UnneededSelect2.ll @@ -0,0 +1,30 @@ +; RUN: llvm-as < %s | opt -analyze -scalar-evolution |& not grep smax +; PR2070 + +define i32 @a(i32 %x) nounwind { +entry: + icmp sgt i32 %x, 1 ; :0 [#uses=1] + br i1 %0, label %bb.nph, label %bb2 + +bb.nph: ; preds = %entry + br label %bb + +bb: ; preds = %bb1, %bb.nph + %z.02 = phi i32 [ %1, %bb1 ], [ 1, %bb.nph ] ; [#uses=1] + %i.01 = phi i32 [ %2, %bb1 ], [ 1, %bb.nph ] ; [#uses=2] + mul i32 %z.02, %i.01 ; :1 [#uses=2] + add i32 %i.01, 1 ; :2 [#uses=2] + br label %bb1 + +bb1: ; preds = %bb + icmp slt i32 %2, %x ; :3 [#uses=1] + br i1 %3, label %bb, label %bb1.bb2_crit_edge + +bb1.bb2_crit_edge: ; preds = %bb1 + %.lcssa = phi i32 [ %1, %bb1 ] ; [#uses=1] + br label %bb2 + +bb2: ; preds = %bb1.bb2_crit_edge, %entry + %z.0.lcssa = phi i32 [ %.lcssa, %bb1.bb2_crit_edge ], [ 1, %entry ] ; [#uses=1] + ret i32 %z.0.lcssa +} -- 2.34.1