[llvm-dev] Scalar Evolution Expressions Involving Sibling Loops

[Bardia Mahjour via llvm-dev]

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>