similar to: [RFC] PT.2 Add IR level interprocedural outliner for code size.

Hey Gerolf, On Thu, Sep 21, 2017 at 7:10 PM, Gerolf Hoflehner <ghoflehner at apple.com> wrote: > In general I would love to see an outliner at the IR level also. But > rather than a comparison vs. the machine outliner I would like to learn > more about how the core data structures between the outliners will be > shared. > The only structure that needs to be shared is a

In general I would love to see an outliner at the IR level also. But rather than a comparison vs. the machine outliner I would like to learn more about how the core data structures between the outliners will be shared. In particular for matching/pruning it seems to be a reasonable approach. A few more remarks/questions are below also. Thanks Gerolf > On Sep 5, 2017, at 4:16 PM, River Riddle

> On Sep 21, 2017, at 8:02 PM, River Riddle <riddleriver at gmail.com> wrote: > > Hey Gerolf, > > On Thu, Sep 21, 2017 at 7:10 PM, Gerolf Hoflehner <ghoflehner at apple.com <mailto:ghoflehner at apple.com>> wrote: > In general I would love to see an outliner at the IR level also. But rather than a comparison vs. the machine outliner I would like to learn more

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

I’m River and I’m a compiler engineer at PlayStation. Recently, I’ve been working on an interprocedural outlining (code folding) pass for code size improvement at the IR level. We hit a couple of use cases that the current code size solutions didn’t handle well enough. Outlining is one of the avenues that seemed potentially beneficial. -- Algorithmic Approach -- The general implementation can be

Hi Evgeny, I know of the current machine outliner in LLVM. If you look in the "More detailed performance data" in the end section it includes performance comparisons to the machine outliner. As for the algorithmic approach they are kind of similar. Machine Outliner: - Builds a suffix tree based on identical equivalence between machine instrs. - Uses target specific cost model for

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

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

> On Jul 25, 2017, at 9:24 AM, Jessica Paquette <jpaquette at apple.com> wrote: > >> The two passes are pretty different in their approaches to congruency finding, so I don't think it helps to group them as though they were interchangeable "outliner technology". The two passes might be totally orthogonal. > > I think that based off how River described his

On Mon, Jul 24, 2017 at 4:14 PM, Quentin Colombet via llvm-dev < llvm-dev at lists.llvm.org> wrote: > Hi River, > > On Jul 24, 2017, at 2:36 PM, River Riddle <riddleriver at gmail.com> wrote: > > Hi Quentin, > I appreciate the feedback. When I reference the cost of Target Hooks it's > mainly for maintainability and cost on a target author. We want to keep the

Hi Andrey, Questions and feedback are very much welcome. - The explanation as to why the improvements can vary between the IR and MIR outliner mainly boil down to the level of abstraction that each are working at. The MIR level has very accurate heuristics and is effectively the last post ISel target independent code gen pass. The IR outliner on the other hand has more estimation in the cost

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

Hi Davide, Thanks! I think that this is a really great thing to be pushing forward in general. > 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

> > --- Algorithmic differences with the Machine Outliner ---- > > There was a lot of confusion on how exactly the algorithm I am > proposing differs from what is available in the Machine Outliner. The > similarities of the two outliners lie in the usage of a string matching > algorithm and candidate pruning. The first step in the algorithm is to > basically do

Daniel, I wonder what the NewGVN would generate for the following C code: int a, b; int foo() { return a + b; } int bar() { return a + b; } ? Obviously, the expressions would be the same ("value1 + value2"), but a single operator is not worthy to be outlined. What classes of congruency would be assigned to operands? The same for both reads of "a" and "b"? If

Apologies for delayed joining of this discussion, but I had a few notes from this thread that I really wanted to chime in about. River, I don't mean to put you on the spot, but I do want to start on a semantic issue. In several places in the thread you used the words "we" and "our" to imply that you're not alone in writing this (which is totally fine), but your

----- Original Message ----- > From: "Daniel Berlin" <dberlin at dberlin.org> > To: "Quentin Colombet" <qcolombet at apple.com> > Cc: "Hal Finkel" <hfinkel at anl.gov>, "llvm-dev" > <llvm-dev at lists.llvm.org> > Sent: Friday, August 26, 2016 11:06:56 PM > Subject: Re: [llvm-dev] [RFC] Interprocedural MIR-level

Hi Chris, > One particular disagreement that I think very much needs to be revisited in this thread was Jessica's proposal of a pipeline of: > 1. IR outline > 2. Inline > 3. MIR outline IMHO, there is no need to restrict a place of the Outliner in the pipeline at the moment. I hope people representing different architectures will try different configurations and the best will be

Hi, I let Jessica give more details but here are some insights. MIR offers a straight forward way to model benefits, because we know which instructions we remove and which one we add and there are no overhead of setting up parameters. Indeed, since the coloring will be the same between the different outlining candidates, the call is just a jump somewhere else. We do not have to worry about the

Hi River, Thanks for the detailed explanation. If people are okay for you to move forward, like I said to Andrey, I won’t oppose. I feel sad we have to split our effort on outlining technology, but I certainly don’t pretend to know what is best! The bottom line is if people are happy with that going in, the conversation on the details can continue in parallel. > On Jul 24, 2017, at 4:56 PM,