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

[Daniel Berlin via llvm-dev]

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> 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 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
> 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/20170908/468dc018/attachment.html>