[llvm-dev] InstCombine, graph rewriting, Equality saturation
John Regehr via llvm-dev
llvm-dev at lists.llvm.org
Fri Sep 8 21:52:08 PDT 2017
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
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/>). There's been a lot of
> work over the years on terminating graph rewriting systems in
> I went down this rabbit hole a few years ago, there's indeed a lot
> of existing material.
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
More information about the llvm-dev