Hi, Yes, I can see why that would not work. The sinking algorithm in SimplifyCFG isn't particularly clever. In particular it can't reason about memory ordering and aliasing. In unswitch1(), it can identify that the stores correlate because the correlating stores appear in the same relative source order. In unswitch2() they have been permuted, and the algorithm cannot deal with this. This requires some kind of value numbering to do efficiently. The GVNSink pass that I really should get around to updating should solve this, eventually! James On Wed, 26 Apr 2017 at 08:19 Hongbin Zheng via llvm-dev < llvm-dev at lists.llvm.org> wrote:> Looks like this do not work: > > // Type your code here, or load an example. > int a[10]; > > void unswitch2(int i, int x, int y0, int y1) { > if (x) { > a[i] = y0; > a[i + 1] = y1; > } else { > a[i + 1] = y0; > a[i] = y1; > } > } > > https://godbolt.org/g/Ldd5qV > > On Tue, Apr 25, 2017 at 10:22 PM, Hongbin Zheng <etherzhhb at gmail.com> > wrote: > >> Thanks, >> >> Looks like inst combine do the job >> >> On Tue, Apr 25, 2017 at 9:36 PM, Davide Italiano <davide at freebsd.org> >> wrote: >> >>> On Tue, Apr 25, 2017 at 9:24 PM, Hongbin Zheng via llvm-dev >>> <llvm-dev at lists.llvm.org> wrote: >>> > Hi, >>> > >>> > Is there a pass in LLVM that can optimize: >>> > >>> > if (x) >>> > a[i] = y0; >>> > else >>> > a[i] = y1; >>> > >>> > to >>> > >>> > a[i] = x ? y0 : y1? >>> > >>> > I tried opt (3.9) with -O3 but looks like such an optimization do not >>> > happened. >>> > >>> >>> The same IR at -O3 for both cases on this example. >>> https://godbolt.org/g/Tk2MM8 >>> >>> -- >>> Davide >>> >>> "There are no solved problems; there are only problems that are more >>> or less solved" -- Henri Poincare >>> >> >> > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170426/e111acb6/attachment.html>
Hi James, I have an ad-hoc solution in mind to solve this problem. But if it can be solved under the framework of GVN"Sink", it is even better. any plan on your https://reviews.llvm.org/D24805? Thanks Hongbin On Wed, Apr 26, 2017 at 2:13 AM, James Molloy <james at jamesmolloy.co.uk> wrote:> Hi, > > Yes, I can see why that would not work. > > The sinking algorithm in SimplifyCFG isn't particularly clever. In > particular it can't reason about memory ordering and aliasing. In > unswitch1(), it can identify that the stores correlate because the > correlating stores appear in the same relative source order. In unswitch2() > they have been permuted, and the algorithm cannot deal with this. This > requires some kind of value numbering to do efficiently. > > The GVNSink pass that I really should get around to updating should solve > this, eventually! > > James > > > On Wed, 26 Apr 2017 at 08:19 Hongbin Zheng via llvm-dev < > llvm-dev at lists.llvm.org> wrote: > >> Looks like this do not work: >> >> // Type your code here, or load an example. >> int a[10]; >> >> void unswitch2(int i, int x, int y0, int y1) { >> if (x) { >> a[i] = y0; >> a[i + 1] = y1; >> } else { >> a[i + 1] = y0; >> a[i] = y1; >> } >> } >> >> https://godbolt.org/g/Ldd5qV >> >> On Tue, Apr 25, 2017 at 10:22 PM, Hongbin Zheng <etherzhhb at gmail.com> >> wrote: >> >>> Thanks, >>> >>> Looks like inst combine do the job >>> >>> On Tue, Apr 25, 2017 at 9:36 PM, Davide Italiano <davide at freebsd.org> >>> wrote: >>> >>>> On Tue, Apr 25, 2017 at 9:24 PM, Hongbin Zheng via llvm-dev >>>> <llvm-dev at lists.llvm.org> wrote: >>>> > Hi, >>>> > >>>> > Is there a pass in LLVM that can optimize: >>>> > >>>> > if (x) >>>> > a[i] = y0; >>>> > else >>>> > a[i] = y1; >>>> > >>>> > to >>>> > >>>> > a[i] = x ? y0 : y1? >>>> > >>>> > I tried opt (3.9) with -O3 but looks like such an optimization do not >>>> > happened. >>>> > >>>> >>>> The same IR at -O3 for both cases on this example. >>>> https://godbolt.org/g/Tk2MM8 >>>> >>>> -- >>>> Davide >>>> >>>> "There are no solved problems; there are only problems that are more >>>> or less solved" -- Henri Poincare >>>> >>> >>> >> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170426/b152f3bc/attachment.html>
It's basically ready to commit; the reviewers were fairly happy with it. It needs rebasing on top of NewGVN and any bugs that shakes out fixed, but that's about it. I want to get around to it soon-ish, but I've wanted that for a while! On Wed, 26 Apr 2017 at 16:50, Hongbin Zheng <etherzhhb at gmail.com> wrote:> Hi James, > > I have an ad-hoc solution in mind to solve this problem. > But if it can be solved under the framework of GVN"Sink", it is even > better. > > any plan on your https://reviews.llvm.org/D24805? > > Thanks > Hongbin > > > On Wed, Apr 26, 2017 at 2:13 AM, James Molloy <james at jamesmolloy.co.uk> > wrote: > >> Hi, >> >> Yes, I can see why that would not work. >> >> The sinking algorithm in SimplifyCFG isn't particularly clever. In >> particular it can't reason about memory ordering and aliasing. In >> unswitch1(), it can identify that the stores correlate because the >> correlating stores appear in the same relative source order. In unswitch2() >> they have been permuted, and the algorithm cannot deal with this. This >> requires some kind of value numbering to do efficiently. >> >> The GVNSink pass that I really should get around to updating should solve >> this, eventually! >> >> James >> >> >> On Wed, 26 Apr 2017 at 08:19 Hongbin Zheng via llvm-dev < >> llvm-dev at lists.llvm.org> wrote: >> >>> Looks like this do not work: >>> >>> // Type your code here, or load an example. >>> int a[10]; >>> >>> void unswitch2(int i, int x, int y0, int y1) { >>> if (x) { >>> a[i] = y0; >>> a[i + 1] = y1; >>> } else { >>> a[i + 1] = y0; >>> a[i] = y1; >>> } >>> } >>> >>> https://godbolt.org/g/Ldd5qV >>> >>> On Tue, Apr 25, 2017 at 10:22 PM, Hongbin Zheng <etherzhhb at gmail.com> >>> wrote: >>> >>>> Thanks, >>>> >>>> Looks like inst combine do the job >>>> >>>> On Tue, Apr 25, 2017 at 9:36 PM, Davide Italiano <davide at freebsd.org> >>>> wrote: >>>> >>>>> On Tue, Apr 25, 2017 at 9:24 PM, Hongbin Zheng via llvm-dev >>>>> <llvm-dev at lists.llvm.org> wrote: >>>>> > Hi, >>>>> > >>>>> > Is there a pass in LLVM that can optimize: >>>>> > >>>>> > if (x) >>>>> > a[i] = y0; >>>>> > else >>>>> > a[i] = y1; >>>>> > >>>>> > to >>>>> > >>>>> > a[i] = x ? y0 : y1? >>>>> > >>>>> > I tried opt (3.9) with -O3 but looks like such an optimization do not >>>>> > happened. >>>>> > >>>>> >>>>> The same IR at -O3 for both cases on this example. >>>>> https://godbolt.org/g/Tk2MM8 >>>>> >>>>> -- >>>>> Davide >>>>> >>>>> "There are no solved problems; there are only problems that are more >>>>> or less solved" -- Henri Poincare >>>>> >>>> >>>> >>> _______________________________________________ >>> LLVM Developers mailing list >>> llvm-dev at lists.llvm.org >>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>> >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170426/4b17134c/attachment.html>