[RFC] Introducing the maynotprogress IR attribute

Hi All,

We’ve prepared a new function attribute `maynotprogress` and loop
metadata `llvm.loop.mustprogress` in order to better formalize the way
LLVM deals with infinite loops without observable side-effects. This
is deeply related to the implicit forward progress requirements in the
IR.

Background:
There has been a demonstrated need for clarity within the forward
progress requirements in LLVM IR. This discussion started with the
longstanding bug [1], followed by subsequent discussion in [2,3].
TL;DR is that LLVM IR needed a clear way to deal with the fact that
C/C++ deems certain infinite side-effect free loops as UB while other
loops, and other languages, have well defined infinite side-effect
free loops.

The proposed mechanism was to add an intrinsic: `llvm.sideeffect()`
that should be inserted by the frontend into loops to indicate that
this loop should be treated as having side-effects, and should not be
optimized out. This was implemented in [4], and long story short, it’s
been an imperfect solution for other language frontends in various
ways. Even C/C++ has loops with and loops without this requirement,
though we could not distinguish so far.

In addition, there has been ambiguity regarding the forward-progress
requirements in IR, as pointed out in [5].

The introduction of the `maynotprogress` IR function attribute and the
`llvm.loop.mustprogress` loop metadata tries to resolve this
situation. The changes proposed are:
- Document that IR Functions are by default expected to make
forward-progress (as defined in the C++ Spec [6]).
- Implement a `maynotprogress` IR function attribute (not droppable)
to indicate that this function is exempt from the above requirement.
This will allow frontends to disable IR optimizations that would
otherwise optimize away their infinite loops without side-effects.
- Implement `llvm.loop.mustprogress` as a loop metadata to notify to
the LLVM optimization passes such as LoopDeletion that even if this
function is permitted to not make progress, this loop is still
required to make progress because it is not one of the infinite
side-effect free loops permitted by the frontend language specs. Note
that loop metadata can be dropped, so even if this metadata is
dropped, we would not optimize away loops that we don’t optimize now
and we wouldn’t preserve loops that we don’t preserve now.

The current implementations are in:
- Changes to the LoopDeletion Pass: https://reviews.llvm.org/D86844
- Changes to the Clang Frontend: https://reviews.llvm.org/D86841
- Changes to LangRef: https://reviews.llvm.org/D86233
- Changed to IR: https://reviews.llvm.org/D85393

The changes preserve what was previously accepted as the “default
behavior” [5]. That is, you get forward progress assumption in case a
function is not marked with the `maynotprogress` attribute. Here the
default behavior is that LLVM IR functions are required to make
forward-progress and are assumed to make forward progress. These
attributes are aimed at helping frontends write correct code as per
their language specs, and in addition, optimize out some dead loops
that we weren’t able to optimize out before but could’ve.

Feedback welcome.

(The name of the function attribute and the loop metadata are still
under discussion, and we’re definitely open to changing them.)

Atmn and Johannes

[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

Hi All,

We’ve prepared a new function attribute `maynotprogress` and loop
metadata `llvm.loop.mustprogress` in order to better formalize the way
LLVM deals with infinite loops without observable side-effects. This
is deeply related to the implicit forward progress requirements in the
IR.

Background:
There has been a demonstrated need for clarity within the forward
progress requirements in LLVM IR. This discussion started with the
longstanding bug [1], followed by subsequent discussion in [2,3].
TL;DR is that LLVM IR needed a clear way to deal with the fact that
C/C++ deems certain infinite side-effect free loops as UB while other
loops, and other languages, have well defined infinite side-effect
free loops.

The proposed mechanism was to add an intrinsic: `llvm.sideeffect()`
that should be inserted by the frontend into loops to indicate that
this loop should be treated as having side-effects, and should not be
optimized out. This was implemented in [4], and long story short, it’s
been an imperfect solution for other language frontends in various
ways.

Can you make the long story not quite so short? What kinds of problems have cropped up with this solution?

  Even C/C++ has loops with and loops without this requirement,
though we could not distinguish so far.

What kinds of loop could we not distinguish? Can you please provide an example?

In addition, there has been ambiguity regarding the forward-progress
requirements in IR, as pointed out in [5].

The introduction of the `maynotprogress` IR function attribute and the
`llvm.loop.mustprogress` loop metadata tries to resolve this
situation. The changes proposed are:
- Document that IR Functions are by default expected to make
forward-progress (as defined in the C++ Spec [6]).
- Implement a `maynotprogress` IR function attribute (not droppable)
to indicate that this function is exempt from the above requirement.
This will allow frontends to disable IR optimizations that would
otherwise optimize away their infinite loops without side-effects.
- Implement `llvm.loop.mustprogress` as a loop metadata to notify to
the LLVM optimization passes such as LoopDeletion that even if this
function is permitted to not make progress, this loop is still
required to make progress because it is not one of the infinite
side-effect free loops permitted by the frontend language specs. Note
that loop metadata can be dropped, so even if this metadata is
dropped, we would not optimize away loops that we don’t optimize now
and we wouldn’t preserve loops that we don’t preserve now.

I'm a bit worried about the following: It seems like you want to handle C functions that have loops that might be infinite (i.e., those with constant controlling expressions) by adding the maynotprogress attribute to the containing function, and then this attribute to all of the other loops. Is that correct? Also, it seems semantically incorrect to inline functions with the attribute into functions without the attribute unless you add the attribute to the caller. Is that correct? If those are true, then we can end up with cases where, with functions from the same C source file, we're either disallowing inlining or pessimizing the optimization of all loops in the caller. Unless, when inlining, we add the attribute to the caller and also add this metadata to all other loops?

In any case, please explain the intended behavior of the attribute and the metadata upon inlining.

The current implementations are in:
- Changes to the LoopDeletion Pass: https://reviews.llvm.org/D86844
- Changes to the Clang Frontend: https://reviews.llvm.org/D86841
- Changes to LangRef: https://reviews.llvm.org/D86233
- Changed to IR: https://reviews.llvm.org/D85393

The changes preserve what was previously accepted as the “default
behavior” [5]. That is, you get forward progress assumption in case a
function is not marked with the `maynotprogress` attribute. Here the
default behavior is that LLVM IR functions are required to make
forward-progress and are assumed to make forward progress. These
attributes are aimed at helping frontends write correct code as per
their language specs, and in addition, optimize out some dead loops
that we weren’t able to optimize out before but could’ve.

Feedback welcome.

(The name of the function attribute and the loop metadata are still
under discussion, and we’re definitely open to changing them.)

Some additional thoughts on the bikeshedding:

I'm not in love with this name. might_not_progress would be better. We could choose something more colloquial, like may_inf_loop. Or more formal, like no_forward_progress_guarantee. I like this because it seems the most technically accurate and isn't likely to be misread. It's long, however, and even though we have attribute lists, it will still appear a lot.

I think that I like nfpg the best (for "no forward-progress guarantee"). Why nfpg? It's technically accurate and short. Short is useful because, for some languages (any maybe even for some IR from C), the attribute is going to appear on nearly every function. I know that we have attribute lists, but even so. no_fpg is good too.

Thanks again,

Hal

>> Hi All,
>>
>> We’ve prepared a new function attribute `maynotprogress` and loop
>> metadata `llvm.loop.mustprogress` in order to better formalize the way
>> LLVM deals with infinite loops without observable side-effects. This
>> is deeply related to the implicit forward progress requirements in the
>> IR.
>>
>> Background:
>> There has been a demonstrated need for clarity within the forward
>> progress requirements in LLVM IR. This discussion started with the
>> longstanding bug [1], followed by subsequent discussion in [2,3].
>> TL;DR is that LLVM IR needed a clear way to deal with the fact that
>> C/C++ deems certain infinite side-effect free loops as UB while other
>> loops, and other languages, have well defined infinite side-effect
>> free loops.
>>
>> The proposed mechanism was to add an intrinsic: `llvm.sideeffect()`
>> that should be inserted by the frontend into loops to indicate that
>> this loop should be treated as having side-effects, and should not be
>> optimized out. This was implemented in [4], and long story short, it’s
>> been an imperfect solution for other language frontends in various
>> ways.
>
> Can you make the long story not quite so short? What kinds of problems
> have cropped up with this solution?

You mean, in addition to the conceptual problem of introducing an
arbitrary side-effect to prevent transformations from happening?
(And yes, we should revisit `llvm.assume` next.)

So why do this at all:
1) We settle the discussion and finally define what semantic LLVM-IR
has. Basically revisiting [1] and [5] with all the reasoning there.
IMHO, it is in itself a good idea to write "something" about forward
progress down. Either non-attributed IR has it or not, but limbo is
bad. For example, we are fairly conservative right now but still
don't promise not to assume forward progress, the worst situation.
In fact, we have optimizations that assume forward progress and some
that don't, ..
2a) Assuming we always had an implicit forward progress guarantee:
We avoid generic pessimizations for languages that require other
semantics for the IR: Rust, C with constant loop expressions, ...
see [1]. A function that might have an endless loop but which does
not write memory does not write memory. I mean, we still want to
perform transformations even if there is a path in which such a
function is called.
2b) Assuming we do not have an implicit forward progress guarantee:
We can delete loops that do not have side effects even if the trip
count is unknown. I mean, we could have done that in the other case
(2a) but we didn't in loop deletion. Though, we do remove a call if
the function only contained such a loop, ...

Why this way:
- The discussions before concluded IR does have a forward process
guarantee [1,5]. So we don't want to pessimize existing code.
That said, we want to exploit the property, e.g. in LoopDeletion,
during the deduction of `willreturn` (and thereby for
`isGuaranteedToTransferExecutionToSuccessor` and everything that
transitively uses it), ...
- Function attributes are the most fine-grained level, except
instructions, to provide sticky semantics. The instruction level has
however only coarse grained effects, that is why we used
`llvm.sideeffect` so far.
- Loop metadata is reasonably sticky in the few cases we might need it
for optimizations, the key is dropping it doesn't compromise
correctness.

>> Even C/C++ has loops with and loops without this requirement,
>> though we could not distinguish so far.
>
> What kinds of loop could we not distinguish? Can you please provide an
> example?

IIRC, this loop is UB and cannot be reached:

int x = ((int)y) + 1;
while (x < y);

while this loop is not UB and can be reached:

while (1);

Though, I'm not a C language lawyer.

>> In addition, there has been ambiguity regarding the forward-progress
>> requirements in IR, as pointed out in [5].
>>
>> The introduction of the `maynotprogress` IR function attribute and the
>> `llvm.loop.mustprogress` loop metadata tries to resolve this
>> situation. The changes proposed are:
>> - Document that IR Functions are by default expected to make
>> forward-progress (as defined in the C++ Spec [6]).
>> - Implement a `maynotprogress` IR function attribute (not droppable)
>> to indicate that this function is exempt from the above requirement.
>> This will allow frontends to disable IR optimizations that would
>> otherwise optimize away their infinite loops without side-effects.
>> - Implement `llvm.loop.mustprogress` as a loop metadata to notify to
>> the LLVM optimization passes such as LoopDeletion that even if this
>> function is permitted to not make progress, this loop is still
>> required to make progress because it is not one of the infinite
>> side-effect free loops permitted by the frontend language specs. Note
>> that loop metadata can be dropped, so even if this metadata is
>> dropped, we would not optimize away loops that we don’t optimize now
>> and we wouldn’t preserve loops that we don’t preserve now.
>
> I'm a bit worried about the following: It seems like you want to
> handle C functions that have loops that might be infinite (i.e., those
> with constant controlling expressions) by adding the maynotprogress
> attribute to the containing function, and then this attribute to all
> of the other loops. Is that correct?

That was the idea (for C/C++), yes.

> Also, it seems semantically incorrect to inline functions with the
> attribute into functions without the attribute unless you add the
> attribute to the caller. Is that correct?

Yes. We actually talked about this and simply forgot to make the
attribute "sticky", same as for example SpeculativeLoadHardeningAttr.
Patch is underway.

> If those are true, then we can end up with cases where, with functions
> from the same C source file, we're either disallowing inlining or
> pessimizing the optimization of all loops in the caller.

Technically true, assuming we do not use the loop metadata or it is
dropped. However, that is still an improvement to the status quo. Right
now, either we have a forward progress guarantee and the C loop that
should not be deleted might be deleted, or we don't have such a
guarantee and no loop is deleted regardless of the presence of one that
should not be deleted.

Note that it is not only about "empty" loops. Assuming finite loops
helps for loops that do something too. Take:

unsigned count = 0;
for (void *p = s; p != e; p += 4)
   ++count;

which is just fine optimized but if we dropped the `inbounds` from the
GEP, at some point, we end up with a loop instead of a closed form
expression:
https://clang.godbolt.org/z/6dYTYe

> Unless, when inlining, we add the attribute to the caller and also add
> this metadata to all other loops?

For "maximal optimization opportunity" yes. For correctness, we don't
need the metadata at all. Atmn is putting a patch up now to make the
attribute sticky, it's a one liner + tests, and then we can look at the
metadata in a follow up.

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

>> The current implementations are in:
>> - Changes to the LoopDeletion Pass: https://reviews.llvm.org/D86844
>> - Changes to the Clang Frontend: https://reviews.llvm.org/D86841
>> - Changes to LangRef: https://reviews.llvm.org/D86233
>> - Changed to IR: https://reviews.llvm.org/D85393
>>
>> The changes preserve what was previously accepted as the “default
>> behavior” [5]. That is, you get forward progress assumption in case a
>> function is not marked with the `maynotprogress` attribute. Here the
>> default behavior is that LLVM IR functions are required to make
>> forward-progress and are assumed to make forward progress. These
>> attributes are aimed at helping frontends write correct code as per
>> their language specs, and in addition, optimize out some dead loops
>> that we weren’t able to optimize out before but could’ve.
>>
>> Feedback welcome.
>>
>> (The name of the function attribute and the loop metadata are still
>> under discussion, and we’re definitely open to changing them.)
>
> Some additional thoughts on the bikeshedding:
>
> I'm not in love with this name. might_not_progress would be better. We
> could choose something more colloquial, like may_inf_loop. Or more
> formal, like no_forward_progress_guarantee. I like this because it
> seems the most technically accurate and isn't likely to be misread.
> It's long, however, and even though we have attribute lists, it will
> still appear a lot.
>
> I think that I like nfpg the best (for "no forward-progress
> guarantee"). Why nfpg? It's technically accurate and short. Short is
> useful because, for some languages (any maybe even for some IR from
> C), the attribute is going to appear on nearly every function. I know
> that we have attribute lists, but even so. no_fpg is good too.

I'm given up on the name. To be honest, if you don't read the langref
you don't know what these things do half the time, at least not in
detail. Let's just number them, this would be `attribute70` I think :wink:

Cheers,
Johannes

>
>> Hi All,
>>
>> We’ve prepared a new function attribute `maynotprogress` and loop
>> metadata `llvm.loop.mustprogress` in order to better formalize the way
>> LLVM deals with infinite loops without observable side-effects. This
>> is deeply related to the implicit forward progress requirements in the
>> IR.
>>
>> Background:
>> There has been a demonstrated need for clarity within the forward
>> progress requirements in LLVM IR. This discussion started with the
>> longstanding bug [1], followed by subsequent discussion in [2,3].
>> TL;DR is that LLVM IR needed a clear way to deal with the fact that
>> C/C++ deems certain infinite side-effect free loops as UB while other
>> loops, and other languages, have well defined infinite side-effect
>> free loops.
>>
>> The proposed mechanism was to add an intrinsic: `llvm.sideeffect()`
>> that should be inserted by the frontend into loops to indicate that
>> this loop should be treated as having side-effects, and should not be
>> optimized out. This was implemented in [4], and long story short, it’s
>> been an imperfect solution for other language frontends in various
>> ways.
>
>
> Can you make the long story not quite so short? What kinds of problems
> have cropped up with this solution?

You mean, in addition to the conceptual problem of introducing an
arbitrary side-effect to prevent transformations from happening?
(And yes, we should revisit `llvm.assume` next.)

So why do this at all:
1) We settle the discussion and finally define what semantic LLVM-IR
    has. Basically revisiting [1] and [5] with all the reasoning there.
    IMHO, it is in itself a good idea to write "something" about forward
    progress down. Either non-attributed IR has it or not, but limbo is
    bad. For example, we are fairly conservative right now but still
    don't promise not to assume forward progress, the worst situation.
    In fact, we have optimizations that assume forward progress and some
    that don't, ..
2a) Assuming we always had an implicit forward progress guarantee:
     We avoid generic pessimizations for languages that require other
     semantics for the IR: Rust, C with constant loop expressions, ...
     see [1]. A function that might have an endless loop but which does
     not write memory does not write memory. I mean, we still want to
     perform transformations even if there is a path in which such a
     function is called.
2b) Assuming we do not have an implicit forward progress guarantee:
     We can delete loops that do not have side effects even if the trip
     count is unknown. I mean, we could have done that in the other case
     (2a) but we didn't in loop deletion. Though, we do remove a call if
     the function only contained such a loop, ...

Why this way:
  - The discussions before concluded IR does have a forward process
    guarantee [1,5]. So we don't want to pessimize existing code.
    That said, we want to exploit the property, e.g. in LoopDeletion,
    during the deduction of `willreturn` (and thereby for
    `isGuaranteedToTransferExecutionToSuccessor` and everything that
    transitively uses it), ...
  - Function attributes are the most fine-grained level, except
    instructions, to provide sticky semantics. The instruction level has
    however only coarse grained effects, that is why we used
    `llvm.sideeffect` so far.
  - Loop metadata is reasonably sticky in the few cases we might need it
    for optimizations, the key is dropping it doesn't compromise
    correctness.

Another reason why the intrinsic is an imperfect solution is that the
`llvm.sideeffect()` intrinsic would in theory need to be emitted by
the frontend many times - potentially once for each loop and perhaps
one for each function too, depending on how the frontend language
views forward-progress.

The Rust Team implemented the intrinsic into the Rust compiler, and
found that there are significant compile time regressions (5-30%) [7]
(which is not entirely attributable to rustc needing to emit more
instructions, see [8] for some indication of this and further Rust
dialogue) because these intrinsics end up being ubiquitous and LLVM
isn't able to effectively coalesce redundant occurrences.

>> Even C/C++ has loops with and loops without this requirement,
>> though we could not distinguish so far.
>
>
> What kinds of loop could we not distinguish? Can you please provide an
> example?

IIRC, this loop is UB and cannot be reached:

int x = ((int)y) + 1;
while (x < y);

while this loop is not UB and can be reached:

while (1);

Though, I'm not a C language lawyer.

>> In addition, there has been ambiguity regarding the forward-progress
>> requirements in IR, as pointed out in [5].
>>
>> The introduction of the `maynotprogress` IR function attribute and the
>> `llvm.loop.mustprogress` loop metadata tries to resolve this
>> situation. The changes proposed are:
>> - Document that IR Functions are by default expected to make
>> forward-progress (as defined in the C++ Spec [6]).
>> - Implement a `maynotprogress` IR function attribute (not droppable)
>> to indicate that this function is exempt from the above requirement.
>> This will allow frontends to disable IR optimizations that would
>> otherwise optimize away their infinite loops without side-effects.
>> - Implement `llvm.loop.mustprogress` as a loop metadata to notify to
>> the LLVM optimization passes such as LoopDeletion that even if this
>> function is permitted to not make progress, this loop is still
>> required to make progress because it is not one of the infinite
>> side-effect free loops permitted by the frontend language specs. Note
>> that loop metadata can be dropped, so even if this metadata is
>> dropped, we would not optimize away loops that we don’t optimize now
>> and we wouldn’t preserve loops that we don’t preserve now.
>
>
> I'm a bit worried about the following: It seems like you want to
> handle C functions that have loops that might be infinite (i.e., those
> with constant controlling expressions) by adding the maynotprogress
> attribute to the containing function, and then this attribute to all
> of the other loops. Is that correct?

That was the idea (for C/C++), yes.

> Also, it seems semantically incorrect to inline functions with the
> attribute into functions without the attribute unless you add the
> attribute to the caller. Is that correct?

Yes. We actually talked about this and simply forgot to make the
attribute "sticky", same as for example SpeculativeLoadHardeningAttr.
Patch is underway.

> If those are true, then we can end up with cases where, with functions
> from the same C source file, we're either disallowing inlining or
> pessimizing the optimization of all loops in the caller.

Technically true, assuming we do not use the loop metadata or it is
dropped. However, that is still an improvement to the status quo. Right
now, either we have a forward progress guarantee and the C loop that
should not be deleted might be deleted, or we don't have such a
guarantee and no loop is deleted regardless of the presence of one that
should not be deleted.

Note that it is not only about "empty" loops. Assuming finite loops
helps for loops that do something too. Take:

unsigned count = 0;
for (void *p = s; p != e; p += 4)
   ++count;

which is just fine optimized but if we dropped the `inbounds` from the
GEP, at some point, we end up with a loop instead of a closed form
expression:
   https://clang.godbolt.org/z/6dYTYe

> Unless, when inlining, we add the attribute to the caller and also add
> this metadata to all other loops?

For "maximal optimization opportunity" yes. For correctness, we don't
need the metadata at all. Atmn is putting a patch up now to make the
attribute sticky, it's a one liner + tests, and then we can look at the
metadata in a follow up.

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

>> The current implementations are in:
>> - Changes to the LoopDeletion Pass: https://reviews.llvm.org/D86844
>> - Changes to the Clang Frontend: https://reviews.llvm.org/D86841
>> - Changes to LangRef: https://reviews.llvm.org/D86233
>> - Changed to IR: https://reviews.llvm.org/D85393
>>
>> The changes preserve what was previously accepted as the “default
>> behavior” [5]. That is, you get forward progress assumption in case a
>> function is not marked with the `maynotprogress` attribute. Here the
>> default behavior is that LLVM IR functions are required to make
>> forward-progress and are assumed to make forward progress. These
>> attributes are aimed at helping frontends write correct code as per
>> their language specs, and in addition, optimize out some dead loops
>> that we weren’t able to optimize out before but could’ve.
>>
>> Feedback welcome.
>>
>> (The name of the function attribute and the loop metadata are still
>> under discussion, and we’re definitely open to changing them.)
>
>
> Some additional thoughts on the bikeshedding:
>
> I'm not in love with this name. might_not_progress would be better. We
> could choose something more colloquial, like may_inf_loop. Or more
> formal, like no_forward_progress_guarantee. I like this because it
> seems the most technically accurate and isn't likely to be misread.
> It's long, however, and even though we have attribute lists, it will
> still appear a lot.
>
> I think that I like nfpg the best (for "no forward-progress
> guarantee"). Why nfpg? It's technically accurate and short. Short is
> useful because, for some languages (any maybe even for some IR from
> C), the attribute is going to appear on nearly every function. I know
> that we have attribute lists, but even so. no_fpg is good too.

I'm given up on the name. To be honest, if you don't read the langref
you don't know what these things do half the time, at least not in
detail. Let's just number them, this would be `attribute70` I think :wink:

Cheers,
   Johannes

> Thanks again,
>
> Hal
>
>
>>
>> Atmn and Johannes
>>
>> [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
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev@lists.llvm.org
>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>

Atmn

[7] https://github.com/rust-lang/compiler-team/issues/177#issuecomment-578549329
[8] https://blog.rust-lang.org/inside-rust/2020/03/19/terminating-rust.html

Hi Johannes and Atmn,

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

A deeper issue I have with the proposal is that I'm concerned about
adding more attributes which add constraints on program transforms.
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 :))

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?

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

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.

Cheers,
Nicolai

Hi Johannes and Atmn,

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

while(1);

is *not* deleted by LoopDeletion right now, which is correct.

Though,

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

Hi Johannes,

> Hi Johannes and Atmn,
>
>> > 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 :slight_smile:

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

Hi Johannes,

>
>> > Hi Johannes and Atmn,
>> >
>> >> > 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?

Metadata to encode what exactly?

The idea is that loops which do not match the `maynotprogress` defined
via the attribute can be annotated. Thus, if the function is not
`maynotprogress` there is no need for the annotation. If the function
is, loops that do not match `maynotprogress` would at some point be
annotated, either by the frontend or inliner (= the two places that add
`maynotprogress`).

You cannot use metadata in the other direction, thus to opt-in to
`maynotprogress`. You can make `maynotprogress` the default and use
metadata to opt-out, sure. In addition to the regressions we might see,
we basically end up with metadata on almost every C/C++ loop, unsure if
that is a good idea.

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

I'm unsure if annotating every "normal" C/C++ loop and hoping loop
metadata survives is a superior design. At the end of the day the
question is where you want to put the cost (compile time and
optimization potential to some degree). Either make the presence of
well-defined non-progress loops more costly or the presence of undefined
non-progress loops. In our scheme the cost is minimal* if all of your
loops (in a function) fall in one or the other category. I would this to
be the "normal" case for all languages C/C++/Rust/... The design is not
any worse than what you propose (assuming I understood) in case you mix
these loop kinds in a function. We basically fall-back to your scheme on
a function level if required. Admittedly this is more complex but it has
benefits and doesn't appear to be any less clean than the alternative.
We hide the query logic behind a helper function anyway.

* minimal cost: no metadata that needs to be maintained (and which could
be dropped) but full optimization potential

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

Required for what?

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

An incomplete list of function attributes that disable transformations
(not actually checked but I expect them too):
cold, convergent, noduplicate, noimplicitfloat, nomerge, noinline,
nobuiltin, null_pointer_is_valid, optsize, optnone, returns_twice,
"thunk"
Similarly there are parameter attributes that prevent transformations.

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

I'm unsure what language has that guarantee. I don't think this is on
topic but feel free to provide me an example where a frontend, w/o
deduction, can use `willreturn` based on the language semantics.

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

I feel like I mentioned this already a few times. It allows to a correct
representation of C/C++ (and other languages) without giving up on
optimizations we already do. Please clearly state if you would prefer us
to regress instead. I mentioned this already, reversing polarity means
we cannot remove calls that do not have the new attribute and, in
addition, all loops that do have the progress guarantee need annotations
(which need to be preserved).

> 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 :slight_smile:

I guess if you do not schedule something there is not much to say about
it. We usually talk about about all executions and if you don't have
any, everything is true anyway. Unsure how you see that tie in here
though.

~ Johannes

> 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

Hi Johannes,

>> > 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 :slight_smile:

I guess if you do not schedule something there is not much to say about
it. We usually talk about about all executions and if you don't have
any, everything is true anyway. Unsure how you see that tie in here
though.

The point is purely one about understandability of the proposed
LangRef change. The LangRef change talks about "progress" as defined
in [intro.progress] of the C++ spec, but the vast majority of that
section, and _all_ parts of that section that actually use the word
"progress", talk about the kind of forward progress guarantees that
have nothing at all to do with what you're trying to get at in the
proposal. My understanding is that for your proposal here, you're only
really interested in what's written in the very first clause of that
C++ spec section, but that's totally non-obvious from what the
proposed patch to the LangRef says. The point is that the proposed
language is misleading to somebody who approaches it without
preconceptions.

Cheers,
Nicolai

Hi Johannes,

  >> > 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 :slight_smile:

I guess if you do not schedule something there is not much to say about
it. We usually talk about about all executions and if you don't have
any, everything is true anyway. Unsure how you see that tie in here
though.

The point is purely one about understandability of the proposed
LangRef change. The LangRef change talks about "progress" as defined
in [intro.progress] of the C++ spec, but the vast majority of that
section, and _all_ parts of that section that actually use the word
"progress", talk about the kind of forward progress guarantees that
have nothing at all to do with what you're trying to get at in the
proposal. My understanding is that for your proposal here, you're only
really interested in what's written in the very first clause of that
C++ spec section, but that's totally non-obvious from what the
proposed patch to the LangRef says. The point is that the proposed
language is misleading to somebody who approaches it without
preconceptions.

I guess we can say something like:
[6, see the first section under the title "forward progress"]
if you think that makes it easier to read.

Would that address your concern or did I still not understand?

~ Johannes

That would be a step in the right direction, yes.

How about the following:

"This attribute indicates that the function is permitted to not return
or interact with the environment. Functions without this attribute are
implicitly ``mustprogress`` and they must eventually return or
interact with the environment in some way, e.g. via a side effect or
synchronization. ``mustprogress`` is intended to model the
requirements of the first section of [intro.progress] of the C++
standard [6]."

This avoids using the expression "make progress" in a sense that
differs from how the C++ standard defines it.

Cheers,
Nicolai

Hi Johannes,

   >> > 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 :slight_smile:

I guess if you do not schedule something there is not much to say about
it. We usually talk about about all executions and if you don't have
any, everything is true anyway. Unsure how you see that tie in here
though.

The point is purely one about understandability of the proposed
LangRef change. The LangRef change talks about "progress" as defined
in [intro.progress] of the C++ spec, but the vast majority of that
section, and _all_ parts of that section that actually use the word
"progress", talk about the kind of forward progress guarantees that
have nothing at all to do with what you're trying to get at in the
proposal. My understanding is that for your proposal here, you're only
really interested in what's written in the very first clause of that
C++ spec section, but that's totally non-obvious from what the
proposed patch to the LangRef says. The point is that the proposed
language is misleading to somebody who approaches it without
preconceptions.

I guess we can say something like:
     [6, see the first section under the title "forward progress"]
if you think that makes it easier to read.

Would that address your concern or did I still not understand?

That would be a step in the right direction, yes.

How about the following:

"This attribute indicates that the function is permitted to not return
or interact with the environment. Functions without this attribute are
implicitly ``mustprogress`` and they must eventually return or
interact with the environment in some way, e.g. via a side effect or
synchronization. ``mustprogress`` is intended to model the
requirements of the first section of [intro.progress] of the C++
standard [6]."

This avoids using the expression "make progress" in a sense that
differs from how the C++ standard defines it.

That sound pretty good to me.

~ Johannes

  >
  >> Hi All,
  >>
  >> We’ve prepared a new function attribute `maynotprogress` and loop
  >> metadata `llvm.loop.mustprogress` in order to better formalize the way
  >> LLVM deals with infinite loops without observable side-effects. This
  >> is deeply related to the implicit forward progress requirements in the
  >> IR.
  >>
  >> Background:
  >> There has been a demonstrated need for clarity within the forward
  >> progress requirements in LLVM IR. This discussion started with the
  >> longstanding bug [1], followed by subsequent discussion in [2,3].
  >> TL;DR is that LLVM IR needed a clear way to deal with the fact that
  >> C/C++ deems certain infinite side-effect free loops as UB while other
  >> loops, and other languages, have well defined infinite side-effect
  >> free loops.
  >>
  >> The proposed mechanism was to add an intrinsic: `llvm.sideeffect()`
  >> that should be inserted by the frontend into loops to indicate that
  >> this loop should be treated as having side-effects, and should not be
  >> optimized out. This was implemented in [4], and long story short, it’s
  >> been an imperfect solution for other language frontends in various
  >> ways.
  >
  > Can you make the long story not quite so short? What kinds of problems
  > have cropped up with this solution?

You mean, in addition to the conceptual problem of introducing an
arbitrary side-effect to prevent transformations from happening?
(And yes, we should revisit `llvm.assume` next.)

So why do this at all:
1) We settle the discussion and finally define what semantic LLVM-IR
     has. Basically revisiting [1] and [5] with all the reasoning there.
     IMHO, it is in itself a good idea to write "something" about forward
     progress down. Either non-attributed IR has it or not, but limbo is
     bad. For example, we are fairly conservative right now but still
     don't promise not to assume forward progress, the worst situation.
     In fact, we have optimizations that assume forward progress and some
     that don't, ..
2a) Assuming we always had an implicit forward progress guarantee:
      We avoid generic pessimizations for languages that require other
      semantics for the IR: Rust, C with constant loop expressions, ...
      see [1]. A function that might have an endless loop but which does
      not write memory does not write memory. I mean, we still want to
      perform transformations even if there is a path in which such a
      function is called.
2b) Assuming we do not have an implicit forward progress guarantee:
      We can delete loops that do not have side effects even if the trip
      count is unknown. I mean, we could have done that in the other case
      (2a) but we didn't in loop deletion. Though, we do remove a call if
      the function only contained such a loop, ...

Why this way:
   - The discussions before concluded IR does have a forward process
     guarantee [1,5]. So we don't want to pessimize existing code.
     That said, we want to exploit the property, e.g. in LoopDeletion,
     during the deduction of `willreturn` (and thereby for
     `isGuaranteedToTransferExecutionToSuccessor` and everything that
     transitively uses it), ...
   - Function attributes are the most fine-grained level, except
     instructions, to provide sticky semantics. The instruction level has
     however only coarse grained effects, that is why we used
     `llvm.sideeffect` so far.
   - Loop metadata is reasonably sticky in the few cases we might need it
     for optimizations, the key is dropping it doesn't compromise
     correctness.

Another reason why the intrinsic is an imperfect solution is that the
`llvm.sideeffect()` intrinsic would in theory need to be emitted by
the frontend many times - potentially once for each loop and perhaps
one for each function too, depending on how the frontend language
views forward-progress.

The Rust Team implemented the intrinsic into the Rust compiler, and
found that there are significant compile time regressions (5-30%) [7]
(which is not entirely attributable to rustc needing to emit more
instructions, see [8] for some indication of this and further Rust
dialogue) because these intrinsics end up being ubiquitous and LLVM
isn't able to effectively coalesce redundant occurrences.

Thanks, Atmn, Johannes. I definitely agree that putting an artificial side effect in the loop is a conservative solution, and that we can do better. It's important that the rationale is in the RFC, and now it is.

There is another thing that I would like for us to document: do infinite loops have any relationship to thread synchronization? As I recall, this issue came up in the past when we discussed the deletion, or not, of infinite loops. If a thread writes a value to memory, and then enters an infinite loop, is that value eventually visible to other threads? My understanding is that some code depends on this property. If this is something that people would like to see guaranteed, I suspect that we may need specific handling (if nothing else, so we don't sink stores past possibly-infinite loops).

-Hal

There is another thing that I would like for us to document: do

> infinite loops have any relationship to thread synchronization? As I
> recall, this issue came up in the past when we discussed the deletion,
> or not, of infinite loops. If a thread writes a value to memory, and
> then enters an infinite loop, is that value eventually visible to
> other threads? My understanding is that some code depends on this
> property. If this is something that people would like to see
> guaranteed,

I doubt we guarantee that now, though we might not actively exploit it.
I also think we should not treat termination as synchronization, at
least not in the case where progress is required. So, in C (and arguably
we might want to do this also in C++), we would say that:

global_signal = 1;
while (1);

is well defined and we will not remove the write.

FWIW, I would agree that we should write this down though.

> I suspect that we may need specific handling (if nothing
> else, so we don't sink stores past possibly-infinite loops).

If (possibly-)infinite loops are well defined, e.g., in a function with
the `mayprogress` attribute, we certainly cannot move any effect past
them. If they are not, they are UB if they loop infinitely and otherwise
finite and therefore a no-op. So we can either delete them, by assuming
they are finite, or, if we know they are not, actually eliminate
anything that is known to transfer execution to the loop [0].

[0] https://reviews.llvm.org/D87149

~ Johannes

Hi Nicolai and Hal,

I was wondering if your present concerns regarding the directions of
the proposed attributes and semantics of the current direction had
been addressed, so I thought I'd send over a friendly ping. Have they?

Atmn

So, just to reiterate, the proposal is that Clang will look at each function, and:

  • if a function contains any loops which may not progress, will emit “maynotprogress” attribute on the function definition, and “mustprogress” metadata on each loop other than those that may be infinite.
  • otherwise, it will not emit the function attribute “maynotprogress”, and will not emit “mustprogress” metadata on the loops.

And then, whenever LLVM inlines code into another function:

  • If the outer function has maynotprogress, and the inner does not: add mustprogress metadata to all the loops (?) from the inner function.
  • If the outer function does not have maynotprogress, and the inner does: add maynotprogress to the outer function, and add mustprogress to all loops in the outer.
    (But, how do you identify the “loop” to put the metadata on?)

An alternative scheme suggested was to do without the function attribute, and for clang to emit “mustprogress” metadata on every loop which has this property.

Some potential reasons to want not to do the simpler scheme have been expressed:

  • Would deoptimize code emitted by previous frontends which don’t know about mustprogress.
  • Concern that the loop metadata may be lost during other transforms, thus losing the optimization.

I’d like to raise another issue, that I haven’t seen anyone bring up yet – the definition of a “loop” in the context of these “infinite loop” optimizations does not seem to have been made clear, and, I think, is problematic. In the current state of LLVM, I believe a candidate “loop” to delete can be derived from any control flow, it does not need to be derived from an explicit source-language loop construct. Under this proposal, that would still be the case. (unless the function was annotated with maynotprogress.)

For C code, that is incorrect. C only has a must-progress requirement explicitly for iteration statements (“for”, “while”, and “do”). (And of those, only ones which do not have a constant controlling expression). Quoting C11, 6.8.5 Iteration statements, p6, “An iteration statement whose controlling expression is not a constant expression, that performs no input/output operations, does not access volatile objects, and performs no synchronization or atomic operations in its body, controlling expression, or (in the case of for statement) its expression-3, may be assumed by the implementation to terminate.”

So, compiling C code, ISTM that every C function needs to be “maynotprogress”, and only for “for”, “while”, or “do” loops without a constant loop-controlling-expression, can we add the “mustprogress” metadata.

On the other hand, in C++, it would appear that by [intro.progress] there is a guarantee of progress for all control flow in a function, even if you’ve built it out of explicit goto statements.

That is, I believe in C++ this function can be optimized away, but not in C.
void loop_weirdly(int should_loop) {
label:
if (should_loop) goto label;
}

While this may be optimized away in both C and C++:
void loop(int should_loop) {
while (should_loop) ;
}

Another question – can we actually be sure that other control flow won’t get merged into the loop – is it possible for the “mustprogress” metadata to get applied to a wider scope than it should’ve been, after other control flow optimizations occur?

Please scroll to the second to last paragraph for an action item!

>
>> Metadata to encode what exactly?
>>
>> The idea is that loops which do not match the `maynotprogress` defined
>> via the attribute can be annotated. Thus, if the function is not
>> `maynotprogress` there is no need for the annotation. If the function
>> is, loops that do not match `maynotprogress` would at some point be
>> annotated, either by the frontend or inliner (= the two places that add
>> `maynotprogress`).
>>
>> You cannot use metadata in the other direction, thus to opt-in to
>> `maynotprogress`. You can make `maynotprogress` the default and use
>> metadata to opt-out, sure. In addition to the regressions we might see,
>> we basically end up with metadata on almost every C/C++ loop, unsure if
>> that is a good idea.
>
> So, just to reiterate, the proposal is that Clang will look at each
> function, and:
> - if a function contains any loops which may not progress, will emit
> "maynotprogress" attribute on the function definition,

Yes. See also below.

> and "mustprogress" metadata on each loop other than those that may be
> infinite.

The metadata is added to loops that have to make progress but are in
a function in which loops do not have to make progress. It is not
"needed" but an optimization.

Example:

void foo(int N) {
for(int i = 0; i < N; ++i) // <- loop.metadata
bar(i);
int M = N + 1;
while (N < M); // <- loop.metadata, would be removed
if (N)
while (1);
while (N < M); // <- loop.metadata, would be removed
}

> - otherwise, it will not emit the function attribute "maynotprogress", and
> will not emit "mustprogress" metadata on the loops.

Yes. If there is no loop in the code with well-defined semantics if it
is infinite, Clang won't do anything different.

Loops with well-defined semantics if they are infinite are C loops with
a constant conditional (=true), we could include all loops (C++,...)
with a constant conditional while we are at it IMHO.

> And then, whenever LLVM inlines code into another function:
> - If the outer function has maynotprogress, and the inner does not: add
> mustprogress metadata to all the loops (?) from the inner function.

Right. We don't have the patch for this yet I think.

> - If the outer function does not have maynotprogress, and the inner does:
> add maynotprogress to the outer function, and add mustprogress to all loops
> in the outer.

Right. We have a patch for this.

> (But, how do you identify the "loop" to put the metadata on?)

For now, LoopInfo. There is no need to get them all, we can miss some.
To be fair, we don't optimize "loops" that are not recognized by
LoopInfo.

> An alternative scheme suggested was to do without the function attribute,
> and for clang to emit "mustprogress" metadata on every loop which has this
> property.

Right: We can make the universal default `maynotprogress`, so the loops
are well-defined if they are infinite and do nothing. (That means calls
that do not have side effects are then something that cannot be removed
if they might loop indefinitely.) Then we must "opt-in" to all
optimizations, e.g., loop-deletion and more importantly call deletion.
There were ideas to use an attribute to "opt-in" and some to use
metadata, or both.

> Some potential reasons to want not to do the simpler scheme have been
> expressed:
> - Would deoptimize code emitted by previous frontends which don't know
> about mustprogress.
> - Concern that the loop metadata may be lost during other transforms, thus
> losing the optimization.
>
> I'd like to raise another issue, that I haven't seen anyone bring up yet --
> the definition of a "loop" in the context of these "infinite loop"
> optimizations does not seem to have been made clear, and, I think, is
> problematic. In the current state of LLVM, I believe a candidate "loop" to
> delete can be derived from *any* control flow, it does not need to be
> derived from an explicit source-language loop construct. Under this
> proposal, that would still be the case. (unless the function was annotated
> with maynotprogress.)
>
> For C code, that is incorrect. C only has a must-progress requirement
> explicitly for iteration statements ("for", "while", and "do"). (And of
> those, only ones which do not have a constant controlling expression).
> Quoting C11, 6.8.5 Iteration statements, p6, "An iteration statement whose
> controlling expression is not a constant expression, that performs no
> input/output operations, does not access volatile objects, and performs no
> synchronization or atomic operations in its body, controlling expression,
> or (in the case of for statement) its expression-3, may be assumed by the
> implementation to terminate."
>
> So, compiling C code, ISTM that every C function needs to be
> "maynotprogress", and *only* for "for", "while", or "do" loops without a
> constant loop-controlling-expression, can we add the "mustprogress"
> metadata.
>
> On the other hand, in C++, it would appear that by [intro.progress] there
> is a guarantee of progress for *all* control flow in a function, even if
> you've built it out of explicit goto statements.
>
> That is, I believe in C++ this function can be optimized away, but not in C.
> void loop_weirdly(int should_loop) {
> label:
> if (should_loop) goto label;
> }
>
> While this may be optimized away in both C and C++:
> void loop(int should_loop) {
> while (should_loop) ;
> }

This example is great; the compiler council [0] is divided:

Clang + icc*: keep the loop in loop_weirdly but remove calls to it,
both in C and C++.
gcc: follows your interpretation, in C the termination is
well-defined behavior and both the loop in loop_weirdly
as well as a call of it are kept. In C++ both are
removed.
MSVC: plays it conservative and doesn't remove anything in
either mode.

*icc13 removes the loop in loop_weirdly.

I was going to provide options what this means for this RFC and existing
optimizations we do right now, but I think it would be better if people
would first chime in and we agree on what behavior is "correct".

Thanks
Johannes

[0] https://godbolt.org/z/KosGnE

> Another question -- can we actually be sure that other control flow won't
> get merged into the loop -- is it possible for the "mustprogress" metadata
> to get applied to a wider scope than it should've been, after other control
> flow optimizations occur?

I think we can be sure this is OK if all transformations behave as they
already have to. While you can imagine a transformation changing the
loop in different ways, let's say fusion, metadata cannot be kept if it
is potentially invalidated. This is already true for all the other ones
we have, e.g., to override the vectorizer legality checks.

Please scroll to the second to last paragraph for an action item!

>
>> Metadata to encode what exactly?
>>
>> The idea is that loops which do not match the `maynotprogress` defined
>> via the attribute can be annotated. Thus, if the function is not
>> `maynotprogress` there is no need for the annotation. If the function
>> is, loops that do not match `maynotprogress` would at some point be
>> annotated, either by the frontend or inliner (= the two places that add
>> `maynotprogress`).
>>
>> You cannot use metadata in the other direction, thus to opt-in to
>> `maynotprogress`. You can make `maynotprogress` the default and use
>> metadata to opt-out, sure. In addition to the regressions we might see,
>> we basically end up with metadata on almost every C/C++ loop, unsure if
>> that is a good idea.
>
> So, just to reiterate, the proposal is that Clang will look at each
> function, and:
> - if a function contains any loops which may not progress, will emit
> "maynotprogress" attribute on the function definition,

Yes. See also below.

> and "mustprogress" metadata on each loop other than those that may be
> infinite.

The metadata is added to loops that have to make progress but are in
a function in which loops do not have to make progress. It is not
"needed" but an optimization.

Example:

void foo(int N) {
for(int i = 0; i < N; ++i) // <- loop.metadata
bar(i);
int M = N + 1;
while (N < M); // <- loop.metadata, would be removed
if (N)
while (1);
while (N < M); // <- loop.metadata, would be removed
}

> - otherwise, it will not emit the function attribute "maynotprogress", and
> will not emit "mustprogress" metadata on the loops.

Yes. If there is no loop in the code with well-defined semantics if it
is infinite, Clang won't do anything different.

Loops with well-defined semantics if they are infinite are C loops with
a constant conditional (=true), we could include all loops (C++,...)
with a constant conditional while we are at it IMHO.

> And then, whenever LLVM inlines code into another function:
> - If the outer function has maynotprogress, and the inner does not: add
> mustprogress metadata to all the loops (?) from the inner function.

Right. We don't have the patch for this yet I think.

> - If the outer function does not have maynotprogress, and the inner does:
> add maynotprogress to the outer function, and add mustprogress to all loops
> in the outer.

Right. We have a patch for this.

> (But, how do you identify the "loop" to put the metadata on?)

For now, LoopInfo. There is no need to get them all, we can miss some.
To be fair, we don't optimize "loops" that are not recognized by
LoopInfo.

> An alternative scheme suggested was to do without the function attribute,
> and for clang to emit "mustprogress" metadata on every loop which has this
> property.

Right: We can make the universal default `maynotprogress`, so the loops
are well-defined if they are infinite and do nothing. (That means calls
that do not have side effects are then something that cannot be removed
if they might loop indefinitely.) Then we must "opt-in" to all
optimizations, e.g., loop-deletion and more importantly call deletion.
There were ideas to use an attribute to "opt-in" and some to use
metadata, or both.

> Some potential reasons to want not to do the simpler scheme have been
> expressed:
> - Would deoptimize code emitted by previous frontends which don't know
> about mustprogress.
> - Concern that the loop metadata may be lost during other transforms, thus
> losing the optimization.
>
> I'd like to raise another issue, that I haven't seen anyone bring up yet --
> the definition of a "loop" in the context of these "infinite loop"
> optimizations does not seem to have been made clear, and, I think, is
> problematic. In the current state of LLVM, I believe a candidate "loop" to
> delete can be derived from *any* control flow, it does not need to be
> derived from an explicit source-language loop construct. Under this
> proposal, that would still be the case. (unless the function was annotated
> with maynotprogress.)
>
> For C code, that is incorrect. C only has a must-progress requirement
> explicitly for iteration statements ("for", "while", and "do"). (And of
> those, only ones which do not have a constant controlling expression).
> Quoting C11, 6.8.5 Iteration statements, p6, "An iteration statement whose
> controlling expression is not a constant expression, that performs no
> input/output operations, does not access volatile objects, and performs no
> synchronization or atomic operations in its body, controlling expression,
> or (in the case of for statement) its expression-3, may be assumed by the
> implementation to terminate."
>
> So, compiling C code, ISTM that every C function needs to be
> "maynotprogress", and *only* for "for", "while", or "do" loops without a
> constant loop-controlling-expression, can we add the "mustprogress"
> metadata.
>
> On the other hand, in C++, it would appear that by [intro.progress] there
> is a guarantee of progress for *all* control flow in a function, even if
> you've built it out of explicit goto statements.
>
> That is, I believe in C++ this function can be optimized away, but not in C.
> void loop_weirdly(int should_loop) {
> label:
> if (should_loop) goto label;
> }
>
> While this may be optimized away in both C and C++:
> void loop(int should_loop) {
> while (should_loop) ;
> }

This example is great; the compiler council [0] is divided:

Clang + icc*: keep the loop in loop_weirdly but remove calls to it,
both in C and C++.
gcc: follows your interpretation, in C the termination is
well-defined behavior and both the loop in loop_weirdly
as well as a call of it are kept. In C++ both are
removed.

This seems like a reasonable interpretation of the wording of the specifications (although it would be nicer if C included this in its list of observable program behaviors to make things clearer).

-Hal

Hi, Atmn,

Has anyone else expressed an opinion regarding the naming? We need to clarify the semantics in C, it seems.

-Hal

Hi Hal,

Hi, Atmn,

Has anyone else expressed an opinion regarding the naming? We need to
clarify the semantics in C, it seems.

No other names have come in yet, in total the names proposed so far (I
think) are:
- maynotprogress
- maybenoprogress
- might_not_progress
- nfpg
- no_fpg
and the loop metadata has been pretty firmly established as
llvm.loop.mustprogress. IMHO, I've warmed up to no_fpg (or even nfpg
in a pinch if we want to save 33% of space and lose some readability)
since we've made substantial progress in clarifying the exact
definitions of progress in this context and I think it's a good idea
to bake it into the attribute name.

I've also modified the clang patch [0] to only apply either of the
attributes for C functions when compiled with C11 or later so we can
tightly adhere to both the C and C++ standards, and the other changes
that need to be made will be forthcoming. Thanks again to James, that
particular example was pretty cool, and I agree that it may be best to
follow that interpretation.

[0] https://reviews.llvm.org/D86841