[LLVM] Introduce llvm.loop.finite metadata to represent loops which are known to iterate a finite number of times

[wsmoses]

Summary

Introduce a new loop metadata llvm.loop.finite which specifies that the loop is known to iterate a finite number of times. This is a stronger form of llvm.loop.mustprogress and useful for various analyses, such as scalar evolution (see: https://reviews.llvm.org/D118090)

[lebedev.ri]

Per-loop attributes are easily lost, what about additional function/module -level attribute, similarly to the one for mustprogress?

llvm/docs/LangRef.rst

6879–6880

Or something like that

[wsmoses]

State willreturn function attribute implies loop.finite

[efriedma]

Is this supposed to be "willreturn" for loops?

The following all terminate the loop in some sense:

The current thread calls abort().
Another thread calls abort().
A call in the loop throws an exception.

I guess given the SCEV patch, you want to exclude all of these, but the current wording doesn't make that clear.

[wsmoses]

In D118168#3271370, @efriedma wrote:

Is this supposed to be "willreturn" for loops?

In essence yes.

The following all terminate the loop in some sense:

The current thread calls abort().
Another thread calls abort().
A call in the loop throws an exception.

I'll rework some of the willreturn verbiage into here.

[wsmoses]

Clarify wording on termination condition.

[jdoerfert]

I think this is generally sensible but lacks tests and a clear path towards usage. Who will produce the annotation?

llvm/include/llvm/Analysis/LoopInfo.h

1345

Why do we need both, esp. given the Note?

llvm/lib/Analysis/LoopInfo.cpp

1126

While it seems to be the state-of-the-art to duplicate the string all over the place, could we please start a new scheme in which we have this definition early in the file and used whenever we need the string. Feel free to update the other ones as well.

[wsmoses]

In D118168#3277051, @jdoerfert wrote:

I think this is generally sensible but lacks tests and a clear path towards usage. Who will produce the annotation?

I think there are several target producers. For example, in here (https://github.com/llvm/llvm-project/issues/51103) an OpenMP for loop can produce it.

llvm/include/llvm/Analysis/LoopInfo.h

1345

For consistency with hasMustProgress? Happy to remove it if undesired.

llvm/lib/Analysis/LoopInfo.cpp

1126

I concur, though I might prefer to split off the string restructuring from the langref change?

[jdoerfert]

In D118168#3277126, @wsmoses wrote:

In D118168#3277051, @jdoerfert wrote:

I think this is generally sensible but lacks tests and a clear path towards usage. Who will produce the annotation?

I think there are several target producers. For example, in here (https://github.com/llvm/llvm-project/issues/51103) an OpenMP for loop can produce it.

Can produce it, maybe yes. Now we should also have that setup or at least planned as we otherwise have no test coverage (esp. given the lack of tests).

llvm/include/llvm/Analysis/LoopInfo.h

1345

Interestingly you split the two is/hasMP in the middle with this. On purpose?
The split for MP is an optimization of sorts, certainly not worth repeating if we are not using it right away.

llvm/lib/Analysis/LoopInfo.cpp

1126

Works for me, string stuff I can review quickly

[reames]

The basic idea of this makes sense to me. I will leave it to other reviewers to help shape the patch into something ready to land due to a lack of near term availability on my part. Mostly want to be explicit about not being a blocker on this.

[lebedev.ri]

In D118168#3277166, @jdoerfert wrote:

In D118168#3277126, @wsmoses wrote:

In D118168#3277051, @jdoerfert wrote:

I think this is generally sensible but lacks tests and a clear path towards usage. Who will produce the annotation?

I think there are several target producers. For example, in here (https://github.com/llvm/llvm-project/issues/51103) an OpenMP for loop can produce it.

Can produce it, maybe yes. Now we should also have that setup or at least planned as we otherwise have no test coverage (esp. given the lack of tests).

Hm, now that i actually did read the spec, no, this absolutely will not help that issue, or any of OpenMP sugar:
https://www.openmp.org/wp-content/uploads/OpenMP-API-Specification-5-2.pdf

12 4.3 Structured Blocks
13 This section specifies the concept of a structured block. A structured block:
14 • may contain infinite loops where the point of exit is never reached;

So helper functions that are used to outline the OpenMP structured block can not be mustprogress/willreturn/loop.finite.

[wsmoses]

So helper functions that are used to outline the OpenMP structured block can not be mustprogress/willreturn/loop.finite.

Today I learned. In any case a more obvious use case is when inlining the body of a willreturn function into a function which is not willreturn, one can mark any inlined loops as finite (preserving the information).

[lebedev.ri]

In D118168#3280138, @wsmoses wrote:

So helper functions that are used to outline the OpenMP structured block can not be mustprogress/willreturn/loop.finite.

Today I learned. In any case a more obvious use case is when inlining the body of a willreturn function into a function which is not willreturn, one can mark any inlined loops as finite (preserving the information).

Yes. Plus there are always other front-ends.

[wsmoses]

Rebase and add test

[lebedev.ri]

llvm/docs/LangRef.rst

6876–6877

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

256

Is this test missing the actual CHECK line?

[nlopes]

Let me come back the usefulness question: which frontend can mark loops as finite but can't mark functions as willreturn?

[lebedev.ri]

In D118168#3362338, @nlopes wrote:

Let me come back the usefulness question: which frontend can mark loops as finite but can't mark functions as willreturn?

I would imagine this will come up when inlining willreturn function into a non-willreturn one.

[jdoerfert]

In D118168#3362338, @nlopes wrote:

Let me come back the usefulness question: which frontend can mark loops as finite but can't mark functions as willreturn?

It's not only frontends, assuming we want to avoid reanalizing a loop.

[reames]

This is close to an LGTM. I was originally going to give a contingent LGTM, but then realized that prior comments have not yet been fully addressed. If you refresh with the requested changes, I will LGTM.

llvm/docs/LangRef.rst

6884

This last sentence is important, and I'd really like to see the dual stated explicitly as well. Something along the lines of "A function which contains a collection of loops marked finite and no other cycles or function calls must be willreturn."

I really want the definition here tightly coupled to willreturn. Allowing divergence in the definition seems like a really bad idea, and I want that said really explicitly in the LangRef.

llvm/lib/Analysis/LoopInfo.cpp

567

This function appears to be unused in the patch. Please removed.

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

256

This comment appears to have not been addressed.

[lebedev.ri]

This review may be stuck/dead, consider abandoning if no longer relevant.
Removing myself as reviewer in attempt to clean dashboard.

llvm/docs/LangRef.rst

 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 The ``llvm.loop.mustprogress`` metadata indicates that this loop is required to
 terminate, unwind, or interact with the environment in an observable way e.g.
 via a volatile memory access, I/O, or other synchronization. If such a loop is
 not found to interact with the environment in an observable way, the loop may
 be removed. This corresponds to the ``mustprogress`` function attribute.
 
+'``llvm.loop.finite``' Metadata
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+The ``llvm.loop.finite`` metadata indicates that this loop is finite. The loop,
+to which this attribute is attached, must terminate and continue exection at some
+instruction outside this loop. The reason for termination is unspecified and may
+come from an exception (i.a, nounwind is not implied). This is a stronger form
+of ``llvm.loop.mustprogress`` which simply says that the loop either may terminate,
+unwind or interact with the environment. All loops within a function marked with
+the attribute ``willreturn`` are finite by definition.
+
 '``irr_loop``' Metadata
 ^^^^^^^^^^^^^^^^^^^^^^^
 
 ``irr_loop`` metadata may be attached to the terminator instruction of a basic
 block that's an irreducible loop header (note that an irreducible loop has more
 than once header basic blocks.) If ``irr_loop`` metadata is attached to the
 terminator instruction of a basic block that is not really an irreducible loop
 header, the behavior is undefined. The intent of this metadata is to improve the

llvm/include/llvm/Analysis/LoopInfo.h

public:
   /// indicate the loop has already been unrolled.  This prevents a loop
   /// from being unrolled more than is directed by a pragma if the loop
   /// unrolling pass is run more than once (which it generally is).
   void setLoopAlreadyUnrolled();
 
   /// Add llvm.loop.mustprogress to this loop's loop id metadata.
   void setLoopMustProgress();
 
+  /// Add llvm.loop.finite to this loop's loop id metadata.
+  void setLoopFinite();
+
   void dump() const;
   void dumpVerbose() const;
 
   /// Return the debug location of the start of this loop.
   /// This looks for a BB terminating instruction with a known debug
   /// location by looking at the preheader and header blocks. If it
   /// cannot find a terminating instruction with location information,
   /// it returns an unknown location.

 Optional<const MDOperand *> findStringMetadataForLoop(const Loop *TheLoop,
                                                       StringRef Name);
 
 /// Look for the loop attribute that requires progress within the loop.
 /// Note: Most consumers probably want "isMustProgress" which checks
 /// the containing function attribute too.
 bool hasMustProgress(const Loop *L);
 
+/// Look for the loop attribute that requires the loop to be finite.
+/// Note: Most consumers probably want "isFinite" which checks
+/// the containing function attribute `willreturn` too.
+bool hasFinite(const Loop *L);
+
+/// Look for the loop attribute that requires the loop to be finite.
+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);
 
 /// Return true if this loop can be assumed to run for a finite number of
 /// iterations.
 bool isFinite(const Loop *L);
 

llvm/lib/Analysis/LoopInfo.cpp

void Loop::setLoopMustProgress() {
   MDNode *MustProgressMD =
       MDNode::get(Context, MDString::get(Context, "llvm.loop.mustprogress"));
   MDNode *LoopID = getLoopID();
   MDNode *NewLoopID =
       makePostTransformationMetadata(Context, LoopID, {}, {MustProgressMD});
   setLoopID(NewLoopID);
 }
 
+void Loop::setLoopFinite() {
+  LLVMContext &Context = getHeader()->getContext();
+
+  MDNode *Finite = findOptionMDForLoop(this, "llvm.loop.finite");
+
+  if (Finite)
+    return;
+
+  MDNode *FiniteMD =
+      MDNode::get(Context, MDString::get(Context, "llvm.loop.finite"));
+  MDNode *LoopID = getLoopID();
+  MDNode *NewLoopID =
+      makePostTransformationMetadata(Context, LoopID, {}, {FiniteMD});
+  setLoopID(NewLoopID);
+}
+
 bool Loop::isAnnotatedParallel() const {
   MDNode *DesiredLoopIdMetadata = getLoopID();
 
   if (!DesiredLoopIdMetadata)
     return false;
 
   MDNode *ParallelAccesses =
       findOptionMDForLoop(this, "llvm.loop.parallel_accesses");
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);
 }
 
+static const char *LLVMLoopFinite = "llvm.loop.finite";
+
+bool llvm::hasFinite(const Loop *L) {
+  return getBooleanLoopAttribute(L, LLVMLoopFinite);
+}
+
 bool llvm::isFinite(const Loop *L) {
-  return L->getHeader()->getParent()->willReturn();
+  return L->getHeader()->getParent()->willReturn() || hasFinite(L);
 }
 
 static const char *LLVMLoopMustProgress = "llvm.loop.mustprogress";
 
 bool llvm::hasMustProgress(const Loop *L) {
   return getBooleanLoopAttribute(L, LLVMLoopMustProgress);
 }
 

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

for.body:
   %iv.next = add i32 %iv, 1024
   call void @sideeffect() nounwind
   %cmp = icmp ult i32 %iv.next, %N
   br i1 %cmp, label %for.body, label %for.cond.cleanup
 
 for.cond.cleanup:
   ret void
 }
+
+define void @test_finite(i32 %S, i32 %N) {
+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, !llvm.loop !8
+
+for.cond.cleanup:
+  ret void
+}
+
+!8 = distinct !{!8, !9}
+!9 = !{!"llvm.loop.finite"}