llvm dev - Sep 2017 - InstCombine, graph rewriting, Equality saturation

Just thinking out loud…. I’m really not familiar with the vast majority of what
instcombine does, so please excuse me if my naiveté is too obvious. I can’t help
but notice all of the uses of ‘and’ in Daniel B’s description of what
instcombine is right now:
> On Sep 8, 2017, at 11:27 PM, Daniel Berlin via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> FWIW, Before getting to "how to do it", I think InstCombine needs
an actual goal.
> Right now it's "do a bunch of instruction combination and
canonicalization and random kinds of semi-local optimization with some weird
analysis and other stuff in the middle.
> Iterate this as hard as we can"
> Nobody can really draw any real dividing line for what should be there or
not except based on how easy or expensive it is to shove it in.
> That's a recipe for pass creep.
This makes me wonder… is it sensible to be talking about splitting up
instcombine into multiple separate passes? Would such a thing even be possible?
For example, split by functionality into separate passes that each do one of:
* instruction combinations
* canonicalization
* semi-local optimizations
* etc…

 Or something like that.

 As separate passes, each would probably have a natural way to be implemented
effectively and those implementations might vary.

-Daniel

---
Daniel Neilson, Ph.D.
Azul Systems

On Mon, Sep 11, 2017 at 8:14 AM, Daniel Neilson via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
>
> Just thinking out loud…. I’m really not familiar with the vast majority of
> what instcombine does, so please excuse me if my naiveté is too obvious. I
> can’t help but notice all of the uses of ‘and’ in Daniel B’s description of
> what instcombine is right now:
>
> > On Sep 8, 2017, at 11:27 PM, Daniel Berlin via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
> >
> > FWIW, Before getting to "how to do it", I think InstCombine
needs an
> actual goal.
> > Right now it's "do a bunch of instruction combination and
> canonicalization and random kinds of semi-local optimization with some
> weird analysis and other stuff in the middle.
> > Iterate this as hard as we can"
> > Nobody can really draw any real dividing line for what should be there
> or not except based on how easy or expensive it is to shove it in.
> > That's a recipe for pass creep.
>
> This makes me wonder… is it sensible to be talking about splitting up
> instcombine into multiple separate passes? Would such a thing even be
> possible? For example, split by functionality into separate passes that
> each do one of:
> * instruction combinations
> * canonicalization
> * semi-local optimizations
> * etc…
>
>  Or something like that.
>
>  As separate passes, each would probably have a natural way to be
> implemented effectively and those implementations might vary.
>
One obstacle to that is that currently instcombine has an internal
fixed-point iteration that it does.

So when splitting it into separate passes we would need to either add
fixed-point iteration to the pass manager running the separate instcombine
passes (extending the pass management in this way is doable and has been
explored in the past, e.g. https://www.youtube.com/watch?v=c7iP43an5_Q ) or
demonstrate/measure that we don't regress without the fixed-point iteration
across separate instcombine passes.

-- Sean Silva

>
> -Daniel
>
> ---
> Daniel Neilson, Ph.D.
> Azul Systems
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170911/1dcbd156/attachment.html>

Or the analysis need to be thought about and extended to not require fix
pointing to get the same end result out of the other end of llvm.

In situations like this, the real question is "does the same kind of
optimized code come out the other end", not "do we perfectly match
every
little optimization on a per-pass basis".
Or at least, that's the answer i got about GVN.
(because trying to replace a do-everything pass that fixpoints with split
up passes rarely can match it perfectly  Too many second order effects.  It
shouldn't be your goal)


On Mon, Sep 11, 2017 at 8:50 AM, Sean Silva <chisophugis at gmail.com>
wrote:
>
>
> On Mon, Sep 11, 2017 at 8:14 AM, Daniel Neilson via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>>
>> Just thinking out loud…. I’m really not familiar with the vast majority
>> of what instcombine does, so please excuse me if my naiveté is too
obvious.
>> I can’t help but notice all of the uses of ‘and’ in Daniel B’s
description
>> of what instcombine is right now:
>>
>> > On Sep 8, 2017, at 11:27 PM, Daniel Berlin via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>> >
>> > FWIW, Before getting to "how to do it", I think
InstCombine needs an
>> actual goal.
>> > Right now it's "do a bunch of instruction combination and
>> canonicalization and random kinds of semi-local optimization with some
>> weird analysis and other stuff in the middle.
>> > Iterate this as hard as we can"
>> > Nobody can really draw any real dividing line for what should be
there
>> or not except based on how easy or expensive it is to shove it in.
>> > That's a recipe for pass creep.
>>
>> This makes me wonder… is it sensible to be talking about splitting up
>> instcombine into multiple separate passes? Would such a thing even be
>> possible? For example, split by functionality into separate passes that
>> each do one of:
>> * instruction combinations
>> * canonicalization
>> * semi-local optimizations
>> * etc…
>>
>>  Or something like that.
>>
>>  As separate passes, each would probably have a natural way to be
>> implemented effectively and those implementations might vary.
>>
>
> One obstacle to that is that currently instcombine has an internal
> fixed-point iteration that it does.
>
> So when splitting it into separate passes we would need to either add
> fixed-point iteration to the pass manager running the separate instcombine
> passes (extending the pass management in this way is doable and has been
> explored in the past, e.g. https://www.youtube.com/watch?v=c7iP43an5_Q )
> or demonstrate/measure that we don't regress without the fixed-point
> iteration across separate instcombine passes.
>
> -- Sean Silva
>
>
>>
>> -Daniel
>>
>> ---
>> Daniel Neilson, Ph.D.
>> Azul Systems
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170911/dcb2800d/attachment.html>

On 09/11/2017 10:50 AM, Sean Silva via llvm-dev wrote:
>
>
> On Mon, Sep 11, 2017 at 8:14 AM, Daniel Neilson via llvm-dev 
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>> wrote:
>
>
>     Just thinking out loud…. I’m really not familiar with the vast
>     majority of what instcombine does, so please excuse me if my
>     naiveté is too obvious. I can’t help but notice all of the uses of
>     ‘and’ in Daniel B’s description of what instcombine is right now:
>
>     > On Sep 8, 2017, at 11:27 PM, Daniel Berlin via llvm-dev
>     <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>> wrote:
>     >
>     > FWIW, Before getting to "how to do it", I think
InstCombine
>     needs an actual goal.
>     > Right now it's "do a bunch of instruction combination and
>     canonicalization and random kinds of semi-local optimization with
>     some weird analysis and other stuff in the middle.
>     > Iterate this as hard as we can"
>     > Nobody can really draw any real dividing line for what should be
>     there or not except based on how easy or expensive it is to shove
>     it in.
>     > That's a recipe for pass creep.
>
>     This makes me wonder… is it sensible to be talking about splitting
>     up instcombine into multiple separate passes? Would such a thing
>     even be possible? For example, split by functionality into
>     separate passes that each do one of:
>     * instruction combinations
>     * canonicalization
>     * semi-local optimizations
>     * etc…
>
The problem is that all of these are really the same thing. Almost all 
canonicalizations are also simplifications, the common underlying factor 
being that they're mostly-local transformations that likely enable other 
optimizations.
>
>      Or something like that.
>
>      As separate passes, each would probably have a natural way to be
>     implemented effectively and those implementations might vary.
>
>
> One obstacle to that is that currently instcombine has an internal 
> fixed-point iteration that it does.
>
> So when splitting it into separate passes we would need to either add 
> fixed-point iteration to the pass manager running the separate 
> instcombine passes (extending the pass management in this way is 
> doable and has been explored in the past, e.g. 
> https://www.youtube.com/watch?v=c7iP43an5_Q ) or demonstrate/measure 
> that we don't regress without the fixed-point iteration across 
> separate instcombine passes.
I agree, but I'll add that I view the fixed-point iteration here to be 
an asset. It increases the robustness and consistency of the compiler, 
and allows later passes to depend on the canonicalization (*) without 
worrying about phase-ordering effects (**).

(*) In my experience, the largest problem we have in this regard is our 
lack of documentation on what our canonical form is.
(**) To be clear, we still have phase-ordering effects within 
InstCombine. Using a better system for dealing with the rewriting rules, 
I hope, will help. Nevertheless, these effects are much rarer than if we 
ran InstCombine only as discrete passe.

I'd like to see us do more fixed-point iteration in our optimization 
pipeline, and our past work has shown this would be practical (i.e., 
only a few iterations will be needed in practice), but even that won't 
remove the advantages of using a fixed-point iteration within InstCombine.

Regardless, I think that if we had a model for what InstCombine did 
(i.e., as a graph-rewriting system), then it would be clear what could 
be part of that system and what couldn't. Otherwise, I think that the 
real challenge here is figuring out the underlying structural 
foundations to make the process efficient and sound.

  -Hal
>
> -- Sean Silva
>
>
>     -Daniel
>
>     ---
>     Daniel Neilson, Ph.D.
>     Azul Systems
>
>     _______________________________________________
>     LLVM Developers mailing list
>     llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>     http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>     <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170911/23ecd0fb/attachment.html>