Patchwork PR53153

login
register
mail settings
Submitter Steven Bosscher
Date May 2, 2012, 8:32 a.m.
Message ID <CABu31nOH+nmDHKQsZToy8mPmkbFPOZ-A43-jXA+_f5Ydckkjzg@mail.gmail.com>
Download mbox | patch
Permalink /patch/156384/
State New
Headers show

Comments

Steven Bosscher - May 2, 2012, 8:32 a.m.
Hello,

The attached patch fixes PR53153.

The problem is that tree-ssa-forwprop.c propagates away a cast, but
leaves out-of-range case labels in the switch. Before my patch for
r186579, the code in stmt.c would remove such case labels before any
of the RTL expanders got to see them. After my patch, the gimplifier
removed those out-of-range labels, but forwprop re-introduces them
and, en passant, makes the type of the switch index expression
different from the types of the case label values.

This patch adds splits out the case label preprocessing code in
gimplify.c to a new function, and makes forwprop use it to update the
switch label values if it changes the switch index type.

Bootstrapped and tested on x86_64-unknown-linux-gnu. OK for trunk?

Ciao!
Steven
gcc/
	* gimplify.c (preprocess_case_label_vec_for_gimple): New function,
	split out from ...
	(gimplify_switch_expr): ... here.
	* gimple.h (preprocess_case_label_vec_for_gimple): Add prototype.
	* tree-ssa-forwprop.c (simplify_gimple_switch_label_vec): New function
	to clean up case labels with values outside the index type range.
	(simplify_gimple_switch): Call it if something changed.
	Remove strange and unnecessary assert.

testsuite/
	* gcc.dg/pr53153.c: New test.
Richard Guenther - May 2, 2012, 10:14 a.m.
On Wed, May 2, 2012 at 10:32 AM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> Hello,
>
> The attached patch fixes PR53153.
>
> The problem is that tree-ssa-forwprop.c propagates away a cast, but
> leaves out-of-range case labels in the switch. Before my patch for
> r186579, the code in stmt.c would remove such case labels before any
> of the RTL expanders got to see them. After my patch, the gimplifier
> removed those out-of-range labels, but forwprop re-introduces them
> and, en passant, makes the type of the switch index expression
> different from the types of the case label values.
>
> This patch adds splits out the case label preprocessing code in
> gimplify.c to a new function, and makes forwprop use it to update the
> switch label values if it changes the switch index type.
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu. OK for trunk?

Ok.

Thanks,
Richard.

> Ciao!
> Steven

Patch

Index: gimplify.c
===================================================================
--- gimplify.c	(revision 186962)
+++ gimplify.c	(working copy)
@@ -1538,7 +1538,7 @@  gimplify_statement_list (tree *expr_p, g
 
   return GS_ALL_DONE;
 }
-
+
 /* Compare two case labels.  Because the front end should already have
    made sure that case ranges do not overlap, it is enough to only compare
    the CASE_LOW values of each case label.  */
@@ -1565,8 +1565,179 @@  sort_case_labels (VEC(tree,heap)* label_
 {
   VEC_qsort (tree, label_vec, compare_case_labels);
 }
+
+/* Prepare a vector of case labels to be used in a GIMPLE_SWITCH statement.
+
+   LABELS is a vector that contains all case labels to look at.
+
+   INDEX_TYPE is the type of the switch index expression.  Case labels
+   in LABELS are discarded if their values are not in the value range
+   covered by INDEX_TYPE.  The remaining case label values are folded
+   to INDEX_TYPE.
+
+   If a default case exists in LABELS, it is removed from LABELS and
+   returned in DEFAULT_CASEP.  If no default case exists, but the
+   case labels already cover the whole range of INDEX_TYPE, a default
+   case is returned pointing to one of the existing case labels.
+   Otherwise DEFAULT_CASEP is set to NULL_TREE.
+
+   DEFAULT_CASEP may be NULL, in which case the above comment doesn't
+   apply and no action is taken regardless of whether a default case is
+   found or not.  */
 
-/* Gimplify a SWITCH_EXPR, and collect a TREE_VEC of the labels it can
+void
+preprocess_case_label_vec_for_gimple (VEC(tree,heap) *labels,
+				      tree index_type,
+				      tree *default_casep)
+{
+  tree min_value, max_value;
+  tree default_case = NULL_TREE;
+  size_t i, len;
+
+  i = 0;
+  min_value = TYPE_MIN_VALUE (index_type);
+  max_value = TYPE_MAX_VALUE (index_type);
+  while (i < VEC_length (tree, labels))
+    {
+      tree elt = VEC_index (tree, labels, i);
+      tree low = CASE_LOW (elt);
+      tree high = CASE_HIGH (elt);
+      bool remove_element = FALSE;
+
+      if (low)
+	{
+	  gcc_checking_assert (TREE_CODE (low) == INTEGER_CST);
+	  gcc_checking_assert (!high || TREE_CODE (high) == INTEGER_CST);
+
+	  /* This is a non-default case label, i.e. it has a value.
+
+	     See if the case label is reachable within the range of
+	     the index type.  Remove out-of-range case values.  Turn
+	     case ranges into a canonical form (high > low strictly)
+	     and convert the case label values to the index type.
+
+	     NB: The type of gimple_switch_index() may be the promoted
+	     type, but the case labels retain the original type.  */
+
+	  if (high)
+	    {
+	      /* This is a case range.  Discard empty ranges.
+		 If the bounds or the range are equal, turn this
+		 into a simple (one-value) case.  */
+	      int cmp = tree_int_cst_compare (high, low);
+	      if (cmp < 0)
+		remove_element = TRUE;
+	      else if (cmp == 0)
+		high = NULL_TREE;
+	    }
+
+	  if (! high)
+	    {
+	      /* If the simple case value is unreachable, ignore it.  */
+	      if ((TREE_CODE (min_value) == INTEGER_CST
+		   && tree_int_cst_compare (low, min_value) < 0)
+		  || (TREE_CODE (max_value) == INTEGER_CST
+		      && tree_int_cst_compare (low, max_value) > 0))
+		remove_element = TRUE;
+	      else
+		low = fold_convert (index_type, low);
+	    }
+	  else
+	    {
+	      /* If the entire case range is unreachable, ignore it.  */
+	      if ((TREE_CODE (min_value) == INTEGER_CST
+		   && tree_int_cst_compare (high, min_value) < 0)
+		  || (TREE_CODE (max_value) == INTEGER_CST
+		      && tree_int_cst_compare (low, max_value) > 0))
+		remove_element = TRUE;
+	      else
+		{
+		  /* If the lower bound is less than the index type's
+		     minimum value, truncate the range bounds.  */
+		  if (TREE_CODE (min_value) == INTEGER_CST
+		      && tree_int_cst_compare (low, min_value) < 0)
+		    low = min_value;
+		  low = fold_convert (index_type, low);
+
+		  /* If the upper bound is greater than the index type's
+		     maximum value, truncate the range bounds.  */
+		  if (TREE_CODE (max_value) == INTEGER_CST
+		      && tree_int_cst_compare (high, max_value) > 0)
+		    high = max_value;
+		  high = fold_convert (index_type, high);
+		}
+	    }
+
+	  CASE_LOW (elt) = low;
+	  CASE_HIGH (elt) = high;
+	}
+      else
+	{
+	  gcc_assert (!default_case);
+	  default_case = elt;
+	  /* The default case must be passed separately to the
+	     gimple_build_switch routines.  But if DEFAULT_CASEP
+	     is NULL, we do not remove the default case (it would
+	     be completely lost).  */
+	  if (default_casep)
+	    remove_element = TRUE;
+	}
+
+      if (remove_element)
+	VEC_ordered_remove (tree, labels, i);
+      else
+	i++;
+    }
+  len = i;
+
+  if (!VEC_empty (tree, labels))
+    sort_case_labels (labels);
+
+  if (default_casep && !default_case)
+    {
+      /* If the switch has no default label, add one, so that we jump
+	 around the switch body.  If the labels already cover the whole
+	 range of the switch index_type, add the default label pointing
+	 to one of the existing labels.  */
+      if (len
+	  && TYPE_MIN_VALUE (index_type)
+	  && TYPE_MAX_VALUE (index_type)
+	  && tree_int_cst_equal (CASE_LOW (VEC_index (tree, labels, 0)),
+				 TYPE_MIN_VALUE (index_type)))
+	{
+	  tree low, high = CASE_HIGH (VEC_index (tree, labels, len - 1));
+	  if (!high)
+	    high = CASE_LOW (VEC_index (tree, labels, len - 1));
+	  if (tree_int_cst_equal (high, TYPE_MAX_VALUE (index_type)))
+	    {
+	      for (i = 1; i < len; i++)
+		{
+		  high = CASE_LOW (VEC_index (tree, labels, i));
+		  low = CASE_HIGH (VEC_index (tree, labels, i - 1));
+		  if (!low)
+		    low = CASE_LOW (VEC_index (tree, labels, i - 1));
+		  if ((TREE_INT_CST_LOW (low) + 1
+		       != TREE_INT_CST_LOW (high))
+		      || (TREE_INT_CST_HIGH (low)
+			  + (TREE_INT_CST_LOW (high) == 0)
+			  != TREE_INT_CST_HIGH (high)))
+		    break;
+		}
+	      if (i == len)
+		{
+		  tree label = CASE_LABEL (VEC_index (tree, labels, 0));
+		  default_case = build_case_label (NULL_TREE, NULL_TREE,
+						   label);
+		}
+	    }
+	}
+    }
+
+  if (default_casep)
+    *default_casep = default_case;
+}
+
+/* Gimplify a SWITCH_EXPR, and collect the vector of labels it can
    branch to.  */
 
 static enum gimplify_status
@@ -1588,9 +1759,7 @@  gimplify_switch_expr (tree *expr_p, gimp
     {
       VEC (tree,heap) *labels;
       VEC (tree,heap) *saved_labels;
-      tree min_value, max_value;
       tree default_case = NULL_TREE;
-      size_t i, len;
       gimple gimple_switch;
 
       /* If someone can be bothered to fill in the labels, they can
@@ -1606,155 +1775,22 @@  gimplify_switch_expr (tree *expr_p, gimp
       labels = gimplify_ctxp->case_labels;
       gimplify_ctxp->case_labels = saved_labels;
 
-      i = 0;
-      min_value = TYPE_MIN_VALUE (index_type);
-      max_value = TYPE_MAX_VALUE (index_type);
-      while (i < VEC_length (tree, labels))
-	{
-	  tree elt = VEC_index (tree, labels, i);
-	  tree low = CASE_LOW (elt);
-	  tree high = CASE_HIGH (elt);
-	  bool remove_element = FALSE;
-
-
-	  if (low)
-	    {
-	      gcc_checking_assert (TREE_CODE (low) == INTEGER_CST);
-	      gcc_checking_assert (!high || TREE_CODE (high) == INTEGER_CST);
-
-	      /* This is a non-default case label, i.e. it has a value.
-
-		 See if the case label is reachable within the range of
-		 the index type.  Remove out-of-range case values.  Turn
-		 case ranges into a canonical form (high > low strictly)
-		 and convert the case label values to the index type.
-
-		 NB: The type of gimple_switch_index() may be the promoted
-		 type, but the case labels retain the original type.  */
-
-	      if (high)
-		{
-		  /* This is a case range.  Discard empty ranges.
-		     If the bounds or the range are equal, turn this
-		     into a simple (one-value) case.  */
-		  int cmp = tree_int_cst_compare (high, low);
-		  if (cmp < 0)
-		    remove_element = TRUE;
-		  else if (cmp == 0)
-		    high = NULL_TREE;
-		}
-
-	      if (! high)
-		{
-		  /* If the simple case value is unreachable, ignore it.  */
-		  if ((TREE_CODE (min_value) == INTEGER_CST
-		       && tree_int_cst_compare (low, min_value) < 0)
-		      || (TREE_CODE (max_value) == INTEGER_CST
-			  && tree_int_cst_compare (low, max_value) > 0))
-		    remove_element = TRUE;
-		  else
-		    low = fold_convert (index_type, low);
-		}
-	      else
-		{
-		  /* If the entire case range is unreachable, ignore it.  */
-		  if ((TREE_CODE (min_value) == INTEGER_CST
-		       && tree_int_cst_compare (high, min_value) < 0)
-		      || (TREE_CODE (max_value) == INTEGER_CST
-			  && tree_int_cst_compare (low, max_value) > 0))
-		    remove_element = TRUE;
-		  else
-		    {
-		      /* If the lower bound is less than the index type's
-			 minimum value, truncate the range bounds.  */
-		      if (TREE_CODE (min_value) == INTEGER_CST
-			  && tree_int_cst_compare (low, min_value) < 0)
-			low = min_value;
-		      low = fold_convert (index_type, low);
-
-		      /* If the upper bound is greater than the index type's
-			 maximum value, truncate the range bounds.  */
-		      if (TREE_CODE (max_value) == INTEGER_CST
-			  && tree_int_cst_compare (high, max_value) > 0)
-			high = max_value;
-		      high = fold_convert (index_type, high);
-		    }
-		}
-
-	      CASE_LOW (elt) = low;
-	      CASE_HIGH (elt) = high;
-	    }
-	  else
-	    {
-	      /* The default case must be the last label in the list.  */
-	      gcc_assert (!default_case);
-	      default_case = elt;
-	      remove_element = TRUE;
-	    }
-
-	  if (remove_element)
-	    VEC_ordered_remove (tree, labels, i);
-	  else
-	    i++;
-	}
-      len = i;
-
-      if (!VEC_empty (tree, labels))
-	sort_case_labels (labels);
+      preprocess_case_label_vec_for_gimple (labels, index_type,
+					    &default_case);
 
       if (!default_case)
 	{
-	  /* If the switch has no default label, add one, so that we jump
-	     around the switch body.  If the labels already cover the whole
-	     range of the switch index_type, add the default label pointing
-	     to one of the existing labels.  */
-	  if (len
-	      && TYPE_MIN_VALUE (index_type)
-	      && TYPE_MAX_VALUE (index_type)
-	      && tree_int_cst_equal (CASE_LOW (VEC_index (tree, labels, 0)),
-				     TYPE_MIN_VALUE (index_type)))
-	    {
-	      tree low, high = CASE_HIGH (VEC_index (tree, labels, len - 1));
-	      if (!high)
-		high = CASE_LOW (VEC_index (tree, labels, len - 1));
-	      if (tree_int_cst_equal (high, TYPE_MAX_VALUE (index_type)))
-		{
-		  for (i = 1; i < len; i++)
-		    {
-		      high = CASE_LOW (VEC_index (tree, labels, i));
-		      low = CASE_HIGH (VEC_index (tree, labels, i - 1));
-		      if (!low)
-			low = CASE_LOW (VEC_index (tree, labels, i - 1));
-		      if ((TREE_INT_CST_LOW (low) + 1
-			   != TREE_INT_CST_LOW (high))
-			  || (TREE_INT_CST_HIGH (low)
-			      + (TREE_INT_CST_LOW (high) == 0)
-			      != TREE_INT_CST_HIGH (high)))
-			break;
-		    }
-		  if (i == len)
-		    {
-		      tree label = CASE_LABEL (VEC_index (tree, labels, 0));
-		      default_case = build_case_label (NULL_TREE, NULL_TREE,
-						       label);
-		    }
-		}
-	    }
-
-	  if (!default_case)
-	    {
-	      gimple new_default;
+	  gimple new_default;
 
-	      default_case
-		= build_case_label (NULL_TREE, NULL_TREE,
-				    create_artificial_label (UNKNOWN_LOCATION));
-	      new_default = gimple_build_label (CASE_LABEL (default_case));
-	      gimplify_seq_add_stmt (&switch_body_seq, new_default);
-	    }
+	  default_case
+	    = build_case_label (NULL_TREE, NULL_TREE,
+				create_artificial_label (UNKNOWN_LOCATION));
+	  new_default = gimple_build_label (CASE_LABEL (default_case));
+	  gimplify_seq_add_stmt (&switch_body_seq, new_default);
 	}
 
       gimple_switch = gimple_build_switch_vec (SWITCH_COND (switch_expr),
-                                               default_case, labels);
+					       default_case, labels);
       gimplify_seq_add_stmt (pre_p, gimple_switch);
       gimplify_seq_add_seq (pre_p, switch_body_seq);
       VEC_free(tree, heap, labels);
Index: tree-ssa-forwprop.c
===================================================================
--- tree-ssa-forwprop.c	(revision 186962)
+++ tree-ssa-forwprop.c	(working copy)
@@ -163,7 +163,7 @@  along with GCC; see the file COPYING3.  
 
 static bool forward_propagate_addr_expr (tree name, tree rhs);
 
-/* Set to true if we delete EH edges during the optimization.  */
+/* Set to true if we delete dead edges during the optimization.  */
 static bool cfg_changed;
 
 static tree rhs_to_tree (tree type, gimple stmt);
@@ -1319,6 +1319,76 @@  simplify_not_neg_expr (gimple_stmt_itera
   return false;
 }
 
+/* Helper function for simplify_gimple_switch.  Remove case labels that
+   have values outside the range of the new type.  */
+
+static void
+simplify_gimple_switch_label_vec (gimple stmt, tree index_type)
+{
+  unsigned int branch_num = gimple_switch_num_labels (stmt);
+  VEC(tree, heap) *labels = VEC_alloc (tree, heap, branch_num);
+  unsigned int i, len;
+
+  /* Collect the existing case labels in a VEC, and preprocess it as if
+     we are gimplifying a GENERIC SWITCH_EXPR.  */
+  for (i = 1; i < branch_num; i++)
+    VEC_quick_push (tree, labels, gimple_switch_label (stmt, i));
+  preprocess_case_label_vec_for_gimple (labels, index_type, NULL);
+
+  /* If any labels were removed, replace the existing case labels
+     in the GIMPLE_SWITCH statement with the correct ones.
+     Note that the type updates were done in-place on the case labels,
+     so we only have to replace the case labels in the GIMPLE_SWITCH
+     if the number of labels changed.  */
+  len = VEC_length (tree, labels);
+  if (len < branch_num - 1)
+    {
+      bitmap target_blocks;
+      edge_iterator ei;
+      edge e;
+
+      /* Corner case: *all* case labels have been removed as being
+	 out-of-range for INDEX_TYPE.  Push one label and let the
+	 CFG cleanups deal with this further.  */
+      if (len == 0)
+	{
+	  tree label, elt;
+
+	  label = CASE_LABEL (gimple_switch_default_label (stmt));
+	  elt = build_case_label (build_int_cst (index_type, 0), NULL, label);
+	  VEC_quick_push (tree, labels, elt);
+	  len = 1;
+	}
+
+      for (i = 0; i < VEC_length (tree, labels); i++)
+	gimple_switch_set_label (stmt, i + 1, VEC_index (tree, labels, i));
+      for (i++ ; i < branch_num; i++)
+	gimple_switch_set_label (stmt, i, NULL_TREE);
+      gimple_switch_set_num_labels (stmt, len + 1);
+
+      /* Cleanup any edges that are now dead.  */
+      target_blocks = BITMAP_ALLOC (NULL);
+      for (i = 0; i < gimple_switch_num_labels (stmt); i++)
+	{
+	  tree elt = gimple_switch_label (stmt, i);
+	  basic_block target = label_to_block (CASE_LABEL (elt));
+	  bitmap_set_bit (target_blocks, target->index);
+	}
+      for (ei = ei_start (gimple_bb (stmt)->succs); (e = ei_safe_edge (ei)); )
+	{
+	  if (! bitmap_bit_p (target_blocks, e->dest->index))
+	    {
+	      remove_edge (e);
+	      cfg_changed = true;
+	      free_dominance_info (CDI_DOMINATORS);
+	    }
+	  else
+	    ei_next (&ei);
+	} 
+      BITMAP_FREE (target_blocks);
+    }
+}
+
 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
    the condition which we may be able to optimize better.  */
 
@@ -1344,9 +1414,6 @@  simplify_gimple_switch (gimple stmt)
 
 	      def = gimple_assign_rhs1 (def_stmt);
 
-	      /* ??? Why was Jeff testing this?  We are gimple...  */
-	      gcc_checking_assert (is_gimple_val (def));
-
 	      to = TREE_TYPE (cond);
 	      ti = TREE_TYPE (def);
 
@@ -1367,6 +1434,7 @@  simplify_gimple_switch (gimple stmt)
 	      if (!fail)
 		{
 		  gimple_switch_set_index (stmt, def);
+		  simplify_gimple_switch_label_vec (stmt, ti);
 		  update_stmt (stmt);
 		  return true;
 		}
Index: gimple.h
===================================================================
--- gimple.h	(revision 186962)
+++ gimple.h	(working copy)
@@ -922,6 +922,7 @@  gimple gimple_build_transaction (gimple_
 gimple gimple_build_predict (enum br_predictor, enum prediction);
 enum gimple_statement_structure_enum gss_for_assign (enum tree_code);
 void sort_case_labels (VEC(tree,heap) *);
+void preprocess_case_label_vec_for_gimple (VEC(tree,heap) *, tree, tree *);
 void gimple_set_body (tree, gimple_seq);
 gimple_seq gimple_body (tree);
 bool gimple_has_body_p (tree);
Index: testsuite/gcc.dg/pr53153.c
===================================================================
--- testsuite/gcc.dg/pr53153.c	(revision 0)
+++ testsuite/gcc.dg/pr53153.c	(revision 0)
@@ -0,0 +1,61 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+
+extern void bar (void);
+
+/* Case 181 is not in the range for 'char'.  */
+void
+foo1 (char *buf)
+{
+  int x = *buf;
+  switch (x)
+    {
+    case -76:
+    case 65:
+    case 181:
+      bar();
+    }
+}
+
+/* All cases are below the range of char.  */
+void
+foo2 (char *buf)
+{
+  int x = *buf;
+  switch (x)
+    {
+    case -150:
+    case -140:
+    case -130:
+      bar();
+    }
+}
+
+/* All cases are above the range of char.  */
+void
+foo3 (char *buf)
+{
+  int x = *buf;
+  switch (x)
+    {
+    case 130:
+    case 140:
+    case 150: /* This case is not in the range for 'char'.  */
+      bar();
+    }
+}
+
+/* The bounding cases are partially out of range for char.  */
+void
+foo4 (char *buf)
+{
+  int x = *buf;
+  switch (x)
+    {
+    case -130 ... -120:
+    case 100:
+    case 120 ... 130:
+      bar();
+    }
+}
+