search for: congruenc

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

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

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

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

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

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

> 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 algorithm, the actual underlying method should be pretty similar. If it is...

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 Jessica's pass. Still, some issues remain. I wonder what leaf nodes for reads of &qu...

...n on the placement of the > outliner in LLVM. > > > My fear with a new framework is that we are going to split the effort for > pushing the outliner technology forward and I’d like to avoid that if at > all possible. > 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 can imagine two extreme outcomes (reality is probably somewhere in between): 1. if you run the LLVM IR level code size outliner,...

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

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

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

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 yes, it would be incorrect, as obviously, these two additions are not guaranteed to be semantically equivalent (a's and b's values can be changed in-between). Also note that one should be able to...

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

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