<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><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]--></head><body lang=EN-US link=blue vlink=purple><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><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>Thanks,<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>Nuno<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'><o:p> </o:p></span></p><p class=MsoNormal><b><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>From:</span></b><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'> Chandler Carruth [mailto:chandlerc@google.com] <br><b>Sent:</b> 4 de novembro de 2016 17:35<br><b>Subject:</b> Re: [llvm-dev] RFC: Killing undef and spreading poison<o:p></o:p></span></p><p class=MsoNormal><o:p> </o:p></p><div><div><div><p class=MsoNormal>On Wed, Oct 19, 2016 at 4:52 AM Nuno Lopes <<a href="mailto:nuno.lopes@ist.utl.pt">nuno.lopes@ist.utl.pt</a>> wrote:<o:p></o:p></p></div><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt'><p class=MsoNormal>> I'm still digesting the proposal in its entirety, but one point I want to call out here:<br>><br>>> On Tue, Oct 18, 2016 at 1:39 PM Friedman, Eli via llvm-dev wrote:<br>>> Instcombine currently transforms "memcpy(dst, src, 4)" to "load i32 src;<br>>> store i32 dst". I guess that's illegal under this model? How about the<br>>> related transform "memcpy(dst, src, 4)" to "load <4 x i8> src; store <4<br>>> x i8> dst"? (SROA also performs similar transforms.)<br>><br>> I think it is really important that memcpy and load/store pair be equivalent. If this is in fact true about the proposal, I would want to really dig into why and whether anything could be done to make them equivalent.<br><br>Memcpy does a byte-by-byte copy. So if one of the bits is poison then only the byte containing that bit becomes poison.<br>Therefore, memcpy(x, y, 1) is equivalent to load i8. But memcpy(x,y,4) is not equivalent to "load i32" since load makes the whole value poison if any of the bits is poison.<o:p></o:p></p></blockquote><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>That is not the semantic model that LLVM uses today. Your proposal is changing this, and it is an *incredibly* fundamental part of the optimizer.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>LLVM, very fundamentally, models an integer, a vector of bytes, and a vector of bits as absolutely identical to the underlying storage in memory. Changing this would completely break SROA, various parts of mem2reg and reg2mem, and all load widening.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>I understand you have reasons here, but this is a much bigger change than the undef vs. poison part. ;] I'm currently deeply concerned by this change and would strongly prefer looking at alternatives.<o:p></o:p></p></div><div><p class=MsoNormal> <o:p></o:p></p></div><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt'><p class=MsoNormal>The alternative as given by Eli is to use "load <4 x i8>". Since now we are loading 4 separate values, poison does not extend past the byte boundary. When load is lowered, you should get exactly the same code as with "load i32", though.<br>So the hope is that there's no diff at assembly level.<o:p></o:p></p></blockquote><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>Note that vectors in LLVM are both quite limited and will have likely very different representations in the assembly.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>You're essentially conferring a *type* onto *memory*. That is not currently LLVM's model. Instead, the types in LLVM are tied to *operations*.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>As a consequence, when LLVM sees a vector type, it canonicalizes, optimizes, and code generates to facilitate vector operations on values of vector type. So for example, a vector of 32 i1s is likely to be put into a vector mask register.<o:p></o:p></p></div></div></div></div></body></html>