[llvm-dev] failing to optimize boolean ops on cmps
Hal Finkel via llvm-dev
llvm-dev at lists.llvm.org
Fri Jul 14 08:45:45 PDT 2017
On 07/14/2017 10:27 AM, Daniel Berlin wrote:
> On Thu, Jul 13, 2017 at 6:18 PM, Hal Finkel <hfinkel at anl.gov
> <mailto: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
> 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.
AFAIK, that's true.
> . 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
I think you're done when you get everything that you have that fits into
a model of local transformations and that should be run to a fixed
point. Certainly an interesting question, but I suspect that the
practical answer is "what's in InstCombine." To do more in this sense
probably requires some more-general scheme (e.g. equality saturation).
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the llvm-dev