<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=us-ascii">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><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;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-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;
margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
p.xmsonormal, li.xmsonormal, div.xmsonormal
{mso-style-name:x_msonormal;
margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
p.xxmsonormal, li.xxmsonormal, div.xxmsonormal
{mso-style-name:x_xmsonormal;
margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle22
{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:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
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">Isn’t DependenceAnalysis dependent on conservative behavior of alias analysis?<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">It invokes AliasAnalysis with unknown size.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I tried it on this case and it returns this-<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">$ opt -analyze -basicaa -da test.ll<o:p></o:p></p>
<p class="MsoNormal">Src: %0 = load double, double* %arrayidx, align 8, !tbaa !2 --> Dst: store double %add, double* %arrayidx6, align 8, !tbaa !2<o:p></o:p></p>
<p class="MsoNormal"> da analyze - none!<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b>From:</b> Finkel, Hal J. <hfinkel@anl.gov> <br>
<b>Sent:</b> Tuesday, March 17, 2020 1:07 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; Kruse, Michael <michael.kruse@anl.gov><br>
<b>Subject:</b> Re: [llvm-dev] valid BasicAA behavior?<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">Hi, Pankaj,<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">You want a dependence analysis, there is a DependenceAnalysis (and also a new DDG).<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"> -Hal<o:p></o:p></span></p>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
</div>
<div id="Signature">
<div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt">Hal Finkel<br>
Lead, Compiler Technology and Programming Languages<br>
Leadership Computing Facility<br>
Argonne National Laboratory<o:p></o:p></span></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
</div>
<div class="MsoNormal" align="center" style="text-align:center">
<hr size="2" width="98%" align="center">
</div>
<div id="divRplyFwdMsg">
<p class="MsoNormal"><b><span style="color:black">From:</span></b><span style="color:black"> Chawla, Pankaj <<a href="mailto:pankaj.chawla@intel.com">pankaj.chawla@intel.com</a>><br>
<b>Sent:</b> Tuesday, March 17, 2020 2:35 PM<br>
<b>To:</b> Finkel, Hal J. <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>>; 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> <o:p></o:p></p>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="xmsonormal">Hi Hal,<o:p></o:p></p>
<p class="xmsonormal"> <o:p></o:p></p>
<p class="xmsonormal">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?<o:p></o:p></p>
<p class="xmsonormal">We were operating under the assumption of ‘conservatively correct’ behavior of alias analysis in the function scope?<o:p></o:p></p>
<p class="xmsonormal"> <o:p></o:p></p>
<p class="xmsonormal">Thanks,<o:p></o:p></p>
<p class="xmsonormal">Pankaj<o:p></o:p></p>
<p class="xmsonormal"> <o:p></o:p></p>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="xmsonormal"><b>From:</b> Finkel, Hal J. <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>>
<br>
<b>Sent:</b> Tuesday, March 17, 2020 11:50 AM<br>
<b>To:</b> Hiroshi Yamauchi <<a href="mailto:yamauchi@google.com">yamauchi@google.com</a>>; 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?<o:p></o:p></p>
</div>
</div>
<p class="xmsonormal"> <o:p></o:p></p>
<div>
<p class="xmsonormal"><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><o:p></o:p></p>
</div>
<div>
<p class="xmsonormal"><span style="font-size:12.0pt;color:black"> </span><o:p></o:p></p>
</div>
<div>
<p class="xmsonormal"><span style="font-size:12.0pt;color:black"> -Hal</span><o:p></o:p></p>
</div>
<div>
<div>
<p class="xmsonormal"><span style="font-size:12.0pt;color:black"> </span><o:p></o:p></p>
</div>
<div id="x_Signature">
<div>
<div>
<p class="xmsonormal"><span style="font-size:10.0pt">Hal Finkel<br>
Lead, Compiler Technology and Programming Languages<br>
Leadership Computing Facility<br>
Argonne National Laboratory</span><o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="xmsonormal"><span style="font-size:12.0pt;color:black"> </span><o:p></o:p></p>
</div>
<div class="MsoNormal" align="center" style="text-align:center">
<hr size="2" width="98%" align="center">
</div>
<div id="x_divRplyFwdMsg">
<p class="xmsonormal"><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> <o:p></o:p></p>
<div>
<p class="xmsonormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="xxmsonormal">My understanding is that alias analysis returns results in the function scope, not in loop scope.
<o:p></o:p></p>
<p class="xxmsonormal">Since both the phis access both global arrays, that should results in BasicAA conservatively returning MayAlias.<o:p></o:p></p>
<p class="xxmsonormal"> <o:p></o:p></p>
<p class="xxmsonormal">I debugged this a little bit and narrowed it down to the section of the code in BasicAAResult::aliasPHI() which has this comment-<o:p></o:p></p>
<p class="xxmsonormal"><i> // Analyse the PHIs' inputs under the assumption that the PHIs are</i><o:p></o:p></p>
<p class="xxmsonormal"><i> // NoAlias.</i><o:p></o:p></p>
<p class="xxmsonormal"><i> // If the PHIs are May/MustAlias there must be (recursively) an input</i><o:p></o:p></p>
<p class="xxmsonormal"><i> // operand from outside the PHIs' cycle that is MayAlias/MustAlias or</i><o:p></o:p></p>
<p class="xxmsonormal"><i> // there must be an operation on the PHIs within the PHIs' value cycle</i><o:p></o:p></p>
<p class="xxmsonormal"><i> // that causes a MayAlias.</i><o:p></o:p></p>
<p class="xxmsonormal"><i> // Pretend the phis do not alias.</i><o:p></o:p></p>
<p class="xxmsonormal"><i> </i><o:p></o:p></p>
<p class="xxmsonormal">It seems to be analyzing corresponding phi operands assuming the PHIs to be ‘Noalias’ to begin with.
<o:p></o:p></p>
<p class="xxmsonormal">IMHO, this setup does not work correctly for loop header phis.<o:p></o:p></p>
<p class="xxmsonormal"> <o:p></o:p></p>
<p class="xxmsonormal"> <o:p></o:p></p>
<p class="xxmsonormal"><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?<o:p></o:p></p>
<p class="xxmsonormal"> <o:p></o:p></p>
<div>
<div>
<p class="xxmsonormal"><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><o:p></o:p></p>
</div>
<div>
<p class="xxmsonormal"><span style="font-family:"Arial",sans-serif"> </span><o:p></o:p></p>
</div>
<div>
<p class="xxmsonormal"><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><o:p></o:p></p>
</div>
<div>
<p class="xxmsonormal"><span style="font-family:"Arial",sans-serif"> </span><o:p></o:p></p>
</div>
<div>
<p class="xxmsonormal"><span style="font-family:"Arial",sans-serif"><a href="https://godbolt.org/z/vHJmL5">https://godbolt.org/z/vHJmL5</a></span><o:p></o:p></p>
</div>
</div>
<p class="xxmsonormal"> <o:p></o:p></p>
<div>
<div>
<p class="xxmsonormal">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:<o:p></o:p></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="xxmsonormal">Hi all,<o:p></o:p></p>
<p class="xxmsonormal"> <o:p></o:p></p>
<p class="xxmsonormal">I have this test case-<o:p></o:p></p>
<p class="xxmsonormal"> <o:p></o:p></p>
<p class="xxmsonormal">#define N 1000<o:p></o:p></p>
<p class="xxmsonormal">extern double Ag[N];<o:p></o:p></p>
<p class="xxmsonormal">extern double Bg[N];<o:p></o:p></p>
<p class="xxmsonormal"> <o:p></o:p></p>
<p class="xxmsonormal">void consume(double *A, double *B);<o:p></o:p></p>
<p class="xxmsonormal"> <o:p></o:p></p>
<p class="xxmsonormal">void swap_deps() {<o:p></o:p></p>
<p class="xxmsonormal"> double *A = Ag;<o:p></o:p></p>
<p class="xxmsonormal"> double *B = Bg;<o:p></o:p></p>
<p class="xxmsonormal"> <o:p></o:p></p>
<p class="xxmsonormal"> for (int i = 0; i < 97; ++i) {<o:p></o:p></p>
<p class="xxmsonormal"> for (int j = 0; j < N; ++j) {<o:p></o:p></p>
<p class="xxmsonormal"> B[j] = A[j] + 1;<o:p></o:p></p>
<p class="xxmsonormal"> }<o:p></o:p></p>
<p class="xxmsonormal"> <o:p></o:p></p>
<p class="xxmsonormal"> double *tmp = A;<o:p></o:p></p>
<p class="xxmsonormal"> A = B;<o:p></o:p></p>
<p class="xxmsonormal"> B = tmp;<o:p></o:p></p>
<p class="xxmsonormal"> }<o:p></o:p></p>
<p class="xxmsonormal"> <o:p></o:p></p>
<p class="xxmsonormal"> consume(A, B);<o:p></o:p></p>
<p class="xxmsonormal">}<o:p></o:p></p>
<p class="xxmsonormal"> <o:p></o:p></p>
<p class="xxmsonormal">BasicAA is returning ‘NoAlias’ when queried for phis created in the i-loop for A and B.<o:p></o:p></p>
<p class="xxmsonormal">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.<o:p></o:p></p>
<p class="xxmsonormal"> <o:p></o:p></p>
<p class="xxmsonormal">Is BasicAA returning the correct result in this case?<o:p></o:p></p>
<p class="xxmsonormal"> <o:p></o:p></p>
<p class="xxmsonormal">Thanks,<o:p></o:p></p>
<p class="xxmsonormal">Pankaj<o:p></o:p></p>
</div>
</div>
<p class="xxmsonormal">_______________________________________________<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><o:p></o:p></p>
</blockquote>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</body>
</html>