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

[Hal Finkel via llvm-dev]

----- Original Message -----

> From: "Eli via llvm-dev Friedman" <llvm-dev at lists.llvm.org>
> To: "Nuno Lopes" <nuno.lopes at ist.utl.pt>, "Chandler Carruth"
> <chandlerc at google.com>, llvm-dev at lists.llvm.org
> Cc: "John Regehr" <regehr at cs.utah.edu>, "Yoonseung Kim"
> <yoonseung.kim at sf.snu.ac.kr>, "Youngju Song"
> <youngju.song at sf.snu.ac.kr>
> Sent: Tuesday, November 8, 2016 2:48:04 PM
> Subject: Re: [llvm-dev] RFC: Killing undef and spreading poison

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

I agree. I think that we need a bitwise model for tracking poison/undef. The bitwise operations will propagate it bitwise, same for memory accesses, and the other operations can (be assumed to) propagate it to all bits. 

-Hal 

> -Eli
> --
> Employee of Qualcomm Innovation Center, Inc.
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a
> Linux Foundation Collaborative Project
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-- 

Hal Finkel 
Lead, Compiler Technology and Programming Languages 
Leadership Computing Facility 
Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20161108/b3ba8603/attachment.html>