<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:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@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;}
/* 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;}
span.EmailStyle17
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 90.0pt 72.0pt 90.0pt;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:799957587;
mso-list-type:hybrid;
mso-list-template-ids:-1214880770 44585902 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;}
@list l0:level1
{mso-level-start-at:0;
mso-level-number-format:bullet;
mso-level-text:-;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-font-family:"Times New Roman";}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";
mso-bidi-font-family:"Times New Roman";}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";
mso-bidi-font-family:"Times New Roman";}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";
mso-bidi-font-family:"Times New Roman";}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
--></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"><a name="_MailEndCompose"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">>
</span></a>It seems like we might we able to use TBAA metadata with struct field information to get this then.<o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">TBAA does not support struct fields yet.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">It shows what type will be stored, but does not have structure info.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal">> See also <a href="http://lists.llvm.org/pipermail/llvm-dev/2016-July/102472.html">
http://lists.llvm.org/pipermail/llvm-dev/2016-July/102472.html</a> .<o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#2F5597;mso-style-textfill-fill-color:#2F5597;mso-style-textfill-fill-alpha:100.0%">It’s not, probably, the case. I need such “inbounds” for any sub-structure.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<div>
<p class="MsoNormal" style="margin-left:36.0pt;text-indent:-18.0pt;mso-list:l0 level1 lfo1">
<![if !supportLists]><span style="font-family:"Calibri",sans-serif;color:#2F5496"><span style="mso-list:Ignore">-<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span dir="LTR"></span><b><i><span style="color:#2F5496"> Elena<o:p></o:p></span></i></b></p>
</div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><a name="_____replyseparator"></a><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"> Finkel, Hal J. [mailto:hfinkel@anl.gov]
<br>
<b>Sent:</b> Tuesday, July 26, 2016 02:03<br>
<b>To:</b> Eli Friedman <eli.friedman@gmail.com><br>
<b>Cc:</b> llvm-dev <llvm-dev@lists.llvm.org>; Demikhovsky, Elena <elena.demikhovsky@intel.com>; Richard Smith <richard-llvm@metafoo.co.uk><br>
<b>Subject:</b> Re: [llvm-dev] Alias Analysis with inbound GEPs<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal"><i><span style="color:#333333">Sent from my Verizon Wireless 4G LTE DROID</span></i><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">On Jul 25, 2016 6:10 PM, Eli Friedman <<a href="mailto:eli.friedman@gmail.com">eli.friedman@gmail.com</a>> wrote:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">> On Mon, Jul 25, 2016 at 2:06 PM, Hal Finkel via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>> ________________________________<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> From: "Elena Demikhovsky" <<a href="mailto:elena.demikhovsky@intel.com">elena.demikhovsky@intel.com</a>><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>> To: "Hal Finkel" <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>> Cc: "llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>> Sent: Monday, July 25, 2016 2:46:34 PM<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>> Subject: RE: [llvm-dev] Alias Analysis with inbound GEPs<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>>> I’m checking aliasing of two pointers:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>>> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>>> %GEP1 = getelementptr inbounds %struct.s, %struct.s* %0, i64 0, i32 1, i64 %indvars.iv41, i64 %indvars.iv39<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>>> %GEP2 = getelementptr inbounds %struct.s, %struct.s* %0, i64 0, i32 16<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>>> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>>> The result I got is “PartialAlias” because the indices of the GEP1 are variable.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> That seems like a bug. PartialAlias should only be returned when we can prove a partial overlap. Otherwise, MayAlias should be returned.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> [Demikhovsky, Elena] There are some comments inside:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> // Statically, we can see that the base objects are the same, but the<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> // pointers have dynamic offsets which we can't resolve. And none of our<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> // little tricks above worked.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> //<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> // TODO: Returning PartialAlias instead of MayAlias is a mild hack; the<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> // practical effect of this is protecting TBAA in the case of dynamic<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> // indices into arrays of unions or malloc'd memory.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> return PartialAlias;<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>> Ah, thanks! That, unfortunately, makes sense.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>>> Shouldn’t the “inbounds” keyword mean that the access to sub-array is also in-bounds?<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> No. inbounds applies only to the whole object.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>>> I’m trying to reach “NoAlias” consensus between GEP1 and GEP2.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> Did the original code come from C or C++? What are we modeling here?<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> [Demikhovsky, Elena] C-code:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> for (m=0; m < params->num; m++) {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> params->a[i][m] = expr;<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> }<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> %GEP1 is the store for params->a[i][m]<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> %GEP2 is the load for params->num.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> The loop is not vectorized due to a possible collision between params->num and params->a[i][m]. If I take loading of params->num outside the loop, it is vectorized.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>>> Bounds of array “a” are known at compile time. Limit of “i” and “m” are runtime variables.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">>> The problem is, IIRC, it is not undefined behavior to access one structure field by over-indexing an earlier array member. C++ has rules for "safely-derived pointers", and I think they include all pointer arithmetic on addresses from
subobjects. If array access is just pointer arithmetic, I'm not sure that helps you as much as you'd like. cc'ing Richard to correct me if necessary.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">>><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">> It is actually undefined behavior. This is explicitly called out in Annex J.2: "An array subscript is out of range, even if an object is apparently accessible with the given subscript (as in the lvalue expression a[1][7] given the declaration
int a[4][5]) ". If you break it apart into separate steps, the interesting bit is that the implicit array-to-pointer conversion is not equivalent to a cast; "int* b = (int*)a;" is not equivalent to "int* b = *a;", even though the expressions have the same
type and value.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">> There currently isn't any way to model the aliasing behavior of the address-of operator or array-to-pointer decay in LLVM IR. See also
<a href="http://lists.llvm.org/pipermail/llvm-dev/2016-July/102472.html">http://lists.llvm.org/pipermail/llvm-dev/2016-July/102472.html</a> .<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">It seems like we might we able to use TBAA metadata with struct field information to get this then.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">-Hal<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">> -Eli<o:p></o:p></p>
</div>
</div>
</div>
</div>
<p>---------------------------------------------------------------------<br>
Intel Israel (74) Limited</p>
<p>This e-mail and any attachments may contain confidential material for<br>
the sole use of the intended recipient(s). Any review or distribution<br>
by others is strictly prohibited. If you are not the intended<br>
recipient, please contact the sender and delete all copies.</p></body>
</html>