[LLVMdev] Add a 'notrap' function attribute?

[Andrew Trick]

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...

- 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.

- 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.

- We would need to encode the sense of the condition (true or false). 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 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131101/90cd0f56/attachment.html>