Re: [PATCH, middle-end] Switch initializations conversion

[Martin Jambor <jamborm at matfyz dot cz>]

Hi,

this is yet a another version  of the pass which complies with most of
Jakub's suggestions.

On Tue, Aug 28, 2007 at 05:30:38AM -0400, Jakub Jelinek wrote:
> On Tue, Aug 28, 2007 at 11:12:25AM +0200, Martin Jambor wrote:
> > 1) I added a testcase.
> 
> I think more testcases (also dg-do run to verify it works correctly) would
> be desirable.

OK, I rewrote the testcase to include a dg-do run.

> > --- gcc/tree-cswtch.c	(revision 0)
> > +++ gcc/tree-cswtch.c	(revision 0)
> > @@ -0,0 +1,907 @@
> > +/* Switch Conversion converts variable initializations based on switch
> > +   statements to initializations from a static array.  Copyright (C) 2006, 2007
> > +   Free Software Foundation, Inc.  Contributed by Martin Jambor
> > +   <jamborm@matfyz.cz>
> 
> Copyright line should be on its own line, Contributed note as well.

OK

> 
> > +/* We never create arrays larger than the following constant (given in number
> > +   of elements).  */
> > +#define MAX_ARRAY_RANGE 0x2000
> > +
> > +/* We never create arrays  if the number of branches is not  at least the range
> > +   divided by the following constant.  */
> > +#define MAX_RANGE_BRANCH_RATIO 8
> 
> Have you considered making these parameters (see params.def)?

I did. However, I don't think  people will bother to set it. Moreover,
as shown in the previous email, the differences in number of performed
conversions is  not that  big.  Also,  I kind of  feel gcc  has enough
parameters already.

However,  if  you  are strongly  in  favour  of  turning this  into  a
parameter, I certainly can do that.

> 
> > +  for (t = &branch_list; 
> > +       (*t != NULL_TREE) 
> > +	 && (folder_evaluate_lt (CASE_LOW (cs), CASE_LOW (TREE_PURPOSE (*t))));
> > +       t = &TREE_CHAIN (*t))
> > +    ; /* empty loop body  */
> 
> This is ugly, the condition is too long.  Much better IMHO to rewrite this
> as a while loop.

OK

> 
> > +	      if (folder_evaluate_eq (TYPE_MIN_VALUE (TREE_TYPE (index)), 
> > +				      index))
> > +		{
> > +		  /* must not underflow unsigned types */
> > +		  break;
> > +		}
> 
> One statement if bodies don't need curly braces.

OK

> > +      if (bb != final) 
> > +	{
> > +	  delete_basic_block (bb);
> > +	} 

OK

> Likewise.
> 
> > +	  if (dump_file) 
> > +	    {
> > +	      fprintf (dump_file, "Processing of case %i failed\n", i);
> > +	    }
> 
> Likewise...

OK
> 
> > +static bool
> > +convswitch_gate (void)
> > +{
> > +  return optimize >= 2;
> > +}
> 
> I think you should add an option which controls this optimization
> instead and by default set it for optimize >= 2, instead of doing it
> unconditionally.

OK, I did that.

> 
> > @@ -564,6 +565,8 @@ init_optimization_passes (void)
> >        NEXT_PASS (pass_merge_phi);
> >        NEXT_PASS (pass_vrp);
> >        NEXT_PASS (pass_dce);
> > +
> > +
> >        NEXT_PASS (pass_dominator);
> >        /* The only const/copy propagation opportunities left after
> >  	 DOM should be due to degenerate PHI nodes.  So rather than
> 
> Why the whitespace change?

I have no clue, I got rid of it.


Again, I bootstrapped and regtested this patch with all default
languages on i686-linux.

What do you think abut it now? 

BTW, thanks a lot :-)


Martin




:ADDPATCH middle-end:

Changelog:

2007-09-03  Martin Jambor  <jamborm@matfyz.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.
	* opts.c (decode_options): Set flag_tree_cswtch when
	optimization level is >= 2.



Index: gcc/tree-pass.h
===================================================================
--- gcc/tree-pass.h	(revision 128023)
+++ gcc/tree-pass.h	(working copy)
@@ -438,6 +438,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/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,71 @@
+/* { 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 1:
+    case 2:
+      a = 8;
+      b = 6;
+      break;
+    case 3:
+      a = 9;
+      b = 5;
+      break;
+    case 12:
+      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(1);
+  assertions (8, 6);
+
+  check(2);
+  assertions (8, 6);
+
+  check(3);
+  assertions (9, 5);
+
+  check(5);
+  assertions (16, 1);
+
+  check(12);
+  assertions (10, 4);
+
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump "Switch converted" "cswtch" } } */
+/* { dg-final { cleanup-tree-dump "cswtch" } } */
Index: gcc/opts.c
===================================================================
--- gcc/opts.c	(revision 128023)
+++ gcc/opts.c	(working copy)
@@ -845,6 +845,7 @@ decode_options (unsigned int argc, const
       flag_tree_store_ccp = 1;
       flag_tree_store_copy_prop = 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,899 @@
+/* Switch Conversion converts variable initializations based on switch
+   statements to initializations from a static array.  
+   Copyright (C) 2006, 2007 Free Software Foundation, Inc.  
+   Contributed by Martin Jambor <jamborm@matfyz.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 = 8;
+                b = 6;
+                break;
+         case 3:
+                a = 9;
+                b = 5;
+                break;
+         case 12:
+                a = 10;
+                b = 4;
+                break;
+         default:
+                a = 16;
+                b = 1;
+        }
+
+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)
+          {
+            tmp1 = CSWTCH01[argc - 1];
+	    tmp2 = CSWTCH02[argc - 1];
+	  }
+	else
+	  {
+	    tmp1 = 1;
+	    tmp2 = 16;
+          }
+
+And all subsequent occurrences of a and b where these values are used is
+replaced by tmp2 and tmp1 respectively.
+
+There are further constraints. Specifically, the range of values across all
+case labels must be smaller than 0x2000 and must not be bigger than eight times
+the number of the actual switch branches.  Both of these constants are rather
+arbitrary but I do not believe they should be set by a compiler switch as no
+one would really bother to tweak them.  Instead, they should be set to any
+fairly permissible value known not to cause trouble.
+
+*/
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include <signal.h>
+
+#include "line-map.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"
+
+
+/* We never create arrays larger than the following constant (given in number
+   of elements).  */
+#define MAX_ARRAY_RANGE 0x2000
+
+/* We never create arrays  if the number of branches is not  at least the range
+   divided by the following constant.  */
+#define MAX_RANGE_BRANCH_RATIO 8
+
+/* The expression used to decide the switch branch.  (It is subsequently used as
+   the index to the created array.) */
+static tree index_expr;
+
+/* The type of the above expression.  */
+static tree index_type;
+
+/* The following integer constants store the minimum and the maximum covered by
+   the cases.  */
+static tree range_min, range_max;
+
+/* 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;
+
+/* A bitmap of BBs.  The BB of the switch statement itself and the BBs of the
+   cases are signalled by one, bits corresponding to all other BBs are
+   zero.  */
+static sbitmap rel_bbs;
+
+/* List of cases and associated assigned values.  Each element's purpose is the
+   corresponding case of the switch, the value contains a list of values for
+   individual variables.  The list is sorted in descending order by the switch
+   case ranges. */
+static tree branch_list;
+
+/* List of values that are assigned to individual variables when the default
+   branch is taken.  */
+static tree default_values;
+
+/* List of temporary variables that are either initialized with a value from a
+   new static array or the default value if the switch expression is out of
+   range.  */
+static tree target_list;
+
+/* 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_end;
+
+/* 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;
+
+/* The following three functions evaluate "equal to" "less then," and "less
+   than or equal to" (receptively) of two integers represented by
+   INTEGER_CSTs.  */
+static int folder_evaluate_rel (enum tree_code code, tree arg1, tree arg2)
+{
+  tree res;
+
+  res = fold_build2 (code, integer_type_node, arg1, arg2);
+  return integer_nonzerop (res);
+}
+
+static int folder_evaluate_eq (tree arg1, tree arg2)
+{
+  return folder_evaluate_rel (EQ_EXPR, arg1, arg2);
+}
+
+static int folder_evaluate_lt (tree arg1, tree arg2)
+{
+  return folder_evaluate_rel (LT_EXPR, arg1, arg2);
+}
+
+static int folder_evaluate_le (tree arg1, tree arg2)
+{
+  return folder_evaluate_rel (LE_EXPR, arg1, arg2);
+}
+
+/* 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)
+{
+  int i;
+  tree min = NULL_TREE; 
+  tree max = NULL_TREE;
+  tree cases = SWITCH_LABELS (swtch);
+  int branch_num = TREE_VEC_LENGTH (cases);
+  bool default_present = false;
+
+  /* loop over all switch labels */
+  for (i = 0; i < branch_num; i++) 
+    {
+      tree lbound, hbound;
+      tree label = TREE_VEC_ELT (cases, i);
+
+      if (CASE_LOW (label) == NULL_TREE) 
+	{
+	  /* the default case */
+	  default_present = true;
+	  continue; 
+	}
+
+      lbound = CASE_LOW (label);
+
+      if (TREE_CODE (lbound) != INTEGER_CST
+	  || (CASE_HIGH (label) != NULL_TREE
+	      && TREE_CODE (CASE_HIGH (label)) != INTEGER_CST))
+	{
+	  reason = "non-cst label.\n";
+	  return false; 
+	}
+
+      if (CASE_HIGH (label) == NULL_TREE)
+	hbound = lbound;
+      else
+	hbound = CASE_HIGH (label);
+
+      if (min == NULL_TREE
+	  || folder_evaluate_lt (lbound, min))
+	min = lbound;
+
+      if (max == NULL_TREE
+	  || folder_evaluate_lt (max, hbound))
+	max = hbound;
+    }
+
+  if (!default_present)
+    {
+      reason = "there is no default case.\n";
+      return false;
+    }
+
+  gcc_assert (min != NULL_TREE); /* switch statements should not be empty */
+
+  range_min = min;
+  range_max = max;
+  
+  range_size = fold_build2 (MINUS_EXPR, index_type, max, min);
+  if (TREE_INT_CST_HIGH (range_size) 
+      || (TREE_INT_CST_LOW (range_size) > MAX_ARRAY_RANGE))
+    {
+      reason = "index range way too large.\n";
+      return false; 
+    }
+
+  if (TREE_INT_CST_LOW (range_size) > ((unsigned) branch_num * 
+				       MAX_RANGE_BRANCH_RATIO))
+    {
+      reason = "the maximum range-branch ratio exceeded.";
+      return false;
+    }
+
+  return true;
+}
+
+/* Creates a list of values for all assigned variables given by the PHI nodes
+   of the given basic block and the edge.  The list is in the order of the PHI
+   nodes. */
+static tree 
+create_val_list (basic_block bb, edge e)
+{
+  tree phi;
+  tree list = NULL_TREE;
+
+  for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 
+    {
+      tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
+      list = tree_cons (NULL_TREE, val, list);
+    }
+
+  return nreverse (list);
+}
+
+/* Adds the given cs switch case and its list of values to the branch_list. */
+static void 
+insert_val_list (tree cs, tree vals)
+{
+  tree *t;
+  tree node;
+
+  t = &branch_list; 
+  while (*t != NULL_TREE
+	 && folder_evaluate_lt (CASE_LOW (cs), CASE_LOW (TREE_PURPOSE (*t))))
+    t = &TREE_CHAIN (*t);
+     
+  node = tree_cons (cs, vals, *t);
+  *t = node;
+  return;
+}
+
+/* Checks the given cs switch case whether it is suitable for conversion
+   (whether all but the default basic blocks are empty, whether assigned values
+   are constants 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, vals;
+  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 (!empty_block_p (label_bb))
+    {
+      if (final_bb && final_bb != label_bb)
+	{
+	  reason = "  Bad case - a non-final BB not empty\n";
+	  return false; /* sth complex going on in this branch  */
+	}
+
+      following_bb = label_bb;
+    } 
+  else 
+    {
+      if (!single_pred_p (label_bb))
+	{
+	  reason = "  Bad case - case BB has more than one predecessor\n";
+	  return false;
+	}
+
+      e = single_succ_edge (label_bb);
+      following_bb = single_succ (label_bb);
+    }
+
+  if (!final_bb) 
+    {
+      tree phi;
+      final_bb = following_bb;
+
+      for (phi = phi_nodes (following_bb); phi; phi = PHI_CHAIN (phi)) 
+	{
+	  int i;
+
+	  for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+	    if (!is_gimple_min_invariant (PHI_ARG_ELT (phi, i).def))
+	      {
+		reason = "  Bad case - non-invariant value\n";
+		return false; 		/* non invariant argument */
+	      }
+	}
+    } 
+  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 */
+    }
+
+  SET_BIT (rel_bbs, label_bb->index);
+
+  vals = create_val_list (following_bb, e);
+
+  if (!CASE_LOW (cs)) 
+    default_values = vals;
+  else 
+    insert_val_list (cs, vals);
+
+  return true;
+}
+
+/* check_phi_edges() traverses all predecessors of final_bb in the cfg and uses
+   rel_bbs to ensure all incoming edges come from the switch.  It returns true
+   in this case, false otherwise.  */
+static bool
+check_phi_edges (void)
+{
+  edge_iterator ei;
+  edge e;
+
+  FOR_EACH_EDGE (e, ei, final_bb->preds)
+    {
+      basic_block bb = e->src;
+
+      if (!TEST_BIT (rel_bbs, bb->index))
+	return false;
+    }  
+
+  return true;
+}
+
+/* build_one_array() creates an appropriate array type and declaration and
+   assembles a static array variable.  It also creates a load statement that
+   initializes a temporary with a value from the array and replaces all
+   immediate uses of the original phi node with this temporary. */
+static bool 
+build_one_array (tree vallist, tree dflt, tree phi)
+{ 
+  tree array_type, arr_index_type;
+  tree constructor;
+  tree decl;
+  char name_buf[32];
+  tree tmp_var;
+
+  tree fetch, load;
+  block_stmt_iterator bsi;
+
+  use_operand_p imm_use_p;
+  tree imm_use_stmt;
+  imm_use_iterator iterator;
+
+  static unsigned int name_num = 1;
+
+  gcc_assert (range_size);
+  arr_index_type = build_index_type (range_size);
+
+  array_type = build_array_type (TREE_TYPE (dflt), arr_index_type); 
+  constructor = build_constructor_from_list (array_type, vallist);
+
+  decl = build_decl (VAR_DECL, NULL_TREE, array_type); 
+  TREE_STATIC (decl) = 1;
+  DECL_INITIAL (decl) = constructor;
+
+  sprintf (name_buf, "CSWTCH%02u", name_num++);
+  DECL_NAME (decl) = get_identifier (name_buf);
+  DECL_ARTIFICIAL (decl) = 1;
+  TREE_CONSTANT (decl) = 1;
+  add_referenced_var (decl);
+  assemble_variable (decl, 0, 0, 0);
+  mark_sym_for_renaming (decl);
+
+  tmp_var = make_rename_temp (TREE_TYPE (dflt), "cstv");
+
+  fetch = build4 (ARRAY_REF, TREE_TYPE (dflt), decl, index_expr,
+		  range_min, NULL_TREE); 
+  load = build2 (GIMPLE_MODIFY_STMT, void_type_node, tmp_var, fetch);
+
+  bsi = bsi_start (final_bb);
+  bsi_insert_before (&bsi, load, BSI_SAME_STMT);
+  mark_symbols_for_renaming (load);
+
+  mark_sym_for_renaming (SSA_NAME_VAR (PHI_RESULT (phi)));
+
+  target_list = tree_cons (NULL_TREE, tmp_var, target_list);
+
+  FOR_EACH_IMM_USE_STMT (imm_use_stmt, iterator, PHI_RESULT (phi))
+    {
+      push_stmt_changes (&imm_use_stmt);
+      FOR_EACH_IMM_USE_ON_STMT (imm_use_p, iterator)
+	{
+	  SET_USE (imm_use_p, tmp_var);
+	}
+      pop_stmt_changes (&imm_use_stmt); 
+    }
+
+  if (!arr_ref_end)
+    arr_ref_end = load;
+  
+  return true;
+}
+
+/* Builds and initializes static arrays initialised with values gathered from
+   the switch statement.  Also creates statements that assign a value.  */
+static bool 
+build_arrays (void)
+{
+  tree ref = branch_list; 
+  tree phi = phi_nodes (final_bb);
+  tree def = default_values;
+
+  gcc_assert (def);
+    
+  if (!ref) 
+    return false; 
+
+  /* for each phi node */
+  while (def) 
+    {
+      tree index;
+      tree dflt_val;
+      tree newlist = NULL_TREE;
+
+      ref = branch_list; 
+
+      dflt_val = TREE_VALUE (def);
+      def = TREE_CHAIN (def);
+  
+      /* index = max index: */
+      index = CASE_HIGH (TREE_PURPOSE (ref)); 
+      if (!index)
+	index = CASE_LOW (TREE_PURPOSE (ref)); 
+
+      for ( ; ref; ref = TREE_CHAIN (ref))  /* for every case statement range */
+	{
+	  tree cs = TREE_PURPOSE (ref); 
+	  tree vals = TREE_VALUE (ref);
+	  tree value;
+	  tree pos;  
+	  
+	  pos = CASE_HIGH (cs); 
+	  if (!pos)
+	    pos = CASE_LOW (cs);
+
+	  /* gaps in between the adjacent ranges are filled with the default
+	     value */
+	  while (folder_evaluate_lt (pos, index)) 
+	    {
+	      newlist = tree_cons (NULL_TREE, dflt_val, newlist);
+	      index = fold_build2 (MINUS_EXPR, index_type, index, 
+				   integer_one_node);
+	    }
+
+	  /* values corresponding to the range are filled by the appropriate
+	     value */
+	  value = TREE_VALUE (vals);
+	  TREE_VALUE (ref) = TREE_CHAIN (vals);
+	  while (folder_evaluate_le (CASE_LOW (cs), index)) 
+	    {
+	      newlist = tree_cons (NULL_TREE, value, newlist);
+	      
+	      if (folder_evaluate_eq (TYPE_MIN_VALUE (TREE_TYPE (index)), 
+				      index))
+		break; /* must not underflow unsigned types */
+
+	      index = fold_build2 (MINUS_EXPR, index_type, index, 
+				  integer_one_node);
+	    }
+	}
+
+      build_one_array (newlist, dflt_val, phi);
+
+      remove_phi_node (phi, NULL_TREE, true);
+      phi = phi_nodes (final_bb);
+    }
+
+  return true;
+}
+
+/* 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)
+{
+  tree targets = nreverse (target_list);
+  tree def = default_values;
+  tree assign = NULL_TREE;
+
+  while (def) 
+    {
+      tree dflt_val  = TREE_VALUE (def);
+      tree tmp_var = TREE_VALUE (targets);
+      
+      assign = build2 (GIMPLE_MODIFY_STMT, void_type_node, 
+		       tmp_var, dflt_val);
+      bsi_insert_before (bsi, assign, BSI_SAME_STMT);
+      find_new_referenced_vars (&assign);
+      mark_symbols_for_renaming (assign);
+      
+      def = TREE_CHAIN (def);
+      targets = TREE_CHAIN (targets);
+    }
+  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);
+}
+
+/* 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 final_bb but split in two so that bb2 has a fall through
+
+   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 (index_type);
+  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, e2d, e1f, e2f;
+
+  gcc_assert (default_values);
+  bb0 = bb_for_stmt (swtch);
+
+  /* (end of) block 0 */
+  bsi = bsi_for_stmt (swtch);
+  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_build2 (MINUS_EXPR, index_type, range_max, range_min);
+  bound = fold_convert (utype, bound);
+
+  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 (swtch);
+  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_start (final_bb);
+  label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
+  bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
+
+  /* block F */
+  bsi = bsi_for_stmt (arr_ref_end);
+  bsi_next (&bsi);
+  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;
+
+  e2d = split_block (bb2, last_assign);
+  bbd = e2d->dest;
+  remove_edge (e2d);
+
+  bb1 = final_bb;
+  e1f = split_block (bb1, arr_ref_end);
+  bbf = e1f->dest;
+  
+  /* 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;
+
+  /* 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;
+
+  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);
+  bbd->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f);
+  
+  free_dominance_info (CDI_DOMINATORS);
+  free_dominance_info (CDI_POST_DOMINATORS);
+
+  prune_bbs (bbd, final_bb); /* to keep calc_dfs_tree() in dominance.c
+				happy */
+}
+
+/* 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;
+
+  /* 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);
+  branch_list = NULL_TREE;
+  target_list = NULL_TREE;
+  arr_ref_end = 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;
+
+  rel_bbs = sbitmap_alloc (cfun->cfg->x_last_basic_block);
+  sbitmap_zero (rel_bbs);
+  SET_BIT (rel_bbs, switch_bb->index);
+
+  /* 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);
+	  goto fail;
+	}
+    }
+
+  /* Check whether all edges to the final bb come from the switch BBs.  */
+  if (!check_phi_edges ())
+    {
+      reason = "incoming edges from outside of the switch stmt.\n";
+      goto fail;
+    }
+ 
+  /* try to build the static arrays */
+  if (!build_arrays ()) 
+    {
+      reason = "building arrays failed\n";
+      goto fail;
+    }
+
+  gen_inbound_check (swtch); 
+  sbitmap_free (rel_bbs);
+  return true;
+
+ fail:
+  sbitmap_free (rel_bbs);
+  return false;
+}
+
+/* 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) 
+  {
+    block_stmt_iterator bsi;
+    bsi = bsi_last (bb);
+
+    if (!bsi_end_p (bsi))
+      {
+	tree stmt = bsi_stmt (bsi);
+	
+	if (TREE_CODE (stmt) == SWITCH_EXPR) 
+	  {
+	    if (dump_file)
+	      {
+		fprintf (dump_file, "\nBeginning 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 128023)
+++ gcc/common.opt	(working copy)
@@ -1094,6 +1094,10 @@ ftree-sra
 Common Report Var(flag_tree_sra) Optimization
 Perform scalar replacement of aggregates
 
+ftree-cswtch
+Common Report Var(flag_tree_cswtch) Optimization
+Perform conversions of switch initializations.
+
 ftree-ter
 Common Report Var(flag_tree_ter) Optimization
 Replace temporary expressions in the SSA->normal pass
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in	(revision 128023)
+++ gcc/Makefile.in	(working copy)
@@ -1157,6 +1157,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 \
@@ -2566,6 +2567,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)
 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 128023)
+++ gcc/passes.c	(working copy)
@@ -550,6 +550,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);
       NEXT_PASS (pass_return_slot);
       NEXT_PASS (pass_rename_ssa_copies);