expr.c (try_casesi): Remove bogus ATTRIBUTE_UNUSED markers.

gcc/
	* expr.c (try_casesi): Remove bogus ATTRIBUTE_UNUSED markers.
	* stmt.c (dump_case_nodes): New.
	(expand_case): Split out code generation parts into new functions.
	(expand_switch_as_decision_tree_p): Split out from expand_case.
	(emit_case_decision_tree): Likewise.
	(emit_case_dispatch_table): Likewise.

testsuite/
	* gcc.c-torture/compile/20000326-1.c: Fix to not optimize to empty.

From-SVN: r189285

1 files changed, 328 insertions, 231 deletions

diff --git a/gcc/stmt.c b/gcc/stmt.c
index f06becd2569..5b336e9528f 100644
--- a/gcc/stmt.c
+++ b/gcc/stmt.c
@@ -1716,6 +1716,35 @@ add_case_node (struct case_node *head, tree type, tree low, tree high,
   return r;
 }
 
+/* Dump ROOT, a list or tree of case nodes, to file.  */
+
+static void
+dump_case_nodes (FILE *f, struct case_node *root,
+		 int indent_step, int indent_level)
+{
+  HOST_WIDE_INT low, high;
+
+  if (root == 0)
+    return;
+  indent_level++;
+
+  dump_case_nodes (f, root->left, indent_step, indent_level);
+
+  low = tree_low_cst (root->low, 0);
+  high = tree_low_cst (root->high, 0);
+
+  fputs (";; ", f);
+  if (high == low)
+    fprintf(f, "%*s" HOST_WIDE_INT_PRINT_DEC,
+	    indent_step * indent_level, "", low);
+  else
+    fprintf(f, "%*s" HOST_WIDE_INT_PRINT_DEC " ... " HOST_WIDE_INT_PRINT_DEC,
+	    indent_step * indent_level, "", low, high);
+  fputs ("\n", f);
+
+  dump_case_nodes (f, root->right, indent_step, indent_level);
+}
+
 #ifndef HAVE_casesi
 #define HAVE_casesi 0
 #endif
@@ -1738,276 +1767,344 @@ case_values_threshold (void)
   return threshold;
 }
 
-/* Terminate a case (Pascal/Ada) or switch (C) statement
-   in which ORIG_INDEX is the expression to be tested.
-   If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
-   type as given in the source before any compiler conversions.
-   Generate the code to test it and jump to the right place.  */
+/* Return true if a switch should be expanded as a decision tree.
+   RANGE is the difference between highest and lowest case.
+   UNIQ is number of unique case node targets, not counting the default case.
+   COUNT is the number of comparisons needed, not counting the default case.  */
 
-void
-expand_case (gimple stmt)
+static bool
+expand_switch_as_decision_tree_p (tree range,
+				  unsigned int uniq ATTRIBUTE_UNUSED,
+				  unsigned int count)
 {
-  tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
-  rtx default_label = 0;
-  struct case_node *n;
-  unsigned int count, uniq;
-  rtx index;
-  rtx table_label;
-  int ncases;
-  rtx *labelvec;
-  int i;
-  rtx before_case, end, lab;
+  int max_ratio;
+
+  /* If neither casesi or tablejump is available, or flag_jump_tables
+     over-ruled us, we really have no choice.  */
+  if (!HAVE_casesi && !HAVE_tablejump)
+    return true;
+  if (!flag_jump_tables)
+    return true;
+
+  /* If the switch is relatively small such that the cost of one
+     indirect jump on the target are higher than the cost of a
+     decision tree, go with the decision tree.
+
+     If range of values is much bigger than number of values,
+     or if it is too large to represent in a HOST_WIDE_INT,
+     make a sequence of conditional branches instead of a dispatch.
+
+     The definition of "much bigger" depends on whether we are
+     optimizing for size or for speed.  If the former, the maximum
+     ratio range/count = 3, because this was found to be the optimal
+     ratio for size on i686-pc-linux-gnu, see PR11823.  The ratio
+     10 is much older, and was probably selected after an extensive
+     benchmarking investigation on numerous platforms.  Or maybe it
+     just made sense to someone at some point in the history of GCC,
+     who knows...  */
+  max_ratio = optimize_insn_for_size_p () ? 3 : 10;
+  if (count < case_values_threshold ()
+      || ! host_integerp (range, /*pos=*/1)
+      || compare_tree_int (range, max_ratio * count) > 0)
+    return true;
 
-  tree index_expr = gimple_switch_index (stmt);
-  tree index_type = TREE_TYPE (index_expr);
-  int unsignedp = TYPE_UNSIGNED (index_type);
+  return false;
+}
 
-  /* The insn after which the case dispatch should finally
-     be emitted.  Zero for a dummy.  */
-  rtx start;
+/* Generate a decision tree, switching on INDEX_EXPR and jumping to
+   one of the labels in CASE_LIST or to the DEFAULT_LABEL.
+   
+   We generate a binary decision tree to select the appropriate target
+   code.  This is done as follows:
 
-  /* A list of case labels; it is first built as a list and it may then
-     be rearranged into a nearly balanced binary tree.  */
-  struct case_node *case_list = 0;
+     If the index is a short or char that we do not have
+     an insn to handle comparisons directly, convert it to
+     a full integer now, rather than letting each comparison
+     generate the conversion.
+
+     Load the index into a register.
+
+     The list of cases is rearranged into a binary tree,
+     nearly optimal assuming equal probability for each case.
+
+     The tree is transformed into RTL, eliminating redundant
+     test conditions at the same time.
 
-  /* Label to jump to if no case matches.  */
-  tree default_label_decl = NULL_TREE;
+     If program flow could reach the end of the decision tree
+     an unconditional jump to the default code is emitted.
 
-  alloc_pool case_node_pool = create_alloc_pool ("struct case_node pool",
-                                                 sizeof (struct case_node),
-                                                 100);
+   The above process is unaware of the CFG.  The caller has to fix up
+   the CFG itself.  This is done in cfgexpand.c.  */     
+
+static void
+emit_case_decision_tree (tree index_expr, tree index_type,
+			 struct case_node *case_list, rtx default_label)
+{
+  rtx index = expand_normal (index_expr);
+
+  if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
+      && ! have_insn_for (COMPARE, GET_MODE (index)))
+    {
+      int unsignedp = TYPE_UNSIGNED (index_type);
+      enum machine_mode wider_mode;
+      for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
+	   wider_mode = GET_MODE_WIDER_MODE (wider_mode))
+	if (have_insn_for (COMPARE, wider_mode))
+	  {
+	    index = convert_to_mode (wider_mode, index, unsignedp);
+	    break;
+	  }
+    }
 
   do_pending_stack_adjust ();
 
-  /* An ERROR_MARK occurs for various reasons including invalid data type.  */
-  if (index_type != error_mark_node)
+  if (MEM_P (index))
     {
-      tree elt;
-      bitmap label_bitmap;
-      int stopi = 0;
+      index = copy_to_reg (index);
+      if (TREE_CODE (index_expr) == SSA_NAME)
+	set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (index_expr), index);
+    }
 
-      /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
-	 expressions being INTEGER_CST.  */
-      gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
+  balance_case_nodes (&case_list, NULL);
 
-      /* The default case, if ever taken, is the first element.  */
-      elt = gimple_switch_label (stmt, 0);
-      if (!CASE_LOW (elt) && !CASE_HIGH (elt))
-	{
-	  default_label_decl = CASE_LABEL (elt);
-	  stopi = 1;
-	}
+  /* Don't want to include tree-pass.h here.  This code will be moved
+     to a GIMPLE pass for GCC 4.9 anyway, so for now always dump.  */
+  if (dump_file && 1/*(dump_flags & TDF_DETAILS)*/)
+    {
+      int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
+      fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
+      dump_case_nodes (dump_file, case_list, indent_step, 0);
+    }
 
-      for (i = gimple_switch_num_labels (stmt) - 1; i >= stopi; --i)
-	{
-	  tree low, high;
-	  elt = gimple_switch_label (stmt, i);
-
-	  low = CASE_LOW (elt);
-	  gcc_assert (low);
-	  high = CASE_HIGH (elt);
-
-	  /* The canonical from of a case label in GIMPLE is that a simple case
-	     has an empty CASE_HIGH.  For the casesi and tablejump expanders,
-	     the back ends want simple cases to have high == low.  */
-	  gcc_assert (! high || tree_int_cst_lt (low, high));
-	  if (! high)
-	    high = low;
-
-	  case_list = add_case_node (case_list, index_type, low, high,
-                                     CASE_LABEL (elt), case_node_pool);
-	}
+  emit_case_nodes (index, case_list, default_label, index_type);
+  if (default_label)
+    emit_jump (default_label);
+}
 
+/* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to
+   one of the labels in CASE_LIST or to the DEFAULT_LABEL.
+   MINVAL, MAXVAL, and RANGE are the extrema and range of the case
+   labels in CASE_LIST.
 
-      before_case = start = get_last_insn ();
-      if (default_label_decl)
-	default_label = label_rtx (default_label_decl);
+   First, a jump insn is emitted.  First we try "casesi".  If that
+   fails, try "tablejump".   A target *must* have one of them (or both).
+
+   Then, a table with the target labels is emitted.
+
+   The process is unaware of the CFG.  The caller has to fix up
+   the CFG itself.  This is done in cfgexpand.c.  */     
+
+static void
+emit_case_dispatch_table (tree index_expr, tree index_type,
+			  struct case_node *case_list, rtx default_label,
+			  tree minval, tree maxval, tree range)
+{
+  int i, ncases;
+  struct case_node *n;
+  rtx *labelvec;
+  rtx fallback_label = label_rtx (case_list->code_label);
+  rtx table_label = gen_label_rtx ();
 
-      /* Get upper and lower bounds of case values.  */
+  if (! try_casesi (index_type, index_expr, minval, range,
+		    table_label, default_label, fallback_label))
+    {
+      bool ok;
 
-      uniq = 0;
-      count = 0;
-      label_bitmap = BITMAP_ALLOC (NULL);
-      for (n = case_list; n; n = n->right)
+      /* Index jumptables from zero for suitable values of minval to avoid
+	 a subtraction.  For the rationale see:
+	 "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html".  */
+      if (optimize_insn_for_speed_p ()
+	  && compare_tree_int (minval, 0) > 0
+	  && compare_tree_int (minval, 3) < 0)
 	{
-	  /* Count the elements and track the largest and smallest
-	     of them (treating them as signed even if they are not).  */
-	  if (count++ == 0)
-	    {
-	      minval = n->low;
-	      maxval = n->high;
-	    }
-	  else
-	    {
-	      if (tree_int_cst_lt (n->low, minval))
-		minval = n->low;
-	      if (tree_int_cst_lt (maxval, n->high))
-		maxval = n->high;
-	    }
-	  /* A range counts double, since it requires two compares.  */
-	  if (! tree_int_cst_equal (n->low, n->high))
-	    count++;
-
-	  /* If we have not seen this label yet, then increase the
-	     number of unique case node targets seen.  */
-	  lab = label_rtx (n->code_label);
-	  if (bitmap_set_bit (label_bitmap, CODE_LABEL_NUMBER (lab)))
-	    uniq++;
+	  minval = build_int_cst (index_type, 0);
+	  range = maxval;
 	}
 
-      BITMAP_FREE (label_bitmap);
-
-      /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
-	 destination, such as one with a default case only.
-	 It also removes cases that are out of range for the switch
-	 type, so we should never get a zero here.  */
-      gcc_assert (count > 0);
-
-      /* Compute span of values.  */
-      range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
-
-      /* If range of values is much bigger than number of values,
-	 make a sequence of conditional branches instead of a dispatch.
-	 If the switch-index is a constant, do it this way
-	 because we can optimize it.  */
-
-      if (count < case_values_threshold ()
-	  || compare_tree_int (range,
-			       (optimize_insn_for_size_p () ? 3 : 10) * count) > 0
-	  /* RANGE may be signed, and really large ranges will show up
-	     as negative numbers.  */
-	  || compare_tree_int (range, 0) < 0
-	  || !flag_jump_tables
-	  || TREE_CONSTANT (index_expr)
-	  /* If neither casesi or tablejump is available, we can
-	     only go this way.  */
-	  || (!HAVE_casesi && !HAVE_tablejump))
-	{
-	  index = expand_normal (index_expr);
+      ok = try_tablejump (index_type, index_expr, minval, range,
+			  table_label, default_label);
+      gcc_assert (ok);
+    }
 
-	  /* If the index is a short or char that we do not have
-	     an insn to handle comparisons directly, convert it to
-	     a full integer now, rather than letting each comparison
-	     generate the conversion.  */
+  /* Get table of labels to jump to, in order of case index.  */
 
-	  if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
-	      && ! have_insn_for (COMPARE, GET_MODE (index)))
-	    {
-	      enum machine_mode wider_mode;
-	      for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
-		   wider_mode = GET_MODE_WIDER_MODE (wider_mode))
-		if (have_insn_for (COMPARE, wider_mode))
-		  {
-		    index = convert_to_mode (wider_mode, index, unsignedp);
-		    break;
-		  }
-	    }
+  ncases = tree_low_cst (range, 0) + 1;
+  labelvec = XALLOCAVEC (rtx, ncases);
+  memset (labelvec, 0, ncases * sizeof (rtx));
 
-	  do_pending_stack_adjust ();
+  for (n = case_list; n; n = n->right)
+    {
+      /* Compute the low and high bounds relative to the minimum
+	 value since that should fit in a HOST_WIDE_INT while the
+	 actual values may not.  */
+      HOST_WIDE_INT i_low
+	= tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
+				     n->low, minval), 1);
+      HOST_WIDE_INT i_high
+	= tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
+				     n->high, minval), 1);
+      HOST_WIDE_INT i;
+
+      for (i = i_low; i <= i_high; i ++)
+	labelvec[i]
+	  = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
+    }
 
-	  if (MEM_P (index))
-	    {
-	      index = copy_to_reg (index);
-	      if (TREE_CODE (index_expr) == SSA_NAME)
-		set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (index_expr), index);
-	    }
+  /* Fill in the gaps with the default.  We may have gaps at
+     the beginning if we tried to avoid the minval subtraction,
+     so substitute some label even if the default label was
+     deemed unreachable.  */
+  if (!default_label)
+    default_label = fallback_label;
+  for (i = 0; i < ncases; i++)
+    if (labelvec[i] == 0)
+      labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
+
+  /* Output the table.  */
+  emit_label (table_label);
+
+  if (CASE_VECTOR_PC_RELATIVE || flag_pic)
+    emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
+					   gen_rtx_LABEL_REF (Pmode, table_label),
+					   gen_rtvec_v (ncases, labelvec),
+					   const0_rtx, const0_rtx));
+  else
+    emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
+				      gen_rtvec_v (ncases, labelvec)));
 
-	  /* We generate a binary decision tree to select the
-	     appropriate target code.  This is done as follows:
+  /* Record no drop-through after the table.  */
+  emit_barrier ();
+}
 
-	     The list of cases is rearranged into a binary tree,
-	     nearly optimal assuming equal probability for each case.
+/* Terminate a case (Pascal/Ada) or switch (C) statement
+   in which ORIG_INDEX is the expression to be tested.
+   If ORIG_TYPE is not NULL, it is the original ORIG_INDEX
+   type as given in the source before any compiler conversions.
+   Generate the code to test it and jump to the right place.  */
+
+void
+expand_case (gimple stmt)
+{
+  tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
+  rtx default_label = NULL_RTX;
+  unsigned int count, uniq;
+  int i, stopi = 0;
+  rtx before_case, end;
+  int ncases = gimple_switch_num_labels (stmt);
+  tree index_expr = gimple_switch_index (stmt);
+  tree index_type = TREE_TYPE (index_expr);
 
-	     The tree is transformed into RTL, eliminating
-	     redundant test conditions at the same time.
+  tree elt;
+  bitmap label_bitmap;
 
-	     If program flow could reach the end of the
-	     decision tree an unconditional jump to the
-	     default code is emitted.  */
+  /* The insn after which the case dispatch should finally
+     be emitted.  Zero for a dummy.  */
+  rtx start;
 
-	  balance_case_nodes (&case_list, NULL);
-	  emit_case_nodes (index, case_list, default_label, index_type);
-	  if (default_label)
-	    emit_jump (default_label);
-	}
-      else
-	{
-	  rtx fallback_label = label_rtx (case_list->code_label);
-	  table_label = gen_label_rtx ();
-	  if (! try_casesi (index_type, index_expr, minval, range,
-			    table_label, default_label, fallback_label))
-	    {
-	      bool ok;
+  /* A list of case labels; it is first built as a list and it may then
+     be rearranged into a nearly balanced binary tree.  */
+  struct case_node *case_list = 0;
 
-	      /* Index jumptables from zero for suitable values of
-                 minval to avoid a subtraction.  */
-	      if (optimize_insn_for_speed_p ()
-		  && compare_tree_int (minval, 0) > 0
-		  && compare_tree_int (minval, 3) < 0)
-		{
-		  minval = build_int_cst (index_type, 0);
-		  range = maxval;
-		}
+  /* A pool for case nodes.  */
+  alloc_pool case_node_pool;
 
-	      ok = try_tablejump (index_type, index_expr, minval, range,
-				  table_label, default_label);
-	      gcc_assert (ok);
-	    }
+  /* An ERROR_MARK occurs for various reasons including invalid data type.
+     ??? Can this still happen, with GIMPLE and all?  */
+  if (index_type == error_mark_node)
+    return;
 
-	  /* Get table of labels to jump to, in order of case index.  */
+  /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
+     expressions being INTEGER_CST.  */
+  gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
+  
+  case_node_pool = create_alloc_pool ("struct case_node pool",
+				      sizeof (struct case_node),
+				      100);
 
-	  ncases = tree_low_cst (range, 0) + 1;
-	  labelvec = XALLOCAVEC (rtx, ncases);
-	  memset (labelvec, 0, ncases * sizeof (rtx));
+  do_pending_stack_adjust ();
 
-	  for (n = case_list; n; n = n->right)
-	    {
-	      /* Compute the low and high bounds relative to the minimum
-		 value since that should fit in a HOST_WIDE_INT while the
-		 actual values may not.  */
-	      HOST_WIDE_INT i_low
-		= tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
-					     n->low, minval), 1);
-	      HOST_WIDE_INT i_high
-		= tree_low_cst (fold_build2 (MINUS_EXPR, index_type,
-					     n->high, minval), 1);
-	      HOST_WIDE_INT i;
-
-	      for (i = i_low; i <= i_high; i ++)
-		labelvec[i]
-		  = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
-	    }
+  /* The default case, if ever taken, is the first element.  */
+  elt = gimple_switch_label (stmt, 0);
+  if (!CASE_LOW (elt) && !CASE_HIGH (elt))
+    {
+      default_label = label_rtx (CASE_LABEL (elt));
+      stopi = 1;
+    }
 
-	  /* Fill in the gaps with the default.  We may have gaps at
-	     the beginning if we tried to avoid the minval subtraction,
-	     so substitute some label even if the default label was
-	     deemed unreachable.  */
-	  if (!default_label)
-	    default_label = fallback_label;
-	  for (i = 0; i < ncases; i++)
-	    if (labelvec[i] == 0)
-	      labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
-
-	  /* Output the table.  */
-	  emit_label (table_label);
-
-	  if (CASE_VECTOR_PC_RELATIVE || flag_pic)
-	    emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
-						   gen_rtx_LABEL_REF (Pmode, table_label),
-						   gen_rtvec_v (ncases, labelvec),
-						   const0_rtx, const0_rtx));
-	  else
-	    emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
-					      gen_rtvec_v (ncases, labelvec)));
+  /* Get upper and lower bounds of case values.  */
+  elt = gimple_switch_label (stmt, stopi);
+  minval = fold_convert (index_type, CASE_LOW (elt));
+  elt = gimple_switch_label (stmt, ncases - 1);
+  if (CASE_HIGH (elt))
+    maxval = fold_convert (index_type, CASE_HIGH (elt));
+  else
+    maxval = fold_convert (index_type, CASE_LOW (elt));
 
-	  /* Record no drop-through after the table.  */
-	  emit_barrier ();
-	}
+  /* Compute span of values.  */
+  range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
 
-      before_case = NEXT_INSN (before_case);
-      end = get_last_insn ();
-      reorder_insns (before_case, end, start);
+  /* Listify the labels queue and gather some numbers to decide
+     how to expand this switch().  */
+  uniq = 0;
+  count = 0;
+  label_bitmap = BITMAP_ALLOC (NULL);
+  for (i = gimple_switch_num_labels (stmt) - 1; i >= stopi; --i)
+    {
+      tree low, high;
+      rtx lab;
+
+      elt = gimple_switch_label (stmt, i);
+      low = CASE_LOW (elt);
+      gcc_assert (low);
+      high = CASE_HIGH (elt);
+      gcc_assert (! high || tree_int_cst_lt (low, high));
+
+      /* Count the elements.
+	 A range counts double, since it requires two compares.  */
+      count++;
+      if (high)
+	count++;
+
+      /* If we have not seen this label yet, then increase the
+	 number of unique case node targets seen.  */
+      lab = label_rtx (CASE_LABEL (elt));
+      if (bitmap_set_bit (label_bitmap, CODE_LABEL_NUMBER (lab)))
+	uniq++;
+
+      /* The canonical from of a case label in GIMPLE is that a simple case
+	 has an empty CASE_HIGH.  For the casesi and tablejump expanders,
+	 the back ends want simple cases to have high == low.  */
+      if (! high)
+	high = low;
+
+      case_list = add_case_node (case_list, index_type, low, high,
+				 CASE_LABEL (elt), case_node_pool);
     }
+  BITMAP_FREE (label_bitmap);
+
+  /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
+     destination, such as one with a default case only.
+     It also removes cases that are out of range for the switch
+     type, so we should never get a zero here.  */
+  gcc_assert (count > 0);
+
+  before_case = start = get_last_insn ();
+
+  /* Decide how to expand this switch.
+     The two options at this point are a dispatch table (casesi or
+     tablejump) or a decision tree.  */
+
+  if (expand_switch_as_decision_tree_p (range, uniq, count))
+    emit_case_decision_tree (index_expr, index_type,
+			     case_list, default_label);
+  else
+    emit_case_dispatch_table (index_expr, index_type,
+			      case_list, default_label,
+			      minval, maxval, range);
+
+  before_case = NEXT_INSN (before_case);
+  end = get_last_insn ();
+  reorder_insns (before_case, end, start);
 
   free_temp_slots ();
   free_alloc_pool (case_node_pool);