re PR middle-end/53153 (ice in tree_low_cst, at tree.c:6569)

gcc/
	PR middle-end/53153
	* 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/
	PR middle-end/53153
	* gcc.dg/pr53153.c: New test.

From-SVN: r187048

6 files changed, 335 insertions, 150 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 4853959..a37a5b4 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,15 @@
+2012-05-02  Steven Bosscher  <steven@gcc.gnu.org>
+
+	PR middle-end/53153
+	* 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.
+
 2012-05-02  Richard Guenther  <rguenther@suse.de>
 
 	* fold-const.c (div_if_zero_remainder): sizetypes no longer
diff --git a/gcc/gimple.h b/gcc/gimple.h
index c3e0798..e0f8660 100644
--- a/gcc/gimple.h
+++ b/gcc/gimple.h
@@ -922,6 +922,7 @@ gimple gimple_build_transaction (gimple_seq, tree);
 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);
diff --git a/gcc/gimplify.c b/gcc/gimplify.c
index 9c58a38..c021fa1 100644
--- a/gcc/gimplify.c
+++ b/gcc/gimplify.c
@@ -1538,7 +1538,7 @@ gimplify_statement_list (tree *expr_p, gimple_seq *pre_p)
 
   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)
 {
   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.  */
+
+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;
 
-/* Gimplify a SWITCH_EXPR, and collect a TREE_VEC of the labels it can
+      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, gimple_seq *pre_p)
     {
       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, gimple_seq *pre_p)
       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);
-		    }
-		}
-	    }
+	  gimple new_default;
 
-	  if (!default_case)
-	    {
-	      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);
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 9565015..a7322f0 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2012-05-02  Steven Bosscher  <steven@gcc.gnu.org>
+
+	PR middle-end/53153
+	* gcc.dg/pr53153.c: New test.
+
 2012-05-02  Richard Guenther  <rguenther@suse.de>
 
 	* g++.dg/tree-ssa/pr19807.C: Adjust.
diff --git a/gcc/testsuite/gcc.dg/pr53153.c b/gcc/testsuite/gcc.dg/pr53153.c
new file mode 100644
index 0000000..8899e04
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr53153.c
@@ -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();
+    }
+}
+
diff --git a/gcc/tree-ssa-forwprop.c b/gcc/tree-ssa-forwprop.c
index 4739de1..d3e9f98 100644
--- a/gcc/tree-ssa-forwprop.c
+++ b/gcc/tree-ssa-forwprop.c
@@ -163,7 +163,7 @@ along with GCC; see the file COPYING3.  If not see
 
 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,78 @@ simplify_not_neg_expr (gimple_stmt_iterator *gsi_p)
   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);
+    }
+
+  VEC_free (tree, heap, labels);
+}
+
 /* 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 +1416,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 +1436,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;
 		}