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

[Matthias Braun via llvm-dev]

> 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 <mailto: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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170927/af81446e/attachment-0001.html>