Index: llvm/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/lib/Analysis/ScalarEvolution.cpp +++ llvm/lib/Analysis/ScalarEvolution.cpp @@ -15071,6 +15071,59 @@ return I != RewriteMap.end() ? I->second : S; }; + // If \p Expr is a min/max expression, adds a pair of rewrites of its + // arguments based on the following rules: + // 'min(a, b) >= c' -> '(a >= c) && (b >= c)', + // 'min(a, b) > c' -> '(a >= c + 1) && (b >= c + 1)', + // 'max(a, b) <= c' -> '(a <= c) && (b <= c)', + // 'max(a, b) < c' -> '(a <= c - 1) && (b <= c - 1)'. + // \p RHS has to be either the unchanged RHS of the current guard, or plus + // or minus one of it depending on the predicate. + auto AddMinMaxRewrites = [&](const SCEV *Expr, const SCEV *RHS) { + switch (Expr->getSCEVType()) { + case scUMaxExpr: + case scSMaxExpr: + case scUMinExpr: + case scSMinExpr: + break; + default: + llvm_unreachable("Unexpected expression type"); + } + auto *MinMaxExpr = cast(Expr); + auto *Op1 = MinMaxExpr->getOperand(0); + auto *Op2 = MinMaxExpr->getOperand(1); + auto *RewrittenOp1 = GetMaybeRewritten(Op1); + auto *RewrittenOp2 = GetMaybeRewritten(Op2); + const SCEV *Op1Rewrite = nullptr; + const SCEV *Op2Rewrite = nullptr; + switch (Predicate) { + case CmpInst::ICMP_ULT: + case CmpInst::ICMP_ULE: + Op1Rewrite = getUMinExpr(RewrittenOp1, RHS); + Op2Rewrite = getUMinExpr(RewrittenOp2, RHS); + break; + case CmpInst::ICMP_SLT: + case CmpInst::ICMP_SLE: + Op1Rewrite = getSMinExpr(RewrittenOp1, RHS); + Op2Rewrite = getSMinExpr(RewrittenOp2, RHS); + break; + case CmpInst::ICMP_UGT: + case CmpInst::ICMP_UGE: + Op1Rewrite = getUMaxExpr(RewrittenOp1, RHS); + Op2Rewrite = getUMaxExpr(RewrittenOp2, RHS); + break; + case CmpInst::ICMP_SGT: + case CmpInst::ICMP_SGE: + Op1Rewrite = getSMaxExpr(RewrittenOp1, RHS); + Op2Rewrite = getSMaxExpr(RewrittenOp2, RHS); + break; + default: + llvm_unreachable("Unexpected expression type"); + } + AddRewrite(Op1, RewrittenOp1, Op1Rewrite); + AddRewrite(Op2, RewrittenOp2, Op2Rewrite); + }; + const SCEV *RewrittenLHS = GetMaybeRewritten(LHS); const SCEV *RewrittenRHS = nullptr; @@ -15079,33 +15132,68 @@ if (RHS->getType()->isPointerTy()) break; const SCEV *One = getOne(RHS->getType()); - RewrittenRHS = - getUMinExpr(RewrittenLHS, getMinusSCEV(getUMaxExpr(RHS, One), One)); + const SCEV *RHSMinusOne = getMinusSCEV(getUMaxExpr(RHS, One), One); + // umax(a, b) (a <=u c - 1) && (b <=u c - 1) + if (isa(RewrittenLHS)) + AddMinMaxRewrites(RewrittenLHS, RHSMinusOne); + else + RewrittenRHS = getUMinExpr(RewrittenLHS, RHSMinusOne); break; } - case CmpInst::ICMP_SLT: - RewrittenRHS = - getSMinExpr(RewrittenLHS, getMinusSCEV(RHS, getOne(RHS->getType()))); + case CmpInst::ICMP_SLT: { + const SCEV *RHSMinusOne = getMinusSCEV(RHS, getOne(RHS->getType())); + // smax(a, b) (a <=s c - 1) && (b <=s c - 1) + if (isa(RewrittenLHS)) + AddMinMaxRewrites(RewrittenLHS, RHSMinusOne); + else + RewrittenRHS = getSMinExpr(RewrittenLHS, RHSMinusOne); break; + } case CmpInst::ICMP_ULE: - RewrittenRHS = getUMinExpr(RewrittenLHS, RHS); + // umax(a, b) <=u c -> a <=u c && b <=u c + if (isa(RewrittenLHS)) + AddMinMaxRewrites(RewrittenLHS, RHS); + else + RewrittenRHS = getUMinExpr(RewrittenLHS, RHS); break; case CmpInst::ICMP_SLE: - RewrittenRHS = getSMinExpr(RewrittenLHS, RHS); + // smax(a, b) <=s c -> a <=s c && b <=s c + if (isa(RewrittenLHS)) + AddMinMaxRewrites(RewrittenLHS, RHS); + else + RewrittenRHS = getSMinExpr(RewrittenLHS, RHS); break; - case CmpInst::ICMP_UGT: - RewrittenRHS = - getUMaxExpr(RewrittenLHS, getAddExpr(RHS, getOne(RHS->getType()))); + case CmpInst::ICMP_UGT: { + const SCEV *RHSPlusOne = getAddExpr(RHS, getOne(RHS->getType())); + // umin(a, b) >u c -> (a >=u c + 1) && (b >=u c + 1) + if (isa(RewrittenLHS)) + AddMinMaxRewrites(RewrittenLHS, RHSPlusOne); + else + RewrittenRHS = getUMaxExpr(RewrittenLHS, RHSPlusOne); break; - case CmpInst::ICMP_SGT: - RewrittenRHS = - getSMaxExpr(RewrittenLHS, getAddExpr(RHS, getOne(RHS->getType()))); + } + case CmpInst::ICMP_SGT: { + const SCEV *RHSPlusOne = getAddExpr(RHS, getOne(RHS->getType())); + // smin(a, b) >s c -> (a >=s c + 1) && (b >=s c + 1) + if (isa(RewrittenLHS)) + AddMinMaxRewrites(RewrittenLHS, RHSPlusOne); + else + RewrittenRHS = getSMaxExpr(RewrittenLHS, RHSPlusOne); break; + } case CmpInst::ICMP_UGE: - RewrittenRHS = getUMaxExpr(RewrittenLHS, RHS); + // umin(a, b) >=u c -> a >=u c && b >=u c + if (isa(RewrittenLHS)) + AddMinMaxRewrites(RewrittenLHS, RHS); + else + RewrittenRHS = getUMaxExpr(RewrittenLHS, RHS); break; case CmpInst::ICMP_SGE: - RewrittenRHS = getSMaxExpr(RewrittenLHS, RHS); + // smin(a, b) >=s c -> a >=s c && b >=s c + if (isa(RewrittenLHS)) + AddMinMaxRewrites(RewrittenLHS, RHS); + else + RewrittenRHS = getSMaxExpr(RewrittenLHS, RHS); break; case CmpInst::ICMP_EQ: if (isa(RHS)) Index: llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info-rewrite-expressions.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info-rewrite-expressions.ll +++ llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info-rewrite-expressions.ll @@ -476,14 +476,14 @@ ; CHECK-NEXT: %n.vec = and i64 %ext, 28 ; CHECK-NEXT: --> (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64)) U: [0,29) S: [0,29) ; CHECK-NEXT: %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ] -; CHECK-NEXT: --> {0,+,4}<%loop> U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 * ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))) /u 4)) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {0,+,4}<%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))) /u 4)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %gep = getelementptr inbounds i32, ptr %arr, i64 %index -; CHECK-NEXT: --> {%arr,+,16}<%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))) /u 4)) + %arr) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {%arr,+,16}<%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))) /u 4)) + %arr) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %index.next = add nuw i64 %index, 4 -; CHECK-NEXT: --> {4,+,4}<%loop> U: [4,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 + (4 * ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))) /u 4))) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {4,+,4}<%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))) /u 4))) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @rewrite_sext_slt_narrow_check ; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))) /u 4) -; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 4611686018427387903 +; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 3 ; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))) /u 4) ; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))) /u 4) ; CHECK-NEXT: Predicates: @@ -522,14 +522,14 @@ ; CHECK-NEXT: %n.vec = and i64 %ext, 28 ; CHECK-NEXT: --> (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64)) U: [0,29) S: [0,29) ; CHECK-NEXT: %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ] -; CHECK-NEXT: --> {0,+,4}<%loop> U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 * ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))) /u 4)) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {0,+,4}<%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))) /u 4)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %gep = getelementptr inbounds i32, ptr %arr, i64 %index -; CHECK-NEXT: --> {%arr,+,16}<%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))) /u 4)) + %arr) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {%arr,+,16}<%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))) /u 4)) + %arr) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %index.next = add nuw i64 %index, 4 -; CHECK-NEXT: --> {4,+,4}<%loop> U: [4,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 + (4 * ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))) /u 4))) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {4,+,4}<%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))) /u 4))) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext_ult_narrow_check ; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))) /u 4) -; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 4611686018427387903 +; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 3 ; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))) /u 4) ; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))) /u 4) ; CHECK-NEXT: Predicates: @@ -568,14 +568,14 @@ ; CHECK-NEXT: %n.vec = and i64 %ext, 28 ; CHECK-NEXT: --> (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64)) U: [0,29) S: [0,29) ; CHECK-NEXT: %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ] -; CHECK-NEXT: --> {0,+,4}<%loop> U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 * ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))) /u 4)) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {0,+,4}<%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))) /u 4)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %gep = getelementptr inbounds i32, ptr %arr, i64 %index -; CHECK-NEXT: --> {%arr,+,16}<%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))) /u 4)) + %arr) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {%arr,+,16}<%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))) /u 4)) + %arr) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %index.next = add nuw i64 %index, 4 -; CHECK-NEXT: --> {4,+,4}<%loop> U: [4,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 + (4 * ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))) /u 4))) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {4,+,4}<%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))) /u 4))) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext_ule_narrow_check ; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))) /u 4) -; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 4611686018427387903 +; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 3 ; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))) /u 4) ; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))) /u 4) ; CHECK-NEXT: Predicates: @@ -614,14 +614,14 @@ ; CHECK-NEXT: %n.vec = and i64 %ext, 28 ; CHECK-NEXT: --> (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64)) U: [0,29) S: [0,29) ; CHECK-NEXT: %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ] -; CHECK-NEXT: --> {0,+,4}<%loop> U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 * ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))) /u 4)) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {0,+,4}<%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))) /u 4)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %gep = getelementptr inbounds i32, ptr %arr, i64 %index -; CHECK-NEXT: --> {%arr,+,16}<%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))) /u 4)) + %arr) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {%arr,+,16}<%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))) /u 4)) + %arr) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %index.next = add nuw i64 %index, 4 -; CHECK-NEXT: --> {4,+,4}<%loop> U: [4,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 + (4 * ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))) /u 4))) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {4,+,4}<%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))) /u 4))) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext_sle_narrow_check ; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))) /u 4) -; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 4611686018427387903 +; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 3 ; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))) /u 4) ; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))) /u 4) ; CHECK-NEXT: Predicates: @@ -660,14 +660,14 @@ ; CHECK-NEXT: %n.vec = and i64 %ext, 28 ; CHECK-NEXT: --> (4 * ((16 umin (zext i32 %N to i64)) /u 4)) U: [0,17) S: [0,17) ; CHECK-NEXT: %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ] -; CHECK-NEXT: --> {0,+,4}<%loop> U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))) /u 4)) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {0,+,4}<%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))) /u 4)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %gep = getelementptr inbounds i32, ptr %arr, i64 %index -; CHECK-NEXT: --> {%arr,+,16}<%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))) /u 4)) + %arr) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {%arr,+,16}<%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))) /u 4)) + %arr) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %index.next = add nuw i64 %index, 4 -; CHECK-NEXT: --> {4,+,4}<%loop> U: [4,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 + (4 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))) /u 4))) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {4,+,4}<%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))) /u 4))) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext_uge_narrow_check ; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))) /u 4) -; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 4611686018427387903 +; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 3 ; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))) /u 4) ; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))) /u 4) ; CHECK-NEXT: Predicates: @@ -706,14 +706,14 @@ ; CHECK-NEXT: %n.vec = and i64 %ext, 28 ; CHECK-NEXT: --> (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64)) U: [0,29) S: [0,29) ; CHECK-NEXT: %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ] -; CHECK-NEXT: --> {0,+,4}<%loop> U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))) /u 4)) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {0,+,4}<%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))) /u 4)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %gep = getelementptr inbounds i32, ptr %arr, i64 %index -; CHECK-NEXT: --> {%arr,+,16}<%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))) /u 4)) + %arr) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {%arr,+,16}<%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))) /u 4)) + %arr) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %index.next = add nuw i64 %index, 4 -; CHECK-NEXT: --> {4,+,4}<%loop> U: [4,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 + (4 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))) /u 4))) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {4,+,4}<%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))) /u 4))) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @rewrite_sext_sge_narrow_check ; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))) /u 4) -; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 4611686018427387903 +; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 3 ; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))) /u 4) ; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))) /u 4) ; CHECK-NEXT: Predicates: @@ -752,14 +752,14 @@ ; CHECK-NEXT: %n.vec = and i64 %ext, 28 ; CHECK-NEXT: --> (4 * ((16 umin (zext i32 %N to i64)) /u 4)) U: [0,17) S: [0,17) ; CHECK-NEXT: %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ] -; CHECK-NEXT: --> {0,+,4}<%loop> U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))) /u 4)) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {0,+,4}<%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))) /u 4)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %gep = getelementptr inbounds i32, ptr %arr, i64 %index -; CHECK-NEXT: --> {%arr,+,16}<%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))) /u 4)) + %arr) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {%arr,+,16}<%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))) /u 4)) + %arr) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %index.next = add nuw i64 %index, 4 -; CHECK-NEXT: --> {4,+,4}<%loop> U: [4,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 + (4 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))) /u 4))) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {4,+,4}<%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))) /u 4))) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext_ugt_narrow_check ; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))) /u 4) -; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 4611686018427387903 +; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 3 ; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))) /u 4) ; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))) /u 4) ; CHECK-NEXT: Predicates: @@ -798,14 +798,14 @@ ; CHECK-NEXT: %n.vec = and i64 %ext, 28 ; CHECK-NEXT: --> (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64)) U: [0,29) S: [0,29) ; CHECK-NEXT: %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ] -; CHECK-NEXT: --> {0,+,4}<%loop> U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))) /u 4)) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {0,+,4}<%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))) /u 4)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %gep = getelementptr inbounds i32, ptr %arr, i64 %index -; CHECK-NEXT: --> {%arr,+,16}<%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))) /u 4)) + %arr) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {%arr,+,16}<%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))) /u 4)) + %arr) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %index.next = add nuw i64 %index, 4 -; CHECK-NEXT: --> {4,+,4}<%loop> U: [4,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 + (4 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))) /u 4))) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {4,+,4}<%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))) /u 4))) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @rewrite_sext_sgt_narrow_check ; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))) /u 4) -; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 4611686018427387903 +; CHECK-NEXT: Loop %loop: constant max backedge-taken count is 3 ; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))) /u 4) ; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))) /u 4) ; CHECK-NEXT: Predicates: Index: llvm/test/Analysis/ScalarEvolution/trip-count-minmax.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/trip-count-minmax.ll +++ llvm/test/Analysis/ScalarEvolution/trip-count-minmax.ll @@ -156,16 +156,16 @@ ; CHECK-NEXT: %cond = select i1 %cmp, i32 %mul, i32 %mul1 ; CHECK-NEXT: --> ((2 * %a) smin (4 * %b)) U: [0,-1) S: [-2147483648,2147483645) ; CHECK-NEXT: %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ] -; CHECK-NEXT: --> {0,+,1}<%for.body> U: [0,2147483647) S: [0,2147483647) Exits: (-1 + ((2 * %a) smin (4 * %b))) LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: --> {0,+,1}<%for.body> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + ((2 * %a) smin (4 * %b))) LoopDispositions: { %for.body: Computable } ; CHECK-NEXT: %inc = add nuw nsw i32 %i.011, 1 -; CHECK-NEXT: --> {1,+,1}<%for.body> U: [1,-2147483648) S: [1,-2147483648) Exits: ((2 * %a) smin (4 * %b)) LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: --> {1,+,1}<%for.body> U: [1,-1) S: [1,-1) Exits: ((2 * %a) smin (4 * %b)) LoopDispositions: { %for.body: Computable } ; CHECK-NEXT: Determining loop execution counts for: @smin ; CHECK-NEXT: Loop %for.body: backedge-taken count is (-1 + ((2 * %a) smin (4 * %b))) -; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is 2147483646 +; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is -3 ; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (-1 + ((2 * %a) smin (4 * %b))) ; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (-1 + ((2 * %a) smin (4 * %b))) ; CHECK-NEXT: Predicates: -; CHECK: Loop %for.body: Trip multiple is 1 +; CHECK: Loop %for.body: Trip multiple is 2 ; ; void smin(signed a, signed b) { ; a *= 2;