+/// 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;
+}
+
+/// isLoopGuardedByCond - Test whether entry to the loop is protected by
+/// a conditional between LHS and RHS.
+bool ScalarEvolutionsImpl::isLoopGuardedByCond(const Loop *L,
+ ICmpInst::Predicate Pred,
+ 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();
+
+ if (Cond == Pred)
+ ; // An exact match.
+ else if (!ICmpInst::isTrueWhenEqual(Cond) && Pred == ICmpInst::ICMP_NE)
+ ; // The actual condition is beyond sufficient.
+ else
+ // Check a few special cases.
+ switch (Cond) {
+ case ICmpInst::ICMP_UGT:
+ if (Pred == ICmpInst::ICMP_ULT) {
+ std::swap(PreCondLHS, PreCondRHS);
+ Cond = ICmpInst::ICMP_ULT;
+ break;
+ }
+ continue;
+ case ICmpInst::ICMP_SGT:
+ if (Pred == ICmpInst::ICMP_SLT) {
+ std::swap(PreCondLHS, PreCondRHS);
+ Cond = ICmpInst::ICMP_SLT;
+ break;
+ }
+ continue;
+ case ICmpInst::ICMP_NE:
+ // Expressions like (x >u 0) are often canonicalized to (x != 0),
+ // so check for this case by checking if the NE is comparing against
+ // a minimum or maximum constant.
+ if (!ICmpInst::isTrueWhenEqual(Pred))
+ if (ConstantInt *CI = dyn_cast<ConstantInt>(PreCondRHS)) {
+ const APInt &A = CI->getValue();
+ switch (Pred) {
+ case ICmpInst::ICMP_SLT:
+ if (A.isMaxSignedValue()) break;
+ continue;
+ case ICmpInst::ICMP_SGT:
+ if (A.isMinSignedValue()) break;
+ continue;
+ case ICmpInst::ICMP_ULT:
+ if (A.isMaxValue()) break;
+ continue;
+ case ICmpInst::ICMP_UGT:
+ if (A.isMinValue()) break;
+ continue;
+ default:
+ continue;
+ }
+ Cond = ICmpInst::ICMP_NE;
+ // NE is symmetric but the original comparison may not be. Swap
+ // the operands if necessary so that they match below.
+ if (isa<SCEVConstant>(LHS))
+ std::swap(PreCondLHS, PreCondRHS);
+ break;
+ }
+ continue;
+ default:
+ // We weren't able to reconcile the condition.
+ 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;
+}
+