<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=Windows-1252">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0); background-color: rgb(255, 255, 255);">
Be careful with a known bug in DA + pointer swapping:</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0); background-color: rgb(255, 255, 255);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0); background-color: rgb(255, 255, 255);">
<a href="http://lists.llvm.org/pipermail/llvm-dev/2019-May/132725.html" style="">http://lists.llvm.org/pipermail/llvm-dev/2019-May/132725.html</a></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0); background-color: rgb(255, 255, 255);">
<a href="https://bugs.llvm.org/show_bug.cgi?id=42143" style="">https://bugs.llvm.org/show_bug.cgi?id=42143</a></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0); background-color: rgb(255, 255, 255);">
<br>
</div>
<div id="appendonsend"></div>
<hr style="display:inline-block;width:98%" tabindex="-1">
<div id="divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" style="font-size:11pt" color="#000000"><b>From:</b> llvm-dev <llvm-dev-bounces@lists.llvm.org> on behalf of Finkel, Hal J. via llvm-dev <llvm-dev@lists.llvm.org><br>
<b>Sent:</b> Tuesday, March 17, 2020 4:06 PM<br>
<b>To:</b> Chawla, Pankaj <pankaj.chawla@intel.com>; Hiroshi Yamauchi <yamauchi@google.com><br>
<b>Cc:</b> llvm-dev@lists.llvm.org <llvm-dev@lists.llvm.org>; Kruse, Michael <michael.kruse@anl.gov><br>
<b>Subject:</b> Re: [llvm-dev] valid BasicAA behavior?</font>
<div> </div>
</div>
<style type="text/css" style="display:none">
<!--
p
{margin-top:0;
margin-bottom:0}
-->
</style>
<div dir="ltr">
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
Hi, Pankaj,</div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<br>
</div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
You want a dependence analysis, there is a DependenceAnalysis (and also a new DDG).</div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<br>
</div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
-Hal</div>
<div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<br>
</div>
<div id="x_Signature">
<div class="x_BodyFragment"><font size="2"><span style="font-size:10pt">
<div class="x_PlainText">Hal Finkel<br>
Lead, Compiler Technology and Programming Languages<br>
Leadership Computing Facility<br>
Argonne National Laboratory</div>
</span></font></div>
<div>
<div id="x_appendonsend"></div>
<div style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:12pt; color:rgb(0,0,0)">
<br>
</div>
<hr tabindex="-1" style="display:inline-block; width:98%">
<div id="x_divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" color="#000000" style="font-size:11pt"><b>From:</b> Chawla, Pankaj <pankaj.chawla@intel.com><br>
<b>Sent:</b> Tuesday, March 17, 2020 2:35 PM<br>
<b>To:</b> Finkel, Hal J. <hfinkel@anl.gov>; Hiroshi Yamauchi <yamauchi@google.com><br>
<b>Cc:</b> llvm-dev@lists.llvm.org <llvm-dev@lists.llvm.org><br>
<b>Subject:</b> RE: [llvm-dev] valid BasicAA behavior?</font>
<div> </div>
</div>
<div lang="EN-US">
<div class="x_x_WordSection1">
<p class="x_x_MsoNormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
Hi Hal,</p>
<p class="x_x_MsoNormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
</p>
<p class="x_x_MsoNormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
In that case what is the best way to query whether there is a loop carried dependence between B[j] and A[j] at i-loop level?</p>
<p class="x_x_MsoNormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
We were operating under the assumption of ‘conservatively correct’ behavior of alias analysis in the function scope?</p>
<p class="x_x_MsoNormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
</p>
<p class="x_x_MsoNormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
Thanks,</p>
<p class="x_x_MsoNormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
Pankaj</p>
<p class="x_x_MsoNormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
</p>
<div>
<div style="border:none; border-top:solid #E1E1E1 1.0pt; padding:3.0pt 0in 0in 0in">
<p class="x_x_MsoNormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<b>From:</b> Finkel, Hal J. <hfinkel@anl.gov> <br>
<b>Sent:</b> Tuesday, March 17, 2020 11:50 AM<br>
<b>To:</b> Hiroshi Yamauchi <yamauchi@google.com>; Chawla, Pankaj <pankaj.chawla@intel.com><br>
<b>Cc:</b> llvm-dev@lists.llvm.org<br>
<b>Subject:</b> Re: [llvm-dev] valid BasicAA behavior?</p>
</div>
</div>
<p class="x_x_MsoNormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
</p>
<div>
<p class="x_x_MsoNormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<span style="font-size:12.0pt; color:black">BasicAA should return a result that is valid for the particular SSA values it is provided, valid at points in the control flow where it would be valid to use both SSA values simultaneously. In this example, the SSA
values representing A and B always point to different memory, so NoAlias seems correct.</span></p>
</div>
<div>
<p class="x_x_MsoNormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<span style="font-size:12.0pt; color:black"> </span></p>
</div>
<div>
<p class="x_x_MsoNormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<span style="font-size:12.0pt; color:black"> -Hal</span></p>
</div>
<div>
<div>
<p class="x_x_MsoNormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<span style="font-size:12.0pt; color:black"> </span></p>
</div>
<div id="x_x_Signature">
<div>
<div>
<p class="x_x_MsoNormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<span style="font-size:10.0pt">Hal Finkel<br>
Lead, Compiler Technology and Programming Languages<br>
Leadership Computing Facility<br>
Argonne National Laboratory</span></p>
</div>
</div>
<div>
<div>
<p class="x_x_MsoNormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<span style="font-size:12.0pt; color:black"> </span></p>
</div>
<div class="x_x_MsoNormal" align="center" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif; text-align:center">
<hr size="2" width="98%" align="center">
</div>
<div id="x_x_divRplyFwdMsg">
<p class="x_x_MsoNormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<b><span style="color:black">From:</span></b><span style="color:black"> llvm-dev <<a href="mailto:llvm-dev-bounces@lists.llvm.org">llvm-dev-bounces@lists.llvm.org</a>> on behalf of Chawla, Pankaj via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><br>
<b>Sent:</b> Tuesday, March 17, 2020 1:34 PM<br>
<b>To:</b> Hiroshi Yamauchi <<a href="mailto:yamauchi@google.com">yamauchi@google.com</a>><br>
<b>Cc:</b> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a> <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><br>
<b>Subject:</b> Re: [llvm-dev] valid BasicAA behavior?</span> </p>
<div>
<p class="x_x_MsoNormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
</p>
</div>
</div>
<div>
<div>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
My understanding is that alias analysis returns results in the function scope, not in loop scope.
</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
Since both the phis access both global arrays, that should results in BasicAA conservatively returning MayAlias.</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
I debugged this a little bit and narrowed it down to the section of the code in BasicAAResult::aliasPHI() which has this comment-</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<i> // Analyse the PHIs' inputs under the assumption that the PHIs are</i></p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<i> // NoAlias.</i></p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<i> // If the PHIs are May/MustAlias there must be (recursively) an input</i></p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<i> // operand from outside the PHIs' cycle that is MayAlias/MustAlias or</i></p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<i> // there must be an operation on the PHIs within the PHIs' value cycle</i></p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<i> // that causes a MayAlias.</i></p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<i> // Pretend the phis do not alias.</i></p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<i> </i></p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
It seems to be analyzing corresponding phi operands assuming the PHIs to be ‘Noalias’ to begin with.
</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
IMHO, this setup does not work correctly for loop header phis.</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<b>From:</b> Hiroshi Yamauchi <<a href="mailto:yamauchi@google.com">yamauchi@google.com</a>>
<br>
<b>Sent:</b> Tuesday, March 17, 2020 8:38 AM<br>
<b>To:</b> Chawla, Pankaj <<a href="mailto:pankaj.chawla@intel.com">pankaj.chawla@intel.com</a>><br>
<b>Cc:</b> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<b>Subject:</b> Re: [llvm-dev] valid BasicAA behavior?</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
</p>
<div>
<div>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<span style="font-family:"Arial",sans-serif">Perhaps BasicAA is telling that A and B don't alias during one particular iteration of the loop even though they are swapped?</span></p>
</div>
<div>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<span style="font-family:"Arial",sans-serif"> </span></p>
</div>
<div>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<span style="font-family:"Arial",sans-serif">1: ; preds = %0, %35<br>
%2 = phi double* [ getelementptr inbounds ([1000 x double], [1000 x double]* @Ag, i64 0, i64 0), %0 ], [ %4, %35 ]<br>
%3 = phi i32 [ 0, %0 ], [ %36, %35 ]<br>
%4 = phi double* [ getelementptr inbounds ([1000 x double], [1000 x double]* @Bg, i64 0, i64 0), %0 ], [ %2, %35 ]<br>
br label %5</span></p>
</div>
<div>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<span style="font-family:"Arial",sans-serif"> </span></p>
</div>
<div>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
<span style="font-family:"Arial",sans-serif"><a href="https://godbolt.org/z/vHJmL5">https://godbolt.org/z/vHJmL5</a></span></p>
</div>
</div>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
</p>
<div>
<div>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
On Mon, Mar 16, 2020 at 10:28 PM Chawla, Pankaj via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:</p>
</div>
<blockquote style="border:none; border-left:solid #CCCCCC 1.0pt; padding:0in 0in 0in 6.0pt; margin-left:4.8pt; margin-top:5.0pt; margin-right:0in; margin-bottom:5.0pt">
<div>
<div>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
Hi all,</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
I have this test case-</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
#define N 1000</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
extern double Ag[N];</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
extern double Bg[N];</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
void consume(double *A, double *B);</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
void swap_deps() {</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
double *A = Ag;</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
double *B = Bg;</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
for (int i = 0; i < 97; ++i) {</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
for (int j = 0; j < N; ++j) {</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
B[j] = A[j] + 1;</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
}</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
double *tmp = A;</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
A = B;</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
B = tmp;</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
}</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
consume(A, B);</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
}</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
BasicAA is returning ‘NoAlias’ when queried for phis created in the i-loop for A and B.</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
I was expecting it to return MayAlias since A and B are being swapped in the outer loop and so they access same locations in alternate iterations of the i-loop.</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
Is BasicAA returning the correct result in this case?</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
Thanks,</p>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
Pankaj</p>
</div>
</div>
<p class="x_x_xmsonormal" style="margin:0in 0in 0.0001pt; font-size:11pt; font-family:Calibri,sans-serif">
_______________________________________________<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="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a></p>
</blockquote>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</body>
</html>