[LLVMdev] Add a 'notrap' function attribute?
Andrew Trick
atrick at apple.com
Fri Nov 1 14:45:15 PDT 2013
On Nov 1, 2013, at 1:45 PM, Filip Pizlo <fpizlo at apple.com> wrote:
>
> 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?
We have to be very clear about answering these questions *if* we actually implement the control dependent metadata, but I don’t see this as a new problem.
In general, metadata uses cannot be considered SSA uses. We are not going to do SSA update on metadata, ever. LLVM will not have metadata phis.
Optimizations that walk uses and correlate their values with control flow should also definitely not process metadata.
I am concerned that the compare itself would be processed by CorrelatedValuePropagation, which would call replaceAllUsesWith. Metadata uses are currently updated with RAUW, but it isn’t clear that’s the right thing. Either the RAUW interface could be extended, or, worst case, we could make these “control dependent uses” a special ValueHandle that doesn’t automatically update on RAUW.
-Andy
>>
>> 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
>
> _______________________________________________
> 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/35861332/attachment.html>
More information about the llvm-dev
mailing list