Index: llvm/lib/Transforms/Utils/SimplifyIndVar.cpp =================================================================== --- llvm/lib/Transforms/Utils/SimplifyIndVar.cpp +++ llvm/lib/Transforms/Utils/SimplifyIndVar.cpp @@ -242,6 +242,83 @@ return true; } +static bool eliminateIVComparisonHelper(ICmpInst::Predicate Pred, + ICmpInst *ICmp, const SCEV *S, + const SCEV *X, const Loop *ICmpLoop, + ScalarEvolution *SE) { + if (SE->isKnownPredicate(Pred, S, X)) + return true; + + auto *AR = dyn_cast(S); + // TODO: Lift affinity limitation in the future. + if (!AR || !AR->isAffine()) + return false; + + // The predicate must be monotonic. + switch (Pred) { + default: + return false; + case ICmpInst::ICMP_SLT: + case ICmpInst::ICMP_ULT: + case ICmpInst::ICMP_SGT: + case ICmpInst::ICMP_UGT: + case ICmpInst::ICMP_SLE: + case ICmpInst::ICMP_ULE: + case ICmpInst::ICMP_SGE: + case ICmpInst::ICMP_UGE: + break; + } + + // First, check the predicate on the 1st iteration. + const SCEV *Base = AR->getOperand(0); + if (!SE->isKnownPredicate(Pred, Base, X)) + return false; + + // TODO: Support steps other than +/- 1. + const SCEV *Step = AR->getOperand(1); + auto *One = SE->getOne(Step->getType()); + auto *MinusOne = SE->getNegativeSCEV(One); + if (Step != One && Step != MinusOne) + return false; + // Compute how much max iteration the loop will make if we eliminate this + // comparison. + // TODO: This should be moved to optimizeLoopExits to avoid recomputation of + // this value over and over. Unfortunately, if the condition is not + // eliminated at this point, its predicate turn to unsigned. And SCEV has + // really big troubles proving facts for unsigned predicates. + // As example, see "isKnownPredicateViaNoOverflow" (only signed preds are + // supported), "isImpliedViaOperations" (only signed gt is supported), etc. + // When it all is fixed, we should definitely move it there. + const SCEV *MaxIter = SE->computeMaxBackedgeTakenCount(ICmpLoop); + if (isa(MaxIter)) + return false; + // Type mismatch here means that MaxIter is potentially larger than max + // unsigned value in base type, which mean we cannot prove no wrap for the + // indvar. + if (Base->getType() != MaxIter->getType()) + return false; + // Value of IV on max possible last iteration. + const SCEV *Last = SE->getAddExpr(Base, SE->getMulExpr(Step, MaxIter)); + // Does it still meet the requirement? + if (!SE->isKnownPredicate(Pred, Last, X)) + return false; + // Because step is +/- 1 and MaxIter has same type as Base (i.e. it does + // not exceed max unsigned value of this type), this effectively proves + // that there is no wrap during the iteration. To prove that there is no + // signed/unsigned wrap, we need to check that + // Base <= Last for step = 1 or Base >= Last for step = -1. + ICmpInst::Predicate OverflowPred; + if (Step == One) + OverflowPred = + CmpInst::isSigned(Pred) ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; + else + OverflowPred = + CmpInst::isSigned(Pred) ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE; + if (!SE->isKnownPredicate(OverflowPred, Base, Last)) + return false; + return true; +} + /// SimplifyIVUsers helper for eliminating useless /// comparisons against an induction variable. void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) { @@ -263,11 +340,12 @@ // If the condition is always true or always false, replace it with // a constant value. - if (SE->isKnownPredicate(Pred, S, X)) { + if (eliminateIVComparisonHelper(Pred, ICmp, S, X, ICmpLoop, SE)) { ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext())); DeadInsts.emplace_back(ICmp); LLVM_DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n'); - } else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) { + } else if (eliminateIVComparisonHelper(ICmpInst::getInversePredicate(Pred), + ICmp, S, X, ICmpLoop, SE)) { ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext())); DeadInsts.emplace_back(ICmp); LLVM_DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n'); Index: llvm/test/Transforms/IndVarSimplify/monotonic_checks.ll =================================================================== --- llvm/test/Transforms/IndVarSimplify/monotonic_checks.ll +++ llvm/test/Transforms/IndVarSimplify/monotonic_checks.ll @@ -12,8 +12,7 @@ ; CHECK: loop: ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV_NEXT]] = add nsw i32 [[IV]], -1 -; CHECK-NEXT: [[RC:%.*]] = icmp slt i32 [[IV_NEXT]], [[LEN]] -; CHECK-NEXT: br i1 [[RC]], label [[BACKEDGE]], label [[FAIL:%.*]] +; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]] ; CHECK: backedge: ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 0 ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]] @@ -93,8 +92,7 @@ ; CHECK: loop: ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], 1 -; CHECK-NEXT: [[RC:%.*]] = icmp sgt i32 [[IV_NEXT]], [[LEN]] -; CHECK-NEXT: br i1 [[RC]], label [[BACKEDGE]], label [[FAIL:%.*]] +; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]] ; CHECK: backedge: ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 0 ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]] @@ -172,8 +170,7 @@ ; CHECK: loop: ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 -; CHECK-NEXT: [[RC:%.*]] = icmp ugt i32 [[IV_NEXT]], [[LEN]] -; CHECK-NEXT: br i1 [[RC]], label [[BACKEDGE]], label [[FAIL:%.*]] +; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]] ; CHECK: backedge: ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 1000 ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]] @@ -211,8 +208,7 @@ ; CHECK: loop: ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV_NEXT]] = add nsw i32 [[IV]], -1 -; CHECK-NEXT: [[RC:%.*]] = icmp slt i32 [[IV_NEXT]], [[LEN]] -; CHECK-NEXT: br i1 [[RC]], label [[BACKEDGE]], label [[FAIL:%.*]] +; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]] ; CHECK: backedge: ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 0 ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]] Index: llvm/test/Transforms/IndVarSimplify/predicated_ranges.ll =================================================================== --- llvm/test/Transforms/IndVarSimplify/predicated_ranges.ll +++ llvm/test/Transforms/IndVarSimplify/predicated_ranges.ll @@ -71,8 +71,7 @@ ; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]] ; CHECK: range_check_block: ; CHECK-NEXT: [[IV_NEXT]] = sub i32 [[IV]], 1 -; CHECK-NEXT: [[RANGE_CHECK:%.*]] = icmp slt i32 [[IV_NEXT]], [[LEN]] -; CHECK-NEXT: br i1 [[RANGE_CHECK]], label [[BACKEDGE]], label [[FAIL:%.*]] +; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]] ; CHECK: backedge: ; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, i32* [[P]], i32 [[IV]] ; CHECK-NEXT: [[EL:%.*]] = load i32, i32* [[EL_PTR]], align 4