llvm dev - Oct 2016 - Killing undef and spreading poison

>> >> Here we are evaluating C2 before C.  If the original loop
never
>> >> executed then we had never evaluated C2, while now we do.  So
we
>> >> need
>> >> to make sure there's no UB for branching on C2.  Freeze
ensures
>> >> that
>> >> so we would actually have 'if (freeze(C2))' instead.
>> >> Note that having branch on poison not trigger UB has its own
>> >> problems.
>> >
>> > Can you please elaborate on these problems?
>>
>> Sure! For example, the following transformation would be wrong if
>> branch on poison was a non-deterministic branch instead of UB:
>>
>>     %a = add i32 %x, 1
>>     %c = icmp eq i32 %a, %poison
>>     br i1 %c, label %bb1, label %bb2
>> bb1:
>>     %b = add i32 %x, 1
>>     %d = call i32 @bar(i32 %b)
>> ->
>> bb1:
>>     %d = call i32 @bar(i32 % poison)
>>
>> GVN will perform this kind of transformation: it concludes that %a,
>> %b, and %poison are all equal and picks one representative value.
>> However, these values are equal only when they are not poison.
>
> Okay; so the problem is that an instruction that is value-equivalent to a 
> poison value is not itself necessarily poison?
Right.
I think there were other examples, but I don't have them here handy.  But at
least this one is very problematic for GVN.

>> >> Discussion on select
>> >> ===================>> >> Select is a tricky
instruction to define semantics for.  There are
>> >> multiple views of select's purpose that are contradictory:
>> >>  1) Select should be equivalent to arithmetic (e.g., allow
>> >>   'select
>> >> %c, true, %x' -> 'or %c, %x' and arithmetic
-> select)
>> >>  2) br + phi -> select should be allowed (simplifyCFG)
>> >>  3) Select -> br + phi should be allowed
>> >>
>> >> Since we really want to have 2) since that's simplifyCFG,
we
>> >> propose
>> >> to make 'select %c, %a, %b' poison if any of the
following holds:
>> >>  - %c is poison
>> >>  - %c = true and %a is poison
>> >>  - %c = false and %b is poison
>> >>
>> >> This disallows 3) and some transformations of 1). Since 3) is
only
>> >> performed in CodeGenPrepare, we can safely ignore it (no
>> >> aggressive
>> >> optimizations are run afterwards).
>> >
>> > This strikes me as a dangerous game to play. CGP's
transformations
>> > need to be semantically sound (even if they are anti-canonical).
>> > In part, this is because our IR-level analyses are used by CGP.
>> > Moreover, targets after CGP run IR-level transformations, and
>> > having different semantic rules there is going to make code reuse
>> > hard in subtle ways. Which brings up another issue: We currently
>> > have undef at the MI level; do you propose changing that, and if
>> > so, how?
>>
>> It is sound to do the transformation at IR level if you freeze the
>> condition.
>> My suggestion was to avoid introducing overhead in CGP.  This is the
>> current state of affairs and it seems to work right now.  I'm not
>> shocked to see the IR changing the semantics throughout the
>> pipeline, since while the compiler proceeds, the type of
>> transformations done also change.
>> But I have to say that my understanding of LLVM after CGP is very
>> limited. I was not aware of the code reuse from IR-level analyses.
>>  I agree this needs to be scrutinized carefully.  Alternatively, we
>> can just introduce freeze and pay the price (likely low anyway).
>
> I think we'd need to do this to ensure consistency; I don't think
that the
> price would be high, especially because we soon drop into different 
> representations and the IR is used only for analysis (for pointer 
> aliasing, etc.).
Ok, makes sense; thanks!

>> Regarding undef at MI level, we are not proposing any change.  I
>> don't see any reason right now to change it since it seems that
>> optimizations at MI level are fine with just having undef. There's
>> no nsw/nuw stuff there and undef seems very useful.
>
> We've already started propagating nsw/nuw into the SDAG, and as we move
> toward GlobalISel, we'll have them at the MI layer as well. I think
we'll
> need to consider how to propagate this information to the MI layer 
> directly.
I see.  Then it might make sense to introduce poison in MI then.  But only 
if there's a plan to start doing optimizations that leverage nsw/nuw at MI 
level as well.  Otherwise undef is just fine.
I guess we need to do this in phases, though, to avoid breaking everything 
at the same time :)

Nuno

Hi,

Nuno Lopes wrote:
>> Okay; so the problem is that an instruction that is value-equivalent
>> to a poison value is not itself necessarily poison?
>
> Right.
> I think there were other examples, but I don't have them here handy.
But
> at least this one is very problematic for GVN.
Another example is this:

void f(int k) {
   if (k != 0) {
     for (< finite loop >) {
       if (always_false_at_runtime) {
         print(1 / k);
       }
     }
   }
}

We'd like to hoist the `1 / k` computation to the preheader.  However, 
we can't do that today if `k` is undef, and we've defined branching on 
undef to be a non-deterministic choice.

I have some more details at: 
http://www.playingwithpointers.com/problem-with-undef.html

-- Sanjoy

> On Oct 18, 2016, at 12:44 PM, Sanjoy Das via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hi,
> 
> Nuno Lopes wrote:
> 
>>> Okay; so the problem is that an instruction that is
value-equivalent
>>> to a poison value is not itself necessarily poison?
>> 
>> Right.
>> I think there were other examples, but I don't have them here
handy. But
>> at least this one is very problematic for GVN.
> 
> Another example is this:
> 
> void f(int k) {
>  if (k != 0) {
>    for (< finite loop >) {
>      if (always_false_at_runtime) {
>        print(1 / k);
>      }
>    }
>  }
> }
> 
> We'd like to hoist the `1 / k` computation to the preheader.  However,
we can't do that today if `k` is undef, and we've defined branching on
undef to be a non-deterministic choice.
This one isn’t clear to me: you can fold 1/k -> 1 when k is undef. And then
it is a constant which makes no point to hoist?

— 
Mehdi

> 
> I have some more details at:
http://www.playingwithpointers.com/problem-with-undef.html
> 
> -- Sanjoy
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev