[LLVMdev] poison and select

[David Majnemer]

I believe Dan struck at the heart of the issue and the consequences have
just become apparent (at least to me).

Consider:
define i32 @f(i32 %a) {
  %cmp = icmp sgt i32 %a, 0
  %sub = sub nsw i32 2147483647, %a
  %sel = select i1 %cmp, i32 %sub, i32 0
  ret i32 %sel
}

If %a is -1, %sub will wrap and be poison. %cmp will be false.
Is %sel poison or not?  We have no definition for what select actually does.

If we assume select boils down to nothing but arithmetic, then %sel may be
poisoned by *any* of its operands.

If we assume select boils down to control flow (branch + PHI), then we are
violating the rules by which it operates in many places in LLVM.
Consider the following input:
%add = add nsw i32 %a, 1
%cmp1 = icmp eq i32 %a, 0
%cmp2 = icmp slt i32 %add, 0
%sel = select i1 %cmp1, i1 %cmp2, i1 false

We currently optimize this to:
%add = add nsw i32 %a, 1
%cmp1 = icmp eq i32 %a, 0
%cmp2 = icmp slt i32 %add, 0
%and = and i1 %cmp1, %cmp2

If %a is 2147483647: %add is poison, %cmp1 is false, %cmp2 is poison, %sel
is false but %and is poison!

The above transform is not an oddity, InstCombine does this sort of thing
*a lot*.

If select is arithmetic, many transforms are "correct" but we can form
select far less often than we thought we could.
If select is control flow, many transforms are "wrong" but we might be able
to form more selects.

What is select? How does it work? How should it work?

On Thu, Sep 18, 2014 at 7:45 PM, John Regehr <regehr at cs.utah.edu> wrote:

> Today I ran into another aspect of the poison problem...
>
> Basically, SimplifyCFG wants to take
>
>   expr1 && expr2
>
> and flatten it into
>
>   x = expr1
>   y = expr2
>   x&y
>
> This isn't safe when expr2 might execute UB.  The consequence is that no
> LLVM shift instruction is safe to speculatively execute, nor is any
> nsw/nuw/exact variant, unless the operands can be proven to be in bounds.
>
> Real example here:
>
>   http://llvm.org/bugs/show_bug.cgi?id=20997
>
>
> John
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140919/a18536ca/attachment.html>