Created attachment 48319 [details] test case Tested with gcc 9.1 9.2 and 9.3 on godbolt. Compiling with "-O2 -Warray-bounds" gives the following false positive : --- <source>: In function 'f': <source>:38:11: warning: array subscript 7 is outside array bounds of 'byte[1]' {aka 'unsigned char[1]'} [-Warray-bounds] 38 | ps->s += len; | ^~ <source>:46:6: note: while referencing 'c' 46 | byte c; | ^ Compiler returned: 0 --- Error also with -O3 but not with -O. Note that the error goes after removing the assert.
The false positive is not due a shortcoming of the warning but rather due to GCC not having a sufficiently sophisticated analysis of relationships of pointers into the same objects. The same warning (and probably a numbers as well) can be reproduced with a simpler example. $ cat pr94675.c && gcc -O2 -S -Wall -fdump-tree-vrp=/dev/stdout pr94675.c unsigned char c, n; int f (void) { if (n <= 7) return 0; unsigned char *p = &c, *q = p + n; if (q - p <= 7) // not eliminated return 0; return p[7]; // spurious -Warray-bounds } ;; Function f (f, funcdef_no=0, decl_uid=1932, cgraph_uid=1, symbol_order=2) ;; 1 loops found ;; ;; Loop 0 ;; header 0, latch 1 ;; depth 0, outer -1 ;; nodes: 0 1 2 3 4 ;; 2 succs { 4 3 } ;; 3 succs { 4 } ;; 4 succs { 1 } Value ranges after VRP: n.0_1: unsigned char VARYING _2: unsigned char VARYING _3: int [0, 255] _5: int [0, 255] pr94675.c: In function ‘f’: pr94675.c:12:11: warning: array subscript 7 is outside array bounds of ‘unsigned char[1]’ [-Warray-bounds] 12 | return p[7]; | ~^~~ pr94675.c:1:15: note: while referencing ‘c’ 1 | unsigned char c, n; | ^ f () { unsigned char n.0_1; unsigned char _2; int _3; int _5; <bb 2> [local count: 1073741824]: n.0_1 = n; if (n.0_1 <= 7) goto <bb 4>; [34.00%] else goto <bb 3>; [66.00%] <bb 3> [local count: 708669601]: _2 = MEM[(unsigned char *)&c + 7B]; _5 = (int) _2; <bb 4> [local count: 1073741824]: # _3 = PHI <0(2), _5(3)> return _3; } ;; Function f (f, funcdef_no=0, decl_uid=1932, cgraph_uid=1, symbol_order=2) ;; 1 loops found ;; ;; Loop 0 ;; header 0, latch 1 ;; depth 0, outer -1 ;; nodes: 0 1 2 3 4 ;; 2 succs { 4 3 } ;; 3 succs { 4 } ;; 4 succs { 1 } Value ranges after VRP: n.0_1: unsigned char VARYING _2: unsigned char VARYING _3: int [0, 255] _5: int [0, 255] f () { unsigned char n.0_1; unsigned char _2; int _3; int _5; <bb 2> [local count: 1073741824]: n.0_1 = n; if (n.0_1 <= 7) goto <bb 4>; [34.00%] else goto <bb 3>; [66.00%] <bb 3> [local count: 708669601]: _2 = MEM[(unsigned char *)&c + 7B]; _5 = (int) _2; <bb 4> [local count: 1073741824]: # _3 = PHI <_5(3), 0(2)> return _3; }
Note that in our code, we are not even dereferencing the pointer, it's just ps->s += len. And since we always keep a pointer right after the array (p_end / s_end), won't that be a source of problems for Warray-bounds ?
(In reply to Martin Sebor from comment #1) > The false positive is not due a shortcoming of the warning but rather due to > GCC not having a sufficiently sophisticated analysis of relationships of > pointers into the same objects. The same warning (and probably a numbers as > well) can be reproduced with a simpler example. > > $ cat pr94675.c && gcc -O2 -S -Wall -fdump-tree-vrp=/dev/stdout pr94675.c > unsigned char c, n; > > int f (void) > { > if (n <= 7) return 0; > > unsigned char *p = &c, *q = p + n; > > if (q - p <= 7) // not eliminated > return 0; Not sure why you write not eliminated - it is eliminated. I believe your testcase is bogus - why would the p[7] access never happen? Because p + n is invoking undefined behavior? > return p[7]; // spurious -Warray-bounds > } > > ;; Function f (f, funcdef_no=0, decl_uid=1932, cgraph_uid=1, symbol_order=2) > > ;; 1 loops found > ;; > ;; Loop 0 > ;; header 0, latch 1 > ;; depth 0, outer -1 > ;; nodes: 0 1 2 3 4 > ;; 2 succs { 4 3 } > ;; 3 succs { 4 } > ;; 4 succs { 1 } > > Value ranges after VRP: > > n.0_1: unsigned char VARYING > _2: unsigned char VARYING > _3: int [0, 255] > _5: int [0, 255] > > > pr94675.c: In function ‘f’: > pr94675.c:12:11: warning: array subscript 7 is outside array bounds of > ‘unsigned char[1]’ [-Warray-bounds] > 12 | return p[7]; > | ~^~~ > pr94675.c:1:15: note: while referencing ‘c’ > 1 | unsigned char c, n; > | ^ > f () > { > unsigned char n.0_1; > unsigned char _2; > int _3; > int _5; > > <bb 2> [local count: 1073741824]: > n.0_1 = n; > if (n.0_1 <= 7) > goto <bb 4>; [34.00%] > else > goto <bb 3>; [66.00%] > > <bb 3> [local count: 708669601]: > _2 = MEM[(unsigned char *)&c + 7B]; > _5 = (int) _2; > > <bb 4> [local count: 1073741824]: > # _3 = PHI <0(2), _5(3)> > return _3; > > } > > > > ;; Function f (f, funcdef_no=0, decl_uid=1932, cgraph_uid=1, symbol_order=2) > > ;; 1 loops found > ;; > ;; Loop 0 > ;; header 0, latch 1 > ;; depth 0, outer -1 > ;; nodes: 0 1 2 3 4 > ;; 2 succs { 4 3 } > ;; 3 succs { 4 } > ;; 4 succs { 1 } > > Value ranges after VRP: > > n.0_1: unsigned char VARYING > _2: unsigned char VARYING > _3: int [0, 255] > _5: int [0, 255] > > > f () > { > unsigned char n.0_1; > unsigned char _2; > int _3; > int _5; > > <bb 2> [local count: 1073741824]: > n.0_1 = n; > if (n.0_1 <= 7) > goto <bb 4>; [34.00%] > else > goto <bb 3>; [66.00%] > > <bb 3> [local count: 708669601]: > _2 = MEM[(unsigned char *)&c + 7B]; > _5 = (int) _2; > > <bb 4> [local count: 1073741824]: > # _3 = PHI <_5(3), 0(2)> > return _3; > > }
In the original testcase I clearly see some missed optimizations, notably the failure to "thread" if (_12 > 6) goto <bb 4>; [50.00%] else goto <bb 3>; [50.00%] <bb 3> [local count: 536870913]: <bb 4> [local count: 1073741824]: # iftmp.2_13 = PHI <0(3), 1(2)> _14 = (_Bool) iftmp.2_13; if (_14 != 0) goto <bb 5>; [90.00%] else goto <bb 6>; [10.00%] and as you say simplification of a pointer comparison _6 = &c + _2; _11 = _6 - &c; _12 = (long unsigned int) _11; if (_12 > 6) we're doing the simplification only late because forwprop depends on FRE and FRE doesn't apply match.pd rules unrestricted like forwprop does. Not doing any DCE before VRP probably doesn't help either (DCE would have removed the offending statement).
(In reply to Martin Sebor from comment #1) > unsigned char c, n; > > int f (void) > { > if (n <= 7) return 0; > > unsigned char *p = &c, *q = p + n; This testcase has UB whenever n > 7 and due to that UB the test actually is eliminated in evrp.
Started with r9-1948-gd893b683f40884cd00b5beb392566ecc7b67f721 on the original testcase.
Backwards jump threading (where we'd like to handle this) doesn't handle the cast assignment (and assignments in general). I've hesitated adding this capability because it'll duplicate a lot of the work done by Ranger. So the threadable path is left in the IL when VRP1 runs, thus generating the false positive. I'd really like to see those warnings move out of VRP, or at least deferred until VRP2 where the dead paths have been cleaned up.
On Tue, 21 Apr 2020, law at redhat dot com wrote: > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=94675 > > Jeffrey A. Law <law at redhat dot com> changed: > > What |Removed |Added > ---------------------------------------------------------------------------- > CC| |law at redhat dot com > > --- Comment #7 from Jeffrey A. Law <law at redhat dot com> --- > Backwards jump threading (where we'd like to handle this) doesn't handle the > cast assignment (and assignments in general). I've hesitated adding this > capability because it'll duplicate a lot of the work done by Ranger. > > So the threadable path is left in the IL when VRP1 runs, thus generating the > false positive. I'd really like to see those warnings move out of VRP, or at > least deferred until VRP2 where the dead paths have been cleaned up. We've moved the warning to VRP1 only because at VRP2 time all the loop opts have been run and esp. unrolling is prone to "thread" unreachable cases.
Yea, unrolling and the array-bounds warning do have bad interactions. I suspect if we cleaned up this block that the backwards threader would likely kick in: # iftmp.2_18 = PHI <1(3), 1(4), 0(5)> _19 = (_Bool) iftmp.2_18; _2 = ~_19; _3 = (long int) _2; _4 = __builtin_expect (_3, 0); if (_4 == 0) goto <bb 7>; [INV] else goto <bb 8>; [INV] I'll play with that and see if there's something we can do cleanly early enough to matter.
On Tue, 21 Apr 2020, law at redhat dot com wrote: > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=94675 > > --- Comment #9 from Jeffrey A. Law <law at redhat dot com> --- > Yea, unrolling and the array-bounds warning do have bad interactions. Note I agree they don't belong in the SSA based VRP pass. Driving them from the DOM-based early VRP range analysis engine would be better. I still would like to see the SSA propagator VRP pass to go away (its jump threading is another blocker there).
(In reply to Richard Biener from comment #3) > (In reply to Martin Sebor from comment #1) > > The false positive is not due a shortcoming of the warning but rather due to > > GCC not having a sufficiently sophisticated analysis of relationships of > > pointers into the same objects. The same warning (and probably a numbers as > > well) can be reproduced with a simpler example. > > > > $ cat pr94675.c && gcc -O2 -S -Wall -fdump-tree-vrp=/dev/stdout pr94675.c > > unsigned char c, n; > > > > int f (void) > > { > > if (n <= 7) return 0; > > > > unsigned char *p = &c, *q = p + n; > > > > if (q - p <= 7) // not eliminated > > return 0; > > Not sure why you write not eliminated - it is eliminated. I believe > your testcase is bogus - why would the p[7] access never happen? > Because p + n is invoking undefined behavior? I may not have entirely accurately describe what happens in the small test case but yes, p + n is undefined for values of n > 1, so the test (either of them) can be assumed to be true and the dereference can be eliminated. The following might be better: unsigned char c, n; int f (void) { unsigned char *p = &c, *q = p + n; if (q - p <= 7) // not eliminated but could be return 0; return p[7]; // spurious -Warray-bounds }
SO it's not terrible to get the key block cleaned up. but that's not sufficient to resolve this issue. We all missed an important tidbit. VRP is complaining about this: ps.D.2041.s = &MEM <byte> [(void *)&c + 7B]; Note the object we reference in the &MEM expression, "c". "c" is a byte: typedef unsigned char byte; byte c; One could argue the problem is FRE. Prior to fre3 we had: ;; basic block 9, loop depth 0 ;; pred: 7 _34 = ps.D.2041.s; _35 = _34 + 7; ps.D.2041.s = _35; fre3 turns that into: ps.D.2041.s = &MEM <byte> [(void *)&c + 7B]; And we're going to lose. One could also argue that the warning has to be tolerant of these actions from FRE. The question would be how to do that without totally compromising the warning.
*** Bug 94655 has been marked as a duplicate of this bug. ***
I can think of only one way the warning code could avoid triggering here: by assuming that the difference between two pointers into the same array is less than or equal the size of the array (with non-array objects being viewed as arrays of a single element). That's necessarily true in any valid C/C++ program so it would be a safe assumption to make here as well. Since there is no array subscripting involved here, issuing -Warray-bounds might also be considered inappropriate, and the warning could be made not to trigger. But that would just mask the problem which would come back if __ps_skip attempted to access ps->s[len]. It would also come back if/when GCC started to warn more diligently for forming out-of-bounds pointers (I already submitted one patch to do that and the work I'm doing in the path isolation pass is an opportunity to revisit the feature). So we're back to deriving assumptions about the results of pointer arithmetic based the sizes of pointed-to objects. The warning would need to work quite hard to figure this out in general, so hard that I don't think it would be worth the effort unless it benefited code generation as well, or at least all other warnings like it (-Warray-bounds isn't the only one that can be triggered -- a number of others could be made to). Which was also the point of my comment #1 (and related to Richard's observation in comment #4 about an missed optimization opportunity). That said and codegen improvements aside, I think the submitted test case is sufficiently tricky that I don't see issuing a warning for it as a problem. All flow-based warnings have a non-zero rate of false positives (as do many front-end warnings) and there are mechanisms to avoid them. Compared to some of the other false positives we have, avoiding this one seems like a low priority to me.
On Tue, 21 Apr 2020, law at redhat dot com wrote: > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=94675 > > --- Comment #12 from Jeffrey A. Law <law at redhat dot com> --- > SO it's not terrible to get the key block cleaned up. but that's not > sufficient to resolve this issue. We all missed an important tidbit. > > > VRP is complaining about this: > > ps.D.2041.s = &MEM <byte> [(void *)&c + 7B]; > > > Note the object we reference in the &MEM expression, "c". "c" is a byte: > > typedef unsigned char byte; > byte c; > > > One could argue the problem is FRE. Prior to fre3 we had: > > ;; basic block 9, loop depth 0 > ;; pred: 7 > _34 = ps.D.2041.s; > _35 = _34 + 7; > ps.D.2041.s = _35; > > fre3 turns that into: > > ps.D.2041.s = &MEM <byte> [(void *)&c + 7B]; > > And we're going to lose. > > One could also argue that the warning has to be tolerant of these actions from > FRE. The question would be how to do that without totally compromising the > warning. FRE does an identity transform. That VRP does not warn about POINTER_PLUS_EXPR &c + 7B (I think it would?) may be another issue. That is FRE does _34 = ps.D.2041.s; -> _34 = &c; _35 = _34 + 7; -> _35 = &c + 7; // propagatable form &MEM[&c + 7] ps.D.2041.s = _35; -> ps.D.2041.s = &MEM[&c + 7]; aka nothing wrong.
(In reply to Martin Sebor from comment #14) > That said and codegen improvements aside, I think the submitted test case is > sufficiently tricky that I don't see issuing a warning for it as a problem. > All flow-based warnings have a non-zero rate of false positives (as do many > front-end warnings) and there are mechanisms to avoid them. Compared to > some of the other false positives we have, avoiding this one seems like a > low priority to me. Well is there a workaround ? Or do you suggest using pragma ignore ?
As you observed, the warning disappears if the assert is removed, so that's one workaround. But rather than working around it I would suggest to rewrite the code to avoid the pointer subtraction. Chances are it will not only avoid the warning but help improve the emitted object code. I'm not sure I understand correctly what the test case is meant to do but the example below shows what I'm thinking of. If modifying the code isn't feasible then #pragma GCC diagnostic is the recommended suppression mechanism. typedef unsigned char byte; typedef __PTRDIFF_TYPE__ ptrdiff_t; typedef __SIZE_TYPE__ size_t; typedef struct pstream_t { const byte * p; ptrdiff_t n; } pstream_t; static inline _Bool ps_has (const pstream_t *ps, size_t len) { return (size_t)ps->n >= len; } static inline int __ps_skip (pstream_t * ps, size_t len) { if (!ps_has (ps, len)) __builtin_abort (); ps->p += len; ps->n -= len; return 0; } static inline int ps_skip (pstream_t * ps, size_t len) { return ps_has (ps, len) ? __ps_skip(ps, len) : -1; } byte c; int c_len; void f(void) { pstream_t ps = { &c, c_len }; ps_skip (&ps, 7); }
The lib has been recently opensourced so I can share it : https://github.com/Intersec/lib-common/blob/master/src/core/str-stream.h We have 100-200 usages of p_end/s_end/b_end so even if it's possible to patch them all, I am not a big fan of this solution.
GCC 9.4 is being released, retargeting bugs to GCC 9.5.
So on the trunk we get: c_len.0_1 = c_len; _2 = (long unsigned int) c_len.0_1; _6 = &c + _2; MEM <const void *> [(struct pstream_t *)&ps] = &c; MEM <const void *> [(struct pstream_t *)&ps + 8B] = _6; _17 = (signed long) c_len.0_1; _11 = _17; _12 = (long unsigned int) _11; if (_12 > 6) goto <bb 3>; [50.00%] else goto <bb 4>; [50.00%] <bb 3> [local count: 483183820]: ps.D.4009.s = &MEM <byte> [(void *)&c + 7B]; <bb 4> [local count: 590558005]: Which is correct, I think the original testcase and the testcase in comment #1 and comment #11 are bogus and incorrect. There is always an out of bounds.
The problem still happens with gcc 9.4.0 but it appears to be fixed with gcc 10.
(In reply to Xavier from comment #21) > The problem still happens with gcc 9.4.0 but it appears to be fixed with gcc > 10. I suppose that's with the original full testcase, I still see the diagnostic on the testcase from the description.
GCC 9 branch is being closed
GCC 10.4 is being released, retargeting bugs to GCC 10.5.
Hmm, At VRP, we have: _6 = &c + _2; We know after that statement, _2 should have a range of [0,1] because we know the size of _6 is 1 byte. If we use that information afterwards, VRP should be able to optimize the rest.
GCC 10 branch is being closed.