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

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

On Wed, Aug 24, 2016 at 12:01 PM, Sanjoy Das
<sanjoy at playingwithpointers.com> wrote:
> 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.
To rephrase it and see if I understand it correctly:

Existing Value A;

Expanded Value B (B is identical with A, but in a different form);

So we can convert both A and B to SCEV again and compare their
equivalence and use the result to guide strength reduction. It is like
to enhance existing cleanup pass using the SCEV CSE rules.

Or the idea of simplify is to transform B back to the form close to A
with SCEV knowledge?

It sounds like an interesting idea.

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

> On Aug 24, 2016, at 1:20 PM, Wei Mi <wmi at google.com> wrote:
> 
> On Wed, Aug 24, 2016 at 12:01 PM, Sanjoy Das
> <sanjoy at playingwithpointers.com> wrote:
>> 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.
> 
> To rephrase it and see if I understand it correctly:
> 
> Existing Value A;
> 
> Expanded Value B (B is identical with A, but in a different form);
> 
> So we can convert both A and B to SCEV again and compare their
> equivalence and use the result to guide strength reduction. It is like
> to enhance existing cleanup pass using the SCEV CSE rules.
> 
> Or the idea of simplify is to transform B back to the form close to A
> with SCEV knowledge?
> 
> It sounds like an interesting idea.

I would need to see how this solves the bugs you posted earlier, like
https://llvm.org/bugs/show_bug.cgi?id=24920
<https://llvm.org/bugs/show_bug.cgi?id=24920>

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

Hi Wei,

Wei Mi wrote:
 > To rephrase it and see if I understand it correctly:
 >
 > Existing Value A;
 >
 > Expanded Value B (B is identical with A, but in a different form);
 >
 > So we can convert both A and B to SCEV again and compare their
 > equivalence and use the result to guide strength reduction. It is like
 > to enhance existing cleanup pass using the SCEV CSE rules.

Yes.  And we don't necessarily have to worry about exact matches
either, we can (for instance) check if getMinusSCEV(getSCEV(A),
getSCEV(B)) is a constant, and use that to cheaply expand B.

 > Or the idea of simplify is to transform B back to the form close to A
 > with SCEV knowledge?

No, that's not what I had in mind.

-- Sanjoy