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

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

On Wed, Sep 27, 2017 at 6:07 PM, Matthias Braun <mbraun at apple.com>
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
I'm in agreement with you, for the outliner working in the mid-level
optimizer.
FWIW, if you get the congruence classes formed by a value numbering
analysis you should get these for free.
Teaching the outliner how to catch congruences as-it-goes instead of
relying on an analysis is madness, and not really fruitful, IMHO. My
question is more how you can get the same effect when you're working
in the backend as the representation you're working on doesn't really
contain that much information.

I guess the answer it's just it's really hard without a Global VN to
understand if `xor %eax, %eax` and `andl %eax, $0` are the same, and
you don't have that information that far in the pipeline.
I'm not an expert in code generation so I may be completely off on
this one, but I assume that you somehow rely on SelectionDAG (e.g.
DAGCombine) to do the canonicalization similarly to what you would do
with InstCombine in the IR optimizer, and cases where you emit
equivalent instructions that have different encodings is relatively
rare, (in the case above, you always emit the XOR idiom).

-- 
Davide

"There are no solved problems; there are only problems that are more
or less solved" -- Henri Poincare

> On Sep 27, 2017, at 6:22 PM, Davide Italiano <davide at freebsd.org>
wrote:
> 
> On Wed, Sep 27, 2017 at 6:07 PM, Matthias Braun <mbraun at apple.com
<mailto:mbraun at apple.com>> 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
> 
> I'm in agreement with you, for the outliner working in the mid-level
optimizer.
> FWIW, if you get the congruence classes formed by a value numbering
> analysis you should get these for free.
> Teaching the outliner how to catch congruences as-it-goes instead of
> relying on an analysis is madness, and not really fruitful, IMHO. My
> question is more how you can get the same effect when you're working
> in the backend as the representation you're working on doesn't
really
> contain that much information.
> 
> I guess the answer it's just it's really hard without a Global VN
to
> understand if `xor %eax, %eax` and `andl %eax, $0` are the same, and
> you don't have that information that far in the pipeline.
> I'm not an expert in code generation so I may be completely off on
> this one, but I assume that you somehow rely on SelectionDAG (e.g.
> DAGCombine) to do the canonicalization similarly to what you would do
> with InstCombine in the IR optimizer, and cases where you emit
> equivalent instructions that have different encodings is relatively
> rare, (in the case above, you always emit the XOR idiom).
Yes SelectionDAG does some normalization and hopefully equivalent things will
get pattern matched to the same instructions.
But in the end CodeGen is usually a place where we neither have a good
understanding of instruction semantics and where transforming instructions is
really hard as you typically already spent several passes doing resource
allocation (registers, stack space, ...) and constraint handling for the
concrete instructions, changing them may bring new constraints/require new
resources that you just cannot handle late in the pipeline. Taking your example:
Switching MOV %eax, $0 to XOR eax, eax would suddenly start setting the eflags
register which at the very least needs legality checks, or ways to spill/restore
it, ...

For the sake of maintainability and keeping a clean separation of concerns into
passes we should not try to do too much that late in the CodeGen Pipeline.

- Matthias
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170927/68e1de13/attachment.html>

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>