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

[Hal Finkel via llvm-dev]

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 
> 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.

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 
> want".
>

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).

  -Hal

-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170714/39cede7d/attachment-0001.html>