* c-common.h (check_case_value): Remove prototype.

        (c_add_case_label): Adjust prototype.
        * c-common.c (check_case_value): Make static.
        (check_case_bounds): New function.
        (c_add_case_label): Use it.  Take new argument orig_type.
        * c-typeck.c (struct c_switch): New orig_type field.
        (c_start_case): Set it.
        (do_case): Pass it to c_add_case_label.
        * expr.c (expand_expr_real_1): Don't warn for out-of-bounds
        cases from here.  Add the labels in reverse order.
        * stmt.c (struct case_node): Adjust comment.  Remove balance field.
        (add_case_node): Return nothing, don't check for duplicate cases.
        Insert new case nodes in a list, not in an AVL tree.
        (expand_end_case_type): Don't turn a case tree into a case list.
        (case_tree2list): Remove.
        * tree.h (add_case_node): Adjust prototype.

cp/
        * cp-tree.h (struct lang_decl_flags): Unify the template_info and
        thunk_alias, and the access and virtual_offset fields.
        (THUNK_VIRTUAL_OFFSET, THUNK_ALIAS): Adjust.
        * decl.c (finish_case_label): Update c_add_case_node call.

testsuite/
	* testsuite/gcc.dg/switch-warn-1.c: New test.
	* testsuite/gcc.dg/switch-warn-2.c: New test.
        * gcc.c-torture/compile/pr14730.c: Update


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@84947 138bc75d-0d04-0410-961f-82ee72b054a4

14 files changed, 241 insertions, 331 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index b609a50fce5..fae5ace8b40 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,22 @@
+2004-07-20  Steven Bosscher  <stevenb@suse.de>
+
+	* c-common.h (check_case_value): Remove prototype.
+	(c_add_case_label): Adjust prototype.
+	* c-common.c (check_case_value): Make static.
+	(check_case_bounds): New function.
+	(c_add_case_label): Use it.  Take new argument orig_type.
+	* c-typeck.c (struct c_switch): New orig_type field.
+	(c_start_case): Set it.
+	(do_case): Pass it to c_add_case_label.
+	* expr.c (expand_expr_real_1): Don't warn for out-of-bounds
+	cases from here.  Add the labels in reverse order.
+	* stmt.c (struct case_node): Adjust comment.  Remove balance field.
+	(add_case_node): Return nothing, don't check for duplicate cases.
+	Insert new case nodes in a list, not in an AVL tree.
+	(expand_end_case_type): Don't turn a case tree into a case list.
+	(case_tree2list): Remove.
+	* tree.h (add_case_node): Adjust prototype.
+
 2004-07-19  Paolo Bonzini  <bonzini@gnu.org>
 
 	* genattr.c (struct range, struct function_unit,
diff --git a/gcc/c-common.c b/gcc/c-common.c
index 1966b0da236..093e839b5c8 100644
--- a/gcc/c-common.c
+++ b/gcc/c-common.c
@@ -510,6 +510,8 @@ const struct fname_var_t fname_vars[] =
 };
 
 static int constant_fits_type_p (tree, tree);
+static tree check_case_value (tree);
+static bool check_case_bounds (tree, tree, tree *, tree *);
 
 static tree handle_packed_attribute (tree *, tree, tree, int, bool *);
 static tree handle_nocommon_attribute (tree *, tree, tree, int, bool *);
@@ -1400,7 +1402,7 @@ verify_sequence_points (tree expr)
 
 /* Validate the expression after `case' and apply default promotions.  */
 
-tree
+static tree
 check_case_value (tree value)
 {
   if (value == NULL_TREE)
@@ -1436,6 +1438,75 @@ check_case_value (tree value)
   return value;
 }
 
+/* See if the case values LOW and HIGH are in the range of the original
+   type (ie. before the default conversion to int) of the switch testing
+   expression.
+   TYPE is the promoted type of the testing expression, and ORIG_TYPE is
+   the type before promiting it.  CASE_LOW_P is a pointer to the lower
+   bound of the case label, and CASE_HIGH_P is the upper bound or NULL
+   if the case is not a case range.
+   The caller has to make sure that we are not called with NULL for
+   CASE_LOW_P (ie. the defualt case).
+   Returns true if the case label is in range of ORIG_TYPE (satured or
+   untouched) or false if the label is out of range.  */
+
+static bool
+check_case_bounds (tree type, tree orig_type,
+		   tree *case_low_p, tree *case_high_p)
+{
+  tree min_value, max_value;
+  tree case_low = *case_low_p;
+  tree case_high = case_high_p ? *case_high_p : case_low;
+
+  /* If there was a problem with the original type, do nothing.  */
+  if (orig_type == error_mark_node)
+    return true;
+
+  min_value = TYPE_MIN_VALUE (orig_type);
+  max_value = TYPE_MAX_VALUE (orig_type);
+
+  /* Case label is less than minimum for type.  */
+  if (tree_int_cst_compare (case_low, min_value) < 0
+      && tree_int_cst_compare (case_high, min_value) < 0)
+    {
+      warning ("case label value is less than minimum value for type");
+      return false;
+    }
+ 
+  /* Case value is greater than maximum for type.  */
+  if (tree_int_cst_compare (case_low, max_value) > 0
+      && tree_int_cst_compare (case_high, max_value) > 0)
+    {
+      warning ("case label value exceeds maximum value for type");
+      return false;
+    }
+
+  /* Saturate lower case label value to minimum.  */
+  if (tree_int_cst_compare (case_high, min_value) >= 0
+      && tree_int_cst_compare (case_low, min_value) < 0)
+    {
+      warning ("lower value in case label range"
+	       " less than minimum value for type");
+      case_low = min_value;
+    }
+ 
+  /* Saturate upper case label value to maximum.  */
+  if (tree_int_cst_compare (case_low, max_value) <= 0
+      && tree_int_cst_compare (case_high, max_value) > 0)
+    {
+      warning ("upper value in case label range"
+	       " exceeds maximum value for type");
+      case_high = max_value;
+    }
+
+  if (*case_low_p != case_low)
+    *case_low_p = convert (type, case_low);
+  if (case_high_p && *case_high_p != case_high)
+    *case_high_p = convert (type, case_high);
+
+  return true;
+}
+
 /* Return an integer type with BITS bits of precision,
    that is unsigned if UNSIGNEDP is nonzero, otherwise signed.  */
 
@@ -3402,8 +3473,8 @@ case_compare (splay_tree_key k1, splay_tree_key k2)
    ERROR_MARK_NODE if no CASE_LABEL_EXPR is created.  */
 
 tree
-c_add_case_label (splay_tree cases, tree cond, tree low_value,
-		  tree high_value)
+c_add_case_label (splay_tree cases, tree cond, tree orig_type,
+		  tree low_value, tree high_value)
 {
   tree type;
   tree label;
@@ -3453,6 +3524,14 @@ c_add_case_label (splay_tree cases, tree cond, tree low_value,
       && !tree_int_cst_lt (low_value, high_value))
     warning ("empty range specified");
 
+  /* See if the case is in range of the type of the original testing
+     expression.  If both low_value and high_value are out of range,
+     don't insert the case label and return NULL_TREE.  */
+  if (low_value
+      && ! check_case_bounds (type, orig_type,
+			      &low_value, high_value ? &high_value : NULL))
+    return NULL_TREE;
+
   /* Look up the LOW_VALUE in the table of case labels we already
      have.  */
   node = splay_tree_lookup (cases, (splay_tree_key) low_value);
diff --git a/gcc/c-common.h b/gcc/c-common.h
index 89fc7eed098..8529acec8f6 100644
--- a/gcc/c-common.h
+++ b/gcc/c-common.h
@@ -644,8 +644,6 @@ extern void binary_op_error (enum tree_code);
 #define my_friendly_assert(EXP, N) (void) \
  (((EXP) == 0) ? (fancy_abort (__FILE__, __LINE__, __FUNCTION__), 0) : 0)
 
-/* Validate the expression after `case' and apply default promotions.  */
-extern tree check_case_value (tree);
 extern tree fix_string_type (tree);
 struct varray_head_tag;
 extern void constant_expression_warning (tree);
@@ -818,7 +816,7 @@ extern void extract_interface_info (void);
 
 extern int case_compare (splay_tree_key, splay_tree_key);
 
-extern tree c_add_case_label (splay_tree, tree, tree, tree);
+extern tree c_add_case_label (splay_tree, tree, tree, tree, tree);
 
 extern void c_do_switch_warnings (splay_tree, tree);
 
diff --git a/gcc/c-typeck.c b/gcc/c-typeck.c
index 29a9ec3abad..82b0108bee3 100644
--- a/gcc/c-typeck.c
+++ b/gcc/c-typeck.c
@@ -6270,12 +6270,18 @@ c_finish_return (tree retval)
 struct c_switch {
   /* The SWITCH_STMT being built.  */
   tree switch_stmt;
+
+  /* The original type of the testing expression, ie. before the
+     default conversion is applied.  */
+  tree orig_type;
+
   /* A splay-tree mapping the low element of a case range to the high
      element, or NULL_TREE if there is no high element.  Used to
      determine whether or not a new case label duplicates an old case
      label.  We need a tree, rather than simply a hash table, because
      of the GNU case range extension.  */
   splay_tree cases;
+
   /* The next node on the stack.  */
   struct c_switch *next;
 };
@@ -6326,6 +6332,7 @@ c_start_case (tree exp)
   /* Add this new SWITCH_STMT to the stack.  */
   cs = xmalloc (sizeof (*cs));
   cs->switch_stmt = build_stmt (SWITCH_STMT, exp, NULL_TREE, orig_type);
+  cs->orig_type = orig_type;
   cs->cases = splay_tree_new (case_compare, NULL, NULL);
   cs->next = c_switch_stack;
   c_switch_stack = cs;
@@ -6344,6 +6351,7 @@ do_case (tree low_value, tree high_value)
     {
       label = c_add_case_label (c_switch_stack->cases,
 				SWITCH_COND (c_switch_stack->switch_stmt),
+				c_switch_stack->orig_type,
 				low_value, high_value);
       if (label == error_mark_node)
 	label = NULL_TREE;
diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog
index 27e45ee9440..0a038fc88dd 100644
--- a/gcc/cp/ChangeLog
+++ b/gcc/cp/ChangeLog
@@ -1,3 +1,10 @@
+2004-07-20  Steven Bosscher  <stevenb@suse.de>
+
+	* cp-tree.h (struct lang_decl_flags): Unify the template_info and
+	thunk_alias, and the access and virtual_offset fields.
+	(THUNK_VIRTUAL_OFFSET, THUNK_ALIAS): Adjust.
+	* decl.c (finish_case_label): Update c_add_case_node call.
+
 2004-07-19  Mark Mitchell  <mark@codesourcery.com>
 
 	Revert patch for PR c++/16623.
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index ca7eae30f3b..4b717de85f9 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -1544,29 +1544,25 @@ struct lang_decl_flags GTY(())
   unsigned this_thunk_p : 1;
 
   union lang_decl_u {
-    /* In a FUNCTION_DECL for which DECL_THUNK_P does not hold,
+    /* In a FUNCTION_DECL for which DECL_THUNK_P holds, this is
+       THUNK_ALIAS.
+       In a FUNCTION_DECL for which DECL_THUNK_P does not hold,
        VAR_DECL, TYPE_DECL, or TEMPLATE_DECL, this is
        DECL_TEMPLATE_INFO.  */
     tree GTY ((tag ("0"))) template_info;
 
     /* In a NAMESPACE_DECL, this is NAMESPACE_LEVEL.  */
     struct cp_binding_level * GTY ((tag ("1"))) level;
-
-    /* In a FUNCTION_DECL for which DECL_THUNK_P holds, this is
-       THUNK_ALIAS.  */
-    tree GTY ((tag ("2"))) thunk_alias;
   } GTY ((desc ("%1.u1sel"))) u;
 
   union lang_decl_u2 {
-    /* This is DECL_ACCESS.  */
+    /* In a FUNCTION_DECL for which DECL_THUNK_P holds, this is
+       THUNK_VIRTUAL_OFFSET.
+       Otherwise this is DECL_ACCESS.  */
     tree GTY ((tag ("0"))) access;
 
     /* For VAR_DECL in function, this is DECL_DISCRIMINATOR.  */
     int GTY ((tag ("1"))) discriminator;
-
-    /* In a FUNCTION_DECL for which DECL_THUNK_P holds, this is
-       THUNK_VIRTUAL_OFFSET.  */
-    tree GTY((tag ("2"))) virtual_offset;
   } GTY ((desc ("%1.u2sel"))) u2;
 };
 
@@ -2827,11 +2823,11 @@ struct lang_decl GTY(())
    binfos.)  */
 
 #define THUNK_VIRTUAL_OFFSET(DECL) \
-  (LANG_DECL_U2_CHECK (FUNCTION_DECL_CHECK (DECL), 0)->virtual_offset)
+  (LANG_DECL_U2_CHECK (FUNCTION_DECL_CHECK (DECL), 0)->access)
 
 /* A thunk which is equivalent to another thunk.  */
 #define THUNK_ALIAS(DECL) \
-  (DECL_LANG_SPECIFIC (FUNCTION_DECL_CHECK (DECL))->decl_flags.u.thunk_alias)
+  (DECL_LANG_SPECIFIC (FUNCTION_DECL_CHECK (DECL))->decl_flags.u.template_info)
 
 /* For thunk NODE, this is the FUNCTION_DECL thunked to.  */
 #define THUNK_TARGET(NODE)				\
diff --git a/gcc/cp/decl.c b/gcc/cp/decl.c
index 874cfcba150..2d4fa895b50 100644
--- a/gcc/cp/decl.c
+++ b/gcc/cp/decl.c
@@ -2444,7 +2444,8 @@ finish_case_label (tree low_value, tree high_value)
   if (cond && TREE_CODE (cond) == TREE_LIST)
     cond = TREE_VALUE (cond);
 
-  r = c_add_case_label (switch_stack->cases, cond, low_value, high_value);
+  r = c_add_case_label (switch_stack->cases, cond, TREE_TYPE (cond),
+			low_value, high_value);
 
   check_switch_goto (switch_stack->level);
 
diff --git a/gcc/expr.c b/gcc/expr.c
index 2ca28db596f..858a7ff2400 100644
--- a/gcc/expr.c
+++ b/gcc/expr.c
@@ -8569,67 +8569,19 @@ expand_expr_real_1 (tree exp, rtx target, enum machine_mode tmode,
         abort ();
       if (SWITCH_LABELS (exp))
 	{
-	  tree duplicate = 0;
 	  tree vec = SWITCH_LABELS (exp);
-	  size_t i, n = TREE_VEC_LENGTH (vec);
+	  size_t i = TREE_VEC_LENGTH (vec);
 
-	  for (i = 0; i < n; ++i)
+	  do
 	    {
-	      tree elt = TREE_VEC_ELT (vec, i);
-	      tree controlling_expr_type = TREE_TYPE (SWITCH_COND (exp));
-	      tree min_value = TYPE_MIN_VALUE (controlling_expr_type);
-	      tree max_value = TYPE_MAX_VALUE (controlling_expr_type);
-	      
-	      tree case_low = CASE_LOW (elt);
-	      tree case_high = CASE_HIGH (elt) ? CASE_HIGH (elt) : case_low;
-	      if (case_low && case_high)
-		{
-		  /* Case label is less than minimum for type.  */
-		  if (TREE_CODE (min_value) == INTEGER_CST
-		      && tree_int_cst_compare (case_low, min_value) < 0
-		      && tree_int_cst_compare (case_high, min_value) < 0)
-		    {
-		      warning ("case label value %d is less than minimum value for type",
-			       TREE_INT_CST (case_low));
-		      continue;
-		    }
-		  
-		  /* Case value is greater than maximum for type.  */
-		  if (TREE_CODE (max_value) == INTEGER_CST
-		      && tree_int_cst_compare (case_low, max_value) > 0
-		      && tree_int_cst_compare (case_high, max_value) > 0)
-		    {
-		      warning ("case label value %d exceeds maximum value for type",
-			       TREE_INT_CST (case_high));
-		      continue;
-		    }
-		  
-		  /* Saturate lower case label value to minimum.  */
-		  if (TREE_CODE (min_value) == INTEGER_CST
-		      && tree_int_cst_compare (case_high, min_value) >= 0
-		      && tree_int_cst_compare (case_low, min_value) < 0)
-		    {
-		      warning ("lower value %d in case label range less than minimum value for type",
-			       TREE_INT_CST (case_low));
-		      case_low = min_value;
-		    }
-		  
-		  /* Saturate upper case label value to maximum.  */
-		  if (TREE_CODE (max_value) == INTEGER_CST
-		      && tree_int_cst_compare (case_low, max_value) <= 0
-		      && tree_int_cst_compare (case_high, max_value) > 0)
-		    {
-		      warning ("upper value %d in case label range exceeds maximum value for type",
-			       TREE_INT_CST (case_high));
-		      case_high = max_value;
-		    }
-		}
-	      
-	      add_case_node (case_low, case_high, CASE_LABEL (elt), &duplicate);
-	      if (duplicate)
-		abort ();
+	      tree elt = TREE_VEC_ELT (vec, --i);
+	      add_case_node (CASE_LOW (elt), CASE_HIGH (elt),
+			     CASE_LABEL (elt));
 	    }
+	  while (i);
 	}
+      else
+	abort ();
       expand_end_case_type (SWITCH_COND (exp), TREE_TYPE (exp));
       return const0_rtx;
 
diff --git a/gcc/stmt.c b/gcc/stmt.c
index 6f7382d3df8..6d3043b3869 100644
--- a/gcc/stmt.c
+++ b/gcc/stmt.c
@@ -66,12 +66,14 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
    statements.  We handle "range" labels; for a single-value label
    as in C, the high and low limits are the same.
 
-   An AVL tree of case nodes is initially created, and later transformed
-   to a list linked via the RIGHT fields in the nodes.  Nodes with
-   higher case values are later in the list.
-
-   Switch statements can be output in one of two forms.  A branch table
-   is used if there are more than a few labels and the labels are dense
+   We start with a vector of case nodes sorted in ascending order, and
+   the default label as the last element in the vector.  Before expanding
+   to RTL, we transform this vector into a list linked via the RIGHT
+   fields in the case_node struct.  Nodes with higher case values are
+   later in the list.
+
+   Switch statements can be output in three forms.  A branch table is
+   used if there are more than a few labels and the labels are dense
    within the range between the smallest and largest case value.  If a
    branch table is used, no further manipulations are done with the case
    node chain.
@@ -82,7 +84,10 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
    totally unbalanced, with everything on the right.  We balance the tree
    with nodes on the left having lower case values than the parent
    and nodes on the right having higher values.  We then output the tree
-   in order.  */
+   in order.
+
+   For very small, suitable switch statements, we can generate a series
+   of simple bit test and branches instead.  */
 
 struct case_node GTY(())
 {
@@ -92,7 +97,6 @@ struct case_node GTY(())
   tree			low;	/* Lowest index value for this label */
   tree			high;	/* Highest index value for this label */
   tree			code_label; /* Label to jump to when node matches */
-  int			balance;
 };
 
 typedef struct case_node case_node;
@@ -274,7 +278,6 @@ static int node_has_low_bound (case_node_ptr, tree);
 static int node_has_high_bound (case_node_ptr, tree);
 static int node_is_bounded (case_node_ptr, tree);
 static void emit_case_nodes (rtx, case_node_ptr, rtx, tree);
-static struct case_node *case_tree2list (case_node *, case_node *);
 
 void
 init_stmt_for_function (void)
@@ -2727,241 +2730,42 @@ expand_start_case (tree index_expr)
 }
 
 /* Do the insertion of a case label into
-   case_stack->data.case_stmt.case_list.  Use an AVL tree to avoid
-   slowdown for large switch statements.  */
+   case_stack->data.case_stmt.case_list.  The labels are fed to us
+   in descending order from the sorted vector of case labels used
+   in the tree part of the middle end.  So the list we construct is
+   sorted in ascending order.  */
 
-int
-add_case_node (tree low, tree high, tree label, tree *duplicate)
+void
+add_case_node (tree low, tree high, tree label)
 {
-  struct case_node *p, **q, *r;
+  struct case_node *r;
 
   /* If there's no HIGH value, then this is not a case range; it's
      just a simple case label.  But that's just a degenerate case
-     range.  */
-  if (!high)
+     range.
+     If the bounds are equal, turn this into the one-value case.  */
+  if (!high || tree_int_cst_equal (low, high))
     high = low;
 
   /* Handle default labels specially.  */
   if (!high && !low)
     {
+#ifdef ENABLE_CHECKING
       if (case_stack->data.case_stmt.default_label != 0)
-	{
-	  *duplicate = case_stack->data.case_stmt.default_label;
-	  return 2;
-	}
+	abort ();
+#endif
       case_stack->data.case_stmt.default_label = label;
-      return 0;
-    }
-
-  q = &case_stack->data.case_stmt.case_list;
-  p = *q;
-
-  while ((r = *q))
-    {
-      p = r;
-
-      /* Keep going past elements distinctly greater than HIGH.  */
-      if (tree_int_cst_lt (high, p->low))
-	q = &p->left;
-
-      /* or distinctly less than LOW.  */
-      else if (tree_int_cst_lt (p->high, low))
-	q = &p->right;
-
-      else
-	{
-	  /* We have an overlap; this is an error.  */
-	  *duplicate = p->code_label;
-	  return 2;
-	}
+      return;
     }
 
-  /* Add this label to the chain, and succeed.  */
-
+  /* Add this label to the chain.  */
   r = ggc_alloc (sizeof (struct case_node));
   r->low = low;
-
-  /* If the bounds are equal, turn this into the one-value case.  */
-  if (tree_int_cst_equal (low, high))
-    r->high = r->low;
-  else
-    r->high = high;
-
+  r->high = high;
   r->code_label = label;
-
-  *q = r;
-  r->parent = p;
-  r->left = 0;
-  r->right = 0;
-  r->balance = 0;
-
-  while (p)
-    {
-      struct case_node *s;
-
-      if (r == p->left)
-	{
-	  int b;
-
-	  if (! (b = p->balance))
-	    /* Growth propagation from left side.  */
-	    p->balance = -1;
-	  else if (b < 0)
-	    {
-	      if (r->balance < 0)
-		{
-		  /* R-Rotation */
-		  if ((p->left = s = r->right))
-		    s->parent = p;
-
-		  r->right = p;
-		  p->balance = 0;
-		  r->balance = 0;
-		  s = p->parent;
-		  p->parent = r;
-
-		  if ((r->parent = s))
-		    {
-		      if (s->left == p)
-			s->left = r;
-		      else
-			s->right = r;
-		    }
-		  else
-		    case_stack->data.case_stmt.case_list = r;
-		}
-	      else
-		/* r->balance == +1 */
-		{
-		  /* LR-Rotation */
-
-		  int b2;
-		  struct case_node *t = r->right;
-
-		  if ((p->left = s = t->right))
-		    s->parent = p;
-
-		  t->right = p;
-		  if ((r->right = s = t->left))
-		    s->parent = r;
-
-		  t->left = r;
-		  b = t->balance;
-		  b2 = b < 0;
-		  p->balance = b2;
-		  b2 = -b2 - b;
-		  r->balance = b2;
-		  t->balance = 0;
-		  s = p->parent;
-		  p->parent = t;
-		  r->parent = t;
-
-		  if ((t->parent = s))
-		    {
-		      if (s->left == p)
-			s->left = t;
-		      else
-			s->right = t;
-		    }
-		  else
-		    case_stack->data.case_stmt.case_list = t;
-		}
-	      break;
-	    }
-
-	  else
-	    {
-	      /* p->balance == +1; growth of left side balances the node.  */
-	      p->balance = 0;
-	      break;
-	    }
-	}
-      else
-	/* r == p->right */
-	{
-	  int b;
-
-	  if (! (b = p->balance))
-	    /* Growth propagation from right side.  */
-	    p->balance++;
-	  else if (b > 0)
-	    {
-	      if (r->balance > 0)
-		{
-		  /* L-Rotation */
-
-		  if ((p->right = s = r->left))
-		    s->parent = p;
-
-		  r->left = p;
-		  p->balance = 0;
-		  r->balance = 0;
-		  s = p->parent;
-		  p->parent = r;
-		  if ((r->parent = s))
-		    {
-		      if (s->left == p)
-			s->left = r;
-		      else
-			s->right = r;
-		    }
-
-		  else
-		    case_stack->data.case_stmt.case_list = r;
-		}
-
-	      else
-		/* r->balance == -1 */
-		{
-		  /* RL-Rotation */
-		  int b2;
-		  struct case_node *t = r->left;
-
-		  if ((p->right = s = t->left))
-		    s->parent = p;
-
-		  t->left = p;
-
-		  if ((r->left = s = t->right))
-		    s->parent = r;
-
-		  t->right = r;
-		  b = t->balance;
-		  b2 = b < 0;
-		  r->balance = b2;
-		  b2 = -b2 - b;
-		  p->balance = b2;
-		  t->balance = 0;
-		  s = p->parent;
-		  p->parent = t;
-		  r->parent = t;
-
-		  if ((t->parent = s))
-		    {
-		      if (s->left == p)
-			s->left = t;
-		      else
-			s->right = t;
-		    }
-
-		  else
-		    case_stack->data.case_stmt.case_list = t;
-		}
-	      break;
-	    }
-	  else
-	    {
-	      /* p->balance == -1; growth of right side balances the node.  */
-	      p->balance = 0;
-	      break;
-	    }
-	}
-
-      r = p;
-      p = p->parent;
-    }
-
-  return 0;
+  r->parent = r->left = NULL;
+  r->right = case_stack->data.case_stmt.case_list;
+  case_stack->data.case_stmt.case_list = r;
 }
 
 /* Maximum number of case bit tests.  */
@@ -3174,11 +2978,6 @@ expand_end_case_type (tree orig_index, tree orig_type)
 
       before_case = get_last_insn ();
 
-      if (thiscase->data.case_stmt.case_list
-	  && thiscase->data.case_stmt.case_list->left)
-	thiscase->data.case_stmt.case_list
-	  = case_tree2list (thiscase->data.case_stmt.case_list, 0);
-
       /* Get upper and lower bounds of case values.
 	 Also convert all the case values to the index expr's data type.  */
 
@@ -3446,28 +3245,6 @@ expand_end_case_type (tree orig_index, tree orig_type)
   free_temp_slots ();
 }
 
-/* Convert the tree NODE into a list linked by the right field, with the left
-   field zeroed.  RIGHT is used for recursion; it is a list to be placed
-   rightmost in the resulting list.  */
-
-static struct case_node *
-case_tree2list (struct case_node *node, struct case_node *right)
-{
-  struct case_node *left;
-
-  if (node->right)
-    right = case_tree2list (node->right, right);
-
-  node->right = right;
-  if ((left = node->left))
-    {
-      node->left = 0;
-      return case_tree2list (left, node);
-    }
-
-  return node;
-}
-
 /* Generate code to jump to LABEL if OP1 and OP2 are equal.  */
 
 static void
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index caadf495fed..51c125813d8 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,9 @@
+2004-07-20  Steven Bosscher  <stevenb@suse.de>
+
+	* testsuite/gcc.dg/switch-warn-1.c: New test.
+	* testsuite/gcc.dg/switch-warn-2.c: New test.
+	* gcc.c-torture/compile/pr14730.c: Update.
+
 2004-07-19  Kelley Cook  <kcook@gcc.gnu.org>
 
 	* g++.dg/lookup/java1.C, g++.dg/lookup/java2.C, g++.dg/other/crash-2.C,
diff --git a/gcc/testsuite/gcc.c-torture/compile/pr14730.c b/gcc/testsuite/gcc.c-torture/compile/pr14730.c
index b4f36a9ae3c..6f08ab4658f 100644
--- a/gcc/testsuite/gcc.c-torture/compile/pr14730.c
+++ b/gcc/testsuite/gcc.c-torture/compile/pr14730.c
@@ -12,5 +12,5 @@ int t (char i)
     case 256:
       return 0;
     }
-  return 0;
+  return 1;
 }
diff --git a/gcc/testsuite/gcc.dg/switch-warn-1.c b/gcc/testsuite/gcc.dg/switch-warn-1.c
new file mode 100644
index 00000000000..d98bfa892d6
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/switch-warn-1.c
@@ -0,0 +1,44 @@
+/* { dg-do run } */
+/* { dg-options "-O0" } */
+
+/* Check that out-of-bounds case warnings work in the case that the
+   testing expression is promoted.  */
+int
+foo1 (unsigned char i)
+{
+  switch (i)
+    {
+    case -1:   /* { dg-warning "case label value is less than minimum value for type" } */
+      return 1;
+    case 256:  /* { dg-warning "case label value exceeds maximum value for type" } */
+      return 2;
+    default:
+      return 3;
+    }
+}
+
+/* Like above, but for case ranges that need to be satured.  */
+int
+foo2 (unsigned char i)
+{
+  switch (i)
+    {
+    case -1 ... 1:   /* { dg-warning "lower value in case label range less than minimum value for type" } */
+      return 1;
+    case 254 ... 256:  /* { dg-warning "upper value in case label range exceeds maximum value for type" } */
+      return 2;
+    default:
+      return 3;
+    }
+}
+
+int
+main (void)
+{
+  if (foo1 (10) != 3)
+    abort ();
+  if (foo2 (10) != 3)
+    abort ();
+  exit (0);
+}
+
diff --git a/gcc/testsuite/gcc.dg/switch-warn-2.c b/gcc/testsuite/gcc.dg/switch-warn-2.c
new file mode 100644
index 00000000000..ab742669163
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/switch-warn-2.c
@@ -0,0 +1,23 @@
+/* This should not warn about the case label being out of range.  */
+/* { dg-do run } */
+/* { dg-options "-O0" } */
+
+int
+foo (unsigned int i)
+{
+  switch (i)
+  {
+    case 123456123456ULL: /* { dg-warning "large integer implicitly truncated to unsigned type" } */
+      return 0;
+    default:
+      return 3;
+  }
+}
+
+int
+main (void)
+{
+  if (foo (10) != 3)
+    abort ();
+  exit (0);
+}
diff --git a/gcc/tree.h b/gcc/tree.h
index 9871387c7e3..f37c7a355da 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -3361,7 +3361,7 @@ extern struct nesting * current_nesting_level (void);
 extern void expand_start_case (tree);
 extern void expand_end_case_type (tree, tree);
 #define expand_end_case(cond) expand_end_case_type (cond, NULL)
-extern int add_case_node (tree, tree, tree, tree *);
+extern void add_case_node (tree, tree, tree);
 
 /* In tree-eh.c */
 extern void using_eh_for_cleanups (void);