[llvm-dev] [RFC] Introducing the maynotprogress IR attribute
Atmn Patel via llvm-dev
llvm-dev at lists.llvm.org
Fri Sep 4 22:40:52 PDT 2020
On Sat, Sep 5, 2020 at 1:07 AM Johannes Doerfert
<johannesdoerfert at gmail.com> wrote:
>
>
> On 9/4/20 7:39 PM, Hal Finkel via llvm-dev wrote:
> >
> > 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?
>
> 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 ;)
>
> 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 at 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
More information about the llvm-dev
mailing list