[llvm-dev] RFC: Killing undef and spreading poison

[Nuno Lopes via llvm-dev]

>> A use of freeze is to enable speculative execution.  For example, loop 
>> switching does the following transformation:
>> while (C) {
>>   if (C2) {
>>    A
>>   } else {
>>    B
>>   }
>> }
>> =>
>> if (C2) {
>>    while (C)
>>       A
>> } else {
>>     while (C)
>>        B
>> }
>> 
>> 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.  If %poison is indeed poison, then the transformation is wrong because before it was passing an ok value to bar() and after the transformation it is passing poison.
On the other hand, if branching on poison is UB, the original program was executing UB already because %poison (and therefore %c) were poison. So the transformation is ok.


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

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.
Poison is lowered into undef. And freeze is lowered into this pair of copy nodes that seems to stop propagation of undef (to ensure all uses see the same value).  I don't know enough about MI to know if there's a better way to lower freeze, though.

Thanks,
Nuno