<div dir="ltr">FWIW, Before getting to "how to do it", I think InstCombine needs an actual goal.<div>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.</div><div>Iterate this as hard as we can"</div><div>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.</div><div>That's a recipe for pass creep.</div><div><br></div><div>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).</div><div><br></div><div>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.</div><div>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.</div><div><br></div><div>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.</div><div><br></div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Sep 8, 2017 at 8:31 PM, John Regehr via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I'd love to see a solution where most of the transformations were specified in TableGen files and:<br>
  1. We, as a result, had an easy way to convert these into a form where some SMT-solver-based checker could certify correctness.<br>
  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.<br>
  3. We, as a result, reduced the number of lines of code we need to maintain for these peephole optimizations.<br>
  4. We, as a result, could generate efficient code for matching the patterns using some automaton technique for minimizing unnecessary visiting of instructions.<br>
</blockquote>
<br></span>
YES to all of this (except TableGen :).<br>
<br>
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.<span class=""><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
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: <a href="http://www.metaborg.org/en/latest/" rel="noreferrer" target="_blank">http://www.metaborg.org/en/lat<wbr>est/</a>). There's been a lot of work over the years on terminating graph rewriting systems in compilers.<br>
</blockquote>
<br></span>
I went down this rabbit hole a few years ago, there's indeed a lot of existing material.<br>
<br>
John<div class="HOEnZb"><div class="h5"><br>
<br>
______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
</div></div></blockquote></div><br></div>