[PATCH, middle-end] Switch initializations conversion

Martin Jambor jamborm@matfyz.cz
Tue Sep 11 12:48:00 GMT 2007


Hi,

the third version of the  patch follows. I have changed somewhat magic
constants into parameters into  optimization parameters as required by
Mark  Mitchell  (http://gcc.gnu.org/ml/gcc/2007-09/msg00202.html)  and
added documentation  entries for  them and the  switch that  turns the
optimization on.

As noted in another email, I do have a FSF assignment
(http://misc.jamborm.net/Jambor305799.pdf).

The changelog would now be:

2007-09-10  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.
	* doc/invoke.texi (Optimize Options): Added description of
	-ftree-cswtch
	(Optimize Options): Added description of cswtch-max-array and
	cswtch-max-branch-ratio


Thanks a lot for reviewing,

Martin



Index: gcc/doc/invoke.texi
===================================================================
--- gcc/doc/invoke.texi	(revision 128343)
+++ gcc/doc/invoke.texi	(working copy)
@@ -360,7 +360,7 @@ Objective-C and Objective-C++ Dialects}.
 -ftree-loop-linear -ftree-loop-im -ftree-loop-ivcanon -fivopts @gol
 -fcheck-data-deps @gol
 -ftree-dominator-opts -ftree-dse -ftree-copyrename -ftree-sink @gol
--ftree-ch -ftree-sra -ftree-ter -ftree-fre -ftree-vectorize @gol
+-ftree-ch -ftree-cswtch -ftree-sra -ftree-ter -ftree-fre -ftree-vectorize @gol
 -ftree-vect-loop-version -fvect-cost-model -ftree-salias -fipa-pta -fweb @gol
 -ftree-copy-prop -ftree-store-ccp -ftree-store-copy-prop -fwhole-program @gol
 --param @var{name}=@var{value}
@@ -5070,6 +5070,7 @@ also turns on the following optimization
 -freorder-blocks  -freorder-functions @gol
 -falign-functions  -falign-jumps @gol
 -falign-loops  -falign-labels @gol
+-ftree-cswtch @gol
 -ftree-vrp @gol
 -ftree-pre}
 
@@ -5681,7 +5682,12 @@ enabled by default at @option{-O} and hi
 @item -ftree-ccp
 Perform sparse conditional constant propagation (CCP) on trees.  This
 pass only operates on local scalar variables and is enabled by default
-at @option{-O} and higher.
+at @option{-O} 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-store-ccp
 Perform sparse conditional constant propagation (CCP) on trees.  This
@@ -7051,6 +7057,15 @@ 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-array
+This is the maximum size of arrays (in number of elements) that switch
+conversion initialization is allowed to construct. 
+
+@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.
+
 @end table
 @end table
 
Index: gcc/tree-pass.h
===================================================================
--- gcc/tree-pass.h	(revision 128343)
+++ gcc/tree-pass.h	(working copy)
@@ -442,6 +442,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 128343)
+++ gcc/params.h	(working copy)
@@ -169,4 +169,8 @@ typedef enum compiler_param
   PARAM_VALUE (PARAM_L2_CACHE_SIZE)
 #define USE_CANONICAL_TYPES \
   PARAM_VALUE (PARAM_USE_CANONICAL_TYPES)
+#define CSWTCH_MAX_ARRAY \
+  PARAM_VALUE (PARAM_CSWTCH_MAX_ARRAY)
+#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,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 128343)
+++ gcc/opts.c	(working copy)
@@ -847,6 +847,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,890 @@
+/* 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 "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"
+
+/* 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) > (unsigned) CSWTCH_MAX_ARRAY))
+    {
+      reason = "index range way too large.\n";
+      return false; 
+    }
+
+  if (TREE_INT_CST_LOW (range_size) > ((unsigned) branch_num * 
+				       CSWTCH_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 128343)
+++ gcc/common.opt	(working copy)
@@ -1056,6 +1056,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 128343)
+++ gcc/Makefile.in	(working copy)
@@ -1158,6 +1158,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 \
@@ -2565,6 +2566,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 128343)
+++ gcc/passes.c	(working copy)
@@ -555,6 +555,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);
Index: gcc/params.def
===================================================================
--- gcc/params.def	(revision 128343)
+++ gcc/params.def	(working copy)
@@ -687,6 +687,23 @@ DEFPARAM (PARAM_USE_CANONICAL_TYPES,
 	  "use-canonical-types",
 	  "Whether to use canonical types",
 	  1, 0, 1)
+
+/* The maximum number of elements that arrays of switch initialization
+   conversion can have.  */
+DEFPARAM (PARAM_CSWTCH_MAX_ARRAY,
+	  "cswtch-max-array",
+	  "Maximum size of arrays switch initializations can be converted into "
+	  "(in elements)" ,
+	  0x2000, 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



More information about the Gcc-patches mailing list