[llvm-dev] Killing undef and spreading poison

[Nuno Lopes via llvm-dev]

>> >> 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