llvm dev - Aug 2016 - Request suggestions about how to remove redundencies caused by SCEV expansion fundementally

On Wed, Aug 24, 2016 at 3:07 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
>
>
> On Fri, Aug 19, 2016 at 3:57 PM, Wei Mi via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
>>
>> SCEV expansion sometimes generates redundent expr even if there is an
>> available expr which can be reused. The redundent exprs can be a lot
>> different from existing exprs so that existing cleanup passes cannot
>> remove them.
>>
>> https://llvm.org/bugs/show_bug.cgi?id=24920
>> https://llvm.org/bugs/show_bug.cgi?id=24442
>>
>> https://reviews.llvm.org/D12090 and https://reviews.llvm.org/D21313
>> already relieved the problem somewhat, but it is far from being solved
>> fundamentally. Recently we found another problematic case described in
>> https://llvm.org/bugs/show_bug.cgi?id=29065. And I believe I can
>> create more tests revealing similar problems.  In PR29065, I explained
>> why it is difficult to fix the problem by extending D12090 and D21313.
>> It is possible but still not very easy to fix the problem by enhancing
>> existing cleanup passes. So I am soliciting ideas here about how to
>> solve the problem in a more fundamental way.
>>
>> One thing I am always wondering is GCC also uses SCEV to calculate the
>> loop iteration number and why it doesn't have such problem. From my
>> limited knowledge about GCC's SCEV I guess it is because gcc only
has
>> the basic function of SCEV which can represent loop recursive expr
>> like llvm SCEVAddRecExpr part, SCEV operands are still gimple
>> variables and it doesn't have such complex transformations on SCEV
as
>> llvm does.
>
>
> This is not really correct :)
>
> In fact, at one point, GCC had *all of the possible scev* (sebastian worked
> a lot on it) ,including mixers, etc.
>
>
> The real thing here is that  GCC just doesn't do a lot of scev
expansion. It
> mainly uses it as an analysis, not as a code generation mechanism.
>
>
You are right, Thanks! I just looked at loop iteration number
computation in GCC. It only uses SCEV to identify simple induction
variables, represent them as affine expr, and then use those affine
exprs and their value ranges in loop to compute loop iteration number,
so it doesn't involve SCEV expansion.

Wei.

----- Original Message -----
> From: "Wei Mi via llvm-dev" <llvm-dev at lists.llvm.org>
> To: "Daniel Berlin" <dberlin at dberlin.org>
> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>, "David
Li" <davidxl at google.com>
> Sent: Wednesday, August 24, 2016 5:41:12 PM
> Subject: Re: [llvm-dev] Request suggestions about how to remove
redundencies caused by SCEV expansion fundementally
> 
> On Wed, Aug 24, 2016 at 3:07 PM, Daniel Berlin <dberlin at
dberlin.org>
> wrote:
> >
> >
> > On Fri, Aug 19, 2016 at 3:57 PM, Wei Mi via llvm-dev
> > <llvm-dev at lists.llvm.org> wrote:
> >>
> >> SCEV expansion sometimes generates redundent expr even if there is
> >> an
> >> available expr which can be reused. The redundent exprs can be a
> >> lot
> >> different from existing exprs so that existing cleanup passes
> >> cannot
> >> remove them.
> >>
> >> https://llvm.org/bugs/show_bug.cgi?id=24920
> >> https://llvm.org/bugs/show_bug.cgi?id=24442
> >>
> >> https://reviews.llvm.org/D12090 and
> >> https://reviews.llvm.org/D21313
> >> already relieved the problem somewhat, but it is far from being
> >> solved
> >> fundamentally. Recently we found another problematic case
> >> described in
> >> https://llvm.org/bugs/show_bug.cgi?id=29065. And I believe I can
> >> create more tests revealing similar problems.  In PR29065, I
> >> explained
> >> why it is difficult to fix the problem by extending D12090 and
> >> D21313.
> >> It is possible but still not very easy to fix the problem by
> >> enhancing
> >> existing cleanup passes. So I am soliciting ideas here about how
> >> to
> >> solve the problem in a more fundamental way.
> >>
> >> One thing I am always wondering is GCC also uses SCEV to calculate
> >> the
> >> loop iteration number and why it doesn't have such problem.
From
> >> my
> >> limited knowledge about GCC's SCEV I guess it is because gcc
only
> >> has
> >> the basic function of SCEV which can represent loop recursive expr
> >> like llvm SCEVAddRecExpr part, SCEV operands are still gimple
> >> variables and it doesn't have such complex transformations on
SCEV
> >> as
> >> llvm does.
> >
> >
> > This is not really correct :)
> >
> > In fact, at one point, GCC had *all of the possible scev*
> > (sebastian worked
> > a lot on it) ,including mixers, etc.
> >
> >
> > The real thing here is that  GCC just doesn't do a lot of scev
> > expansion. It
> > mainly uses it as an analysis, not as a code generation mechanism.
> >
> >
> 
> You are right, Thanks! I just looked at loop iteration number
> computation in GCC. It only uses SCEV to identify simple induction
> variables, represent them as affine expr, and then use those affine
> exprs and their value ranges in loop to compute loop iteration
> number,
> so it doesn't involve SCEV expansion.
So how are you thinking about moving forward here?

 -Hal
> 
> Wei.
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

On Sat, Aug 27, 2016 at 7:07 PM, Hal Finkel <hfinkel at anl.gov>
wrote:
> ----- Original Message -----
>> From: "Wei Mi via llvm-dev" <llvm-dev at
lists.llvm.org>
>> To: "Daniel Berlin" <dberlin at dberlin.org>
>> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>,
"David Li" <davidxl at google.com>
>> Sent: Wednesday, August 24, 2016 5:41:12 PM
>> Subject: Re: [llvm-dev] Request suggestions about how to remove
redundencies caused by SCEV expansion fundementally
>>
>> On Wed, Aug 24, 2016 at 3:07 PM, Daniel Berlin <dberlin at
dberlin.org>
>> wrote:
>> >
>> >
>> > On Fri, Aug 19, 2016 at 3:57 PM, Wei Mi via llvm-dev
>> > <llvm-dev at lists.llvm.org> wrote:
>> >>
>> >> SCEV expansion sometimes generates redundent expr even if
there is
>> >> an
>> >> available expr which can be reused. The redundent exprs can be
a
>> >> lot
>> >> different from existing exprs so that existing cleanup passes
>> >> cannot
>> >> remove them.
>> >>
>> >> https://llvm.org/bugs/show_bug.cgi?id=24920
>> >> https://llvm.org/bugs/show_bug.cgi?id=24442
>> >>
>> >> https://reviews.llvm.org/D12090 and
>> >> https://reviews.llvm.org/D21313
>> >> already relieved the problem somewhat, but it is far from
being
>> >> solved
>> >> fundamentally. Recently we found another problematic case
>> >> described in
>> >> https://llvm.org/bugs/show_bug.cgi?id=29065. And I believe I
can
>> >> create more tests revealing similar problems.  In PR29065, I
>> >> explained
>> >> why it is difficult to fix the problem by extending D12090 and
>> >> D21313.
>> >> It is possible but still not very easy to fix the problem by
>> >> enhancing
>> >> existing cleanup passes. So I am soliciting ideas here about
how
>> >> to
>> >> solve the problem in a more fundamental way.
>> >>
>> >> One thing I am always wondering is GCC also uses SCEV to
calculate
>> >> the
>> >> loop iteration number and why it doesn't have such
problem. From
>> >> my
>> >> limited knowledge about GCC's SCEV I guess it is because
gcc only
>> >> has
>> >> the basic function of SCEV which can represent loop recursive
expr
>> >> like llvm SCEVAddRecExpr part, SCEV operands are still gimple
>> >> variables and it doesn't have such complex transformations
on SCEV
>> >> as
>> >> llvm does.
>> >
>> >
>> > This is not really correct :)
>> >
>> > In fact, at one point, GCC had *all of the possible scev*
>> > (sebastian worked
>> > a lot on it) ,including mixers, etc.
>> >
>> >
>> > The real thing here is that  GCC just doesn't do a lot of scev
>> > expansion. It
>> > mainly uses it as an analysis, not as a code generation mechanism.
>> >
>> >
>>
>> You are right, Thanks! I just looked at loop iteration number
>> computation in GCC. It only uses SCEV to identify simple induction
>> variables, represent them as affine expr, and then use those affine
>> exprs and their value ranges in loop to compute loop iteration
>> number,
>> so it doesn't involve SCEV expansion.
>
> So how are you thinking about moving forward here?
Shorterm I feel easy to try is to enhance the expansion of
SCEVNAryExpr: As suggested by Andy, for a new SCEV C = A1 + A2 + B
which is generated by getAddExpr(A, B), adding an opaque value node
somewhere to record C equals to opaque_value = Value_A + Value_B. It
is possible that B doesn't have Value_B recorded in ExprValueMap. Need
to find some representation saying opaque_value = Value_A + expand(B).
This will relieve the problem in PR29065. I may extend ExprValueMap
from recording a single value to some form more flexible to represent
various expr.

Longterm, enhancing cleanup, especially reassociate is something worth
doing because it may be generally helpful (not just for scev
expansion). From my current experience, a large part of expansion
redundency uncleaned is caused by some weakness of reassociation,
especially the problem mentioned in
http://lists.llvm.org/pipermail/llvm-dev/2015-May/085406.html and
problem related with multiple getelementptr. NaryReassociate solved
some common problems but there are more. The paper mentioned in Pact08
may be worthy to try.

By the way, to answer Andy's question. I did some experiment using the
testcase in PR29065 to see if we regenerate SCEV for existing and
expanded IR, whether it will be easier to check equivalence suppose we
have SCEV cse rules. The reassociated order of generated SCEVs seems
more consistent. For C= A1 + A2 + B above, the SCEV corresponding to
A1 + A2 has the same computation sequence with the SCEV corresponding
to A (A1, A2 and A are all complex SCEV themselves). However, during
expansion, the cost of searching existing IR, convert them to SCEV and
see if they are equivalent with the SCEV to be expanded looks
expensive. And we need to add complex rules to define SCEV equivalence
from CSE perspective. So I think the method provides me one more
alternative, but I am not going to persue it right away.

This is the ideas what I currently have. More suggestions are welcomed.

Thanks,
Wei.