[ScalarEvolution] Mark a loop as finite if in a willreturn function

[wsmoses]

Summary

A limited version of (https://reviews.llvm.org/D118090) that only marks a loop as finite if in a willreturn function.

[nikic]

Can you please add a test for this? Taking an existing mustprogress test and adding a possibly side-effecting call should serve as a demonstration. Otherwise this looks fine to me.

[wsmoses]

Add test

[jdoerfert]

Assuming the second test can be added, see below, LG.

llvm/test/Analysis/ScalarEvolution/lt-overflow.ll

219

This should also work w/o the call site attributes, correct?
If so add a second test.

[jdoerfert]

llvm/test/Analysis/ScalarEvolution/lt-overflow.ll

219

If it doesn't work w/o, can u add negative tests with a FIXME.
Call site should inherit willreturn and one test with the outer function marked as willreturn and nounwind so the call site could inherit both.

[wsmoses]

Add tests

llvm/include/llvm/Analysis/LoopInfo.h

 /// Note: Most consumers probably want "isMustProgress" which checks
 /// the containing function attribute too.
 bool hasMustProgress(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);
 
+/// Return true if this loop can be assumed to run for a finite number of
+/// iterations.
+bool isFinite(const Loop *L);
+
 /// Return whether an MDNode might represent an access group.
 ///
 /// Access group metadata nodes have to be distinct and empty. Being
 /// always-empty ensures that it never needs to be changed (which -- because
 /// MDNodes are designed immutable -- would require creating a new MDNode). Note
 /// that this is not a sufficient condition: not every distinct and empty NDNode
 /// is representing an access group.
 bool isValidAsAccessGroup(MDNode *AccGroup);

llvm/lib/Analysis/LoopInfo.cpp

llvm::Optional<int> llvm::getOptionalIntLoopAttribute(const Loop *TheLoop,
   return IntMD->getSExtValue();
 }
 
 int llvm::getIntLoopAttribute(const Loop *TheLoop, StringRef Name,
                               int Default) {
   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) {
   return getBooleanLoopAttribute(L, LLVMLoopMustProgress);
 }
 
 bool llvm::isMustProgress(const Loop *L) {
   return L->getHeader()->getParent()->mustProgress() || hasMustProgress(L);

llvm/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::getLoopProperties(const Loop *L) {
 
   return Itr->second;
 }
 
 bool ScalarEvolution::loopIsFiniteByAssumption(const Loop *L) {
   // 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) {
   if (!isSCEVable(V->getType()))
     return getUnknown(V);
 
   if (Instruction *I = dyn_cast<Instruction>(V)) {
     // Don't attempt to analyze instructions in blocks that aren't

llvm/test/Analysis/ScalarEvolution/lt-overflow.ll

 ; CHECK: Determining loop execution counts for: @test_non_invariant_rhs
 ; CHECK: Loop %for.body: Unpredictable backedge-taken count.
 ; CHECK: Determining loop execution counts for: @test_abnormal_exit
 ; CHECK: Loop %for.body: Unpredictable backedge-taken count.
 ; CHECK: Determining loop execution counts for: @test_other_exit
 ; CHECK: Loop %for.body: <multiple exits> Unpredictable backedge-taken count.
 ; CHECK: Determining loop execution counts for: @test_gt
 ; CHECK: Loop %for.body: Unpredictable backedge-taken count.
+; CHECK: Determining loop execution counts for: @test_willreturn
+; CHECK: Loop %for.body: backedge-taken count is ((-1 + (1024 umax %N)) /u 1024)
 
 define void @test(i32 %N) mustprogress {
 entry:
   br label %for.body
 
 for.body:
   %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
   %iv.next = add i32 %iv, 2
for.body:
   %iv = phi i32 [ %iv.next, %for.body ], [ %S, %entry ]
   %iv.next = add i32 %iv, -2
   %cmp = icmp ugt i32 %iv.next, %N
   br i1 %cmp, label %for.body, label %for.cond.cleanup
 
 for.cond.cleanup:
   ret void
 }
+
+declare void @sideeffect()
+
+define void @test_willreturn(i32 %S, i32 %N) willreturn {
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
+  %iv.next = add i32 %iv, 1024
+  call void @sideeffect() nounwind willreturn
+  %cmp = icmp ult i32 %iv.next, %N
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:
+  ret void
+}