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>
----- 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
On Nov 1, 2013, at 3:13 PM, Hal Finkel <hfinkel at anl.gov> wrote:> 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.Oh, of course. I missed that. I don’t have any clever ideas. Brute force would be adding a metadata ID to the call. We’re already talking about adding TBAA to calls though. It doesn’t solve the problem, but might handle some of the use-cases. -Andy -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131101/6f107444/attachment.html>
On 11/1/13 2:07 PM, Andrew Trick wrote:> > - 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.This is far enough off topic to not be worth discussing now, but I want to throw out that there would be interested parties in defining trapping versions of LLVM instructions which currently use undef semantics for edge cases. We haven't dug into this much yet, but it is something we're probably going to be interested in long term. Our initial approach is to simply use explicit conditional guards to handle things like div-by-zero and null-dereference. Depending on the performance we see with that approach, we may be interested in implementing support for implicit checks which would likely require explicitly trapping semantics. Philip -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131104/8ec3f689/attachment.html>