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

[Davide Italiano via llvm-dev]

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)

So, I wonder whether you plan to enhance the logic for value numbering
in your current scheme. If you do, and you plan to share more code
between IR and MI outliner, then it's a good idea I guess to have a
common interface (I'd love to hear your thoughts on this one).

About the `getOutliningCost()` API, what do you think to do in the MI outliner?
Currently, if I remember correctly, (almost) all instructions have
unit cost except for something.
It's not unreasonable to think this model will evolve. A relatively
obvious improvement might be that of taking in account the length
encoding for the target architecture when outlining. The IR outliner
uses TargetTransformInfo to do estimation costs. I think we may want
to evaluate whether (or not) it's feasible to have a base class for
the cost model that doesn't introduce too much boilerplate, or whether
we should bite the bullet and pay a small cost in duplication for this
logic across the two outliners.

Thanks,

--
Davide