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

[John Regehr via llvm-dev]

I was thinking that the role of InstCombine would become clarified 
through the design of the table-based mechanism that Hal outlines. It 
needs to hit a sweet spot that is reasonably powerful (able to 
implement, say, 90% of today's InstCombine) and very efficient. At that 
point we have a pass that won't creep much, since it's clearly not 
general-purpose, and then there's a pile of residual C++ that isn't a 
lot of fun but at least it's a lot smaller than the 30,0000 lines of 
code we have now.

I'm not saying it's the answer, but Alive is an example of a restricted 
class of transformations that captures a lot of InstCombine-ish things, 
that has verification support, and that translates into relatively 
efficient C++.

John



On 9/8/17 10:27 PM, Daniel Berlin via llvm-dev 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.
>
> If instcombine becomes the thing that does everything, then everyone
> will want it to run every time they generate a bunch more code. We
> already see this now, where people want to add more optimizations to
> instcombine, and then more  runs of those. Right now there are 4 or 5
> runs in most pipelines (if i'm counting right :P).
>
> If it becomes a more expensive, globally encompassing graph rewriting
> pass, it almost certainly needs to be able to be run less than 5 times
> per function.  Whether by making other passes better at whatever use
> cases it drops, or deciding we get the same result anyway, or whatever.
> If it becomes a cheap, local graph-rewriting pass, running it more is
> not so bad, but other passes may need to be better at the more global
> use cases that are dropped.
>
> But i'd suggest that step 1 is actually define what we really are trying
> to get out of it, and what we want it to tackle, before we decide how it
> should tackle them.
>
>
>
> On Fri, Sep 8, 2017 at 8:31 PM, John Regehr via llvm-dev
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>
>         I'd love to see a solution where most of the transformations
>         were specified in TableGen files and:
>           1. We, as a result, had an easy way to convert these into a
>         form where some SMT-solver-based checker could certify correctness.
>           2. We, as a result, has an easy way to somehow check
>         soundness, as a rewrite system, so we'd know it would reach a
>         fixed point for all inputs.
>           3. We, as a result, reduced the number of lines of code we
>         need to maintain for these peephole optimizations.
>           4. We, as a result, could generate efficient code for matching
>         the patterns using some automaton technique for minimizing
>         unnecessary visiting of instructions.
>
>
>     YES to all of this (except TableGen :).
>
>     It should also be possible to find chains of transformations that
>     fire in sequence and make them happen all at once, avoiding
>     intermediate results and associated allocations/deallocations. Nuno
>     has some ideas along these lines.
>
>         I'm not sure how closely it matches what we would need, but
>         Stratego/XT comes to mind in terms of prior art (now here:
>         http://www.metaborg.org/en/latest/
>         <http://www.metaborg.org/en/latest/>). There's been a lot of
>         work over the years on terminating graph rewriting systems in
>         compilers.
>
>
>     I went down this rabbit hole a few years ago, there's indeed a lot
>     of existing material.
>
>     John
>
>
>     _______________________________________________
>     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
>