Bardia Mahjour via llvm-dev
2020-Mar-30 18:27 UTC
[llvm-dev] Scalar Evolution Expressions Involving Sibling Loops
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). 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? 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 -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200330/66ff98ad/attachment-0001.html>
Philip Reames via llvm-dev
2020-Mar-30 18:50 UTC
[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/IBMon 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/44c533e6/attachment-0001.html>
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>