Re: [PATCH] Fix PR/8268: implement compile time array subscript checking

[Dirk Mueller <dmuell@gmx.net>]

[-- Attachment #1: Type: text/plain, Size: 1452 bytes --]

On Saturday, 13. January 2007 18:35, Roger Sayle wrote:

I've addressed your coding style comments. 

> > +static bool array_bounds_already_done;
> New global variables require a comment above them, describing their
> semantics.  Particularly important is their scope.  It looks like this
> variable is never reset, so you may only be reporting array bounds
> problems (or some class of array bound problems) for the first function
> in a file (or the first function to reach VRP).

Hmm, indeed, this is a major oversight which I forgot about :-( It sucks when 
you put aside a half-finished patch for almost a year and then forget about 
all the unfinished todo's. Many thanks for catching this. I've reworked the 
patch by removing this static variable and adding a workaround to avoid 
warning on such statements as generated by the optimizing passes.

> As a very minor style nit, though this is just a personal preference,
> initially unconditionally sets the warning issued indicator, then decides
> whether or not to issue the warning and ultimately may reset it back to
> zero in the common case. 

Correct, which made the patch quite some lines shorter :)

> Much preferred is something like: 

Ok, I don't mind much, so I've changed it that way now. 

Many thanks for looking at the patch. 

Patch below is bootstrapped and regtested against not entirely recent trunk 
(because of the current bootstrap failure) with no new failures. 


Dirk

[-- Attachment #2: array_bounds_vrp_4.patch --]
[-- Type: text/x-diff, Size: 11107 bytes --]

2007-01-15  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.
	* tree-vrp.c (vrp_finalize): Call check_array_refs if -Warray-bounds
	is enabled.
	(check_array_refs, check_array_bounds, check_array_ref): New.

	* testsuite/gcc.dg/Warray-bounds.c: New testcase.


--- doc/invoke.texi	(revision 120757)
+++ doc/invoke.texi	(working copy)
@@ -247,7 +247,7 @@ Objective-C and Objective-C++ Dialects}.
 -Wreturn-type  -Wsequence-point  -Wshadow @gol
 -Wsign-compare  -Wstack-protector @gol
 -Wstrict-aliasing -Wstrict-aliasing=2 @gol
--Wstring-literal-comparison @gol
+-Wstring-literal-comparison -Warray-bounds @gol
 -Wswitch  -Wswitch-default  -Wswitch-enum @gol
 -Wsystem-headers  -Wtrigraphs  -Wundef  -Wuninitialized @gol
 -Wunknown-pragmas  -Wno-pragmas -Wunreachable-code @gol
@@ -2842,6 +2843,12 @@ compiler is using for optimization.  Thi
 @option{-Wstrict-aliasing}, but it will also give a warning for some ambiguous
 cases that are safe.
 
+@item -Warray-bounds
+@opindex Warray-bounds
+This option is only active when @option{-ftree-vrp} is active
+(default for -O2 and above). It warns about subscripts to arrays
+that are always out of bounds.
+
 @item -Wall
 @opindex Wall
 All of the above @samp{-W} options combined.  This enables all the
--- common.opt	(revision 120757)
+++ common.opt	(working copy)
@@ -61,6 +61,10 @@ Walways-true
 Common Var(warn_always_true)
 Warn about comparisons that always evaluate to true
 
+Warray-bounds
+Common Var(warn_array_bounds)
+Warn if an array is accessed out of bounds
+
 Wattributes
 Common Var(warn_attributes) Init(1)
 Warn about inappropriate attribute usage
--- Makefile.in	(revision 120757)
+++ Makefile.in	(working copy)
@@ -1862,7 +1862,7 @@ tree-vn.o : tree-vn.c $(CONFIG_H) $(SYST
 tree-vrp.o : tree-vrp.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
    $(TREE_FLOW_H) tree-pass.h $(TREE_DUMP_H) $(DIAGNOSTIC_H) $(GGC_H) \
    $(BASIC_BLOCK_H) tree-ssa-propagate.h $(FLAGS_H) $(TREE_DUMP_H) \
-   $(CFGLOOP_H) $(SCEV_H) tree-chrec.h $(TIMEVAR_H)
+   $(CFGLOOP_H) $(SCEV_H) tree-chrec.h $(TIMEVAR_H) toplev.h
 tree-cfg.o : tree-cfg.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
    $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) $(FLAGS_H) output.h \
    $(DIAGNOSTIC_H) $(FUNCTION_H) $(TIMEVAR_H) $(TM_H) coretypes.h \
--- tree-vrp.c	(revision 120757)
+++ tree-vrp.c	(working copy)
@@ -32,6 +32,7 @@ Boston, MA 02110-1301, USA.  */
 #include "tree-dump.h"
 #include "timevar.h"
 #include "diagnostic.h"
+#include "toplev.h"
 #include "cfgloop.h"
 #include "tree-scalar-evolution.h"
 #include "tree-ssa-propagate.h"
@@ -3478,6 +3478,154 @@ insert_range_assertions (void)
   BITMAP_FREE (need_assert_for);
 }
 
+/* Checks one ARRAY_REF in REF, located at LOCUS. Ignores flexible arrays
+   and "struct" hacks. If VRP can determine that the
+   array subscript is a contant, check if it is outside valid
+   range. If the array subscript is a RANGE, warn if it is
+   non-overlapping with valid range.
+   IGNORE_OFF_BY_ONE is true if the ARRAY_REF is inside a ADDR_EXPR.  */
+
+static void
+check_array_ref (tree ref, location_t* locus, bool ignore_off_by_one)
+{
+  value_range_t* vr = NULL;
+  tree low_sub, up_sub;
+  tree low_bound, up_bound = array_ref_up_bound (ref);
+
+  low_sub = up_sub = TREE_OPERAND (ref, 1);
+
+  if (!up_bound || !locus || TREE_NO_WARNING (ref)
+      || TREE_CODE (up_bound) != INTEGER_CST
+      /* Can not check flexible arrays.  */
+      || (TYPE_SIZE (TREE_TYPE (ref)) == NULL_TREE
+          && TYPE_DOMAIN (TREE_TYPE (ref)) != NULL_TREE
+          && TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (ref))) == NULL_TREE)
+      /* Accesses after the end of arrays of size 0 (gcc
+         extension) and 1 are likely intentional ("struct
+         hack").  */
+      || compare_tree_int (up_bound, 1) <= 0)
+    return;
+
+  low_bound = array_ref_low_bound (ref);
+
+  if (TREE_CODE (low_sub) == SSA_NAME)
+    {
+      vr = get_value_range (low_sub);
+      if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
+        {
+          low_sub = vr->type == VR_RANGE ? vr->max : vr->min;
+          up_sub = vr->type == VR_RANGE ? vr->min : vr->max;
+        }
+    }
+
+  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 (OPT_Warray_bounds,
+                   "%Harray subscript is outside array bounds", locus);
+          TREE_NO_WARNING (ref) = 1;
+        }
+    }
+  else if (TREE_CODE (up_sub) == INTEGER_CST
+           && tree_int_cst_lt (up_bound, up_sub)
+           && !tree_int_cst_equal (up_bound, up_sub)
+           && (!ignore_off_by_one
+               || !tree_int_cst_equal (int_const_binop (PLUS_EXPR,
+                                                        up_bound,
+                                                        integer_one_node,
+                                                        0),
+                                       up_sub)))
+    {
+      warning (OPT_Warray_bounds, "%Harray subscript is above array bounds",
+               locus);
+      TREE_NO_WARNING (ref) = 1;
+    }
+  else if (TREE_CODE (low_sub) == INTEGER_CST
+           && tree_int_cst_lt (low_sub, low_bound))
+    {
+      warning (OPT_Warray_bounds, "%Harray subscript is below array bounds",
+               locus);
+      TREE_NO_WARNING (ref) = 1;
+    }
+}
+
+/* walk_tree() callback that checks if *TP is
+   an ARRAY_REF inside an ADDR_EXPR (in which an array
+   subscript one outside the valid range is allowed). Call
+   check_array_ref for each ARRAY_REF found. The location is 
+   passed in DATA.  */
+
+static tree
+check_array_bounds (tree *tp, int *walk_subtree, void *data)
+{
+  tree t = *tp;
+  location_t *location = EXPR_LOCUS ((tree) data);
+
+  *walk_subtree = TRUE;
+
+  if (TREE_CODE (t) == ARRAY_REF)
+    check_array_ref (t, location, false /*ignore_off_by_one*/);
+  else if (TREE_CODE (t) == ADDR_EXPR)
+    {
+       t = TREE_OPERAND (t, 0);
+
+       /* Don't warn on statements like
+          ssa_name = 500 + &array[-200] which are sometimes
+          produced by various optimizing passes.  */
+       if (TREE_CODE ((tree)data) == GIMPLE_MODIFY_STMT
+           && BINARY_CLASS_P (GIMPLE_STMT_OPERAND ((tree)data, 1)))
+         {
+           *walk_subtree = FALSE;
+           return NULL_TREE;
+         }
+       while (handled_component_p (t))
+         {
+           if (TREE_CODE (t) == ARRAY_REF)
+             check_array_ref (t, location, true /*ignore_off_by_one*/);
+           t = TREE_OPERAND (t, 0);
+         }
+       *walk_subtree = FALSE;
+    }
+
+  return NULL_TREE;
+}
+
+/* Walk over all statements of all reachable BBs and call check_array_bounds
+   on them.  */
+
+static void
+check_all_array_refs (void)
+{
+  basic_block bb;
+  block_stmt_iterator si;
+
+  FOR_EACH_BB (bb)
+    {
+      /* Skip bb's that are clearly unreachable.  */
+      if (single_pred_p (bb))
+      {
+	basic_block pred_bb = EDGE_PRED (bb, 0)->src;
+	tree ls = NULL_TREE;
+
+	if (!bsi_end_p (bsi_last (pred_bb)))
+	  ls = bsi_stmt (bsi_last (pred_bb));
+
+	if (ls && TREE_CODE (ls) == COND_EXPR
+	    && ((COND_EXPR_COND (ls) == boolean_false_node
+		 && (EDGE_PRED (bb, 0)->flags & EDGE_TRUE_VALUE))
+		|| (COND_EXPR_COND (ls) == boolean_true_node
+		    && (EDGE_PRED (bb, 0)->flags & EDGE_FALSE_VALUE))))
+	  continue;
+      }
+      for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
+	walk_tree (bsi_stmt_ptr (si), check_array_bounds,
+		   bsi_stmt (si), NULL);
+    }
+}
 
 /* Convert range assertion expressions into the implied copies and
    copy propagate away the copies.  Doing the trivial copy propagation
@@ -4797,6 +4945,9 @@ vrp_finalize (void)
 
   substitute_and_fold (single_val_range, true);
 
+  if (warn_array_bounds)
+      check_all_array_refs();
+
   /* We must identify jump threading opportunities before we release
      the datastructures built by VRP.  */
   identify_jump_threads ();
--- testsuite/gcc.dg/Warray-bounds.c	(revision 0)
+++ testsuite/gcc.dg/Warray-bounds.c	(revision 0)
@@ -0,0 +1,94 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -Warray-bounds" } */
+
+int a[10];
+
+static inline int n(void) {
+    __SIZE_TYPE__ strlen(const char *s);
+    return strlen("12345");
+}
+
+void g(int *p);
+void h(int p);
+
+int* f(void) {
+    int b[10];
+    int i;
+    struct {
+       int c[10];
+    } c;
+
+    a[-1] = 0;             /* { dg-warning "array subscript" } */
+    a[ 0] = 0;
+    a[ 1] = 0;
+
+
+    a[ 9] = 0;
+    a[10] = 0;             /* { dg-warning "array subscript" } */
+    a[11] = 0;             /* { dg-warning "array subscript" } */
+    a[2 * n() - 11] = 0;    /* { dg-warning "array subscript" } */
+    a[2 * n() - 10] = 0;
+    a[2 * n() -  1] = 0;
+    a[2 * n() -  0] = 0;    /* { dg-warning "array subscript" } */
+
+    b[-1] = 0;             /* { dg-warning "array subscript" } */
+    b[ 0] = 0;
+    b[ 1] = 0;
+    b[ 9] = 0;
+    b[10] = 0;             /* { dg-warning "array subscript" } */
+    b[11] = 0;             /* { dg-warning "array subscript" } */
+    b[2 * n() - 11] = 0;    /* { dg-warning "array subscript" } */
+    b[2 * n() - 10] = 0;
+    b[2 * n() -  1] = 0;
+    b[2 * n() -  0] = 0;    /* { dg-warning "array subscript" } */
+
+    c.c[-1] = 0;           /* { dg-warning "array subscript" } */
+    c.c[ 0] = 0;
+    c.c[ 1] = 0;
+    c.c[ 9] = 0;
+    c.c[10] = 0;           /* { dg-warning "array subscript" } */
+    c.c[11] = 0;           /* { dg-warning "array subscript" } */
+    c.c[2 * n() - 11] = 0;  /* { dg-warning "array subscript" } */
+    c.c[2 * n() - 10] = 0;
+    c.c[2 * n() -  1] = 0;
+    c.c[2 * n() -  0] = 0;  /* { dg-warning "array subscript" } */
+
+    g(&a[8]);
+    g(&a[9]);
+    g(&a[10]);
+    g(&a[11]);             /* { dg-warning "array subscript" } */
+    g(&a[-30]+10);             /* { dg-warning "array subscript" } */
+    g(&a[-30]+30);
+
+    g(&b[10]);
+    g(&c.c[10]);
+    g(&a[11]);             /* { dg-warning "array subscript" } */
+    g(&b[11]);             /* { dg-warning "array subscript" } */
+    g(&c.c[11]);           /* { dg-warning "array subscript" } */
+
+    g(&a[0]);
+    g(&b[0]);
+    g(&c.c[0]);
+
+    g(&a[-1]);             /* { dg-warning "array subscript" } */
+    g(&b[-1]);             /* { dg-warning "array subscript" } */ 
+    h(sizeof a[-1]);
+    h(sizeof a[10]);
+    h(sizeof b[-1]);
+    h(sizeof b[10]);
+    h(sizeof c.c[-1]);
+    h(sizeof c.c[10]);
+
+    if (10 < 10)
+       a[10] = 0;
+    if (10 < 10)
+       b[10] = 0;
+    if (-1 >= 0)
+       c.c[-1] = 0;
+
+    for (i = 20; i < 30; ++i)
+             a[i] = 1;       /* { dg-warning "array subscript" } */
+
+    return a;
+}
+