[LLVMdev] Add a 'notrap' function attribute?

[Hal Finkel]

----- Original Message -----
> 
> 
> 
> On Nov 1, 2013, at 4:48 AM, Hal Finkel < hfinkel at anl.gov > wrote:
> 
> 
> 3. Represent the control dependencies explicitly in the metadata.
> Andy, Arnold (CC'd) and I have been discussing this in a
> slightly-different context, and briefly, this means adding all of
> the relevant conditional branch inputs to the metadata, and ensuring
> dominance before the metadata is respected. For example:
> 
> if (i1 %c = call z_is_never_zero()) {
> %x = %y / %z !notrap !{ %c }
> ...
> }
> 
> and so if we run across this situation:
> 
> %x = %y / %z !notrap !{ %c }
> if (i1 %c = call z_is_never_zero()) {
> ...
> }
> 
> we can test that the %c does not dominate %x, and so the metadata
> needs to be ignored. The complication here is that you may need to
> encode all conditional branch inputs along all paths from the entry
> to the value, and the scheme also needs to deal with maythrow
> functions.
> 
> 
> 
> This does not need to be resolved to move forward with Pekka’s
> proposal, but since we’re talking about it...
> 

*If* we're going to introduce metadata with implied control dependencies, then we need to figure this out. Otherwise, yes.

> 
> - The control dependent metadata looks like it could work, I like the
> idea (although we’re lacking a strong motivation)
> 
> 
> - I’m not sure why divide-by-zero would motivate this (probably just
> missing something). LLVM doesn’t model it as a trap currently. And
> if it did, an explicit nonzero-divisor check would be easy to reason
> about without any metadata.

I think that the proposal is meant to be more general, also covering things like ensuring that loads/stores don't trap. Specifically being able to indicate that certain loads (and perhaps stores) are safe to speculatively execute is my primary interest in this. 

> 
> 
> - The semantics should be that control dependent metadata is
> guaranteed if only the encoded conditions can be proven to hold,
> independent of surrounding control flow. So we would never use this
> if we needed to encode all branch conditions from entry to home
> block. e.g. only a single nonzero divisor check is sufficient.

Sounds good (I've not thought of a counter-example).

> 
> 
> - We would need to encode the sense of the condition (true or false).

Good point. More generally, it would need to encode which branch index we need (in the case of a switch instruction).

> The metadata is still valid if we can see that the condition
> controls a branch, and the corresponding branch target
> (non-critical-edge) dominates the operation. This is cool because
> optimizations can be totally oblivious, but the information will
> still be preserved most of the time.
> 
> 
> 
> 
> 
> and the scheme also needs to deal with maythrow functions.

I think that you misunderstood what I meant. If we have:

 check_something();
 %x = load %ptr, !notrap

 Then it could be that %ptr will never trap because check_something() will throw in all cases where the load will trap. As a result, we also need to encode a dependency between all functions that may throw (or longjmp or whatever) and the notrap metadata.

Thanks again,
Hal

> 
> 
> I guess maythrow is implicitly the inverse of nounwind. notrap is
> similar but actually makes much more sense to me as an attribute. (I
> always thought that maythrow should be modeled with an invoke).
> longjmp isn’t clean but could be modeled as writing all memory and
> maybe-trapping.
> 
> 
> Adding a flag for every subtle behavior gets pedantic, as seen in
> this thread:
> http://llvm.1065342.n5.nabble.com/Does-nounwind-have-semantics-td59631.html
> 
> 
> The much more interesting question to me is what are the semantics of
> traps? Conservatively, we now assume they are well defined calls to
> abort(). I think that is way too conservative for most uses. It
> would be great to have another flavor of trap that can be reordered
> with certain side effects, particularly other “floating traps". Nuno
> Lopes ran into this problem with bounds check elimination. I don’t
> have a link to the discussion.
> 
> 
> 
> 
> Given that the common use case for this seems like it will be for
> some language frontend to add !notrap to *all* instances of some
> kind of instruction (divisions, load, etc.), I think that adding a
> new flag (like the nsw flag) may be more appropriate for efficiency
> reasons. Even easier, add some more fine-grained function attributes
> (as you had suggested).
> 
> 
> 
> Good point. Seems like a future optimization though.
> 
> 
> Also, I think that being able to tag a memory access as no trapping
> could be a big win for C++ too, because we could tag all
> loads/stores that come from C++ reference types as not trapping.
> Because of the way that iterators are defined, I suspect this would
> have a lot of positive benefits in terms of LICM and other
> optimizations.
> 
> 
> I didn’t follow this, but obviously it would be a huge benefit type
> checked languages. Teaching optimizations about it would be
> nontrivial work though.
> 
> 
> -Andy

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory