Bug 8268 - no compile time array index checking
Summary: no compile time array index checking
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: c (show other bugs)
Version: 3.2
: P3 enhancement
Target Milestone: 4.3.0
Assignee: Dirk Mueller
URL:
Keywords: diagnostic
: 22546 24728 (view as bug list)
Depends on:
Blocks:
 
Reported: 2002-10-17 14:26 UTC by d.binderman
Modified: 2007-01-18 13:12 UTC (History)
10 users (show)

See Also:
Host:
Target:
Build:
Known to work: 4.3.0
Known to fail:
Last reconfirmed: 2005-05-27 01:06:18


Attachments
patch (1.28 KB, patch)
2006-02-18 02:51 UTC, Dirk Mueller
Details | Diff
alternative patch (2.27 KB, patch)
2006-02-18 07:19 UTC, Falk Hueffner
Details | Diff
reworked patch (2.33 KB, patch)
2006-02-23 09:59 UTC, Dirk Mueller
Details | Diff
updated patch. (2.53 KB, patch)
2006-02-23 15:47 UTC, Dirk Mueller
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description d.binderman 2002-10-17 14:26:00 UTC
# include <stdlib.h>

// some compilers can find fault with this

// simple case

int a[ 10];

void
f()
{
	a[ -1] = -1;	// bug
	a[ 0] = 0;
	a[ 9] = 9;
	a[ 10] = 10;	// bug
}

// bit more complex

void
g()
{
	int b[ 10];

	const int n = 5;

	b[ 2 * n - 11] = -1;	// bug
	b[ 2 * n - 10] = 0;
	b[ n + 4] = 9;
	b[ n + 5] = 10;		// bug
}

// Can any compiler find fault with this ?

void
h()
{
	int * const c = (int *) malloc( 10 * sizeof( int));

	int n = 5;

	c[ 2 * n - 11] = -1;	// bug
	c[ 2 * n - 10] = 0;
	c[ n + 4] = 9;
	c[ n + 5] = 10;			// bug

	free( c);
}

Release:
gcc 3.2

How-To-Repeat:
I tried to compile the above source code with
gcc 3.2 -g -O2 -Wall. 

It produced no warnings. I count six bugs in the code.
Comment 1 falk.hueffner 2002-10-18 19:22:53 UTC
From: Falk Hueffner <falk.hueffner@student.uni-tuebingen.de>
To: gcc-gnats@gcc.gnu.org
Cc:  
Subject: Re: c/8268: no compile time array index checking
Date: 18 Oct 2002 19:22:53 +0200

 --=-=-=
 
 Hi,
 
 ages ago, I wrote a patch for c-typeck.c that does this. Jeff Law
 suggested to place it in expr.c, so other languages would catch it,
 too. Here's a patch. Does it look like I'm on the right track?
 
 -- 
 	Falk
 
 --=-=-=
 Content-Type: text/x-patch
 Content-Disposition: attachment; filename=array-bounds.patch
 
 Index: expr.c
 ===================================================================
 RCS file: /cvs/gcc/gcc/gcc/expr.c,v
 retrieving revision 1.488
 diff -u -r1.488 expr.c
 --- expr.c	15 Oct 2002 20:09:32 -0000	1.488
 +++ expr.c	18 Oct 2002 15:59:49 -0000
 @@ -5634,6 +5634,19 @@
  	  tree low_bound = (domain ? TYPE_MIN_VALUE (domain) : 0);
  	  tree unit_size = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (array)));
  
 +	  if (domain && TREE_CODE (index) == INTEGER_CST)
 +	    {
 +	      if ((TREE_CODE (low_bound) == INTEGER_CST
 +		   && tree_int_cst_lt(index, low_bound))
 +		  || (TREE_CODE (TYPE_MAX_VALUE (domain)) == INTEGER_CST
 +		      && tree_int_cst_lt (TYPE_MAX_VALUE (domain), index)
 +		      /* Accesses after the end of arrays of size 0 (gcc
 +			 extension) and 1 are likely intentional. */
 +		      && !tree_int_cst_lt (TYPE_MAX_VALUE (domain),
 +					   build_int_2 (2, 0))))
 +		warning ("array subscript out of range");
 +	    }
 +
  	  /* We assume all arrays have sizes that are a multiple of a byte.
  	     First subtract the lower bound, if any, in the type of the
  	     index, then convert to sizetype and multiply by the size of the
 
 --=-=-=--
Comment 2 Wolfgang Bangerth 2003-01-07 18:40:02 UTC
State-Changed-From-To: open->analyzed
State-Changed-Why: Valid request. Falk even has a patch for that, but it
    does not seem to be in.
    
    In fact, the category should not be accepts-illegal, since
    the code is perfectly legal. It just does something
    undefined.
    
    W.
Comment 3 d.binderman 2003-01-26 16:08:53 UTC
From: "David Binderman" <d.binderman@virgin.net>
To: <bangerth@dealii.org>,
	<gcc-prs@gcc.gnu.org>,
	<nobody@gcc.gnu.org>,
	<gcc-gnats@gcc.gnu.org>,
	<gcc-bugs@gcc.gnu.org>
Cc:  
Subject: Re: c/8268: no compile time array index checking
Date: Sun, 26 Jan 2003 16:08:53 -0000

 Hello there,
 
 I tried out the suggested patch, and it seems ok, until I run
 the gcc test suite, where I get problems on test
 
 gcc.c-torture/execute/20010924-1.c
 
 as shown
 
 (gdb) r /tmp/1.i
 Starting program:
 /home/dcb/gnu/gcc321/results.check/lib/gcc-lib/i686-pc-linux-gnu/3.2.1/cc1
 /tmp/1.i
  main
 Program received signal SIGSEGV, Segmentation fault.
 0x080f12d3 in get_inner_reference (exp=0x40271700, pbitsize=0xbffff1ec,
     pbitpos=0xbffff1f0, poffset=0xbffff1f4, pmode=0x0,
 punsignedp=0x40016c60,
     pvolatilep=0xbffff1fc) at ../../src/gcc-3.2.1/gcc/expr.c:5338
 5338                      || (TREE_CODE (TYPE_MAX_VALUE (domain)) ==
 INTEGER_CST(gdb) list
 5333
 5334              if (domain && TREE_CODE (index) == INTEGER_CST)
 5335                {
 5336                  if ((TREE_CODE (low_bound) == INTEGER_CST
 5337                       && tree_int_cst_lt(index, low_bound))
 5338                      || (TREE_CODE (TYPE_MAX_VALUE (domain)) ==
 INTEGER_CST5339                          && tree_int_cst_lt (TYPE_MAX_VALUE
 (domain), index)
 5340                          /* Accesses after the end of arrays of size 0
 (gcc5341                             extension) and 1 are likely
 intentional. */
 5342                          && !tree_int_cst_lt (TYPE_MAX_VALUE (domain),
 (gdb)
 
 
 Further, it seems a good idea if the warning message produced could be
 enhanced to give a clue about the index value and the size of the array.
 
 Something like
 
  warning: array index '10' in array 'fred' of size '5' is not valid.
 
 A possible second enhancement is to make sure that all six bugs in my
 original demonstration case are found. The current version of the patch
 only finds four of the six problems.
 
 The supplied patch does seem to find bugs in the gcc321 source code,
 however.
 
 Regards
 
 dcb
 
 
 ----- Original Message -----
 From: <bangerth@dealii.org>
 To: <d.binderman@virgin.net>; <gcc-bugs@gcc.gnu.org>; <gcc-prs@gcc.gnu.org>;
 <nobody@gcc.gnu.org>
 Sent: Wednesday, January 08, 2003 2:40 AM
 Subject: Re: c/8268: no compile time array index checking
 
 
 > Synopsis: no compile time array index checking
 >
 > State-Changed-From-To: open->analyzed
 > State-Changed-By: bangerth
 > State-Changed-When: Tue Jan  7 18:40:02 2003
 > State-Changed-Why:
 >     Valid request. Falk even has a patch for that, but it
 >     does not seem to be in.
 >
 >     In fact, the category should not be accepts-illegal, since
 >     the code is perfectly legal. It just does something
 >     undefined.
 >
 >     W.
 >
 >
 http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&p
 r=8268
 >
 

Comment 4 Wolfgang Bangerth 2003-01-27 18:45:53 UTC
From: Wolfgang Bangerth <bangerth@ticam.utexas.edu>
To: David Binderman <d.binderman@virgin.net>,
   <falk.hueffner@student.uni-tuebingen.de>
Cc: gcc-gnats@gcc.gnu.org
Subject: Re: c/8268: no compile time array index checking
Date: Mon, 27 Jan 2003 18:45:53 -0600 (CST)

 David,
 thanks for checking this out. This seems like if the patch was going in 
 the right direction. Falk, regarding the abort, can you take a look at it?
 
 Thanks
   W.
 
 
 > I tried out the suggested patch, and it seems ok, until I run
 > the gcc test suite, where I get problems on test
 > 
 > gcc.c-torture/execute/20010924-1.c
 > 
 > as shown
 > 
 > (gdb) r /tmp/1.i
 > Starting program:
 > /home/dcb/gnu/gcc321/results.check/lib/gcc-lib/i686-pc-linux-gnu/3.2.1/cc1
 > /tmp/1.i
 >  main
 > Program received signal SIGSEGV, Segmentation fault.
 > 0x080f12d3 in get_inner_reference (exp=0x40271700, pbitsize=0xbffff1ec,
 >     pbitpos=0xbffff1f0, poffset=0xbffff1f4, pmode=0x0,
 > punsignedp=0x40016c60,
 >     pvolatilep=0xbffff1fc) at ../../src/gcc-3.2.1/gcc/expr.c:5338
 > 5338                      || (TREE_CODE (TYPE_MAX_VALUE (domain)) ==
 > INTEGER_CST(gdb) list
 > 5333
 > 5334              if (domain && TREE_CODE (index) == INTEGER_CST)
 > 5335                {
 > 5336                  if ((TREE_CODE (low_bound) == INTEGER_CST
 > 5337                       && tree_int_cst_lt(index, low_bound))
 > 5338                      || (TREE_CODE (TYPE_MAX_VALUE (domain)) ==
 > INTEGER_CST5339                          && tree_int_cst_lt (TYPE_MAX_VALUE
 > (domain), index)
 > 5340                          /* Accesses after the end of arrays of size 0
 > (gcc5341                             extension) and 1 are likely
 > intentional. */
 > 5342                          && !tree_int_cst_lt (TYPE_MAX_VALUE (domain),
 > (gdb)
 > 
 > 
 > Further, it seems a good idea if the warning message produced could be
 > enhanced to give a clue about the index value and the size of the array.
 > 
 > Something like
 > 
 >  warning: array index '10' in array 'fred' of size '5' is not valid.
 > 
 > A possible second enhancement is to make sure that all six bugs in my
 > original demonstration case are found. The current version of the patch
 > only finds four of the six problems.
 > 
 > The supplied patch does seem to find bugs in the gcc321 source code,
 > however.
 > 
 > Regards
 > 
 > dcb
 > 
 > 
 > ----- Original Message -----
 > From: <bangerth@dealii.org>
 > To: <d.binderman@virgin.net>; <gcc-bugs@gcc.gnu.org>; <gcc-prs@gcc.gnu.org>;
 > <nobody@gcc.gnu.org>
 > Sent: Wednesday, January 08, 2003 2:40 AM
 > Subject: Re: c/8268: no compile time array index checking
 > 
 > 
 > > Synopsis: no compile time array index checking
 > >
 > > State-Changed-From-To: open->analyzed
 > > State-Changed-By: bangerth
 > > State-Changed-When: Tue Jan  7 18:40:02 2003
 > > State-Changed-Why:
 > >     Valid request. Falk even has a patch for that, but it
 > >     does not seem to be in.
 > >
 > >     In fact, the category should not be accepts-illegal, since
 > >     the code is perfectly legal. It just does something
 > >     undefined.
 > >
 > >     W.
 > >
 > >
 > http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&p
 > r=8268
 > >
 > 
 
 -------------------------------------------------------------------------
 Wolfgang Bangerth             email:            bangerth@ticam.utexas.edu
                               www: http://www.ticam.utexas.edu/~bangerth/
Comment 5 David Binderman 2005-06-20 08:10:57 UTC
I fiddled with the supplied patch, and got this

--- expr.c.sav	2005-06-18 14:45:34.000000000 +0100
+++ expr.c	2005-06-19 11:19:02.000000000 +0100
@@ -5537,6 +5537,20 @@
 	  tree low_bound = (domain ? TYPE_MIN_VALUE (domain) : 0);
 	  tree unit_size = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (array)));
 
+          if ((domain != 0) && (TREE_CODE (index) == INTEGER_CST))
+          {
+            if ((TREE_CODE (low_bound) == INTEGER_CST
+                   && tree_int_cst_lt(index, low_bound))
+               || ((TYPE_MAX_VALUE (domain) != 0)
+                   && (TREE_CODE (TYPE_MAX_VALUE (domain)) == INTEGER_CST)
+                   && tree_int_cst_lt (TYPE_MAX_VALUE (domain), index)
+                   /* Accesses after the end of arrays of size 0 (gcc
+                      extension) and 1 are likely intentional. */
+                   && !tree_int_cst_lt (TYPE_MAX_VALUE (domain),
+                                         build_int_2 (2, 0))))
+                warning ("array subscript out of range");
+          }
+
 	  /* We assume all arrays have sizes that are a multiple of a byte.
 	     First subtract the lower bound, if any, in the type of the
 	     index, then convert to sizetype and multiply by the size of the

I tried it out on the gcc34, and it seemed to work fine, finding eight 
bugs in the Linux kernel.

I don't know how to progress this patch to get it into the official sources for
the gcc34 series. Advice sought.

I tried out the patch on gcc400, and it didn't work. More work needed there.
Comment 6 Falk Hueffner 2005-06-20 09:36:09 UTC
(In reply to comment #5)
> I fiddled with the supplied patch, and got this
> 
> --- expr.c.sav	2005-06-18 14:45:34.000000000 +0100
> +++ expr.c	2005-06-19 11:19:02.000000000 +0100
> @@ -5537,6 +5537,20 @@
> [...]
> I tried it out on the gcc34, and it seemed to work fine, finding eight 
> bugs in the Linux kernel.

I think popular opinion has changed now in that expr.c is not the right place
for a warning after all, so it should rather be done in the frontend 
in c-typeck.c as originally proposed. Jeff, do you agree?
(original thread: http://gcc.gnu.org/ml/gcc/2000-07/msg01000.html)
Comment 7 Jeffrey A. Law 2005-06-20 21:22:31 UTC
Subject: Re:  no compile time array index checking

On Mon, 2005-06-20 at 09:36 +0000, falk at debian dot org wrote:
> ------- Additional Comments From falk at debian dot org  2005-06-20 09:36 -------
> (In reply to comment #5)
> > I fiddled with the supplied patch, and got this
> > 
> > --- expr.c.sav	2005-06-18 14:45:34.000000000 +0100
> > +++ expr.c	2005-06-19 11:19:02.000000000 +0100
> > @@ -5537,6 +5537,20 @@
> > [...]
> > I tried it out on the gcc34, and it seemed to work fine, finding eight 
> > bugs in the Linux kernel.
> 
> I think popular opinion has changed now in that expr.c is not the right place
> for a warning after all, so it should rather be done in the frontend 
> in c-typeck.c as originally proposed. Jeff, do you agree?
> (original thread: http://gcc.gnu.org/ml/gcc/2000-07/msg01000.html)
I would not agree at all.  Bounds checking of this sort does not belong
in the front-end.


Jeff

Comment 8 Giovanni Bajo 2005-06-21 00:10:27 UTC
Doesn't -fmudflap handle this?
Comment 9 Jeffrey A. Law 2005-06-21 01:20:19 UTC
Subject: Re:  no compile time array index checking

On Tue, 2005-06-21 at 00:10 +0000, giovannibajo at libero dot it wrote:
> ------- Additional Comments From giovannibajo at libero dot it  2005-06-21 00:10 -------
> Doesn't -fmudflap handle this?
I would expect mudflap to issue a runtime warning.

If we really wanted to tackle this better a compile-time, we'd run a
pass to look at all the ARRAY_REFs for those which have an out-of-range
index.  It wouldn't be terribly hard to stick one in just before we
leave SSA form.

Doing it that way has a number of useful advantages -- we'll see a
lot more ARRAY_REFs rather than pointer arithmetic (due to constant
address propagation as well as ADDR_EXPR propagation).  We'll also
see more constant indices due to const propagation done by CCP,
VRP and DOM.  And (of course) it would "just work" for all the 
languages currently supported by GCC.

I believe Jakub has done some work in this area that might be useful
as a starting point.

jeff


Comment 10 Wolfgang Bangerth 2005-06-21 14:02:23 UTC
Subject: Re:  no compile time array index checking


> Doesn't -fmudflap handle this?

The idea was to get a compile-time error whenever possible.
W.

-------------------------------------------------------------------------
Wolfgang Bangerth              email:            bangerth@ices.utexas.edu
                               www: http://www.ices.utexas.edu/~bangerth/
Comment 11 Andrew Pinski 2005-06-21 14:05:52 UTC
(In reply to comment #10)
> The idea was to get a compile-time error whenever possible.
It has to be a diagnostic/warning as this is just undefined and undefined code still has to compile as 
one of the DR says.
Comment 12 Tom Truscott 2005-06-21 15:55:50 UTC
Since there is mudflap, it is especially important to avoid false positives.

One type occurs in code that never actually executes, e.g. conditional lookup:
   #define LOOKUP(i) (i < XSIZE ? x[i]: 0)
To defend against that, issue the warning only if skip_evaluation is zero.
(For a more general fix, see http://gcc.gnu.org/ml/gcc/2004-10/msg00859.html) 

Another is taking the address one past the last element, e.g.
    int a[10];
    int *aend = &a[10];  // this is perfectly valid, and common
Comment 13 Andrew Pinski 2005-07-18 14:02:47 UTC
*** Bug 22546 has been marked as a duplicate of this bug. ***
Comment 14 Falk Hueffner 2005-08-21 00:05:06 UTC
(In reply to comment #9)

> If we really wanted to tackle this better a compile-time, we'd run a
> pass to look at all the ARRAY_REFs for those which have an out-of-range
> index.  It wouldn't be terribly hard to stick one in just before we
> leave SSA form.

I'll give this a try.
Comment 15 sebastian.pop@cri.ensmp.fr 2005-08-22 12:38:24 UTC
(In reply to comment #14)
> (In reply to comment #9)
> 
> > If we really wanted to tackle this better a compile-time, we'd run a
> > pass to look at all the ARRAY_REFs for those which have an out-of-range
> > index.  It wouldn't be terribly hard to stick one in just before we
> > leave SSA form.
> 
> I'll give this a try.
> 

Have a look at tree-data-ref.c:analyze_array_indexes
The warning can be implemented in this function.

seb
Comment 16 Andrew Pinski 2005-11-08 02:41:04 UTC
*** Bug 24728 has been marked as a duplicate of this bug. ***
Comment 17 Dirk Mueller 2006-02-18 02:51:38 UTC
Created attachment 10869 [details]
patch

I'm currently testing this patch.
Comment 18 Falk Hueffner 2006-02-18 07:19:11 UTC
Created attachment 10870 [details]
alternative patch

Hi,

I've also been working on a patch, although as an SSA pass. It probably catches
more, but there were some weird interactions with inlining yielding messages
in unexpected places. I'll attach my (preliminary) patch, which also contains a test case.
Comment 19 David Binderman 2006-02-18 12:09:05 UTC
(In reply to comment #17)
> Created an attachment (id=10869) [edit]
> patch
> 
> I'm currently testing this patch.

I tried out the suggested patch on gcc version 4.2, snapshot 20060211,
and tried to build the compiler. It said

../../src/gcc-4.2-20060211/libiberty/cp-demangle.c: In function 'd_demangle':
../../src/gcc-4.2-20060211/libiberty/cp-demangle.c:3899: internal compiler error: tree check: expected catch_expr, have try_finally in array_offset_warning, at c-common.c:5893
Please submit a full bug report,
with preprocessed source if appropriate.
See <URL:http://gcc.gnu.org/bugs.html> for instructions.

The source code line causing problems is

    array_offset_warning (&CATCH_BODY (t));

Also, there seems to be some dead code after the break
statement:

+      case EH_FILTER_EXPR:
+	array_offset_warning (&EH_FILTER_FAILURE (t));
+	break;
+	array_offset_warning (&TREE_OPERAND (t, 0));
+	array_offset_warning (&TREE_OPERAND (t, 1));

Possibly a missing case ?
Comment 20 Richard Biener 2006-02-18 12:28:43 UTC
Also make sure not to trip on

typedef struct {
  int len;
  char str[4];
} String;

char foo(String *s)
{
  return s->str[42];
}
Comment 21 Dirk Mueller 2006-02-18 12:39:11 UTC
hmm, thanks. it should have looked like this:

+      case TRY_FINALLY_EXPR:
+      case TRY_CATCH_EXPR:
+        array_offset_warning (&TREE_OPERAND (t, 0));
+        array_offset_warning (&TREE_OPERAND (t, 1));
+        break;
+      case CATCH_EXPR:
+       array_offset_warning (&CATCH_BODY (t));
+       break;

Anyway, I agree that the SSA pass after all const folding has happened is a  much better approach than my quick hack, as long as it isn't significantly slower (compile time). I'm currently trying Falk's patch. 



Comment 22 Dirk Mueller 2006-02-18 12:42:51 UTC
Richard: Under which assumption? because the array size is <= sizeof(int) ?
Why not suppressing the warning by changing the code to: 

 
typedef struct {
  int len;
  char str[0];
} String;

?
Comment 23 Falk Hueffner 2006-02-18 12:58:54 UTC
(In reply to comment #21)
> hmm, thanks. it should have looked like this:
> 
> +      case TRY_FINALLY_EXPR:
> +      case TRY_CATCH_EXPR:
> +        array_offset_warning (&TREE_OPERAND (t, 0));
> +        array_offset_warning (&TREE_OPERAND (t, 1));
> +        break;
> +      case CATCH_EXPR:
> +       array_offset_warning (&CATCH_BODY (t));
> +       break;
> 
> Anyway, I agree that the SSA pass after all const folding has happened is a 
> much better approach than my quick hack, as long as it isn't significantly
> slower (compile time). I'm currently trying Falk's patch. 

The problem it had was with inlining: code like

static inline int f(int a[], int b) {
    return a[b]; // line 2
}

int g(void) {
    int a[2] = {1, 2};
    return f(a, 2); // line 7
}

To really be helpful, the warning should say something like "array access
out of bound in line 2 after inlining in line 7", but I don't know how
to achieve that. The "uninitialized" warning has the same problem by running
so late; it punts and just says "a used uninitialized in g", which seems
kinda lame.

Anyway, the warning is probably still useful if this is not resolved...
Comment 24 Richard Biener 2006-02-18 13:15:50 UTC
(In reply to comment #22)

We need to allow offsetting beyond the declared array size if this array is the
last member of a structure.  This is refered to as "malloc trick" to allocate
variable sized structures with a flexible array member.  Due to compilers lacking
support for the correct char str[] declaration you will find all of
  char str[0]  (GNU extension)
  char str[]
  char str[1]
  char str[4]  (or whatever number)
so in this case we need to allow all accesses, or with a separate warning flag
only warn if the decl was not one of [0], [] or [1].
Comment 25 Falk Hueffner 2006-02-18 13:25:12 UTC
(In reply to comment #24)
> We need to allow offsetting beyond the declared array size if this array is the
> last member of a structure.  This is refered to as "malloc trick" to allocate
> variable sized structures with a flexible array member.  Due to compilers
> lacking
> support for the correct char str[] declaration you will find all of
>   char str[0]  (GNU extension)
>   char str[]
>   char str[1]
>   char str[4]  (or whatever number)
> so in this case we need to allow all accesses, or with a separate warning flag
> only warn if the decl was not one of [0], [] or [1].

I tried to handle this by never warning for any size-0 or size-1 array. Is
there some way to check that this array is in fact the last member of a
struct? That would clearly be better. I'd still consider warning for
sizes >1, because it's probably rare enough to not justify the false negatives
we get otherwise.

Comment 26 Richard Biener 2006-02-18 13:44:22 UTC
I agree that the false positives would be acceptable.  One could even warn for
[0] and [1] arrays if std=c99 (I believe flexible array members were not in c89, but i didn't check).

For a way to check if an array access can possibly cross structure extent you
can look at tree-dfa.c:get_ref_base_and_extent which also accounts for flexible
array members.
Comment 27 David Binderman 2006-02-18 14:33:20 UTC
(In reply to comment #21)
> hmm, thanks. it should have looked like this:

I tried your second patch, and the compile of the compiler got as far
as the following

/home/dcb/gnu/42-20060211/working/./prev-gcc/xgcc -B/home/dcb/gnu/42-20060211/working/./prev-gcc/ -B/home/dcb/gnu/42-20060211/results/x86_64-unknown-linux-gnu/bin/ -c   -g -O2 -DIN_GCC   -W -Wall -Wwrite-strings -Wstrict-prototypes -Wmissing-prototypes -pedantic -Wno-long-long -Wno-variadic-macros -Wno-overlength-strings -Wold-style-definition -Wmissing-format-attribute -Werror -fno-common   -DHAVE_CONFIG_H -I. -I. -I../../src/gcc-4.2-20060211/gcc -I../../src/gcc-4.2-20060211/gcc/. -I../../src/gcc-4.2-20060211/gcc/../include -I../../src/gcc-4.2-20060211/gcc/../libcpp/include  -I../../src/gcc-4.2-20060211/gcc/../libdecnumber -I../libdecnumber    ../../src/gcc-4.2-20060211/gcc/real.c -o real.o../../src/gcc-4.2-20060211/gcc/real.c: In function 'real_to_integer2':
../../src/gcc-4.2-20060211/gcc/real.c:1385: error: array reference -1 below range min (0)
../../src/gcc-4.2-20060211/gcc/real.c: In function 'real_from_integer':
../../src/gcc-4.2-20060211/gcc/real.c:2050: error: array reference -1 below range min (0)
../../src/gcc-4.2-20060211/gcc/real.c: In function 'encode_ieee_quad':
../../src/gcc-4.2-20060211/gcc/real.c:3564: error: array reference 3 above range max (2)
../../src/gcc-4.2-20060211/gcc/real.c:3615: error: array reference 3 above range max (2)
../../src/gcc-4.2-20060211/gcc/real.c: In function 'decode_ieee_quad':
../../src/gcc-4.2-20060211/gcc/real.c:3693: error: array reference 3 above range max (2)
../../src/gcc-4.2-20060211/gcc/real.c:3719: error: array reference 3 above range max (2)
../../src/gcc-4.2-20060211/gcc/real.c:3745: error: array reference 3 above range max (2)

It seems that a combination of the new warning and the Werror flag prevents
compilation.

On the other point about using arrayName[ 4] for the "end of struct" hack,
I'd be entirely happy with false positives. 

Folks who want that hack can just say arrayName[ 1] to avoid the new warning
anyway.
 
Comment 28 Giovanni Bajo 2006-02-18 14:48:28 UTC
Jakub, you have provided some infrastructure to compute object size and provide warnings for unsafe use of builtins. Do you believe that infrastructure could be reused/enhanced for this bug?
Comment 29 Jakub Jelinek 2006-02-18 15:24:58 UTC
Yes, fairly easily.
Just add another pass, probably into tree-object-size.c, where you:
init_object_sizes ();
and for each ARRAY_REF compute objsz = compute_builtin_object_size (TREE_OPERAND (array_ref, 0), 0) and if (objsz != (unsigned HOST_WIDE_INT) -1 &&
compare_tree_int (TREE_OPERAND (array_ref, 1), objsz)) >= 0)
warning (...);
When done with the pass, call fini_object_sizes ();.
Comment 30 Neil Booth 2006-02-19 00:52:21 UTC
Subject: Re:  no compile time array index checking

rguenth at gcc dot gnu dot org wrote:-

> Also make sure not to trip on
> 
> typedef struct {
>   int len;
>   char str[4];
> } String;
> 
> char foo(String *s)
> {
>   return s->str[42];
> }

That definitely deserves a warning.

Neil.
Comment 31 Dirk Mueller 2006-02-19 21:42:31 UTC
I see many false positives and negatives with the -Warray-bounds patch. I haven't closely investigated the false positives yet, but one of the false negatives is this: 

=== Cut ===
struct bla {

  bla();

  int* foo[3];
};


bla::bla()
{
  foo[3] = 0;
}
=== Cut ===

this one is caught by my patch. 

Comment 32 Dirk Mueller 2006-02-23 09:59:08 UTC
Created attachment 10899 [details]
reworked patch

Ok, based on Falk's patch, I've hammered on it long enough until there were no more false positives.
Comment 33 Dirk Mueller 2006-02-23 15:47:32 UTC
Created attachment 10902 [details]
updated patch.

better patch. I'm going to post that one when regtesting completes.
Comment 34 Falk Hueffner 2006-02-23 16:16:26 UTC
(In reply to comment #33)
> Created an attachment (id=10902) [edit]
> updated patch.
> 
> better patch. I'm going to post that one when regtesting completes. 

BTW, have you considered Sebastian's suggestion to put this into 
tree-data-ref.c/analyze_array_indexes?
Comment 35 Richard Biener 2006-02-23 16:18:13 UTC
I suggested to put it in VRP so one can do analysis for non-constant indices.  Possibly by splitting the warning like strict aliasing.
Comment 36 Jeffrey A. Law 2006-02-23 16:31:14 UTC
Subject: Re:  no compile time array index checking

On Thu, 2006-02-23 at 16:18 +0000, rguenth at gcc dot gnu dot org wrote:
> 
> ------- Comment #35 from rguenth at gcc dot gnu dot org  2006-02-23 16:18 -------
> I suggested to put it in VRP so one can do analysis for non-constant indices. 
> Possibly by splitting the warning like strict aliasing.
Using the VRP information for array bound checking purposes has 
always been something we wanted to do.  Though we always thought
the first use would be for eliminating bounds checks rather than
for warning purposes :-)

This will bring to the forefront the need to either make VRP
data persistent or at least mark array references VRP determines
are safe, unsafe or unsure so that a later pass can issue the
appropriate warnings (possibly after further analysis).

Jeff

Comment 37 David Binderman 2006-02-24 17:38:41 UTC
(In reply to comment #33)
> Created an attachment (id=10902) [edit]
> updated patch.
> 
> better patch. I'm going to post that one when regtesting completes. 

I tried your patch on gcc 4.2 current snapshot and I had to 
bodge it a bit to get it to compile.

After that, it segfaulted during bootstrapping ;-<

Comment 38 Dirk Mueller 2006-02-25 18:37:24 UTC
I think the anaylize_array_indexes has the problem of the "taking address of array sentinel" as well. 

I'll look into moving it to VRP pass. 

re segfault: I got the same, will fix. 
Comment 39 Falk Hueffner 2006-06-08 15:02:16 UTC
I'm not actually working on this at the moment
Comment 40 Dirk Mueller 2006-06-08 15:50:10 UTC
I've a patch, which is currently blocked by -fivopts bug
Comment 41 David Binderman 2007-01-16 21:18:58 UTC
(In reply to comment #40)
> I've a patch, which is currently blocked by -fivopts bug

Still blocked ?


Comment 42 Dirk Mueller 2007-01-17 10:51:37 UTC
no, its going in real soon now (finally) :)
Comment 43 Dirk Mueller 2007-01-18 13:00:47 UTC
Subject: Bug 8268

Author: mueller
Date: Thu Jan 18 13:00:33 2007
New Revision: 120898

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=120898
Log:
2007-01-18  Dirk Mueller  <dmueller@suse.de>
·           Richard Guenther <rguenther@suse.de>

·       PR diagnostic/8268
·       * doc/invoke.texi (Warray-bounds): Document -Warray-bounds.
·       * common.opt (Warray-bounds): Add new warning option.
·       * c-opts.c (c_common_handle_option): Define -Warray-bounds
·       if -Wall is given.
        * Makefile.in: make tree-vrp.o depend on toplev.h
·       * tree-vrp.c (vrp_finalize): Call check_array_refs if -Warray-bounds
·       is enabled.
·       (check_array_refs, check_array_bounds, check_array_ref): New.

·       * gcc.dg/Warray-bounds.c: New testcase.
        * gcc.dg/Warray-bounds-2.c: New testcase.
        * g++.dg/warn/Warray-bounds.C: New testcase.
        * g++.dg/warn/Warray-bounds-2.C: New testcase.

Added:
    trunk/gcc/testsuite/g++.dg/warn/Warray-bounds-2.C
    trunk/gcc/testsuite/g++.dg/warn/Warray-bounds.C
    trunk/gcc/testsuite/gcc.dg/Warray-bounds-2.c
    trunk/gcc/testsuite/gcc.dg/Warray-bounds.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/Makefile.in
    trunk/gcc/c-opts.c
    trunk/gcc/common.opt
    trunk/gcc/doc/invoke.texi
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vrp.c

Comment 44 Dirk Mueller 2007-01-18 13:12:46 UTC
Fixed for 4.3. 
Comment 45 Dirk Mueller 2007-01-30 17:17:57 UTC
Subject: Bug 8268

Author: mueller
Date: Tue Jan 30 17:17:39 2007
New Revision: 121346

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=121346
Log:
backport from mainline:

  2007-01-21  Dirk Mueller  <dmueller@suse.de>

        PR bootstrap/30511
        * tree-vrp.c (check_array_bounds): do not warn
        about ADDR_EXPR's of ARRAY_REF's which are immediately
        used in binary expressions.

  2007-01-19  Dirk Mueller  <dmueller@suse.de>

        * config/i386.h (CONDITIONAL_REGISTER_USAGE): Store
        result of PIC_OFFSET_TABLE_REGNUM in temporary variable to avoid
        duplicate evaluation.

  2007-01-18  Dirk Mueller  <dmueller@suse.de>
            Richard Guenther <rguenther@suse.de>

        PR diagnostic/8268
        * doc/invoke.texi (Warray-bounds): Document -Warray-bounds.
        * common.opt (Warray-bounds): Add new warning option.
        * c-opts.c (c_common_handle_option): Define -Warray-bounds
        if -Wall is given.
        * Makefile.in: make tree-vrp.o depend on toplev.h
        * tree-vrp.c (vrp_finalize): Call check_array_refs if
        * -Warray-bounds
        is enabled.
        (check_array_refs, check_array_bounds, check_array_ref): New.


Added:
    branches/suse/gcc-4_2-branch/gcc/testsuite/g++.dg/warn/Warray-bounds-2.C
      - copied unchanged from r120898, trunk/gcc/testsuite/g++.dg/warn/Warray-bounds-2.C
    branches/suse/gcc-4_2-branch/gcc/testsuite/g++.dg/warn/Warray-bounds.C
      - copied unchanged from r120898, trunk/gcc/testsuite/g++.dg/warn/Warray-bounds.C
    branches/suse/gcc-4_2-branch/gcc/testsuite/gcc.dg/Warray-bounds-2.c
      - copied unchanged from r120898, trunk/gcc/testsuite/gcc.dg/Warray-bounds-2.c
    branches/suse/gcc-4_2-branch/gcc/testsuite/gcc.dg/Warray-bounds.c
      - copied unchanged from r120898, trunk/gcc/testsuite/gcc.dg/Warray-bounds.c
Modified:
    branches/suse/gcc-4_2-branch/gcc/Makefile.in
    branches/suse/gcc-4_2-branch/gcc/c-opts.c
    branches/suse/gcc-4_2-branch/gcc/common.opt
    branches/suse/gcc-4_2-branch/gcc/config/i386/i386.h
    branches/suse/gcc-4_2-branch/gcc/doc/invoke.texi
    branches/suse/gcc-4_2-branch/gcc/tree-vrp.c