<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:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:SimSun;
panose-1:2 1 6 0 3 1 1 1 1 1;}
@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:SimSun;
panose-1:2 1 6 0 3 1 1 1 1 1;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
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;}
p
{mso-style-priority:99;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
tt
{mso-style-priority:99;
font-family:"Courier New";}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
margin-bottom:.0001pt;
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:8.5in 11.0in;
margin:1.0in 1.25in 1.0in 1.25in;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:17853925;
mso-list-type:hybrid;
mso-list-template-ids:1538714124 67698703 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l0:level1
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l1
{mso-list-id:678972915;
mso-list-template-ids:915297732;}
@list l1:level1
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:.5in;
mso-level-number-position:left;
text-indent:-.25in;
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:1.0in;
mso-level-number-position:left;
text-indent:-.25in;
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:\F0A7;
mso-level-tab-stop:1.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level4
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:2.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level5
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:2.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level6
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:3.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level7
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:3.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level8
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:4.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l1:level9
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:4.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l2
{mso-list-id:1215846186;
mso-list-template-ids:1912603302;}
@list l2:level1
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:"Courier New";
mso-bidi-font-family:"Times New Roman";}
@list l2:level3
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:1.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l2:level4
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:2.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l2:level5
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:2.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l2:level6
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:3.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l2:level7
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:3.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l2:level8
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:4.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l2:level9
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:4.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l3
{mso-list-id:1526555226;
mso-list-template-ids:-793345250;}
@list l3:level1
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l3:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:"Courier New";
mso-bidi-font-family:"Times New Roman";}
@list l3:level3
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:1.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l3:level4
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:2.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l3:level5
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:2.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l3:level6
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:3.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l3:level7
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:3.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l3:level8
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:4.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
@list l3:level9
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:4.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Wingdings;}
ol
{margin-bottom:0in;}
ul
{margin-bottom:0in;}
--></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"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Hi Bardia,<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">I am encountering a similar problem and totally agree that getAddExpr shouldn’t generate any assertion error or at least provide condition check. Even if this
is something to avoid, would it be better to return nullptr instead of assertion error?<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">Thanks,<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Jimmy<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>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><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"> llvm-dev [mailto:llvm-dev-bounces@lists.llvm.org]
<b>On Behalf Of </b>Bardia Mahjour via llvm-dev<br>
<b>Sent:</b> Monday, March 30, 2020 4:59 PM<br>
<b>To:</b> Philip Reames <listmail@philipreames.com><br>
<b>Cc:</b> LLVM Development List <llvm-dev@lists.llvm.org><br>
<b>Subject:</b> Re: [llvm-dev] Scalar Evolution Expressions Involving Sibling Loops<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p><tt><span style="font-size:10.0pt">> </span></tt><span style="font-size:10.0pt">I'm not following your example. If you have two sibling loops with the same parent, one will frequently, but not always dominate the other. Can you give a specific example
of when forming a recurrence between two siblings (without one dominating the other), is useful?
</span><br>
<br>
<span style="font-size:10.0pt">The situation can happen with guarded loops or with a user guard like below:</span><br>
<br>
<span style="font-size:10.0pt">if (c) {<br>
for (i = 0; i < n; i++) <br>
...<br>
}<br>
for (j = 0; j < n; j++)<br>
...</span><br>
<br>
<br>
<span style="font-size:10.0pt">The specific example that we ran into is described in
</span><a href="https://reviews.llvm.org/D75628"><span style="font-size:10.0pt">https://reviews.llvm.org/D75628</span></a><span style="font-size:10.0pt">. Basically we have two triangular loops that are siblings and we'd like to run Banerjee MIV tests on the
memory accesses in those loops. The loop looks like:</span><br>
<br>
<span style="font-size:10.0pt">void foo(int *restrict A, int n1, int n2, int n3) {<br>
for (int i1 = 0; i1 < n1; i1++) {<br>
for (int i2 = 2; i2 < n2; i2++) {<br>
for (int i3 = i2 + 1; i3 < n3; i3++) {<br>
A[i2 + i3*n2] = 11;<br>
}<br>
}<br>
for (int i4 = 2; i4 < n3; i4++) {<br>
for (int i5 = 1; i5 < i4 - 1; i5++) {<br>
A[i5] = 22;<br>
}<br>
}<br>
}<br>
}</span><br>
<br>
<span style="font-size:10.0pt">To check the bounds of the dependence function we need to create a symbolic expression that involves AddRecs for i2 and i4.</span><br>
<br>
<span style="font-size:10.0pt">Bardia Mahjour<br>
<br>
</span><br>
<br>
<img border="0" width="16" height="16" id="_x0000_i1025" src="cid:image001.gif@01D6140C.1D238B00" alt="Inactive hide details for Philip Reames ---2020/03/30 02:50:45 PM---On 3/30/20 11:27 AM, Bardia Mahjour via llvm-dev wrote: >"><span style="font-size:10.0pt;color:#424282">Philip
Reames ---2020/03/30 02:50:45 PM---On 3/30/20 11:27 AM, Bardia Mahjour via llvm-dev wrote: ></span><br>
<br>
<span style="font-size:10.0pt;color:#5F5F5F">From: </span><span style="font-size:10.0pt">Philip Reames <<a href="mailto:listmail@philipreames.com">listmail@philipreames.com</a>></span><br>
<span style="font-size:10.0pt;color:#5F5F5F">To: </span><span style="font-size:10.0pt">Bardia Mahjour <<a href="mailto:bmahjour@ca.ibm.com">bmahjour@ca.ibm.com</a>>, LLVM Development List <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>></span><br>
<span style="font-size:10.0pt;color:#5F5F5F">Date: </span><span style="font-size:10.0pt">2020/03/30 02:50 PM</span><br>
<span style="font-size:10.0pt;color:#5F5F5F">Subject: </span><span style="font-size:10.0pt">[EXTERNAL] Re: [llvm-dev] Scalar Evolution Expressions Involving Sibling Loops</span><o:p></o:p></p>
<div class="MsoNormal">
<hr size="2" width="100%" noshade="" style="color:#8091A5" align="left">
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><br>
<br>
<o:p></o:p></p>
<p>On 3/30/20 11:27 AM, Bardia Mahjour via llvm-dev wrote: <o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:10.0pt">Forwarding to the dev list, in case others ran into similar issues and/or have input on this topic.</span><br>
<span style="font-size:10.0pt"><br>
Bardia Mahjour</span><br>
<span style="font-size:10.0pt;color:purple"><br>
----- Forwarded by Bardia Mahjour/Toronto/IBM on 2020/03/30 02:25 PM -----</span><br>
<span style="font-size:10.0pt;color:#5F5F5F"><br>
From: </span><span style="font-size:10.0pt">Bardia Mahjour/Toronto/IBM<span style="color:#5F5F5F"><br>
To: </span></span><a href="mailto:listmail@philipreames.com"><span style="font-size:10.0pt">listmail@philipreames.com</span></a><span style="font-size:10.0pt;color:#5F5F5F"><br>
Cc: </span><span style="font-size:10.0pt">"Michael Kruse" </span><a href="mailto:llvm@meinersbur.de"><span style="font-size:10.0pt"><llvm@meinersbur.de></span></a><span style="font-size:10.0pt;color:#5F5F5F"><br>
Date: </span><span style="font-size:10.0pt">2020/03/26 11:47 AM<span style="color:#5F5F5F"><br>
Subject: </span>Scalar Evolution Expressions Involving Sibling Loops</span><o:p></o:p></p>
<div class="MsoNormal" style="margin-left:1.0in">
<hr size="2" width="100%" noshade="" style="color:#A0A0A0" align="left">
</div>
<p class="MsoNormal" style="margin-left:1.0in"><br>
<span style="font-size:10.0pt"><br>
Hi Philip,</span><br>
<span style="font-size:10.0pt"><br>
I hope you are doing well. </span><br>
<span style="font-size:10.0pt"><br>
We've recently run into an issue with SCEV in the context of dependence analysis, and would like your opinion on it. Background discussion can be found here
</span><a href="https://reviews.llvm.org/D75628#inline-689527"><span style="font-size:10.0pt">https://reviews.llvm.org/D75628#inline-689527</span></a><span style="font-size:10.0pt">.</span><br>
<span style="font-size:10.0pt"><br>
Basically in this case, the dependence equation requires us to symbolically create an expression involving two or more recurrences that recur with non-dominating loops (sibling loops).
</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:10.0pt">I'm not following your example. If you have two sibling loops with the same parent, one will frequently, but not always dominate the other. Can you give a specific example of when forming a recurrence between
two siblings (without one dominating the other), is useful? </span><o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:10.0pt">Currently creating such a SCEV expression trips asserts in `</span><tt><span style="font-size:10.0pt">CompareSCEVComplexity</span></tt><span style="font-size:10.0pt">()` and `</span><tt><span style="font-size:10.0pt">isKnownViaInduction</span></tt><span style="font-size:10.0pt">()`
saying that a given SCEV expression cannot be composed of recurrences that have no dominance relationship between them.
</span><br>
<span style="font-size:10.0pt"><br>
Michael tried explaining to me why there is this restriction about dominance, and I'm beginning to understand why such restriction may be necessary when evaluating or expanding SCEV expressions in outer scopes (eg. `</span><tt><span style="font-size:10.0pt">getSCEVAtScope</span></tt><span style="font-size:10.0pt">(nullptr)`)
but I still don't understand why this restriction is imposed at construction. Shouldn't this restriction be asserted on when calling getSCEVAtScope instead of when creating AddRecs, given that simplification steps may remove identical terms involving non-dominating
loops? </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:10.0pt">Well, SCEV construction is generally done to parallel IR. SSA requires dominance, so having the SCEV operands require dominance would seem like a reasonable thing. If you want to change this, you'll need
to motivate the change. (i.e. see above question)</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:1.0in">
<span style="font-size:10.0pt"><br>
We would appreciate any other insight you might have about this issue.</span><br>
<span style="font-size:10.0pt"><br>
Regards,</span><br>
<span style="font-size:10.0pt"><br>
Bardia Mahjour<br>
Compiler Optimizations<br>
IBM Toronto Software Lab<u><span style="color:blue"><br>
</span></u></span><a href="mailto:bmahjour@ca.ibm.com"><span style="font-size:10.0pt">bmahjour@ca.ibm.com</span></a><br>
<br>
<br>
<tt><span style="font-size:10.0pt">_______________________________________________</span></tt><span style="font-size:10.0pt;font-family:"Courier New""><br>
<tt>LLVM Developers mailing list</tt><br>
</span><a href="mailto:llvm-dev@lists.llvm.org"><tt><span style="font-size:10.0pt">llvm-dev@lists.llvm.org</span></tt></a><span style="font-size:10.0pt;font-family:"Courier New""><br>
</span><a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"><tt><span style="font-size:10.0pt">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</span></tt></a><span style="font-size:10.0pt;font-family:"Courier New""><br>
<br>
</span><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</body>
</html>