[PATCH] -Warray-bounds TLC

[PATCH] -Warray-bounds TLC

[Richard Biener]

The following applies the patch produced earlier this year, applying
TLC to array bound warnings and catching a few more cases.

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied.

Richard.

2015-04-16  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/64277
	* tree-vrp.c (check_array_ref): Fix anti-range handling,
	simplify upper bound handling.
	(search_for_addr_array): Simplify.
	(check_array_bounds): Handle ADDR_EXPRs here.
	(check_all_array_refs): Simplify.

	* gcc.dg/Warray-bounds-12.c: New testcase.
	* gcc.dg/Warray-bounds-13.c: Likewise.
	* c-c++-common/ubsan/bounds-4.c: Disable -Warray-bounds.
	* c-c++-common/ubsan/bounds-6.c: Likewise.

Index: gcc/tree-vrp.c
===================================================================
*** gcc/tree-vrp.c.orig	2015-01-27 10:47:58.812933951 +0100
--- gcc/tree-vrp.c	2015-01-27 11:18:02.129291796 +0100
*************** check_array_ref (location_t location, tr
*** 6533,6538 ****
--- 6533,6546 ----
    up_bound_p1 = int_const_binop (PLUS_EXPR, up_bound,
  				 build_int_cst (TREE_TYPE (up_bound), 1));
  
+   /* Empty array.  */
+   if (tree_int_cst_equal (low_bound, up_bound_p1))
+     {
+       warning_at (location, OPT_Warray_bounds,
+ 		  "array subscript is above array bounds");
+       TREE_NO_WARNING (ref) = 1;
+     }
+ 
    if (TREE_CODE (low_sub) == SSA_NAME)
      {
        vr = get_value_range (low_sub);
*************** check_array_ref (location_t location, tr
*** 6546,6554 ****
    if (vr && vr->type == VR_ANTI_RANGE)
      {
        if (TREE_CODE (up_sub) == INTEGER_CST
!           && tree_int_cst_lt (up_bound, up_sub)
            && TREE_CODE (low_sub) == INTEGER_CST
!           && tree_int_cst_lt (low_sub, low_bound))
          {
            warning_at (location, OPT_Warray_bounds,
  		      "array subscript is outside array bounds");
--- 6554,6564 ----
    if (vr && vr->type == VR_ANTI_RANGE)
      {
        if (TREE_CODE (up_sub) == INTEGER_CST
!           && (ignore_off_by_one
! 	      ? tree_int_cst_lt (up_bound, up_sub)
! 	      : tree_int_cst_le (up_bound, up_sub))
            && TREE_CODE (low_sub) == INTEGER_CST
!           && tree_int_cst_le (low_sub, low_bound))
          {
            warning_at (location, OPT_Warray_bounds,
  		      "array subscript is outside array bounds");
*************** check_array_ref (location_t location, tr
*** 6557,6566 ****
      }
    else if (TREE_CODE (up_sub) == INTEGER_CST
  	   && (ignore_off_by_one
! 	       ? (tree_int_cst_lt (up_bound, up_sub)
! 		  && !tree_int_cst_equal (up_bound_p1, up_sub))
! 	       : (tree_int_cst_lt (up_bound, up_sub)
! 		  || tree_int_cst_equal (up_bound_p1, up_sub))))
      {
        if (dump_file && (dump_flags & TDF_DETAILS))
  	{
--- 6567,6574 ----
      }
    else if (TREE_CODE (up_sub) == INTEGER_CST
  	   && (ignore_off_by_one
! 	       ? !tree_int_cst_le (up_sub, up_bound_p1)
! 	       : !tree_int_cst_le (up_sub, up_bound)))
      {
        if (dump_file && (dump_flags & TDF_DETAILS))
  	{
*************** check_array_ref (location_t location, tr
*** 6593,6617 ****
  static void
  search_for_addr_array (tree t, location_t location)
  {
-   while (TREE_CODE (t) == SSA_NAME)
-     {
-       gimple g = SSA_NAME_DEF_STMT (t);
- 
-       if (gimple_code (g) != GIMPLE_ASSIGN)
- 	return;
- 
-       if (get_gimple_rhs_class (gimple_assign_rhs_code (g))
- 	  != GIMPLE_SINGLE_RHS)
- 	return;
- 
-       t = gimple_assign_rhs1 (g);
-     }
- 
- 
-   /* We are only interested in addresses of ARRAY_REF's.  */
-   if (TREE_CODE (t) != ADDR_EXPR)
-     return;
- 
    /* Check each ARRAY_REFs in the reference chain. */
    do
      {
--- 6601,6606 ----
*************** check_array_bounds (tree *tp, int *walk_
*** 6701,6712 ****
    if (TREE_CODE (t) == ARRAY_REF)
      check_array_ref (location, t, false /*ignore_off_by_one*/);
  
!   if (TREE_CODE (t) == MEM_REF
!       || (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0)))
!     search_for_addr_array (TREE_OPERAND (t, 0), location);
! 
!   if (TREE_CODE (t) == ADDR_EXPR)
!     *walk_subtree = FALSE;
  
    return NULL_TREE;
  }
--- 6690,6700 ----
    if (TREE_CODE (t) == ARRAY_REF)
      check_array_ref (location, t, false /*ignore_off_by_one*/);
  
!   else if (TREE_CODE (t) == ADDR_EXPR)
!     {
!       search_for_addr_array (t, location);
!       *walk_subtree = FALSE;
!     }
  
    return NULL_TREE;
  }
*************** check_all_array_refs (void)
*** 6736,6764 ****
  	{
  	  gimple stmt = gsi_stmt (si);
  	  struct walk_stmt_info wi;
! 	  if (!gimple_has_location (stmt))
  	    continue;
  
! 	  if (is_gimple_call (stmt))
! 	    {
! 	      size_t i;
! 	      size_t n = gimple_call_num_args (stmt);
! 	      for (i = 0; i < n; i++)
! 		{
! 		  tree arg = gimple_call_arg (stmt, i);
! 		  search_for_addr_array (arg, gimple_location (stmt));
! 		}
! 	    }
! 	  else
! 	    {
! 	      memset (&wi, 0, sizeof (wi));
! 	      wi.info = CONST_CAST (void *, (const void *)
! 				    gimple_location_ptr (stmt));
! 
! 	      walk_gimple_op (gsi_stmt (si),
! 			      check_array_bounds,
! 			      &wi);
! 	    }
  	}
      }
  }
--- 6724,6740 ----
  	{
  	  gimple stmt = gsi_stmt (si);
  	  struct walk_stmt_info wi;
! 	  if (!gimple_has_location (stmt)
! 	      || is_gimple_debug (stmt))
  	    continue;
  
! 	  memset (&wi, 0, sizeof (wi));
! 	  wi.info = CONST_CAST (void *, (const void *)
! 				gimple_location_ptr (stmt));
! 
! 	  walk_gimple_op (gsi_stmt (si),
! 			  check_array_bounds,
! 			  &wi);
  	}
      }
  }
Index: gcc/testsuite/gcc.dg/Warray-bounds-12.c
===================================================================
*** gcc/testsuite/gcc.dg/Warray-bounds-12.c.orig	2015-01-27 10:47:58.813933937 +0100
--- gcc/testsuite/gcc.dg/Warray-bounds-12.c	2015-01-27 10:53:02.737370976 +0100
***************
*** 1,4 ****
--- 1,32 ----
  /* { dg-do compile } */
+ /* { dg-options "-O2 -Warray-bounds" } */
+ 
+ int a[10];
+ int foo1 (int i)
+ {
+   if (i < 0 || i > 9)
+     return a[i];  /* { dg-warning "outside array bounds" } */
+   return 0;
+ }
+ int foo2 (int i)
+ {
+   if (i < 0 || i > 8)
+     return a[i];  /* { dg-bogus "outside array bounds" } */
+   return 0;
+ }
+ int *foo3 (int i)
+ {
+   if (i < 0 || i > 10)
+     return &a[i];  /* { dg-warning "outside array bounds" } */
+   return (void *)0;
+ }
+ int *foo4 (int i)
+ {
+   if (i < 0 || i > 9)
+     return &a[i];  /* { dg-bogus "outside array bounds" } */
+   return (void *)0;
+ }
+ /* { dg-do compile } */
  /* { dg-options "-O3 -Warray-bounds" } */
  /* { dg-additional-options "-mssse3" { target x86_64-*-* i?86-*-* } } */
  
Index: gcc/testsuite/gcc.dg/Warray-bounds-13.c
===================================================================
*** gcc/testsuite/gcc.dg/Warray-bounds-13.c.orig	2015-01-27 10:47:58.814933926 +0100
--- gcc/testsuite/gcc.dg/Warray-bounds-13.c	2015-01-27 10:53:02.738370988 +0100
***************
*** 1,4 ****
--- 1,24 ----
  /* { dg-do compile } */
+ /* { dg-options "-O2 -Warray-bounds" } */
+ 
+ int a[10];
+ int *foo1 (int i)
+ {
+   return &a[10]; /* { dg-bogus "above array bounds" } */
+ }
+ int *foo2 (int i)
+ {
+   return &a[11]; /* { dg-warning "above array bounds" } */
+ }
+ int foo3 (int i)
+ {
+   return a[9]; /* { dg-bogus "above array bounds" } */
+ }
+ int foo4 (int i)
+ {
+   return a[10]; /* { dg-warning "above array bounds" } */
+ }
+ /* { dg-do compile } */
  /* { dg-options "-O3 -Warray-bounds" } */
  
  extern char *bar[17];
Index: gcc/testsuite/c-c++-common/ubsan/bounds-4.c
===================================================================
--- gcc/testsuite/c-c++-common/ubsan/bounds-4.c	(revision 222140)
+++ gcc/testsuite/c-c++-common/ubsan/bounds-4.c	(working copy)
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-fsanitize=bounds -Wall -Wextra -Wno-unused" } */
+/* { dg-options "-fsanitize=bounds -Wall -Wextra -Wno-array-bounds -Wno-unused" } */
 
 /* Initializers of TREE_STATICs aren't instrumented.
    But don't ICE on 'em.  */
@@ -11,7 +11,7 @@ int *gpi;
 int
 main (void)
 {
-  gpi = &A[4];
+  gpi = &A[4]; /* This will warn with -Warray-bounds, but only if VRP runs.  */
   static int *pi = &A[4];
   return 0;
 }
Index: gcc/testsuite/c-c++-common/ubsan/bounds-6.c
===================================================================
--- gcc/testsuite/c-c++-common/ubsan/bounds-6.c	(revision 222140)
+++ gcc/testsuite/c-c++-common/ubsan/bounds-6.c	(working copy)
@@ -1,5 +1,5 @@
 /* { dg-do run } */
-/* { dg-options "-fsanitize=bounds -Wall -Wextra" } */
+/* { dg-options "-fsanitize=bounds -Wall -Wextra -Wno-array-bounds" } */
 
 /* Test off-by-one.  */
 
@@ -24,7 +24,7 @@ main (void)
   a = &u[4].a[10]; // Error
   a = &u[3].a[9]; // OK
   a = &u[3].a[10]; // OK
-  a = &u[3].a[11]; // Error
+  a = &u[3].a[11]; // Error, warns with -Warray-bounds, but only if VRP runs
 
   return 0;
 }

Re: [PATCH] -Warray-bounds TLC

[Steve Ellcey]

On Thu, 2015-04-16 at 13:55 +0200, Richard Biener wrote:
> The following applies the patch produced earlier this year, applying
> TLC to array bound warnings and catching a few more cases.
> 
> Bootstrapped and tested on x86_64-unknown-linux-gnu, applied.
> 
> Richard.
> 
> 2015-04-16  Richard Biener  <rguenther@suse.de>
> 
> 	PR tree-optimization/64277
> 	* tree-vrp.c (check_array_ref): Fix anti-range handling,
> 	simplify upper bound handling.
> 	(search_for_addr_array): Simplify.
> 	(check_array_bounds): Handle ADDR_EXPRs here.
> 	(check_all_array_refs): Simplify.

This caused an interesting build failure of glibc when using the latest
GCC.  Here is a cut down case from elf/dl-open.c:

	extern void foo(void);
	struct s { int n; } v[1];
	int bar (int i)
	{
  		if ((i != 0 && i != -1 && i != -2) && (v[i].n == 0))
    			foo ();
  		return 0;
	}
	int baz (int i)
	{
  		if ((i != 0 && i != -2) && (v[i].n == 0))
    			foo ();
  		return 0;
	}

When compiled with -O2 -Wall -Werror, I now get an error about v[i]
being out-of-bounds in bar.  But I do not get this error in baz (where
we don't check for -1.  In reality, in glibc, we know that i can only be
0, -1, or -2.  GCC of course doesn't know that.  Does this error/warning
seem right?  The difference in behavior between bar and baz seems odd.

Steve Ellcey
sellcey@imgtec.com

Re: [PATCH] -Warray-bounds TLC

[Richard Biener]

On April 17, 2015 8:01:42 PM GMT+02:00, Steve Ellcey <sellcey@imgtec.com> wrote:
>On Thu, 2015-04-16 at 13:55 +0200, Richard Biener wrote:
>> The following applies the patch produced earlier this year, applying
>> TLC to array bound warnings and catching a few more cases.
>> 
>> Bootstrapped and tested on x86_64-unknown-linux-gnu, applied.
>> 
>> Richard.
>> 
>> 2015-04-16  Richard Biener  <rguenther@suse.de>
>> 
>> 	PR tree-optimization/64277
>> 	* tree-vrp.c (check_array_ref): Fix anti-range handling,
>> 	simplify upper bound handling.
>> 	(search_for_addr_array): Simplify.
>> 	(check_array_bounds): Handle ADDR_EXPRs here.
>> 	(check_all_array_refs): Simplify.
>
>This caused an interesting build failure of glibc when using the latest
>GCC.  Here is a cut down case from elf/dl-open.c:
>
>	extern void foo(void);
>	struct s { int n; } v[1];
>	int bar (int i)
>	{
>  		if ((i != 0 && i != -1 && i != -2) && (v[i].n == 0))
>    			foo ();
>  		return 0;
>	}
>	int baz (int i)
>	{
>  		if ((i != 0 && i != -2) && (v[i].n == 0))
>    			foo ();
>  		return 0;
>	}
>
>When compiled with -O2 -Wall -Werror, I now get an error about v[i]
>being out-of-bounds in bar.  But I do not get this error in baz (where
>we don't check for -1.  In reality, in glibc, we know that i can only
>be
>0, -1, or -2.  GCC of course doesn't know that.  Does this
>error/warning
>seem right? 

Yes.  Once you reach the array reference it will be out of bounds.

 The difference in behavior between bar and baz seems odd.
>

Yeah, I suppose VRP gets conservative in a way that's not helpful for consistency of this warning.  ~[0,0] and ~[-2,-2] likely meet as VARYING and the warning code doesn't look at equivalences.

Richard.

>Steve Ellcey
>sellcey@imgtec.com

Re: [PATCH] -Warray-bounds TLC

[Marc Glisse]

On Fri, 17 Apr 2015, Richard Biener wrote:

>> The difference in behavior between bar and baz seems odd.
>
> Yeah, I suppose VRP gets conservative in a way that's not helpful for 
> consistency of this warning.  ~[0,0] and ~[-2,-2] likely meet as VARYING 
> and the warning code doesn't look at equivalences.

Visiting statement:
i_10 = ASSERT_EXPR <i_9, i_9 != -2>;
Intersecting
   ~[-2, -2]  EQUIVALENCES: { i_2(D) i_9 } (2 elements)
and
   ~[0, 0]  EQUIVALENCES: { i_2(D) } (1 elements)
to
   ~[-2, -2]  EQUIVALENCES: { i_2(D) i_9 } (2 elements)
Found new range for i_10: ~[-2, -2]

It has to pick one of the 2 anti-ranges, which one it picks is pretty 
arbitrary. It probably warns if you swap the tests for 0 and -2.

-- 
Marc Glisse

Re: [PATCH] -Warray-bounds TLC

[Steve Ellcey]

On Fri, 2015-04-17 at 21:08 +0200, Marc Glisse wrote:
> On Fri, 17 Apr 2015, Richard Biener wrote:
> 
> >> The difference in behavior between bar and baz seems odd.
> >
> > Yeah, I suppose VRP gets conservative in a way that's not helpful for 
> > consistency of this warning.  ~[0,0] and ~[-2,-2] likely meet as VARYING 
> > and the warning code doesn't look at equivalences.
> 
> Visiting statement:
> i_10 = ASSERT_EXPR <i_9, i_9 != -2>;
> Intersecting
>    ~[-2, -2]  EQUIVALENCES: { i_2(D) i_9 } (2 elements)
> and
>    ~[0, 0]  EQUIVALENCES: { i_2(D) } (1 elements)
> to
>    ~[-2, -2]  EQUIVALENCES: { i_2(D) i_9 } (2 elements)
> Found new range for i_10: ~[-2, -2]
> 
> It has to pick one of the 2 anti-ranges, which one it picks is pretty 
> arbitrary. It probably warns if you swap the tests for 0 and -2.

You are right, If I swap the tests then I do get the warning.

Steve Ellcey
sellcey@imgtec.com

Re: [PATCH] -Warray-bounds TLC

[Steve Ellcey]

As a follow-up, I got the same error with dl-close.c from glibc and
assumed it was the same type of code but when I looked at it and cut it
down I got this code and error.  This seems more like a real GCC error
(in that it should not be warning).  Note that I only get the error when
bad is declared as 'noreturn'.

Steve Ellcey
sellcey@imgtec.com



extern void bad (const char *__assertion)  __attribute__ ((__noreturn__));
struct link_map { long int l_ns; };
extern struct link_namespaces
  {
    unsigned int _ns_nloaded;
  } _dl_ns[1];
void _dl_close_worker (struct link_map *map)
{
  long int nsid = map->l_ns;
  struct link_namespaces *ns = &_dl_ns[nsid];
  (nsid != 0) ? (void) (0) : bad ("nsid != 0");
  --ns->_ns_nloaded;
}



% inst*/bin/*-gcc -O2 -Wall -Werror x.c
x.c: In function '_dl_close_worker':
x.c:10:39: error: array subscript is outside array bounds [-Werror=array-bounds]
   struct link_namespaces *ns = &_dl_ns[nsid];
                                       ^
x.c:10:39: error: array subscript is outside array bounds [-Werror=array-bounds]
cc1: all warnings being treated as errors

Re: [PATCH] -Warray-bounds TLC

[Mike Stump]

On Apr 17, 2015, at 1:52 PM, Steve Ellcey <sellcey@imgtec.com> wrote:
>  struct link_namespaces *ns = &_dl_ns[nsid];
>  (nsid != 0) ? (void) (0) : bad ("nsid != 0”);

Without disagreeing with the fact this looks like a bug, ideally, the two lines above would be switched:

c++98:
  If both the pointer operand and the result point to  elements
  of  the  same  array object, or one past the last element of the array
  object, the evaluation shall not produce an overflow;  otherwise,  the
  behavior is undefined.

and c99 tc3:
8   When an expression that has integer type is added to or subtracted from a pointer, the
    result has the type of the pointer operand. If the pointer operand points to an element of
    an array object, and the array is large enough, the result points to an element offset from
    the original element such that the difference of the subscripts of the resulting and original
    array elements equals the integer expression. In other words, if the expression P points to
    the i-th element of an array object, the expressions (P)+N (equivalently, N+(P)) and
    (P)-N (where N has the value n) point to, respectively, the i+n-th and i-n-th elements of
    the array object, provided they exist. Moreover, if the expression P points to the last
    element of an array object, the expression (P)+1 points one past the last element of the
    array object, and if the expression Q points one past the last element of an array object,
    the expression (Q)-1 points to the last element of the array object. If both the pointer
    operand and the result point to elements of the same array object, or one past the last
    element of the array object, the evaluation shall not produce an overflow; otherwise, the
    behavior is undefined.

Re: [PATCH] -Warray-bounds TLC

[Marc Glisse]

On Fri, 17 Apr 2015, Steve Ellcey wrote:

> As a follow-up, I got the same error with dl-close.c from glibc and
> assumed it was the same type of code but when I looked at it and cut it
> down I got this code and error.  This seems more like a real GCC error
> (in that it should not be warning).  Note that I only get the error when
> bad is declared as 'noreturn'.
>
> Steve Ellcey
> sellcey@imgtec.com
>
>
>
> extern void bad (const char *__assertion)  __attribute__ ((__noreturn__));
> struct link_map { long int l_ns; };
> extern struct link_namespaces
>  {
>    unsigned int _ns_nloaded;
>  } _dl_ns[1];
> void _dl_close_worker (struct link_map *map)
> {
>  long int nsid = map->l_ns;
>  struct link_namespaces *ns = &_dl_ns[nsid];
>  (nsid != 0) ? (void) (0) : bad ("nsid != 0");
>  --ns->_ns_nloaded;
> }

It looks close enough to me. The actual access to _dl_ns[nsid] only ever 
happens for an index that is out of range. The last line of the function 
can never make sense (unreachable or undefined behavior), it is good that 
the compiler tells you about it.

-- 
Marc Glisse

Re: [PATCH] -Warray-bounds TLC

[Steve Ellcey]

On Sat, 2015-04-18 at 00:15 +0200, Marc Glisse wrote:
> >
> > extern void bad (const char *__assertion)  __attribute__ ((__noreturn__));
> > struct link_map { long int l_ns; };
> > extern struct link_namespaces
> >  {
> >    unsigned int _ns_nloaded;
> >  } _dl_ns[1];
> > void _dl_close_worker (struct link_map *map)
> > {
> >  long int nsid = map->l_ns;
> >  struct link_namespaces *ns = &_dl_ns[nsid];
> >  (nsid != 0) ? (void) (0) : bad ("nsid != 0");
> >  --ns->_ns_nloaded;
> > }
> 
> It looks close enough to me. The actual access to _dl_ns[nsid] only ever 
> happens for an index that is out of range. The last line of the function 
> can never make sense (unreachable or undefined behavior), it is good that 
> the compiler tells you about it.

I guess, but it left me very confused because the compiler didn't point
me at the last line, it pointed me at the '*ns = &_dl_ns[nsid]' line.
If there was a lot of stuff in between that line, the line with the call
to the noreturn function, and the ns->ns_loaded line (like there is in
the real glibc), it is very hard to understand what the compiler is
trying to tell me when it only points out the first line as where the
error is.

Steve Ellcey

Re: [PATCH] -Warray-bounds TLC

[Richard Biener]

On Fri, 17 Apr 2015, Steve Ellcey wrote:

> On Sat, 2015-04-18 at 00:15 +0200, Marc Glisse wrote:
> > >
> > > extern void bad (const char *__assertion)  __attribute__ ((__noreturn__));
> > > struct link_map { long int l_ns; };
> > > extern struct link_namespaces
> > >  {
> > >    unsigned int _ns_nloaded;
> > >  } _dl_ns[1];
> > > void _dl_close_worker (struct link_map *map)
> > > {
> > >  long int nsid = map->l_ns;
> > >  struct link_namespaces *ns = &_dl_ns[nsid];
> > >  (nsid != 0) ? (void) (0) : bad ("nsid != 0");
> > >  --ns->_ns_nloaded;
> > > }
> > 
> > It looks close enough to me. The actual access to _dl_ns[nsid] only ever 
> > happens for an index that is out of range. The last line of the function 
> > can never make sense (unreachable or undefined behavior), it is good that 
> > the compiler tells you about it.
> 
> I guess, but it left me very confused because the compiler didn't point
> me at the last line, it pointed me at the '*ns = &_dl_ns[nsid]' line.
> If there was a lot of stuff in between that line, the line with the call
> to the noreturn function, and the ns->ns_loaded line (like there is in
> the real glibc), it is very hard to understand what the compiler is
> trying to tell me when it only points out the first line as where the
> error is.

Yeah - we actually warn on both

 _4 = MEM[(struct link_namespaces *)&_dl_ns][nsid_8]._ns_nloaded;

and

 MEM[(struct link_namespaces *)&_dl_ns][nsid_8]._ns_nloaded = _5;

which is also why you get two warnings.  The location of the
ARRAY_REF is that of the original address taking operation.
What eventually misses is the location of the dereference
statement (line 12).

Richard.