[PATCH, middle-end] Switch initializations conversion (take four)

[PATCH, middle-end] Switch initializations conversion (take four)

[Martin Jambor]

Hi,

since we are again in stage 1, I am re-submitting an improved the pass
converting constant assignments in switch statements into assignments
from a static array. 

My previous attempt is here:
http://gcc.gnu.org/ml/gcc-patches/2007-09/msg00972.html

Most of the changes have been inspired by Richard Henderson's mail
available here:
http://gcc.gnu.org/ml/gcc-patches/2007-10/msg01470.html

There are  many small improvements, usually  I replaced some  of my own
helper functions  with those  already present in  gcc. In  addition to
that there are some other bigger changes:

1. There  is only one parameter  driving the optimization  and that is
   the  required density  of  a  case statement  (i.e.   the ratio  in
   between the number of non-default slots in the array to the size of
   the range covered by the switch statement).

2. I  make use of the  switch tree properties Richard  revealed to me,
   saving some extra checking and case traversing.

3. The pass no longer requires that there are no incoming edges to the
   last BB of the switch. I build a new PHI node in it manually.

4. The conversion is now done during early optimizations and therefore
   before  inlining which supposedly  improves inlining  decisions and
   creates only one array per original function.

I know  that some  people were not  convinced about the  usefulness of
this pass. I would therefore like to stress again that the overhead is
very low  as it only  examines the last  statements of every BB  and I
believe  Honza thinks  that  the improvements  for  inlining of  large
switch initializations are substantial.  I have measured the number of
conversions when  bootstrapping gcc some  time ago but I  somehow lost
the results  but I remember they  were slightly better  than before. I
will try to do that again soon.

The patch below passed bootstrap  and regression suit of all languages
including  ADA  on   linux-i386  (revision  132669)  and  linux-x86_64
(revision 132440) with "yes,fold" checking.

I would be grateful for reviewing and considering applying and of
course any comments and suggestions are strongly welcome. 

Martin


Changelog:

2008-02-29  Martin Jambor  <mjambor@suse.cz>
        * Makefile.in (tree-cswtch.o): Add.
        (OBJS-common): Add tree-cswtch.o
        * passes.c (init_optimization_passes): Add pass_convert_switch.
        * tree-pass.h: Add a declaration of the structure describing
	the new pass.
        * tree-cswtch.c: New file.
        * gcc.dg/tree-ssa/cswtch.c: New testcase.
        * common.opt (ftree-cswtch): New option. 
	* params.h (PARAM_CSWTCH_BRANCH_RATIO): New parameter.
	* params.def (PARAM_CSWTCH_BRANCH_RATIO): New parameter.
        * opts.c (decode_options): Set flag_tree_cswtch when
        optimization level is >= 2.
	* doc/invoke.texi (Optimize Options): Added description of
	-ftree-cswtch
	(Optimize Options): Added description of cswtch-max-branch-ratio


Index: gcc/doc/invoke.texi
===================================================================
--- gcc/doc/invoke.texi	(revision 132768)
+++ gcc/doc/invoke.texi	(working copy)
@@ -352,7 +352,7 @@ Objective-C and Objective-C++ Dialects}.
 -fsignaling-nans -fsingle-precision-constant -fsplit-ivs-in-unroller @gol
 -fsplit-wide-types -fstack-protector -fstack-protector-all @gol
 -fstrict-aliasing -fstrict-overflow -fthread-jumps -ftracer -ftree-ccp @gol
--ftree-ch -ftree-copy-prop -ftree-copyrename -ftree-dce @gol
+-ftree-ch -ftree-copy-prop -ftree-copyrename -ftree-cswtch -ftree-dce @gol
 -ftree-dominator-opts -ftree-dse -ftree-fre -ftree-loop-im @gol
 -ftree-loop-distribution @gol
 -ftree-loop-ivcanon -ftree-loop-linear -ftree-loop-optimize @gol
@@ -5208,6 +5208,7 @@ also turns on the following optimization
 -fsched-interblock  -fsched-spec @gol
 -fschedule-insns  -fschedule-insns2 @gol
 -fstrict-aliasing -fstrict-overflow @gol
+-ftree-cswtch @gol
 -ftree-pre @gol
 -ftree-vrp}
 
@@ -5887,6 +5888,11 @@ pass operates on both local scalar varia
 loads (global variables, structures, arrays, etc).  This flag is
 enabled by default at @option{-O2} and higher.
 
+@item -ftree-cswtch
+Perform conversion of simple initializations in a switch to
+initializations from a scalar array.  This flag is enabled by default
+at @option{-O2} and higher.
+
 @item -ftree-dce
 @opindex ftree-dce
 Perform dead code elimination (DCE) on trees.  This flag is enabled by
@@ -7313,6 +7319,11 @@ mechanism for comparing types in C++ and
 bugs in the canonical type system are causing compilation failures,
 set this value to 0 to disable canonical types.
 
+@item cswtch-max-branch-ratio
+Switch initialization conversion will refuse to create arrays that are
+bigger than @option{cswtch-max-branch-ratio} times the number of
+branches in the switch.
+
 @item max-partial-antic-length
 Maximum length of the partial antic set computed during the tree
 partial redundancy elimination optimization (@option{-ftree-pre}) when
Index: gcc/tree-pass.h
===================================================================
--- gcc/tree-pass.h	(revision 132768)
+++ gcc/tree-pass.h	(working copy)
@@ -444,6 +444,7 @@ extern struct tree_opt_pass pass_shorten
 extern struct tree_opt_pass pass_set_nothrow_function_flags;
 extern struct tree_opt_pass pass_final;
 extern struct tree_opt_pass pass_rtl_seqabstr;
+extern struct tree_opt_pass pass_convert_switch;
 extern struct tree_opt_pass pass_release_ssa_names;
 extern struct tree_opt_pass pass_early_inline;
 extern struct tree_opt_pass pass_inline_parameters;
Index: gcc/params.h
===================================================================
--- gcc/params.h	(revision 132768)
+++ gcc/params.h	(working copy)
@@ -171,4 +171,6 @@ typedef enum compiler_param
   PARAM_VALUE (PARAM_L2_CACHE_SIZE)
 #define USE_CANONICAL_TYPES \
   PARAM_VALUE (PARAM_USE_CANONICAL_TYPES)
+#define CSWTCH_BRANCH_RATIO \
+  PARAM_VALUE (PARAM_CSWTCH_BRANCH_RATIO)
 #endif /* ! GCC_PARAMS_H */
Index: gcc/testsuite/gcc.dg/tree-ssa/cswtch.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/cswtch.c	(revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/cswtch.c	(revision 0)
@@ -0,0 +1,81 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-cswtch" } */
+/* { dg-do run } */
+
+extern void abort (void);
+
+static int X, Y;
+
+int check(int param)
+{
+  int a = 0;
+  int b = 1;
+  
+  switch (param) 
+    {
+    case -2:
+      a = 0;
+      b = -1;
+      break;
+    case 1:
+    case 2:
+      a = 8;
+      b = 6;
+      break;
+    case 3:
+      a = 9;
+      b = 5;
+      break;
+    case 6:
+      a = 10;
+      b = 4;
+      break;
+    default:
+      a = 16;
+      b = 1;
+    }
+  
+  X = a;
+  Y = b;
+  return 0;
+}
+
+void assertions(int a, int b)
+{
+  if (X != a || Y != b)
+    abort();  
+
+  return;
+}
+
+int main ()
+{
+  check (-10);
+  assertions (16, 1);
+
+  check (-2);
+  assertions (0, -1);
+
+  check(1);
+  assertions (8, 6);
+
+  check(2);
+  assertions (8, 6);
+
+  check(3);
+  assertions (9, 5);
+
+  check(5);
+  assertions (16, 1);
+
+  check(6);
+  assertions (10, 4);
+
+  check(12);
+  assertions (16, 1);
+
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump "Switch converted" "cswtch" } } */
+/* { dg-final { cleanup-tree-dump "cswtch" } } */
Index: gcc/opts.c
===================================================================
--- gcc/opts.c	(revision 132768)
+++ gcc/opts.c	(working copy)
@@ -887,6 +887,7 @@ decode_options (unsigned int argc, const
       flag_reorder_functions = 1;
       flag_tree_store_ccp = 1;
       flag_tree_vrp = 1;
+      flag_tree_cswtch = 1;
 
       if (!optimize_size)
 	{
Index: gcc/tree-cswtch.c
===================================================================
--- gcc/tree-cswtch.c	(revision 0)
+++ gcc/tree-cswtch.c	(revision 0)
@@ -0,0 +1,840 @@
+/* Switch Conversion converts variable initializations based on switch
+   statements to initializations from a static array.  
+   Copyright (C) 2006, 2008 Free Software Foundation, Inc.  
+   Contributed by Martin Jambor <jamborm@suse.cz>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 3, or (at your option) any
+later version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not, write to the Free
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA.  */
+
+/*  
+     Switch initialization conversion
+
+The following pass changes simple initializations of scalars in a switch
+statement into initializations from a static array.  Obviously, the values must
+be constant and known at compile time and a default branch must be
+provided.  For example, the following code:
+
+        int a,b;
+
+        switch (argc) 
+	{
+         case 1:
+         case 2:
+                a_1 = 8;
+                b_1 = 6;
+                break;
+         case 3:
+                a_2 = 9;
+                b_2 = 5;
+                break;
+         case 12:
+                a_3 = 10;
+                b_3 = 4;
+                break;
+         default:
+                a_4 = 16;
+                b_4 = 1;
+        }
+	a_5 = PHI <a_1, a_2, a_3, a_4>
+	b_5 = PHI <b_1, b_2, b_3, b_4>
+
+
+is changed into:
+
+        static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
+        static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16, 
+                                 16, 16, 10};
+
+        if (((unsigned) argc) - 1 < 11)
+          {
+	    a_6 = CSWTCH02[argc - 1];
+            b_6 = CSWTCH01[argc - 1];
+	  }
+	else
+	  {
+	    a_7 = 16;
+	    b_7 = 1;
+          }
+	  a_5 = PHI <a_6, a_7>
+	  b_b = PHI <b_6, b_7>
+
+There are further constraints.  Specifically, the range of values across all
+case labels must not be bigger than CSWTCH_BRANCH_RATIO (default eight) times
+the number of the actual switch branches.  
+*/
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include <signal.h>
+
+#include "line-map.h"
+#include "params.h"
+#include "flags.h"
+#include "tree.h"
+#include "basic-block.h"
+#include "tree-flow.h"
+#include "tree-flow-inline.h"
+#include "tree-ssa-operands.h"
+#include "output.h"
+#include "tree-pass.h"
+#include "diagnostic.h"
+#include "tree-dump.h"
+
+/* The expression used to decide the switch branch.  (It is subsequently used
+   as the index to the created array.) */
+static tree index_expr;
+
+/* The following integer constants store the minimum value covered by the
+   cases.  */
+static tree range_min;
+
+/* The difference of between the above two numbers, i.e. The size of the array
+   that would have to be created by the transformation.  */
+static tree range_size;
+
+/* Basic block that contains the actual SWITCH_EXPR.  */
+static basic_block switch_bb;
+
+/* All branches of the switch statement must have a single successor stored in
+   the following variable.  */
+static basic_block final_bb;
+
+/* Number of phi nodes in the final bb (that we'll be replacing).  */
+static int phi_count;
+
+/* Array of default values, n the same order as phi nodes.  */
+static tree *default_values;
+
+/* Constructors of new static arrays.  */
+static VEC (constructor_elt, gc) **constructors;
+
+/* Array of ssa names that are initialized with a value from a new static
+   array.  */
+static tree *target_inbound_names;
+
+/* Array of ssa names that are initialized with the default value if the switch
+   expression is out of range.  */
+static tree *target_outbound_names;
+
+/* The probability of the default edge in the replaced switch.  */
+static int default_prob;
+
+/* The count of the default edge in the replaced switch.  */
+static gcov_type default_count;
+
+/* Combined count of all other (non-default) edges in the replaced switch.  */
+static gcov_type other_count;
+
+/* The last load statement that loads a temporary from a new static array.  */
+static tree arr_ref_first;
+
+/* The last load statement that loads a temporary from a new static array.  */
+static tree arr_ref_last;
+
+/* String reason why the case wasn't a good candidate that is written to the
+   dump file, if there is one.  */
+static const char *reason;
+
+
+/* Checks whether the range given by individual case statements isn't too big
+   and whether the number of branches actually satisfy the size of the new
+   array.  */
+static bool 
+check_range (tree swtch)
+{
+  tree min_case, max_case;
+  tree cases = SWITCH_LABELS (swtch);
+  int branch_num = TREE_VEC_LENGTH (cases);
+  tree range_max;
+
+  /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
+     is a default label which is the last in the vector.  */
+
+  min_case = TREE_VEC_ELT (cases, 0);
+  range_min = CASE_LOW (min_case);
+
+  gcc_assert (branch_num > 1);
+  max_case = TREE_VEC_ELT (cases, branch_num - 2);
+  if (CASE_HIGH (max_case) != NULL_TREE)
+    range_max = CASE_HIGH (max_case);
+  else
+    range_max = CASE_LOW (max_case);
+
+  gcc_assert (range_min);
+  gcc_assert (range_max);
+  
+  range_size = int_const_binop (MINUS_EXPR, range_max, range_min, 0);
+
+  gcc_assert (range_size);
+  if (!host_integerp (range_size, 1))
+    {
+      reason = "index range way too large or otherwise unusable.\n";
+      return false; 
+    }
+
+  if ((unsigned HOST_WIDE_INT) tree_low_cst (range_size, 1) 
+      > ((unsigned) branch_num * CSWTCH_BRANCH_RATIO))
+    {
+      reason = "the maximum range-branch ratio exceeded.";
+      return false;
+    }
+
+  return true;
+}
+
+/* Checks the given cs switch case whether it is suitable for conversion
+   (whether all but the default basic blocks are empty and so on).  If it is,
+   adds the case to the branch list along with values for the defined variables
+   and returns true.  Otherwise returns false.  */
+static bool 
+check_process_case (tree cs)
+{
+  tree ldecl;
+  basic_block label_bb, following_bb;
+  edge e;
+
+  ldecl = CASE_LABEL (cs);
+  label_bb = label_to_block (ldecl);
+
+  e = find_edge (switch_bb, label_bb);
+  gcc_assert (e);
+
+  if (CASE_LOW (cs) == NULL_TREE) 
+    {
+      /* default branch */
+      default_prob = e->probability;
+      default_count = e->count;
+    }
+  else
+    other_count += e->count;
+  
+  if (!label_bb)
+    {
+      reason = "  Bad case - cs BB  label is NULL\n";
+      return false;
+    }
+
+  if (!single_pred_p (label_bb))
+    {
+      if (final_bb && final_bb != label_bb)
+	{
+	  reason = "  Bad case - a non-final BB has two predecessors\n";
+	  return false; /* sth complex going on in this branch  */
+	}
+
+      following_bb = label_bb;
+    }
+  else
+    {
+      if (!empty_block_p (label_bb))
+	{
+	  reason = "  Bad case - a non-final BB not empty\n";
+	  return false;
+	}
+
+      e = single_succ_edge (label_bb);
+      following_bb = single_succ (label_bb);
+    }
+
+  if (!final_bb) 
+    final_bb = following_bb;
+  else if (final_bb != following_bb)
+    {
+      reason = "  Bad case - different final BB\n";
+      return false; /* the only successor is not common for all the branches */
+    }
+
+  return true;
+}
+
+/* check_final_bb() checks whether all required values in phi nodes in final_bb
+   are constants.  Required values are those that correspond to a basic block
+   which is a part of the examined switch statement.  It returns true if the
+   phi nodes are OK, otherwise false.  */
+static bool
+check_final_bb (void)
+{
+  tree phi;
+
+  phi_count = 0;
+  for (phi = phi_nodes (final_bb); phi; phi = PHI_CHAIN (phi)) 
+    {
+      int i;
+
+      phi_count++;
+
+      for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+	{
+	  basic_block bb = PHI_ARG_EDGE (phi, i)->src;
+	  
+	  if ((bb == switch_bb 
+	       || (single_pred_p (bb) && single_pred (bb) == switch_bb))
+	      && !is_gimple_min_invariant (PHI_ARG_ELT (phi, i).def))
+	    {
+	      reason = "   Non-invariant value from a case\n";
+	      return false; 		/* non invariant argument */
+	    }
+	}
+    }
+
+  return true;
+}
+
+/* create_temp_arrays() allocates default_values, target_{in,out}_names and
+   constructors arrays.  The last one is also populated with pointers to
+   vectors that will become constructors of new arrays.  */
+static void
+create_temp_arrays (void)
+{
+  int i;
+
+  default_values = xcalloc (phi_count, sizeof (tree));
+  constructors = xcalloc (phi_count, sizeof (tree));
+  target_inbound_names = xcalloc (phi_count, sizeof (tree));
+  target_outbound_names = xcalloc (phi_count, sizeof (tree));
+
+  for (i = 0; i < phi_count; i++)
+    {
+      constructors[i] = VEC_alloc (constructor_elt, gc, 
+				   tree_low_cst (range_size, 1) + 1);
+    }
+}
+
+/* free_temp_arrays() frees the arrays created by create_temp_arrays().  The
+   vectors that are created by that function are not freed here, however,
+   because they have already become the constructors and must be preserved.  */
+static void
+free_temp_arrays (void)
+{
+  free (constructors);
+  free (default_values);
+  free (target_inbound_names);
+  free (target_outbound_names);
+}
+
+/* gather_default_values() populates the array of default values in the order
+   of phi nodes.  */
+static void
+gather_default_values (tree default_case)
+{
+  tree phi;
+  basic_block bb = label_to_block (CASE_LABEL (default_case));
+  edge e;
+  int i;
+
+  gcc_assert (CASE_LOW (default_case) == NULL_TREE);
+
+  if (bb == final_bb)
+    e = find_edge (switch_bb, bb);
+  else
+    e = single_succ_edge (bb);
+  
+  for (phi = phi_nodes (final_bb), i = 0; phi; phi = PHI_CHAIN (phi), i++) 
+    {
+      tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
+      gcc_assert (val);
+      default_values[i] = val;
+    }
+}
+
+/* build_constructors() populates the vectors in the constructors array with
+   future contents of the static arrays.  The vectors are populated in the
+   order of phi nodes.  */
+static void
+build_constructors (tree swtch)
+{
+  int i;
+  tree cases = SWITCH_LABELS (swtch);
+  tree pos = range_min;
+  
+  for (i = 0; i < TREE_VEC_LENGTH (cases) - 1; i++) 
+    {
+      tree cs = TREE_VEC_ELT (cases, i);
+      basic_block bb = label_to_block (CASE_LABEL (cs));
+      edge e;
+      tree phi, high;
+      int j;
+
+      if (bb == final_bb)
+	e = find_edge (switch_bb, bb);
+      else
+	e = single_succ_edge (bb);
+      gcc_assert (e);
+
+      while (tree_int_cst_lt (pos, CASE_LOW (cs)))
+	{
+	  int k;
+	  for (k = 0; k < phi_count; k++)
+	    {
+	      constructor_elt *elt;
+
+	      elt = VEC_quick_push (constructor_elt, 
+				    constructors[k], NULL);
+	      elt->index = int_const_binop (MINUS_EXPR, pos, range_min, 0);
+	      elt->value = default_values[k];
+	    }
+
+	  pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0);
+	}
+      gcc_assert (tree_int_cst_equal (pos, CASE_LOW(cs)));
+      
+      j = 0;
+      if (CASE_HIGH (cs))
+	high = CASE_HIGH (cs);
+      else
+	high = CASE_LOW(cs);
+      for (phi = phi_nodes (final_bb); phi; phi = PHI_CHAIN (phi)) 
+	{
+	  tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
+	  pos = CASE_LOW (cs);
+
+	  while (!tree_int_cst_lt (high, pos))
+	    {
+	      constructor_elt *elt;
+
+	      elt = VEC_quick_push (constructor_elt, 
+				    constructors[j], NULL);
+	      elt->index = int_const_binop (MINUS_EXPR, pos, range_min, 0);
+	      elt->value = val;
+	      
+	      pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0);
+	    }
+	  j++;
+	}
+    }
+}
+
+/* build_one_array() creates an appropriate array type and declaration and
+   assembles a static array variable.  It also creates a load statement that
+   initializes the variable in question with a value from the static array.  */
+static void 
+build_one_array (tree swtch, int num, tree arr_index_type, tree phi, tree tidx)
+{ 
+  tree array_type;
+  tree ctor;
+  tree decl;
+  tree value_type;
+  tree name;
+  tree fetch, load;
+  block_stmt_iterator bsi;
+
+  gcc_assert (default_values[num]);
+  value_type = TREE_TYPE (default_values[num]);
+  array_type = build_array_type (value_type, arr_index_type); 
+
+  ctor = build_constructor (array_type, constructors[num]);
+  TREE_CONSTANT (ctor) = true;
+
+  decl = build_decl (VAR_DECL, NULL_TREE, array_type); 
+  TREE_STATIC (decl) = 1;
+  DECL_INITIAL (decl) = ctor;
+
+  DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
+  DECL_ARTIFICIAL (decl) = 1;
+  TREE_CONSTANT (decl) = 1;
+  add_referenced_var (decl);
+  assemble_variable (decl, 0, 0, 0);
+  mark_sym_for_renaming (decl);
+
+  name = make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi)), NULL_TREE);
+  target_inbound_names[num] = name;
+
+  fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE, 
+		  NULL_TREE); 
+  load = build2 (GIMPLE_MODIFY_STMT, void_type_node, name, fetch);
+  SSA_NAME_DEF_STMT (name) = load;
+
+  bsi = bsi_for_stmt (swtch);
+  bsi_insert_before (&bsi, load, BSI_SAME_STMT);
+  mark_symbols_for_renaming (load);
+
+  arr_ref_last = load;
+  
+  return;
+}
+
+/* Builds and initializes static arrays initialized with values gathered from
+   the switch statement.  Also creates statements that assign a value.  */
+static void 
+build_arrays (tree swtch)
+{
+  tree arr_index_type;
+  tree tidx, sub;
+  block_stmt_iterator bsi;
+  tree phi = phi_nodes (final_bb);
+  int i;
+    
+  arr_index_type = build_index_type (range_size);
+  tidx = make_rename_temp (arr_index_type, "csti");
+  sub = build2 (MINUS_EXPR, TREE_TYPE (index_expr), index_expr, 
+		fold_convert (TREE_TYPE (index_expr), range_min));
+  sub = build2 (GIMPLE_MODIFY_STMT, void_type_node, tidx, sub);
+  
+  bsi = bsi_for_stmt (swtch);
+  bsi_insert_before (&bsi, sub, BSI_SAME_STMT);
+  mark_symbols_for_renaming (sub);
+  arr_ref_first = sub;
+
+  for (phi = phi_nodes (final_bb), i = 0; phi; phi = PHI_CHAIN (phi), i++) 
+    build_one_array (swtch, i, arr_index_type, phi, tidx);
+  
+  return;
+}
+
+/* Generates and appropriately inserts loads of default values at the given
+   position.  Returns the last inserted statement.  */
+static tree 
+gen_def_assigns (block_stmt_iterator *bsi)
+{
+  int i;
+  tree assign = NULL_TREE;
+
+  for (i = 0; i < phi_count; i++)
+    {
+      tree name = make_ssa_name (SSA_NAME_VAR (target_inbound_names[i]), 
+				 NULL_TREE);
+
+      target_outbound_names[i] = name;
+      assign = build2 (GIMPLE_MODIFY_STMT, void_type_node, name, 
+		       default_values[i]);
+      SSA_NAME_DEF_STMT (name) = assign;
+      bsi_insert_before (bsi, assign, BSI_SAME_STMT);
+      find_new_referenced_vars (&assign);
+      mark_symbols_for_renaming (assign);
+    }
+  return assign;
+}
+
+/* Deletes the unused bbs and edges that now contain the switch statement and
+   its empty branch bbs.  */
+static void 
+prune_bbs (basic_block bbd, basic_block final)
+{
+  edge_iterator ei;
+  edge e;
+  
+  for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
+    {
+      basic_block bb;
+      bb = e->dest;
+      remove_edge (e);
+      if (bb != final) 
+	delete_basic_block (bb);
+    }
+  delete_basic_block (bbd);
+}
+
+/* fix_phi_nodes() adds values to phi nodes in final_bb for the two new
+   edges.  e1f is the edge from the basic block loading values from an array and
+   e2f from the basic block loading default values.  */
+static void 
+fix_phi_nodes (edge e1f, edge e2f, basic_block bbf)
+{
+  tree phi;
+  int i;
+
+  for (phi = phi_nodes (bbf), i = 0; phi; phi = PHI_CHAIN (phi), i++) 
+    {
+      add_phi_arg (phi, target_inbound_names[i], e1f);
+      add_phi_arg (phi, target_outbound_names[i], e2f);
+    }
+
+}
+
+/* Creates a check whether the switch expression value actually falls into the
+   range given by all the cases.  If it not, the temporaries are loaded with
+   default values instead.
+   
+   bb0 is the bb with the switch statement, however, we'll end it with a
+       condition instead.
+
+   bb1 is the bb to be used when the range check went ok.  It is derived from
+       the switch BB
+
+   bb2 is the bb taken when the expression evaluated outside of the range
+       covered by the created arrays.  It is populated by loads of default
+       values.
+
+   bbF is a fall through for both bb1 and bb2 and contains exactly what
+       originally followed the switch statement.
+
+   bbD contains the switch statement (in the end).  It is unreachable but we
+       still need to strip off its edges.
+*/
+static void 
+gen_inbound_check (tree swtch)
+{
+  tree label_decl1 = create_artificial_label ();
+  tree label_decl2 = create_artificial_label ();
+  tree label_decl3 = create_artificial_label ();
+  tree label1, label2, label3;
+
+  tree utype = unsigned_type_for (TREE_TYPE (index_expr));
+  tree tmp_u;
+  tree cast, cast_assign;
+  tree ulb, minus, minus_assign;
+  tree bound;
+  
+  tree if_expr;
+
+  tree last_assign;
+  block_stmt_iterator bsi;
+  basic_block bb0, bb1, bb2, bbf, bbd;
+  edge e01, e02, e21, e1d, e1f, e2f;
+
+  gcc_assert (default_values);
+  bb0 = bb_for_stmt (swtch);
+
+  /* (end of) block 0 */
+  bsi = bsi_for_stmt (arr_ref_first);
+  tmp_u = make_rename_temp (utype, "csui");
+  
+  cast = build1 (NOP_EXPR, utype, index_expr);
+  cast_assign = build2 (GIMPLE_MODIFY_STMT, void_type_node, tmp_u, cast);
+  find_new_referenced_vars (&cast_assign);
+  bsi_insert_before (&bsi, cast_assign, BSI_SAME_STMT);
+  mark_symbols_for_renaming (cast_assign);
+  
+  ulb = fold_convert (utype, range_min);
+  minus = build2 (MINUS_EXPR, utype, tmp_u, ulb);
+  minus_assign = build2 (GIMPLE_MODIFY_STMT, void_type_node, tmp_u, minus);
+  find_new_referenced_vars (&minus_assign);
+  bsi_insert_before (&bsi, minus_assign, BSI_SAME_STMT);
+  mark_symbols_for_renaming (minus_assign);
+
+  bound = fold_convert (utype, range_size);
+
+  if_expr = build3 (COND_EXPR, void_type_node,
+		    build2 (LE_EXPR, boolean_type_node, tmp_u, bound),
+		    NULL_TREE, NULL_TREE);
+  
+  find_new_referenced_vars (&if_expr);
+  bsi_insert_before (&bsi, if_expr, BSI_SAME_STMT);
+  mark_symbols_for_renaming (if_expr);
+  
+  /* block 2 */
+  bsi = bsi_for_stmt (arr_ref_first);
+  label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
+  bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
+  last_assign = gen_def_assigns (&bsi);
+
+  /* block 1 */
+  bsi = bsi_for_stmt (arr_ref_first);
+  label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
+  bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
+
+  /* block F */
+  bsi = bsi_start (final_bb);
+  label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
+  bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
+
+  /* cfg fix */
+  e02 = split_block (bb0, if_expr);
+  bb2 = e02->dest;
+
+  e21 = split_block (bb2, last_assign);
+  bb1 = e21->dest;
+  remove_edge (e21);
+
+  e1d = split_block (bb1, arr_ref_last);
+  bbd = e1d->dest;
+  remove_edge (e1d);
+
+  /* flags and profiles of the edge for in-range values */
+  e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
+  e01->probability = REG_BR_PROB_BASE - default_prob;
+  e01->count = other_count;
+
+  /* flags and profiles of the edge taking care of out-of-range values */
+  e02->flags &= ~EDGE_FALLTHRU;
+  e02->flags |= EDGE_FALSE_VALUE;
+  e02->probability = default_prob;
+  e02->count = default_count;
+
+  bbf = final_bb;
+
+  e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
+  e1f->probability = REG_BR_PROB_BASE;
+  e1f->count = other_count;
+
+  e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
+  e2f->probability = REG_BR_PROB_BASE;
+  e2f->count = default_count;
+
+  /* frequencies of the new BBs */
+  bb1->frequency = EDGE_FREQUENCY (e01);
+  bb2->frequency = EDGE_FREQUENCY (e02);
+  bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f);
+  
+  prune_bbs (bbd, final_bb); /* to keep calc_dfs_tree() in dominance.c
+				happy */
+  
+  fix_phi_nodes (e1f, e2f, bbf);
+
+  free_dominance_info (CDI_DOMINATORS);
+  free_dominance_info (CDI_POST_DOMINATORS);
+}
+
+/* process_switch() is invoked on every switch statement and runs the individual
+   phases of switch conversion on it one after another until one fails or the
+   conversion is completed.  */
+static bool 
+process_switch (tree swtch)
+{
+  int i;
+  tree cases;
+  tree index_type;
+
+  /* operand 2 is either NULL_TREE or a vector of cases (stmt.c)*/
+  if (TREE_OPERAND (swtch, 2) == NULL_TREE) 
+    {
+      reason = "swtch has no labels\n";
+      return false;
+    }
+
+  /* Comment from stmt.c: 
+     The switch body is lowered in gimplify.c, we should never have switches
+     with a non-NULL SWITCH_BODY here.  */
+  gcc_assert (!SWITCH_BODY (swtch));
+
+  cases = SWITCH_LABELS (swtch);
+  final_bb = NULL;
+  switch_bb = bb_for_stmt (swtch);
+  index_expr = SWITCH_COND (swtch); 
+  index_type = TREE_TYPE (index_expr);
+  arr_ref_first = NULL_TREE;
+  arr_ref_last = NULL_TREE;
+  default_prob = 0;
+  default_count = 0;
+  other_count = 0;
+
+  /* An ERROR_MARK occurs for various reasons including invalid data type.
+     (comment from stmt.c) */
+  if (index_type == error_mark_node) 
+    {
+      reason = "index error.\n";
+      return false; 
+    }
+
+  /* check the case label values are within reasonable range:  */
+  if (!check_range (swtch))
+    return false;
+
+  /* for all the cases, see whether they are empty, the assignments they
+     represent constant and so on...  */
+  for (i = 0; i < TREE_VEC_LENGTH (cases); i++) 
+    {
+      tree part_case = TREE_VEC_ELT (cases, i);
+      if (!check_process_case (part_case)) 
+	{
+	  if (dump_file) 
+	    fprintf (dump_file, "Processing of case %i failed\n", i);
+	  return false;
+	}
+    }
+
+  if (!check_final_bb ())
+    return false;
+
+  /* at this point all checks have passed and we can proceed with the
+     transformation.  */
+  
+  create_temp_arrays ();
+  gather_default_values (TREE_VEC_ELT (cases, TREE_VEC_LENGTH (cases) - 1));
+  build_constructors (swtch);
+  
+  build_arrays (swtch); /* build the static arrays and assignments */
+  gen_inbound_check (swtch); 	/* build the bound check */
+
+  /* cleanup: */
+  free_temp_arrays ();
+  return true;
+}
+
+/* The main function of the pass scans statements for switches and invokes
+   process_switch on them.  */
+static unsigned int 
+do_convswitch (void)
+{
+  basic_block bb;
+  bool need_update = false;
+  
+  FOR_EACH_BB (bb) 
+  {
+    tree stmt = last_stmt (bb);
+    if (stmt && TREE_CODE (stmt) == SWITCH_EXPR) 
+      {
+	if (dump_file)
+	  {
+	    fprintf (dump_file, "\beginning to process the following "
+		     "SWITCH statement: ------- \n");
+	    print_generic_stmt (dump_file, stmt, 2);
+	    fprintf (dump_file, "\n");
+	  }
+
+	reason = NULL;
+	if (process_switch (stmt))
+	  {
+	    need_update = true;
+	    
+	    if (dump_file)
+	      {
+		fprintf (dump_file, "Switch converted\n");
+		fprintf (dump_file, "--------------------------------\n");
+	      }
+	  }
+	else
+	  {
+	    if (dump_file)
+	      {
+		gcc_assert (reason);
+		fprintf (dump_file, "Bailing out - ");
+		fprintf (dump_file, reason);
+		fprintf (dump_file, "--------------------------------\n");
+	      }
+	  }
+      }
+  }
+
+  return 0;
+}
+
+static bool
+convswitch_gate (void)
+{
+  return flag_tree_cswtch != 0;
+}
+
+struct tree_opt_pass pass_convert_switch =
+{
+  "cswtch",				/* name */
+  convswitch_gate,        		/* gate */
+  do_convswitch,			/* execute */
+  NULL,					/* sub */
+  NULL,					/* next */
+  0,					/* static_pass_number */
+  0,			        	/* tv_id */
+  PROP_cfg | PROP_ssa,	                /* properties_required */
+  0,					/* properties_provided */
+  0,					/* properties_destroyed */
+  0,					/* todo_flags_start */
+  TODO_update_ssa | TODO_dump_func 
+  | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
+  0					/* letter */
+};
Index: gcc/common.opt
===================================================================
--- gcc/common.opt	(revision 132768)
+++ gcc/common.opt	(working copy)
@@ -1082,6 +1082,10 @@ ftree-cselim
 Common Report Var(flag_tree_cselim) Init(2) Optimization
 Transform condition stores into unconditional ones
 
+ftree-cswtch
+Common Report Var(flag_tree_cswtch) Optimization
+Perform conversions of switch initializations.
+
 ftree-dce
 Common Report Var(flag_tree_dce) Optimization
 Enable SSA dead code elimination optimization on trees
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in	(revision 132768)
+++ gcc/Makefile.in	(working copy)
@@ -1170,6 +1170,7 @@ OBJS-common = \
 	tree-profile.o \
 	tree-scalar-evolution.o \
 	tree-sra.o \
+	tree-cswtch.o \
 	tree-ssa-address.o \
 	tree-ssa-alias.o \
 	tree-ssa-alias-warnings.o \
@@ -2593,6 +2594,11 @@ tree-sra.o : tree-sra.c $(CONFIG_H) $(SY
     $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) $(TREE_GIMPLE_H) \
     langhooks.h tree-pass.h $(FLAGS_H) $(EXPR_H) $(BASIC_BLOCK_H) \
     bitmap.h $(GGC_H) hard-reg-set.h $(OBSTACK_H) $(PARAMS_H) $(TARGET_H)
+tree-cswtch.o : tree-cswtch.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) \
+    $(TM_P_H) $(TREE_FLOW_H) $(DIAGNOSTIC_H) $(TREE_INLINE_H) \
+    $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) $(TREE_GIMPLE_H) \
+    tree-pass.h $(FLAGS_H) $(EXPR_H) $(BASIC_BLOCK_H) output.h \
+    $(GGC_H) $(OBSTACK_H) $(PARAMS_H) $(CPPLIB_H) $(PARAMS_H)
 tree-complex.o : tree-complex.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TREE_H) \
     $(TM_H) $(RTL_H) $(REAL_H) $(FLAGS_H) $(TREE_FLOW_H) $(TREE_GIMPLE_H) \
     tree-iterator.h tree-pass.h tree-ssa-propagate.h $(DIAGNOSTIC_H)
Index: gcc/passes.c
===================================================================
--- gcc/passes.c	(revision 132768)
+++ gcc/passes.c	(working copy)
@@ -532,6 +532,7 @@ init_optimization_passes (void)
 	  NEXT_PASS (pass_update_address_taken);
 	  NEXT_PASS (pass_simple_dse);
 	  NEXT_PASS (pass_tail_recursion);
+	  NEXT_PASS (pass_convert_switch);
           NEXT_PASS (pass_profile);
 	  NEXT_PASS (pass_release_ssa_names);
 	}
@@ -556,6 +557,7 @@ init_optimization_passes (void)
   NEXT_PASS (pass_all_optimizations);
     {
       struct tree_opt_pass **p = &pass_all_optimizations.sub;
+      /*NEXT_PASS (pass_convert_switch);*/
       NEXT_PASS (pass_create_structure_vars);
       /* ??? pass_build_alias is a dummy pass that ensures that we
 	 execute TODO_rebuild_alias at this point even if
Index: gcc/params.def
===================================================================
--- gcc/params.def	(revision 132768)
+++ gcc/params.def	(working copy)
@@ -729,6 +729,15 @@ DEFPARAM (PARAM_DF_DOUBLE_QUEUE_THRESHOL
 	  "Multiplier used for determining the double-queueing threshold",
 	  2, 0, 0)
 
+/* Switch initialization conversion will refuse to create arrays that are
+   bigger than this parameter times the number of switch branches.  */
+
+DEFPARAM (PARAM_CSWTCH_BRANCH_RATIO,
+	  "cswtch-max-branch-ratio",
+	  "The maximum ratio between array size and switch branches for "
+	  "a switch conversion to take place",
+	  8, 1, 0)
+
 /*
 Local variables:
 mode:c

Re: [PATCH, middle-end] Switch initializations conversion (take four)

[Mark Mitchell]

Martin Jambor wrote:

> since we are again in stage 1, I am re-submitting an improved the pass
> converting constant assignments in switch statements into assignments
> from a static array. 

Thank you.

> I know  that some  people were not  convinced about the  usefulness of
> this pass. I would therefore like to stress again that the overhead is
> very low  as it only  examines the last  statements of every BB  and I
> believe  Honza thinks  that  the improvements  for  inlining of  large
> switch initializations are substantial.  I have measured the number of
> conversions when  bootstrapping gcc some  time ago but I  somehow lost
> the results  but I remember they  were slightly better  than before. I
> will try to do that again soon.

Optimization is a quantitative question: the whole point is to make the 
program smaller, faster, etc.  So, all non-obvious optimization patches 
should come with quantitative information, in addition to qualitative 
information.

In particular, which benchmark(s), on which platform(s), with which 
flags did you use to measure improvement?  And how much improvement did 
you see?  And, what benchmark(s) on which platforms which which flags 
did you use to measure costs?  And how high were the costs?

For example, if you said "this patch makes CSiBE on ARM EABI with -Os 1% 
smaller" and "I measured the time required to build libstdc++ on ARM 
EABI with default flags with this patch and it made the compiler 
0.00001% slower", then that would be strongly compelling.  There might 
be some follow-up questions, but, without that kind of information it's 
hard to know whether we should invest further in the patch.

I hope that's not discouraging.  Personally, I think this is a good 
idea, and might be a big win on some codes.  Even if the benchmark is a 
single real-world application you have at hand -- rather than some 
well-known benchmark suite -- the patch might be worthwhile if the costs 
are low enough.  But, we need to have some quantitative information in 
order to evaluate it.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [PATCH, middle-end] Switch initializations conversion (take four)

[Jan Hubicka]

> I hope that's not discouraging.  Personally, I think this is a good 
> idea, and might be a big win on some codes.  Even if the benchmark is a 
> single real-world application you have at hand -- rather than some 
> well-known benchmark suite -- the patch might be worthwhile if the costs 
> are low enough.  But, we need to have some quantitative information in 
> order to evaluate it.

PR34708 contains a nice real world testcase where such a conversion
would make real difference.  SWIG contains an error reporting function 

static __attribute__ ((__unused__)) const char*
SWIG_Perl_ErrorType(int code) 

that is basically resonably sized switch translating codes to names.
When inlined many times we explode in number of references to string
pools while this conversion would turn the function into simple lookup.

Honza
> 
> -- 
> Mark Mitchell
> CodeSourcery
> mark@codesourcery.com
> (650) 331-3385 x713

Re: [PATCH, middle-end] Switch initializations conversion (take four)

[Martin Jambor]

On Fri, Feb 29, 2008 at 12:07:05PM -0800, Mark Mitchell wrote:
> Optimization is a quantitative question: the whole point is to make the 
> program smaller, faster, etc.  So, all non-obvious optimization patches 
> should come with quantitative information, in addition to qualitative 
> information.
>
> In particular, which benchmark(s), on which platform(s), with which flags 
> did you use to measure improvement?  And how much improvement did you see?  
> And, what benchmark(s) on which platforms which which flags did you use to 
> measure costs?  And how high were the costs?

So far I have only managed to  find out how many and what switches get
converted during GCC bootstrap (this time all languages including ADA)
on i386 Linux. 177 conversions take  place (59 twice and 1 once during
the whole  process). The exact  switches as reported  by EXPR_LOCATION
are listed in http://misc.jamborm.net/cswtch.log  

I did not  include the numbers with my last post  because I've sent my
previous results  here in August  and I know  I did not get  any worse
than that. In  fact, since I now do the  conversion before inlining, I
certainly do a better job than before.

In summer I  was not able to measure  any compilation/runtime slowdown
that could not  be accounted for the noise.  I do  not expect this has
changed either.   However, I will re-measure  that too so  that I have
the numbers.

All  in all,  even  though  the transformation  does  not bring  about
record-breaking speedups,  it does make  the code nicer  (which helps,
for  example the  inliner in  cases like  PR34708) and  I  believe the
cost/benefit ratio is favorable.

As far  as maintaining  is concerned,  I strive hard  to make  gcc the
central part of my work so I  am willing to take care of this pass for
the foreseeable future.

I will try to come up with some time measurements soon.

Martin

Re: [PATCH, middle-end] Switch initializations conversion (take four)

[Mark Mitchell]

Martin Jambor wrote:

> So far I have only managed to  find out how many and what switches get
> converted during GCC bootstrap (this time all languages including ADA)
> on i386 Linux. 177 conversions take  place (59 twice and 1 once during
> the whole  process). The exact  switches as reported  by EXPR_LOCATION
> are listed in http://misc.jamborm.net/cswtch.log  

That's good data, thanks.  Does it make the resulting binary a bit 
smaller?  If so, how much?

> In summer I  was not able to measure  any compilation/runtime slowdown
> that could not  be accounted for the noise.  I do  not expect this has
> changed either.   However, I will re-measure  that too so  that I have
> the numbers.

Yes, please report on that; if the number is in the noise, that's fine. 
  I'm not trying to make a lot of work for you; I just think that a 
little quantitative data is useful.

Thanks,

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [PATCH, middle-end] Switch initializations conversion (take four)

[Jan Hubicka]

> On Fri, Feb 29, 2008 at 12:07:05PM -0800, Mark Mitchell wrote:
> > Optimization is a quantitative question: the whole point is to make the 
> > program smaller, faster, etc.  So, all non-obvious optimization patches 
> > should come with quantitative information, in addition to qualitative 
> > information.
> >
> > In particular, which benchmark(s), on which platform(s), with which flags 
> > did you use to measure improvement?  And how much improvement did you see?  
> > And, what benchmark(s) on which platforms which which flags did you use to 
> > measure costs?  And how high were the costs?
> 
> So far I have only managed to  find out how many and what switches get
> converted during GCC bootstrap (this time all languages including ADA)
> on i386 Linux. 177 conversions take  place (59 twice and 1 once during
> the whole  process). The exact  switches as reported  by EXPR_LOCATION
> are listed in http://misc.jamborm.net/cswtch.log  

Hi,
I've dropped the patch to periodic tester (vangelis) for last 2 days.
The compile time seems to be off noise (first CPU2000 build was 4
seconds slower, other 40 seconds faster than the build just before that
might be result of mainline change) as are performance results.

There are some code size improvements, though interestingly GCC
benchmark size grew from 2242->2246Kb (in peak so might be more
inlining). Perl changes 938->935Kb, Mesa 692Kb->688Kb.

Honza

Re: [PATCH, middle-end] Switch initializations conversion (take four)

[Jan Hubicka]

> > On Fri, Feb 29, 2008 at 12:07:05PM -0800, Mark Mitchell wrote:
> > > Optimization is a quantitative question: the whole point is to make the 
> > > program smaller, faster, etc.  So, all non-obvious optimization patches 
> > > should come with quantitative information, in addition to qualitative 
> > > information.
> > >
> > > In particular, which benchmark(s), on which platform(s), with which flags 
> > > did you use to measure improvement?  And how much improvement did you see?  
> > > And, what benchmark(s) on which platforms which which flags did you use to 
> > > measure costs?  And how high were the costs?
> > 
> > So far I have only managed to  find out how many and what switches get
> > converted during GCC bootstrap (this time all languages including ADA)
> > on i386 Linux. 177 conversions take  place (59 twice and 1 once during
> > the whole  process). The exact  switches as reported  by EXPR_LOCATION
> > are listed in http://misc.jamborm.net/cswtch.log  
> 
> Hi,
> I've dropped the patch to periodic tester (vangelis) for last 2 days.
> The compile time seems to be off noise (first CPU2000 build was 4
			       ^^ in ;)
> seconds slower, other 40 seconds faster than the build just before that
> might be result of mainline change) as are performance results.
> 
> There are some code size improvements, though interestingly GCC
> benchmark size grew from 2242->2246Kb (in peak so might be more
> inlining). Perl changes 938->935Kb, Mesa 692Kb->688Kb.
> 
> Honza

Re: [PATCH, middle-end] Switch initializations conversion (take four)

[Mark Mitchell]

Jan Hubicka wrote:

> I've dropped the patch to periodic tester (vangelis) for last 2 days.
> The compile time seems to be off noise (first CPU2000 build was 4
> seconds slower, other 40 seconds faster than the build just before that
> might be result of mainline change) as are performance results.
> 
> There are some code size improvements, though interestingly GCC
> benchmark size grew from 2242->2246Kb (in peak so might be more
> inlining). Perl changes 938->935Kb, Mesa 692Kb->688Kb.

OK, that sounds like the data we expect: on change in compile-time and 
some code-size improvement overall.  I think that ought to resolve any 
concern about benchmarking the optimization.

Thanks,

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [PATCH, middle-end] Switch initializations conversion (take four)

[Martin Jambor]

On Sat, Mar 08, 2008 at 03:42:24PM -1000, Mark Mitchell wrote:
> OK, that sounds like the data we expect: on change in compile-time and some 
> code-size improvement overall.  I think that ought to resolve any concern 
> about benchmarking the optimization.
>

Thank you. Can any appropriate reviewer have a look at the patch then?
In case you lost it, the original mail with the patch can be found at:

http://gcc.gnu.org/ml/gcc-patches/2008-02/msg01468.html

Thanks in advance,

Martin

Re: [PATCH, middle-end] Switch initializations conversion (take four.1)

[Martin Jambor]

Hi, 

in order  to reflect the  transition from struct  tree_opt_pass to
gimple_opt_pass,  I have  modified my  proposed  switch conversion
pass that I sent here more than a month ago in

http://gcc.gnu.org/ml/gcc-patches/2008-02/msg01468.html

I have re-bootstrapped and re-tested this on i686-pc-linux-gnu,
revision 133790, all languages including ADA.

Can anyone review the patch, please? Thank you very much in advance.

Martin


The changelog stays the same:

2008-04-08  Martin Jambor  <mjambor@suse.cz>
        * Makefile.in (tree-cswtch.o): Add.
        (OBJS-common): Add tree-cswtch.o
        * passes.c (init_optimization_passes): Add pass_convert_switch.
        * tree-pass.h: Add a declaration of the structure describing
        the new pass.
        * tree-cswtch.c: New file.
        * gcc.dg/tree-ssa/cswtch.c: New testcase.
        * common.opt (ftree-cswtch): New option.
        * params.h (PARAM_CSWTCH_BRANCH_RATIO): New parameter.
        * params.def (PARAM_CSWTCH_BRANCH_RATIO): New parameter.
        * opts.c (decode_options): Set flag_tree_cswtch when
        optimization level is >= 2.
        * doc/invoke.texi (Optimize Options): Added description of
        -ftree-cswtch
        (Optimize Options): Added description of cswtch-max-branch-ratio


Index: gcc/doc/invoke.texi
===================================================================
--- gcc/doc/invoke.texi	(revision 133790)
+++ gcc/doc/invoke.texi	(working copy)
@@ -353,7 +353,7 @@ Objective-C and Objective-C++ Dialects}.
 -fsignaling-nans -fsingle-precision-constant -fsplit-ivs-in-unroller @gol
 -fsplit-wide-types -fstack-protector -fstack-protector-all @gol
 -fstrict-aliasing -fstrict-overflow -fthread-jumps -ftracer -ftree-ccp @gol
--ftree-ch -ftree-copy-prop -ftree-copyrename -ftree-dce @gol
+-ftree-ch -ftree-copy-prop -ftree-copyrename -ftree-cswtch -ftree-dce @gol
 -ftree-dominator-opts -ftree-dse -ftree-fre -ftree-loop-im @gol
 -ftree-loop-distribution @gol
 -ftree-loop-ivcanon -ftree-loop-linear -ftree-loop-optimize @gol
@@ -5160,6 +5160,7 @@ also turns on the following optimization
 -fsched-interblock  -fsched-spec @gol
 -fschedule-insns  -fschedule-insns2 @gol
 -fstrict-aliasing -fstrict-overflow @gol
+-ftree-cswtch @gol
 -ftree-pre @gol
 -ftree-vrp}
 
@@ -5839,6 +5840,11 @@ pass operates on both local scalar varia
 loads (global variables, structures, arrays, etc).  This flag is
 enabled by default at @option{-O2} and higher.
 
+@item -ftree-cswtch
+Perform conversion of simple initializations in a switch to
+initializations from a scalar array.  This flag is enabled by default
+at @option{-O2} and higher.
+
 @item -ftree-dce
 @opindex ftree-dce
 Perform dead code elimination (DCE) on trees.  This flag is enabled by
@@ -7300,6 +7306,11 @@ mechanism for comparing types in C++ and
 bugs in the canonical type system are causing compilation failures,
 set this value to 0 to disable canonical types.
 
+@item cswtch-max-branch-ratio
+Switch initialization conversion will refuse to create arrays that are
+bigger than @option{cswtch-max-branch-ratio} times the number of
+branches in the switch.
+
 @item max-partial-antic-length
 Maximum length of the partial antic set computed during the tree
 partial redundancy elimination optimization (@option{-ftree-pre}) when
Index: gcc/tree-pass.h
===================================================================
--- gcc/tree-pass.h	(revision 133790)
+++ gcc/tree-pass.h	(working copy)
@@ -473,6 +473,7 @@ extern struct gimple_opt_pass pass_inlin
 extern struct gimple_opt_pass pass_apply_inline;
 extern struct gimple_opt_pass pass_all_early_optimizations;
 extern struct gimple_opt_pass pass_update_address_taken;
+extern struct gimple_opt_pass pass_convert_switch;
 
 /* The root of the compilation pass tree, once constructed.  */
 extern struct opt_pass *all_passes, *all_ipa_passes, *all_lowering_passes;
Index: gcc/params.h
===================================================================
--- gcc/params.h	(revision 133790)
+++ gcc/params.h	(working copy)
@@ -171,4 +171,6 @@ typedef enum compiler_param
   PARAM_VALUE (PARAM_L2_CACHE_SIZE)
 #define USE_CANONICAL_TYPES \
   PARAM_VALUE (PARAM_USE_CANONICAL_TYPES)
+#define CSWTCH_BRANCH_RATIO \
+  PARAM_VALUE (PARAM_CSWTCH_BRANCH_RATIO)
 #endif /* ! GCC_PARAMS_H */
Index: gcc/testsuite/gcc.dg/tree-ssa/cswtch.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/cswtch.c	(revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/cswtch.c	(revision 0)
@@ -0,0 +1,81 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-cswtch" } */
+/* { dg-do run } */
+
+extern void abort (void);
+
+static int X, Y;
+
+int check(int param)
+{
+  int a = 0;
+  int b = 1;
+  
+  switch (param) 
+    {
+    case -2:
+      a = 0;
+      b = -1;
+      break;
+    case 1:
+    case 2:
+      a = 8;
+      b = 6;
+      break;
+    case 3:
+      a = 9;
+      b = 5;
+      break;
+    case 6:
+      a = 10;
+      b = 4;
+      break;
+    default:
+      a = 16;
+      b = 1;
+    }
+  
+  X = a;
+  Y = b;
+  return 0;
+}
+
+void assertions(int a, int b)
+{
+  if (X != a || Y != b)
+    abort();  
+
+  return;
+}
+
+int main ()
+{
+  check (-10);
+  assertions (16, 1);
+
+  check (-2);
+  assertions (0, -1);
+
+  check(1);
+  assertions (8, 6);
+
+  check(2);
+  assertions (8, 6);
+
+  check(3);
+  assertions (9, 5);
+
+  check(5);
+  assertions (16, 1);
+
+  check(6);
+  assertions (10, 4);
+
+  check(12);
+  assertions (16, 1);
+
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump "Switch converted" "cswtch" } } */
+/* { dg-final { cleanup-tree-dump "cswtch" } } */
Index: gcc/opts.c
===================================================================
--- gcc/opts.c	(revision 133790)
+++ gcc/opts.c	(working copy)
@@ -887,6 +887,7 @@ decode_options (unsigned int argc, const
       flag_reorder_functions = 1;
       flag_tree_store_ccp = 1;
       flag_tree_vrp = 1;
+      flag_tree_cswtch = 1;
 
       if (!optimize_size)
 	{
Index: gcc/tree-cswtch.c
===================================================================
--- gcc/tree-cswtch.c	(revision 0)
+++ gcc/tree-cswtch.c	(revision 0)
@@ -0,0 +1,845 @@
+/* Switch Conversion converts variable initializations based on switch
+   statements to initializations from a static array.  
+   Copyright (C) 2006, 2008 Free Software Foundation, Inc.  
+   Contributed by Martin Jambor <jamborm@suse.cz>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 3, or (at your option) any
+later version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not, write to the Free
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA.  */
+
+/*  
+     Switch initialization conversion
+
+The following pass changes simple initializations of scalars in a switch
+statement into initializations from a static array.  Obviously, the values must
+be constant and known at compile time and a default branch must be
+provided.  For example, the following code:
+
+        int a,b;
+
+        switch (argc) 
+	{
+         case 1:
+         case 2:
+                a_1 = 8;
+                b_1 = 6;
+                break;
+         case 3:
+                a_2 = 9;
+                b_2 = 5;
+                break;
+         case 12:
+                a_3 = 10;
+                b_3 = 4;
+                break;
+         default:
+                a_4 = 16;
+                b_4 = 1;
+        }
+	a_5 = PHI <a_1, a_2, a_3, a_4>
+	b_5 = PHI <b_1, b_2, b_3, b_4>
+
+
+is changed into:
+
+        static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
+        static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16, 
+                                 16, 16, 10};
+
+        if (((unsigned) argc) - 1 < 11)
+          {
+	    a_6 = CSWTCH02[argc - 1];
+            b_6 = CSWTCH01[argc - 1];
+	  }
+	else
+	  {
+	    a_7 = 16;
+	    b_7 = 1;
+          }
+	  a_5 = PHI <a_6, a_7>
+	  b_b = PHI <b_6, b_7>
+
+There are further constraints.  Specifically, the range of values across all
+case labels must not be bigger than CSWTCH_BRANCH_RATIO (default eight) times
+the number of the actual switch branches.  
+*/
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include <signal.h>
+
+#include "line-map.h"
+#include "params.h"
+#include "flags.h"
+#include "tree.h"
+#include "basic-block.h"
+#include "tree-flow.h"
+#include "tree-flow-inline.h"
+#include "tree-ssa-operands.h"
+#include "output.h"
+#include "input.h"
+#include "tree-pass.h"
+#include "diagnostic.h"
+#include "tree-dump.h"
+
+/* The expression used to decide the switch branch.  (It is subsequently used
+   as the index to the created array.) */
+static tree index_expr;
+
+/* The following integer constants store the minimum value covered by the
+   cases.  */
+static tree range_min;
+
+/* The difference of between the above two numbers, i.e. The size of the array
+   that would have to be created by the transformation.  */
+static tree range_size;
+
+/* Basic block that contains the actual SWITCH_EXPR.  */
+static basic_block switch_bb;
+
+/* All branches of the switch statement must have a single successor stored in
+   the following variable.  */
+static basic_block final_bb;
+
+/* Number of phi nodes in the final bb (that we'll be replacing).  */
+static int phi_count;
+
+/* Array of default values, n the same order as phi nodes.  */
+static tree *default_values;
+
+/* Constructors of new static arrays.  */
+static VEC (constructor_elt, gc) **constructors;
+				 
+/* Array of ssa names that are initialized with a value from a new static
+   array.  */
+static tree *target_inbound_names;
+
+/* Array of ssa names that are initialized with the default value if the switch
+   expression is out of range.  */
+static tree *target_outbound_names;
+
+/* The probability of the default edge in the replaced switch.  */
+static int default_prob;
+
+/* The count of the default edge in the replaced switch.  */
+static gcov_type default_count;
+
+/* Combined count of all other (non-default) edges in the replaced switch.  */
+static gcov_type other_count;
+
+/* The last load statement that loads a temporary from a new static array.  */
+static tree arr_ref_first;
+
+/* The last load statement that loads a temporary from a new static array.  */
+static tree arr_ref_last;
+
+/* String reason why the case wasn't a good candidate that is written to the
+   dump file, if there is one.  */
+static const char *reason;
+
+				 
+
+
+/* Checks whether the range given by individual case statements isn't too big
+   and whether the number of branches actually satisfy the size of the new
+   array.  */
+static bool 
+check_range (tree swtch)
+{
+  tree min_case, max_case;
+  tree cases = SWITCH_LABELS (swtch);
+  int branch_num = TREE_VEC_LENGTH (cases);
+  tree range_max;
+
+  /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
+     is a default label which is the last in the vector.  */
+
+  min_case = TREE_VEC_ELT (cases, 0);
+  range_min = CASE_LOW (min_case);
+
+  gcc_assert (branch_num > 1);
+  max_case = TREE_VEC_ELT (cases, branch_num - 2);
+  if (CASE_HIGH (max_case) != NULL_TREE)
+    range_max = CASE_HIGH (max_case);
+  else
+    range_max = CASE_LOW (max_case);
+
+  gcc_assert (range_min);
+  gcc_assert (range_max);
+  
+  range_size = int_const_binop (MINUS_EXPR, range_max, range_min, 0);
+
+  gcc_assert (range_size);
+  if (!host_integerp (range_size, 1))
+    {
+      reason = "index range way too large or otherwise unusable.\n";
+      return false; 
+    }
+
+  if ((unsigned HOST_WIDE_INT) tree_low_cst (range_size, 1) 
+      > ((unsigned) branch_num * CSWTCH_BRANCH_RATIO))
+    {
+      reason = "the maximum range-branch ratio exceeded.";
+      return false;
+    }
+
+  return true;
+}
+
+/* Checks the given cs switch case whether it is suitable for conversion
+   (whether all but the default basic blocks are empty and so on).  If it is,
+   adds the case to the branch list along with values for the defined variables
+   and returns true.  Otherwise returns false.  */
+static bool 
+check_process_case (tree cs)
+{
+  tree ldecl;
+  basic_block label_bb, following_bb;
+  edge e;
+
+  ldecl = CASE_LABEL (cs);
+  label_bb = label_to_block (ldecl);
+
+  e = find_edge (switch_bb, label_bb);
+  gcc_assert (e);
+
+  if (CASE_LOW (cs) == NULL_TREE) 
+    {
+      /* default branch */
+      default_prob = e->probability;
+      default_count = e->count;
+    }
+  else
+    other_count += e->count;
+  
+  if (!label_bb)
+    {
+      reason = "  Bad case - cs BB  label is NULL\n";
+      return false;
+    }
+
+  if (!single_pred_p (label_bb))
+    {
+      if (final_bb && final_bb != label_bb)
+	{
+	  reason = "  Bad case - a non-final BB has two predecessors\n";
+	  return false; /* sth complex going on in this branch  */
+	}
+
+      following_bb = label_bb;
+    }
+  else
+    {
+      if (!empty_block_p (label_bb))
+	{
+	  reason = "  Bad case - a non-final BB not empty\n";
+	  return false;
+	}
+
+      e = single_succ_edge (label_bb);
+      following_bb = single_succ (label_bb);
+    }
+
+  if (!final_bb) 
+    final_bb = following_bb;
+  else if (final_bb != following_bb)
+    {
+      reason = "  Bad case - different final BB\n";
+      return false; /* the only successor is not common for all the branches */
+    }
+
+  return true;
+}
+
+/* check_final_bb() checks whether all required values in phi nodes in final_bb
+   are constants.  Required values are those that correspond to a basic block
+   which is a part of the examined switch statement.  It returns true if the
+   phi nodes are OK, otherwise false.  */
+static bool
+check_final_bb (void)
+{
+  tree phi;
+
+  phi_count = 0;
+  for (phi = phi_nodes (final_bb); phi; phi = PHI_CHAIN (phi)) 
+    {
+      int i;
+
+      phi_count++;
+
+      for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+	{
+	  basic_block bb = PHI_ARG_EDGE (phi, i)->src;
+	  
+	  if ((bb == switch_bb 
+	       || (single_pred_p (bb) && single_pred (bb) == switch_bb))
+	      && !is_gimple_min_invariant (PHI_ARG_ELT (phi, i).def))
+	    {
+	      reason = "   Non-invariant value from a case\n";
+	      return false; 		/* non invariant argument */
+	    }
+	}
+    }
+
+  return true;
+}
+
+/* create_temp_arrays() allocates default_values, target_{in,out}_names and
+   constructors arrays.  The last one is also populated with pointers to
+   vectors that will become constructors of new arrays.  */
+static void
+create_temp_arrays (void)
+{
+  int i;
+
+  default_values = xcalloc (phi_count, sizeof (tree));
+  constructors = xcalloc (phi_count, sizeof (tree));
+  target_inbound_names = xcalloc (phi_count, sizeof (tree));
+  target_outbound_names = xcalloc (phi_count, sizeof (tree));
+
+  for (i = 0; i < phi_count; i++)
+    {
+      constructors[i] = VEC_alloc (constructor_elt, gc, 
+				   tree_low_cst (range_size, 1) + 1);
+    }
+}
+
+/* free_temp_arrays() frees the arrays created by create_temp_arrays().  The
+   vectors that are created by that function are not freed here, however,
+   because they have already become the constructors and must be preserved.  */
+static void
+free_temp_arrays (void)
+{
+  free (constructors);
+  free (default_values);
+  free (target_inbound_names);
+  free (target_outbound_names);
+}
+
+/* gather_default_values() populates the array of default values in the order
+   of phi nodes.  */
+static void
+gather_default_values (tree default_case)
+{
+  tree phi;
+  basic_block bb = label_to_block (CASE_LABEL (default_case));
+  edge e;
+  int i;
+
+  gcc_assert (CASE_LOW (default_case) == NULL_TREE);
+
+  if (bb == final_bb)
+    e = find_edge (switch_bb, bb);
+  else
+    e = single_succ_edge (bb);
+  
+  for (phi = phi_nodes (final_bb), i = 0; phi; phi = PHI_CHAIN (phi), i++) 
+    {
+      tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
+      gcc_assert (val);
+      default_values[i] = val;
+    }
+}
+
+/* build_constructors() populates the vectors in the constructors array with
+   future contents of the static arrays.  The vectors are populated in the
+   order of phi nodes.  */
+static void
+build_constructors (tree swtch)
+{
+  int i;
+  tree cases = SWITCH_LABELS (swtch);
+  tree pos = range_min;
+  
+  for (i = 0; i < TREE_VEC_LENGTH (cases) - 1; i++) 
+    {
+      tree cs = TREE_VEC_ELT (cases, i);
+      basic_block bb = label_to_block (CASE_LABEL (cs));
+      edge e;
+      tree phi, high;
+      int j;
+
+      if (bb == final_bb)
+	e = find_edge (switch_bb, bb);
+      else
+	e = single_succ_edge (bb);
+      gcc_assert (e);
+
+      while (tree_int_cst_lt (pos, CASE_LOW (cs)))
+	{
+	  int k;
+	  for (k = 0; k < phi_count; k++)
+	    {
+	      constructor_elt *elt;
+
+	      elt = VEC_quick_push (constructor_elt, 
+				    constructors[k], NULL);
+	      elt->index = int_const_binop (MINUS_EXPR, pos, range_min, 0);
+	      elt->value = default_values[k];
+	    }
+
+	  pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0);
+	}
+      gcc_assert (tree_int_cst_equal (pos, CASE_LOW(cs)));
+      
+      j = 0;
+      if (CASE_HIGH (cs))
+	high = CASE_HIGH (cs);
+      else
+	high = CASE_LOW(cs);
+      for (phi = phi_nodes (final_bb); phi; phi = PHI_CHAIN (phi)) 
+	{
+	  tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
+	  pos = CASE_LOW (cs);
+
+	  while (!tree_int_cst_lt (high, pos))
+	    {
+	      constructor_elt *elt;
+
+	      elt = VEC_quick_push (constructor_elt, 
+				    constructors[j], NULL);
+	      elt->index = int_const_binop (MINUS_EXPR, pos, range_min, 0);
+	      elt->value = val;
+	      
+	      pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0);
+	    }
+	  j++;
+	}
+    }
+}
+
+/* build_one_array() creates an appropriate array type and declaration and
+   assembles a static array variable.  It also creates a load statement that
+   initializes the variable in question with a value from the static array.  */
+static void 
+build_one_array (tree swtch, int num, tree arr_index_type, tree phi, tree tidx)
+{ 
+  tree array_type;
+  tree ctor;
+  tree decl;
+  tree value_type;
+  tree name;
+  tree fetch, load;
+  block_stmt_iterator bsi;
+
+  gcc_assert (default_values[num]);
+  value_type = TREE_TYPE (default_values[num]);
+  array_type = build_array_type (value_type, arr_index_type); 
+
+  ctor = build_constructor (array_type, constructors[num]);
+  TREE_CONSTANT (ctor) = true;
+
+  decl = build_decl (VAR_DECL, NULL_TREE, array_type); 
+  TREE_STATIC (decl) = 1;
+  DECL_INITIAL (decl) = ctor;
+
+  DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
+  DECL_ARTIFICIAL (decl) = 1;
+  TREE_CONSTANT (decl) = 1;
+  add_referenced_var (decl);
+  assemble_variable (decl, 0, 0, 0);
+  mark_sym_for_renaming (decl);
+
+  name = make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi)), NULL_TREE);
+  target_inbound_names[num] = name;
+
+  fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE, 
+		  NULL_TREE); 
+  load = build2 (GIMPLE_MODIFY_STMT, void_type_node, name, fetch);
+  SSA_NAME_DEF_STMT (name) = load;
+
+  bsi = bsi_for_stmt (swtch);
+  bsi_insert_before (&bsi, load, BSI_SAME_STMT);
+  mark_symbols_for_renaming (load);
+
+  arr_ref_last = load;
+  
+  return;
+}
+
+/* Builds and initializes static arrays initialized with values gathered from
+   the switch statement.  Also creates statements that assign a value.  */
+static void 
+build_arrays (tree swtch)
+{
+  tree arr_index_type;
+  tree tidx, sub;
+  block_stmt_iterator bsi;
+  tree phi = phi_nodes (final_bb);
+  int i;
+    
+  arr_index_type = build_index_type (range_size);
+  tidx = make_rename_temp (arr_index_type, "csti");
+  sub = build2 (MINUS_EXPR, TREE_TYPE (index_expr), index_expr, 
+		fold_convert (TREE_TYPE (index_expr), range_min));
+  sub = build2 (GIMPLE_MODIFY_STMT, void_type_node, tidx, sub);
+  
+  bsi = bsi_for_stmt (swtch);
+  bsi_insert_before (&bsi, sub, BSI_SAME_STMT);
+  mark_symbols_for_renaming (sub);
+  arr_ref_first = sub;
+
+  for (phi = phi_nodes (final_bb), i = 0; phi; phi = PHI_CHAIN (phi), i++) 
+    build_one_array (swtch, i, arr_index_type, phi, tidx);
+  
+  return;
+}
+
+/* Generates and appropriately inserts loads of default values at the given
+   position.  Returns the last inserted statement.  */
+static tree 
+gen_def_assigns (block_stmt_iterator *bsi)
+{
+  int i;
+  tree assign = NULL_TREE;
+
+  for (i = 0; i < phi_count; i++)
+    {
+      tree name = make_ssa_name (SSA_NAME_VAR (target_inbound_names[i]), 
+				 NULL_TREE);
+
+      target_outbound_names[i] = name;
+      assign = build2 (GIMPLE_MODIFY_STMT, void_type_node, name, 
+		       default_values[i]);
+      SSA_NAME_DEF_STMT (name) = assign;
+      bsi_insert_before (bsi, assign, BSI_SAME_STMT);
+      find_new_referenced_vars (&assign);
+      mark_symbols_for_renaming (assign);
+    }
+  return assign;
+}
+
+/* Deletes the unused bbs and edges that now contain the switch statement and
+   its empty branch bbs.  */
+static void 
+prune_bbs (basic_block bbd, basic_block final)
+{
+  edge_iterator ei;
+  edge e;
+  
+  for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
+    {
+      basic_block bb;
+      bb = e->dest;
+      remove_edge (e);
+      if (bb != final) 
+	delete_basic_block (bb);
+    }
+  delete_basic_block (bbd);
+}
+
+/* fix_phi_nodes() adds values to phi nodes in final_bb for the two new
+   edges.  e1f is the edge from the basic block loading values from an array and
+   e2f from the basic block loading default values.  */
+static void 
+fix_phi_nodes (edge e1f, edge e2f, basic_block bbf)
+{
+  tree phi;
+  int i;
+
+  for (phi = phi_nodes (bbf), i = 0; phi; phi = PHI_CHAIN (phi), i++) 
+    {
+      add_phi_arg (phi, target_inbound_names[i], e1f);
+      add_phi_arg (phi, target_outbound_names[i], e2f);
+    }
+
+}
+
+/* Creates a check whether the switch expression value actually falls into the
+   range given by all the cases.  If it not, the temporaries are loaded with
+   default values instead.
+   
+   bb0 is the bb with the switch statement, however, we'll end it with a
+       condition instead.
+
+   bb1 is the bb to be used when the range check went ok.  It is derived from
+       the switch BB
+
+   bb2 is the bb taken when the expression evaluated outside of the range
+       covered by the created arrays.  It is populated by loads of default
+       values.
+
+   bbF is a fall through for both bb1 and bb2 and contains exactly what
+       originally followed the switch statement.
+
+   bbD contains the switch statement (in the end).  It is unreachable but we
+       still need to strip off its edges.
+*/
+static void 
+gen_inbound_check (tree swtch)
+{
+  tree label_decl1 = create_artificial_label ();
+  tree label_decl2 = create_artificial_label ();
+  tree label_decl3 = create_artificial_label ();
+  tree label1, label2, label3;
+
+  tree utype = unsigned_type_for (TREE_TYPE (index_expr));
+  tree tmp_u;
+  tree cast, cast_assign;
+  tree ulb, minus, minus_assign;
+  tree bound;
+  
+  tree if_expr;
+
+  tree last_assign;
+  block_stmt_iterator bsi;
+  basic_block bb0, bb1, bb2, bbf, bbd;
+  edge e01, e02, e21, e1d, e1f, e2f;
+
+  gcc_assert (default_values);
+  bb0 = bb_for_stmt (swtch);
+
+  /* (end of) block 0 */
+  bsi = bsi_for_stmt (arr_ref_first);
+  tmp_u = make_rename_temp (utype, "csui");
+  
+  cast = build1 (NOP_EXPR, utype, index_expr);
+  cast_assign = build2 (GIMPLE_MODIFY_STMT, void_type_node, tmp_u, cast);
+  find_new_referenced_vars (&cast_assign);
+  bsi_insert_before (&bsi, cast_assign, BSI_SAME_STMT);
+  mark_symbols_for_renaming (cast_assign);
+  
+  ulb = fold_convert (utype, range_min);
+  minus = build2 (MINUS_EXPR, utype, tmp_u, ulb);
+  minus_assign = build2 (GIMPLE_MODIFY_STMT, void_type_node, tmp_u, minus);
+  find_new_referenced_vars (&minus_assign);
+  bsi_insert_before (&bsi, minus_assign, BSI_SAME_STMT);
+  mark_symbols_for_renaming (minus_assign);
+
+  bound = fold_convert (utype, range_size);
+
+  if_expr = build3 (COND_EXPR, void_type_node,
+		    build2 (LE_EXPR, boolean_type_node, tmp_u, bound),
+		    NULL_TREE, NULL_TREE);
+  
+  find_new_referenced_vars (&if_expr);
+  bsi_insert_before (&bsi, if_expr, BSI_SAME_STMT);
+  mark_symbols_for_renaming (if_expr);
+  
+  /* block 2 */
+  bsi = bsi_for_stmt (arr_ref_first);
+  label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
+  bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
+  last_assign = gen_def_assigns (&bsi);
+
+  /* block 1 */
+  bsi = bsi_for_stmt (arr_ref_first);
+  label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
+  bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
+
+  /* block F */
+  bsi = bsi_start (final_bb);
+  label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
+  bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
+
+  /* cfg fix */
+  e02 = split_block (bb0, if_expr);
+  bb2 = e02->dest;
+
+  e21 = split_block (bb2, last_assign);
+  bb1 = e21->dest;
+  remove_edge (e21);
+
+  e1d = split_block (bb1, arr_ref_last);
+  bbd = e1d->dest;
+  remove_edge (e1d);
+
+  /* flags and profiles of the edge for in-range values */
+  e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
+  e01->probability = REG_BR_PROB_BASE - default_prob;
+  e01->count = other_count;
+
+  /* flags and profiles of the edge taking care of out-of-range values */
+  e02->flags &= ~EDGE_FALLTHRU;
+  e02->flags |= EDGE_FALSE_VALUE;
+  e02->probability = default_prob;
+  e02->count = default_count;
+
+  bbf = final_bb;
+
+  e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
+  e1f->probability = REG_BR_PROB_BASE;
+  e1f->count = other_count;
+
+  e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
+  e2f->probability = REG_BR_PROB_BASE;
+  e2f->count = default_count;
+
+  /* frequencies of the new BBs */
+  bb1->frequency = EDGE_FREQUENCY (e01);
+  bb2->frequency = EDGE_FREQUENCY (e02);
+  bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f);
+  
+  prune_bbs (bbd, final_bb); /* to keep calc_dfs_tree() in dominance.c
+				happy */
+  
+  fix_phi_nodes (e1f, e2f, bbf);
+
+  free_dominance_info (CDI_DOMINATORS);
+  free_dominance_info (CDI_POST_DOMINATORS);
+}
+
+/* process_switch() is invoked on every switch statement and runs the individual
+   phases of switch conversion on it one after another until one fails or the
+   conversion is completed.  */
+static bool 
+process_switch (tree swtch)
+{
+  int i;
+  tree cases;
+  tree index_type;
+
+  /* operand 2 is either NULL_TREE or a vector of cases (stmt.c)*/
+  if (TREE_OPERAND (swtch, 2) == NULL_TREE) 
+    {
+      reason = "swtch has no labels\n";
+      return false;
+    }
+
+  /* Comment from stmt.c: 
+     The switch body is lowered in gimplify.c, we should never have switches
+     with a non-NULL SWITCH_BODY here.  */
+  gcc_assert (!SWITCH_BODY (swtch));
+
+  cases = SWITCH_LABELS (swtch);
+  final_bb = NULL;
+  switch_bb = bb_for_stmt (swtch);
+  index_expr = SWITCH_COND (swtch); 
+  index_type = TREE_TYPE (index_expr);
+  arr_ref_first = NULL_TREE;
+  arr_ref_last = NULL_TREE;
+  default_prob = 0;
+  default_count = 0;
+  other_count = 0;
+
+  /* An ERROR_MARK occurs for various reasons including invalid data type.
+     (comment from stmt.c) */
+  if (index_type == error_mark_node) 
+    {
+      reason = "index error.\n";
+      return false; 
+    }
+
+  /* check the case label values are within reasonable range:  */
+  if (!check_range (swtch))
+    return false;
+
+  /* for all the cases, see whether they are empty, the assignments they
+     represent constant and so on...  */
+  for (i = 0; i < TREE_VEC_LENGTH (cases); i++) 
+    {
+      tree part_case = TREE_VEC_ELT (cases, i);
+      if (!check_process_case (part_case)) 
+	{
+	  if (dump_file) 
+	    fprintf (dump_file, "Processing of case %i failed\n", i);
+	  return false;
+	}
+    }
+
+  if (!check_final_bb ())
+    return false;
+
+  /* at this point all checks have passed and we can proceed with the
+     transformation.  */
+  
+  create_temp_arrays ();
+  gather_default_values (TREE_VEC_ELT (cases, TREE_VEC_LENGTH (cases) - 1));
+  build_constructors (swtch);
+  
+  build_arrays (swtch); /* build the static arrays and assignments */
+  gen_inbound_check (swtch); 	/* build the bound check */
+
+  /* cleanup: */
+  free_temp_arrays ();
+  return true;
+}
+
+/* The main function of the pass scans statements for switches and invokes
+   process_switch on them.  */
+static unsigned int 
+do_convswitch (void)
+{
+  basic_block bb;
+  
+  FOR_EACH_BB (bb) 
+  {
+    tree stmt = last_stmt (bb);
+    if (stmt && TREE_CODE (stmt) == SWITCH_EXPR) 
+      {
+	expanded_location loc = expand_location (EXPR_LOCATION (stmt));
+
+	if (dump_file)
+	  {
+	    fprintf (dump_file, "beginning to process the following "
+		     "SWITCH statement (%s:%d) : ------- \n",
+		     loc.file, loc.line);
+	    print_generic_stmt (dump_file, stmt, 2);
+	    fprintf (dump_file, "\n");
+	  }
+
+	reason = NULL;
+	if (process_switch (stmt))
+	  {
+	    if (dump_file)
+	      {
+		fprintf (dump_file, "Switch converted\n");
+		fprintf (dump_file, "--------------------------------\n");
+	      }
+	  }
+	else
+	  {
+	    if (dump_file)
+	      {
+		gcc_assert (reason);
+		fprintf (dump_file, "Bailing out - ");
+		fprintf (dump_file, reason);
+		fprintf (dump_file, "--------------------------------\n");
+	      }
+	  }
+      }
+  }
+
+  return 0;
+}
+
+static bool
+convswitch_gate (void)
+{
+  return flag_tree_cswtch != 0;
+}
+
+struct gimple_opt_pass pass_convert_switch =
+{
+ {
+  GIMPLE_PASS,
+  "cswtch",				/* name */
+  convswitch_gate,        		/* gate */
+  do_convswitch,			/* execute */
+  NULL,					/* sub */
+  NULL,					/* next */
+  0,					/* static_pass_number */
+  0,			        	/* tv_id */
+  PROP_cfg | PROP_ssa,	                /* properties_required */
+  0,					/* properties_provided */
+  0,					/* properties_destroyed */
+  0,					/* todo_flags_start */
+  TODO_update_ssa | TODO_dump_func 
+  | TODO_ggc_collect | TODO_verify_ssa  /* todo_flags_finish */
+ }
+};
Index: gcc/common.opt
===================================================================
--- gcc/common.opt	(revision 133790)
+++ gcc/common.opt	(working copy)
@@ -1099,6 +1099,10 @@ ftree-cselim
 Common Report Var(flag_tree_cselim) Init(2) Optimization
 Transform condition stores into unconditional ones
 
+ftree-cswtch
+Common Report Var(flag_tree_cswtch) Optimization
+Perform conversions of switch initializations.
+
 ftree-dce
 Common Report Var(flag_tree_dce) Optimization
 Enable SSA dead code elimination optimization on trees
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in	(revision 133790)
+++ gcc/Makefile.in	(working copy)
@@ -1169,6 +1169,7 @@ OBJS-common = \
 	tree-profile.o \
 	tree-scalar-evolution.o \
 	tree-sra.o \
+	tree-cswtch.o \
 	tree-ssa-address.o \
 	tree-ssa-alias.o \
 	tree-ssa-alias-warnings.o \
@@ -2597,6 +2598,11 @@ tree-sra.o : tree-sra.c $(CONFIG_H) $(SY
     $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) $(TREE_GIMPLE_H) \
     langhooks.h tree-pass.h $(FLAGS_H) $(EXPR_H) $(BASIC_BLOCK_H) \
     bitmap.h $(GGC_H) hard-reg-set.h $(OBSTACK_H) $(PARAMS_H) $(TARGET_H)
+tree-cswtch.o : tree-cswtch.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) \
+    $(TM_P_H) $(TREE_FLOW_H) $(DIAGNOSTIC_H) $(TREE_INLINE_H) \
+    $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) $(TREE_GIMPLE_H) \
+    tree-pass.h $(FLAGS_H) $(EXPR_H) $(BASIC_BLOCK_H) output.h \
+    $(GGC_H) $(OBSTACK_H) $(PARAMS_H) $(CPPLIB_H) $(PARAMS_H)
 tree-complex.o : tree-complex.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TREE_H) \
     $(TM_H) $(RTL_H) $(REAL_H) $(FLAGS_H) $(TREE_FLOW_H) $(TREE_GIMPLE_H) \
     tree-iterator.h tree-pass.h tree-ssa-propagate.h $(DIAGNOSTIC_H)
Index: gcc/passes.c
===================================================================
--- gcc/passes.c	(revision 133790)
+++ gcc/passes.c	(working copy)
@@ -536,6 +536,7 @@ init_optimization_passes (void)
 	  NEXT_PASS (pass_update_address_taken);
 	  NEXT_PASS (pass_simple_dse);
 	  NEXT_PASS (pass_tail_recursion);
+	  NEXT_PASS (pass_convert_switch);
           NEXT_PASS (pass_profile);
 	  NEXT_PASS (pass_release_ssa_names);
 	}
Index: gcc/params.def
===================================================================
--- gcc/params.def	(revision 133790)
+++ gcc/params.def	(working copy)
@@ -729,6 +729,15 @@ DEFPARAM (PARAM_DF_DOUBLE_QUEUE_THRESHOL
 	  "Multiplier used for determining the double-queueing threshold",
 	  2, 0, 0)
 
+/* Switch initialization conversion will refuse to create arrays that are
+   bigger than this parameter times the number of switch branches.  */
+
+DEFPARAM (PARAM_CSWTCH_BRANCH_RATIO,
+	  "cswtch-max-branch-ratio",
+	  "The maximum ratio between array size and switch branches for "
+	  "a switch conversion to take place",
+	  8, 1, 0)
+
 /*
 Local variables:
 mode:c

Re: [PATCH, middle-end] Switch initializations conversion (take four.1)

[Diego Novillo]

On Thu, Apr 3, 2008 at 08:32, Martin Jambor <mjambor@suse.cz> wrote:

>  Can anyone review the patch, please? Thank you very much in advance.

I will.


Diego.

Re: [PATCH, middle-end] Switch initializations conversion (take four.1)

[Richard Guenther]

On Thu, Apr 3, 2008 at 1:32 PM, Martin Jambor <mjambor@suse.cz> wrote:
> Hi,
>
>  in order  to reflect the  transition from struct  tree_opt_pass to
>  gimple_opt_pass,  I have  modified my  proposed  switch conversion
>  pass that I sent here more than a month ago in
>
>  http://gcc.gnu.org/ml/gcc-patches/2008-02/msg01468.html
>
>  I have re-bootstrapped and re-tested this on i686-pc-linux-gnu,
>  revision 133790, all languages including ADA.
>
>  Can anyone review the patch, please? Thank you very much in advance.

A few comments below.

>  Martin
>
>
>  The changelog stays the same:
>
>  2008-04-08  Martin Jambor  <mjambor@suse.cz>
>         * Makefile.in (tree-cswtch.o): Add.
>         (OBJS-common): Add tree-cswtch.o
>         * passes.c (init_optimization_passes): Add pass_convert_switch.
>         * tree-pass.h: Add a declaration of the structure describing
>         the new pass.
>         * tree-cswtch.c: New file.

IMHO abbreviations like cswtch are unneccessary for file names
(and options as well).  Please use tree-switch-conversion.c (or similar)
and -ftree-switch-conversion.

>         * gcc.dg/tree-ssa/cswtch.c: New testcase.
>         * common.opt (ftree-cswtch): New option.
>         * params.h (PARAM_CSWTCH_BRANCH_RATIO): New parameter.
>         * params.def (PARAM_CSWTCH_BRANCH_RATIO): New parameter.
>         * opts.c (decode_options): Set flag_tree_cswtch when
>         optimization level is >= 2.
>         * doc/invoke.texi (Optimize Options): Added description of
>         -ftree-cswtch
>         (Optimize Options): Added description of cswtch-max-branch-ratio
>
>
>  Index: gcc/doc/invoke.texi
>  ===================================================================
>  --- gcc/doc/invoke.texi (revision 133790)
>  +++ gcc/doc/invoke.texi (working copy)
>  @@ -353,7 +353,7 @@ Objective-C and Objective-C++ Dialects}.
>   -fsignaling-nans -fsingle-precision-constant -fsplit-ivs-in-unroller @gol
>   -fsplit-wide-types -fstack-protector -fstack-protector-all @gol
>   -fstrict-aliasing -fstrict-overflow -fthread-jumps -ftracer -ftree-ccp @gol
>  --ftree-ch -ftree-copy-prop -ftree-copyrename -ftree-dce @gol
>  +-ftree-ch -ftree-copy-prop -ftree-copyrename -ftree-cswtch -ftree-dce @gol
>   -ftree-dominator-opts -ftree-dse -ftree-fre -ftree-loop-im @gol
>   -ftree-loop-distribution @gol
>   -ftree-loop-ivcanon -ftree-loop-linear -ftree-loop-optimize @gol
>  @@ -5160,6 +5160,7 @@ also turns on the following optimization
>   -fsched-interblock  -fsched-spec @gol
>   -fschedule-insns  -fschedule-insns2 @gol
>   -fstrict-aliasing -fstrict-overflow @gol
>  +-ftree-cswtch @gol
>   -ftree-pre @gol
>   -ftree-vrp}
>
>  @@ -5839,6 +5840,11 @@ pass operates on both local scalar varia
>   loads (global variables, structures, arrays, etc).  This flag is
>   enabled by default at @option{-O2} and higher.
>
>  +@item -ftree-cswtch
>  +Perform conversion of simple initializations in a switch to
>  +initializations from a scalar array.  This flag is enabled by default
>  +at @option{-O2} and higher.
>  +
>   @item -ftree-dce
>   @opindex ftree-dce
>   Perform dead code elimination (DCE) on trees.  This flag is enabled by
>  @@ -7300,6 +7306,11 @@ mechanism for comparing types in C++ and
>   bugs in the canonical type system are causing compilation failures,
>   set this value to 0 to disable canonical types.
>
>  +@item cswtch-max-branch-ratio
>  +Switch initialization conversion will refuse to create arrays that are
>  +bigger than @option{cswtch-max-branch-ratio} times the number of
>  +branches in the switch.
>  +
>   @item max-partial-antic-length
>   Maximum length of the partial antic set computed during the tree
>   partial redundancy elimination optimization (@option{-ftree-pre}) when
>  Index: gcc/tree-pass.h
>  ===================================================================
>  --- gcc/tree-pass.h     (revision 133790)
>  +++ gcc/tree-pass.h     (working copy)
>  @@ -473,6 +473,7 @@ extern struct gimple_opt_pass pass_inlin
>   extern struct gimple_opt_pass pass_apply_inline;
>   extern struct gimple_opt_pass pass_all_early_optimizations;
>   extern struct gimple_opt_pass pass_update_address_taken;
>  +extern struct gimple_opt_pass pass_convert_switch;
>
>   /* The root of the compilation pass tree, once constructed.  */
>   extern struct opt_pass *all_passes, *all_ipa_passes, *all_lowering_passes;
>  Index: gcc/params.h
>  ===================================================================
>  --- gcc/params.h        (revision 133790)
>  +++ gcc/params.h        (working copy)
>  @@ -171,4 +171,6 @@ typedef enum compiler_param
>    PARAM_VALUE (PARAM_L2_CACHE_SIZE)
>   #define USE_CANONICAL_TYPES \
>    PARAM_VALUE (PARAM_USE_CANONICAL_TYPES)
>  +#define CSWTCH_BRANCH_RATIO \
>  +  PARAM_VALUE (PARAM_CSWTCH_BRANCH_RATIO)
>   #endif /* ! GCC_PARAMS_H */
>  Index: gcc/testsuite/gcc.dg/tree-ssa/cswtch.c
>  ===================================================================
>  --- gcc/testsuite/gcc.dg/tree-ssa/cswtch.c      (revision 0)
>  +++ gcc/testsuite/gcc.dg/tree-ssa/cswtch.c      (revision 0)
>  @@ -0,0 +1,81 @@
>  +/* { dg-do compile } */
>  +/* { dg-options "-O2 -fdump-tree-cswtch" } */
>  +/* { dg-do run } */
>  +
>  +extern void abort (void);
>  +
>  +static int X, Y;
>  +
>  +int check(int param)
>  +{
>  +  int a = 0;
>  +  int b = 1;
>  +
>  +  switch (param)
>  +    {
>  +    case -2:
>  +      a = 0;
>  +      b = -1;
>  +      break;
>  +    case 1:
>  +    case 2:
>  +      a = 8;
>  +      b = 6;
>  +      break;
>  +    case 3:
>  +      a = 9;
>  +      b = 5;
>  +      break;
>  +    case 6:
>  +      a = 10;
>  +      b = 4;
>  +      break;
>  +    default:
>  +      a = 16;
>  +      b = 1;
>  +    }
>  +
>  +  X = a;
>  +  Y = b;
>  +  return 0;
>  +}
>  +
>  +void assertions(int a, int b)
>  +{
>  +  if (X != a || Y != b)
>  +    abort();
>  +
>  +  return;
>  +}
>  +
>  +int main ()
>  +{
>  +  check (-10);
>  +  assertions (16, 1);
>  +
>  +  check (-2);
>  +  assertions (0, -1);
>  +
>  +  check(1);
>  +  assertions (8, 6);
>  +
>  +  check(2);
>  +  assertions (8, 6);
>  +
>  +  check(3);
>  +  assertions (9, 5);
>  +
>  +  check(5);
>  +  assertions (16, 1);
>  +
>  +  check(6);
>  +  assertions (10, 4);
>  +
>  +  check(12);
>  +  assertions (16, 1);
>  +
>  +  return 0;
>  +}
>  +
>  +/* { dg-final { scan-tree-dump "Switch converted" "cswtch" } } */
>  +/* { dg-final { cleanup-tree-dump "cswtch" } } */
>  Index: gcc/opts.c
>  ===================================================================
>  --- gcc/opts.c  (revision 133790)
>  +++ gcc/opts.c  (working copy)
>  @@ -887,6 +887,7 @@ decode_options (unsigned int argc, const
>        flag_reorder_functions = 1;
>        flag_tree_store_ccp = 1;
>        flag_tree_vrp = 1;
>  +      flag_tree_cswtch = 1;
>
>        if (!optimize_size)
>         {
>  Index: gcc/tree-cswtch.c
>  ===================================================================
>  --- gcc/tree-cswtch.c   (revision 0)
>  +++ gcc/tree-cswtch.c   (revision 0)
>  @@ -0,0 +1,845 @@
>  +/* Switch Conversion converts variable initializations based on switch
>  +   statements to initializations from a static array.
>  +   Copyright (C) 2006, 2008 Free Software Foundation, Inc.
>  +   Contributed by Martin Jambor <jamborm@suse.cz>
>  +
>  +This file is part of GCC.
>  +
>  +GCC is free software; you can redistribute it and/or modify it
>  +under the terms of the GNU General Public License as published by the
>  +Free Software Foundation; either version 3, or (at your option) any
>  +later version.
>  +
>  +GCC is distributed in the hope that it will be useful, but WITHOUT
>  +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
>  +FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
>  +for more details.
>  +
>  +You should have received a copy of the GNU General Public License
>  +along with GCC; see the file COPYING3.  If not, write to the Free
>  +Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
>  +02110-1301, USA.  */
>  +
>  +/*
>  +     Switch initialization conversion
>  +
>  +The following pass changes simple initializations of scalars in a switch
>  +statement into initializations from a static array.  Obviously, the values must
>  +be constant and known at compile time and a default branch must be
>  +provided.  For example, the following code:
>  +
>  +        int a,b;
>  +
>  +        switch (argc)
>  +       {
>  +         case 1:
>  +         case 2:
>  +                a_1 = 8;
>  +                b_1 = 6;
>  +                break;
>  +         case 3:
>  +                a_2 = 9;
>  +                b_2 = 5;
>  +                break;
>  +         case 12:
>  +                a_3 = 10;
>  +                b_3 = 4;
>  +                break;
>  +         default:
>  +                a_4 = 16;
>  +                b_4 = 1;
>  +        }
>  +       a_5 = PHI <a_1, a_2, a_3, a_4>
>  +       b_5 = PHI <b_1, b_2, b_3, b_4>
>  +
>  +
>  +is changed into:
>  +
>  +        static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
>  +        static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
>  +                                 16, 16, 10};
>  +
>  +        if (((unsigned) argc) - 1 < 11)
>  +          {
>  +           a_6 = CSWTCH02[argc - 1];
>  +            b_6 = CSWTCH01[argc - 1];
>  +         }
>  +       else
>  +         {
>  +           a_7 = 16;
>  +           b_7 = 1;
>  +          }
>  +         a_5 = PHI <a_6, a_7>
>  +         b_b = PHI <b_6, b_7>
>  +
>  +There are further constraints.  Specifically, the range of values across all
>  +case labels must not be bigger than CSWTCH_BRANCH_RATIO (default eight) times
>  +the number of the actual switch branches.
>  +*/
>  +
>  +#include "config.h"
>  +#include "system.h"
>  +#include "coretypes.h"
>  +#include "tm.h"
>  +#include <signal.h>
>  +
>  +#include "line-map.h"
>  +#include "params.h"
>  +#include "flags.h"
>  +#include "tree.h"
>  +#include "basic-block.h"
>  +#include "tree-flow.h"
>  +#include "tree-flow-inline.h"
>  +#include "tree-ssa-operands.h"
>  +#include "output.h"
>  +#include "input.h"
>  +#include "tree-pass.h"
>  +#include "diagnostic.h"
>  +#include "tree-dump.h"
>  +
>  +/* The expression used to decide the switch branch.  (It is subsequently used
>  +   as the index to the created array.) */
>  +static tree index_expr;
>  +
>  +/* The following integer constants store the minimum value covered by the
>  +   cases.  */
>  +static tree range_min;
>  +
>  +/* The difference of between the above two numbers, i.e. The size of the array
>  +   that would have to be created by the transformation.  */
>  +static tree range_size;
>  +
>  +/* Basic block that contains the actual SWITCH_EXPR.  */
>  +static basic_block switch_bb;
>  +
>  +/* All branches of the switch statement must have a single successor stored in
>  +   the following variable.  */
>  +static basic_block final_bb;
>  +
>  +/* Number of phi nodes in the final bb (that we'll be replacing).  */
>  +static int phi_count;
>  +
>  +/* Array of default values, n the same order as phi nodes.  */
>  +static tree *default_values;
>  +
>  +/* Constructors of new static arrays.  */
>  +static VEC (constructor_elt, gc) **constructors;
>  +
>  +/* Array of ssa names that are initialized with a value from a new static
>  +   array.  */
>  +static tree *target_inbound_names;
>  +
>  +/* Array of ssa names that are initialized with the default value if the switch
>  +   expression is out of range.  */
>  +static tree *target_outbound_names;
>  +
>  +/* The probability of the default edge in the replaced switch.  */
>  +static int default_prob;
>  +
>  +/* The count of the default edge in the replaced switch.  */
>  +static gcov_type default_count;
>  +
>  +/* Combined count of all other (non-default) edges in the replaced switch.  */
>  +static gcov_type other_count;
>  +
>  +/* The last load statement that loads a temporary from a new static array.  */
>  +static tree arr_ref_first;
>  +
>  +/* The last load statement that loads a temporary from a new static array.  */
>  +static tree arr_ref_last;
>  +
>  +/* String reason why the case wasn't a good candidate that is written to the
>  +   dump file, if there is one.  */
>  +static const char *reason;

These are a lot of global statics - can you localize them where possible
or at least stick them into a structure?

>  +
>  +
>  +
>  +/* Checks whether the range given by individual case statements isn't too big
>  +   and whether the number of branches actually satisfy the size of the new
>  +   array.  */
>  +static bool
>  +check_range (tree swtch)
>  +{
>  +  tree min_case, max_case;
>  +  tree cases = SWITCH_LABELS (swtch);
>  +  int branch_num = TREE_VEC_LENGTH (cases);
>  +  tree range_max;
>  +
>  +  /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
>  +     is a default label which is the last in the vector.  */

This may be no longer true if the pass runs after the first VRP pass, as
that is now removing the default lablel if it was proved unreachable.

Thanks,
Richard.

Re: [PATCH, middle-end] Switch initializations conversion (take four.1)

[Roger Sayle]

>>  +/*
>>  +     Switch initialization conversion
>>  +
>>  +The following pass changes simple initializations of scalars in a 
>> switch
>>  +statement into initializations from a static array.  Obviously, the 
>> values must
>>  +be constant and known at compile time and a default branch must be
>>  +provided.  For example, the following code:
>>  +
>>  +        int a,b;
>>  +
>>  +        switch (argc)
>>  +       {
>>  +         case 1:
>>  +         case 2:
>>  +                a_1 = 8;
>>  +                b_1 = 6;
>>  +                break;
>>  +         case 3:
>>  +                a_2 = 9;
>>  +                b_2 = 5;
>>  +                break;
>>  +         case 12:
>>  +                a_3 = 10;
>>  +                b_3 = 4;
>>  +                break;
>>  +         default:
>>  +                a_4 = 16;
>>  +                b_4 = 1;
>>  +        }
>>  +       a_5 = PHI <a_1, a_2, a_3, a_4>
>>  +       b_5 = PHI <b_1, b_2, b_3, b_4>
>>  +
>>  +
>>  +is changed into:
>>  +
>>  +        static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 
>> 1, 4};
>>  +        static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 
>> 16, 16,
>>  +                                 16, 16, 10};
>>  +
>>  +        if (((unsigned) argc) - 1 < 11)
>>  +          {
>>  +           a_6 = CSWTCH02[argc - 1];
>>  +            b_6 = CSWTCH01[argc - 1];
>>  +         }
>>  +       else
>>  +         {
>>  +           a_7 = 16;
>>  +           b_7 = 1;
>>  +          }
>>  +         a_5 = PHI <a_6, a_7>
>>  +         b_b = PHI <b_6, b_7>
>>  +
>>  +There are further constraints.  Specifically, the range of values 
>> across all
>>  +case labels must not be bigger than CSWTCH_BRANCH_RATIO (default eight) 
>> times
>>  +the number of the actual switch branches.
>>  +*/

By a strange coincidence, one of the switch statement transformations that 
I'll
describe at the GCC summit this year is called "index mapping" which is used
to improve the density/space requirements of sparse switch statements.  When
combined with "switch initialization converstion" and lower bound 
elimination,
the resulting code would look like:

  static const char map[13] = { 0,  1, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3 };
  static const int CSWITCH_a[4] = { 16, 8, 9, 10 };
  static const int CSWITCH_b[4] = {   1, 6, 5, 4   };
  int i;
  // This is potentially a conditional move instruction
  // even if a,b are floating point or BLKmode types.
  if ((unsigned) argc) <= 12)
    i = map[argc];
  else i = 0;
  a = CSWITCH01[i];
  b = CSWITCH02[i];

You'll notice that the resulting code scales better for sparse tables
and also for more (and more complex) assignments.  The indexes can
even be permuted based upon frequency such that the hot case
values map to consecutive indexes.

More in Ottawa,

Roger
--

Re: [PATCH, middle-end] Switch initializations conversion (take four.2)

[Martin Jambor]

Hi,

On Thu, Apr 03, 2008 at 02:02:56PM +0100, Richard Guenther wrote:
> On Thu, Apr 3, 2008 at 1:32 PM, Martin Jambor <mjambor@suse.cz> wrote:
> 
> A few comments below.
> 

Thanks.

> 
> IMHO abbreviations like cswtch are unneccessary for file names
> (and options as well).  Please use tree-switch-conversion.c (or similar)
> and -ftree-switch-conversion.
> 

I guess you're right, I've changed that.

> 
> These are a lot of global statics - can you localize them where possible
> or at least stick them into a structure?
> 

They  are very  convenient and  yes,  all of  them are  used to  carry
information  between  functions.   I've  moved them  to  a  structure,
though.

> >  +  /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
> >  +     is a default label which is the last in the vector.  */
> 
> This may be no longer true if the pass runs after the first VRP pass, as
> that is now removing the default lablel if it was proved unreachable.
> 

I was wondering what to do about  this.  This pass is run as a part of
early optimizations,  even before early inlining and  way earlier than
VRP.  Basically there are two options, either handle this nevertheless
but then end up with a  branch of code never executing and bit-rotting
or asserting the default switch case was there.

In the end I chose the second option rather than adding complexity for
a  non-existent   case.   I  have   also  added  an   assert  checking
specifically  for existence  of the  default  branch so  that if  this
invariant ever goes away we will catch it in a controlled way.

I have bootstrapped and regtested the following on i686-pc-linux-gnu,
revision 134135 (this time without ADA, however). 

Martin


The changelog stays almost the same again:

2008-04-10  Martin Jambor  <mjambor@suse.cz>
        * Makefile.in (tree-switch-conversion.o): Add.
        (OBJS-common): Add tree-swtch-conversion.o
        * passes.c (init_optimization_passes): Add pass_convert_switch.
        * tree-pass.h: Add a declaration of the structure describing
        the new pass.
        * tree-switch-conversion.c: New file.
        * gcc.dg/tree-ssa/cswtch.c: New testcase.
        * common.opt (ftree-cswtch): New option.
        * params.h (PARAM_SWITCH_CONVERSION_BRANCH_RATIO): New parameter.
        * params.def (PARAM_SWITCH_CONVERSION_BRANCH_RATIO): New parameter.
        * opts.c (decode_options): Set flag_tree_switch_conversion when
        optimization level is >= 2.
        * doc/invoke.texi (Optimize Options): Added description of
        -ftree-swtch-conversion
        (Optimize Options): Added description of 
	switch-conversion-max-branch-ratio


Index: gcc/doc/invoke.texi
===================================================================
--- gcc/doc/invoke.texi	(revision 134135)
+++ gcc/doc/invoke.texi	(working copy)
@@ -353,8 +353,8 @@ Objective-C and Objective-C++ Dialects}.
 -fsignaling-nans -fsingle-precision-constant -fsplit-ivs-in-unroller @gol
 -fsplit-wide-types -fstack-protector -fstack-protector-all @gol
 -fstrict-aliasing -fstrict-overflow -fthread-jumps -ftracer -ftree-ccp @gol
--ftree-ch -ftree-copy-prop -ftree-copyrename -ftree-dce @gol
--ftree-dominator-opts -ftree-dse -ftree-fre -ftree-loop-im @gol
+-ftree-ch -ftree-copy-prop -ftree-copyrename -ftree-switch-conversion @gol
+-ftree-dce -ftree-dominator-opts -ftree-dse -ftree-fre -ftree-loop-im @gol
 -ftree-loop-distribution @gol
 -ftree-loop-ivcanon -ftree-loop-linear -ftree-loop-optimize @gol
 -ftree-parallelize-loops=@var{n} -ftree-pre -ftree-reassoc -ftree-salias @gol
@@ -5167,6 +5167,7 @@ also turns on the following optimization
 -fsched-interblock  -fsched-spec @gol
 -fschedule-insns  -fschedule-insns2 @gol
 -fstrict-aliasing -fstrict-overflow @gol
+-ftree-switch-conversion @gol
 -ftree-pre @gol
 -ftree-vrp}
 
@@ -5846,6 +5847,11 @@ pass operates on both local scalar varia
 loads (global variables, structures, arrays, etc).  This flag is
 enabled by default at @option{-O2} and higher.
 
+@item -ftree-switch-conversion
+Perform conversion of simple initializations in a switch to
+initializations from a scalar array.  This flag is enabled by default
+at @option{-O2} and higher.
+
 @item -ftree-dce
 @opindex ftree-dce
 Perform dead code elimination (DCE) on trees.  This flag is enabled by
@@ -7307,6 +7313,11 @@ mechanism for comparing types in C++ and
 bugs in the canonical type system are causing compilation failures,
 set this value to 0 to disable canonical types.
 
+@item switch-conversion-max-branch-ratio
+Switch initialization conversion will refuse to create arrays that are
+bigger than @option{cswtch-max-branch-ratio} times the number of
+branches in the switch.
+
 @item max-partial-antic-length
 Maximum length of the partial antic set computed during the tree
 partial redundancy elimination optimization (@option{-ftree-pre}) when
Index: gcc/tree-pass.h
===================================================================
--- gcc/tree-pass.h	(revision 134135)
+++ gcc/tree-pass.h	(working copy)
@@ -472,6 +472,7 @@ extern struct gimple_opt_pass pass_inlin
 extern struct gimple_opt_pass pass_apply_inline;
 extern struct gimple_opt_pass pass_all_early_optimizations;
 extern struct gimple_opt_pass pass_update_address_taken;
+extern struct gimple_opt_pass pass_convert_switch;
 
 /* The root of the compilation pass tree, once constructed.  */
 extern struct opt_pass *all_passes, *all_ipa_passes, *all_lowering_passes;
Index: gcc/params.h
===================================================================
--- gcc/params.h	(revision 134135)
+++ gcc/params.h	(working copy)
@@ -171,4 +171,6 @@ typedef enum compiler_param
   PARAM_VALUE (PARAM_L2_CACHE_SIZE)
 #define USE_CANONICAL_TYPES \
   PARAM_VALUE (PARAM_USE_CANONICAL_TYPES)
+#define SWITCH_CONVERSION_BRANCH_RATIO \
+  PARAM_VALUE (PARAM_SWITCH_CONVERSION_BRANCH_RATIO)
 #endif /* ! GCC_PARAMS_H */
Index: gcc/testsuite/gcc.dg/tree-ssa/cswtch.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/cswtch.c	(revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/cswtch.c	(revision 0)
@@ -0,0 +1,81 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-switchconv" } */
+/* { dg-do run } */
+
+extern void abort (void);
+
+static int X, Y;
+
+int check(int param)
+{
+  int a = 0;
+  int b = 1;
+  
+  switch (param) 
+    {
+    case -2:
+      a = 0;
+      b = -1;
+      break;
+    case 1:
+    case 2:
+      a = 8;
+      b = 6;
+      break;
+    case 3:
+      a = 9;
+      b = 5;
+      break;
+    case 6:
+      a = 10;
+      b = 4;
+      break;
+    default:
+      a = 16;
+      b = 1;
+    }
+  
+  X = a;
+  Y = b;
+  return 0;
+}
+
+void assertions(int a, int b)
+{
+  if (X != a || Y != b)
+    abort();  
+
+  return;
+}
+
+int main ()
+{
+  check (-10);
+  assertions (16, 1);
+
+  check (-2);
+  assertions (0, -1);
+
+  check(1);
+  assertions (8, 6);
+
+  check(2);
+  assertions (8, 6);
+
+  check(3);
+  assertions (9, 5);
+
+  check(5);
+  assertions (16, 1);
+
+  check(6);
+  assertions (10, 4);
+
+  check(12);
+  assertions (16, 1);
+
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump "Switch converted" "cswtch" } } */
+/* { dg-final { cleanup-tree-dump "cswtch" } } */
Index: gcc/opts.c
===================================================================
--- gcc/opts.c	(revision 134135)
+++ gcc/opts.c	(working copy)
@@ -887,6 +887,7 @@ decode_options (unsigned int argc, const
       flag_reorder_functions = 1;
       flag_tree_store_ccp = 1;
       flag_tree_vrp = 1;
+      flag_tree_switch_conversion = 1;
 
       if (!optimize_size)
 	{
Index: gcc/common.opt
===================================================================
--- gcc/common.opt	(revision 134135)
+++ gcc/common.opt	(working copy)
@@ -1099,6 +1099,10 @@ ftree-cselim
 Common Report Var(flag_tree_cselim) Init(2) Optimization
 Transform condition stores into unconditional ones
 
+ftree-switch-conversion
+Common Report Var(flag_tree_switch_conversion) Optimization
+Perform conversions of switch initializations.
+
 ftree-dce
 Common Report Var(flag_tree_dce) Optimization
 Enable SSA dead code elimination optimization on trees
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in	(revision 134135)
+++ gcc/Makefile.in	(working copy)
@@ -1160,6 +1160,7 @@ OBJS-common = \
 	tree-profile.o \
 	tree-scalar-evolution.o \
 	tree-sra.o \
+	tree-switch-conversion.o \
 	tree-ssa-address.o \
 	tree-ssa-alias.o \
 	tree-ssa-alias-warnings.o \
@@ -2597,6 +2598,11 @@ tree-sra.o : tree-sra.c $(CONFIG_H) $(SY
     $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) $(TREE_GIMPLE_H) \
     langhooks.h tree-pass.h $(FLAGS_H) $(EXPR_H) $(BASIC_BLOCK_H) \
     bitmap.h $(GGC_H) hard-reg-set.h $(OBSTACK_H) $(PARAMS_H) $(TARGET_H)
+tree-switch-conversion.o : tree-switch-conversion.c $(CONFIG_H) $(SYSTEM_H) \
+    $(TREE_H) $(TM_P_H) $(TREE_FLOW_H) $(DIAGNOSTIC_H) $(TREE_INLINE_H) \
+    $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) $(TREE_GIMPLE_H) \
+    tree-pass.h $(FLAGS_H) $(EXPR_H) $(BASIC_BLOCK_H) output.h \
+    $(GGC_H) $(OBSTACK_H) $(PARAMS_H) $(CPPLIB_H) $(PARAMS_H)
 tree-complex.o : tree-complex.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TREE_H) \
     $(TM_H) $(RTL_H) $(REAL_H) $(FLAGS_H) $(TREE_FLOW_H) $(TREE_GIMPLE_H) \
     tree-iterator.h tree-pass.h tree-ssa-propagate.h $(DIAGNOSTIC_H)
Index: gcc/tree-switch-conversion.c
===================================================================
--- gcc/tree-switch-conversion.c	(revision 0)
+++ gcc/tree-switch-conversion.c	(revision 0)
@@ -0,0 +1,851 @@
+/* Switch Conversion converts variable initializations based on switch
+   statements to initializations from a static array.  
+   Copyright (C) 2006, 2008 Free Software Foundation, Inc.  
+   Contributed by Martin Jambor <jamborm@suse.cz>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 3, or (at your option) any
+later version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not, write to the Free
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA.  */
+
+/*  
+     Switch initialization conversion
+
+The following pass changes simple initializations of scalars in a switch
+statement into initializations from a static array.  Obviously, the values must
+be constant and known at compile time and a default branch must be
+provided.  For example, the following code:
+
+        int a,b;
+
+        switch (argc) 
+	{
+         case 1:
+         case 2:
+                a_1 = 8;
+                b_1 = 6;
+                break;
+         case 3:
+                a_2 = 9;
+                b_2 = 5;
+                break;
+         case 12:
+                a_3 = 10;
+                b_3 = 4;
+                break;
+         default:
+                a_4 = 16;
+                b_4 = 1;
+        }
+	a_5 = PHI <a_1, a_2, a_3, a_4>
+	b_5 = PHI <b_1, b_2, b_3, b_4>
+
+
+is changed into:
+
+        static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
+        static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16, 
+                                 16, 16, 10};
+
+        if (((unsigned) argc) - 1 < 11)
+          {
+	    a_6 = CSWTCH02[argc - 1];
+            b_6 = CSWTCH01[argc - 1];
+	  }
+	else
+	  {
+	    a_7 = 16;
+	    b_7 = 1;
+          }
+	  a_5 = PHI <a_6, a_7>
+	  b_b = PHI <b_6, b_7>
+
+There are further constraints.  Specifically, the range of values across all
+case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
+eight) times the number of the actual switch branches.
+*/
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include <signal.h>
+
+#include "line-map.h"
+#include "params.h"
+#include "flags.h"
+#include "tree.h"
+#include "basic-block.h"
+#include "tree-flow.h"
+#include "tree-flow-inline.h"
+#include "tree-ssa-operands.h"
+#include "output.h"
+#include "input.h"
+#include "tree-pass.h"
+#include "diagnostic.h"
+#include "tree-dump.h"
+
+/* The main structure of the pass.  */
+struct switch_conv_info
+{
+  /* The expression used to decide the switch branch.  (It is subsequently used
+     as the index to the created array.) */
+  tree index_expr;
+
+  /* The following integer constants store the minimum value covered by the
+     cases.  */
+  tree range_min;
+
+  /* The difference of between the above two numbers, i.e. The size of the array
+     that would have to be created by the transformation.  */
+  tree range_size;
+
+  /* Basic block that contains the actual SWITCH_EXPR.  */
+  basic_block switch_bb;
+
+  /* All branches of the switch statement must have a single successor stored in
+     the following variable.  */
+  basic_block final_bb;
+
+  /* Number of phi nodes in the final bb (that we'll be replacing).  */
+  int phi_count;
+
+  /* Array of default values, n the same order as phi nodes.  */
+  tree *default_values;
+
+  /* Constructors of new static arrays.  */
+  VEC (constructor_elt, gc) **constructors;
+				 
+  /* Array of ssa names that are initialized with a value from a new static
+     array.  */
+  tree *target_inbound_names;
+
+  /* Array of ssa names that are initialized with the default value if the
+     switch expression is out of range.  */
+  tree *target_outbound_names;
+
+  /* The probability of the default edge in the replaced switch.  */
+  int default_prob;
+
+  /* The count of the default edge in the replaced switch.  */
+  gcov_type default_count;
+
+  /* Combined count of all other (non-default) edges in the replaced switch.  */
+  gcov_type other_count;
+
+  /* The last load statement that loads a temporary from a new static array.  */
+  tree arr_ref_first;
+
+  /* The last load statement that loads a temporary from a new static array.  */
+  tree arr_ref_last;
+
+  /* String reason why the case wasn't a good candidate that is written to the
+     dump file, if there is one.  */
+  const char *reason;
+};
+
+/* Global pass info.  */
+static struct switch_conv_info info;
+
+
+/* Checks whether the range given by individual case statements isn't too big
+   and whether the number of branches actually satisfy the size of the new
+   array.  */
+static bool 
+check_range (tree swtch)
+{
+  tree min_case, max_case;
+  tree cases = SWITCH_LABELS (swtch);
+  int branch_num = TREE_VEC_LENGTH (cases);
+  tree range_max;
+
+  /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
+     is a default label which is the last in the vector.  */
+
+  min_case = TREE_VEC_ELT (cases, 0);
+  info.range_min = CASE_LOW (min_case);
+
+  gcc_assert (branch_num > 1);
+  gcc_assert (CASE_LOW (TREE_VEC_ELT (cases, branch_num - 1)) == NULL_TREE);
+  max_case = TREE_VEC_ELT (cases, branch_num - 2);
+  if (CASE_HIGH (max_case) != NULL_TREE)
+    range_max = CASE_HIGH (max_case);
+  else
+    range_max = CASE_LOW (max_case);
+
+  gcc_assert (info.range_min);
+  gcc_assert (range_max);
+  
+  info.range_size = int_const_binop (MINUS_EXPR, range_max, info.range_min, 0);
+
+  gcc_assert (info.range_size);
+  if (!host_integerp (info.range_size, 1))
+    {
+      info.reason = "index range way too large or otherwise unusable.\n";
+      return false; 
+    }
+
+  if ((unsigned HOST_WIDE_INT) tree_low_cst (info.range_size, 1) 
+      > ((unsigned) branch_num * SWITCH_CONVERSION_BRANCH_RATIO))
+    {
+      info.reason = "the maximum range-branch ratio exceeded.";
+      return false;
+    }
+
+  return true;
+}
+
+/* Checks the given cs switch case whether it is suitable for conversion
+   (whether all but the default basic blocks are empty and so on).  If it is,
+   adds the case to the branch list along with values for the defined variables
+   and returns true.  Otherwise returns false.  */
+static bool 
+check_process_case (tree cs)
+{
+  tree ldecl;
+  basic_block label_bb, following_bb;
+  edge e;
+
+  ldecl = CASE_LABEL (cs);
+  label_bb = label_to_block (ldecl);
+
+  e = find_edge (info.switch_bb, label_bb);
+  gcc_assert (e);
+
+  if (CASE_LOW (cs) == NULL_TREE) 
+    {
+      /* default branch */
+      info.default_prob = e->probability;
+      info.default_count = e->count;
+    }
+  else
+    info.other_count += e->count;
+  
+  if (!label_bb)
+    {
+      info.reason = "  Bad case - cs BB  label is NULL\n";
+      return false;
+    }
+
+  if (!single_pred_p (label_bb))
+    {
+      if (info.final_bb && info.final_bb != label_bb)
+	{
+	  info.reason = "  Bad case - a non-final BB has two predecessors\n";
+	  return false; /* sth complex going on in this branch  */
+	}
+
+      following_bb = label_bb;
+    }
+  else
+    {
+      if (!empty_block_p (label_bb))
+	{
+	  info.reason = "  Bad case - a non-final BB not empty\n";
+	  return false;
+	}
+
+      e = single_succ_edge (label_bb);
+      following_bb = single_succ (label_bb);
+    }
+
+  if (!info.final_bb) 
+    info.final_bb = following_bb;
+  else if (info.final_bb != following_bb)
+    {
+      info.reason = "  Bad case - different final BB\n";
+      return false; /* the only successor is not common for all the branches */
+    }
+
+  return true;
+}
+
+/* check_final_bb() checks whether all required values in phi nodes in final_bb
+   are constants.  Required values are those that correspond to a basic block
+   which is a part of the examined switch statement.  It returns true if the
+   phi nodes are OK, otherwise false.  */
+static bool
+check_final_bb (void)
+{
+  tree phi;
+
+  info.phi_count = 0;
+  for (phi = phi_nodes (info.final_bb); phi; phi = PHI_CHAIN (phi)) 
+    {
+      int i;
+
+      info.phi_count++;
+
+      for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+	{
+	  basic_block bb = PHI_ARG_EDGE (phi, i)->src;
+	  
+	  if ((bb == info.switch_bb 
+	       || (single_pred_p (bb) && single_pred (bb) == info.switch_bb))
+	      && !is_gimple_min_invariant (PHI_ARG_ELT (phi, i).def))
+	    {
+	      info.reason = "   Non-invariant value from a case\n";
+	      return false; 		/* non invariant argument */
+	    }
+	}
+    }
+
+  return true;
+}
+
+/* create_temp_arrays() allocates default_values, target_{in,out}_names and
+   constructors arrays.  The last one is also populated with pointers to
+   vectors that will become constructors of new arrays.  */
+static void
+create_temp_arrays (void)
+{
+  int i;
+
+  info.default_values = xcalloc (info.phi_count, sizeof (tree));
+  info.constructors = xcalloc (info.phi_count, sizeof (tree));
+  info.target_inbound_names = xcalloc (info.phi_count, sizeof (tree));
+  info.target_outbound_names = xcalloc (info.phi_count, sizeof (tree));
+
+  for (i = 0; i < info.phi_count; i++)
+    {
+      info.constructors[i] = VEC_alloc (constructor_elt, gc, 
+				   tree_low_cst (info.range_size, 1) + 1);
+    }
+}
+
+/* free_temp_arrays() frees the arrays created by create_temp_arrays().  The
+   vectors that are created by that function are not freed here, however,
+   because they have already become the constructors and must be preserved.  */
+static void
+free_temp_arrays (void)
+{
+  free (info.constructors);
+  free (info.default_values);
+  free (info.target_inbound_names);
+  free (info.target_outbound_names);
+}
+
+/* gather_default_values() populates the array of default values in the order
+   of phi nodes.  */
+static void
+gather_default_values (tree default_case)
+{
+  tree phi;
+  basic_block bb = label_to_block (CASE_LABEL (default_case));
+  edge e;
+  int i;
+
+  gcc_assert (CASE_LOW (default_case) == NULL_TREE);
+
+  if (bb == info.final_bb)
+    e = find_edge (info.switch_bb, bb);
+  else
+    e = single_succ_edge (bb);
+  
+  for (phi = phi_nodes (info.final_bb), i = 0; phi; phi = PHI_CHAIN (phi), i++) 
+    {
+      tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
+      gcc_assert (val);
+      info.default_values[i] = val;
+    }
+}
+
+/* build_constructors() populates the vectors in the constructors array with
+   future contents of the static arrays.  The vectors are populated in the
+   order of phi nodes.  */
+static void
+build_constructors (tree swtch)
+{
+  int i;
+  tree cases = SWITCH_LABELS (swtch);
+  tree pos = info.range_min;
+  
+  for (i = 0; i < TREE_VEC_LENGTH (cases) - 1; i++) 
+    {
+      tree cs = TREE_VEC_ELT (cases, i);
+      basic_block bb = label_to_block (CASE_LABEL (cs));
+      edge e;
+      tree phi, high;
+      int j;
+
+      if (bb == info.final_bb)
+	e = find_edge (info.switch_bb, bb);
+      else
+	e = single_succ_edge (bb);
+      gcc_assert (e);
+
+      while (tree_int_cst_lt (pos, CASE_LOW (cs)))
+	{
+	  int k;
+	  for (k = 0; k < info.phi_count; k++)
+	    {
+	      constructor_elt *elt;
+
+	      elt = VEC_quick_push (constructor_elt, 
+				    info.constructors[k], NULL);
+	      elt->index = int_const_binop (MINUS_EXPR, pos, info.range_min, 0);
+	      elt->value = info.default_values[k];
+	    }
+
+	  pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0);
+	}
+      gcc_assert (tree_int_cst_equal (pos, CASE_LOW(cs)));
+      
+      j = 0;
+      if (CASE_HIGH (cs))
+	high = CASE_HIGH (cs);
+      else
+	high = CASE_LOW(cs);
+      for (phi = phi_nodes (info.final_bb); phi; phi = PHI_CHAIN (phi)) 
+	{
+	  tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
+	  pos = CASE_LOW (cs);
+
+	  while (!tree_int_cst_lt (high, pos))
+	    {
+	      constructor_elt *elt;
+
+	      elt = VEC_quick_push (constructor_elt, 
+				    info.constructors[j], NULL);
+	      elt->index = int_const_binop (MINUS_EXPR, pos, info.range_min, 0);
+	      elt->value = val;
+	      
+	      pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0);
+	    }
+	  j++;
+	}
+    }
+}
+
+/* build_one_array() creates an appropriate array type and declaration and
+   assembles a static array variable.  It also creates a load statement that
+   initializes the variable in question with a value from the static array.  */
+static void 
+build_one_array (tree swtch, int num, tree arr_index_type, tree phi, tree tidx)
+{ 
+  tree array_type;
+  tree ctor;
+  tree decl;
+  tree value_type;
+  tree name;
+  tree fetch, load;
+  block_stmt_iterator bsi;
+
+  gcc_assert (info.default_values[num]);
+  value_type = TREE_TYPE (info.default_values[num]);
+  array_type = build_array_type (value_type, arr_index_type); 
+
+  ctor = build_constructor (array_type, info.constructors[num]);
+  TREE_CONSTANT (ctor) = true;
+
+  decl = build_decl (VAR_DECL, NULL_TREE, array_type); 
+  TREE_STATIC (decl) = 1;
+  DECL_INITIAL (decl) = ctor;
+
+  DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
+  DECL_ARTIFICIAL (decl) = 1;
+  TREE_CONSTANT (decl) = 1;
+  add_referenced_var (decl);
+  assemble_variable (decl, 0, 0, 0);
+  mark_sym_for_renaming (decl);
+
+  name = make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi)), NULL_TREE);
+  info.target_inbound_names[num] = name;
+
+  fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE, 
+		  NULL_TREE); 
+  load = build2 (GIMPLE_MODIFY_STMT, void_type_node, name, fetch);
+  SSA_NAME_DEF_STMT (name) = load;
+
+  bsi = bsi_for_stmt (swtch);
+  bsi_insert_before (&bsi, load, BSI_SAME_STMT);
+  mark_symbols_for_renaming (load);
+
+  info.arr_ref_last = load;
+  
+  return;
+}
+
+/* Builds and initializes static arrays initialized with values gathered from
+   the switch statement.  Also creates statements that assign a value.  */
+static void 
+build_arrays (tree swtch)
+{
+  tree arr_index_type;
+  tree tidx, sub;
+  block_stmt_iterator bsi;
+  tree phi = phi_nodes (info.final_bb);
+  int i;
+    
+  arr_index_type = build_index_type (info.range_size);
+  tidx = make_rename_temp (arr_index_type, "csti");
+  sub = build2 (MINUS_EXPR, TREE_TYPE (info.index_expr), info.index_expr, 
+		fold_convert (TREE_TYPE (info.index_expr), info.range_min));
+  sub = build2 (GIMPLE_MODIFY_STMT, void_type_node, tidx, sub);
+  
+  bsi = bsi_for_stmt (swtch);
+  bsi_insert_before (&bsi, sub, BSI_SAME_STMT);
+  mark_symbols_for_renaming (sub);
+  info.arr_ref_first = sub;
+
+  for (phi = phi_nodes (info.final_bb), i = 0; phi; phi = PHI_CHAIN (phi), i++) 
+    build_one_array (swtch, i, arr_index_type, phi, tidx);
+  
+  return;
+}
+
+/* Generates and appropriately inserts loads of default values at the given
+   position.  Returns the last inserted statement.  */
+static tree 
+gen_def_assigns (block_stmt_iterator *bsi)
+{
+  int i;
+  tree assign = NULL_TREE;
+
+  for (i = 0; i < info.phi_count; i++)
+    {
+      tree name = make_ssa_name (SSA_NAME_VAR (info.target_inbound_names[i]), 
+				 NULL_TREE);
+
+      info.target_outbound_names[i] = name;
+      assign = build2 (GIMPLE_MODIFY_STMT, void_type_node, name, 
+		       info.default_values[i]);
+      SSA_NAME_DEF_STMT (name) = assign;
+      bsi_insert_before (bsi, assign, BSI_SAME_STMT);
+      find_new_referenced_vars (&assign);
+      mark_symbols_for_renaming (assign);
+    }
+  return assign;
+}
+
+/* Deletes the unused bbs and edges that now contain the switch statement and
+   its empty branch bbs.  */
+static void 
+prune_bbs (basic_block bbd, basic_block final)
+{
+  edge_iterator ei;
+  edge e;
+  
+  for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
+    {
+      basic_block bb;
+      bb = e->dest;
+      remove_edge (e);
+      if (bb != final) 
+	delete_basic_block (bb);
+    }
+  delete_basic_block (bbd);
+}
+
+/* fix_phi_nodes() adds values to phi nodes in final_bb for the two new
+   edges.  e1f is the edge from the basic block loading values from an array and
+   e2f from the basic block loading default values.  */
+static void 
+fix_phi_nodes (edge e1f, edge e2f, basic_block bbf)
+{
+  tree phi;
+  int i;
+
+  for (phi = phi_nodes (bbf), i = 0; phi; phi = PHI_CHAIN (phi), i++) 
+    {
+      add_phi_arg (phi, info.target_inbound_names[i], e1f);
+      add_phi_arg (phi, info.target_outbound_names[i], e2f);
+    }
+
+}
+
+/* Creates a check whether the switch expression value actually falls into the
+   range given by all the cases.  If it not, the temporaries are loaded with
+   default values instead.
+   
+   bb0 is the bb with the switch statement, however, we'll end it with a
+       condition instead.
+
+   bb1 is the bb to be used when the range check went ok.  It is derived from
+       the switch BB
+
+   bb2 is the bb taken when the expression evaluated outside of the range
+       covered by the created arrays.  It is populated by loads of default
+       values.
+
+   bbF is a fall through for both bb1 and bb2 and contains exactly what
+       originally followed the switch statement.
+
+   bbD contains the switch statement (in the end).  It is unreachable but we
+       still need to strip off its edges.
+*/
+static void 
+gen_inbound_check (tree swtch)
+{
+  tree label_decl1 = create_artificial_label ();
+  tree label_decl2 = create_artificial_label ();
+  tree label_decl3 = create_artificial_label ();
+  tree label1, label2, label3;
+
+  tree utype = unsigned_type_for (TREE_TYPE (info.index_expr));
+  tree tmp_u;
+  tree cast, cast_assign;
+  tree ulb, minus, minus_assign;
+  tree bound;
+  
+  tree if_expr;
+
+  tree last_assign;
+  block_stmt_iterator bsi;
+  basic_block bb0, bb1, bb2, bbf, bbd;
+  edge e01, e02, e21, e1d, e1f, e2f;
+
+  gcc_assert (info.default_values);
+  bb0 = bb_for_stmt (swtch);
+
+  /* (end of) block 0 */
+  bsi = bsi_for_stmt (info.arr_ref_first);
+  tmp_u = make_rename_temp (utype, "csui");
+  
+  cast = build1 (NOP_EXPR, utype, info.index_expr);
+  cast_assign = build2 (GIMPLE_MODIFY_STMT, void_type_node, tmp_u, cast);
+  find_new_referenced_vars (&cast_assign);
+  bsi_insert_before (&bsi, cast_assign, BSI_SAME_STMT);
+  mark_symbols_for_renaming (cast_assign);
+  
+  ulb = fold_convert (utype, info.range_min);
+  minus = build2 (MINUS_EXPR, utype, tmp_u, ulb);
+  minus_assign = build2 (GIMPLE_MODIFY_STMT, void_type_node, tmp_u, minus);
+  find_new_referenced_vars (&minus_assign);
+  bsi_insert_before (&bsi, minus_assign, BSI_SAME_STMT);
+  mark_symbols_for_renaming (minus_assign);
+
+  bound = fold_convert (utype, info.range_size);
+
+  if_expr = build3 (COND_EXPR, void_type_node,
+		    build2 (LE_EXPR, boolean_type_node, tmp_u, bound),
+		    NULL_TREE, NULL_TREE);
+  
+  find_new_referenced_vars (&if_expr);
+  bsi_insert_before (&bsi, if_expr, BSI_SAME_STMT);
+  mark_symbols_for_renaming (if_expr);
+  
+  /* block 2 */
+  bsi = bsi_for_stmt (info.arr_ref_first);
+  label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
+  bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
+  last_assign = gen_def_assigns (&bsi);
+
+  /* block 1 */
+  bsi = bsi_for_stmt (info.arr_ref_first);
+  label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
+  bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
+
+  /* block F */
+  bsi = bsi_start (info.final_bb);
+  label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
+  bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
+
+  /* cfg fix */
+  e02 = split_block (bb0, if_expr);
+  bb2 = e02->dest;
+
+  e21 = split_block (bb2, last_assign);
+  bb1 = e21->dest;
+  remove_edge (e21);
+
+  e1d = split_block (bb1, info.arr_ref_last);
+  bbd = e1d->dest;
+  remove_edge (e1d);
+
+  /* flags and profiles of the edge for in-range values */
+  e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
+  e01->probability = REG_BR_PROB_BASE - info.default_prob;
+  e01->count = info.other_count;
+
+  /* flags and profiles of the edge taking care of out-of-range values */
+  e02->flags &= ~EDGE_FALLTHRU;
+  e02->flags |= EDGE_FALSE_VALUE;
+  e02->probability = info.default_prob;
+  e02->count = info.default_count;
+
+  bbf = info.final_bb;
+
+  e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
+  e1f->probability = REG_BR_PROB_BASE;
+  e1f->count = info.other_count;
+
+  e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
+  e2f->probability = REG_BR_PROB_BASE;
+  e2f->count = info.default_count;
+
+  /* frequencies of the new BBs */
+  bb1->frequency = EDGE_FREQUENCY (e01);
+  bb2->frequency = EDGE_FREQUENCY (e02);
+  bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f);
+  
+  prune_bbs (bbd, info.final_bb); /* to keep calc_dfs_tree() in dominance.c
+				     happy */
+  
+  fix_phi_nodes (e1f, e2f, bbf);
+
+  free_dominance_info (CDI_DOMINATORS);
+  free_dominance_info (CDI_POST_DOMINATORS);
+}
+
+/* process_switch() is invoked on every switch statement and runs the individual
+   phases of switch conversion on it one after another until one fails or the
+   conversion is completed.  */
+static bool 
+process_switch (tree swtch)
+{
+  int i;
+  tree cases;
+  tree index_type;
+
+  /* operand 2 is either NULL_TREE or a vector of cases (stmt.c)*/
+  if (TREE_OPERAND (swtch, 2) == NULL_TREE) 
+    {
+      info.reason = "swtch has no labels\n";
+      return false;
+    }
+
+  /* Comment from stmt.c: 
+     The switch body is lowered in gimplify.c, we should never have switches
+     with a non-NULL SWITCH_BODY here.  */
+  gcc_assert (!SWITCH_BODY (swtch));
+
+  cases = SWITCH_LABELS (swtch);
+  info.final_bb = NULL;
+  info.switch_bb = bb_for_stmt (swtch);
+  info.index_expr = SWITCH_COND (swtch); 
+  index_type = TREE_TYPE (info.index_expr);
+  info.arr_ref_first = NULL_TREE;
+  info.arr_ref_last = NULL_TREE;
+  info.default_prob = 0;
+  info.default_count = 0;
+  info.other_count = 0;
+
+  /* An ERROR_MARK occurs for various reasons including invalid data type.
+     (comment from stmt.c) */
+  if (index_type == error_mark_node) 
+    {
+      info.reason = "index error.\n";
+      return false; 
+    }
+
+  /* check the case label values are within reasonable range:  */
+  if (!check_range (swtch))
+    return false;
+
+  /* for all the cases, see whether they are empty, the assignments they
+     represent constant and so on...  */
+  for (i = 0; i < TREE_VEC_LENGTH (cases); i++) 
+    {
+      tree part_case = TREE_VEC_ELT (cases, i);
+      if (!check_process_case (part_case)) 
+	{
+	  if (dump_file) 
+	    fprintf (dump_file, "Processing of case %i failed\n", i);
+	  return false;
+	}
+    }
+
+  if (!check_final_bb ())
+    return false;
+
+  /* at this point all checks have passed and we can proceed with the
+     transformation.  */
+  
+  create_temp_arrays ();
+  gather_default_values (TREE_VEC_ELT (cases, TREE_VEC_LENGTH (cases) - 1));
+  build_constructors (swtch);
+  
+  build_arrays (swtch); /* build the static arrays and assignments */
+  gen_inbound_check (swtch); 	/* build the bound check */
+
+  /* cleanup: */
+  free_temp_arrays ();
+  return true;
+}
+
+/* The main function of the pass scans statements for switches and invokes
+   process_switch on them.  */
+static unsigned int 
+do_switchconv (void)
+{
+  basic_block bb;
+  
+  FOR_EACH_BB (bb) 
+  {
+    tree stmt = last_stmt (bb);
+    if (stmt && TREE_CODE (stmt) == SWITCH_EXPR) 
+      {
+	expanded_location loc = expand_location (EXPR_LOCATION (stmt));
+
+	if (dump_file)
+	  {
+	    fprintf (dump_file, "beginning to process the following "
+		     "SWITCH statement (%s:%d) : ------- \n",
+		     loc.file, loc.line);
+	    print_generic_stmt (dump_file, stmt, 2);
+	    fprintf (dump_file, "\n");
+	  }
+
+	info.reason = NULL;
+	if (process_switch (stmt))
+	  {
+	    if (dump_file)
+	      {
+		fprintf (dump_file, "Switch converted\n");
+		fprintf (dump_file, "--------------------------------\n");
+	      }
+	  }
+	else
+	  {
+	    if (dump_file)
+	      {
+		gcc_assert (info.reason);
+		fprintf (dump_file, "Bailing out - ");
+		fprintf (dump_file, info.reason);
+		fprintf (dump_file, "--------------------------------\n");
+	      }
+	  }
+      }
+  }
+
+  return 0;
+}
+
+static bool
+switchconv_gate (void)
+{
+  return flag_tree_switch_conversion != 0;
+}
+
+struct gimple_opt_pass pass_convert_switch =
+{
+ {
+  GIMPLE_PASS,
+  "switchconv",				/* name */
+  switchconv_gate,        		/* gate */
+  do_switchconv,			/* execute */
+  NULL,					/* sub */
+  NULL,					/* next */
+  0,					/* static_pass_number */
+  0,			        	/* tv_id */
+  PROP_cfg | PROP_ssa,	                /* properties_required */
+  0,					/* properties_provided */
+  0,					/* properties_destroyed */
+  0,					/* todo_flags_start */
+  TODO_update_ssa | TODO_dump_func 
+  | TODO_ggc_collect | TODO_verify_ssa  /* todo_flags_finish */
+ }
+};
Index: gcc/passes.c
===================================================================
--- gcc/passes.c	(revision 134135)
+++ gcc/passes.c	(working copy)
@@ -534,6 +534,7 @@ init_optimization_passes (void)
 	  NEXT_PASS (pass_update_address_taken);
 	  NEXT_PASS (pass_simple_dse);
 	  NEXT_PASS (pass_tail_recursion);
+	  NEXT_PASS (pass_convert_switch);
           NEXT_PASS (pass_profile);
 	  NEXT_PASS (pass_release_ssa_names);
 	}
Index: gcc/params.def
===================================================================
--- gcc/params.def	(revision 134135)
+++ gcc/params.def	(working copy)
@@ -729,6 +729,15 @@ DEFPARAM (PARAM_DF_DOUBLE_QUEUE_THRESHOL
 	  "Multiplier used for determining the double-queueing threshold",
 	  2, 0, 0)
 
+/* Switch initialization conversion will refuse to create arrays that are
+   bigger than this parameter times the number of switch branches.  */
+
+DEFPARAM (PARAM_SWITCH_CONVERSION_BRANCH_RATIO,
+	  "switch-conversion-max-branch-ratio",
+	  "The maximum ratio between array size and switch branches for "
+	  "a switch conversion to take place",
+	  8, 1, 0)
+
 /*
 Local variables:
 mode:c