Bug 94675 - [10/11/12/13 regression] -Warray-bounds false positive with -O2 since r9-1948
Summary: [10/11/12/13 regression] -Warray-bounds false positive with -O2 since r9-1948
Status: NEW
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 9.3.0
: P2 normal
Target Milestone: 10.5
Assignee: Not yet assigned to anyone
URL:
Keywords: diagnostic, missed-optimization
Depends on:
Blocks: Warray-bounds
  Show dependency treegraph
 
Reported: 2020-04-20 19:42 UTC by Xavier
Modified: 2022-11-18 22:59 UTC (History)
7 users (show)

See Also:
Host:
Target:
Build:
Known to work: 8.4.0
Known to fail: 10.0, 9.3.0
Last reconfirmed: 2020-04-21 00:00:00


Attachments
test case (405 bytes, text/x-csrc)
2020-04-20 19:42 UTC, Xavier
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Xavier 2020-04-20 19:42:11 UTC
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.
Comment 1 Martin Sebor 2020-04-20 22:16:33 UTC
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;

}
Comment 2 Xavier 2020-04-21 06:51:26 UTC
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 ?
Comment 3 Richard Biener 2020-04-21 07:46:20 UTC
(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;
> 
> }
Comment 4 Richard Biener 2020-04-21 07:58:54 UTC
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).
Comment 5 Jakub Jelinek 2020-04-21 07:59:13 UTC
(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.
Comment 6 Jakub Jelinek 2020-04-21 08:06:06 UTC
Started with r9-1948-gd893b683f40884cd00b5beb392566ecc7b67f721 on the original testcase.
Comment 7 Jeffrey A. Law 2020-04-21 14:03:41 UTC
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.
Comment 8 rguenther@suse.de 2020-04-21 14:18:37 UTC
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.
Comment 9 Jeffrey A. Law 2020-04-21 14:43:55 UTC
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.
Comment 10 rguenther@suse.de 2020-04-21 14:57:08 UTC
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).
Comment 11 Martin Sebor 2020-04-21 14:58:03 UTC
(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
}
Comment 12 Jeffrey A. Law 2020-04-21 19:14:38 UTC
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.
Comment 13 Jeffrey A. Law 2020-04-21 20:10:24 UTC
*** Bug 94655 has been marked as a duplicate of this bug. ***
Comment 14 Martin Sebor 2020-04-21 21:00:17 UTC
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.
Comment 15 rguenther@suse.de 2020-04-22 06:34:32 UTC
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.
Comment 16 Xavier 2020-04-24 07:48:51 UTC
(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 ?
Comment 17 Martin Sebor 2020-04-24 15:16:23 UTC
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);
}
Comment 18 Xavier 2020-04-30 13:12:27 UTC
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.
Comment 19 Richard Biener 2021-06-01 08:17:18 UTC
GCC 9.4 is being released, retargeting bugs to GCC 9.5.
Comment 20 Andrew Pinski 2021-09-06 11:25:44 UTC
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.
Comment 21 Xavier 2022-03-16 11:09:16 UTC
The problem still happens with gcc 9.4.0 but it appears to be fixed with gcc 10.
Comment 22 Richard Biener 2022-03-16 13:24:45 UTC
(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.
Comment 23 Richard Biener 2022-05-27 09:42:30 UTC
GCC 9 branch is being closed
Comment 24 Jakub Jelinek 2022-06-28 10:40:18 UTC
GCC 10.4 is being released, retargeting bugs to GCC 10.5.