[llvm-dev] [RFC] PT.2 Add IR level interprocedural outliner for code size.

[Daniel Berlin via llvm-dev]

They normalize, but at least NewGVN (and GVNSink, which is closer to how
the outliners work) there are opportunities it can discover for outlining
that won't be CSE'd.

In particular, if you have two groups of instructions with the same value,
but one doesn't dominate the other, you could outline them, but we wouldn't
eliminate them.

(We could speculate them in some cases if we wanted to get to one copy in a
single function, but they can *always* be outlined into a function call).


On Wed, Sep 27, 2017 at 6:07 PM, Matthias Braun via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

>
> On Sep 27, 2017, at 3:23 PM, Davide Italiano via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> On Wed, Sep 27, 2017 at 9:28 AM, Jessica Paquette via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
>
>
> I think that, given previous discussion on the topic, we might want a split
> like this:
>
> (1) Search structure
>
> Suffix tree or suffix array.
>
> (2) Numbering/mapping/congruence scheme
>
> Every outliner should implement a function that maps instructions (or
> whatever structure you want to outline, crazy thoughts…) to integers. That
> should be passed to the search structure, which will return a list of
> repeated sequences.
>
> The MachineOutliner currently has an “InstructionMapper” struct in it. I
> think we can probably build on that struct so that we can choose different
> mapping schemes.
>
> (3) Cost model/candidate selection scheme
>
> Every outliner should implement a function that returns the outlining cost
> or benefit of a candidate. In the MachineOutliner, this is a joint effort
> between the pass and the target.
>
> (4) Outlining scheme
>
> Every outliner should implement a function that actually performs
> outlining.
> That is, we should have a function that replaces each instance of a
> repeated
> sequence of instructions with a call to a newly-created function. In the
> MachineOutliner, the method by which we do this is decided on by the
> target.
>
> So, we at the very least might want an interface that implements something
> like
>
> unsigned mapInstructions(…);
> unsigned getOutliningCost(…);
> unsigned findCandidates(…);
> bool outline(…);
>
>
> Hi Jessica, I tend to agree we should try to maximize code reuse in
> this context, and I think yours is a good step forward. In particular,
> I'm particularly confident the `findCandidates()` bits should be
> split.
> That said, do we really want encapsulate the logic for finding
> candidates into an interface? It's unclear whether it should live but
> it seems much more akin to the stuff living in Transforms/Utils than a
> proper interface.
> So, IMHO it's much more suitable for an helper/utility.
>
> For what it concerns `mapInstructions()` [please correct me if I'm wrong].
> This bit of the interface should be responsible for value numbering
> the instructions, as far as I can tell.
> To the best of my understanding the way your outliner value numbers
> using a nominal approach, i.e. two instructions get the same value
> number if their string representation is the same (or something like
> that).
>
> With the notion above,
> xorl %eax %eax
> movl %eax, $0
>
> aren't really considered equivalent (although, in practice, they are).
>
> The way I imagined outlining to work at the IR level (and how I once
> discussed with Dan) is leveraging the result of a value number
> analysis (NewGVN) to assign numbers.
>
> While the problem NewGVN solves is that of finding all the Herbrand
> equivalences (structural equivalence, same operation and operand
> structurally congruent), it also does a canonicalization step calling
> InstSimplify to canonicalize (so, in this sense it catches more
> stuffs, e.g.:
>
> %x = add %a, 0
> %y = sub %b, 0
> not equivalent
>
> instSimplify(%y) -> add %a, 0
> now they're equivalent.
>
> Note: The current IR outlliner doesn't really use the approach I just
> described, yet, but it's not hard to imagine extending (or rewriting
> it to use a real Global Value number analysis to get instructions that
> are equivalent, for some definition of  structural equivalency)
>
> I would also note that we already have InstCombine, GVN and other passes.
> Right now I see little value in teaching the outliner about those
> equivalences if we can just rely on earlier passes to normalize. This case
> also doesn't look like a pass ordering problems as I don't see the outliner
> enabling further optimizations in other passes.
>
> - Matthias
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170927/dde8cca8/attachment.html>