<html><body><p><font size="2">Hi Jimmy,</font><br><br><font size="2">It's good to know that the problem is not specific to the case I ran into. May be you can provide your example as well, since Philip seems to be interested in some specific examples. If the assertion in getAddrExpr is deemed necessary, then I think a condition check would be the next best solution as it helps client code guard against such cases and make alternative arrangements to avoid an assertion or miscompile. </font><br><br><font size="2">Bardia Mahjour<br>Compiler Optimizations<br>IBM Toronto Software Lab<br><br></font><br><br><img width="16" height="16" src="cid:1__=8FBB0FDFDFE240048f9e8a93df938690918c8FB@" border="0" alt="Inactive hide details for Jimmy Zhongduo Lin ---2020/04/16 04:34:24 PM---Hi Bardia, I am encountering a similar problem and tot"><font size="2" color="#424282">Jimmy Zhongduo Lin ---2020/04/16 04:34:24 PM---Hi Bardia, I am encountering a similar problem and totally agree that getAddExpr shouldn't generate</font><br><br><font size="2" color="#5F5F5F">From: </font><font size="2">Jimmy Zhongduo Lin <jimmy.zhongduo.lin@huawei.com></font><br><font size="2" color="#5F5F5F">To: </font><font size="2">Bardia Mahjour <bmahjour@ca.ibm.com>, Philip Reames <listmail@philipreames.com>, "llvm-dev@lists.llvm.org" <llvm-dev@lists.llvm.org></font><br><font size="2" color="#5F5F5F">Date: </font><font size="2">2020/04/16 04:34 PM</font><br><font size="2" color="#5F5F5F">Subject: </font><font size="2">[EXTERNAL] RE: [llvm-dev] Scalar Evolution Expressions Involving Sibling Loops</font><br><hr width="100%" size="2" align="left" noshade style="color:#8091A5; "><br><br><br><font color="#1F497D">Hi Bardia,</font><br><font color="#1F497D"> </font><br><font 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?</font><br><font color="#1F497D"> </font><br><font color="#1F497D">Thanks,</font><br><font color="#1F497D">Jimmy</font><br><font color="#1F497D"> </font><br><b>From:</b> llvm-dev [<a href="mailto:llvm-dev-bounces@lists.llvm.org">mailto:llvm-dev-bounces@lists.llvm.org</a>] <b>On Behalf Of </b>Bardia Mahjour via llvm-dev<b><br>Sent:</b> Monday, March 30, 2020 4:59 PM<b><br>To:</b> Philip Reames <listmail@philipreames.com><b><br>Cc:</b> LLVM Development List <llvm-dev@lists.llvm.org><b><br>Subject:</b> Re: [llvm-dev] Scalar Evolution Expressions Involving Sibling Loops<br><font face="Times New Roman"> </font><p><font size="2" face="Courier New">> </font><font size="2" face="Times New Roman">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? </font><font face="Times New Roman"><br></font><font size="2" face="Times New Roman"><br>The situation can happen with guarded loops or with a user guard like below:</font><font face="Times New Roman"><br></font><font size="2" face="Times New Roman"><br>if (c) {<br>for (i = 0; i < n; i++) <br>...<br>}<br>for (j = 0; j < n; j++)<br>...</font><font face="Times New Roman"><br><br></font><font size="2" face="Times New Roman"><br>The specific example that we ran into is described in </font><a href="https://reviews.llvm.org/D75628"><u><font size="2" color="#0000FF" face="Times New Roman">https://reviews.llvm.org/D75628</font></u></a><font size="2" face="Times New Roman">. 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:</font><font face="Times New Roman"><br></font><font size="2" face="Times New Roman"><br>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>}</font><font face="Times New Roman"><br></font><font size="2" face="Times New Roman"><br>To check the bounds of the dependence function we need to create a symbolic expression that involves AddRecs for i2 and i4.</font><font face="Times New Roman"><br></font><font size="2" face="Times New Roman"><br>Bardia Mahjour<br></font><font face="Times New Roman"><br><br><br></font><img src="cid:1__=8FBB0FDFDFE240048f9e8a93df938690918c8FB@" width="16" height="16" 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: >"><font size="2" color="#424282" face="Times New Roman">Philip Reames ---2020/03/30 02:50:45 PM---On 3/30/20 11:27 AM, Bardia Mahjour via llvm-dev wrote: ></font><font face="Times New Roman"><br></font><font size="2" color="#5F5F5F" face="Times New Roman"><br>From: </font><font size="2" face="Times New Roman">Philip Reames <</font><a href="mailto:listmail@philipreames.com"><u><font size="2" color="#0000FF" face="Times New Roman">listmail@philipreames.com</font></u></a><font size="2" face="Times New Roman">></font><font size="2" color="#5F5F5F" face="Times New Roman"><br>To: </font><font size="2" face="Times New Roman">Bardia Mahjour <</font><a href="mailto:bmahjour@ca.ibm.com"><u><font size="2" color="#0000FF" face="Times New Roman">bmahjour@ca.ibm.com</font></u></a><font size="2" face="Times New Roman">>, LLVM Development List <</font><a href="mailto:llvm-dev@lists.llvm.org"><u><font size="2" color="#0000FF" face="Times New Roman">llvm-dev@lists.llvm.org</font></u></a><font size="2" face="Times New Roman">></font><font size="2" color="#5F5F5F" face="Times New Roman"><br>Date: </font><font size="2" face="Times New Roman">2020/03/30 02:50 PM</font><font size="2" color="#5F5F5F" face="Times New Roman"><br>Subject: </font><font size="2" face="Times New Roman">[EXTERNAL] Re: [llvm-dev] Scalar Evolution Expressions Involving Sibling Loops</font><br><hr width="100%" size="2" align="left" noshade><br><font face="Times New Roman"><br></font><p><font face="Times New Roman">On 3/30/20 11:27 AM, Bardia Mahjour via llvm-dev wrote: </font><ul><ul><ul><ul><font size="2" face="Times New Roman">Forwarding to the dev list, in case others ran into similar issues and/or have input on this topic.<br><br>Bardia Mahjour</font><font size="2" color="#800080" face="Times New Roman"><br><br>----- Forwarded by Bardia Mahjour/Toronto/IBM on 2020/03/30 02:25 PM -----</font><font size="2" color="#5F5F5F" face="Times New Roman"><br><br>From: </font><font size="2" face="Times New Roman">Bardia Mahjour/Toronto/IBM</font><font size="2" color="#5F5F5F" face="Times New Roman"><br>To: </font><a href="mailto:listmail@philipreames.com"><u><font size="2" color="#0000FF" face="Times New Roman">listmail@philipreames.com</font></u></a><font size="2" color="#5F5F5F" face="Times New Roman"><br>Cc: </font><font size="2" face="Times New Roman">"Michael Kruse" </font><a href="mailto:llvm@meinersbur.de"><u><font size="2" color="#0000FF" face="Times New Roman"><llvm@meinersbur.de></font></u></a><font size="2" color="#5F5F5F" face="Times New Roman"><br>Date: </font><font size="2" face="Times New Roman">2020/03/26 11:47 AM</font><font size="2" color="#5F5F5F" face="Times New Roman"><br>Subject: </font><font size="2" face="Times New Roman">Scalar Evolution Expressions Involving Sibling Loops</font><br><hr width="100%" size="2" align="left" noshade><br><font size="2" face="Times New Roman"><br><br>Hi Philip,<br><br>I hope you are doing well. <br><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 </font><a href="https://reviews.llvm.org/D75628#inline-689527"><u><font size="2" color="#0000FF" face="Times New Roman">https://reviews.llvm.org/D75628#inline-689527</font></u></a><font size="2" face="Times New Roman">.<br><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). </font></ul></ul></ul></ul><font size="2" face="Times New Roman">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? </font><ul><ul><ul><ul><font size="2" face="Times New Roman">Currently creating such a SCEV expression trips asserts in `</font><font size="2" face="Courier New">CompareSCEVComplexity</font><font size="2" face="Times New Roman">()` and `</font><font size="2" face="Courier New">isKnownViaInduction</font><font size="2" face="Times New Roman">()` saying that a given SCEV expression cannot be composed of recurrences that have no dominance relationship between them. <br><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. `</font><font size="2" face="Courier New">getSCEVAtScope</font><font size="2" face="Times New Roman">(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? </font></ul></ul></ul></ul><font size="2" face="Times New Roman">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)</font><ul><ul><ul><ul><font size="2" face="Times New Roman"><br>We would appreciate any other insight you might have about this issue.<br><br>Regards,<br><br>Bardia Mahjour<br>Compiler Optimizations<br>IBM Toronto Software Lab</font><u><font color="#0000FF" face="Times New Roman"><br></font></u><a href="mailto:bmahjour@ca.ibm.com"><u><font size="2" color="#0000FF" face="Times New Roman">bmahjour@ca.ibm.com</font></u></a><font face="Times New Roman"><br><br></font><font size="2" face="Courier New"><br>_______________________________________________<br>LLVM Developers mailing list</font><u><font color="#0000FF" face="Times New Roman"><br></font></u><a href="mailto:llvm-dev@lists.llvm.org"><u><font size="2" color="#0000FF" face="Courier New">llvm-dev@lists.llvm.org</font></u></a><u><font color="#0000FF" face="Times New Roman"><br></font></u><a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"><u><font size="2" color="#0000FF" face="Courier New">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</font></u></a><font size="2" face="Courier New"><br></font></ul></ul></ul></ul><font face="Times New Roman"> </font><br><br><BR>
</body></html>