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-Mar-30 20:59 UTC

[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





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/20200330/e5d7d38e/attachment-0001.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/20200330/e5d7d38e/attachment-0001.gif>

Jimmy Zhongduo Lin via llvm-dev

2020-Apr-16 20:34 UTC

head link

[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<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/20200416/5dabfbdc/attachment.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/20200416/5dabfbdc/attachment.gif>

Bardia Mahjour via llvm-dev

2020-Apr-16 20:50 UTC

head link

[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





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/20200416/ed126578/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/20200416/ed126578/attachment.gif>

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