| Message ID | DB5PR0801MB2742138FC6CB70DAAE2B2D95E75D0@DB5PR0801MB2742.eurprd08.prod.outlook.com |
|---|---|
| State | New |
| Headers | show |
| Series | [PR82776] Exploit more undefined pointer overflow behavior in loop niter analysis | expand |
On Fri, Nov 3, 2017 at 1:35 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: > Hi, > This is a simple patch exploiting more undefined pointer overflow behavior in > loop niter analysis. Originally, it only supports POINTER_PLUS_EXPR if the > offset part is IV. This patch also handles the case if pointer is IV. With > this patch, the while(true) loop in test can be removed by cddce pass now. > > Bootstrap and test on x86_64 and AArch64. This patch introduces two failures: > FAIL: g++.dg/pr79095-1.C -std=gnu++98 (test for excess errors) > FAIL: g++.dg/pr79095-2.C -std=gnu++11 (test for excess errors) > I believe this exposes inaccurate value range information issue. For below code: > /* { dg-do compile } */ > /* { dg-options "-Wall -O3" } */ > > typedef long unsigned int size_t; > > inline void > fill (int *p, size_t n, int) > { > while (n--) > *p++ = 0; > } > > struct B > { > int* p0, *p1, *p2; > > size_t size () const { > return size_t (p1 - p0); > } > > void resize (size_t n) { > if (n > size()) > append (n - size()); > } > > void append (size_t n) > { > if (size_t (p2 - p1) >= n) { > fill (p1, n, 0); > } > } > }; > > void foo (B &b) > { > if (b.size () != 0) > b.resize (b.size () - 1); > } > > GCC gives below warning with this patch: > pr79095-1.C: In function ‘void foo(B&)’: > pr79095-1.C:10:7: warning: iteration 4611686018427387903 invokes undefined behavior [-Waggressive-loop-optimizations] > *p++ = 0; > ~^~ > pr79095-1.C:9:11: note: within this loop > while (n--) > ^~ > > Problem is VRP should understand that it's never the case with condition: > (size_t (p2 - p1) >= n) > in function B::append. > > So, any comment? I'm looking hard but I can't see you changed anything in infer_loop_bounds_from_pointer_arith besides adding a expr_invariant_in_loop_p (loop, rhs2) check. What am I missing? Richard. > Thanks, > bin > 2017-11-02 Bin Cheng <bin.cheng@arm.com> > > PR tree-optimization/82776 > * tree-ssa-loop-niter.c (infer_loop_bounds_from_pointer_arith): Handle > POINTER_PLUS_EXPR in which the pointer is an IV. > (infer_loop_bounds_from_signedness): Refine comment. > > gcc/testsuite > 2017-11-02 Bin Cheng <bin.cheng@arm.com> > > PR tree-optimization/82776 > * g++.dg/pr82776.C: New test. > * gcc.dg/tree-ssa/split-path-6.c: Refine test.
On Tue, Nov 7, 2017 at 10:44 AM, Richard Biener <richard.guenther@gmail.com> wrote: > On Fri, Nov 3, 2017 at 1:35 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: >> Hi, >> This is a simple patch exploiting more undefined pointer overflow behavior in >> loop niter analysis. Originally, it only supports POINTER_PLUS_EXPR if the >> offset part is IV. This patch also handles the case if pointer is IV. With >> this patch, the while(true) loop in test can be removed by cddce pass now. >> >> Bootstrap and test on x86_64 and AArch64. This patch introduces two failures: >> FAIL: g++.dg/pr79095-1.C -std=gnu++98 (test for excess errors) >> FAIL: g++.dg/pr79095-2.C -std=gnu++11 (test for excess errors) >> I believe this exposes inaccurate value range information issue. For below code: >> /* { dg-do compile } */ >> /* { dg-options "-Wall -O3" } */ >> >> typedef long unsigned int size_t; >> >> inline void >> fill (int *p, size_t n, int) >> { >> while (n--) >> *p++ = 0; >> } >> >> struct B >> { >> int* p0, *p1, *p2; >> >> size_t size () const { >> return size_t (p1 - p0); >> } >> >> void resize (size_t n) { >> if (n > size()) >> append (n - size()); >> } >> >> void append (size_t n) >> { >> if (size_t (p2 - p1) >= n) { >> fill (p1, n, 0); >> } >> } >> }; >> >> void foo (B &b) >> { >> if (b.size () != 0) >> b.resize (b.size () - 1); >> } >> >> GCC gives below warning with this patch: >> pr79095-1.C: In function ‘void foo(B&)’: >> pr79095-1.C:10:7: warning: iteration 4611686018427387903 invokes undefined behavior [-Waggressive-loop-optimizations] >> *p++ = 0; >> ~^~ >> pr79095-1.C:9:11: note: within this loop >> while (n--) >> ^~ >> >> Problem is VRP should understand that it's never the case with condition: >> (size_t (p2 - p1) >= n) >> in function B::append. >> >> So, any comment? > > I'm looking hard but I can't see you changed anything in > infer_loop_bounds_from_pointer_arith > besides adding a expr_invariant_in_loop_p (loop, rhs2) check. yes, that's enough for this fix? - ptr = gimple_assign_rhs1 (stmt); - if (!expr_invariant_in_loop_p (loop, ptr)) + rhs2 = gimple_assign_rhs2 (stmt); + if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (rhs2))) return; - var = gimple_assign_rhs2 (stmt); - if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var))) + rhs1 = gimple_assign_rhs1 (stmt); + if (!expr_invariant_in_loop_p (loop, rhs1) + && !expr_invariant_in_loop_p (loop, rhs2)) return; Before this change, the function skips if ptr in "res = ptr +p offset" is non-invariant. This change only skips if both ptr and offset are non-invariant, thus the PR is handled. Thanks, bin > > What am I missing? > > Richard. > >> Thanks, >> bin >> 2017-11-02 Bin Cheng <bin.cheng@arm.com> >> >> PR tree-optimization/82776 >> * tree-ssa-loop-niter.c (infer_loop_bounds_from_pointer_arith): Handle >> POINTER_PLUS_EXPR in which the pointer is an IV. >> (infer_loop_bounds_from_signedness): Refine comment. >> >> gcc/testsuite >> 2017-11-02 Bin Cheng <bin.cheng@arm.com> >> >> PR tree-optimization/82776 >> * g++.dg/pr82776.C: New test. >> * gcc.dg/tree-ssa/split-path-6.c: Refine test.
On Tue, Nov 7, 2017 at 1:17 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: > On Tue, Nov 7, 2017 at 10:44 AM, Richard Biener > <richard.guenther@gmail.com> wrote: >> On Fri, Nov 3, 2017 at 1:35 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: >>> Hi, >>> This is a simple patch exploiting more undefined pointer overflow behavior in >>> loop niter analysis. Originally, it only supports POINTER_PLUS_EXPR if the >>> offset part is IV. This patch also handles the case if pointer is IV. With >>> this patch, the while(true) loop in test can be removed by cddce pass now. >>> >>> Bootstrap and test on x86_64 and AArch64. This patch introduces two failures: >>> FAIL: g++.dg/pr79095-1.C -std=gnu++98 (test for excess errors) >>> FAIL: g++.dg/pr79095-2.C -std=gnu++11 (test for excess errors) >>> I believe this exposes inaccurate value range information issue. For below code: >>> /* { dg-do compile } */ >>> /* { dg-options "-Wall -O3" } */ >>> >>> typedef long unsigned int size_t; >>> >>> inline void >>> fill (int *p, size_t n, int) >>> { >>> while (n--) >>> *p++ = 0; >>> } >>> >>> struct B >>> { >>> int* p0, *p1, *p2; >>> >>> size_t size () const { >>> return size_t (p1 - p0); >>> } >>> >>> void resize (size_t n) { >>> if (n > size()) >>> append (n - size()); >>> } >>> >>> void append (size_t n) >>> { >>> if (size_t (p2 - p1) >= n) { >>> fill (p1, n, 0); >>> } >>> } >>> }; >>> >>> void foo (B &b) >>> { >>> if (b.size () != 0) >>> b.resize (b.size () - 1); >>> } >>> >>> GCC gives below warning with this patch: >>> pr79095-1.C: In function ‘void foo(B&)’: >>> pr79095-1.C:10:7: warning: iteration 4611686018427387903 invokes undefined behavior [-Waggressive-loop-optimizations] >>> *p++ = 0; >>> ~^~ >>> pr79095-1.C:9:11: note: within this loop >>> while (n--) >>> ^~ >>> >>> Problem is VRP should understand that it's never the case with condition: >>> (size_t (p2 - p1) >= n) >>> in function B::append. >>> >>> So, any comment? Does it warn when not inlining fill()? Isn't the issue that one test tests p2 - p1 and the loop goes from p1 to p1 + (p1 - p0)? What kind of optimization do we apply to the loop in fill? >> I'm looking hard but I can't see you changed anything in >> infer_loop_bounds_from_pointer_arith >> besides adding a expr_invariant_in_loop_p (loop, rhs2) check. > yes, that's enough for this fix? > > - ptr = gimple_assign_rhs1 (stmt); > - if (!expr_invariant_in_loop_p (loop, ptr)) > + rhs2 = gimple_assign_rhs2 (stmt); > + if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (rhs2))) > return; > > - var = gimple_assign_rhs2 (stmt); > - if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var))) > + rhs1 = gimple_assign_rhs1 (stmt); > + if (!expr_invariant_in_loop_p (loop, rhs1) > + && !expr_invariant_in_loop_p (loop, rhs2)) > return; > > Before this change, the function skips if ptr in "res = ptr +p offset" > is non-invariant. This change only skips if both ptr and offset are > non-invariant, thus the PR is handled. Ah, of course. Thanks for the explanation. > Thanks, > bin > > >> >> What am I missing? >> >> Richard. >> >>> Thanks, >>> bin >>> 2017-11-02 Bin Cheng <bin.cheng@arm.com> >>> >>> PR tree-optimization/82776 >>> * tree-ssa-loop-niter.c (infer_loop_bounds_from_pointer_arith): Handle >>> POINTER_PLUS_EXPR in which the pointer is an IV. >>> (infer_loop_bounds_from_signedness): Refine comment. >>> >>> gcc/testsuite >>> 2017-11-02 Bin Cheng <bin.cheng@arm.com> >>> >>> PR tree-optimization/82776 >>> * g++.dg/pr82776.C: New test. >>> * gcc.dg/tree-ssa/split-path-6.c: Refine test.
On Tue, Nov 7, 2017 at 12:23 PM, Richard Biener <richard.guenther@gmail.com> wrote: > On Tue, Nov 7, 2017 at 1:17 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >> On Tue, Nov 7, 2017 at 10:44 AM, Richard Biener >> <richard.guenther@gmail.com> wrote: >>> On Fri, Nov 3, 2017 at 1:35 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: >>>> Hi, >>>> This is a simple patch exploiting more undefined pointer overflow behavior in >>>> loop niter analysis. Originally, it only supports POINTER_PLUS_EXPR if the >>>> offset part is IV. This patch also handles the case if pointer is IV. With >>>> this patch, the while(true) loop in test can be removed by cddce pass now. >>>> >>>> Bootstrap and test on x86_64 and AArch64. This patch introduces two failures: >>>> FAIL: g++.dg/pr79095-1.C -std=gnu++98 (test for excess errors) >>>> FAIL: g++.dg/pr79095-2.C -std=gnu++11 (test for excess errors) >>>> I believe this exposes inaccurate value range information issue. For below code: >>>> /* { dg-do compile } */ >>>> /* { dg-options "-Wall -O3" } */ >>>> >>>> typedef long unsigned int size_t; >>>> >>>> inline void >>>> fill (int *p, size_t n, int) >>>> { >>>> while (n--) >>>> *p++ = 0; >>>> } >>>> >>>> struct B >>>> { >>>> int* p0, *p1, *p2; >>>> >>>> size_t size () const { >>>> return size_t (p1 - p0); >>>> } >>>> >>>> void resize (size_t n) { >>>> if (n > size()) >>>> append (n - size()); >>>> } >>>> >>>> void append (size_t n) >>>> { >>>> if (size_t (p2 - p1) >= n) { >>>> fill (p1, n, 0); >>>> } >>>> } >>>> }; >>>> >>>> void foo (B &b) >>>> { >>>> if (b.size () != 0) >>>> b.resize (b.size () - 1); >>>> } >>>> >>>> GCC gives below warning with this patch: >>>> pr79095-1.C: In function ‘void foo(B&)’: >>>> pr79095-1.C:10:7: warning: iteration 4611686018427387903 invokes undefined behavior [-Waggressive-loop-optimizations] >>>> *p++ = 0; >>>> ~^~ >>>> pr79095-1.C:9:11: note: within this loop >>>> while (n--) >>>> ^~ >>>> >>>> Problem is VRP should understand that it's never the case with condition: >>>> (size_t (p2 - p1) >= n) >>>> in function B::append. >>>> >>>> So, any comment? > > Does it warn when not inlining fill()? Isn't the issue that one test With this patch, yes. > tests p2 - p1 and > the loop goes from p1 to p1 + (p1 - p0)? don't follow here. so the code is: >>>> inline void >>>> fill (int *p, size_t n, int) >>>> { >>>> while (n--) >>>> *p++ = 0; >>>> } >>>> void append (size_t n) >>>> { >>>> if (size_t (p2 - p1) >= n) { >>>> fill (p1, n, 0); >>>> } fill is only called if size_t (p2 - p1) >= n, so while loop in fill can only zero-out memory range [p1, p2)? > > What kind of optimization do we apply to the loop in fill? Depends on some conditions, the loop could be distributed into memset. Anyway, the warning message is issued as long as niter analysis believes it takes advantage of undefined pointer overflow behavior. Thanks, bin > >>> I'm looking hard but I can't see you changed anything in >>> infer_loop_bounds_from_pointer_arith >>> besides adding a expr_invariant_in_loop_p (loop, rhs2) check. >> yes, that's enough for this fix? >> >> - ptr = gimple_assign_rhs1 (stmt); >> - if (!expr_invariant_in_loop_p (loop, ptr)) >> + rhs2 = gimple_assign_rhs2 (stmt); >> + if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (rhs2))) >> return; >> >> - var = gimple_assign_rhs2 (stmt); >> - if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var))) >> + rhs1 = gimple_assign_rhs1 (stmt); >> + if (!expr_invariant_in_loop_p (loop, rhs1) >> + && !expr_invariant_in_loop_p (loop, rhs2)) >> return; >> >> Before this change, the function skips if ptr in "res = ptr +p offset" >> is non-invariant. This change only skips if both ptr and offset are >> non-invariant, thus the PR is handled. > > Ah, of course. Thanks for the explanation. > >> Thanks, >> bin >> >> >>> >>> What am I missing? >>> >>> Richard. >>> >>>> Thanks, >>>> bin >>>> 2017-11-02 Bin Cheng <bin.cheng@arm.com> >>>> >>>> PR tree-optimization/82776 >>>> * tree-ssa-loop-niter.c (infer_loop_bounds_from_pointer_arith): Handle >>>> POINTER_PLUS_EXPR in which the pointer is an IV. >>>> (infer_loop_bounds_from_signedness): Refine comment. >>>> >>>> gcc/testsuite >>>> 2017-11-02 Bin Cheng <bin.cheng@arm.com> >>>> >>>> PR tree-optimization/82776 >>>> * g++.dg/pr82776.C: New test. >>>> * gcc.dg/tree-ssa/split-path-6.c: Refine test.
On Tue, Nov 7, 2017 at 1:44 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: > On Tue, Nov 7, 2017 at 12:23 PM, Richard Biener > <richard.guenther@gmail.com> wrote: >> On Tue, Nov 7, 2017 at 1:17 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >>> On Tue, Nov 7, 2017 at 10:44 AM, Richard Biener >>> <richard.guenther@gmail.com> wrote: >>>> On Fri, Nov 3, 2017 at 1:35 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: >>>>> Hi, >>>>> This is a simple patch exploiting more undefined pointer overflow behavior in >>>>> loop niter analysis. Originally, it only supports POINTER_PLUS_EXPR if the >>>>> offset part is IV. This patch also handles the case if pointer is IV. With >>>>> this patch, the while(true) loop in test can be removed by cddce pass now. >>>>> >>>>> Bootstrap and test on x86_64 and AArch64. This patch introduces two failures: >>>>> FAIL: g++.dg/pr79095-1.C -std=gnu++98 (test for excess errors) >>>>> FAIL: g++.dg/pr79095-2.C -std=gnu++11 (test for excess errors) >>>>> I believe this exposes inaccurate value range information issue. For below code: >>>>> /* { dg-do compile } */ >>>>> /* { dg-options "-Wall -O3" } */ >>>>> >>>>> typedef long unsigned int size_t; >>>>> >>>>> inline void >>>>> fill (int *p, size_t n, int) >>>>> { >>>>> while (n--) >>>>> *p++ = 0; >>>>> } >>>>> >>>>> struct B >>>>> { >>>>> int* p0, *p1, *p2; >>>>> >>>>> size_t size () const { >>>>> return size_t (p1 - p0); >>>>> } >>>>> >>>>> void resize (size_t n) { >>>>> if (n > size()) >>>>> append (n - size()); >>>>> } >>>>> >>>>> void append (size_t n) >>>>> { >>>>> if (size_t (p2 - p1) >= n) { >>>>> fill (p1, n, 0); >>>>> } >>>>> } >>>>> }; >>>>> >>>>> void foo (B &b) >>>>> { >>>>> if (b.size () != 0) >>>>> b.resize (b.size () - 1); >>>>> } >>>>> >>>>> GCC gives below warning with this patch: >>>>> pr79095-1.C: In function ‘void foo(B&)’: >>>>> pr79095-1.C:10:7: warning: iteration 4611686018427387903 invokes undefined behavior [-Waggressive-loop-optimizations] >>>>> *p++ = 0; >>>>> ~^~ >>>>> pr79095-1.C:9:11: note: within this loop >>>>> while (n--) >>>>> ^~ >>>>> >>>>> Problem is VRP should understand that it's never the case with condition: >>>>> (size_t (p2 - p1) >= n) >>>>> in function B::append. >>>>> >>>>> So, any comment? >> >> Does it warn when not inlining fill()? Isn't the issue that one test > With this patch, yes. >> tests p2 - p1 and >> the loop goes from p1 to p1 + (p1 - p0)? > don't follow here. so the code is: > >>>>> inline void >>>>> fill (int *p, size_t n, int) >>>>> { >>>>> while (n--) >>>>> *p++ = 0; >>>>> } > >>>>> void append (size_t n) >>>>> { >>>>> if (size_t (p2 - p1) >= n) { >>>>> fill (p1, n, 0); >>>>> } > > fill is only called if size_t (p2 - p1) >= n, so while loop in fill > can only zero-out memory range [p1, p2)? what happens if p1 is before p0? The compare p2 - p1 >= p1 - p0 doesn't tell us much when iterating from p1 to p1 + ((p1 - p0) - 1), no? > >> >> What kind of optimization do we apply to the loop in fill? > Depends on some conditions, the loop could be distributed into memset. > Anyway, the warning message is issued as long as niter analysis > believes it takes advantage of undefined pointer overflow behavior. Hmm, yes. Not sure if the warning will be too noisy in the end. I'd say go ahead and add a dg-warning for the testcase for the moment. Thanks, Richard. > Thanks, > bin >> >>>> I'm looking hard but I can't see you changed anything in >>>> infer_loop_bounds_from_pointer_arith >>>> besides adding a expr_invariant_in_loop_p (loop, rhs2) check. >>> yes, that's enough for this fix? >>> >>> - ptr = gimple_assign_rhs1 (stmt); >>> - if (!expr_invariant_in_loop_p (loop, ptr)) >>> + rhs2 = gimple_assign_rhs2 (stmt); >>> + if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (rhs2))) >>> return; >>> >>> - var = gimple_assign_rhs2 (stmt); >>> - if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var))) >>> + rhs1 = gimple_assign_rhs1 (stmt); >>> + if (!expr_invariant_in_loop_p (loop, rhs1) >>> + && !expr_invariant_in_loop_p (loop, rhs2)) >>> return; >>> >>> Before this change, the function skips if ptr in "res = ptr +p offset" >>> is non-invariant. This change only skips if both ptr and offset are >>> non-invariant, thus the PR is handled. >> >> Ah, of course. Thanks for the explanation. >> >>> Thanks, >>> bin >>> >>> >>>> >>>> What am I missing? >>>> >>>> Richard. >>>> >>>>> Thanks, >>>>> bin >>>>> 2017-11-02 Bin Cheng <bin.cheng@arm.com> >>>>> >>>>> PR tree-optimization/82776 >>>>> * tree-ssa-loop-niter.c (infer_loop_bounds_from_pointer_arith): Handle >>>>> POINTER_PLUS_EXPR in which the pointer is an IV. >>>>> (infer_loop_bounds_from_signedness): Refine comment. >>>>> >>>>> gcc/testsuite >>>>> 2017-11-02 Bin Cheng <bin.cheng@arm.com> >>>>> >>>>> PR tree-optimization/82776 >>>>> * g++.dg/pr82776.C: New test. >>>>> * gcc.dg/tree-ssa/split-path-6.c: Refine test.
On Wed, Nov 8, 2017 at 11:55 AM, Richard Biener <richard.guenther@gmail.com> wrote: > On Tue, Nov 7, 2017 at 1:44 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >> On Tue, Nov 7, 2017 at 12:23 PM, Richard Biener >> <richard.guenther@gmail.com> wrote: >>> On Tue, Nov 7, 2017 at 1:17 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >>>> On Tue, Nov 7, 2017 at 10:44 AM, Richard Biener >>>> <richard.guenther@gmail.com> wrote: >>>>> On Fri, Nov 3, 2017 at 1:35 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: >>>>>> Hi, >>>>>> This is a simple patch exploiting more undefined pointer overflow behavior in >>>>>> loop niter analysis. Originally, it only supports POINTER_PLUS_EXPR if the >>>>>> offset part is IV. This patch also handles the case if pointer is IV. With >>>>>> this patch, the while(true) loop in test can be removed by cddce pass now. >>>>>> >>>>>> Bootstrap and test on x86_64 and AArch64. This patch introduces two failures: >>>>>> FAIL: g++.dg/pr79095-1.C -std=gnu++98 (test for excess errors) >>>>>> FAIL: g++.dg/pr79095-2.C -std=gnu++11 (test for excess errors) >>>>>> I believe this exposes inaccurate value range information issue. For below code: >>>>>> /* { dg-do compile } */ >>>>>> /* { dg-options "-Wall -O3" } */ >>>>>> >>>>>> typedef long unsigned int size_t; >>>>>> >>>>>> inline void >>>>>> fill (int *p, size_t n, int) >>>>>> { >>>>>> while (n--) >>>>>> *p++ = 0; >>>>>> } >>>>>> >>>>>> struct B >>>>>> { >>>>>> int* p0, *p1, *p2; >>>>>> >>>>>> size_t size () const { >>>>>> return size_t (p1 - p0); >>>>>> } >>>>>> >>>>>> void resize (size_t n) { >>>>>> if (n > size()) >>>>>> append (n - size()); >>>>>> } >>>>>> >>>>>> void append (size_t n) >>>>>> { >>>>>> if (size_t (p2 - p1) >= n) { >>>>>> fill (p1, n, 0); >>>>>> } >>>>>> } >>>>>> }; >>>>>> >>>>>> void foo (B &b) >>>>>> { >>>>>> if (b.size () != 0) >>>>>> b.resize (b.size () - 1); >>>>>> } >>>>>> >>>>>> GCC gives below warning with this patch: >>>>>> pr79095-1.C: In function ‘void foo(B&)’: >>>>>> pr79095-1.C:10:7: warning: iteration 4611686018427387903 invokes undefined behavior [-Waggressive-loop-optimizations] >>>>>> *p++ = 0; >>>>>> ~^~ >>>>>> pr79095-1.C:9:11: note: within this loop >>>>>> while (n--) >>>>>> ^~ >>>>>> >>>>>> Problem is VRP should understand that it's never the case with condition: >>>>>> (size_t (p2 - p1) >= n) >>>>>> in function B::append. >>>>>> >>>>>> So, any comment? >>> >>> Does it warn when not inlining fill()? Isn't the issue that one test >> With this patch, yes. >>> tests p2 - p1 and >>> the loop goes from p1 to p1 + (p1 - p0)? >> don't follow here. so the code is: >> >>>>>> inline void >>>>>> fill (int *p, size_t n, int) >>>>>> { >>>>>> while (n--) >>>>>> *p++ = 0; >>>>>> } >> >>>>>> void append (size_t n) >>>>>> { >>>>>> if (size_t (p2 - p1) >= n) { >>>>>> fill (p1, n, 0); >>>>>> } >> >> fill is only called if size_t (p2 - p1) >= n, so while loop in fill >> can only zero-out memory range [p1, p2)? > > what happens if p1 is before p0? The compare > p2 - p1 >= p1 - p0 doesn't tell us much when > iterating from p1 to p1 + ((p1 - p0) - 1), no? I double thought on this. Looks like the warning message is not spurious when p2 is before p1, in which case we have no information about argument "n" to the call of fill. Otherwise, if p1 is before p2, we can always assume n has value that *p++ never overflow. In this case it has nothing to do with p0, right? > >> >>> >>> What kind of optimization do we apply to the loop in fill? >> Depends on some conditions, the loop could be distributed into memset. >> Anyway, the warning message is issued as long as niter analysis >> believes it takes advantage of undefined pointer overflow behavior. > > Hmm, yes. > > Not sure if the warning will be too noisy in the end. I'd say go ahead I guess it could be too noisy. And as above, the warning looks like correct? Thanks, bin > and add a dg-warning for the testcase for the moment. > > Thanks, > Richard. > >> Thanks, >> bin >>> >>>>> I'm looking hard but I can't see you changed anything in >>>>> infer_loop_bounds_from_pointer_arith >>>>> besides adding a expr_invariant_in_loop_p (loop, rhs2) check. >>>> yes, that's enough for this fix? >>>> >>>> - ptr = gimple_assign_rhs1 (stmt); >>>> - if (!expr_invariant_in_loop_p (loop, ptr)) >>>> + rhs2 = gimple_assign_rhs2 (stmt); >>>> + if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (rhs2))) >>>> return; >>>> >>>> - var = gimple_assign_rhs2 (stmt); >>>> - if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var))) >>>> + rhs1 = gimple_assign_rhs1 (stmt); >>>> + if (!expr_invariant_in_loop_p (loop, rhs1) >>>> + && !expr_invariant_in_loop_p (loop, rhs2)) >>>> return; >>>> >>>> Before this change, the function skips if ptr in "res = ptr +p offset" >>>> is non-invariant. This change only skips if both ptr and offset are >>>> non-invariant, thus the PR is handled. >>> >>> Ah, of course. Thanks for the explanation. >>> >>>> Thanks, >>>> bin >>>> >>>> >>>>> >>>>> What am I missing? >>>>> >>>>> Richard. >>>>> >>>>>> Thanks, >>>>>> bin >>>>>> 2017-11-02 Bin Cheng <bin.cheng@arm.com> >>>>>> >>>>>> PR tree-optimization/82776 >>>>>> * tree-ssa-loop-niter.c (infer_loop_bounds_from_pointer_arith): Handle >>>>>> POINTER_PLUS_EXPR in which the pointer is an IV. >>>>>> (infer_loop_bounds_from_signedness): Refine comment. >>>>>> >>>>>> gcc/testsuite >>>>>> 2017-11-02 Bin Cheng <bin.cheng@arm.com> >>>>>> >>>>>> PR tree-optimization/82776 >>>>>> * g++.dg/pr82776.C: New test. >>>>>> * gcc.dg/tree-ssa/split-path-6.c: Refine test.
On Wed, Nov 8, 2017 at 1:25 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: > On Wed, Nov 8, 2017 at 11:55 AM, Richard Biener > <richard.guenther@gmail.com> wrote: >> On Tue, Nov 7, 2017 at 1:44 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >>> On Tue, Nov 7, 2017 at 12:23 PM, Richard Biener >>> <richard.guenther@gmail.com> wrote: >>>> On Tue, Nov 7, 2017 at 1:17 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >>>>> On Tue, Nov 7, 2017 at 10:44 AM, Richard Biener >>>>> <richard.guenther@gmail.com> wrote: >>>>>> On Fri, Nov 3, 2017 at 1:35 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: >>>>>>> Hi, >>>>>>> This is a simple patch exploiting more undefined pointer overflow behavior in >>>>>>> loop niter analysis. Originally, it only supports POINTER_PLUS_EXPR if the >>>>>>> offset part is IV. This patch also handles the case if pointer is IV. With >>>>>>> this patch, the while(true) loop in test can be removed by cddce pass now. >>>>>>> >>>>>>> Bootstrap and test on x86_64 and AArch64. This patch introduces two failures: >>>>>>> FAIL: g++.dg/pr79095-1.C -std=gnu++98 (test for excess errors) >>>>>>> FAIL: g++.dg/pr79095-2.C -std=gnu++11 (test for excess errors) >>>>>>> I believe this exposes inaccurate value range information issue. For below code: >>>>>>> /* { dg-do compile } */ >>>>>>> /* { dg-options "-Wall -O3" } */ >>>>>>> >>>>>>> typedef long unsigned int size_t; >>>>>>> >>>>>>> inline void >>>>>>> fill (int *p, size_t n, int) >>>>>>> { >>>>>>> while (n--) >>>>>>> *p++ = 0; >>>>>>> } >>>>>>> >>>>>>> struct B >>>>>>> { >>>>>>> int* p0, *p1, *p2; >>>>>>> >>>>>>> size_t size () const { >>>>>>> return size_t (p1 - p0); >>>>>>> } >>>>>>> >>>>>>> void resize (size_t n) { >>>>>>> if (n > size()) >>>>>>> append (n - size()); >>>>>>> } >>>>>>> >>>>>>> void append (size_t n) >>>>>>> { >>>>>>> if (size_t (p2 - p1) >= n) { >>>>>>> fill (p1, n, 0); >>>>>>> } >>>>>>> } >>>>>>> }; >>>>>>> >>>>>>> void foo (B &b) >>>>>>> { >>>>>>> if (b.size () != 0) >>>>>>> b.resize (b.size () - 1); >>>>>>> } >>>>>>> >>>>>>> GCC gives below warning with this patch: >>>>>>> pr79095-1.C: In function ‘void foo(B&)’: >>>>>>> pr79095-1.C:10:7: warning: iteration 4611686018427387903 invokes undefined behavior [-Waggressive-loop-optimizations] >>>>>>> *p++ = 0; >>>>>>> ~^~ >>>>>>> pr79095-1.C:9:11: note: within this loop >>>>>>> while (n--) >>>>>>> ^~ >>>>>>> >>>>>>> Problem is VRP should understand that it's never the case with condition: >>>>>>> (size_t (p2 - p1) >= n) >>>>>>> in function B::append. >>>>>>> >>>>>>> So, any comment? >>>> >>>> Does it warn when not inlining fill()? Isn't the issue that one test >>> With this patch, yes. >>>> tests p2 - p1 and >>>> the loop goes from p1 to p1 + (p1 - p0)? >>> don't follow here. so the code is: >>> >>>>>>> inline void >>>>>>> fill (int *p, size_t n, int) >>>>>>> { >>>>>>> while (n--) >>>>>>> *p++ = 0; >>>>>>> } >>> >>>>>>> void append (size_t n) >>>>>>> { >>>>>>> if (size_t (p2 - p1) >= n) { >>>>>>> fill (p1, n, 0); >>>>>>> } >>> >>> fill is only called if size_t (p2 - p1) >= n, so while loop in fill >>> can only zero-out memory range [p1, p2)? >> >> what happens if p1 is before p0? The compare >> p2 - p1 >= p1 - p0 doesn't tell us much when >> iterating from p1 to p1 + ((p1 - p0) - 1), no? > I double thought on this. Looks like the warning message is not > spurious when p2 is before p1, in which case we have no information > about argument "n" to the call of fill. > Otherwise, if p1 is before p2, we can always assume n has value that > *p++ never overflow. In this case it has nothing to do with p0, > right? >> >>> >>>> >>>> What kind of optimization do we apply to the loop in fill? >>> Depends on some conditions, the loop could be distributed into memset. >>> Anyway, the warning message is issued as long as niter analysis >>> believes it takes advantage of undefined pointer overflow behavior. >> >> Hmm, yes. >> >> Not sure if the warning will be too noisy in the end. I'd say go ahead > I guess it could be too noisy. And as above, the warning looks like correct? Yes, it does. Richard. > Thanks, > bin >> and add a dg-warning for the testcase for the moment. >> >> Thanks, >> Richard. >> >>> Thanks, >>> bin >>>> >>>>>> I'm looking hard but I can't see you changed anything in >>>>>> infer_loop_bounds_from_pointer_arith >>>>>> besides adding a expr_invariant_in_loop_p (loop, rhs2) check. >>>>> yes, that's enough for this fix? >>>>> >>>>> - ptr = gimple_assign_rhs1 (stmt); >>>>> - if (!expr_invariant_in_loop_p (loop, ptr)) >>>>> + rhs2 = gimple_assign_rhs2 (stmt); >>>>> + if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (rhs2))) >>>>> return; >>>>> >>>>> - var = gimple_assign_rhs2 (stmt); >>>>> - if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var))) >>>>> + rhs1 = gimple_assign_rhs1 (stmt); >>>>> + if (!expr_invariant_in_loop_p (loop, rhs1) >>>>> + && !expr_invariant_in_loop_p (loop, rhs2)) >>>>> return; >>>>> >>>>> Before this change, the function skips if ptr in "res = ptr +p offset" >>>>> is non-invariant. This change only skips if both ptr and offset are >>>>> non-invariant, thus the PR is handled. >>>> >>>> Ah, of course. Thanks for the explanation. >>>> >>>>> Thanks, >>>>> bin >>>>> >>>>> >>>>>> >>>>>> What am I missing? >>>>>> >>>>>> Richard. >>>>>> >>>>>>> Thanks, >>>>>>> bin >>>>>>> 2017-11-02 Bin Cheng <bin.cheng@arm.com> >>>>>>> >>>>>>> PR tree-optimization/82776 >>>>>>> * tree-ssa-loop-niter.c (infer_loop_bounds_from_pointer_arith): Handle >>>>>>> POINTER_PLUS_EXPR in which the pointer is an IV. >>>>>>> (infer_loop_bounds_from_signedness): Refine comment. >>>>>>> >>>>>>> gcc/testsuite >>>>>>> 2017-11-02 Bin Cheng <bin.cheng@arm.com> >>>>>>> >>>>>>> PR tree-optimization/82776 >>>>>>> * g++.dg/pr82776.C: New test. >>>>>>> * gcc.dg/tree-ssa/split-path-6.c: Refine test.
diff --git a/gcc/testsuite/g++.dg/pr82776.C b/gcc/testsuite/g++.dg/pr82776.C new file mode 100644 index 0000000..2a66817 --- /dev/null +++ b/gcc/testsuite/g++.dg/pr82776.C @@ -0,0 +1,78 @@ +// PR tree-optimization/82776 +// { dg-do compile } +// { dg-options "-O2 -std=c++14 -fdump-tree-cddce2-details" } + +#include <type_traits> +#include <cstdint> +#include <vector> +#include <cstdlib> +#include <array> +#include <memory> + + +unsigned baz (unsigned); + +struct Chunk { + std::array<uint8_t,14> tags_; + uint8_t control_; + + bool eof() const { + return (control_ & 1) != 0; + } + + static constexpr unsigned kFullMask = (1 << 14) - 1; + + unsigned occupiedMask() const { + return baz (kFullMask); + } +}; + +#define LIKELY(x) __builtin_expect((x), true) +#define UNLIKELY(x) __builtin_expect((x), false) + +struct Iter { + Chunk* chunk_; + std::size_t index_; + + void advance() { + // common case is packed entries + while (index_ > 0) { + --index_; + if (LIKELY(chunk_->tags_[index_] != 0)) { + return; + } + } + + // bar only skips the work of advance() if this loop can + // be guaranteed to terminate +#ifdef ENABLE_FORLOOP + for (std::size_t i = 1; i != 0; ++i) { +#else + while (true) { +#endif + // exhausted the current chunk + if (chunk_->eof()) { + chunk_ = nullptr; + break; + } + ++chunk_; + auto m = chunk_->occupiedMask(); + if (m != 0) { + index_ = 31 - __builtin_clz(m); + break; + } + } + } +}; + +static Iter foo(Iter iter) { + puts("hello"); + iter.advance(); + return iter; +} + +void bar(Iter iter) { + foo(iter); +} + +// { dg-final { scan-tree-dump-not "can not prove finiteness of loop" "cddce2" } } diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c b/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c index 682166f..2206d05 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c @@ -53,10 +53,11 @@ oof () } void -lookharder (string) +lookharder (string, res) char *string; + char *res; { - register char *g; + register char *g = res; register char *s; for (s = string; *s != '\0'; s++) { diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 6efe67a..7c1ac61 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -3422,7 +3422,7 @@ static void infer_loop_bounds_from_pointer_arith (struct loop *loop, gimple *stmt) { tree def, base, step, scev, type, low, high; - tree var, ptr; + tree rhs2, rhs1; if (!is_gimple_assign (stmt) || gimple_assign_rhs_code (stmt) != POINTER_PLUS_EXPR) @@ -3436,12 +3436,13 @@ infer_loop_bounds_from_pointer_arith (struct loop *loop, gimple *stmt) if (!nowrap_type_p (type)) return; - ptr = gimple_assign_rhs1 (stmt); - if (!expr_invariant_in_loop_p (loop, ptr)) + rhs2 = gimple_assign_rhs2 (stmt); + if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (rhs2))) return; - var = gimple_assign_rhs2 (stmt); - if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var))) + rhs1 = gimple_assign_rhs1 (stmt); + if (!expr_invariant_in_loop_p (loop, rhs1) + && !expr_invariant_in_loop_p (loop, rhs2)) return; struct loop *uloop = loop_containing_stmt (stmt); @@ -3521,6 +3522,8 @@ infer_loop_bounds_from_signedness (struct loop *loop, gimple *stmt) allocated size, - signed variables should not overflow when flag_wrapv is not set. + + - pointer variables should not overflow when flag_wrapv is not set. */ static void
Hi, This is a simple patch exploiting more undefined pointer overflow behavior in loop niter analysis. Originally, it only supports POINTER_PLUS_EXPR if the offset part is IV. This patch also handles the case if pointer is IV. With this patch, the while(true) loop in test can be removed by cddce pass now. Bootstrap and test on x86_64 and AArch64. This patch introduces two failures: FAIL: g++.dg/pr79095-1.C -std=gnu++98 (test for excess errors) FAIL: g++.dg/pr79095-2.C -std=gnu++11 (test for excess errors) I believe this exposes inaccurate value range information issue. For below code: /* { dg-do compile } */ /* { dg-options "-Wall -O3" } */ typedef long unsigned int size_t; inline void fill (int *p, size_t n, int) { while (n--) *p++ = 0; } struct B { int* p0, *p1, *p2; size_t size () const { return size_t (p1 - p0); } void resize (size_t n) { if (n > size()) append (n - size()); } void append (size_t n) { if (size_t (p2 - p1) >= n) { fill (p1, n, 0); } } }; void foo (B &b) { if (b.size () != 0) b.resize (b.size () - 1); } GCC gives below warning with this patch: pr79095-1.C: In function ‘void foo(B&)’: pr79095-1.C:10:7: warning: iteration 4611686018427387903 invokes undefined behavior [-Waggressive-loop-optimizations] *p++ = 0; ~^~ pr79095-1.C:9:11: note: within this loop while (n--) ^~ Problem is VRP should understand that it's never the case with condition: (size_t (p2 - p1) >= n) in function B::append. So, any comment? Thanks, bin 2017-11-02 Bin Cheng <bin.cheng@arm.com> PR tree-optimization/82776 * tree-ssa-loop-niter.c (infer_loop_bounds_from_pointer_arith): Handle POINTER_PLUS_EXPR in which the pointer is an IV. (infer_loop_bounds_from_signedness): Refine comment. gcc/testsuite 2017-11-02 Bin Cheng <bin.cheng@arm.com> PR tree-optimization/82776 * g++.dg/pr82776.C: New test. * gcc.dg/tree-ssa/split-path-6.c: Refine test.