diff --git a/llvm/include/llvm/Analysis/LoopInfo.h b/llvm/include/llvm/Analysis/LoopInfo.h
--- a/llvm/include/llvm/Analysis/LoopInfo.h
+++ b/llvm/include/llvm/Analysis/LoopInfo.h
@@ -1332,6 +1332,10 @@
/// the containing function attribute too.
bool hasMustProgress(const Loop *L);
+/// Return true if this loop can be assumed to run for a finite number of
+/// iterations.
+bool isFinite(const Loop *L);
+
/// Return true if this loop can be assumed to make progress. (i.e. can't
/// be infinite without side effects without also being undefined)
bool isMustProgress(const Loop *L);
diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h
--- a/llvm/include/llvm/Analysis/ScalarEvolution.h
+++ b/llvm/include/llvm/Analysis/ScalarEvolution.h
@@ -1111,9 +1111,11 @@
/// Simplify LHS and RHS in a comparison with predicate Pred. Return true
/// iff any changes were made. If the operands are provably equal or
/// unequal, LHS and RHS are set to the same value and Pred is set to either
- /// ICMP_EQ or ICMP_NE.
+ /// ICMP_EQ or ICMP_NE. ControllingFiniteLoop is set if this comparison
+ /// controls the exit of a loop known to have a finite number of iterations.
bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS,
- const SCEV *&RHS, unsigned Depth = 0);
+ const SCEV *&RHS, unsigned Depth = 0,
+ bool ControlingFiniteLoop = false);
/// Return the "disposition" of the given SCEV with respect to the given
/// loop.
diff --git a/llvm/lib/Analysis/LoopInfo.cpp b/llvm/lib/Analysis/LoopInfo.cpp
--- a/llvm/lib/Analysis/LoopInfo.cpp
+++ b/llvm/lib/Analysis/LoopInfo.cpp
@@ -1107,6 +1107,10 @@
return getOptionalIntLoopAttribute(TheLoop, Name).getValueOr(Default);
}
+bool llvm::isFinite(const Loop *L) {
+ return L->getHeader()->getParent()->willReturn();
+}
+
static const char *LLVMLoopMustProgress = "llvm.loop.mustprogress";
bool llvm::hasMustProgress(const Loop *L) {
@@ -1114,7 +1118,8 @@
}
bool llvm::isMustProgress(const Loop *L) {
- return L->getHeader()->getParent()->mustProgress() || hasMustProgress(L);
+ return L->getHeader()->getParent()->mustProgress() || hasMustProgress(L) ||
+ isFinite(L);
}
bool llvm::isValidAsAccessGroup(MDNode *Node) {
diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -7017,7 +7017,7 @@
// A mustprogress loop without side effects must be finite.
// TODO: The check used here is very conservative. It's only *specific*
// side effects which are well defined in infinite loops.
- return isMustProgress(L) && loopHasNoSideEffects(L);
+ return isFinite(L) || (isMustProgress(L) && loopHasNoSideEffects(L));
}
const SCEV *ScalarEvolution::createSCEV(Value *V) {
@@ -8472,7 +8472,10 @@
}
// Simplify the operands before analyzing them.
- (void)SimplifyICmpOperands(Pred, LHS, RHS);
+ (void)SimplifyICmpOperands(Pred, LHS, RHS, /*Depth=*/0,
+ /*ControllingFiniteLoop=*/ControlsExit &&
+ loopHasNoAbnormalExits(L) &&
+ loopIsFiniteByAssumption(L));
// If we have a comparison of a chrec against a constant, try to use value
// ranges to answer this query.
@@ -9945,7 +9948,8 @@
bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred,
const SCEV *&LHS, const SCEV *&RHS,
- unsigned Depth) {
+ unsigned Depth,
+ bool ControllingFiniteLoop) {
bool Changed = false;
// Simplifies ICMP to trivial true or false by turning it into '0 == 0' or
// '0 != 0'.
@@ -10074,10 +10078,16 @@
}
// If possible, canonicalize GE/LE comparisons to GT/LT comparisons, by
- // adding or subtracting 1 from one of the operands.
+ // adding or subtracting 1 from one of the operands. This can be done for
+ // one of two reasons:
+ // 1) The range of the RHS does not include the (signed/unsigned) boundaries
+ // 2) The loop is finite, with this comparison controling the exit. Since the
+ // loop
+ // is finite, the bound cannot include the corresponding boundary
+ // (otherwise it would loop forever).
switch (Pred) {
case ICmpInst::ICMP_SLE:
- if (!getSignedRangeMax(RHS).isMaxSignedValue()) {
+ if (!getSignedRangeMax(RHS).isMaxSignedValue() || ControllingFiniteLoop) {
RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS,
SCEV::FlagNSW);
Pred = ICmpInst::ICMP_SLT;
@@ -10090,7 +10100,7 @@
}
break;
case ICmpInst::ICMP_SGE:
- if (!getSignedRangeMin(RHS).isMinSignedValue()) {
+ if (!getSignedRangeMin(RHS).isMinSignedValue() || ControllingFiniteLoop) {
RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS,
SCEV::FlagNSW);
Pred = ICmpInst::ICMP_SGT;
@@ -10103,7 +10113,7 @@
}
break;
case ICmpInst::ICMP_ULE:
- if (!getUnsignedRangeMax(RHS).isMaxValue()) {
+ if (!getUnsignedRangeMax(RHS).isMaxValue() || ControllingFiniteLoop) {
RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS,
SCEV::FlagNUW);
Pred = ICmpInst::ICMP_ULT;
@@ -10115,7 +10125,7 @@
}
break;
case ICmpInst::ICMP_UGE:
- if (!getUnsignedRangeMin(RHS).isMinValue()) {
+ if (!getUnsignedRangeMin(RHS).isMinValue() || ControllingFiniteLoop) {
RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS);
Pred = ICmpInst::ICMP_UGT;
Changed = true;
@@ -10135,7 +10145,8 @@
// Recursively simplify until we either hit a recursion limit or nothing
// changes.
if (Changed)
- return SimplifyICmpOperands(Pred, LHS, RHS, Depth+1);
+ return SimplifyICmpOperands(Pred, LHS, RHS, Depth + 1,
+ ControllingFiniteLoop);
return Changed;
}
diff --git a/llvm/test/Analysis/ScalarEvolution/finite-trip-count.ll b/llvm/test/Analysis/ScalarEvolution/finite-trip-count.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Analysis/ScalarEvolution/finite-trip-count.ll
@@ -0,0 +1,98 @@
+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
+; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" -scalar-evolution-max-iterations=0 -scalar-evolution-classify-expressions=0 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @non_exit_use(i32 %i) #0
+
+define void @SLE(i32 %len) #1 {
+; CHECK-LABEL: 'SLE'
+; CHECK-NEXT: Determining loop execution counts for: @SLE
+; CHECK-NEXT: Loop %for.body: backedge-taken count is (0 smax (1 + %len)<nsw>)
+; CHECK-NEXT: Loop %for.body: max backedge-taken count is 2147483647
+; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (0 smax (1 + %len)<nsw>)
+; CHECK-NEXT: Predicates:
+;
+entry:
+ br label %for.body
+
+for.body:
+ %iv = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+ call void @non_exit_use(i32 %iv)
+ %inc = add i32 %iv, 1
+ %cmp = icmp sle i32 %iv, %len
+ br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+ ret void
+}
+
+define void @ULE(i32 %len) #1 {
+; CHECK-LABEL: 'ULE'
+; CHECK-NEXT: Determining loop execution counts for: @ULE
+; CHECK-NEXT: Loop %for.body: backedge-taken count is (1 + %len)<nuw>
+; CHECK-NEXT: Loop %for.body: max backedge-taken count is -1
+; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (1 + %len)<nuw>
+; CHECK-NEXT: Predicates:
+;
+entry:
+ br label %for.body
+
+for.body:
+ %iv = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+ call void @non_exit_use(i32 %iv)
+ %inc = add i32 %iv, 1
+ %cmp = icmp ule i32 %iv, %len
+ br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+ ret void
+}
+
+define void @SGE(i32 %len) #1 {
+; CHECK-LABEL: 'SGE'
+; CHECK-NEXT: Determining loop execution counts for: @SGE
+; CHECK-NEXT: Loop %for.body: backedge-taken count is ((-1 * (0 smin %len)) + %len)
+; CHECK-NEXT: Loop %for.body: max backedge-taken count is 2147483647
+; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is ((-1 * (0 smin %len)) + %len)
+; CHECK-NEXT: Predicates:
+;
+entry:
+ br label %for.body
+
+for.body:
+ %iv = phi i32 [ %inc, %for.body ], [ %len, %entry ]
+ call void @non_exit_use(i32 %iv)
+ %inc = add i32 %iv, -1
+ %cmp = icmp sge i32 %iv, 1
+ br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+ ret void
+}
+
+define void @UGE(i32 %len) #1 {
+; CHECK-LABEL: 'UGE'
+; CHECK-NEXT: Determining loop execution counts for: @UGE
+; CHECK-NEXT: Loop %for.body: backedge-taken count is %len
+; CHECK-NEXT: Loop %for.body: max backedge-taken count is -1
+; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is %len
+; CHECK-NEXT: Predicates:
+;
+entry:
+ br label %for.body
+
+for.body:
+ %iv = phi i32 [ %inc, %for.body ], [ %len, %entry ]
+ call void @non_exit_use(i32 %iv)
+ %inc = add i32 %iv, -1
+ %cmp = icmp uge i32 %iv, 1
+ br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+ ret void
+}
+
+attributes #0 = { nounwind willreturn }
+attributes #1 = { willreturn }