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

Fri Sep 4 17:39:01 PDT 2020

On 9/4/20 6:31 PM, Atmn Patel via llvm-dev wrote:
> 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

>
> 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 at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory