[LLVMdev] poison and select

[Reid Kleckner]

I think the simpler way of phrasing 1 is: "poison has the same propagation
rules as undef". This means that poison is a property of bits, not of
values, and basic arithmetic like 'and 0', 'or 1', and 'mul 0' can mask it
away. This makes a CFG diamond equivalent to a select and select equivalent
to arithmetic, which seems like general goodness. I wonder if we lose
optimization power around these kinds of masking arithmetic instructions,
though.

On Sun, Nov 23, 2014 at 2:16 PM, David Majnemer <david.majnemer at gmail.com>
wrote:

> I think that there are fundamentally two different solutions to the
> select-poison issue with their own pros and cons:
>
> Either:
>
> We allow instructions to not care about poison operands because their
> output will not contain any information tainted by the poison.  This would
> mean that select is allowed to ignore a poisoned operand if it doesn't
> select it.  It would also mean that a poison condition value guarantees
> that you get *one* of the two operands *but* that the select instruction
> itself has been poisoned.
>
> AFAICT, this doesn't lose out on any optimizations.
>
>
> Or:
>
> We introduce a 'vile' attribute to the select instruction.  A 'vile'
> select is poison even if the operand which wasn't selected if poison while
> 'normal' selects behave more like br/phi instructions.
>
> This is a more conservative and, IMO, uglier approach which is sound but
> would require auditing LLVM to make sure that it only transforms 'vile'
> selects into arithmetic.  I think it would be very hard to optimize a
> normal select into a 'vile' select which would mean that we might lose out
> on some optimizations.
>
>
> If there is a reason we shouldn't go with approach #1?  I can't
> immediately come up with IR that we would stop optimizing.
>
> On Sun, Nov 23, 2014 at 12:03 AM, Sanjoy Das <
> sanjoy at playingwithpointers.com> wrote:
>
>> Hi,
>>
>> > Does this make any sense at all?  Have there been past attempts at
>> > formalizing poison along these lines?
>>
>> Answering my own question, what I was considering is a slight variant
>> of the scheme mentioned in an earlier email by Dan:
>> http://lists.cs.uiuc.edu/pipermail/llvmdev/2011-November/045730.html
>>
>> "
>>  - Instead of trying to define dependence in LangRef, just say that if
>>    changing the value returned from an overflowing add nsw would
>>    affect the observable behavior of the program, then the behavior of
>>    the program is undefined. This would reduce the amount of text in
>>    LangRef, but it would be a weaker definition, and it would require
>>    sign-extension optimizers and others to do significantly more work
>>    to establish that their transformations are safe.
>> "
>>
>> That said, this scheme does not work as expected -- the bitness of the
>> result of an overflowing add prevents some optimizations:
>>
>>  %a = add nsw i32 %v, 1
>>  %c = icmp slt i32 %v, %a
>>  store %c, < global variable >
>>
>> In the case of signed overflow, %v is INT32_MAX.  For all values of
>> %a, the observable behavior of the program is the same (we store false
>> to < global variable > for all values of %a); and so we cannot exploit
>> undefined behavior and simplify '%c' to true.
>>
>> Similar issues arise if you, for example, zero extend a poison value,
>> and then right shift out all the "poison bits" -- the resulting value
>> is all zeroes and do not capture overflowing semantics.
>>
>> Thanks,
>> -- Sanjoy
>>
>
>
> _______________________________________________
> 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/20141124/352c0f81/attachment.html>