diff options
| -rw-r--r-- | lib/Analysis/ScalarEvolution.cpp | 112 | ||||
| -rw-r--r-- | test/Analysis/ScalarEvolution/avoid-smax.ll | 35 |
2 files changed, 92 insertions, 55 deletions
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 00a4475e28..786212ed87 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -2709,66 +2709,68 @@ 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<BranchInst>(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<BranchInst>(Preheader->getTerminator()); - if (!LoopEntryPredicate) return false; - } - ICmpInst *ICI = dyn_cast<ICmpInst>(LoopEntryPredicate->getCondition()); - if (!ICI) return false; + // Starting at the preheader, climb up the predecessor chain, as long as + // there are unique predecessors, looking for a conditional branch that + // protects the loop. + // + // This is a conservative apporoximation of a climb of the + // control-dependence predecessors. - // 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(); + for (; Preheader; PreheaderDest = Preheader, + Preheader = Preheader->getSinglePredecessor()) { - 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; - } + BranchInst *LoopEntryPredicate = + dyn_cast<BranchInst>(Preheader->getTerminator()); + if (!LoopEntryPredicate || + LoopEntryPredicate->isUnconditional()) + continue; + + ICmpInst *ICI = dyn_cast<ICmpInst>(LoopEntryPredicate->getCondition()); + if (!ICI) continue; + + // 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) continue; + std::swap(PreCondLHS, PreCondRHS); + Cond = ICmpInst::ICMP_ULT; + break; + case ICmpInst::ICMP_SGT: + if (!isSigned) continue; + std::swap(PreCondLHS, PreCondRHS); + Cond = ICmpInst::ICMP_SLT; + break; + case ICmpInst::ICMP_ULT: + if (isSigned) continue; + break; + case ICmpInst::ICMP_SLT: + if (!isSigned) continue; + break; + default: + continue; + } + + if (!PreCondLHS->getType()->isInteger()) continue; - if (!PreCondLHS->getType()->isInteger()) return false; + SCEVHandle PreCondLHSSCEV = getSCEV(PreCondLHS); + SCEVHandle PreCondRHSSCEV = getSCEV(PreCondRHS); + if ((LHS == PreCondLHSSCEV && RHS == PreCondRHSSCEV) || + (LHS == SE.getNotSCEV(PreCondRHSSCEV) && + RHS == SE.getNotSCEV(PreCondLHSSCEV))) + return true; + } - SCEVHandle PreCondLHSSCEV = getSCEV(PreCondLHS); - SCEVHandle PreCondRHSSCEV = getSCEV(PreCondRHS); - return (LHS == PreCondLHSSCEV && RHS == PreCondRHSSCEV) || - (LHS == SE.getNotSCEV(PreCondRHSSCEV) && - RHS == SE.getNotSCEV(PreCondLHSSCEV)); + return false; } /// HowManyLessThans - Return the number of times a backedge containing the diff --git a/test/Analysis/ScalarEvolution/avoid-smax.ll b/test/Analysis/ScalarEvolution/avoid-smax.ll new file mode 100644 index 0000000000..fe4b86f21e --- /dev/null +++ b/test/Analysis/ScalarEvolution/avoid-smax.ll @@ -0,0 +1,35 @@ +; RUN: llvm-as < %s | opt -scalar-evolution -analyze | grep {Loop bb3: ( -1 + %n) iterations!} + +; We don't want to use a max in the trip count expression in +; this testcase. + +define void @foo(i32 %n, i32* %p, i32* %q) nounwind { +entry: + icmp sgt i32 %n, 0 + br i1 %0, label %bb, label %return + +bb: + load i32* %q, align 4 + icmp eq i32 %1, 0 + br i1 %2, label %return, label %bb3.preheader + +bb3.preheader: + br label %bb3 + +bb3: + %i.0 = phi i32 [ %7, %bb3 ], [ 0, %bb3.preheader ] + getelementptr i32* %p, i32 %i.0 + load i32* %3, align 4 + add i32 %4, 1 + getelementptr i32* %p, i32 %i.0 + store i32 %5, i32* %6, align 4 + add i32 %i.0, 1 + icmp slt i32 %7, %n + br i1 %8, label %bb3, label %return.loopexit + +return.loopexit: + br label %return + +return: + ret void +} |