Hi Nadav, On 10/31/2013 08:53 PM, Nadav Rotem wrote:> data-parallel languages which have a completely different semantics. In > OpenCL/Cuda you would want to vectorize the outermost loop, and the > language guarantees that it is safe to so.Yeah. This is the separate (old) discussion and not strictly related to the problem at hand. Better if-conversion benefits more than OpenCL C work-item loops. [For reference, here's an email in the thread from Spring. This discussion lead to the parallel loop metadata to mark the data-parallel loops: http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-January/058710.html The current status of this work is that there's now also effectively loop interchange functionality in pocl so the inner (sequential) loops in the OpenCL C kernels are interchanged with the implicit parallel work-item (outer) loops when it's semantically legal. After this the inner loop vectorizer can be used efficiently also for kernels with sequential loops.]> Function attribute is one possible solution. Another solution would be to > use metadata. I think that we need to explore both solutions and estimate > their effect on the rest of the compiler. Can you estimate which parts of > the compiler would need to be changed in order to support this new piece > of information ? We need to think about what happens when we merge or > hoist load/stores. Will we need to review and change every single memory > optimization in the compiler ?The original idea was that if the function is marked notrap, it only loosens the previous restrictions for the optimizations. Thus, if the old code still assumes trapping semantics, it should be still safe (only worse optimizations might result). Anyways, this has at least one problem that I see: functions that have the notrap attribute cannot be safely inlined to functions without that attribute. Otherwise a function which has possibly been optimized with the assumption of not trapping (and speculate an instruction that might trap), might again trap due to dropping the attribute (and the runtime not knowing it has to switch off the trapping behavior). Thus, perhaps notrap should simply always imply noinline to avoid this issue. The another way is to add 'notrap' metadata to all possibly trapping instructions. This should be safe and perhaps work across inlining, but it requires more maintenance code and it might not work very well in practice: the runtime might want to (or be able to) switch the trapping semantics of e.g. the FP hardware on function basis, not per instruction. If that's not the case, the code generator has to support the instructions separately, injecting instructions that switch on/off the trapping behavior. The metadata approach has a benefit that there can be optimizations, unrelated to the input language, that intelligently prove whether a particular instruction instance can trap or not. E.g., if it's known from code that a divider of a division is never zero, one can set this metadata to a single DIV instruction, perhaps helping later optimizations. IMHO, the attribute approach is easier and makes more sense in this particular case where the trapping behavior is dictated by the input language, but OTOH the metadata approach seems to go better along how it has been done previously (fpmath) and might open the door for separate non-language-specific optimizations. BR, -- --Pekka
----- Original Message -----> Hi Nadav, > > On 10/31/2013 08:53 PM, Nadav Rotem wrote: > > data-parallel languages which have a completely different > > semantics. In > > OpenCL/Cuda you would want to vectorize the outermost loop, and the > > language guarantees that it is safe to so. > > Yeah. This is the separate (old) discussion and not strictly related > to > the problem at hand. Better if-conversion benefits more than OpenCL C > work-item loops. > > > > [For reference, here's an email in the thread from Spring. This > discussion > lead to the parallel loop metadata to mark the data-parallel loops: > > http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-January/058710.html > > The current status of this work is that there's now also effectively > loop interchange functionality in pocl so the inner (sequential) > loops > in the OpenCL C kernels are interchanged with the implicit parallel > work-item (outer) loops when it's semantically legal. After this the > inner loop vectorizer can be used efficiently also for kernels with > sequential loops.] > > > Function attribute is one possible solution. Another solution > > would be to > > use metadata. I think that we need to explore both solutions and > > estimate > > their effect on the rest of the compiler. Can you estimate which > > parts of > > the compiler would need to be changed in order to support this new > > piece > > of information ? We need to think about what happens when we merge > > or > > hoist load/stores. Will we need to review and change every single > > memory > > optimization in the compiler ? > > The original idea was that if the function is marked notrap, it only > loosens the previous restrictions for the optimizations. Thus, if the > old code still assumes trapping semantics, it should be still safe > (only > worse optimizations might result). > > Anyways, this has at least one problem that I see: functions that > have > the notrap attribute cannot be safely inlined to functions without > that > attribute. Otherwise a function which has possibly been optimized > with the > assumption of not trapping (and speculate an instruction that might > trap), > might again trap due to dropping the attribute (and the runtime not > knowing it has to switch off the trapping behavior). Thus, perhaps > notrap should simply always imply noinline to avoid this issue. > > The another way is to add 'notrap' metadata to all possibly trapping > instructions. This should be safe and perhaps work across inlining, > but it requires more maintenance code and it might not work very > well in practice: the runtime might want to (or be able to) switch > the trapping semantics of e.g. the FP hardware on function basis, not > per instruction. If that's not the case, the code generator has > to support the instructions separately, injecting instructions that > switch on/off the trapping behavior. > > The metadata approach has a benefit that there can be optimizations, > unrelated to the input language, that intelligently prove whether a > particular instruction instance can trap or not. E.g., if it's known > from code that a divider of a division is never zero, one can set > this metadata to a single DIV instruction, perhaps helping later > optimizations. > > IMHO, the attribute approach is easier and makes more sense in > this particular case where the trapping behavior is dictated > by the input language, but OTOH the metadata approach seems to go > better along how it has been done previously (fpmath) and might > open the door for separate non-language-specific optimizations.The large complication that you end up with a scheme like this is maintaining control dependencies. For example: if (z_is_never_zero()) { x = y / z !notrap ... } the !notrap asserts that the division won't trap, which is good, but also makes it safe to speculatively execute. That's the desired effect, but not in this instance, because it will allow hoisting outside of the current block: x = y / z !notrap if (z_is_never_zero()) { ... } and that obviously won't work correctly. This seems to leave us with three options: 1. Add logic to all passes that might do this to prevent it (in which case, we might as well add some new (subclass data) flags instead of metadata). 2. Assert that !notrap cannot be used where its validity might be affected by control dependencies. 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. 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). 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. -Hal> > BR, > -- > --Pekka > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
On 11/01/2013 01:48 PM, Hal Finkel wrote:> The large complication that you end up with a scheme like this is > maintaining control dependencies. [...]Good point.> 2. Assert that !notrap cannot be used where its validity might be affected > by control dependencies.Thus, I propose that if this ends up being per-instruction property, its semantics would include this restriction.> 3. Represent the control dependencies explicitly in the metadata. [...]This could work but might get quite complex (especially its maintenance) for the received benefit.> 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). > > 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.True. So, it seems there would be benefit from per-instruction flags or metadata. Which one (an instruction flag or MD) is better, I'm not sure. Is the flag too intrusive (it affects the bitcode format, doesn't it?). The MD seems more trivial. The main drawback I see is maintaining it across optimizations. The question is whether the basic metadata principle applies: Optimizations that do not maintain it (and thus might drop it), or do not understand its semantics, should not break. A problem is that the notrap has two use cases: to communicate to the optimizations that an instruction instance does never trap (known from the language or static analysis), thus it's safe to speculate it. The second meaning (my original one) is that the language (or maybe a compiler switch) dictates that any instruction instance _should_ not trap (is undefined if it does or use NaN propagation). In this case the instructions might trap unless hardware is instructed not to (switch off FP exceptions, use a special dummy signal handler for divbyzero) before executing the instruction (or function). If the latter is implemented using MD and some optimization drops it, it might break programs that assume (due to the language/switch) that there are no traps, but propagate NaNs from illegal fp operations, because the instructions work as intended only if the FP exceptions are switched off. So, perhaps both, a function attribute, and an MD (that can be safely removed) are called for as their use cases and applicability are different. -- Pekka
On Nov 1, 2013, at 4:48 AM, Hal Finkel <hfinkel at anl.gov> wrote:> ----- Original Message ----- >> Hi Nadav, >> >> On 10/31/2013 08:53 PM, Nadav Rotem wrote: >>> data-parallel languages which have a completely different >>> semantics. In >>> OpenCL/Cuda you would want to vectorize the outermost loop, and the >>> language guarantees that it is safe to so. >> >> Yeah. This is the separate (old) discussion and not strictly related >> to >> the problem at hand. Better if-conversion benefits more than OpenCL C >> work-item loops. >> >> >> >> [For reference, here's an email in the thread from Spring. This >> discussion >> lead to the parallel loop metadata to mark the data-parallel loops: >> >> http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-January/058710.html >> >> The current status of this work is that there's now also effectively >> loop interchange functionality in pocl so the inner (sequential) >> loops >> in the OpenCL C kernels are interchanged with the implicit parallel >> work-item (outer) loops when it's semantically legal. After this the >> inner loop vectorizer can be used efficiently also for kernels with >> sequential loops.] >> >>> Function attribute is one possible solution. Another solution >>> would be to >>> use metadata. I think that we need to explore both solutions and >>> estimate >>> their effect on the rest of the compiler. Can you estimate which >>> parts of >>> the compiler would need to be changed in order to support this new >>> piece >>> of information ? We need to think about what happens when we merge >>> or >>> hoist load/stores. Will we need to review and change every single >>> memory >>> optimization in the compiler ? >> >> The original idea was that if the function is marked notrap, it only >> loosens the previous restrictions for the optimizations. Thus, if the >> old code still assumes trapping semantics, it should be still safe >> (only >> worse optimizations might result). >> >> Anyways, this has at least one problem that I see: functions that >> have >> the notrap attribute cannot be safely inlined to functions without >> that >> attribute. Otherwise a function which has possibly been optimized >> with the >> assumption of not trapping (and speculate an instruction that might >> trap), >> might again trap due to dropping the attribute (and the runtime not >> knowing it has to switch off the trapping behavior). Thus, perhaps >> notrap should simply always imply noinline to avoid this issue. >> >> The another way is to add 'notrap' metadata to all possibly trapping >> instructions. This should be safe and perhaps work across inlining, >> but it requires more maintenance code and it might not work very >> well in practice: the runtime might want to (or be able to) switch >> the trapping semantics of e.g. the FP hardware on function basis, not >> per instruction. If that's not the case, the code generator has >> to support the instructions separately, injecting instructions that >> switch on/off the trapping behavior. >> >> The metadata approach has a benefit that there can be optimizations, >> unrelated to the input language, that intelligently prove whether a >> particular instruction instance can trap or not. E.g., if it's known >> from code that a divider of a division is never zero, one can set >> this metadata to a single DIV instruction, perhaps helping later >> optimizations. >> >> IMHO, the attribute approach is easier and makes more sense in >> this particular case where the trapping behavior is dictated >> by the input language, but OTOH the metadata approach seems to go >> better along how it has been done previously (fpmath) and might >> open the door for separate non-language-specific optimizations. > > The large complication that you end up with a scheme like this is maintaining control dependencies. For example: > > if (z_is_never_zero()) { > x = y / z !notrap > ... > } > > the !notrap asserts that the division won't trap, which is good, but also makes it safe to speculatively execute. That's the desired effect, but not in this instance, because it will allow hoisting outside of the current block: > > x = y / z !notrap > if (z_is_never_zero()) { > ... > } > > and that obviously won't work correctly. This seems to leave us with three options: > > 1. Add logic to all passes that might do this to prevent it (in which case, we might as well add some new (subclass data) flags instead of metadata). > > 2. Assert that !notrap cannot be used where its validity might be affected by control dependencies. > > 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 } > ... > }Does this !{%c} reference to %c obey the same rules that other uses of a value would obey in LLVM? If it does, then the following transformation would be trivially valid: if (i1 %c = call z_is_never_zero()) { %x = %y / %z !notrap !{ 1 } ... } Because we can prove that %c must have the value 1 inside the then case. But, now you have a !notrap !{1}, which means you can do: %x = %y / %z !notrap !{ 1 } if (i1 %c = call z_is_never_zero()) { ... } ... and the world just broke. So clearly, the !{ %c } reference cannot obey all of the same rules as other uses of a value would obey in LLVM IR. Can you describe exactly what rules such a use of %c would have? What would replaceAllUsesWith do for it? How should other phases treat it? What can they do to it?> > 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. > > 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). > > 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. > > -Hal > >> >> BR, >> -- >> --Pekka >> >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> > > -- > Hal Finkel > Assistant Computational Scientist > Leadership Computing Facility > Argonne National Laboratory > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131101/b9f7c7d0/attachment.html>
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>