[llvm-dev] InstCombine, graph rewriting, Equality saturation

[Hal Finkel via llvm-dev]

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>