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

Mon Sep 7 09:49:22 PDT 2020

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.

 > A deeper issue I have with the proposal is that I'm concerned about
 > adding more attributes which add constraints on program transforms.

Let me start with something that seems to get lost:
We miscompile C/C++ programs right now and we do not apply
transformations to hide the issue one level.

That is,
```C
while(1);
```
is *not* deleted by LoopDeletion right now, which is correct.

Though,
```C
int b = a + 1;
while(b > a);
```
is *not* deleted by LoopDeletion either, which is not necessary and a
side effect of our existing failure to distinguish the two.

Finally,
```
void foo() { while (1); }
void bar() { foo(); }
```
can be optimized by us to `void bar() {}` which is *incorrect*.

So, to summarize, we are in a situation in which we constraint program
transformations, perform wrong program transformations, and require
languages like Rust to add spurious side-effects to avoid this.

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

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

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

Take
```
foo();
*ptr = 0;
```
If we know `foo` is `willreturn` and `nounwind` we know `ptr` is
`derefereceable` prior to the call (on most targets). This allows to
hoist/sink code, improves alias analysis, ... On the other end, with
https://reviews.llvm.org/rGb22910daab95 we can remove more dead code
based on `willreturn` (and `nounwind`).

 > Assuming the simple flip of polarity, is a new attribute needed at
 > all? It seems like the "mustprogress" loop metadata would be
 > sufficient.

I think that is correct. Though, then we are back the regressing all
existing IR. I'm not opposing this choice but it seems to me of little
gain.

To put the regression into perspective: We would basically need to stop
removing an unused `readonly` + `nounwind` call as it could loop
indefinitely and that would be well defined. In the proposed scheme you
would not remove them if they carry the `maynotprogress` attribute, and
you can drop the `maynotprogress` attribute once you proven it will make
progress, e.g., once you proven `willreturn`.

 > 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"?

~ 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
 >
 >
 >