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

[Atmn Patel via llvm-dev]

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