<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'><br><br><hr id="zwchr"><blockquote id="DWT38772" style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><b>From: </b>"Eli via llvm-dev Friedman" <llvm-dev@lists.llvm.org><br><b>To: </b>"Nuno Lopes" <nuno.lopes@ist.utl.pt>, "Chandler Carruth" <chandlerc@google.com>, llvm-dev@lists.llvm.org<br><b>Cc: </b>"John Regehr" <regehr@cs.utah.edu>, "Yoonseung Kim" <yoonseung.kim@sf.snu.ac.kr>, "Youngju Song" <youngju.song@sf.snu.ac.kr><br><b>Sent: </b>Tuesday, November 8, 2016 2:48:04 PM<br><b>Subject: </b>Re: [llvm-dev] RFC: Killing undef and spreading poison<br><br>
<div class="moz-cite-prefix">On 11/8/2016 10:47 AM, Nuno Lopes
wrote:<br>
</div>
<blockquote cite="mid:003c01d239f0$9126f770$b374e650$@ist.utl.pt">
<style><!--
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
@font-face
{font-family:"Lucida Console";
panose-1:2 11 6 9 4 5 4 2 2 4;}
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0cm;
mso-margin-bottom-alt:auto;
margin-left:0cm;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
--></style>
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif;">Hi
Chandler,</span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif;"> </span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif;">Thanks
for your feedback!</span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif;">I</span><span style="font-size: 11pt;">’</span><span style="font-size: 11pt; font-family: "Calibri",sans-serif;">m
still trying to get to the bottom of your concerns and how
to best address them.</span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif;"> </span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif;">As
far as I understand, your main concern is that the following
should be equivalent to a no-op (thanks Sanjoy for the
example!):</span></p>
<p class="MsoNormal"><span style="font-size: 10pt; font-family: Consolas;">i32* ptr = ...</span></p>
<p class="MsoNormal"><span style="font-size: 10pt; font-family: Consolas;">%tmp = load
i32, i32* %ptr</span></p>
<p class="MsoNormal"><span style="font-size: 10pt; font-family: Consolas;">store i32
%tmp, i32* %ptr</span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif;"> </span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif;">So
introducing a store of the loaded value should be ok, but
under our proposal it</span><span style="font-size: 11pt;">’</span><span style="font-size: 11pt; font-family: "Calibri",sans-serif;">s
not. Just to clarify: is this actually your main concern?</span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif;"> </span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif;">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:</span></p>
<p class="MsoNormal"><span style="font-size: 10pt; font-family: Consolas;">define i16
@g(i8 %in) {</span></p>
<p class="MsoNormal"><span style="font-size: 10pt; font-family: Consolas;"> %a = alloca
i32</span></p>
<p class="MsoNormal"><span style="font-size: 10pt; font-family: Consolas;"> %v = add nsw
i8 127, %in</span></p>
<p class="MsoNormal"><span style="font-size: 10pt; font-family: Consolas;"> %ptr =
bitcast i32* %a to i8*</span></p>
<p class="MsoNormal"><span style="font-size: 10pt; font-family: Consolas;"> %ptr1 =
getelementptr i8, i8* %ptr, i32 1</span></p>
<p class="MsoNormal"><span style="font-size: 10pt; font-family: Consolas;"> store i8 %v,
i8* %ptr1</span></p>
<p class="MsoNormal"><span style="font-size: 10pt; font-family: Consolas;"> %ptr16 =
bitcast i32* %a to i16*</span></p>
<p class="MsoNormal"><span style="font-size: 10pt; font-family: Consolas;"> %load = load
i16, i16* %ptr16</span></p>
<p class="MsoNormal"><span style="font-size: 10pt; font-family: Consolas;"> ret i16
%load</span></p>
<p class="MsoNormal"><span style="font-size: 10pt; font-family: Consolas;">}</span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif;"> </span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif;">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:</span></p>
<p class="MsoNormal" style=""><span style="font-size: 10pt; font-family: Consolas;">define i16
@g(i8 %in) {</span></p>
<p class="MsoNormal" style=""><span style="font-size: 10pt; font-family: Consolas;"> %v = add nsw
i8 127, %in</span></p>
<p class="MsoNormal" style=""><span style="font-size: 10pt; font-family: Consolas;"> %1 = zext i8
%v to i16</span></p>
<p class="MsoNormal" style=""><span style="font-size: 10pt; font-family: Consolas;"> %2 = shl i16
%1, 8</span></p>
<p class="MsoNormal" style=""><span style="font-size: 10pt; font-family: Consolas;"> %3 = and i16
undef, 255</span></p>
<p class="MsoNormal" style=""><span style="font-size: 10pt; font-family: Consolas;"> %4 = or i16
%3, %2</span></p>
<p class="MsoNormal" style=""><span style="font-size: 10pt; font-family: Consolas;"> ret i16 %4</span></p>
<p class="MsoNormal"><span style="font-size: 10pt; font-family: Consolas;">}</span><span style="font-family: Consolas;"></span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif;"> </span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif;">SROA
gets rid of the alloca/store/load instructions and replaces
those with an OR of undef and shifted %v.</span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif;">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 </span><span style="font-size: 11pt;">“</span><span style="font-size: 11pt; font-family: "Calibri",sans-serif;">ret
i16 poison</span><span style="font-size: 11pt;">”</span><span style="font-size: 11pt; font-family: "Calibri",sans-serif;">
(if we had a poison value in IR, or otherwise fold to </span><span style="font-size: 11pt;">“</span><span style="font-size: 11pt; font-family: "Calibri",sans-serif;">add
nsw i16 INT_MAX, 1</span><span style="font-size: 11pt;">”</span><span style="font-size: 11pt; font-family: "Calibri",sans-serif;">).</span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif;">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.</span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif;"> </span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif;">Please
let me know what you think. I may be missing some important
detail.</span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif;"> </span></p>
</div>
</blockquote>
<br>
Well, I wouldn't pay too much attention to what LangRef currently
says about poison, considering that the current model isn't actually
consistent.<br>
<br>
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.<br>
<br>
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.<br>
<br>
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.<br></blockquote>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.<br><br> -Hal<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;">
<br>
-Eli<br>
<pre class="moz-signature">-- <br>Employee of Qualcomm Innovation Center, Inc.<br>Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project</pre>
<br>_______________________________________________<br>LLVM Developers mailing list<br>llvm-dev@lists.llvm.org<br>http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br></blockquote><br><br><br>-- <br><div><span name="x"></span>Hal Finkel<br>Lead, Compiler Technology and Programming Languages<br>Leadership Computing Facility<br>Argonne National Laboratory<span name="x"></span><br></div></div></body></html>