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

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. Correct me if I say something wrong here. I am also
wondering if llvm doesn't have such complex transformations on SCEV
(including so many simplifications and canonicalizations), what will
be missing? Why IR based canonicalization and simplification not
enough?

Thanks,
Wei Mi.

Hi Wei,

I've not seen GCC's SCEV so I cannot make a comparative comment here
(maybe Chris, Andy or Dan can chime in here), but I personally am in
the "make the cleanup passes smarter" camp.  We can also try to make
SCEV expansion smarter -- not by putting more things in SCEVExpander
(it is already complex enough!), but by splitting out a dedicated
SCEVSimplifier that you invoke on code generated from SCEVExpander to
strength reduce it.  SCEVSimplifier can then internally use routines
in SCEV, so that it is "as smart as" SCEV in most cases.

-- Sanjoy

> On Aug 23, 2016, at 11:30 PM, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
> 
> Hi Wei,
> 
> I've not seen GCC's SCEV so I cannot make a comparative comment
here
> (maybe Chris, Andy or Dan can chime in here), but I personally am in
> the "make the cleanup passes smarter" camp.  We can also try to
make
> SCEV expansion smarter -- not by putting more things in SCEVExpander
> (it is already complex enough!), but by splitting out a dedicated
> SCEVSimplifier that you invoke on code generated from SCEVExpander to
> strength reduce it.  SCEVSimplifier can then internally use routines
> in SCEV, so that it is "as smart as" SCEV in most cases.
> 
> — Sanjoy
SCEV is super useful as an analysis without SCEVExpander. The only real issue
with SCEV itself is invalidating the expressions.

I’ve always thought SCEVExpander is very dangerous to use directly. Ideally the
SCEV expression should always be reformulated based on existing IR values before
expanding. It would be nice if that was provided as a layer of functionality on
top of SCEVExpander.

-Andy

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160824/3d191a77/attachment.html>

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.