# [llvm-dev] Scalar Evolution Expressions Involving Sibling Loops

Bardia Mahjour via llvm-dev llvm-dev at lists.llvm.org
Mon Mar 30 13:59:17 PDT 2020

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

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)

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