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

> 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

Sanjoy and Andy, thanks a lot for your suggestions.

On Wed, Aug 24, 2016 at 8:53 AM, Andrew Trick <atrick at apple.com>
wrote:
>
>
> > 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
Combine the efforts of making the cleanup passes smarter and
simplifying the expanded code to make it more IR canonical looks like
a promising way. But I may not understand SCEVSimplifier you suggested
here correctly: The input of SCEVSimplifier is IR or SCEV? The code
generated by SCEVExpander is IR. If the input of SCEVSimplifier is IR,
how does it use SCEV routine internally?
>
>
> 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
>
Yes, it makes me think that the original idea in D12090 to try to
reuse the existing value directly may not be the right way to solve
the problem fundamentally. Reformulating SCEV to make it more
consistent with cannonical IR form is more promising. If only the IR
expanded is cannonical compared with existing IR, cleanup pass can
have big chance to catch the reuse.

Thanks,
Wei.

> On Aug 24, 2016, at 10:27 AM, Wei Mi <wmi at google.com> wrote:
> 
>> 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
>> 
> 
> Yes, it makes me think that the original idea in D12090 to try to
> reuse the existing value directly may not be the right way to solve
> the problem fundamentally. Reformulating SCEV to make it more
> consistent with cannonical IR form is more promising. If only the IR
> expanded is cannonical compared with existing IR, cleanup pass can
> have big chance to catch the reuse.
I was thinking that the SCEV expression should be reformulated in terms of
opaque nodes for existing IR values before expansion.

-Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160824/2e548133/attachment.html>

Hi Wei,

Wei Mi wrote:
 > Sanjoy and Andy, thanks a lot for your suggestions.
 >
 > On Wed, Aug 24, 2016 at 8:53 AM, Andrew Trick<atrick at apple.com> 
wrote:
 >>
 >>> 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
 >
 > Combine the efforts of making the cleanup passes smarter and
 > simplifying the expanded code to make it more IR canonical looks like
 > a promising way. But I may not understand SCEVSimplifier you suggested
 > here correctly: The input of SCEVSimplifier is IR or SCEV? The code
 > generated by SCEVExpander is IR. If the input of SCEVSimplifier is IR,
 > how does it use SCEV routine internally?

It accepts a ScalarEvolution instance that it uses internally to check
for equivalences, so the interface is:

class Simplifier {
public:
   Simplifier(ScalarEvolution &SE);
   Value *simplify(Value *);
};

or something like that.  Once we have this separation between
expansion and strength reduction, we can be more aggressive (than we
can reasonably be within SCEVExpander) about teaching Simplifier SCEV
based CSE rules.

In this scheme it would be more complicated to have a "expand, but
only if we can do it cheaply" type schemes.

-- Sanjoy