<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><hr id="zwchr"><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" <elena.demikhovsky@intel.com><br><b>To: </b>"Hal Finkel" <hfinkel@anl.gov><br><b>Cc: </b>"llvm-dev" <llvm-dev@lists.llvm.org><br><b>Sent: </b>Monday, July 25, 2016 2:46:34 PM<br><b>Subject: </b>RE: [llvm-dev] Alias Analysis with inbound GEPs<br><br>
<style><!--
@font-face
{font-family:Helvetica;
panose-1:2 11 6 4 2 2 2 2 2 4;}
@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;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 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:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
p
{mso-style-priority:99;
margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
p.emailquote, li.emailquote, div.emailquote
{mso-style-name:emailquote;
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:1.0pt;
margin-bottom:.0001pt;
border:none;
padding:0cm;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
span.EmailStyle19
{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 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;}
@list l1
{mso-list-id:1972514770;
mso-list-template-ids:-1333129978;}
@list l1:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:"Courier New";
mso-bidi-font-family:"Times New Roman";}
@list l1:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
--></style>
<div class="WordSection1">
<p class="MsoNormal"><a name="_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 class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif; color: black;">I’m checking aliasing of two pointers:</span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif; color: black;"> </span></p>
</div>
<div>
<p class="MsoNormal"><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 class="MsoNormal"><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 class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif; color: black;"> </span></p>
</div>
<div id="DWT16163">
<p class="MsoNormal"><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 class="MsoNormal"><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 class="MsoNormal"><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 class="MsoNormal" style=""><span style="font-size: 11pt; font-family: Consolas; color: black; background: none repeat scroll 0% 0% white;">
</span><span style="font-size: 11pt; font-family: Consolas; color: green; background: none repeat scroll 0% 0% white;">// 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: none repeat scroll 0% 0% white;"></span></p>
<p class="MsoNormal" style=""><span style="font-size: 11pt; font-family: Consolas; color: black; background: none repeat scroll 0% 0% white;">
</span><span style="font-size: 11pt; font-family: Consolas; color: green; background: none repeat scroll 0% 0% white;">// 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: none repeat scroll 0% 0% white;"></span></p>
<p class="MsoNormal" style=""><span style="font-size: 11pt; font-family: Consolas; color: black; background: none repeat scroll 0% 0% white;">
</span><span style="font-size: 11pt; font-family: Consolas; color: green; background: none repeat scroll 0% 0% white;">// little tricks above worked.</span><span style="font-size: 11pt; font-family: Consolas; color: black; background: none repeat scroll 0% 0% white;"></span></p>
<p class="MsoNormal" style=""><span style="font-size: 11pt; font-family: Consolas; color: black; background: none repeat scroll 0% 0% white;">
</span><span style="font-size: 11pt; font-family: Consolas; color: green; background: none repeat scroll 0% 0% white;">//</span><span style="font-size: 11pt; font-family: Consolas; color: black; background: none repeat scroll 0% 0% white;"></span></p>
<p class="MsoNormal" style=""><span style="font-size: 11pt; font-family: Consolas; color: black; background: none repeat scroll 0% 0% white;">
</span><span style="font-size: 11pt; font-family: Consolas; color: green; background: none repeat scroll 0% 0% white;">// TODO: Returning PartialAlias instead of MayAlias is a mild hack; the</span><span style="font-size: 11pt; font-family: Consolas; color: black; background: none repeat scroll 0% 0% white;"></span></p>
<p class="MsoNormal" style=""><span style="font-size: 11pt; font-family: Consolas; color: black; background: none repeat scroll 0% 0% white;">
</span><span style="font-size: 11pt; font-family: Consolas; color: green; background: none repeat scroll 0% 0% white;">// practical effect of this is protecting TBAA in the case of dynamic</span><span style="font-size: 11pt; font-family: Consolas; color: black; background: none repeat scroll 0% 0% white;"></span></p>
<p class="MsoNormal" style=""><span style="font-size: 11pt; font-family: Consolas; color: black; background: none repeat scroll 0% 0% white;"> </span><span style="font-size: 11pt; font-family: Consolas; color: green; background: none repeat scroll 0% 0% white;">//
indices into arrays of unions or malloc'd memory.</span><span style="font-size: 11pt; font-family: Consolas; color: black; background: none repeat scroll 0% 0% white;"></span></p>
<p class="MsoNormal" style=""><span style="font-size: 11pt; font-family: Consolas; color: black; background: none repeat scroll 0% 0% white;">
</span><span style="font-size: 11pt; font-family: Consolas; color: blue; background: none repeat scroll 0% 0% white;">return</span><span style="font-size: 11pt; font-family: Consolas; color: black; background: none repeat scroll 0% 0% white;">
</span><span style="font-size: 11pt; font-family: Consolas; color: darkslategray; background: none repeat scroll 0% 0% white;">PartialAlias</span><span id="DWT27277" style="font-size: 11pt; font-family: Consolas; color: black; background: none repeat scroll 0% 0% white;">;</span></p></div></div></div></blockquote>Ah, thanks! That, unfortunately, makes sense.<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 class="WordSection1"><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 class="MsoNormal" style=""><span style="font-size: 11pt; font-family: Consolas; color: black; background: none repeat scroll 0% 0% white;"></span></p>
<p class="MsoNormal"><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 id="DWT16164">
<p class="MsoNormal"><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 class="MsoNormal"><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 id="DWT16165">
<p class="MsoNormal"><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 class="MsoNormal"><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 class="MsoNormal"><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 class="MsoNormal" 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 class="MsoNormal" 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 class="MsoNormal"><b><i><span style="font-size: 11pt; font-family: "Calibri",sans-serif; color: rgb(31, 73, 125);"> }</span></i></b></p>
<p class="MsoNormal"><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 class="MsoNormal"><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 class="MsoNormal"><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 class="MsoNormal"><b><i><span id="DWT27278" 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>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><br>Out of curiosity, does SCEVAA get this if you add it to the pipeline before the vectorizer?<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;"><div class="WordSection1"><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 class="MsoNormal"><b><i><span style="font-size: 11pt; font-family: "Calibri",sans-serif; color: rgb(31, 73, 125);"></span></i></b></p>
<p class="MsoNormal"><span style="font-size: 10pt; font-family: "Arial",sans-serif; color: black;"><br>
<br>
-Hal</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 class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif; color: black;"> </span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif; color: black;">Thanks.</span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif; color: black;"> </span></p>
</div>
<p class="MsoNormal" style="margin-left: 0cm; text-indent: -18pt;">
<span style="font-size: 10pt; font-family: Symbol; color: rgb(47, 84, 150);"><span style="">·<span style="font: 7pt "Times New Roman";">
</span></span></span><span dir="LTR"></span><b><i><span style="color: rgb(47, 84, 150);">Elena</span></i></b><span style="color: rgb(47, 84, 150);"></span></p>
<div>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif; color: black;"> </span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif; color: black;"> </span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: "Calibri",sans-serif; color: black;"> </span></p>
</div>
<p><span style="font-family: "Helvetica",sans-serif; color: black;">---------------------------------------------------------------------<br>
Intel Israel (74) Limited</span></p>
<p><span style="font-family: "Helvetica",sans-serif; color: black;">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.</span></p>
<p class="MsoNormal"><span style="font-family: "Helvetica",sans-serif; color: black;"><br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a></span></p>
</blockquote>
<p class="MsoNormal"><span style="font-size: 10pt; font-family: "Arial",sans-serif; color: black;"><br>
<br>
<br>
-- </span></p>
<div>
<p class="MsoNormal"><span style="font-size: 10pt; font-family: "Arial",sans-serif; color: black;">Hal Finkel<br>
Assistant Computational Scientist<br>
Leadership Computing Facility<br>
Argonne National Laboratory</span></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></blockquote><br><br><br>-- <br><div><span name="x"></span>Hal Finkel<br>Assistant Computational Scientist<br>Leadership Computing Facility<br>Argonne National Laboratory<span name="x"></span><br></div></div></body></html>