llvm dev - Jun 2019 - [RFC][SCEV] Behavior of AddRec in CompareSCEVComplexity

Hi,

Thanks for the input. In my ptr_test.O1.ll, the two loops should fall into
the last case due to loop rotations. And I think we should handle that case.
I propose to check the dominance relation between loop predecessor blocks
of the two loops if there is no dominance relation between their loop
headers just like case three. The only thing I'm not pretty sure is that is
there guarantee to exist dominance relation on their loop predecessor
blocks. That is, either LPred dominates RPred or RPred dominate LPred?

B.R.
- Min

On Tue, Jun 11, 2019 at 8:41 PM Michael Kruse <llvmdev at meinersbur.de>
wrote:
> Hi,
>
> if I understand CompareSCEVComplexity  correctly, we just need some
> deterministic order, not that important which one. We have three
> cases:
>
> 1. LHead dominates RHead
> 2. RHead dominates LHead
> 3. There is no dominance relationship between the loops
>
> LHead dominating RHead can either mean that R is nested inside L, or
> the entire loop of L dominated R. From ptr_test.c that latter seems
> the case, but LoopRotation might change this relation.
>
> For the third case, we might just find another tie breaker rule, such
> as a NumOps comparison afterwards or the order in which LoopInfo finds
> them (this might be indeterministic). However, it might also be ok to
> just return 0, meaning both are equally complex.
>
> Michael
>
>
> Am Di., 11. Juni 2019 um 14:21 Uhr schrieb Min-Yih Hsu via llvm-dev
> <llvm-dev at lists.llvm.org>:
> >
> > Hi,
> >
> > Recently I got a crash when I tried to analysis a program with
> ScalarEvolution AliasAnalysis(SCEV-AA for short). It turns out to be a
> (possibly) incorrect assertion inside the CompareSCEVComplexity routine.
> > The simplest solution would be just remove that assertion but I also
> found that the surrounding logics on calculating SCEV cost seems to be
> incorrect either. Thus I want to discuss with you folks about the best way
> to solve this.
> > Here are the details:
> >
> > Setup
> > Off-the-tip llvm-project, including clang and libcxx, built in full
> Debug build
> >
> > Input Program
> > Both the original C file and IR file are enclosed in the attachment.
The
> IR generation command is `clang -O1 -emit-llvm -S ptr_test.c -o
> ptr_test.O1.ll`
> >
> > Crashed Command
> > `opt -S -disable-output -basicaa -scev-aa -aa-eval -print-no-aliases
> ptr_test.O1.ll`
> > The core dump message is also in the attachments.
> >
> > Investigations
> > 1. SCEV-AA try to ‘minus' the SCEV expressions of the given two
> pointers(lib/Analysis/ScalarEvolutionAliasAnalysis.cpp:64)
> > 2. ScalarEvolution::getMinusSCEV will boil down into
> ScalarEvolution::getAddExpr. On line 2383 of
> lib/Analysis/ScalarEvolution.cpp, GroupByComplexity is invoked.
> > 3. CompareSCEVComplexity is eventually called to give a partial order
> between two SCEV expression.
> > 4. If there are two SCEVAddExpr that are located in different loops
> which don’t have any hierarchical relation, just like pointers in line 6
> and line 10 in the input program(i.e. ptr_test.c), it will violate the
> assertion in line 705 in lib/Analysis/ScalarEvolution.cpp.
> >
> > The point is that the assertion in line 705 doesn’t make sense in most
> of the cases: I don’t think there is any limitation imposed on arbitrary
> SCEV expressions to make the enclosing SCEVAddRec to be in the same loop(Or
> should we?).
> > As I mentioned earlier, the simplest solution is to remove this
> assertion, but still, the very assumption is still encoded in the
> surrounding code.
> > So I want to hear from you folks whether we should calculate the
> complexity of SCEVAddRec located in different loops. If yes, what’s the
> best way? For the latter question, currently I have an idea in my mind to
> compare their loop trip counts before doing the following lexicographic
> comparison.
> >
> > Thank you,
> >
> > B.R.
> > - Min
> >
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org
> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>

-- 
Min-Yih Hsu
Ph.D Student in ICS Department, University of California, Irvine (UCI).
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190612/a8a41e15/attachment.html>

The SCEVAA issue has come up before; see https://reviews.llvm.org/D41689 .  I
didn’t really continue pursuing it because SCEVAA is off by default… and the
discussion there concluded it’s likely not actually a bug in SCEVAA.  Instead,
-aa-eval and -basicaa shouldn’t be making those queries.

I think it doesn’t make sense to create a SCEV expression where the components
don’t have a dominance relationship.  It would be the same as constructing an
“Instruction” where the definitions of the operands don’t dominate the
instruction; it doesn’t have any meaning given the definition of SSA form.

If you do try to pursue changing CompareSCEVComplexity, it’s more complicated
than this discussion indicates.  It’s used as a sort comparator, so it needs to
be a strict weak ordering, so you’d need a strict ordering for domtree nodes. 
That’s possible (using getDFSNumIn() or something like that), but I’m not sure
how that interacts with domtree updates; I don’t think domtree updates keep the
children in a consistent order.

-Eli

From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of Min-Yih
Hsu via llvm-dev
Sent: Wednesday, June 12, 2019 10:53 AM
To: Michael Kruse <llvmdev at meinersbur.de>
Cc: llvm-dev <llvm-dev at lists.llvm.org>
Subject: [EXT] Re: [llvm-dev] [RFC][SCEV] Behavior of AddRec in
CompareSCEVComplexity

Hi,

Thanks for the input. In my ptr_test.O1.ll, the two loops should fall into the
last case due to loop rotations. And I think we should handle that case.
I propose to check the dominance relation between loop predecessor blocks of the
two loops if there is no dominance relation between their loop headers just like
case three. The only thing I'm not pretty sure is that is there guarantee to
exist dominance relation on their loop predecessor blocks. That is, either LPred
dominates RPred or RPred dominate LPred?

B.R.
- Min

On Tue, Jun 11, 2019 at 8:41 PM Michael Kruse <llvmdev at
meinersbur.de<mailto:llvmdev at meinersbur.de>> wrote:
Hi,

if I understand CompareSCEVComplexity  correctly, we just need some
deterministic order, not that important which one. We have three
cases:

1. LHead dominates RHead
2. RHead dominates LHead
3. There is no dominance relationship between the loops

LHead dominating RHead can either mean that R is nested inside L, or
the entire loop of L dominated R. From ptr_test.c that latter seems
the case, but LoopRotation might change this relation.

For the third case, we might just find another tie breaker rule, such
as a NumOps comparison afterwards or the order in which LoopInfo finds
them (this might be indeterministic). However, it might also be ok to
just return 0, meaning both are equally complex.

Michael


Am Di., 11. Juni 2019 um 14:21 Uhr schrieb Min-Yih Hsu via llvm-dev
<llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>:
>
> Hi,
>
> Recently I got a crash when I tried to analysis a program with
ScalarEvolution AliasAnalysis(SCEV-AA for short). It turns out to be a
(possibly) incorrect assertion inside the CompareSCEVComplexity routine.
> The simplest solution would be just remove that assertion but I also found
that the surrounding logics on calculating SCEV cost seems to be incorrect
either. Thus I want to discuss with you folks about the best way to solve this.
> Here are the details:
>
> Setup
> Off-the-tip llvm-project, including clang and libcxx, built in full Debug
build
>
> Input Program
> Both the original C file and IR file are enclosed in the attachment. The IR
generation command is `clang -O1 -emit-llvm -S ptr_test.c -o ptr_test.O1.ll`
>
> Crashed Command
> `opt -S -disable-output -basicaa -scev-aa -aa-eval -print-no-aliases
ptr_test.O1.ll`
> The core dump message is also in the attachments.
>
> Investigations
> 1. SCEV-AA try to ‘minus' the SCEV expressions of the given two
pointers(lib/Analysis/ScalarEvolutionAliasAnalysis.cpp:64)
> 2. ScalarEvolution::getMinusSCEV will boil down into
ScalarEvolution::getAddExpr. On line 2383 of lib/Analysis/ScalarEvolution.cpp,
GroupByComplexity is invoked.
> 3. CompareSCEVComplexity is eventually called to give a partial order
between two SCEV expression.
> 4. If there are two SCEVAddExpr that are located in different loops which
don’t have any hierarchical relation, just like pointers in line 6 and line 10
in the input program(i.e. ptr_test.c), it will violate the assertion in line 705
in lib/Analysis/ScalarEvolution.cpp.
>
> The point is that the assertion in line 705 doesn’t make sense in most of
the cases: I don’t think there is any limitation imposed on arbitrary SCEV
expressions to make the enclosing SCEVAddRec to be in the same loop(Or should
we?).
> As I mentioned earlier, the simplest solution is to remove this assertion,
but still, the very assumption is still encoded in the surrounding code.
> So I want to hear from you folks whether we should calculate the complexity
of SCEVAddRec located in different loops. If yes, what’s the best way? For the
latter question, currently I have an idea in my mind to compare their loop trip
counts before doing the following lexicographic comparison.
>
> Thank you,
>
> B.R.
> - Min
>
>
> _______________________________________________
> 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

--
Min-Yih Hsu
Ph.D Student in ICS Department, University of California, Irvine (UCI).
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190612/e8370ea4/attachment.html>

Hi,

Thanks for bringing up D41689, it's really helpful. I think Hal had made a
pretty neat summarized of this problem in that review: we definitely need a
better contract on the alias query interface regarding instruction
dominance.
I think it benefit not just on SCEVAA buy also BasicAA as well as AAEval,
where the last one is usually heavily used during prototyping and it's
crucial for it to deliver correct and precise alias information.

B.R.
- Min

On Wed, Jun 12, 2019 at 11:35 AM Eli Friedman <efriedma at quicinc.com>
wrote:
> The SCEVAA issue has come up before; see https://reviews.llvm.org/D41689
> .  I didn’t really continue pursuing it because SCEVAA is off by default…
> and the discussion there concluded it’s likely not actually a bug in
> SCEVAA.  Instead, -aa-eval and -basicaa shouldn’t be making those queries.
>
>
>
> I think it doesn’t make sense to create a SCEV expression where the
> components don’t have a dominance relationship.  It would be the same as
> constructing an “Instruction” where the definitions of the operands don’t
> dominate the instruction; it doesn’t have any meaning given the definition
> of SSA form.
>
>
>
> If you do try to pursue changing CompareSCEVComplexity, it’s more
> complicated than this discussion indicates.  It’s used as a sort
> comparator, so it needs to be a strict weak ordering, so you’d need a
> strict ordering for domtree nodes.  That’s possible (using getDFSNumIn() or
> something like that), but I’m not sure how that interacts with domtree
> updates; I don’t think domtree updates keep the children in a consistent
> order.
>
>
>
> -Eli
>
>
>
> *From:* llvm-dev <llvm-dev-bounces at lists.llvm.org> *On Behalf Of
*Min-Yih
> Hsu via llvm-dev
> *Sent:* Wednesday, June 12, 2019 10:53 AM
> *To:* Michael Kruse <llvmdev at meinersbur.de>
> *Cc:* llvm-dev <llvm-dev at lists.llvm.org>
> *Subject:* [EXT] Re: [llvm-dev] [RFC][SCEV] Behavior of AddRec in
> CompareSCEVComplexity
>
>
>
> Hi,
>
>
>
> Thanks for the input. In my ptr_test.O1.ll, the two loops should fall into
> the last case due to loop rotations. And I think we should handle that
case.
>
> I propose to check the dominance relation between loop predecessor blocks
> of the two loops if there is no dominance relation between their loop
> headers just like case three. The only thing I'm not pretty sure is
that is
> there guarantee to exist dominance relation on their loop predecessor
> blocks. That is, either LPred dominates RPred or RPred dominate LPred?
>
>
>
> B.R.
>
> - Min
>
>
>
> On Tue, Jun 11, 2019 at 8:41 PM Michael Kruse <llvmdev at
meinersbur.de>
> wrote:
>
> Hi,
>
> if I understand CompareSCEVComplexity  correctly, we just need some
> deterministic order, not that important which one. We have three
> cases:
>
> 1. LHead dominates RHead
> 2. RHead dominates LHead
> 3. There is no dominance relationship between the loops
>
> LHead dominating RHead can either mean that R is nested inside L, or
> the entire loop of L dominated R. From ptr_test.c that latter seems
> the case, but LoopRotation might change this relation.
>
> For the third case, we might just find another tie breaker rule, such
> as a NumOps comparison afterwards or the order in which LoopInfo finds
> them (this might be indeterministic). However, it might also be ok to
> just return 0, meaning both are equally complex.
>
> Michael
>
>
> Am Di., 11. Juni 2019 um 14:21 Uhr schrieb Min-Yih Hsu via llvm-dev
> <llvm-dev at lists.llvm.org>:
> >
> > Hi,
> >
> > Recently I got a crash when I tried to analysis a program with
> ScalarEvolution AliasAnalysis(SCEV-AA for short). It turns out to be a
> (possibly) incorrect assertion inside the CompareSCEVComplexity routine.
> > The simplest solution would be just remove that assertion but I also
> found that the surrounding logics on calculating SCEV cost seems to be
> incorrect either. Thus I want to discuss with you folks about the best way
> to solve this.
> > Here are the details:
> >
> > Setup
> > Off-the-tip llvm-project, including clang and libcxx, built in full
> Debug build
> >
> > Input Program
> > Both the original C file and IR file are enclosed in the attachment.
The
> IR generation command is `clang -O1 -emit-llvm -S ptr_test.c -o
> ptr_test.O1.ll`
> >
> > Crashed Command
> > `opt -S -disable-output -basicaa -scev-aa -aa-eval -print-no-aliases
> ptr_test.O1.ll`
> > The core dump message is also in the attachments.
> >
> > Investigations
> > 1. SCEV-AA try to ‘minus' the SCEV expressions of the given two
> pointers(lib/Analysis/ScalarEvolutionAliasAnalysis.cpp:64)
> > 2. ScalarEvolution::getMinusSCEV will boil down into
> ScalarEvolution::getAddExpr. On line 2383 of
> lib/Analysis/ScalarEvolution.cpp, GroupByComplexity is invoked.
> > 3. CompareSCEVComplexity is eventually called to give a partial order
> between two SCEV expression.
> > 4. If there are two SCEVAddExpr that are located in different loops
> which don’t have any hierarchical relation, just like pointers in line 6
> and line 10 in the input program(i.e. ptr_test.c), it will violate the
> assertion in line 705 in lib/Analysis/ScalarEvolution.cpp.
> >
> > The point is that the assertion in line 705 doesn’t make sense in most
> of the cases: I don’t think there is any limitation imposed on arbitrary
> SCEV expressions to make the enclosing SCEVAddRec to be in the same loop(Or
> should we?).
> > As I mentioned earlier, the simplest solution is to remove this
> assertion, but still, the very assumption is still encoded in the
> surrounding code.
> > So I want to hear from you folks whether we should calculate the
> complexity of SCEVAddRec located in different loops. If yes, what’s the
> best way? For the latter question, currently I have an idea in my mind to
> compare their loop trip counts before doing the following lexicographic
> comparison.
> >
> > Thank you,
> >
> > B.R.
> > - Min
> >
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org
> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
>
> --
>
> Min-Yih Hsu
>
> Ph.D Student in ICS Department, University of California, Irvine (UCI).
>

-- 
Min-Yih Hsu
Ph.D Student in ICS Department, University of California, Irvine (UCI).
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190612/353977c3/attachment.html>