[llvm-dev] Scalar Evolution Expressions Involving Sibling Loops
Bardia Mahjour via llvm-dev
llvm-dev at lists.llvm.org
Fri Apr 17 08:16:38 PDT 2020
Thanks for sharing the known problem.
I think to solve the problem properly, we need to fully understand why that
assumption about dominance is there and the implications of removing it.
It would be good if you could be more specific about your idea of nullptr
or SCEV_unknown (eg which function would return those values and when), but
returning nullptr from getAddExpr or getSCEVAtScope may be problematic
since they currently return valid pointers all the time and changing that
would be error prone and would increase code complexity. Returning
SCEV_Unknown from getAddExpr would seem plausible except that it would not
allow for expression simplifications where recurrences over non-dominating
loops can get canceled out. Having said that it may still be a reasonable
middle-ground solution.
Philip, do you have any thoughts on that?
Bardia Mahjour
From: Jimmy Zhongduo Lin <jimmy.zhongduo.lin at huawei.com>
To: Bardia Mahjour <bmahjour at ca.ibm.com>
Cc: Philip Reames <listmail at philipreames.com>,
"llvm-dev at lists.llvm.org" <llvm-dev at lists.llvm.org>
Date: 2020/04/16 08:39 PM
Subject: [EXTERNAL] RE: [llvm-dev] Scalar Evolution Expressions
Involving Sibling Loops
Hi Bardia,
This is actually a long known problem:
http://lists.llvm.org/pipermail/llvm-bugs/2017-July/056757.html
As shown above, the problem gets triggered easily with scev-aa since it
will compare two SCEVs from anywhere in the code, including your case of
course. I believe the real problem is how to solve it properly. In the long
run, checking satisfiesTotalOrder is too costly as it is duplicating part
of the work in getAddExpr, but I agree it is way better than assertion
error. Maybe SCEV_Unknown or nullptr can be used too.
Thanks,
Jimmy
From: Bardia Mahjour [mailto:bmahjour at ca.ibm.com]
Sent: Thursday, April 16, 2020 4:51 PM
To: Jimmy Zhongduo Lin <jimmy.zhongduo.lin at huawei.com>
Cc: Philip Reames <listmail at philipreames.com>; llvm-dev at lists.llvm.org
Subject: RE: [llvm-dev] Scalar Evolution Expressions Involving Sibling
Loops
Hi Jimmy,
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.
Bardia Mahjour
Compiler Optimizations
IBM Toronto Software Lab
Inactive hide details for Jimmy Zhongduo Lin ---2020/04/16 04:34:24 PM---Hi
Bardia, I am encountering a similar problem and totJimmy 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
From: Jimmy Zhongduo Lin <jimmy.zhongduo.lin at huawei.com>
To: Bardia Mahjour <bmahjour at ca.ibm.com>, Philip Reames <
listmail at philipreames.com>, "llvm-dev at lists.llvm.org" <
llvm-dev at lists.llvm.org>
Date: 2020/04/16 04:34 PM
Subject: [EXTERNAL] RE: [llvm-dev] Scalar Evolution Expressions Involving
Sibling Loops
Hi Bardia,
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?
Thanks,
Jimmy
From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of Bardia
Mahjour via llvm-dev
Sent: Monday, March 30, 2020 4:59 PM
To: Philip Reames <listmail at philipreames.com>
Cc: LLVM Development List <llvm-dev at lists.llvm.org>
Subject: Re: [llvm-dev] Scalar Evolution Expressions Involving Sibling
Loops
> 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?
The situation can happen with guarded loops or with a user guard like
below:
if (c) {
for (i = 0; i < n; i++)
...
}
for (j = 0; j < n; j++)
...
The specific example that we ran into is described in
https://reviews.llvm.org/D75628. 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:
void foo(int *restrict A, int n1, int n2, int n3) {
for (int i1 = 0; i1 < n1; i1++) {
for (int i2 = 2; i2 < n2; i2++) {
for (int i3 = i2 + 1; i3 < n3; i3++) {
A[i2 + i3*n2] = 11;
}
}
for (int i4 = 2; i4 < n3; i4++) {
for (int i5 = 1; i5 < i4 - 1; i5++) {
A[i5] = 22;
}
}
}
}
To check the bounds of the dependence function we need to create a symbolic
expression that involves AddRecs for i2 and i4.
Bardia Mahjour
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: >Philip Reames
---2020/03/30 02:50:45 PM---On 3/30/20 11:27 AM, Bardia Mahjour via
llvm-dev wrote: >
From: Philip Reames <listmail at philipreames.com>
To: Bardia Mahjour <bmahjour at ca.ibm.com>, LLVM Development List <
llvm-dev at lists.llvm.org>
Date: 2020/03/30 02:50 PM
Subject: [EXTERNAL] Re: [llvm-dev] Scalar Evolution Expressions Involving
Sibling Loops
On 3/30/20 11:27 AM, Bardia Mahjour via llvm-dev wrote:
Forwarding to the dev list, in case others ran into
similar issues and/or have input on this topic.
Bardia Mahjour
----- Forwarded by Bardia Mahjour/Toronto/IBM on
2020/03/30 02:25 PM -----
From: Bardia Mahjour/Toronto/IBM
To: listmail at philipreames.com
Cc: "Michael Kruse" <llvm at meinersbur.de>
Date: 2020/03/26 11:47 AM
Subject: Scalar Evolution Expressions Involving
Sibling Loops
Hi Philip,
I hope you are doing well.
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 https://reviews.llvm.org/D75628#inline-689527.
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).
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?
Currently creating such a SCEV expression trips
asserts in `CompareSCEVComplexity()` and `
isKnownViaInduction()` saying that a given SCEV
expression cannot be composed of recurrences that
have no dominance relationship between them.
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. `getSCEVAtScope(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?
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)
We would appreciate any other insight you might
have about this issue.
Regards,
Bardia Mahjour
Compiler Optimizations
IBM Toronto Software Lab
bmahjour at ca.ibm.com
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200417/948103a2/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: graycol.gif
Type: image/gif
Size: 105 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200417/948103a2/attachment.gif>
More information about the llvm-dev
mailing list