Index: llvm/include/llvm/Analysis/ScalarEvolution.h =================================================================== --- llvm/include/llvm/Analysis/ScalarEvolution.h +++ llvm/include/llvm/Analysis/ScalarEvolution.h @@ -695,10 +695,12 @@ const SCEV *LHS, const SCEV *RHS); /// Test whether entry to the basic block is protected by a conditional - /// between LHS and RHS. - bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB, - ICmpInst::Predicate Pred, const SCEV *LHS, - const SCEV *RHS); + /// between LHS and RHS. Returns true if proven by dominating control flow, + /// false if disproven, or None if we can't tell. + Optional + isBasicBlockEntryGuardedByCond(const BasicBlock *BB, + ICmpInst::Predicate Pred, const SCEV *LHS, + const SCEV *RHS); /// Test whether the backedge of the loop is protected by a conditional /// between LHS and RHS. This is used to eliminate casts. Index: llvm/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/lib/Analysis/ScalarEvolution.cpp +++ llvm/lib/Analysis/ScalarEvolution.cpp @@ -9560,13 +9560,7 @@ if (KnownWithoutContext) return KnownWithoutContext; - if (isBasicBlockEntryGuardedByCond(Context->getParent(), Pred, LHS, RHS)) - return true; - else if (isBasicBlockEntryGuardedByCond(Context->getParent(), - ICmpInst::getInversePredicate(Pred), - LHS, RHS)) - return false; - return None; + return isBasicBlockEntryGuardedByCond(Context->getParent(), Pred, LHS, RHS); } bool ScalarEvolution::isKnownOnEveryIteration(ICmpInst::Predicate Pred, @@ -10010,14 +10004,17 @@ return false; } -bool ScalarEvolution::isBasicBlockEntryGuardedByCond(const BasicBlock *BB, - ICmpInst::Predicate Pred, - const SCEV *LHS, - const SCEV *RHS) { +Optional +ScalarEvolution::isBasicBlockEntryGuardedByCond(const BasicBlock *BB, + ICmpInst::Predicate Pred, + const SCEV *LHS, + const SCEV *RHS) { if (VerifyIR) assert(!verifyFunction(*BB->getParent(), &dbgs()) && "This cannot be done on broken IR!"); + const auto InversePred = ICmpInst::getInversePredicate(Pred); + // If we cannot prove strict comparison (e.g. a > b), maybe we can prove // the facts (a >= b && a != b) separately. A typical situation is when the // non-strict comparison is known from ranges and non-equality is known from @@ -10029,51 +10026,63 @@ bool ProvedNonEquality = false; auto SplitAndProve = - [&](std::function Fn) -> bool { - if (!ProvedNonStrictComparison) + [&](std::function Fn) -> Optional { + if (!ProvedNonStrictComparison) { + if (Fn(ICmpInst::getInversePredicate(NonStrictPredicate))) + return false; ProvedNonStrictComparison = Fn(NonStrictPredicate); - if (!ProvedNonEquality) + } + if (!ProvedNonEquality) { + if (Fn(ICmpInst::ICMP_EQ)) + return false; ProvedNonEquality = Fn(ICmpInst::ICMP_NE); + } if (ProvedNonStrictComparison && ProvedNonEquality) return true; - return false; + return None; }; if (ProvingStrictComparison) { auto ProofFn = [&](ICmpInst::Predicate P) { return isKnownViaNonRecursiveReasoning(P, LHS, RHS); }; - if (SplitAndProve(ProofFn)) - return true; + if (auto Opt = SplitAndProve(ProofFn)) + return Opt; } // Try to prove (Pred, LHS, RHS) using isImpliedViaGuard. - auto ProveViaGuard = [&](const BasicBlock *Block) { + auto ProveViaGuard = [&](const BasicBlock *Block) -> Optional { if (isImpliedViaGuard(Block, Pred, LHS, RHS)) return true; + if (isImpliedViaGuard(Block, InversePred, LHS, RHS)) + return false; + if (ProvingStrictComparison) { auto ProofFn = [&](ICmpInst::Predicate P) { return isImpliedViaGuard(Block, P, LHS, RHS); }; - if (SplitAndProve(ProofFn)) - return true; + if (auto Opt = SplitAndProve(ProofFn)) + return Opt; } - return false; + return None; }; // Try to prove (Pred, LHS, RHS) using isImpliedCond. - auto ProveViaCond = [&](const Value *Condition, bool Inverse) { + auto ProveViaCond = [&](const Value *Condition, bool Inverse) + -> Optional { const Instruction *Context = &BB->front(); if (isImpliedCond(Pred, LHS, RHS, Condition, Inverse, Context)) return true; + if (isImpliedCond(InversePred, LHS, RHS, Condition, Inverse, Context)) + return false; if (ProvingStrictComparison) { auto ProofFn = [&](ICmpInst::Predicate P) { return isImpliedCond(P, LHS, RHS, Condition, Inverse, Context); }; - if (SplitAndProve(ProofFn)) - return true; + if (auto Opt = SplitAndProve(ProofFn)) + return Opt; } - return false; + return None; }; // Starting at the block's predecessor, climb up the predecessor chain, as long @@ -10087,8 +10096,8 @@ PredBB = BB->getSinglePredecessor(); for (std::pair Pair(PredBB, BB); Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) { - if (ProveViaGuard(Pair.first)) - return true; + if (auto Opt = ProveViaGuard(Pair.first)) + return Opt; const BranchInst *LoopEntryPredicate = dyn_cast(Pair.first->getTerminator()); @@ -10096,9 +10105,9 @@ LoopEntryPredicate->isUnconditional()) continue; - if (ProveViaCond(LoopEntryPredicate->getCondition(), - LoopEntryPredicate->getSuccessor(0) != Pair.second)) - return true; + bool Inverse = LoopEntryPredicate->getSuccessor(0) != Pair.second; + if (auto Opt = ProveViaCond(LoopEntryPredicate->getCondition(), Inverse)) + return Opt; } // Check conditions due to any @llvm.assume intrinsics. @@ -10109,11 +10118,11 @@ if (!DT.dominates(CI, BB)) continue; - if (ProveViaCond(CI->getArgOperand(0), false)) - return true; + if (auto Opt = ProveViaCond(CI->getArgOperand(0), false)) + return Opt; } - return false; + return None; } bool ScalarEvolution::isLoopEntryGuardedByCond(const Loop *L, @@ -10134,7 +10143,8 @@ if (isKnownViaNonRecursiveReasoning(Pred, LHS, RHS)) return true; - return isBasicBlockEntryGuardedByCond(L->getHeader(), Pred, LHS, RHS); + auto ResOpt = isBasicBlockEntryGuardedByCond(L->getHeader(), Pred, LHS, RHS); + return ResOpt && *ResOpt; } bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, Index: llvm/test/Transforms/IndVarSimplify/2011-10-27-lftrnull.ll =================================================================== --- llvm/test/Transforms/IndVarSimplify/2011-10-27-lftrnull.ll +++ llvm/test/Transforms/IndVarSimplify/2011-10-27-lftrnull.ll @@ -28,13 +28,16 @@ ; CHECK-NEXT: br label [[FOR_BODY21_I:%.*]] ; CHECK: for.body21.i: ; CHECK-NEXT: [[DESTYPIXELPTR_010_I:%.*]] = phi i8* [ null, [[FOR_BODY21_LR_PH_I]] ], [ [[INCDEC_PTR_I:%.*]], [[IF_END_I126:%.*]] ] +; CHECK-NEXT: [[X_09_I:%.*]] = phi i32 [ 0, [[FOR_BODY21_LR_PH_I]] ], [ [[INC_I125:%.*]], [[IF_END_I126]] ] ; CHECK-NEXT: br i1 undef, label [[IF_END_I126]], label [[IF_ELSE_I124:%.*]] ; CHECK: if.else.i124: ; CHECK-NEXT: store i8 undef, i8* [[DESTYPIXELPTR_010_I]], align 1 ; CHECK-NEXT: br label [[IF_END_I126]] ; CHECK: if.end.i126: ; CHECK-NEXT: [[INCDEC_PTR_I]] = getelementptr inbounds i8, i8* [[DESTYPIXELPTR_010_I]], i32 1 -; CHECK-NEXT: br i1 true, label [[FOR_BODY21_I]], label [[FOR_END_I129_LOOPEXIT:%.*]] +; CHECK-NEXT: [[INC_I125]] = add nuw i32 [[X_09_I]], 1 +; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i32 [[INC_I125]], undef +; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR_BODY21_I]], label [[FOR_END_I129_LOOPEXIT:%.*]] ; CHECK: for.end.i129.loopexit: ; CHECK-NEXT: br label [[FOR_END_I129]] ; CHECK: for.end.i129: Index: llvm/test/Transforms/IndVarSimplify/X86/pr35406.ll =================================================================== --- llvm/test/Transforms/IndVarSimplify/X86/pr35406.ll +++ llvm/test/Transforms/IndVarSimplify/X86/pr35406.ll @@ -19,7 +19,7 @@ ; CHECK-NEXT: br label [[LOOP2:%.*]] ; CHECK: loop2: ; CHECK-NEXT: [[INDVARS_IV1:%.*]] = phi i64 [ [[TMP1]], [[LOOP2_PREHEADER]] ], [ [[INDVARS_IV_NEXT2:%.*]], [[LOOP2]] ] -; CHECK-NEXT: [[INDVARS_IV_NEXT2]] = add nuw nsw i64 [[INDVARS_IV1]], -1 +; CHECK-NEXT: [[INDVARS_IV_NEXT2]] = add nsw i64 [[INDVARS_IV1]], -1 ; CHECK-NEXT: [[I4:%.*]] = load atomic i64, i64* [[P1:%.*]] unordered, align 8 ; CHECK-NEXT: [[I6:%.*]] = sub i64 [[I4]], [[INDVARS_IV_NEXT2]] ; CHECK-NEXT: store atomic i64 [[I6]], i64* [[P1]] unordered, align 8 Index: llvm/test/Transforms/IndVarSimplify/eliminate-comparison.ll =================================================================== --- llvm/test/Transforms/IndVarSimplify/eliminate-comparison.ll +++ llvm/test/Transforms/IndVarSimplify/eliminate-comparison.ll @@ -575,18 +575,13 @@ ; CHECK-NEXT: [[ENTRY_COND:%.*]] = and i1 [[ENTRY_COND_0]], [[ENTRY_COND_1]] ; CHECK-NEXT: br i1 [[ENTRY_COND]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]] ; CHECK: loop.preheader: -; CHECK-NEXT: [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[LEN]], i32 0) -; CHECK-NEXT: [[TMP0:%.*]] = add nsw i32 [[SMAX]], -5 ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ -6, [[LOOP_PREHEADER]] ] ; CHECK-NEXT: call void @side_effect() -; CHECK-NEXT: [[IV_INC]] = add nsw i32 [[IV]], 1 -; CHECK-NEXT: br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]] +; CHECK-NEXT: br i1 true, label [[BE:%.*]], label [[LEAVE_LOOPEXIT:%.*]] ; CHECK: be: ; CHECK-NEXT: call void @side_effect() -; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[TMP0]] -; CHECK-NEXT: br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]] +; CHECK-NEXT: br i1 false, label [[LOOP]], label [[LEAVE_LOOPEXIT]] ; CHECK: leave.loopexit: ; CHECK-NEXT: br label [[LEAVE]] ; CHECK: leave: