search for: congruences

Hey Everybody, A little while ago I posted an RFC( http://lists.llvm.org/pipermail/llvm-dev/2017-July/115666.html) with the proposition of adding a new outliner at the IR level. There was some confusion and many questions regarding the proposal which I’d like to address here: Note about nomenclature: Candidate: A repeated sequence of instructions within a module. Occurrence: One instance

...t; 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'...

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

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

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

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

> 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

> 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

Daniel, OK, I see your point. My understanding was that VNDAG is an internal representation, not meant to be used by VN's customers (that should really care for classes of congruency, nothing more). Also, I thought that VN's results are available for a single function at a time. It seems that NewGVN provides access to VNDAGs computed for the whole program -- which enables its usage in

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

1. ————— Dan, The reasoning given below for how GVN operates seems odd to me, Poison is an attribute of a value, just like nsw is an attribute of an operation, So when GVN sees a pair of equal values, one of which has an extra attribute, The proper choice for representative value is the one without the attribute, Just like when GVN sees a pair of add operations, one of which has an

...oices of what make *good* representative values in NewGVN. > I would deny any assertion that there is a proper choice, and that if there is one, it must be what you suggest :) > You actually can prove that there is no optimal such choice. Different choices will lead you to discover different congruences in any practical algorithms, even complete ones (as the issues here are orthogonal to herbrand equivalence., and instead related to inference of facts from control flow and other things, as well as what the results from symbolic evaluation and simplification) > There are examples in the paper ci...

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

> On Feb 27, 2017, at 9:39 AM, Daniel Berlin <dberlin at dberlin.org> wrote: > > > > On Mon, Feb 27, 2017 at 9:29 AM, Adam Nemet <anemet at apple.com <mailto:anemet at apple.com>> wrote: > >> On Feb 27, 2017, at 7:27 AM, Hal Finkel <hfinkel at anl.gov <mailto:hfinkel at anl.gov>> wrote: >> >> >> On 02/27/2017 06:29 AM,

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

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

Hello, I need to do a principal component analysis with EQUAMAX-rotation. Unfortunately the function principal() I use normally for PCA does not offer this rotation specification. I could find out that this might be possible somehow with the package GPArotation but until now I could not figure out how to use this in the principal component analysis. Maybe someone can give an example on how to do

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

There's another issue with re-running the vectorizer (which I support, btw - I'm just saying there are more problems to solve on the way :-) ) Historically, we haven't even tried to evaluate the cost of the "constant" (not per-iteration) vectorization overhead - things like alias checks. Instead, we have hard bounds - we won't perform alias checks that are "too