On Wed, May 9, 2018 at 10:39 AM, Hiroshi Yamauchi <yamauchi at google.com> wrote:> > > 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 discussion.) >>> >>> If >>> we will >>> move >>> reassociation, >>> or keep additional ones >>> , >>> out of instcombine, >>> open questions for me would be >>> : >>> >>> >>> 1. Since -reassociate isn't a fixed point pass, >>> >> >> This is fixable, fwiw, without fixpointing it. >> > > How? >Depends on specifically which part you would like to know about ;)> > >> >>> we might need to repeat "-instcombine -reassociate" multiple times to >>> fold >>> down to what we want (relating to my comment here >>> <https://reviews.llvm.org/D46336#1087082>). I assumed this isn't not >>> what we want to do >>> ? My impression is we don't do a fixed-point with passes? >>> >> >> Well, i mean there is no practical difference between passes that we >> fixpoint externally and fixpoint internally. >> > > I had the following in mind: Does the pass manager support fixpointing > externally? Is there any performance difference? Are people okay with that > in general? > > But if there is no practical difference, I don't see any problem with > that :) > > >> >>> >>> >> 2. >>> Since -reassociate needs to come up with one operand order (at least >>> currently as the only reassociate pass), would there exist a single, >>> unique operand order that would enable all reassociative/commutative >>> foldings that we want? >>> >> >> In what way? >> Are you asking whether there is a single reassociation order that makes >> all foldings occur in the same operation or something? >> I don't feel like i understand what you are asking. >> > > Does this rephrase help: with the motivating examples (like and-of-shifts > or bit check patterns) from the above differentials in mind, can we come up > with a single reassociation order that solves all those and all the > others that may come up in the future? Would we need different reassociation > orders to fold different patterns? >It doesn't quite help. When stated that generally, there can be no such ordering at all, that's easy to prove. It is a statically undecidable problem. There is however, a different question and answer to a few related problems that maybe you are really asking? 1. Is there a way to determine and apply the a maximal or nearly-maximal set of folds/graph transforms that could be applied to a given set of code in a sane and principled way -> yes (see, e.g., http://www.cs.cornell.edu/~ross/publications/eqsat/) 2. Is there a way to determine all expressions in the program as it exists that are equivalent or equivalent under constant time constant folding/reassociation, in a reasonable time bound -> yes (not a single easy link, happy to talk about it) Your original question is basically equivalent to Is there a way to determine all expressions in the program as it exists that are equivalent or could be made equivalent through any type of folding that one can think up? The answer to that is "no", 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>
On Wed, May 9, 2018 at 8:24 PM Daniel Berlin <dberlin at dberlin.org> wrote:> > > On Wed, May 9, 2018 at 10:39 AM, Hiroshi Yamauchi <yamauchi at google.com> > wrote: > >> >> >> 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 discussion.) >>>> >>>> If >>>> we will >>>> move >>>> reassociation, >>>> or keep additional ones >>>> , >>>> out of instcombine, >>>> open questions for me would be >>>> : >>>> >>>> >>>> 1. Since -reassociate isn't a fixed point pass, >>>> >>> >>> This is fixable, fwiw, without fixpointing it. >>> >> >> How? >> > > Depends on specifically which part you would like to know about ;) >Maybe I misunderstood what you meant by "This is fixable". Did you mean that we won't somehow need to fixpoint between instcombine and reassociate, or that the specific motivating examples from the above differentials are foldable without fixpointing? If the latter, that may be the case. The concern was that we may encounter examples that may need many more iterations, if not fixpointing. As long as it's feasible to fixpoint between instcombine and reassociate, it seems to work, but I guess that would probably need some pass management change.> >> >> >>> >>>> we might need to repeat "-instcombine -reassociate" multiple times to >>>> fold >>>> down to what we want (relating to my comment here >>>> <https://reviews.llvm.org/D46336#1087082>). I assumed this isn't not >>>> what we want to do >>>> ? My impression is we don't do a fixed-point with passes? >>>> >>> >>> Well, i mean there is no practical difference between passes that we >>> fixpoint externally and fixpoint internally. >>> >> >> I had the following in mind: Does the pass manager support fixpointing >> externally? Is there any performance difference? Are people okay with that >> in general? >> >> But if there is no practical difference, I don't see any problem with >> that :) >> >> >>> >>>> >>>> >>> 2. >>>> Since -reassociate needs to come up with one operand order (at least >>>> currently as the only reassociate pass), would there exist a single, >>>> unique operand order that would enable all reassociative/commutative >>>> foldings that we want? >>>> >>> >>> In what way? >>> Are you asking whether there is a single reassociation order that makes >>> all foldings occur in the same operation or something? >>> I don't feel like i understand what you are asking. >>> >> >> Does this rephrase help: with the motivating examples (like and-of-shifts >> or bit check patterns) from the above differentials in mind, can we come up >> with a single reassociation order that solves all those and all the >> others that may come up in the future? Would we need different reassociation >> orders to fold different patterns? >> > > It doesn't quite help. > When stated that generally, there can be no such ordering at all, that's > easy to prove. It is a statically undecidable problem. > > There is however, a different question and answer to a few related > problems that maybe you are really asking? > 1. Is there a way to determine and apply the a maximal or nearly-maximal > set of folds/graph transforms that could be applied to a given set of code > in a sane and principled way -> yes > > (see, e.g., http://www.cs.cornell.edu/~ross/publications/eqsat/) > > 2. Is there a way to determine all expressions in the program as it exists > that are equivalent or equivalent under constant time constant > folding/reassociation, in a reasonable time bound -> yes > > (not a single easy link, happy to talk about it) > > Your original question is basically equivalent to > Is there a way to determine all expressions in the program as it exists > that are equivalent or could be made equivalent through any type of folding > that one can think up? > The answer to that is "no", 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. > > > 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 reassociative pattern to be folded (D41574), and I want yet another particular reassociative pattern to be folded (D46336), would we potentially need three different reassociate passes with each combined with instcombine, rather than just one that may be able to somehow handle those cases in one shot, (assuming we don't want to put those in instcombine)? And it sounds like the answer is yes? -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180510/c10f5692/attachment.html>
On Thu, May 10, 2018 at 12:05 PM, Hiroshi Yamauchi <yamauchi at google.com> wrote:> > > On Wed, May 9, 2018 at 8:24 PM Daniel Berlin <dberlin at dberlin.org> wrote: > >> >> >> On Wed, May 9, 2018 at 10:39 AM, Hiroshi Yamauchi <yamauchi at google.com> >> wrote: >> >>> >>> >>> 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 discussion.) >>>>> >>>>> If >>>>> we will >>>>> move >>>>> reassociation, >>>>> or keep additional ones >>>>> , >>>>> out of instcombine, >>>>> open questions for me would be >>>>> : >>>>> >>>>> >>>>> 1. Since -reassociate isn't a fixed point pass, >>>>> >>>> >>>> This is fixable, fwiw, without fixpointing it. >>>> >>> >>> How? >>> >> >> Depends on specifically which part you would like to know about ;) >> > > Maybe I misunderstood what you meant by "This is fixable". Did you mean > that we won't somehow need to fixpoint between instcombine and reassociate, > or that the specific motivating examples from the above differentials are > foldable without fixpointing? >If by fixpointing you mean "fixpointing reassociate and instcombine", then yes, that is fixable without fixpointing reassociate and instcombine, but would require rewriting instcombine :)> > If the latter, that may be the case. The concern was that we may encounter > examples that may need many more iterations, if not fixpointing. As long as > it's feasible to fixpoint between instcombine and reassociate, it seems > to work, but I guess that would probably need some pass management change. > > >> >>> >>> >>>> >>>>> we might need to repeat "-instcombine -reassociate" multiple times to >>>>> fold >>>>> down to what we want (relating to my comment here >>>>> <https://reviews.llvm.org/D46336#1087082>). I assumed this isn't not >>>>> what we want to do >>>>> ? My impression is we don't do a fixed-point with passes? >>>>> >>>> >>>> Well, i mean there is no practical difference between passes that we >>>> fixpoint externally and fixpoint internally. >>>> >>> >>> I had the following in mind: Does the pass manager support fixpointing >>> externally? Is there any performance difference? Are people okay with that >>> in general? >>> >>> But if there is no practical difference, I don't see any problem with >>> that :) >>> >>> >>>> >>>>> >>>>> >>>> 2. >>>>> Since -reassociate needs to come up with one operand order (at least >>>>> currently as the only reassociate pass), would there exist a single, >>>>> unique operand order that would enable all reassociative/commutative >>>>> foldings that we want? >>>>> >>>> >>>> In what way? >>>> Are you asking whether there is a single reassociation order that makes >>>> all foldings occur in the same operation or something? >>>> I don't feel like i understand what you are asking. >>>> >>> >>> Does this rephrase help: with the motivating examples (like >>> and-of-shifts or bit check patterns) from the above differentials in mind, >>> can we come up with a single reassociation order that solves all those >>> and all the others that may come up in the future? Would we need different reassociation >>> orders to fold different patterns? >>> >> >> It doesn't quite help. >> When stated that generally, there can be no such ordering at all, that's >> easy to prove. It is a statically undecidable problem. >> >> There is however, a different question and answer to a few related >> problems that maybe you are really asking? >> 1. Is there a way to determine and apply the a maximal or nearly-maximal >> set of folds/graph transforms that could be applied to a given set of code >> in a sane and principled way -> yes >> >> (see, e.g., http://www.cs.cornell.edu/~ross/publications/eqsat/) >> >> 2. Is there a way to determine all expressions in the program as it >> exists that are equivalent or equivalent under constant time constant >> folding/reassociation, in a reasonable time bound -> yes >> >> (not a single easy link, happy to talk about it) >> >> Your original question is basically equivalent to >> Is there a way to determine all expressions in the program as it exists >> that are equivalent or could be made equivalent through any type of folding >> that one can think up? >> The answer to that is "no", 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. >> >> >> > 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 reassociative pattern to > be folded (D41574), and I want yet another particular reassociative > pattern to be folded (D46336), would we potentially need three > different reassociate passes with each combined with instcombine, rather > than just one that may be able to somehow handle those cases in one shot, > (assuming we don't want to put those in instcombine)? > > And it sounds like the answer is yes? >If you take the current instcombine as a base, then yes, that is correct. If you are willing to rearchitect instcombine, the answer is no, it's possible to do this all in a single pass in a relatively sane way. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180510/2429409e/attachment.html>