thr3ads.net - llvm dev - [llvm-dev] Scalar Evolution Expressions Involving Sibling Loops [Apr 2020]

If this information is useful, please help other people find it:
Share via:

Bardia Mahjour via llvm-dev

2020-Apr-17 15:16 UTC

[llvm-dev] Scalar Evolution Expressions Involving Sibling Loops

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 thesame 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>

Jimmy Zhongduo Lin via llvm-dev

2020-Apr-17 15:32 UTC

head link

[llvm-dev] Scalar Evolution Expressions Involving Sibling Loops

Hi Bardia,

I agree that we need to understand the consequence of that. I thought SCEV is
just folding operations to a tree-like structure, so I am surprised it couldn’t
handle two AddRec of didfferent loops. To support that, it might break a lot of
codes with that assumption. So we will likely need to review all the public
interfaces to make sure it is safe.

So I am just talking about middle-ground solution. If we have GroupByComplexity
returning bool to signal if the condition is satisfied, which will require the
compare function to return certain flag too, we will avoid introducing a
condition check and have the callers return SCEV_unknown etc.

Thanks,
Jimmy

From: Bardia Mahjour [mailto:bmahjour at ca.ibm.com]
Sent: Friday, April 17, 2020 11:17 AM
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


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


[Inactive hide details for Jimmy Zhongduo Lin ---2020/04/16 08:39:34 PM---Hi
Bardia, This is actually a long known problem: http]Jimmy Zhongduo Lin
---2020/04/16 08:39:34 PM---Hi Bardia, This is actually a long known problem:
INVALID URI REMOVED<INVALID%20URI%20REMOVED>

From: Jimmy Zhongduo Lin <jimmy.zhongduo.lin at
huawei.com<mailto:jimmy.zhongduo.lin at huawei.com>>
To: Bardia Mahjour <bmahjour at ca.ibm.com<mailto:bmahjour at
ca.ibm.com>>
Cc: Philip Reames <listmail at philipreames.com<mailto:listmail at
philipreames.com>>, "llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>" <llvm-dev at lists.llvm.org<mailto: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<mailto:jimmy.zhongduo.lin at huawei.com>>
Cc: Philip Reames <listmail at philipreames.com<mailto:listmail at
philipreames.com>>; llvm-dev at lists.llvm.org<mailto: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 tot]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

From: Jimmy Zhongduo Lin <jimmy.zhongduo.lin at
huawei.com<mailto:jimmy.zhongduo.lin at huawei.com>>
To: Bardia Mahjour <bmahjour at ca.ibm.com<mailto:bmahjour at
ca.ibm.com>>, Philip Reames <listmail at
philipreames.com<mailto:listmail at philipreames.com>>, "llvm-dev
at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>" <llvm-dev at
lists.llvm.org<mailto: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<mailto:listmail at
philipreames.com>>
Cc: LLVM Development List <llvm-dev at lists.llvm.org<mailto: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<mailto:listmail at
philipreames.com>>
To: Bardia Mahjour <bmahjour at ca.ibm.com<mailto:bmahjour at
ca.ibm.com>>, LLVM Development List <llvm-dev at
lists.llvm.org<mailto: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<mailto:listmail at philipreames.com>
Cc: "Michael Kruse" <llvm at meinersbur.de><mailto: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<mailto:bmahjour at ca.ibm.com>


_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto: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/b918a51a/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.gif
Type: image/gif
Size: 105 bytes
Desc: image001.gif
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200417/b918a51a/attachment-0001.gif>

Michael Kruse via llvm-dev

2020-Apr-18 02:58 UTC

head link

[llvm-dev] Scalar Evolution Expressions Involving Sibling Loops

My interpretation of ScalarEvolution is that an AddRecExpr is only
intended in a context within a loop, since it references the loop
induction variable of which there is none outside the loop.
Outside the loop, one has to use the exit value obtainable by
getSCEVAtScope that removes the AddRecExpr not nested inside the
parameter.
With this interpretation, two AddRecExpr with two sibling loop would
always be invalid since one can never be in both loop at the same
time.

Michael


Am Fr., 17. Apr. 2020 um 10:32 Uhr schrieb Jimmy Zhongduo Lin via
llvm-dev <llvm-dev at lists.llvm.org>:>
> Hi Bardia,
>
>
>
> I agree that we need to understand the consequence of that. I thought SCEV
is just folding operations to a tree-like structure, so I am surprised it
couldn’t handle two AddRec of didfferent loops. To support that, it might break
a lot of codes with that assumption. So we will likely need to review all the
public interfaces to make sure it is safe.
>
>
>
> So I am just talking about middle-ground solution. If we have
GroupByComplexity returning bool to signal if the condition is satisfied, which
will require the compare function to return certain flag too, we will avoid
introducing a condition check and have the callers return SCEV_unknown etc.
>
>
>
> Thanks,
>
> Jimmy
>
>
>
> From: Bardia Mahjour [mailto:bmahjour at ca.ibm.com]
> Sent: Friday, April 17, 2020 11:17 AM
> 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
>
>
>
> 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
>
>
> Jimmy Zhongduo Lin ---2020/04/16 08:39:34 PM---Hi Bardia, This is actually
a long known problem: INVALID URI REMOVED
>
> 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
>
>
>
> 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
>
> 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
>
>
>
> 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
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

llvm dev - Apr 2020 - Scalar Evolution Expressions Involving Sibling Loops

[llvm-dev] Scalar Evolution Expressions Involving Sibling Loops

[llvm-dev] Scalar Evolution Expressions Involving Sibling Loops

[llvm-dev] Scalar Evolution Expressions Involving Sibling Loops