Hello, OpenCL C specifies that instructions should not trap (it is "discouraged" in the specs). If they do, it's vendor-specific how the hardware exceptions are handled. It might be also the case with some other (future) languages targeting "streamlined" parallel accelerators in an heterogeneous setting. At least CUDA comes to mind. What about OpenACC and the new OpenMP, does someone know offhand? It would help several optimizations if they could assume certain instructions do not trap. E.g., I was looking at the if-conversion of the loop vectorizer, and it seems to not support speculating stores, divs, etc. which could be done if we knew it's safe to speculatively execute them. [In this particular if-conversion case proper predicated execution (not speculative) would require predicates to be added for all LLVM instructions so they could be squashed. I think this was discussed several years ago in the context of a generic IR-level if-conversion pass, but it seems such a thing did not realize eventually.] Anyways, "speculative" if-conversion is just one example where knowing that traps need not to be considered in the function at hand would help the optimizations. Also other speculative code motion optimizations, e.g., LICM, could benefit from it. One way would be to introduce a new function attribute. Functions (e.g., OpenCL C or CUDA kernels) could be marked with an attribute that states that the instructions can be assumed not to trap -- it's a programmer's or the runtime's mistake if they do. The runtime should change the fp computation mode to the non-trapping one before calling such a function (this is actually stated in the OpenCL specs). If such handling is not supported by the target, then the attribute should not be added the first place. The attribute could be called 'notrap' which would include the semantics of any trap caused by any instruction. Or that could be split, just in case the hardware is known not to support one of the features. Three could suffice: 'nofptrap' (no IEEE FP exceptions), 'nodivtrap' (no divide by zero exceptions, undef value output instead), 'nomemtrap' (no mem exceptions). What do you think of the general idea? Or is there something similar already that can accomplish this? Thanks in advance, -- Pekka
Hi Pekka, The motivation for the ’notrap’ bit is clear. Domain specific languages can set this bit to enable more aggressive optimizations. I don’t think that the Loop Vectorizer is a good example because it is not designed to vectorize 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. 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 ? Thanks, Nadav On Oct 31, 2013, at 7:38 AM, Pekka Jääskeläinen <pekka.jaaskelainen at tut.fi> wrote:> Hello, > > OpenCL C specifies that instructions should not trap (it is "discouraged" > in the specs). If they do, it's vendor-specific how the hardware > exceptions are handled. > > It might be also the case with some other (future) languages targeting "streamlined" parallel accelerators in an heterogeneous setting. > At least CUDA comes to mind. What about OpenACC and the new OpenMP, > does someone know offhand? > > It would help several optimizations if they could assume certain > instructions do not trap. E.g., I was looking at the if-conversion of > the loop vectorizer, and it seems to not support speculating stores, > divs, etc. which could be done if we knew it's safe to speculatively > execute them. > > [In this particular if-conversion case proper predicated execution > (not speculative) would require predicates to be added for all LLVM > instructions so they could be squashed. I think this was discussed > several years ago in the context of a generic IR-level if-conversion > pass, but it seems such a thing did not realize eventually.] > > Anyways, "speculative" if-conversion is just one example where knowing > that traps need not to be considered in the function at hand > would help the optimizations. Also other speculative code motion > optimizations, e.g., LICM, could benefit from it. > > One way would be to introduce a new function attribute. Functions (e.g., > OpenCL C or CUDA kernels) could be marked with an attribute that states > that the instructions can be assumed not to trap -- it's a programmer's or > the runtime's mistake if they do. The runtime should change the fp > computation mode to the non-trapping one before calling such > a function (this is actually stated in the OpenCL specs). If such > handling is not supported by the target, then the attribute should not > be added the first place. > > The attribute could be called 'notrap' which would include the > semantics of any trap caused by any instruction. Or that could be > split, just in case the hardware is known not to support one of the > features. Three could suffice: 'nofptrap' (no IEEE FP exceptions), > 'nodivtrap' (no divide by zero exceptions, undef value output instead), > 'nomemtrap' (no mem exceptions). > > What do you think of the general idea? Or is there something similar > already that can accomplish this? > > Thanks in advance, > -- > Pekka > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
----- Original Message -----> Hi Pekka, > > The motivation for the ’notrap’ bit is clear.I'd also like to see this functionality.> Domain specific > languages can set this bit to enable more aggressive optimizations. > I don’t think that the Loop Vectorizer is a good example because it > is not designed to vectorize 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. > > 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 ?My hope is that almost all of the benefit can be obtained only by changing isSafeToSpeculativelyExecute -- for memory functions, we already preserve TBAA metadata, and so auditing to preserve notrap seems like it should be reasonable. For floating-point, we preserve fpmath metadata, so that should not be too hard. -Hal> > Thanks, > Nadav > > On Oct 31, 2013, at 7:38 AM, Pekka Jääskeläinen > <pekka.jaaskelainen at tut.fi> wrote: > > > Hello, > > > > OpenCL C specifies that instructions should not trap (it is > > "discouraged" > > in the specs). If they do, it's vendor-specific how the hardware > > exceptions are handled. > > > > It might be also the case with some other (future) languages > > targeting "streamlined" parallel accelerators in an heterogeneous > > setting. > > At least CUDA comes to mind. What about OpenACC and the new OpenMP, > > does someone know offhand? > > > > It would help several optimizations if they could assume certain > > instructions do not trap. E.g., I was looking at the if-conversion > > of > > the loop vectorizer, and it seems to not support speculating > > stores, > > divs, etc. which could be done if we knew it's safe to > > speculatively > > execute them. > > > > [In this particular if-conversion case proper predicated execution > > (not speculative) would require predicates to be added for all LLVM > > instructions so they could be squashed. I think this was discussed > > several years ago in the context of a generic IR-level > > if-conversion > > pass, but it seems such a thing did not realize eventually.] > > > > Anyways, "speculative" if-conversion is just one example where > > knowing > > that traps need not to be considered in the function at hand > > would help the optimizations. Also other speculative code motion > > optimizations, e.g., LICM, could benefit from it. > > > > One way would be to introduce a new function attribute. Functions > > (e.g., > > OpenCL C or CUDA kernels) could be marked with an attribute that > > states > > that the instructions can be assumed not to trap -- it's a > > programmer's or > > the runtime's mistake if they do. The runtime should change the fp > > computation mode to the non-trapping one before calling such > > a function (this is actually stated in the OpenCL specs). If such > > handling is not supported by the target, then the attribute should > > not > > be added the first place. > > > > The attribute could be called 'notrap' which would include the > > semantics of any trap caused by any instruction. Or that could be > > split, just in case the hardware is known not to support one of the > > features. Three could suffice: 'nofptrap' (no IEEE FP exceptions), > > 'nodivtrap' (no divide by zero exceptions, undef value output > > instead), > > 'nomemtrap' (no mem exceptions). > > > > What do you think of the general idea? Or is there something > > similar > > already that can accomplish this? > > > > Thanks in advance, > > -- > > Pekka > > _______________________________________________ > > LLVM Developers mailing list > > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > _______________________________________________ > 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
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
FYI, see also the previous discussion about "speculatable": http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-July/064426.html I think such an attribute should be added. In the thread which lead up to that thread, I proposed using more fine-grained attributes and Michael rightly pointed out the problem with that: you'd need one for every possible form of undefined behaviour. You listed "nofptrap", "nodivtrap" and "nomemtrap", but you didn't say "nounreachabletrap". Whoops! Nick On 31 October 2013 07:38, Pekka Jääskeläinen <pekka.jaaskelainen at tut.fi>wrote:> Hello, > > OpenCL C specifies that instructions should not trap (it is "discouraged" > in the specs). If they do, it's vendor-specific how the hardware > exceptions are handled. > > It might be also the case with some other (future) languages targeting > "streamlined" parallel accelerators in an heterogeneous setting. > At least CUDA comes to mind. What about OpenACC and the new OpenMP, > does someone know offhand? > > It would help several optimizations if they could assume certain > instructions do not trap. E.g., I was looking at the if-conversion of > the loop vectorizer, and it seems to not support speculating stores, > divs, etc. which could be done if we knew it's safe to speculatively > execute them. > > [In this particular if-conversion case proper predicated execution > (not speculative) would require predicates to be added for all LLVM > instructions so they could be squashed. I think this was discussed > several years ago in the context of a generic IR-level if-conversion > pass, but it seems such a thing did not realize eventually.] > > Anyways, "speculative" if-conversion is just one example where knowing > that traps need not to be considered in the function at hand > would help the optimizations. Also other speculative code motion > optimizations, e.g., LICM, could benefit from it. > > One way would be to introduce a new function attribute. Functions (e.g., > OpenCL C or CUDA kernels) could be marked with an attribute that states > that the instructions can be assumed not to trap -- it's a programmer's or > the runtime's mistake if they do. The runtime should change the fp > computation mode to the non-trapping one before calling such > a function (this is actually stated in the OpenCL specs). If such > handling is not supported by the target, then the attribute should not > be added the first place. > > The attribute could be called 'notrap' which would include the > semantics of any trap caused by any instruction. Or that could be > split, just in case the hardware is known not to support one of the > features. Three could suffice: 'nofptrap' (no IEEE FP exceptions), > 'nodivtrap' (no divide by zero exceptions, undef value output instead), > 'nomemtrap' (no mem exceptions). > > What do you think of the general idea? Or is there something similar > already that can accomplish this? > > Thanks in advance, > -- > Pekka > ______________________________**_________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/**mailman/listinfo/llvmdev<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/19bed835/attachment.html>
On 11/01/2013 10:26 PM, Nick Lewycky wrote:> FYI, see also the previous discussion about "speculatable": > > http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-July/064426.html > > I think such an attribute should be added. > > In the thread which lead up to that thread, I proposed using more > fine-grained attributes and Michael rightly pointed out the problem with > that: you'd need one for every possible form of undefined behaviour. You > listed "nofptrap", "nodivtrap" and "nomemtrap", but you didn't say > "nounreachabletrap". Whoops!Thanks for the link. I'm not sure if you meant to merge the 'speculatable' with 'notrap' or just take it in account when implementing optimizations based on 'notrap'. The notrap attribute(s) will not work as a replacement for the 'speculatable' to be able to speculatively call the function itself, but would work for optimizations inside the function itself. "Speculatable" implies also more of the semantic information of the program's logic (e.g. the halting problem mentioned in the above thread). Also, 'speculatable' does not imply 'notrap' because the function itself might have instructions that should not be speculated separately. That is, it won't trap if the original control dependencies are respected, but might trap in case of some (illegal) speculative execution is done inside the function (for example tests for special cases in FP computation or NULL ptr checks). The connection here is that optimizations based on 'notrap' might make a previously 'speculatable' function 'non-speculatable' unless the 'notrap' is respected (by the runtime so it disables exceptions). It should be ok, the notrap should just not be dropped. This also indicates that it should be an attribute, not MD. On the question whether there should be one or more fine grained 'notrap' attributes: If there is a single 'notrap' only, it would state that none of the instructions inside the function cause traps regardless of how they were speculatively executed. This can be true because of the hardware (e.g. one that does not implement the exceptions the first place or does not have an MMU/mem protection) or if the exceptions can be and are switched off before calling the function. E.g., a load inside a NULL pointer check can be hoisted above the check, etc. Creepy looking optimizations for memory protected envs that trap on illegal access. If there were more fine grained attributes, one could just state the non-trapping property for a subset of cases. It's future proof in a sense that a monolithic 'notrap' implies it is possible switch off any type of potential exception, which it might not be for some platform while the finer granularity ones assume only partial support. It should be emphasized that 'no*trap' attirubtes would be a contract: it does not state that it is known that the instructions do not trap, but tells that inside the function there might be speculated instructions that do trap in case the trap(s) are not switched off. -- Pekka
Nick, I like the simplicity of the attribute approach. However, one of the problems of using the attribute approach is that you lose them when you inline the function. I am not sure if this problem disqualifies this approach for the proposed uses or not. Thanks, Nadav On Nov 1, 2013, at 1:26 PM, Nick Lewycky <nlewycky at google.com> wrote:> FYI, see also the previous discussion about "speculatable": > > http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-July/064426.html > > I think such an attribute should be added. > > In the thread which lead up to that thread, I proposed using more fine-grained attributes and Michael rightly pointed out the problem with that: you'd need one for every possible form of undefined behaviour. You listed "nofptrap", "nodivtrap" and "nomemtrap", but you didn't say "nounreachabletrap". Whoops! > > Nick > > > On 31 October 2013 07:38, Pekka Jääskeläinen <pekka.jaaskelainen at tut.fi> wrote: > Hello, > > OpenCL C specifies that instructions should not trap (it is "discouraged" > in the specs). If they do, it's vendor-specific how the hardware > exceptions are handled. > > It might be also the case with some other (future) languages targeting "streamlined" parallel accelerators in an heterogeneous setting. > At least CUDA comes to mind. What about OpenACC and the new OpenMP, > does someone know offhand? > > It would help several optimizations if they could assume certain > instructions do not trap. E.g., I was looking at the if-conversion of > the loop vectorizer, and it seems to not support speculating stores, > divs, etc. which could be done if we knew it's safe to speculatively > execute them. > > [In this particular if-conversion case proper predicated execution > (not speculative) would require predicates to be added for all LLVM > instructions so they could be squashed. I think this was discussed > several years ago in the context of a generic IR-level if-conversion > pass, but it seems such a thing did not realize eventually.] > > Anyways, "speculative" if-conversion is just one example where knowing > that traps need not to be considered in the function at hand > would help the optimizations. Also other speculative code motion > optimizations, e.g., LICM, could benefit from it. > > One way would be to introduce a new function attribute. Functions (e.g., > OpenCL C or CUDA kernels) could be marked with an attribute that states > that the instructions can be assumed not to trap -- it's a programmer's or > the runtime's mistake if they do. The runtime should change the fp > computation mode to the non-trapping one before calling such > a function (this is actually stated in the OpenCL specs). If such > handling is not supported by the target, then the attribute should not > be added the first place. > > The attribute could be called 'notrap' which would include the > semantics of any trap caused by any instruction. Or that could be > split, just in case the hardware is known not to support one of the > features. Three could suffice: 'nofptrap' (no IEEE FP exceptions), > 'nodivtrap' (no divide by zero exceptions, undef value output instead), > 'nomemtrap' (no mem exceptions). > > What do you think of the general idea? Or is there something similar > already that can accomplish this? > > Thanks in advance, > -- > Pekka > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > _______________________________________________ > 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/20131104/679fe367/attachment.html>