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

[James Y Knight via llvm-dev]

On Mon, Sep 7, 2020 at 5:17 PM Johannes Doerfert via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> 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, 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?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200910/025866fe/attachment.html>