Sanjoy Das via llvm-dev
2017-Jul-17 21:09 UTC
[llvm-dev] A bug related with undef value when bootstrap MemorySSA.cpp
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> >> >> >> 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 >
Wei Mi via llvm-dev
2017-Jul-18 00:11 UTC
[llvm-dev] A bug related with undef value when bootstrap MemorySSA.cpp
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. > > -- SanjoyTalked 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.> >> >>> >>> >>> 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 >>
Xinliang David Li via llvm-dev
2017-Jul-18 00:35 UTC
[llvm-dev] A bug related with undef value when bootstrap MemorySSA.cpp
At runtime, without the hoisting, the undef value will never be referenced, but the speculative hoisting of the comparison introduces the real undef reference. Another workaround is to disable such speculative LICM in the first place. If it is hoisted, it should really be like: if (some_cond) t1 = (a == i) else t2 = undef t = phi(t1, t2) In this case, the condition is loop variant, so it is not possible. David 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. > > > > >> > >>> > >>> > >>> 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 > >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170717/936f9ca9/attachment-0001.html>
Wei Mi via llvm-dev
2017-Jul-18 22:40 UTC
[llvm-dev] A bug related with undef value when bootstrap MemorySSA.cpp
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 >>>
Possibly Parallel Threads
- A bug related with undef value when bootstrap MemorySSA.cpp
- A bug related with undef value when bootstrap MemorySSA.cpp
- A bug related with undef value when bootstrap MemorySSA.cpp
- A bug related with undef value when bootstrap MemorySSA.cpp
- A bug related with undef value when bootstrap MemorySSA.cpp