Better sequence point warnings

Bernd Schmidt bernds@redhat.co.uk
Mon Oct 16 05:57:00 GMT 2000


I found the new sequence point warnings rather interesting, but the current
code has some drawbacks, the main one being that it's based on checking
MODIFY_EXPRs only (missing simple cases like "f (a++, a++)").

This one is a reimplementation which should fix these problems.  I know of
no cases where this current algorithm generates false positives, with one
exception: in one of the testcases in sequence-pt-1.c, constant folding
removes a sequence point and this leads to a warning.  This is a bug in
fold-const.c AFAICT, so I've removed the xfail.

It also detects a couple new cases, but there's no hope of catching them
all.  There are some easy ones still missing, however: verifying accesses
to structure elements being the most straightforward extension.


Bernd

	* c-tree.h (warn_sequence_point): Move declaration to...
	* c-common.h (warn_sequence_point): ... here.
	* c-decl.c (warn_sequence_point): Move definition to...
	* c-common.c (warn_sequence_point): ... here.
	(struct reverse_tree): New.
	(reverse_list, reverse_max_depth): New static variables.
	(build_reverse_tree, common_ancestor, modify_ok
	verify_sequence_points): New functions.
	(c_expand_expr_stmt): Call verify_sequence_points if -Wsequence-point.
	* c-typeck.c (check_modify_expr): Delete.
	(build_modify_expr): Don't call it.

	* sequence-pt-1.c: Several new tests; remove xfail from some old tests.

Index: c-common.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/c-common.c,v
retrieving revision 1.170
diff -u -p -r1.170 c-common.c
--- c-common.c	2000/10/13 19:28:07	1.170
+++ c-common.c	2000/10/16 12:35:47
@@ -140,6 +140,10 @@ cpp_reader  parse_in;
 
 tree c_global_trees[CTI_MAX];
 
+/* Nonzero means warn about possible violations of sequence point rules.  */
+
+int warn_sequence_point;
+
 /* The elements of `ridpointers' are identifier nodes for the reserved
    type names and storage classes.  It is indexed by a RID_... value.  */
 tree *ridpointers;
@@ -3162,6 +3167,263 @@ convert_and_check (type, expr)
   return t;
 }
 
+/* Describe a reversed version of a normal tree, so that we can get to the
+   parent of each node.  */
+struct reverse_tree
+{
+  /* All reverse_tree structures for a given tree are chained through this
+     field.  */
+  struct reverse_tree *next;
+  /* The parent of this node.  */
+  struct reverse_tree *parent;
+  /* The actual tree node.  */
+  tree x;
+  /* The operand number this node corresponds to in the parent.  */
+  int operandno;
+  /* Describe whether this expression is written to or read.  */
+  char read, write;
+};
+
+/* A list of all reverse_tree structures for a given expression, built by
+   build_reverse_tree.  */
+static struct reverse_tree *reverse_list;
+/* The maximum depth of a tree, computed by build_reverse_tree.  */
+static int reverse_max_depth;
+
+static void build_reverse_tree PARAMS ((tree, struct reverse_tree *, int, int,
+					int, int));
+static struct reverse_tree *common_ancestor PARAMS ((struct reverse_tree *,
+						     struct reverse_tree *,
+						     struct reverse_tree **,
+						     struct reverse_tree **));
+static int modify_ok PARAMS ((struct reverse_tree *, struct reverse_tree *));
+static void verify_sequence_points PARAMS ((tree));
+
+/* Recursively process an expression, X, building a reverse tree while
+   descending and recording OPERANDNO, READ, and WRITE in the created
+   structures.  DEPTH is used to compute reverse_max_depth.
+   FIXME: if walk_tree gets moved out of the C++ front end, this should
+   probably use walk_tree.  */
+
+static void
+build_reverse_tree (x, parent, operandno, read, write, depth)
+     tree x;
+     struct reverse_tree *parent;
+     int operandno, read, write, depth;
+{
+  struct reverse_tree *node;
+
+  if (x == 0 || x == error_mark_node)
+    return;
+
+  node = (struct reverse_tree *) xmalloc (sizeof (struct reverse_tree));
+
+  node->parent = parent;
+  node->x = x;
+  node->read = read;
+  node->write = write;
+  node->operandno = operandno;
+  node->next = reverse_list;
+  reverse_list = node;
+  if (depth > reverse_max_depth)
+    reverse_max_depth = depth;
+
+  switch (TREE_CODE (x))
+    {
+    case PREDECREMENT_EXPR:
+    case PREINCREMENT_EXPR:
+    case POSTDECREMENT_EXPR:
+    case POSTINCREMENT_EXPR:
+      build_reverse_tree (TREE_OPERAND (x, 0), node, 0, 1, 1, depth + 1);
+      break;
+
+    case CALL_EXPR:
+      build_reverse_tree (TREE_OPERAND (x, 0), node, 0, 1, 0, depth + 1);
+      x = TREE_OPERAND (x, 1);
+      while (x)
+	{
+	  build_reverse_tree (TREE_VALUE (x), node, 1, 1, 0, depth + 1);
+	  x = TREE_CHAIN (x);
+	}
+      break;
+
+    case TREE_LIST:
+      /* Scan all the list, e.g. indices of multi dimensional array.  */
+      while (x)
+	{
+	  build_reverse_tree (TREE_VALUE (x), node, 0, 1, 0, depth + 1);
+	  x = TREE_CHAIN (x);
+	}
+      break;
+
+    case MODIFY_EXPR:
+      build_reverse_tree (TREE_OPERAND (x, 0), node, 0, 0, 1, depth + 1);
+      build_reverse_tree (TREE_OPERAND (x, 1), node, 1, 1, 0, depth + 1);
+      break;
+
+    default:
+      switch (TREE_CODE_CLASS (TREE_CODE (x)))
+	{
+	case 'r':
+	case '<':
+	case '2':
+	case 'b':
+	case '1':
+	case 'e':
+	case 's':
+	case 'x':
+	  {
+	    int lp;
+	    int max = first_rtl_op (TREE_CODE (x));
+	    for (lp = 0; lp < max; lp++)
+	      build_reverse_tree (TREE_OPERAND (x, lp), node, lp, 1, 0,
+				  depth + 1);
+	    break;
+	  }
+	default:
+	  break;
+	}
+      break;
+    }
+}
+
+/* Given nodes P1 and P2 as well as enough scratch space pointed to by TMP1
+   and TMP2, find the common ancestor of P1 and P2.  */
+
+static struct reverse_tree *
+common_ancestor (p1, p2, tmp1, tmp2)
+     struct reverse_tree *p1, *p2;
+     struct reverse_tree **tmp1, **tmp2;
+{
+  struct reverse_tree *t1 = p1;
+  struct reverse_tree *t2 = p2;
+  int i, j;
+
+  /* First, check if we're actually looking at the same expression twice,
+     which can happen if it's wrapped in a SAVE_EXPR - in this case there's
+     no chance of conflict.  */
+  while (t1 && t2 && t1->x == t2->x)
+    {
+      if (TREE_CODE (t1->x) == SAVE_EXPR)
+	return 0;
+      t1 = t1->parent;
+      t2 = t2->parent;
+    }
+
+  for (i = 0; p1; i++, p1 = p1->parent)
+    tmp1[i] = p1;
+  for (j = 0; p2; j++, p2 = p2->parent)
+    tmp2[j] = p2;
+  while (tmp1[i - 1] == tmp2[j - 1])
+    i--, j--;
+
+  return tmp1[i];
+}
+
+/* Subroutine of verify_sequence_points to check whether a node T corresponding
+   to a MODIFY_EXPR invokes undefined behaviour.  OTHER occurs somewhere in the
+   RHS, and an identical expression is the LHS of T.
+   For MODIFY_EXPRs, some special cases apply when testing for undefined
+   behaviour if one of the expressions we found is the LHS of the MODIFY_EXPR.
+   If the other expression is just a use, then there's no undefined behaviour.
+   Likewise, if the other expression is wrapped inside another expression that
+   will force a sequence point, then there's no undefined behaviour either.  */
+
+static int
+modify_ok (t, other)
+     struct reverse_tree *t, *other;
+{
+  struct reverse_tree *p;
+
+  if (! other->write)
+    return 1;
+
+  /* See if there's an intervening sequence point.  */
+  for (p = other; p->parent != t; p = p->parent)
+    {
+      if ((TREE_CODE (p->parent->x) == COMPOUND_EXPR
+	   || TREE_CODE (p->parent->x) == TRUTH_ANDIF_EXPR
+	   || TREE_CODE (p->parent->x) == TRUTH_ORIF_EXPR
+	   || TREE_CODE (p->parent->x) == COND_EXPR)
+	  && p->operandno == 0)
+	return 1;
+      if (TREE_CODE (p->parent->x) == SAVE_EXPR)
+	return 1;
+      if (TREE_CODE (p->parent->x) == CALL_EXPR
+	  && p->operandno != 0)
+	return 1;
+    }
+  return 0;
+}
+
+/* Try to warn for undefined behaviour in EXPR due to missing sequence
+   points.  */
+
+static void
+verify_sequence_points (expr)
+     tree expr;
+{
+  struct reverse_tree **tmp1, **tmp2;
+  struct reverse_tree *p;
+
+  reverse_list = 0;
+  reverse_max_depth = 0;
+  build_reverse_tree (expr, NULL, 0, 1, 0, 1);
+
+  tmp1 = (struct reverse_tree **) xmalloc (sizeof (struct reverse_tree *)
+					   * reverse_max_depth);
+  tmp2 = (struct reverse_tree **) xmalloc (sizeof (struct reverse_tree *)
+					   * reverse_max_depth);
+
+  /* Search for multiple occurrences of the same variable, where either both
+     occurrences are writes, or one is a read and a write.  If we can't prove
+     that these are ordered by a sequence point, warn that the expression is
+     undefined.  */
+  for (p = reverse_list; p; p = p->next)
+    {
+      struct reverse_tree *p2;
+      if (TREE_CODE (p->x) != VAR_DECL && TREE_CODE (p->x) != PARM_DECL)
+	continue;
+      for (p2 = p->next; p2; p2 = p2->next)
+	{
+	  if ((TREE_CODE (p2->x) == VAR_DECL || TREE_CODE (p2->x) == PARM_DECL)
+	      && DECL_NAME (p->x) == DECL_NAME (p2->x)
+	      && (p->write || p2->write))
+	    {
+	      struct reverse_tree *t = common_ancestor (p, p2, tmp1, tmp2);
+
+	      if (t == 0
+		  || TREE_CODE (t->x) == COMPOUND_EXPR
+		  || TREE_CODE (t->x) == TRUTH_ANDIF_EXPR
+		  || TREE_CODE (t->x) == TRUTH_ORIF_EXPR
+		  || TREE_CODE (t->x) == COND_EXPR)
+		continue;
+	      if (TREE_CODE (t->x) == MODIFY_EXPR
+		  && p->parent == t
+		  && modify_ok (t, p2))
+		continue;
+	      if (TREE_CODE (t->x) == MODIFY_EXPR
+		  && p2->parent == t
+		  && modify_ok (t, p))
+		continue;
+
+	      warning ("operation on `%s' may be undefined",
+		       IDENTIFIER_POINTER (DECL_NAME (p->x)));
+	      break;
+	    }
+	}
+    }
+
+  while (reverse_list)
+    {
+      struct reverse_tree *p = reverse_list;
+      reverse_list = p->next;
+      free (p);
+    }
+  free (tmp1);
+  free (tmp2);
+}
+
 void
 c_expand_expr_stmt (expr)
      tree expr;
@@ -3171,6 +3433,9 @@ c_expand_expr_stmt (expr)
   if ((TREE_CODE (TREE_TYPE (expr)) == ARRAY_TYPE && lvalue_p (expr))
       || TREE_CODE (TREE_TYPE (expr)) == FUNCTION_TYPE)
     expr = default_conversion (expr);
+
+  if (warn_sequence_point)
+    verify_sequence_points (expr);
 
   if (TREE_TYPE (expr) != error_mark_node
       && !COMPLETE_OR_VOID_TYPE_P (TREE_TYPE (expr))
Index: c-common.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/c-common.h,v
retrieving revision 1.42
diff -u -p -r1.42 c-common.h
--- c-common.h	2000/10/08 21:20:43	1.42
+++ c-common.h	2000/10/16 12:35:48
@@ -337,6 +337,10 @@ extern int flag_const_strings;
 
 extern int warn_format;
 
+/* Warn about possible violations of sequence point rules.  */
+
+extern int warn_sequence_point;
+
 /* Nonzero means do some things the same way PCC does.  */
 
 extern int flag_traditional;
Index: c-decl.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/c-decl.c,v
retrieving revision 1.166
diff -u -p -r1.166 c-decl.c
--- c-decl.c	2000/10/13 06:26:23	1.166
+++ c-decl.c	2000/10/16 12:35:49
@@ -494,10 +494,6 @@ int warn_float_equal = 0;
 
 int warn_multichar = 1;
 
-/* Nonzero means warn about possible violations of sequence point rules.  */
-
-int warn_sequence_point;
-
 /* The variant of the C language being processed.  */
 
 c_language_kind c_language = clk_c;
Index: c-tree.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/c-tree.h,v
retrieving revision 1.48
diff -u -p -r1.48 c-tree.h
--- c-tree.h	2000/10/11 21:54:31	1.48
+++ c-tree.h	2000/10/16 12:35:50
@@ -366,10 +366,6 @@ extern int warn_missing_braces;
 
 extern int warn_sign_compare;
 
-/* Warn about possible violations of sequence point rules.  */
-
-extern int warn_sequence_point;
-
 /* Warn about testing equality of floating point numbers. */
 
 extern int warn_float_equal;
Index: c-typeck.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/c-typeck.c,v
retrieving revision 1.94
diff -u -p -r1.94 c-typeck.c
--- c-typeck.c	2000/10/11 21:54:31	1.94
+++ c-typeck.c	2000/10/16 12:35:51
@@ -61,7 +61,6 @@ static tree pointer_diff		PARAMS ((tree,
 static tree unary_complex_lvalue	PARAMS ((enum tree_code, tree));
 static void pedantic_lvalue_warning	PARAMS ((enum tree_code));
 static tree internal_build_compound_expr PARAMS ((tree, int));
-static void check_modify_expr		PARAMS ((tree, tree));
 static tree convert_for_assignment	PARAMS ((tree, tree, const char *,
 						 tree, tree, int));
 static void warn_for_assignment		PARAMS ((const char *, const char *,
@@ -3816,132 +3815,6 @@ build_c_cast (type, expr)
   return value;
 }
 
-/* Recursive check for expressions that break the sequence point rules
-   and so have undefined semantics (e.g. n = n++).  FIXME: if walk_tree
-   gets moved out of the C++ front end, this should probably be moved
-   to code shared between the front ends and use walk_tree.  */
-static void
-check_modify_expr (lhs, rhs)
-     tree lhs, rhs;
-{
-  tree identifier_name;   /* A VAR_DECL name on the LHS that could
-			     be the same as one on the RHS. */
-  identifier_name = NULL_TREE;
-
-  if ((lhs == NULL_TREE) || (rhs == NULL_TREE))
-    return;
-
-  switch (TREE_CODE (rhs))
-    {
-    case ERROR_MARK:
-      return;
-    case VAR_DECL:
-    case PARM_DECL:
-      identifier_name = DECL_NAME (rhs);
-      break;
-    case PREDECREMENT_EXPR:
-    case PREINCREMENT_EXPR:
-    case POSTDECREMENT_EXPR:
-    case POSTINCREMENT_EXPR:
-      {
-	tree var_decl = TREE_OPERAND (rhs, 0);
-	if (TREE_CODE (var_decl) == VAR_DECL
-	    || TREE_CODE (var_decl) == PARM_DECL)
-	  identifier_name = DECL_NAME (var_decl);
-      }
-      break;
-    case TREE_LIST:
-      {
-	tree parm = TREE_CHAIN (rhs);
-	/* Now scan all the list, e.g. indices of multi dimensional array.  */
-	while (parm)
-	  {
-	    check_modify_expr (lhs, TREE_VALUE (parm));
-	    parm = TREE_CHAIN (parm);
-	  }
-      }
-      return;
-    case NOP_EXPR:
-    case CONVERT_EXPR:
-    case NON_LVALUE_EXPR:
-      check_modify_expr (lhs, TREE_OPERAND (rhs, 0));
-      return;
-    case MODIFY_EXPR:
-      /* First check for form a = b = a++ by checking RHS.  */
-      check_modify_expr (lhs, TREE_OPERAND (rhs, 1));
-      /* Then check for a = (a = 1) + 2 and a = b[a++] = c.  */
-      if (TREE_CODE (TREE_OPERAND (rhs, 0)) == VAR_DECL
-	  || TREE_CODE (TREE_OPERAND (rhs, 0)) == PARM_DECL)
-	{
-	  identifier_name = DECL_NAME (TREE_OPERAND (rhs, 0));
-	  break;
-	}
-      else
-	{
-	  check_modify_expr (lhs, TREE_OPERAND (rhs, 0));
-	  return;
-	}
-    default:
-      /* We don't know what to do... pray check_modify_expr removes
-	 loops in the tree.  */
-      switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
-	{
-	case 'r':
-	case '<':
-	case '2':
-	case 'b':
-	case '1':
-	case 'e':
-	case 's':
-	case 'x':
-	  {
-	    int lp;
-	    int max = first_rtl_op (TREE_CODE (rhs));
-	    for (lp = 0; lp < max; lp++)
-	      check_modify_expr (lhs, TREE_OPERAND (rhs, lp));
-	    return;
-	  }
-	default:
-	  return;
-	}
-      break;
-    }
-  if (identifier_name != NULL_TREE)
-    {
-      switch (TREE_CODE (lhs))
-	{
-	case ERROR_MARK:
-	  return;
-	  /* Perhaps this variable was incremented on the RHS.  */
-	case VAR_DECL:
-	case PARM_DECL:
-	  if (TREE_CODE (rhs) != VAR_DECL && TREE_CODE (rhs) != PARM_DECL)
-	    if (DECL_NAME (lhs) == identifier_name)
-	      warning ("operation on `%s' may be undefined",
-		       IDENTIFIER_POINTER (DECL_NAME (lhs)));
-	  break;
-	case PREDECREMENT_EXPR:
-	case PREINCREMENT_EXPR:
-	case POSTDECREMENT_EXPR:
-	case POSTINCREMENT_EXPR:
-	  {
-	    tree var_decl = TREE_OPERAND (lhs, 0);
-	    if (TREE_CODE (var_decl) == VAR_DECL
-		|| TREE_CODE (var_decl) == PARM_DECL)
-	      if (identifier_name == DECL_NAME (var_decl))
-		warning ("operation on `%s' may be undefined",
-			 IDENTIFIER_POINTER (DECL_NAME (var_decl)));
-	  }
-	  break;
-	default:
-	  /* To save duplicating tree traversal code swap args, and recurse.  */
-	  check_modify_expr (rhs, lhs);
-	  break;
-	}
-    }
-}
-
-
 /* Build an assignment expression of lvalue LHS from value RHS.
    MODIFYCODE is the code for a binary operator that we use
    to combine the old value of LHS with RHS to get the new value.
@@ -4095,9 +3968,6 @@ build_modify_expr (lhs, modifycode, rhs)
 				   NULL_TREE, NULL_TREE, 0);
   if (TREE_CODE (newrhs) == ERROR_MARK)
     return error_mark_node;
-
-  if (warn_sequence_point)
-    check_modify_expr (lhs, rhs);
 
   /* Scan operands */
 
Index: testsuite/gcc.dg/sequence-pt-1.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/testsuite/gcc.dg/sequence-pt-1.c,v
retrieving revision 1.1
diff -u -p -r1.1 sequence-pt-1.c
--- testsuite/gcc.dg/sequence-pt-1.c	2000/10/11 21:54:33	1.1
+++ testsuite/gcc.dg/sequence-pt-1.c	2000/10/16 12:35:53
@@ -11,6 +11,8 @@ struct s
 };
 
 extern int fn (int);
+extern int fnb (int, int);
+extern int fnc (int *);
 extern int sprintf (char *, const char *, ...);
 
 void
@@ -22,7 +24,6 @@ foo (int a, int b, int n, int p, int *pt
   a = --a; /* { dg-warning "undefined" "sequence point warning" } */
   a = ++a + b; /* { dg-warning "undefined" "sequence point warning" } */
   a = a-- + b; /* { dg-warning "undefined" "sequence point warning" } */
-  a = (a++ && 4); /* { dg-bogus "undefined" "bogus sequence point warning" { xfail *-*-* } } */
   ap[n] = bp[n++]; /* { dg-warning "undefined" "sequence point warning" } */
   ap[--n] = bp[n]; /* { dg-warning "undefined" "sequence point warning" } */
   ap[++n] = bp[--n]; /* { dg-warning "undefined" "sequence point warning" } */
@@ -31,12 +32,27 @@ foo (int a, int b, int n, int p, int *pt
   *ptr++ = (int)ptr++; /* { dg-warning "undefined" "sequence point warning" } */
   sptr->a = sptr->a++; /* { dg-warning "undefined" "sequence point warning" { xfail *-*-* } } */
   sptr->a = (int)(sptr++); /* { dg-warning "undefined" "sequence point warning" } */
-  len = sprintf (ans, "%d", len++); /* { dg-bogus "undefined" "bogus sequence point warning" { xfail *-*-* } } */
-  *ptr++ = fn (*ptr); /* { dg-warning "undefined" "sequence point warning" { xfail *-*-* } } */
+  *ptr++ = fn (*ptr); /* { dg-warning "undefined" "sequence point warning" } */
   a = b = a++; /* { dg-warning "undefined" "sequence point warning" } */
   b = a = --b; /* { dg-warning "undefined" "sequence point warning" } */
   a = 1 + (a = 1); /* { dg-warning "undefined" "sequence point warning" } */
   a = (a = b); /* { dg-warning "undefined" "sequence point warning" } */
   a = (a = b) + 1; /* { dg-warning "undefined" "sequence point warning" } */
   a = (bp[a++] = b) + 1; /* { dg-warning "undefined" "sequence point warning" } */
+  a = b++ * b++; /* { dg-warning "undefined" "sequence point warning" } */
+  a = fnb (b++, b++); /* { dg-warning "undefined" "sequence point warning" } */
+  *ap = fnc (ap++); /* { dg-warning "undefined" "sequence point warning" } */
+  (a += b) + (a += n); /* { dg-warning "undefined" "sequence point warning" } */
+  a =  (b, b++) + (b++, b); /* { dg-warning "undefined" "sequence point warning" } */
+
+  a = (a++ && 4); /* { dg-bogus "undefined" "bogus sequence point warning" } */
+  len = sprintf (ans, "%d", len++); /* { dg-bogus "undefined" "bogus sequence point warning" } */
+  a = fn (a++); /* { dg-bogus "undefined" "sequence point warning" } */
+  (a = b++), (a = b++); /* { dg-bogus "undefined" "sequence point warning" } */
+  a = (b++, b++); /* { dg-bogus "undefined" "sequence point warning" } */
+  a = b++ && b++; /* { dg-bogus "undefined" "sequence point warning" } */
+  a = b++ || b++; /* { dg-bogus "undefined" "sequence point warning" } */
+  a = (b++ ? b++ : a); /* { dg-bogus "undefined" "sequence point warning" } */
+  a = (b++ ? a : b++); /* { dg-bogus "undefined" "sequence point warning" } */
+  ap[a++] += bp[b]; /* { dg-bogus "undefined" "sequence point warning" } */
 }



More information about the Gcc-patches mailing list