Hi Nadav,
> 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