[llvm-dev] InstCombine, graph rewriting, Equality saturation
Hal Finkel via llvm-dev
llvm-dev at lists.llvm.org
Mon Sep 11 19:34:50 PDT 2017
On 09/11/2017 03:50 PM, Craig Topper wrote:
> The sinking in InstCombine also has a bogus single use check on the
> front of it. Why does it matter how many uses there are as long as
> they are all in the same basic block?
It shouldn't. At least at this point in time, we should be able to do
this in a better way. The other problem with this transformation for
loads, besides being inefficient and seemingly over specific, is that it
is not information preserving (it sinks loads that we then can't
re-hoist). As a result, we should consider doing this later in the
pipeline (or preserving the point-of-validity information some other way).
-Hal
>
> ~Craig
>
> On Mon, Sep 11, 2017 at 1:32 PM, Sean Silva via llvm-dev
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>
>
>
> On Mon, Sep 11, 2017 at 9:48 AM, Hal Finkel <hfinkel at anl.gov
> <mailto:hfinkel at anl.gov>> wrote:
>
>
> On 09/11/2017 10:50 AM, Sean Silva via llvm-dev wrote:
>>
>>
>> On Mon, Sep 11, 2017 at 8:14 AM, Daniel Neilson via llvm-dev
>> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>>
>>
>> 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
>> <mailto: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…
>>
>
> The problem is that all of these are really the same thing.
> Almost all canonicalizations are also simplifications, the
> common underlying factor being that they're mostly-local
> transformations that likely enable other optimizations.
>
>>
>> Or something like that.
>>
>> As separate passes, each would probably have a natural
>> way to be implemented effectively and those
>> implementations might vary.
>>
>>
>> One obstacle to that is that currently instcombine has an
>> internal fixed-point iteration that it does.
>>
>> So when splitting it into separate passes we would need to
>> either add fixed-point iteration to the pass manager running
>> the separate instcombine passes (extending the pass
>> management in this way is doable and has been explored in the
>> past, e.g. https://www.youtube.com/watch?v=c7iP43an5_Q
>> <https://www.youtube.com/watch?v=c7iP43an5_Q> ) or
>> demonstrate/measure that we don't regress without the
>> fixed-point iteration across separate instcombine passes.
>
> I agree, but I'll add that I view the fixed-point iteration
> here to be an asset. It increases the robustness and
> consistency of the compiler, and allows later passes to depend
> on the canonicalization (*) without worrying about
> phase-ordering effects (**).
>
> (*) In my experience, the largest problem we have in this
> regard is our lack of documentation on what our canonical form is.
> (**) To be clear, we still have phase-ordering effects within
> InstCombine. Using a better system for dealing with the
> rewriting rules, I hope, will help. Nevertheless, these
> effects are much rarer than if we ran InstCombine only as
> discrete passe.
>
> I'd like to see us do more fixed-point iteration in our
> optimization pipeline, and our past work has shown this would
> be practical (i.e., only a few iterations will be needed in
> practice), but even that won't remove the advantages of using
> a fixed-point iteration within InstCombine.
>
> Regardless, I think that if we had a model for what
> InstCombine did (i.e., as a graph-rewriting system), then it
> would be clear what could be part of that system and what
> couldn't. Otherwise, I think that the real challenge here is
> figuring out the underlying structural foundations to make the
> process efficient and sound.
>
>
> As a data point for this, I did a quick walkthrough of the
> top-level of instcombine, and one thing that stuck out to me is
> that it tries to sink instructions in certain "easy" scenarios.
> That doesn't fit a graph rewriting system.
>
> As a side note, TryToSinkInstruction does a whole-BB scan to check
> safety for sinking loads, which will go quadratic (in the number
> of loads) on an input like:
>
> ```
> void use(int);
> void foo(int *p, int *q, bool b) {
> int p0 = p[0];
> int p1 = p[1];
> int p2 = p[2];
> int p3 = p[3];
> if (b) {
> use(p0);
> use(p1);
> use(p2);
> use(p3);
> }
> }
> ```
> (script attached)
>
> The commit where it was introduced
> (https://reviews.llvm.org/rL18677
> <https://reviews.llvm.org/rL18677> /
> https://reviews.llvm.org/rL18692
> <https://reviews.llvm.org/rL18692> yes that's from 2004) indicated
> that it actually caught a bunch of cases in SPEC, but it isn't
> clear that it's really providing much value integrated into the
> fixed-point iteration compared to an appropriate standalone global
> code motion pass (which would not have the quadratic complexity
> and would be more general to boot).
>
> -- Sean Silva
>
>
>
> -Hal
>
>>
>> -- Sean Silva
>>
>>
>> -Daniel
>>
>> ---
>> Daniel Neilson, Ph.D.
>> Azul Systems
>>
>> _______________________________________________
>> 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 <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>
>
> --
> Hal Finkel
> Lead, Compiler Technology and Programming Languages
> Leadership Computing Facility
> Argonne National Laboratory
>
> _______________________________________________ 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>
>
--
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/20170911/4faac2cf/attachment.html>
More information about the llvm-dev
mailing list