+/// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB
+/// (which may not be an immediate predecessor) which has exactly one
+/// successor from which BB is reachable, or null if no such block is
+/// found.
+///
+BasicBlock *
+ScalarEvolutionsImpl::getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB) {
+ // If the block has a unique predecessor, the predecessor must have
+ // no other successors from which BB is reachable.
+ if (BasicBlock *Pred = BB->getSinglePredecessor())
+ return Pred;
+
+ // A loop's header is defined to be a block that dominates the loop.
+ // If the loop has a preheader, it must be a block that has exactly
+ // one successor that can reach BB. This is slightly more strict
+ // than necessary, but works if critical edges are split.
+ if (Loop *L = LI.getLoopFor(BB))
+ return L->getLoopPreheader();
+
+ return 0;
+}
+
+/// executesAtLeastOnce - Test whether entry to the loop is protected by
+/// a conditional between LHS and RHS.
+bool ScalarEvolutionsImpl::executesAtLeastOnce(const Loop *L, bool isSigned,
+ bool trueWhenEqual,
+ SCEV *LHS, SCEV *RHS) {
+ BasicBlock *Preheader = L->getLoopPreheader();
+ BasicBlock *PreheaderDest = L->getHeader();
+
+ // Starting at the preheader, climb up the predecessor chain, as long as
+ // there are predecessors that can be found that have unique successors
+ // leading to the original header.
+ for (; Preheader;
+ PreheaderDest = Preheader,
+ Preheader = getPredecessorWithUniqueSuccessorForBB(Preheader)) {
+
+ 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 || trueWhenEqual) continue;
+ std::swap(PreCondLHS, PreCondRHS);
+ Cond = ICmpInst::ICMP_ULT;
+ break;
+ case ICmpInst::ICMP_SGT:
+ if (!isSigned || trueWhenEqual) continue;
+ std::swap(PreCondLHS, PreCondRHS);
+ Cond = ICmpInst::ICMP_SLT;
+ break;
+ case ICmpInst::ICMP_ULT:
+ if (isSigned || trueWhenEqual) continue;
+ break;
+ case ICmpInst::ICMP_SLT:
+ if (!isSigned || trueWhenEqual) continue;
+ break;
+ case ICmpInst::ICMP_UGE:
+ if (isSigned || !trueWhenEqual) continue;
+ std::swap(PreCondLHS, PreCondRHS);
+ Cond = ICmpInst::ICMP_ULE;
+ break;
+ case ICmpInst::ICMP_SGE:
+ if (!isSigned || !trueWhenEqual) continue;
+ std::swap(PreCondLHS, PreCondRHS);
+ Cond = ICmpInst::ICMP_SLE;
+ break;
+ case ICmpInst::ICMP_ULE:
+ if (isSigned || !trueWhenEqual) continue;
+ break;
+ case ICmpInst::ICMP_SLE:
+ if (!isSigned || !trueWhenEqual) continue;
+ break;
+ default:
+ continue;
+ }
+
+ if (!PreCondLHS->getType()->isInteger()) continue;
+
+ SCEVHandle PreCondLHSSCEV = getSCEV(PreCondLHS);
+ SCEVHandle PreCondRHSSCEV = getSCEV(PreCondRHS);
+ if ((LHS == PreCondLHSSCEV && RHS == PreCondRHSSCEV) ||
+ (LHS == SE.getNotSCEV(PreCondRHSSCEV) &&
+ RHS == SE.getNotSCEV(PreCondLHSSCEV)))
+ return true;
+ }
+
+ return false;
+}
+
+/// potentialInfiniteLoop - Test whether the loop might jump over the exit value
+/// due to wrapping around 2^n.
+bool ScalarEvolutionsImpl::potentialInfiniteLoop(SCEV *Stride, SCEV *RHS,
+ bool isSigned, bool trueWhenEqual) {
+ // Return true when the distance from RHS to maxint > Stride.
+
+ if (!isa<SCEVConstant>(Stride))
+ return true;
+ SCEVConstant *SC = cast<SCEVConstant>(Stride);
+
+ if (SC->getValue()->isZero())
+ return true;
+ if (!trueWhenEqual && SC->getValue()->isOne())
+ return false;
+
+ if (!isa<SCEVConstant>(RHS))
+ return true;
+ SCEVConstant *R = cast<SCEVConstant>(RHS);
+
+ if (isSigned)
+ return true; // XXX: because we don't have an sdiv scev.
+
+ // If negative, it wraps around every iteration, but we don't care about that.
+ APInt S = SC->getValue()->getValue().abs();
+
+ APInt Dist = APInt::getMaxValue(R->getValue()->getBitWidth()) -
+ R->getValue()->getValue();
+
+ if (trueWhenEqual)
+ return !S.ult(Dist);
+ else
+ return !S.ule(Dist);
+}
+