Index: llvm/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/lib/Analysis/ScalarEvolution.cpp +++ llvm/lib/Analysis/ScalarEvolution.cpp @@ -11102,6 +11102,24 @@ isKnownPredicateAt(SignFlippedPred, ArLHS, RHS, CtxI)) return ScalarEvolution::LoopInvariantPredicate(Pred, ArLHS->getStart(), RHS); + + // Given preconditions + // (1) Positive step + // (2) RHS >=s 0 + // (3) Unsigned comparison is guarded by the same signed comparison + // + // We can replace the loop variant 'ArLHS getStepRecurrence(*this)) && + isKnownNonNegative(RHS) && + isBasicBlockEntryGuardedByCond(CtxI->getParent(), SignFlippedPred, LHS, + RHS)) { + return ScalarEvolution::LoopInvariantPredicate(Pred, ArLHS->getStart(), + RHS); + } } } Index: llvm/lib/Transforms/Utils/SimplifyIndVar.cpp =================================================================== --- llvm/lib/Transforms/Utils/SimplifyIndVar.cpp +++ llvm/lib/Transforms/Utils/SimplifyIndVar.cpp @@ -93,6 +93,7 @@ void replaceRemWithNumeratorOrZero(BinaryOperator *Rem); void replaceSRemWithURem(BinaryOperator *Rem); bool eliminateSDiv(BinaryOperator *SDiv); + bool strengthenBinaryOp(BinaryOperator *BO, Instruction *IVOperand); bool strengthenOverflowingOperation(BinaryOperator *OBO, Instruction *IVOperand); bool strengthenRightShift(BinaryOperator *BO, Instruction *IVOperand); @@ -747,6 +748,13 @@ return true; } +bool SimplifyIndvar::strengthenBinaryOp(BinaryOperator *BO, + Instruction *IVOperand) { + return (isa(BO) && + strengthenOverflowingOperation(BO, IVOperand)) || + (isa(BO) && strengthenRightShift(BO, IVOperand)); +} + /// Annotate BO with nsw / nuw if it provably does not signed-overflow / /// unsigned-overflow. Returns true if anything changed, false otherwise. bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO, @@ -876,6 +884,14 @@ // do for loop header phis that use each other. pushIVUsers(CurrIV, L, Simplified, SimpleIVUsers); + // Annotate binary operators primarily to give more context for analyzes and + // transformations with users, which are visited before binary operators. E.g. + // for IV comparison invariant making + for (auto [UseInst, IVOperand] : SimpleIVUsers) + if (BinaryOperator *BO = dyn_cast(UseInst)) + if (strengthenBinaryOp(BO, IVOperand)) + pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers); + while (!SimpleIVUsers.empty()) { std::pair UseOper = SimpleIVUsers.pop_back_val(); @@ -917,9 +933,7 @@ } if (BinaryOperator *BO = dyn_cast(UseInst)) { - if ((isa(BO) && - strengthenOverflowingOperation(BO, IVOperand)) || - (isa(BO) && strengthenRightShift(BO, IVOperand))) { + if (strengthenBinaryOp(BO, IVOperand)) { // re-queue uses of the now modified binary operator and fall // through to the checks that remain. pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers); Index: llvm/test/Transforms/IndVarSimplify/cycled_phis.ll =================================================================== --- llvm/test/Transforms/IndVarSimplify/cycled_phis.ll +++ llvm/test/Transforms/IndVarSimplify/cycled_phis.ll @@ -67,7 +67,7 @@ ret i32 %iv } -; TODO: The 2nd check can be made invariant. +; The 2nd check can be made invariant. ; slt and ult checks are equivalent. When IV is negative, slt check will pass and ult will ; fail. Because IV is incrementing, this will fail on 1st iteration or never. define i32 @unknown.start(i32 %start, ptr %len.ptr) { @@ -82,7 +82,7 @@ ; CHECK-NEXT: [[SIGNED_CMP:%.*]] = icmp slt i32 [[IV]], [[LEN]] ; CHECK-NEXT: br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]] ; CHECK: signed.passed: -; CHECK-NEXT: [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV]], [[LEN]] +; CHECK-NEXT: [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[START]], [[LEN]] ; CHECK-NEXT: br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]] ; CHECK: backedge: ; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 @@ -132,7 +132,7 @@ } -; TODO: We should be able to prove that: +; We should be able to prove that: ; - %sibling.iv.next is non-negative; ; - therefore, %iv is non-negative; ; - therefore, unsigned check can be removed. @@ -155,11 +155,10 @@ ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[SIBLING_IV_NEXT_LCSSA]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] -; CHECK-NEXT: [[SIGNED_CMP:%.*]] = icmp slt i32 [[IV]], [[LEN]] +; CHECK-NEXT: [[SIGNED_CMP:%.*]] = icmp ult i32 [[IV]], [[LEN]] ; CHECK-NEXT: br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]] ; CHECK: signed.passed: -; CHECK-NEXT: [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV]], [[LEN]] -; CHECK-NEXT: br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]] +; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]] ; CHECK: backedge: ; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 ; CHECK-NEXT: [[COND:%.*]] = call i1 @cond() @@ -354,7 +353,7 @@ ; CHECK-NEXT: [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV_START]], [[LEN]] ; CHECK-NEXT: br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]] ; CHECK: backedge: -; CHECK-NEXT: [[IV_NEXT]] = add nsw i32 [[IV]], 1 +; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 ; CHECK-NEXT: [[COND:%.*]] = call i1 @cond() ; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[OUTER_LOOP_BACKEDGE]] ; CHECK: outer.loop.backedge: @@ -472,7 +471,7 @@ ; CHECK-NEXT: [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV_START]], [[LEN]] ; CHECK-NEXT: br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]] ; CHECK: backedge: -; CHECK-NEXT: [[IV_NEXT]] = add nsw i32 [[IV]], 1 +; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 ; CHECK-NEXT: [[COND:%.*]] = call i1 @cond() ; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[OUTER_LOOP_SELECTION:%.*]] ; CHECK: outer.loop.selection: Index: llvm/test/Transforms/IndVarSimplify/pr57247.ll =================================================================== --- llvm/test/Transforms/IndVarSimplify/pr57247.ll +++ llvm/test/Transforms/IndVarSimplify/pr57247.ll @@ -102,7 +102,7 @@ ; CHECK-NEXT: br label [[OUTER_LOOP:%.*]] ; CHECK: outer.loop: ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 2147483640, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[OUTER_LATCH:%.*]] ] -; CHECK-NEXT: [[CHECK_1:%.*]] = icmp ult i32 [[IV]], 2147483647 +; CHECK-NEXT: [[CHECK_1:%.*]] = icmp ult i32 2147483640, 2147483647 ; CHECK-NEXT: br label [[INNER_LOOP:%.*]] ; CHECK: inner.loop: ; CHECK-NEXT: [[STOREMERGE611_I:%.*]] = phi i64 [ 0, [[OUTER_LOOP]] ], [ [[ADD_I:%.*]], [[INNER_LATCH:%.*]] ]