public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH, middle-end] Switch initializations conversion (take four)
@ 2008-02-29 17:22 Martin Jambor
  2008-02-29 20:16 ` Mark Mitchell
  2008-04-03 12:55 ` [PATCH, middle-end] Switch initializations conversion (take four.1) Martin Jambor
  0 siblings, 2 replies; 14+ messages in thread
From: Martin Jambor @ 2008-02-29 17:22 UTC (permalink / raw)
  To: GCC Patches

Hi,

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

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

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

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

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

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

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

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

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

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

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

Martin


Changelog:

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


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

^ permalink raw reply	[flat|nested] 14+ messages in thread
end of thread, other threads:[~2008-04-10 13:53 UTC | newest]

Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2008-02-29 17:22 [PATCH, middle-end] Switch initializations conversion (take four) Martin Jambor
2008-02-29 20:16 ` Mark Mitchell
2008-02-29 20:57   ` Jan Hubicka
2008-03-04 20:23   ` Martin Jambor
2008-03-05  7:57     ` Mark Mitchell
2008-03-08 14:17     ` Jan Hubicka
2008-03-08 14:19       ` Jan Hubicka
2008-03-09  2:22       ` Mark Mitchell
2008-03-17 18:42         ` Martin Jambor
2008-04-03 12:55 ` [PATCH, middle-end] Switch initializations conversion (take four.1) Martin Jambor
2008-04-03 13:01   ` Diego Novillo
2008-04-03 13:47   ` Richard Guenther
2008-04-03 18:10     ` Roger Sayle
2008-04-10 14:54     ` [PATCH, middle-end] Switch initializations conversion (take four.2) Martin Jambor

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).