- 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;
+/// isNecessaryCond - Test whether the given CondValue value is a condition
+/// which is at least as strict as the one described by Pred, LHS, and RHS.
+bool ScalarEvolution::isNecessaryCond(Value *CondValue,
+ ICmpInst::Predicate Pred,
+ const SCEV *LHS, const SCEV *RHS,
+ bool Inverse) {
+ // Recursivly handle And and Or conditions.
+ if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CondValue)) {
+ if (BO->getOpcode() == Instruction::And) {
+ if (!Inverse)
+ return isNecessaryCond(BO->getOperand(0), Pred, LHS, RHS, Inverse) ||
+ isNecessaryCond(BO->getOperand(1), Pred, LHS, RHS, Inverse);
+ } else if (BO->getOpcode() == Instruction::Or) {
+ if (Inverse)
+ return isNecessaryCond(BO->getOperand(0), Pred, LHS, RHS, Inverse) ||
+ isNecessaryCond(BO->getOperand(1), Pred, LHS, RHS, Inverse);
+ }
+ }
+
+ ICmpInst *ICI = dyn_cast<ICmpInst>(CondValue);
+ 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 (Inverse)
+ Cond = ICI->getInversePredicate();
+ else
+ Cond = ICI->getPredicate();
+
+ 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;
+ }
+ return false;
+ case ICmpInst::ICMP_SGT:
+ if (Pred == ICmpInst::ICMP_SLT) {
+ std::swap(PreCondLHS, PreCondRHS);
+ Cond = ICmpInst::ICMP_SLT;
+ break;
+ }
+ return false;
+ 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;
+ return false;
+ case ICmpInst::ICMP_SGT:
+ if (A.isMinSignedValue()) break;
+ return false;
+ case ICmpInst::ICMP_ULT:
+ if (A.isMaxValue()) break;
+ return false;
+ case ICmpInst::ICMP_UGT:
+ if (A.isMinValue()) break;
+ return false;
+ default:
+ return false;
+ }
+ 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);