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

[Martin Jambor <mjambor at suse dot cz>]

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