[llvm-dev] failing to optimize boolean ops on cmps

[Daniel Berlin via llvm-dev]

On Thu, Jul 13, 2017 at 6:18 PM, Hal Finkel <hfinkel at anl.gov> wrote:

>
> On 07/13/2017 06:40 PM, Daniel Berlin via llvm-dev wrote:
>
> Ah yes, it can only return one instruction and you need two.
>
> NewGVN could still handle it if instsimplify was changed to return the
> right binary operators because it has infrastructure that can handle
> insertion.
> (it would need a little work).
>
>
> (At this point, InstCombine seems to have become worse to me than GCC's
> combining infrastructure, so i'd really like to see if we can stop putting
> things there. Otherwise, we just go farther down the path of 'let's  just
> make everything one big graph rewrite)
>
>
> Perhaps something of a digression:
>
> My general impression is that if InstCombine were actually doing a
> principled graph rewrite, then we wouldn't have these problems.
>

Define "these problems"?

:)
I mean, you are right it would be better in general.
But the notion of adding more and more graph rewrites to a single part of
the compiler, to get second/third/etc order effects, is endless.  Pretty
much everything can be expressed as a set of graph rewrites.  There is no
principled stopping point.  IE You have to decide what you want each pass
to do, and if you have one pass whose job is "perform all possible graph
rewrites", that pass is in fact, your compiler :)

That's not such a bad thing, mind you, there are entire libraries/languages
centered around this (see, e.g., stratego,
https://en.wikipedia.org/wiki/Stratego/XT and
http://www.metaborg.org/en/latest/source/langdev/meta/lang/stratego/strategoxt/index.html),
but it should be a deliberate thing.


> e problem we have, however, is that we have phase-ordering problems (even
> within the fixed-point iteration scheme): Patterns being matched depend on
> a canonical form, instructions nearly matching those patterns might be
> created, and then suboptimally consumed (i.e. further transformed), before
> being subject to the canonicalizing transformation(s) that would make the
> better pattern actually match.
>
> Except for TableGen'ing the whole thing, and making an actual graph
> automaton to match the patterns, it's not clear to me how to efficiently
> fix this
>

That is what people used to do, make parsing grammars, etc.
Stratego is also  quite efficient at term rewriting, from what i remember.

. In the mean time, what we've been doing in practice, is that we have
> InstCombine patterns depend on canonical forms, until we hit some
> phase-ordering problem, and then we extend the pattern in question to match
> some non-canonical forms. We might do this here as well (if that's the
> problem here), but at some point I suspect we'll end up redoing everything.
>

The question i would have is "how do you know when you are done?". As I
said, pretty much everything can be expressed as a graph transform, and the
more it gets added here, the more people want to run instcombine 50 times
because cse/gvn/you name it "doesn't do what they want".
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170714/54ebf781/attachment.html>