[LLVMdev] Add a 'notrap' function attribute?
Filip Pizlo
fpizlo at apple.com
Fri Nov 1 19:20:40 PDT 2013
On Nov 1, 2013, at 2:44 PM, Hal Finkel <hfinkel at anl.gov> wrote:
> ----- Original Message -----
>>
>>
>>
>> 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?
>
> Only in the operational sense, not in the semantic sense. Operationally, the metadata node has a weak reference to the value.
>
>>
>>
>> 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.
>
> Correct.
>
>> Can you describe exactly what rules such a use of
>> %c would have?
>
> I don't think that there are any special rules, as such, but there are only a limited set of things that you can meaningfully do with it.
>
>> What would replaceAllUsesWith do for it?
>
> I think that it is replaced with the new value.
I don't think this will work. If it did, what about:
%c = load %p
if (%c) {
%c2 = load %p
if (%c2)
%t = load %q !{ %c2 }
}
It might be strange, but it would certainly be fine to write an optimization that would realize that %c2 is 1 and call replaceAllUsesWith. And then you end up with the breakage.
>
>> How should
>> other phases treat it? What can they do to it?
>>
>
> Other passes can ignore it (although hopefully passes that tend to hoist values, like LICM, will be taught to limit themselves based on this metadata). It can be used only for checking dominance for the purpose of ensuring metadata validity.
I guess I don't follow what it is about !{ %c } that controls when it is safe to execute a load.
- If it's that %c must dominate the load, then that's clearly wrong, since I could have:
%x = ...
if (%b) {
%c = add %x, 1
if (%c)
%t = load %p !{ %c }
}
and then I could hoist %c over the branch on %b, and then the load would seem to be hoistable above the %b check, which could be wrong.
- If it's that %c must be true at the load, then you need to be careful to ensure that any transformation that moves %c or proves anything about it using reasoning about control flow also removes the meta-data. This feels awkward.
-Filip
>
> -Hal
>
>>
>>
>>
>> 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
>>
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131101/981ba207/attachment.html>
More information about the llvm-dev
mailing list