Hal Finkel via llvm-dev
2017-Jul-18 23:15 UTC
[llvm-dev] A bug related with undef value when bootstrap MemorySSA.cpp
On 07/18/2017 06:03 PM, David Majnemer via llvm-dev wrote:> I doubt it is possible for us to try and make any fix which is > predicated on eagerly treating undef in a particular way, refinement > will always cause these problems to come about... > > Given what I've seen in LLVM (and what I've learned from other > compilers), we probably have two choices: > 1. Rework undef so that it is an instruction, not a constant. This > will make it easy to unswitch, etc. because it would be stable. This > approach is used by other production quality compilers and is > workable. Would also result in a lot of churn. > 2. Keep undef as a constant, introduce freeze. Churn would mostly be > restricted to correctness fixes instead of to core IR representation. > > Note that option #1 is basically a short-hand for freeze(undef). > > We don't need to fix all the problems at the same time but I think we > need to start somewhere. I don't think there are any good shortcuts.I agree; I don't think there are any good shortcuts here. Sadly, I think we should follow our traditional policy: revert to green. Whatever commit actually triggers the self-hosting bug, revert it (or effectively revert it by disabling whatever it is by default). Then we should proceed with fixing the underlying problem with all due haste. -Hal> > On Tue, Jul 18, 2017 at 3:40 PM, Wei Mi via llvm-dev > <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote: > > On Mon, Jul 17, 2017 at 5:11 PM, Wei Mi <wmi at google.com > <mailto:wmi at google.com>> wrote: > > On Mon, Jul 17, 2017 at 2:09 PM, Sanjoy Das > > <sanjoy at playingwithpointers.com > <mailto:sanjoy at playingwithpointers.com>> wrote: > >> Hi, > >> > >> On Mon, Jul 17, 2017 at 1:56 PM, Daniel Berlin via llvm-dev > >> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote: > >>> > >>> > >>> On Mon, Jul 17, 2017 at 1:53 PM, Wei Mi <wmi at google.com > <mailto:wmi at google.com>> wrote: > >>>> > >>>> It seems MemorySSA.cpp is the only real code where we found the > >>>> problem happening. > >>> > >>> > >>> This is doubtful, ¸FWIW :) > >>> > >>>> > >>>> Is it possible to change the source of > >>>> MemorySSA.cpp to hide the problem and buy some time for now? > Now we > >>>> use an empty generic_def_path_iterator with Optional<ListIndex> N > >>>> being initialized by None as the end of range. Can we > initialize the > >>>> Optional var with a special value instead of None? > >>>> > >>>> iterator_range<def_path_iterator> def_path(ListIndex From) { > >>>> return make_range(def_path_iterator(this, From), > def_path_iterator()); > >>>> } > >>>> > >>> > >>> Why does this work? > >> > >> Fwiw, I don't think this is a good idea. If it can happen in > >> MemorySSA it can happen in other organic C++ source code too - > think > >> about what you're going to tell other folks who run into this > issue, > >> where such a workaround may be difficult to achieve or explain. > >> > >> -- Sanjoy > > > > Talked with David offline and he suggested a simple workaround > > solution. For the case in MemorySSA.cpp, we have "if (a == b)" > with b > > being defined by a phi, and the phi has an undef operand. We can > > recognize the simple pattern and give up loop unswitch for it. The > > idea is not to use isGuaranteedNotToBeUndefOrPoison to prove > > correctness, but just to rule out some patterns where such error may > > appear. > > > > I admit the solution is far from ideal, but at least it is very > simple > > to implement, and serves to mitigate the immediate correctness issue > > while avoiding performance regression. What do you think? > > > > Thanks, > > Wei. > > I tried the idea and it worked for the simple case, but didn't work > when compiling MemorySSA.cpp. That is because for the following > pattern: > > foo(c) { > b = phi(c, undef) > t = (a == b) > loop: > if (t) > end loop > } > > cfgsimplify will convert it to > foo(c) { > b = select i1 cond i32 c, undef > t = (a == b) > loop: > if (t) > end loop > } > > And instcombine can remove the select and generate: > foo(c) { > t = (a == c) > loop: > if (t) > end loop > } > > Now c is a param so loop unswitch kicks in. However, the argument of > foo is undef too, so we run into the problem again. > > Wei. > > > > >> > >>> > >>>> > >>>> > >>>> On Mon, Jul 17, 2017 at 1:37 PM, Daniel Berlin > <dberlin at dberlin.org <mailto:dberlin at dberlin.org>> > >>>> wrote: > >>>> > I think everyone agrees pretty much everything short of > "Fix undef" will > >>>> > not > >>>> > fix the problem for good. > >>>> > I think we are more trying to hide it well enough that we > get the months > >>>> > we > >>>> > need for various folks to work on the larger proposals. > >>>> > Which sucks, but not sure we have a better answer, because > i don't think > >>>> > we > >>>> > are going to commit the freeze/etc patches tomorrow. > >>>> > > >>>> > > >>>> > On Mon, Jul 17, 2017 at 1:34 PM, Juneyoung Lee > >>>> > <juneyoung.lee at sf.snu.ac.kr > <mailto:juneyoung.lee at sf.snu.ac.kr>> > >>>> > wrote: > >>>> >> > >>>> >> Hello, some of the patches had conflicts with LLVM head, > so I updated > >>>> >> them. If you experienced patch failure before then you can > try it > >>>> >> again. > >>>> >> > >>>> >> I compiled your code (1.c) with LLVM r308173 with the 5 > patches > >>>> >> applied, > >>>> >> and it generated assembly like this. Now it contains store > to c(%rip). > >>>> >> It tries to store a(%rip) + b(%rip) to c(%rip). I wish > this translation > >>>> >> is > >>>> >> now correct. > >>>> >> > >>>> >> ``` > >>>> >> 73 .globl hoo # -- Begin function hoo > >>>> >> 74 .p2align 4, 0x90 > >>>> >> 75 .type hoo, at function > >>>> >> 76 hoo: # @hoo > >>>> >> 77 .cfi_startproc > >>>> >> 78 # BB#0: > >>>> >> 79 movq a(%rip), %rax > >>>> >> 80 movq cnt(%rip), %rcx > >>>> >> 81 cmpq $0, i_hasval(%rip) > >>>> >> 82 sete %sil > >>>> >> 83 xorl %edx, %edx > >>>> >> 84 .p2align 4, 0x90 > >>>> >> 85 .LBB1_1: # =>This Inner Loop Header: > >>>> >> Depth=1 > >>>> >> 86 testb $1, %sil > >>>> >> 87 je .LBB1_3 > >>>> >> 88 # BB#2: # in Loop: Header=BB1_1 > >>>> >> Depth=1 > >>>> >> 89 movq b(%rip), %rsi > >>>> >> 90 addq %rax, %rsi > >>>> >> 91 movq %rsi, c(%rip) > >>>> >> 92 movq $3, i_hasval(%rip) > >>>> >> 93 incq %rdx > >>>> >> 94 xorl %esi, %esi > >>>> >> 95 cmpq %rcx, %rdx > >>>> >> 96 jl .LBB1_1 > >>>> >> 97 .LBB1_3: > >>>> >> 98 retq > >>>> >> ``` > >>>> >> > >>>> >> IMHO, enhancing `isGuaranteedNotToBeUndefOrPoison` and > using it as a > >>>> >> precondition in loop unswitching is > >>>> >> not enough. undef (and poison) value can be stored into > memory, and > >>>> >> also > >>>> >> be passed by a function argument. > >>>> >> `isGuaranteedNotToBeUndefOrPoison` will virtually return > `false` for > >>>> >> all > >>>> >> cases except the value is > >>>> >> some integer constant. Sanjoy's suggestion might be > helpful (if I > >>>> >> understood correctly), but I'm > >>>> >> not sure how much it will be. > >>>> >> > >>>> >> Best Regards, > >>>> >> Juneyoung Lee > >>>> >> > >>>> >> On Tue, Jul 18, 2017 at 3:43 AM, Sanjoy Das via llvm-dev > >>>> >> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> > wrote: > >>>> >>> > >>>> >>> On Mon, Jul 17, 2017 at 11:21 AM, Daniel Berlin > <dberlin at dberlin.org <mailto:dberlin at dberlin.org>> > >>>> >>> wrote: > >>>> >>> >> On Mon, Jul 17, 2017 at 10:32 AM, Xinliang David Li > >>>> >>> >> <davidxl at google.com <mailto:davidxl at google.com>> > >>>> >>> >> wrote: > >>>> >>> >> > The issue blocks another optimization patch and Wei > has spent > >>>> >>> >> > huge > >>>> >>> >> > amount of > >>>> >>> >> > effort isolating the the bootstrap failure to this > same problem. > >>>> >>> >> > I > >>>> >>> >> > agree > >>>> >>> >> > with Wei that other developers may also get hit by > the same issue > >>>> >>> >> > and > >>>> >>> >> > the > >>>> >>> >> > cost of leaving this issue open for long can be very > high to the > >>>> >>> >> > community. > >>>> >>> >> > >>>> >>> >> I can't speak for others, but I am fine with adding a > workaround > >>>> >>> >> for > >>>> >>> >> this. However, I suspect > isGuaranteedNotToBeUndefOrPoison in > >>>> >>> >> LoopUnswitch may regress other benchmarks. > >>>> >>> > > >>>> >>> > Any other thoughts on a more minimal fix? > >>>> >>> > >>>> >>> I can't think of any good answers here. > >>>> >>> > >>>> >>> The semantic we want is "branching on poison or undef is > undefined > >>>> >>> behavior" (which lets us do propagateEquality). Given > that, we could > >>>> >>> be clever about implementing > isGuaranteedNotToBeUndefOrPoison; for > >>>> >>> instance if we have: > >>>> >>> > >>>> >>> do { > >>>> >>> if (a != b) { > >>>> >>> ... > >>>> >>> } > >>>> >>> } while (...); > >>>> >>> > >>>> >>> then we can use post-domination to prove that "a != b" is > not undef > >>>> >>> (otherwise the loop is guaranteed to have undefined > behavior). > >>>> >>> > >>>> >>> (I hate to say this), a more aggressive fix is to > introduce a "freeze" > >>>> >>> intrinsic that freezes only an i1. LoopUnswitch would > wrap the loop > >>>> >>> invariant condition in this after hoisting the branch. > This would be > >>>> >>> a poor man's version of the more invasive patches > Juneyoung already > >>>> >>> has developed. > >>>> >>> > >>>> >>> -- Sanjoy > >>>> >>> _______________________________________________ > >>>> >>> LLVM Developers mailing list > >>>> >>> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> > >>>> >>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev> > >>>> >> > >>>> >> > >>>> >> > >>>> >> > >>>> >> -- > >>>> >> > >>>> >> Juneyoung Lee > >>>> >> Software Foundation Lab, Seoul National University > >>>> > > >>>> > > >>> > >>> > >>> > >>> _______________________________________________ > >>> LLVM Developers mailing list > >>> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> > >>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev> > >>> > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev> > > > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-- Hal Finkel Lead, Compiler Technology and Programming Languages Leadership Computing Facility Argonne National Laboratory -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170718/dd276f0e/attachment.html>
Xinliang David Li via llvm-dev
2017-Jul-19 00:21 UTC
[llvm-dev] A bug related with undef value when bootstrap MemorySSA.cpp
On Tue, Jul 18, 2017 at 4:15 PM, Hal Finkel <hfinkel at anl.gov> wrote:> > On 07/18/2017 06:03 PM, David Majnemer via llvm-dev wrote: > > I doubt it is possible for us to try and make any fix which is predicated > on eagerly treating undef in a particular way, refinement will always cause > these problems to come about... > > Given what I've seen in LLVM (and what I've learned from other compilers), > we probably have two choices: > 1. Rework undef so that it is an instruction, not a constant. This will > make it easy to unswitch, etc. because it would be stable. This approach is > used by other production quality compilers and is workable. Would also > result in a lot of churn. > 2. Keep undef as a constant, introduce freeze. Churn would mostly be > restricted to correctness fixes instead of to core IR representation. > > Note that option #1 is basically a short-hand for freeze(undef). > > We don't need to fix all the problems at the same time but I think we need > to start somewhere. I don't think there are any good shortcuts. > > > I agree; I don't think there are any good shortcuts here. Sadly, I think > we should follow our traditional policy: revert to green. Whatever commit > actually triggers the self-hosting bug, revert it (or effectively revert it > by disabling whatever it is by default). Then we should proceed with fixing > the underlying problem with all due haste. > > -Hal > >In this case, should the compiler not generate the reference to undefined value in the first place (i.e, from guarded to unguarded)? GCC also hoists the comparison a == i outside the loop, but its use is properly guarded: long i, k; if (hasval) { i = b; } k = 0; if (hasval) { t = (a == i); if (t) { if (i_hasval != hasval) return; m = m + 1; c = a + d + e + f; return; } else { /* if (t) --> false */ do { if (i_hasval != hasval) return; m = m + 1; c = a + b; i_hasval = 3; k++; } while (k < cnt); } else { /* if (hasval) -->false */ do { if (i_hasval != hasval) return; c = a + b; i_hasval = 3; k++; } while (k < cnt); } David> > > On Tue, Jul 18, 2017 at 3:40 PM, Wei Mi via llvm-dev < > llvm-dev at lists.llvm.org> wrote: > >> On Mon, Jul 17, 2017 at 5:11 PM, Wei Mi <wmi at google.com> wrote: >> > On Mon, Jul 17, 2017 at 2:09 PM, Sanjoy Das >> > <sanjoy at playingwithpointers.com> wrote: >> >> Hi, >> >> >> >> On Mon, Jul 17, 2017 at 1:56 PM, Daniel Berlin via llvm-dev >> >> <llvm-dev at lists.llvm.org> wrote: >> >>> >> >>> >> >>> On Mon, Jul 17, 2017 at 1:53 PM, Wei Mi <wmi at google.com> wrote: >> >>>> >> >>>> It seems MemorySSA.cpp is the only real code where we found the >> >>>> problem happening. >> >>> >> >>> >> >>> This is doubtful, ¸FWIW :) >> >>> >> >>>> >> >>>> Is it possible to change the source of >> >>>> MemorySSA.cpp to hide the problem and buy some time for now? Now we >> >>>> use an empty generic_def_path_iterator with Optional<ListIndex> N >> >>>> being initialized by None as the end of range. Can we initialize the >> >>>> Optional var with a special value instead of None? >> >>>> >> >>>> iterator_range<def_path_iterator> def_path(ListIndex From) { >> >>>> return make_range(def_path_iterator(this, From), >> def_path_iterator()); >> >>>> } >> >>>> >> >>> >> >>> Why does this work? >> >> >> >> Fwiw, I don't think this is a good idea. If it can happen in >> >> MemorySSA it can happen in other organic C++ source code too - think >> >> about what you're going to tell other folks who run into this issue, >> >> where such a workaround may be difficult to achieve or explain. >> >> >> >> -- Sanjoy >> > >> > Talked with David offline and he suggested a simple workaround >> > solution. For the case in MemorySSA.cpp, we have "if (a == b)" with b >> > being defined by a phi, and the phi has an undef operand. We can >> > recognize the simple pattern and give up loop unswitch for it. The >> > idea is not to use isGuaranteedNotToBeUndefOrPoison to prove >> > correctness, but just to rule out some patterns where such error may >> > appear. >> > >> > I admit the solution is far from ideal, but at least it is very simple >> > to implement, and serves to mitigate the immediate correctness issue >> > while avoiding performance regression. What do you think? >> > >> > Thanks, >> > Wei. >> >> I tried the idea and it worked for the simple case, but didn't work >> when compiling MemorySSA.cpp. That is because for the following >> pattern: >> >> foo(c) { >> b = phi(c, undef) >> t = (a == b) >> loop: >> if (t) >> end loop >> } >> >> cfgsimplify will convert it to >> foo(c) { >> b = select i1 cond i32 c, undef >> t = (a == b) >> loop: >> if (t) >> end loop >> } >> >> And instcombine can remove the select and generate: >> foo(c) { >> t = (a == c) >> loop: >> if (t) >> end loop >> } >> >> Now c is a param so loop unswitch kicks in. However, the argument of >> foo is undef too, so we run into the problem again. >> >> Wei. >> >> > >> >> >> >>> >> >>>> >> >>>> >> >>>> On Mon, Jul 17, 2017 at 1:37 PM, Daniel Berlin <dberlin at dberlin.org> >> >>>> wrote: >> >>>> > I think everyone agrees pretty much everything short of "Fix >> undef" will >> >>>> > not >> >>>> > fix the problem for good. >> >>>> > I think we are more trying to hide it well enough that we get the >> months >> >>>> > we >> >>>> > need for various folks to work on the larger proposals. >> >>>> > Which sucks, but not sure we have a better answer, because i don't >> think >> >>>> > we >> >>>> > are going to commit the freeze/etc patches tomorrow. >> >>>> > >> >>>> > >> >>>> > On Mon, Jul 17, 2017 at 1:34 PM, Juneyoung Lee >> >>>> > <juneyoung.lee at sf.snu.ac.kr> >> >>>> > wrote: >> >>>> >> >> >>>> >> Hello, some of the patches had conflicts with LLVM head, so I >> updated >> >>>> >> them. If you experienced patch failure before then you can try it >> >>>> >> again. >> >>>> >> >> >>>> >> I compiled your code (1.c) with LLVM r308173 with the 5 patches >> >>>> >> applied, >> >>>> >> and it generated assembly like this. Now it contains store to >> c(%rip). >> >>>> >> It tries to store a(%rip) + b(%rip) to c(%rip). I wish this >> translation >> >>>> >> is >> >>>> >> now correct. >> >>>> >> >> >>>> >> ``` >> >>>> >> 73 .globl hoo # -- Begin function hoo >> >>>> >> 74 .p2align 4, 0x90 >> >>>> >> 75 .type hoo, at function >> >>>> >> 76 hoo: # @hoo >> >>>> >> 77 .cfi_startproc >> >>>> >> 78 # BB#0: >> >>>> >> 79 movq a(%rip), %rax >> >>>> >> 80 movq cnt(%rip), %rcx >> >>>> >> 81 cmpq $0, i_hasval(%rip) >> >>>> >> 82 sete %sil >> >>>> >> 83 xorl %edx, %edx >> >>>> >> 84 .p2align 4, 0x90 >> >>>> >> 85 .LBB1_1: # =>This Inner Loop >> Header: >> >>>> >> Depth=1 >> >>>> >> 86 testb $1, %sil >> >>>> >> 87 je .LBB1_3 >> >>>> >> 88 # BB#2: # in Loop: >> Header=BB1_1 >> >>>> >> Depth=1 >> >>>> >> 89 movq b(%rip), %rsi >> >>>> >> 90 addq %rax, %rsi >> >>>> >> 91 movq %rsi, c(%rip) >> >>>> >> 92 movq $3, i_hasval(%rip) >> >>>> >> 93 incq %rdx >> >>>> >> 94 xorl %esi, %esi >> >>>> >> 95 cmpq %rcx, %rdx >> >>>> >> 96 jl .LBB1_1 >> >>>> >> 97 .LBB1_3: >> >>>> >> 98 retq >> >>>> >> ``` >> >>>> >> >> >>>> >> IMHO, enhancing `isGuaranteedNotToBeUndefOrPoison` and using it >> as a >> >>>> >> precondition in loop unswitching is >> >>>> >> not enough. undef (and poison) value can be stored into memory, >> and >> >>>> >> also >> >>>> >> be passed by a function argument. >> >>>> >> `isGuaranteedNotToBeUndefOrPoison` will virtually return `false` >> for >> >>>> >> all >> >>>> >> cases except the value is >> >>>> >> some integer constant. Sanjoy's suggestion might be helpful (if I >> >>>> >> understood correctly), but I'm >> >>>> >> not sure how much it will be. >> >>>> >> >> >>>> >> Best Regards, >> >>>> >> Juneyoung Lee >> >>>> >> >> >>>> >> On Tue, Jul 18, 2017 at 3:43 AM, Sanjoy Das via llvm-dev >> >>>> >> <llvm-dev at lists.llvm.org> wrote: >> >>>> >>> >> >>>> >>> On Mon, Jul 17, 2017 at 11:21 AM, Daniel Berlin < >> dberlin at dberlin.org> >> >>>> >>> wrote: >> >>>> >>> >> On Mon, Jul 17, 2017 at 10:32 AM, Xinliang David Li >> >>>> >>> >> <davidxl at google.com> >> >>>> >>> >> wrote: >> >>>> >>> >> > The issue blocks another optimization patch and Wei has >> spent >> >>>> >>> >> > huge >> >>>> >>> >> > amount of >> >>>> >>> >> > effort isolating the the bootstrap failure to this same >> problem. >> >>>> >>> >> > I >> >>>> >>> >> > agree >> >>>> >>> >> > with Wei that other developers may also get hit by the same >> issue >> >>>> >>> >> > and >> >>>> >>> >> > the >> >>>> >>> >> > cost of leaving this issue open for long can be very high >> to the >> >>>> >>> >> > community. >> >>>> >>> >> >> >>>> >>> >> I can't speak for others, but I am fine with adding a >> workaround >> >>>> >>> >> for >> >>>> >>> >> this. However, I suspect isGuaranteedNotToBeUndefOrPoison in >> >>>> >>> >> LoopUnswitch may regress other benchmarks. >> >>>> >>> > >> >>>> >>> > Any other thoughts on a more minimal fix? >> >>>> >>> >> >>>> >>> I can't think of any good answers here. >> >>>> >>> >> >>>> >>> The semantic we want is "branching on poison or undef is >> undefined >> >>>> >>> behavior" (which lets us do propagateEquality). Given that, we >> could >> >>>> >>> be clever about implementing isGuaranteedNotToBeUndefOrPoison; >> for >> >>>> >>> instance if we have: >> >>>> >>> >> >>>> >>> do { >> >>>> >>> if (a != b) { >> >>>> >>> ... >> >>>> >>> } >> >>>> >>> } while (...); >> >>>> >>> >> >>>> >>> then we can use post-domination to prove that "a != b" is not >> undef >> >>>> >>> (otherwise the loop is guaranteed to have undefined behavior). >> >>>> >>> >> >>>> >>> (I hate to say this), a more aggressive fix is to introduce a >> "freeze" >> >>>> >>> intrinsic that freezes only an i1. LoopUnswitch would wrap the >> loop >> >>>> >>> invariant condition in this after hoisting the branch. This >> would be >> >>>> >>> a poor man's version of the more invasive patches Juneyoung >> already >> >>>> >>> has developed. >> >>>> >>> >> >>>> >>> -- Sanjoy >> >>>> >>> _______________________________________________ >> >>>> >>> LLVM Developers mailing list >> >>>> >>> llvm-dev at lists.llvm.org >> >>>> >>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >> >>>> >> >> >>>> >> >> >>>> >> >> >>>> >> >> >>>> >> -- >> >>>> >> >> >>>> >> Juneyoung Lee >> >>>> >> Software Foundation Lab, Seoul National University >> >>>> > >> >>>> > >> >>> >> >>> >> >>> >> >>> _______________________________________________ >> >>> LLVM Developers mailing list >> >>> llvm-dev at lists.llvm.org >> >>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >> >>> >> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >> > > > > _______________________________________________ > LLVM Developers mailing listllvm-dev at lists.llvm.orghttp://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > > > -- > Hal Finkel > Lead, Compiler Technology and Programming Languages > Leadership Computing Facility > Argonne National Laboratory > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170718/a47fed6b/attachment.html>
Juneyoung Lee via llvm-dev
2017-Jul-22 21:36 UTC
[llvm-dev] A bug related with undef value when bootstrap MemorySSA.cpp
What if it is hard to find the condition of the guard? `a` can contain undefined value as well. Optimizations like ``` store %ptr, %v %w = load %ptr use(%w) -> store %ptr, %v use(%v) ``` can transform load from `a` into `undef`. Best Regards, Juneyoung Lee On Wed, Jul 19, 2017 at 9:21 AM, Xinliang David Li via llvm-dev < llvm-dev at lists.llvm.org> wrote:> > > On Tue, Jul 18, 2017 at 4:15 PM, Hal Finkel <hfinkel at anl.gov> wrote: > >> >> On 07/18/2017 06:03 PM, David Majnemer via llvm-dev wrote: >> >> I doubt it is possible for us to try and make any fix which is predicated >> on eagerly treating undef in a particular way, refinement will always cause >> these problems to come about... >> >> Given what I've seen in LLVM (and what I've learned from other >> compilers), we probably have two choices: >> 1. Rework undef so that it is an instruction, not a constant. This will >> make it easy to unswitch, etc. because it would be stable. This approach is >> used by other production quality compilers and is workable. Would also >> result in a lot of churn. >> 2. Keep undef as a constant, introduce freeze. Churn would mostly be >> restricted to correctness fixes instead of to core IR representation. >> >> Note that option #1 is basically a short-hand for freeze(undef). >> >> We don't need to fix all the problems at the same time but I think we >> need to start somewhere. I don't think there are any good shortcuts. >> >> >> I agree; I don't think there are any good shortcuts here. Sadly, I think >> we should follow our traditional policy: revert to green. Whatever commit >> actually triggers the self-hosting bug, revert it (or effectively revert it >> by disabling whatever it is by default). Then we should proceed with fixing >> the underlying problem with all due haste. >> >> -Hal >> >> > In this case, should the compiler not generate the reference to undefined > value in the first place (i.e, from guarded to unguarded)? GCC also > hoists the comparison a == i outside the loop, but its use is properly > guarded: > > > long i, k; > if (hasval) { > i = b; > } > > k = 0; > > if (hasval) { > t = (a == i); > if (t) { > if (i_hasval != hasval) > return; > > m = m + 1; > c = a + d + e + f; > return; > } else { /* if (t) --> false */ > do { > if (i_hasval != hasval) > return; > m = m + 1; > c = a + b; > i_hasval = 3; > k++; > } while (k < cnt); > > } else { /* if (hasval) -->false */ > > do { > if (i_hasval != hasval) > return; > c = a + b; > i_hasval = 3; > k++; > } while (k < cnt); > } > > > David > > >> >> >> On Tue, Jul 18, 2017 at 3:40 PM, Wei Mi via llvm-dev < >> llvm-dev at lists.llvm.org> wrote: >> >>> On Mon, Jul 17, 2017 at 5:11 PM, Wei Mi <wmi at google.com> wrote: >>> > On Mon, Jul 17, 2017 at 2:09 PM, Sanjoy Das >>> > <sanjoy at playingwithpointers.com> wrote: >>> >> Hi, >>> >> >>> >> On Mon, Jul 17, 2017 at 1:56 PM, Daniel Berlin via llvm-dev >>> >> <llvm-dev at lists.llvm.org> wrote: >>> >>> >>> >>> >>> >>> On Mon, Jul 17, 2017 at 1:53 PM, Wei Mi <wmi at google.com> wrote: >>> >>>> >>> >>>> It seems MemorySSA.cpp is the only real code where we found the >>> >>>> problem happening. >>> >>> >>> >>> >>> >>> This is doubtful, ¸FWIW :) >>> >>> >>> >>>> >>> >>>> Is it possible to change the source of >>> >>>> MemorySSA.cpp to hide the problem and buy some time for now? Now we >>> >>>> use an empty generic_def_path_iterator with Optional<ListIndex> N >>> >>>> being initialized by None as the end of range. Can we initialize the >>> >>>> Optional var with a special value instead of None? >>> >>>> >>> >>>> iterator_range<def_path_iterator> def_path(ListIndex From) { >>> >>>> return make_range(def_path_iterator(this, From), >>> def_path_iterator()); >>> >>>> } >>> >>>> >>> >>> >>> >>> Why does this work? >>> >> >>> >> Fwiw, I don't think this is a good idea. If it can happen in >>> >> MemorySSA it can happen in other organic C++ source code too - think >>> >> about what you're going to tell other folks who run into this issue, >>> >> where such a workaround may be difficult to achieve or explain. >>> >> >>> >> -- Sanjoy >>> > >>> > Talked with David offline and he suggested a simple workaround >>> > solution. For the case in MemorySSA.cpp, we have "if (a == b)" with b >>> > being defined by a phi, and the phi has an undef operand. We can >>> > recognize the simple pattern and give up loop unswitch for it. The >>> > idea is not to use isGuaranteedNotToBeUndefOrPoison to prove >>> > correctness, but just to rule out some patterns where such error may >>> > appear. >>> > >>> > I admit the solution is far from ideal, but at least it is very simple >>> > to implement, and serves to mitigate the immediate correctness issue >>> > while avoiding performance regression. What do you think? >>> > >>> > Thanks, >>> > Wei. >>> >>> I tried the idea and it worked for the simple case, but didn't work >>> when compiling MemorySSA.cpp. That is because for the following >>> pattern: >>> >>> foo(c) { >>> b = phi(c, undef) >>> t = (a == b) >>> loop: >>> if (t) >>> end loop >>> } >>> >>> cfgsimplify will convert it to >>> foo(c) { >>> b = select i1 cond i32 c, undef >>> t = (a == b) >>> loop: >>> if (t) >>> end loop >>> } >>> >>> And instcombine can remove the select and generate: >>> foo(c) { >>> t = (a == c) >>> loop: >>> if (t) >>> end loop >>> } >>> >>> Now c is a param so loop unswitch kicks in. However, the argument of >>> foo is undef too, so we run into the problem again. >>> >>> Wei. >>> >>> > >>> >> >>> >>> >>> >>>> >>> >>>> >>> >>>> On Mon, Jul 17, 2017 at 1:37 PM, Daniel Berlin <dberlin at dberlin.org >>> > >>> >>>> wrote: >>> >>>> > I think everyone agrees pretty much everything short of "Fix >>> undef" will >>> >>>> > not >>> >>>> > fix the problem for good. >>> >>>> > I think we are more trying to hide it well enough that we get the >>> months >>> >>>> > we >>> >>>> > need for various folks to work on the larger proposals. >>> >>>> > Which sucks, but not sure we have a better answer, because i >>> don't think >>> >>>> > we >>> >>>> > are going to commit the freeze/etc patches tomorrow. >>> >>>> > >>> >>>> > >>> >>>> > On Mon, Jul 17, 2017 at 1:34 PM, Juneyoung Lee >>> >>>> > <juneyoung.lee at sf.snu.ac.kr> >>> >>>> > wrote: >>> >>>> >> >>> >>>> >> Hello, some of the patches had conflicts with LLVM head, so I >>> updated >>> >>>> >> them. If you experienced patch failure before then you can try it >>> >>>> >> again. >>> >>>> >> >>> >>>> >> I compiled your code (1.c) with LLVM r308173 with the 5 patches >>> >>>> >> applied, >>> >>>> >> and it generated assembly like this. Now it contains store to >>> c(%rip). >>> >>>> >> It tries to store a(%rip) + b(%rip) to c(%rip). I wish this >>> translation >>> >>>> >> is >>> >>>> >> now correct. >>> >>>> >> >>> >>>> >> ``` >>> >>>> >> 73 .globl hoo # -- Begin function hoo >>> >>>> >> 74 .p2align 4, 0x90 >>> >>>> >> 75 .type hoo, at function >>> >>>> >> 76 hoo: # @hoo >>> >>>> >> 77 .cfi_startproc >>> >>>> >> 78 # BB#0: >>> >>>> >> 79 movq a(%rip), %rax >>> >>>> >> 80 movq cnt(%rip), %rcx >>> >>>> >> 81 cmpq $0, i_hasval(%rip) >>> >>>> >> 82 sete %sil >>> >>>> >> 83 xorl %edx, %edx >>> >>>> >> 84 .p2align 4, 0x90 >>> >>>> >> 85 .LBB1_1: # =>This Inner Loop >>> Header: >>> >>>> >> Depth=1 >>> >>>> >> 86 testb $1, %sil >>> >>>> >> 87 je .LBB1_3 >>> >>>> >> 88 # BB#2: # in Loop: >>> Header=BB1_1 >>> >>>> >> Depth=1 >>> >>>> >> 89 movq b(%rip), %rsi >>> >>>> >> 90 addq %rax, %rsi >>> >>>> >> 91 movq %rsi, c(%rip) >>> >>>> >> 92 movq $3, i_hasval(%rip) >>> >>>> >> 93 incq %rdx >>> >>>> >> 94 xorl %esi, %esi >>> >>>> >> 95 cmpq %rcx, %rdx >>> >>>> >> 96 jl .LBB1_1 >>> >>>> >> 97 .LBB1_3: >>> >>>> >> 98 retq >>> >>>> >> ``` >>> >>>> >> >>> >>>> >> IMHO, enhancing `isGuaranteedNotToBeUndefOrPoison` and using it >>> as a >>> >>>> >> precondition in loop unswitching is >>> >>>> >> not enough. undef (and poison) value can be stored into memory, >>> and >>> >>>> >> also >>> >>>> >> be passed by a function argument. >>> >>>> >> `isGuaranteedNotToBeUndefOrPoison` will virtually return >>> `false` for >>> >>>> >> all >>> >>>> >> cases except the value is >>> >>>> >> some integer constant. Sanjoy's suggestion might be helpful (if I >>> >>>> >> understood correctly), but I'm >>> >>>> >> not sure how much it will be. >>> >>>> >> >>> >>>> >> Best Regards, >>> >>>> >> Juneyoung Lee >>> >>>> >> >>> >>>> >> On Tue, Jul 18, 2017 at 3:43 AM, Sanjoy Das via llvm-dev >>> >>>> >> <llvm-dev at lists.llvm.org> wrote: >>> >>>> >>> >>> >>>> >>> On Mon, Jul 17, 2017 at 11:21 AM, Daniel Berlin < >>> dberlin at dberlin.org> >>> >>>> >>> wrote: >>> >>>> >>> >> On Mon, Jul 17, 2017 at 10:32 AM, Xinliang David Li >>> >>>> >>> >> <davidxl at google.com> >>> >>>> >>> >> wrote: >>> >>>> >>> >> > The issue blocks another optimization patch and Wei has >>> spent >>> >>>> >>> >> > huge >>> >>>> >>> >> > amount of >>> >>>> >>> >> > effort isolating the the bootstrap failure to this same >>> problem. >>> >>>> >>> >> > I >>> >>>> >>> >> > agree >>> >>>> >>> >> > with Wei that other developers may also get hit by the >>> same issue >>> >>>> >>> >> > and >>> >>>> >>> >> > the >>> >>>> >>> >> > cost of leaving this issue open for long can be very high >>> to the >>> >>>> >>> >> > community. >>> >>>> >>> >> >>> >>>> >>> >> I can't speak for others, but I am fine with adding a >>> workaround >>> >>>> >>> >> for >>> >>>> >>> >> this. However, I suspect isGuaranteedNotToBeUndefOrPoison >>> in >>> >>>> >>> >> LoopUnswitch may regress other benchmarks. >>> >>>> >>> > >>> >>>> >>> > Any other thoughts on a more minimal fix? >>> >>>> >>> >>> >>>> >>> I can't think of any good answers here. >>> >>>> >>> >>> >>>> >>> The semantic we want is "branching on poison or undef is >>> undefined >>> >>>> >>> behavior" (which lets us do propagateEquality). Given that, we >>> could >>> >>>> >>> be clever about implementing isGuaranteedNotToBeUndefOrPoison; >>> for >>> >>>> >>> instance if we have: >>> >>>> >>> >>> >>>> >>> do { >>> >>>> >>> if (a != b) { >>> >>>> >>> ... >>> >>>> >>> } >>> >>>> >>> } while (...); >>> >>>> >>> >>> >>>> >>> then we can use post-domination to prove that "a != b" is not >>> undef >>> >>>> >>> (otherwise the loop is guaranteed to have undefined behavior). >>> >>>> >>> >>> >>>> >>> (I hate to say this), a more aggressive fix is to introduce a >>> "freeze" >>> >>>> >>> intrinsic that freezes only an i1. LoopUnswitch would wrap the >>> loop >>> >>>> >>> invariant condition in this after hoisting the branch. This >>> would be >>> >>>> >>> a poor man's version of the more invasive patches Juneyoung >>> already >>> >>>> >>> has developed. >>> >>>> >>> >>> >>>> >>> -- Sanjoy >>> >>>> >>> _______________________________________________ >>> >>>> >>> LLVM Developers mailing list >>> >>>> >>> llvm-dev at lists.llvm.org >>> >>>> >>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>> >>>> >> >>> >>>> >> >>> >>>> >> >>> >>>> >> >>> >>>> >> -- >>> >>>> >> >>> >>>> >> Juneyoung Lee >>> >>>> >> Software Foundation Lab, Seoul National University >>> >>>> > >>> >>>> > >>> >>> >>> >>> >>> >>> >>> >>> _______________________________________________ >>> >>> LLVM Developers mailing list >>> >>> llvm-dev at lists.llvm.org >>> >>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>> >>> >>> _______________________________________________ >>> LLVM Developers mailing list >>> llvm-dev at lists.llvm.org >>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>> >> >> >> >> _______________________________________________ >> LLVM Developers mailing listllvm-dev at lists.llvm.orghttp://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >> >> >> -- >> Hal Finkel >> Lead, Compiler Technology and Programming Languages >> Leadership Computing Facility >> Argonne National Laboratory >> >> > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > >-- Juneyoung Lee Software Foundation Lab, Seoul National University -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170723/b126716e/attachment.html>