search for: congruence

...om 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 the same common substring / pruning algorithm the post-RA MO uses but with a specially chosen congruence relation. I’d like to delve into the differences between the two: Congruence Detection: - Machine Outliner The machine outliner has the advantage of having this problem already taken care of by the register allocator, it simply checks to see if the two machine instructions are identical...

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

...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 the same common substring / pruning algorithm the post-RA MO > uses but with a specially chosen congruence relation. I’d like to delve > into the differences between the two: > > Congruence Detection: > > - Machine Outliner > > The machine outliner has the advantage of having this problem already > taken care of by the register allocator, it simply checks to see if the t...

...rg <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. >> &...

...om 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 the same common substring / pruning algorithm the post-RA MO uses but with a specially chosen congruence relation. I’d like to delve into the differences between the two: > > Congruence Detection: > > - Machine Outliner > The machine outliner has the advantage of having this problem already taken care of by the register allocator, it simply checks to see if the two machine...

...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 the same common substring / pruning algorithm the post-RA MO > uses but with a specially chosen congruence relation. I’d like to delve > into the differences between the two: > > Congruence Detection: > > - Machine Outliner > The machine outliner has the advantage of having this problem already > taken care of by the register allocator, it simply checks to see if the two &g...

...om 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 the same common substring / pruning algorithm the post-RA MO uses but with a specially chosen congruence relation. I’d like to delve into the differences between the two: >> >> Congruence Detection: >> >> - Machine Outliner >> The machine outliner has the advantage of having this problem already taken care of by the register allocator, it simply checks to se...

...gt; By that I mean that the actual suffix tree/array candidate search algorithm would be separate from the actual implementation of *outlining things*. The actual implementation at each level of representation would define > > - How to outline a sequence of instructions > - An equivalence/congruence scheme for two instructions > - A cost model > > I don’t think it’d be too difficult to split it up in that sort of way. I’d also like to experiment with pre-regalloc outlining in general, so it’d make it easier to explore that route as well. > >> 1. if you run the LLVM IR level...

...ressions would be the same ("value1 + value2"), but a >> single operator is not worthy to be outlined. >> > > > Sure. > > > >> What classes of congruency would be assigned to operands? >> > > > GVN is not interprocedural, so comparing gvn congruencey results (as > opposed to functions) between functions is udefined. > > >> The same for both reads of "a" and "b"? If yes, it would be incorrect, as >> obviously, these two additions are not guaranteed to be semantically >> equivalent (a's and b...

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

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

...bably don’t want to run a full GVN after the “loop-scheduling” passes. I guess the pipeline to experiment with for now is opt -loop-vectorize -loop-vectorize -newgvn. Adam > The only thing you'd have to do is write some code to set "live on entry" subgraph variables in their own congruence classes. > We already do this for incoming arguments. > > Otherwise, it's trivial to make it only walk things in the subgraph. > > -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170227...

...edundancies it does now. So what you want is "i want to know what >> globally is the same", it doesn't really answer that well. >> >> Doing the analysis Quentin wants is pretty trivial in NewGVN (analysis >> and elimination are split, everything is broken into congruence classes >> explicitly, each congruence class has an id, you could sub in that id as >> the value for the terminated string), but i'd agree that GVN as it exists >> now will not do what they want, and would be pretty hard to make work well. >> >> (FWIW: Davide Itali...

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

...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 explained in stages: * Candidate Selection: Each instruction in the module is mapped to a congruence class based upon relaxed equivalency constraints. For most instructions this is simply: The type, opcode, and operand types. The constraints are tightened for instructions with special state that require more exact equivalence (e.g. ShuffleVector requires a constant mask vector). Candidates are the...

...olutions didn’t handle well enough. Outlining is one of the > avenues that seemed potentially beneficial. > > -- Algorithmic Approach -- > > The general implementation can be explained in stages: > > * Candidate Selection: > > Each instruction in the module is mapped to a congruence class based upon > relaxed equivalency constraints. For most instructions this is simply: The > type, opcode, and operand types. The constraints are tightened for > instructions with special state that require more exact equivalence (e.g. > ShuffleVector requires a constant mask vector)...

...n that > mode. > > -Hal > > > I guess the pipeline to experiment with for now is opt -loop-vectorize > -loop-vectorize -newgvn. > > Adam > > The only thing you'd have to do is write some code to set "live on entry" > subgraph variables in their own congruence classes. > We already do this for incoming arguments. > > Otherwise, it's trivial to make it only walk things in the subgraph. > > > > > -- > Hal Finkel > Lead, Compiler Technology and Programming Languages > Leadership Computing Facility > Argonne National L...