<div dir="ltr">On Mon, Jul 25, 2016 at 2:06 PM, Hal Finkel via llvm-dev <span dir="ltr"><<a target="_blank" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:rgb(0,0,0)"><br><hr><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"><b>From: </b>"Elena Demikhovsky" <<a target="_blank" href="mailto:elena.demikhovsky@intel.com">elena.demikhovsky@intel.com</a>><br><b>To: </b>"Hal Finkel" <<a target="_blank" href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>><br><b>Cc: </b>"llvm-dev" <<a target="_blank" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><br><b>Sent: </b>Monday, July 25, 2016 2:46:34 PM<br><b>Subject: </b>RE: [llvm-dev] Alias Analysis with inbound GEPs<span><br><br>
<div>
<p><a name="m_1680342593794024819_m_-5987039856553261346_m_-2933703288019341856__MailEndCompose"><span style="font-size:11pt;font-family:"calibri",sans-serif;color:rgb(31,73,125)"> </span></a></p>
<div style="border-width:medium medium medium 1.5pt;border-style:none none none solid;border-color:-moz-use-text-color -moz-use-text-color -moz-use-text-color blue;padding:0cm 0cm 0cm 4pt">
<div>
<blockquote style="border-width:medium medium medium 1.5pt;border-style:none none none solid;border-color:-moz-use-text-color -moz-use-text-color -moz-use-text-color rgb(16,16,255);padding:0cm 0cm 0cm 4pt;margin-left:3.75pt;margin-top:5pt;margin-bottom:5pt">
<div>
<p><span style="font-size:11pt;font-family:"calibri",sans-serif;color:black">I’m checking aliasing of two pointers:</span></p>
</div>
<div>
<p><span style="font-size:11pt;font-family:"calibri",sans-serif;color:black"> </span></p>
</div>
<div>
<p><span style="font-size:11pt;font-family:"calibri",sans-serif;color:black"> %GEP1 = getelementptr inbounds %struct.s, %struct.s* %0, i64 0, i32 1, i64 %indvars.iv41, i64 %indvars.iv39</span></p>
</div>
<div>
<p><span style="font-size:11pt;font-family:"calibri",sans-serif;color:black"> %GEP2 = getelementptr inbounds %struct.s, %struct.s* %0, i64 0, i32 16</span></p>
</div>
<div>
<p><span style="font-size:11pt;font-family:"calibri",sans-serif;color:black"> </span></p>
</div>
<div>
<p><span style="font-size:11pt;font-family:"calibri",sans-serif;color:black">The result I got is “PartialAlias” because the indices of the GEP1 are variable.</span></p>
</div>
</blockquote>
<p><span style="font-size:10pt;font-family:"arial",sans-serif;color:black">That seems like a bug. PartialAlias should only be returned when we can prove a partial overlap. Otherwise, MayAlias should be returned.</span></p>
<p><b><i><span style="font-size:11pt;font-family:"calibri",sans-serif;color:rgb(31,73,125)">[Demikhovsky, Elena] There are some comments inside:</span></i></b></p>
<p><span style="font-size:11pt;font-family:consolas;color:black;background:white none repeat scroll 0% 0%">
</span><span style="font-size:11pt;font-family:consolas;color:green;background:white none repeat scroll 0% 0%">// Statically, we can see that the base objects are the same, but the</span><span style="font-size:11pt;font-family:consolas;color:black;background:white none repeat scroll 0% 0%"></span></p>
<p><span style="font-size:11pt;font-family:consolas;color:black;background:white none repeat scroll 0% 0%">
</span><span style="font-size:11pt;font-family:consolas;color:green;background:white none repeat scroll 0% 0%">// pointers have dynamic offsets which we can't resolve. And none of our</span><span style="font-size:11pt;font-family:consolas;color:black;background:white none repeat scroll 0% 0%"></span></p>
<p><span style="font-size:11pt;font-family:consolas;color:black;background:white none repeat scroll 0% 0%">
</span><span style="font-size:11pt;font-family:consolas;color:green;background:white none repeat scroll 0% 0%">// little tricks above worked.</span><span style="font-size:11pt;font-family:consolas;color:black;background:white none repeat scroll 0% 0%"></span></p>
<p><span style="font-size:11pt;font-family:consolas;color:black;background:white none repeat scroll 0% 0%">
</span><span style="font-size:11pt;font-family:consolas;color:green;background:white none repeat scroll 0% 0%">//</span><span style="font-size:11pt;font-family:consolas;color:black;background:white none repeat scroll 0% 0%"></span></p>
<p><span style="font-size:11pt;font-family:consolas;color:black;background:white none repeat scroll 0% 0%">
</span><span style="font-size:11pt;font-family:consolas;color:green;background:white none repeat scroll 0% 0%">// TODO: Returning PartialAlias instead of MayAlias is a mild hack; the</span><span style="font-size:11pt;font-family:consolas;color:black;background:white none repeat scroll 0% 0%"></span></p>
<p><span style="font-size:11pt;font-family:consolas;color:black;background:white none repeat scroll 0% 0%">
</span><span style="font-size:11pt;font-family:consolas;color:green;background:white none repeat scroll 0% 0%">// practical effect of this is protecting TBAA in the case of dynamic</span><span style="font-size:11pt;font-family:consolas;color:black;background:white none repeat scroll 0% 0%"></span></p>
<p><span style="font-size:11pt;font-family:consolas;color:black;background:white none repeat scroll 0% 0%"> </span><span style="font-size:11pt;font-family:consolas;color:green;background:white none repeat scroll 0% 0%">//
indices into arrays of unions or malloc'd memory.</span><span style="font-size:11pt;font-family:consolas;color:black;background:white none repeat scroll 0% 0%"></span></p>
<p><span style="font-size:11pt;font-family:consolas;color:black;background:white none repeat scroll 0% 0%">
</span><span style="font-size:11pt;font-family:consolas;color:blue;background:white none repeat scroll 0% 0%">return</span><span style="font-size:11pt;font-family:consolas;color:black;background:white none repeat scroll 0% 0%">
</span><span style="font-size:11pt;font-family:consolas;color:darkslategray;background:white none repeat scroll 0% 0%">PartialAlias</span><span style="font-size:11pt;font-family:consolas;color:black;background:white none repeat scroll 0% 0%">;</span></p></div></div></div></span></blockquote>Ah, thanks! That, unfortunately, makes sense.<span><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"><div><div style="border-width:medium medium medium 1.5pt;border-style:none none none solid;border-color:-moz-use-text-color -moz-use-text-color -moz-use-text-color blue;padding:0cm 0cm 0cm 4pt"><div><p><span style="font-size:11pt;font-family:consolas;color:black;background:white none repeat scroll 0% 0%"></span></p>
<p><span style="font-size:11pt;font-family:"calibri",sans-serif;color:rgb(31,73,125)"> </span></p>
<blockquote style="border-width:medium medium medium 1.5pt;border-style:none none none solid;border-color:-moz-use-text-color -moz-use-text-color -moz-use-text-color rgb(16,16,255);padding:0cm 0cm 0cm 4pt;margin-left:3.75pt;margin-top:5pt;margin-bottom:5pt">
<div>
<p><span style="font-size:11pt;font-family:"calibri",sans-serif;color:black">Shouldn’t the “inbounds” keyword mean that the access to sub-array is also in-bounds?</span></p>
</div>
</blockquote>
<p><span style="font-size:10pt;font-family:"arial",sans-serif;color:black">No. inbounds applies only to the whole object.</span></p>
<blockquote style="border-width:medium medium medium 1.5pt;border-style:none none none solid;border-color:-moz-use-text-color -moz-use-text-color -moz-use-text-color rgb(16,16,255);padding:0cm 0cm 0cm 4pt;margin-left:3.75pt;margin-top:5pt;margin-bottom:5pt">
<div>
<p><span style="font-size:11pt;font-family:"calibri",sans-serif;color:black">I’m trying to reach “NoAlias” consensus between GEP1 and GEP2.</span></p>
</div>
</blockquote>
<p><span style="font-size:10pt;font-family:"arial",sans-serif;color:black">Did the original code come from C or C++? What are we modeling here?</span><span style="font-size:10pt;font-family:"arial",sans-serif;color:rgb(31,73,125)"></span></p>
<p><b><i><span style="font-size:11pt;font-family:"calibri",sans-serif;color:rgb(31,73,125)">[Demikhovsky, Elena] C-code:</span></i></b></p>
<p style="margin-left:5.25pt"><b><i><span style="font-size:11pt;font-family:"calibri",sans-serif;color:rgb(31,73,125)"> for (m=0; m < params->num; m++) {</span></i></b></p>
<p style="margin-left:5.25pt"><b><i><span style="font-size:11pt;font-family:"calibri",sans-serif;color:rgb(31,73,125)"> params->a[i][m] = expr;</span></i></b></p>
<p><b><i><span style="font-size:11pt;font-family:"calibri",sans-serif;color:rgb(31,73,125)"> }</span></i></b></p>
<p><b><i><span style="font-size:11pt;font-family:"calibri",sans-serif;color:rgb(31,73,125)">%GEP1 is the store for params->a[i][m]</span></i></b></p>
<p><b><i><span style="font-size:11pt;font-family:"calibri",sans-serif;color:rgb(31,73,125)">%GEP2 is the load for params->num.</span></i></b></p>
<p><b><i><span style="font-size:11pt;font-family:"calibri",sans-serif;color:rgb(31,73,125)">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.</span></i></b></p>
<p><b><i><span style="font-size:11pt;font-family:"calibri",sans-serif;color:rgb(31,73,125)">Bounds of array “a” are known at compile time. Limit of “i” and “m” are runtime variables.</span></i></b></p></div></div></div></blockquote></span>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.<br></div></div><br></blockquote><div><br></div><div>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.<br><br></div>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> .<br></div><br></div><div class="gmail_extra">-Eli<br></div></div>