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

> 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

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>

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
>

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