<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<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"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered
medium)">
<style><!--
/* Font Definitions */
@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;}
/* Style Definitions */
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><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
<div class="WordSection1">
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif">Hi
Chandler,<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif">Thanks
for your feedback!<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif">I</span><span
style="font-size:11.0pt">’</span><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif">m
still trying to get to the bottom of your concerns and how
to best address them.<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;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!):<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:10.0pt;font-family:Consolas">i32* ptr = ...<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:10.0pt;font-family:Consolas">%tmp = load
i32, i32* %ptr<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:10.0pt;font-family:Consolas">store i32
%tmp, i32* %ptr<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;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:11.0pt">’</span><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif">s
not. Just to clarify: is this actually your main concern?<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;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:<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:10.0pt;font-family:Consolas">define i16
@g(i8 %in) {<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:10.0pt;font-family:Consolas"> %a = alloca
i32<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:10.0pt;font-family:Consolas"> %v = add nsw
i8 127, %in<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:10.0pt;font-family:Consolas"> %ptr =
bitcast i32* %a to i8*<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:10.0pt;font-family:Consolas"> %ptr1 =
getelementptr i8, i8* %ptr, i32 1<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:10.0pt;font-family:Consolas"> store i8 %v,
i8* %ptr1<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:10.0pt;font-family:Consolas"> %ptr16 =
bitcast i32* %a to i16*<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:10.0pt;font-family:Consolas"> %load = load
i16, i16* %ptr16<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:10.0pt;font-family:Consolas"> ret i16
%load<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:10.0pt;font-family:Consolas">}<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;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:<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span
style="font-size:10.0pt;font-family:Consolas">define i16
@g(i8 %in) {<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span
style="font-size:10.0pt;font-family:Consolas"> %v = add nsw
i8 127, %in<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span
style="font-size:10.0pt;font-family:Consolas"> %1 = zext i8
%v to i16<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span
style="font-size:10.0pt;font-family:Consolas"> %2 = shl i16
%1, 8<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span
style="font-size:10.0pt;font-family:Consolas"> %3 = and i16
undef, 255<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span
style="font-size:10.0pt;font-family:Consolas"> %4 = or i16
%3, %2<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span
style="font-size:10.0pt;font-family:Consolas"> ret i16 %4<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:10.0pt;font-family:Consolas">}</span><span
style="font-family:Consolas"><o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;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.<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;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:11.0pt">“</span><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif">ret
i16 poison</span><span style="font-size:11.0pt">”</span><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif">
(if we had a poison value in IR, or otherwise fold to </span><span
style="font-size:11.0pt">“</span><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif">add
nsw i16 INT_MAX, 1</span><span style="font-size:11.0pt">”</span><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif">).<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;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.<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif">Please
let me know what you think. I may be missing some important
detail.<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p> </o:p></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>
<br>
-Eli<br>
<pre class="moz-signature" cols="72">--
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project</pre>
</body>
</html>