search for: herbrand

...lin <dberlin at dberlin.org> wrote: > I tend to agree with Hal -- value numbering computes equivalent *values*, >> > Sorry, but this is just flat out wrong > > "A Global Value Numbering(GVN) algorithm is considered to be complete (or > precise), if it can detect all Herbrand equivalences among expressions in a > program. > Two expressions are said to be Herbrand equivalent (or transparent > equivalent ), if they are computed by the same operator applied to > equivalent operands " > > This is, AFAIK, precisely what you want. > > I'm not...

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

...o", it's provable that this is not statically decidable, so the time bound doesn't matter :) You have to limit the possible folding/evaluation you apply in various ways to make this decidable, and then further limit it to make the time bound reasonable. This all quickly devolves into herbrand equivalence and it's variations. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180509/946f6ad4/attachment-0001.html>

...#39;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 th...

The current gvn equality propagation is not powerful enough to get this because it doesn't try to infer values in predicates based on other predicates, so it never realizes a>b -> a !=b in a useful way. It otherwise would get this On Thu, Jun 30, 2016, 7:41 PM Sean Silva <chisophugis at gmail.com> wrote: > On Thu, Jun 30, 2016 at 6:45 PM, Daniel Berlin via llvm-dev <

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

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

...his is not statically > decidable, so the time bound doesn't matter :) > > You have to limit the possible folding/evaluation you apply in various > ways to make this decidable, and then further limit it to make the time > bound reasonable. > > This all quickly devolves into herbrand equivalence and it's variations. > > > ​ Let me try one more time :) May we need multiple reassociate passes to fold different reassociative patterns? A longer version: If Sanjay wants a particular reassociative pattern to be folded (D45842), Omer wants another particular reassociativ...

...ere 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 cited by newgvn of situations where different choices of values for predicate and phi inference w...

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

...t; decidable, so the time bound doesn't matter :) >> >> You have to limit the possible folding/evaluation you apply in various >> ways to make this decidable, and then further limit it to make the time >> bound reasonable. >> >> This all quickly devolves into herbrand equivalence and it's variations. >> >> >> ​ > Let me try one more time :) May we need multiple reassociate passes to > fold different reassociative patterns? > > A longer version: If Sanjay wants a particular reassociative pattern to be > folded (D45842), Omer w...

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

...e bound doesn't matter :) >>> >>> You have to limit the possible folding/evaluation you apply in various >>> ways to make this decidable, and then further limit it to make the time >>> bound reasonable. >>> >>> This all quickly devolves into herbrand equivalence and it's variations. >>> >>> >>> ​ >> Let me try one more time :) May we need multiple reassociate passes to >> fold different reassociative patterns? >> >> A longer version: If Sanjay wants a particular reassociative pattern to &gt...

...er :) >>>> >>>> You have to limit the possible folding/evaluation you apply in various >>>> ways to make this decidable, and then further limit it to make the time >>>> bound reasonable. >>>> >>>> This all quickly devolves into herbrand equivalence and it's variations. >>>> >>>> >>>> ​ >>> Let me try one more time :) May we need multiple reassociate passes to >>> fold different reassociative patterns? >>> >>> A longer version: If Sanjay wants a particular...

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

...matter :) > > You have to limit the possible folding/evaluation you > apply in various ways to make this decidable, and then > further limit it to make the time bound reasonable. > > This all quickly devolves into herbrand equivalence > and it's variations. > > > ​ > Let me try one more time :) May we need multiple > reassociate passes to fold different reassociative patterns? > > A longer version: If Sanjay wants a particular...

On Tue, May 8, 2018 at 11:15 AM Daniel Berlin <dberlin at dberlin.org> wrote: > > > On Tue, May 8, 2018 at 10:38 AM, Hiroshi Yamauchi via llvm-dev < > llvm-dev at lists.llvm.org> wrote: > >> ( >> ​I came across this issue in the context of >> D46336 <https://reviews.llvm.org/D46336>. >> ​ ​ >> Thanks, Sanjay, for starting this

...t; >>>>> You have to limit the possible folding/evaluation you apply in various >>>>> ways to make this decidable, and then further limit it to make the time >>>>> bound reasonable. >>>>> >>>>> This all quickly devolves into herbrand equivalence and it's >>>>> variations. >>>>> >>>>> >>>>> ​ >>>> Let me try one more time :) May we need multiple reassociate passes to >>>> fold different reassociative patterns? >>>> >>>&gt...

...gt;> You have to limit the possible folding/evaluation you apply in >>>>>> various ways to make this decidable, and then further limit it to make the >>>>>> time bound reasonable. >>>>>> >>>>>> This all quickly devolves into herbrand equivalence and it's >>>>>> variations. >>>>>> >>>>>> >>>>>> ​ >>>>> Let me try one more time :) May we need multiple reassociate passes >>>>> to fold different reassociative patterns? >>...

On Tue, May 8, 2018 at 10:38 AM, Hiroshi Yamauchi via llvm-dev < llvm-dev at lists.llvm.org> wrote: > ( > ​I came across this issue in the context of > D46336 <https://reviews.llvm.org/D46336>. > ​ ​ > Thanks, Sanjay, for starting this discussion.) > > If > ​we will > move > ​reassociation, > or keep additional ones > ​,​ > out of instcombine,