Page MenuHomePhabricator

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

Authored by wsmoses on Jan 25 2022, 11:07 AM.

Details

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)

Diff Detail

Event Timeline

wsmoses created this revision.Jan 25 2022, 11:07 AM
wsmoses requested review of this revision.Jan 25 2022, 11:07 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 25 2022, 11:07 AM

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 updated this revision to Diff 403048.Jan 25 2022, 3:00 PM

State willreturn function attribute implies loop.finite

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.

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 updated this revision to Diff 403126.Jan 25 2022, 8:41 PM

Clarify wording on termination condition.

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.

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?

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

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.

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.

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).

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 updated this revision to Diff 404110.Jan 28 2022, 11:29 AM

Rebase and add test

lebedev.ri added inline comments.Mar 5 2022, 12:30 PM
llvm/docs/LangRef.rst
6876–6877
llvm/test/Analysis/ScalarEvolution/lt-overflow.ll
256

Is this test missing the actual CHECK line?

Herald added a project: Restricted Project. · View Herald TranscriptMar 5 2022, 12:30 PM
nlopes added a comment.Mar 6 2022, 4:32 AM

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

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.

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 requested changes to this revision.Mar 7 2022, 9:11 AM

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.

This revision now requires changes to proceed.Mar 7 2022, 9:11 AM