[llvm-dev] [RFC] Introducing the maynotprogress IR attribute

Mon Sep 7 12:52:08 PDT 2020

Hi Johannes,

On Mon, Sep 7, 2020 at 6:51 PM Johannes Doerfert
<johannesdoerfert at gmail.com> wrote:
> On 9/7/20 10:56 AM, Nicolai Hähnle wrote:
>  > Hi Johannes and Atmn,
>  >
>  > On Sat, Sep 5, 2020 at 7:07 AM Johannes Doerfert via llvm-dev
>  > <llvm-dev at lists.llvm.org> wrote:
>  >>  > In any case, please explain the intended behavior of the
> attribute and
>  >>  > the metadata upon inlining.
>  >>
>  >> The attribute will be attached to the caller upon inlining as this is
>  >> the only way to keep semantics correct. Metadata can be added to the
>  >> loops of the caller if the caller did not have the attribute, but that
>  >> is an optimization and not required. The patch for the first part will
>  >> be part of this change set.
>  >
>  > I don't understand why this would be correct, unless you meant this
>  > statement to only refer to loops in the caller that contain the
>  > inlined call.
>
> I'm not sure I interpret "loops in the caller that contain the inlined
> call" correctly but let me give it a try.
>
> So this is the first inliner patch: https://reviews.llvm.org/D87180
> It is alone sufficient for correctness of this scheme. A follow up can
> provide better optimization opportunities by using metadata to annotate
> loops in the caller, assuming the caller did not have the
> `maynotprogress` function attribute already. All loops originally in the
> caller would be given the loop metadata that indicates the new
> `maynotprogress` inherited from the callee does not apply to them. If
> the metadata is lost for some reason, we do not loose correctness.

Okay, thank you for that first explanation. It does feel like there's
some redundancy there, though. Why weren't all those loops annotated
with metadata in the first place?

>  > I'm afraid I don't have the full history of these discussions, but is
>  > there really a _good_ reason for doing so? It would feel more natural
>  > to have no progress requirement by default and add a "willprogress"
>  > attribute to indicate that the so annotated function will eventually
>  > make progress (whatever that means, which is the other issue I have
>  > with this :))
>
> We can certainly turn everything around. Though, that would basically
> regress our current IR and the "normal" C/C++ case (which is forward
> progress requirement). So if people feel we want to make the IR more
> restrictive than it is arguably right now, with an opt-in way to get the
> current semantics back, I won't oppose that. However, all conversations
> up to this point seemed to indicate that we do not want this. Please see
> [1] and [5].

Those discussions are fairly long and I didn't see a concrete argument
against changing the default in them. I may have just missed it, but I
also wonder if it's one of those cases where people in the LLVM
community are too timid, leading us to muddle through with suboptimal
designs.

If changing the default allows us to get away without a new attribute
and redundant representations of semantics, then that's an overall
simpler design in the long run, which should weigh _very_ heavily IMO.

That said, [5] mentions the problem of recursion, which suggests that
perhaps even with a changed default, a solution purely based on
metadata _wouldn't_ be enough? Obviously you could put metadata on
function calls, but that's not usually how we do that kind of thing.
So even with the changed default, it seems like a "willprogress"
attribute might be required? It's admittedly not clear to me.

There is still the argument that it's annoying to have attributes that
_forbid_ program transforms, when virtually all attributes _allow_
program transforms instead. The only other example I can think of
right now is "convergent".

>  > Assuming the simple flip of polarity from the previous paragraph, what
>  > is the difference between the existing "willreturn" and the proposed
>  > "willprogress"? Furthermore, if there is a difference, why is it
>  > relevant to the compiler?
>
> I mean there is plenty of cases where you have one but not the other:
> ```
> while (1) {
>    atomic_add(X, 1);
> }
> ```
> does make progress but will not return. More importantly, willreturn is
> a property we derive, willprogress is a property of the input language
> embedded in the IR. We can use the latter to derive the former, sure,
> but only one of them is rooted in (high-level) language semantics.

"willreturn" could be stated in the source language.

> We want `willreturn` to improve
> isGuaranteedToTransferExecutionToSuccessor (or something like that)
> which then has various uses.
[snip]

Yes, the question was really more about what a "willprogress" buys us.
(Other than as a function-wide default for loop metadata which could
get lost, I suppose -- but we've been going away from function-wide
defaults for a while, e.g. fast math flags, not to mention that
redundant encodings of semantics are generally a bad thing.)

Perhaps something about recursion, as mentioned above? That's not clear to me.

>  > As a separate comment, I don't find the reference to the C++ spec in
>  > https://reviews.llvm.org/D86233 to be informative enough. Whenever
>  > that section of the C++ spec talks about "progress" it is referring to
>  > how some abstract scheduler schedules execution of multiple threads.
>  > That is, it is talking about the dynamic behavior of the
>  > implementation. On the other hand, the proposed attribute presumably
>  > makes a statement about the program itself _assuming that_ its
>  > execution gets scheduled. So there is no applicable definition of
>  > "progress" in the cited section of the C++ spec.
>
> I don't understand. What is the alternative to "assuming that its
> execution gets scheduled"?

The alternative is dealing with the possibility that execution of a
thread is _not_ scheduled by the abstract machine :)

This is a serious topic on GPUs, where you may have no or very weak
forward progress guarantees, e.g. because threads mapped to the same
vector/wave might not make progress while the vector is executing some
other divergent part of the CFG, or because more threads are requested
than physically fit on the machine.

Cheers,
Nicolai

>
> ~ Johannes
>
>
>  > Cheers,
>  > Nicolai
>  >
>  >
>  >>  >> [1] https://bugs.llvm.org/show_bug.cgi?id=965
>  >>  >> [2] https://lists.llvm.org/pipermail/llvm-dev/2015-July/088103.html
>  >>  >> [3]
> https://lists.llvm.org/pipermail/llvm-dev/2017-October/118558.html
>  >>  >> [4] https://reviews.llvm.org/D38336
>  >>  >> [5] https://reviews.llvm.org/D65718
>  >>  >> [6] https://eel.is/c++draft/intro.progress
>  >
>  >
>  >
>

-- 
Lerne, wie die Welt wirklich ist,
aber vergiss niemals, wie sie sein sollte.