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

[Friedman, Eli via llvm-dev]

On 11/8/2016 10:47 AM, Nuno Lopes wrote:
>
> Hi Chandler,
>
> Thanks for your feedback!
>
> I’m still trying to get to the bottom of your concerns and how to best 
> address them.
>
> As far as I understand, your main concern is that the following should 
> be equivalent to a no-op (thanks Sanjoy for the example!):
>
> i32* ptr = ...
>
> %tmp = load i32, i32* %ptr
>
> store i32 %tmp, i32* %ptr
>
> So introducing a store of the loaded value should be ok, but under our 
> proposal it’s not.  Just to clarify: is this actually your main concern?
>
> I believe many parts of LLVM already interpret poison as a per-value 
> attribute, including when it comes to loads.  Take the following 
> function as an example:
>
> define i16 @g(i8 %in) {
>
>   %a = alloca i32
>
>   %v = add nsw i8 127, %in
>
>   %ptr = bitcast i32* %a to i8*
>
>   %ptr1 = getelementptr i8, i8* %ptr, i32 1
>
>   store i8 %v, i8* %ptr1
>
>   %ptr16 = bitcast i32* %a to i16*
>
>   %load = load i16, i16* %ptr16
>
>   ret i16 %load
>
> }
>
> This program stores 8 bits, and leaves the remaining 24 bits 
> uninitialized. It then loads 16 bits, half initialized to %v, half 
> uninitialized. SROA transforms the above function to:
>
> define i16 @g(i8 %in) {
>
>   %v = add nsw i8 127, %in
>
>   %1 = zext i8 %v to i16
>
>   %2 = shl i16 %1, 8
>
>   %3 = and i16 undef, 255
>
>   %4 = or i16 %3, %2
>
>   ret i16 %4
>
> }
>
> SROA gets rid of the alloca/store/load instructions and replaces those 
> with an OR of undef and shifted %v.
>
> If I call g() with %in=1, then the addition overflows and %v is 
> poison.  Under LLVM semantics, all instructions return poison if given 
> poison as input. Therefore the whole function can be folded to “ret 
> i16 poison”(if we had a poison value in IR, or otherwise fold to “add 
> nsw i16 INT_MAX, 1”).
>
> So, to justify the correctness of SROA, the load in the original 
> program had to be widening the poison from the stored i8 value and 
> return a i16 poison (i.e., %load had to be poison if %v was poison).  
> Therefore, we can conclude that in current semantics, loads already 
> widen poison from bit-representation into value-wise representation, 
> which makes the insertion of a load-store round-trip illegal in general.
>
> Please let me know what you think. I may be missing some important detail.
>

Well, I wouldn't pay too much attention to what LangRef currently says 
about poison, considering that the current model isn't actually consistent.

It's possible we could tweak your model a little to make poison a 
bit-wise property, so an i32 can be partially poison, sort of like how 
undef currently works.  Then we can consider on an operation by 
operation basis how it propagates poison bits.  In other words, let's 
pretend every Value has type <n x i1> for the purpose of poison until we 
actually do math on it.

Under this model, we can say a non-vector icmp with any poisoned bit as 
input returns poison, but a load produces a value whose bits are poison 
only where the input is poison.  We can say "freeze(load i32)" does the 
same thing as "bitcast(freeze(load <32 x i1>) to i32)".  We can define 
lshr and trunc to allow merging two i8 loads into an i16 load.  Not sure 
what the rules for arithmetic and logic operations would be off the top 
of my head; there are some tradeoffs here.

I'm not sure this is the right approach (this model is more complicated, 
and we probably lose a bit of optimization power in some cases), but 
it's definitely nicer from the perspective of SROA and GVN.

-Eli

-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20161108/9d3a237a/attachment.html>