From b6e99746ac31845e39844334378bafbb9a93517c Mon Sep 17 00:00:00 2001 From: Martin Jambor Date: Tue, 1 Jul 2008 10:54:18 +0200 Subject: [PATCH] Makefile.in (tree-switch-conversion.o): Add. 2008-07-01 Martin Jambor * Makefile.in (tree-switch-conversion.o): Add. (OBJS-common): Add tree-swtch-conversion.o. * passes.c (init_optimization_passes): Add pass_convert_switch. * tree-pass.h: (pass_convert_switch): Add. * tree-switch-conversion.c: New file. * gcc.dg/tree-ssa/cswtch.c: New testcase. * common.opt (ftree-cswtch): New option. * params.h (PARAM_SWITCH_CONVERSION_BRANCH_RATIO): New parameter. * params.def (PARAM_SWITCH_CONVERSION_BRANCH_RATIO): New parameter. * opts.c (decode_options): Set flag_tree_switch_conversion when optimization level is >= 2. * doc/invoke.texi (Optimize Options): Added description of -ftree-swtch-conversion and switch-conversion-max-branch-ratio. From-SVN: r137313 --- gcc/ChangeLog | 15 + gcc/Makefile.in | 6 + gcc/common.opt | 4 + gcc/doc/invoke.texi | 19 +- gcc/opts.c | 1 + gcc/params.def | 9 + gcc/params.h | 2 + gcc/passes.c | 1 + gcc/testsuite/gcc.dg/tree-ssa/cswtch.c | 81 +++ gcc/tree-pass.h | 1 + gcc/tree-switch-conversion.c | 878 +++++++++++++++++++++++++++++++++ 11 files changed, 1013 insertions(+), 4 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/cswtch.c create mode 100644 gcc/tree-switch-conversion.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index a48eef2..7084a42 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,18 @@ +2008-07-01 Martin Jambor + * Makefile.in (tree-switch-conversion.o): Add. + (OBJS-common): Add tree-swtch-conversion.o. + * passes.c (init_optimization_passes): Add pass_convert_switch. + * tree-pass.h: (pass_convert_switch): Add. + * tree-switch-conversion.c: New file. + * gcc.dg/tree-ssa/cswtch.c: New testcase. + * common.opt (ftree-cswtch): New option. + * params.h (PARAM_SWITCH_CONVERSION_BRANCH_RATIO): New parameter. + * params.def (PARAM_SWITCH_CONVERSION_BRANCH_RATIO): New parameter. + * opts.c (decode_options): Set flag_tree_switch_conversion when + optimization level is >= 2. + * doc/invoke.texi (Optimize Options): Added description of + -ftree-swtch-conversion and switch-conversion-max-branch-ratio. + 2008-06-30 Kaveh R. Ghazi * config/darwin-driver.c (darwin_default_min_version): Fix diff --git a/gcc/Makefile.in b/gcc/Makefile.in index b29b0a8..a792144 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1176,6 +1176,7 @@ OBJS-common = \ tree-profile.o \ tree-scalar-evolution.o \ tree-sra.o \ + tree-switch-conversion.o \ tree-ssa-address.o \ tree-ssa-alias.o \ tree-ssa-alias-warnings.o \ @@ -2629,6 +2630,11 @@ tree-sra.o : tree-sra.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) $(RTL_H) \ $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) $(TREE_GIMPLE_H) \ langhooks.h tree-pass.h $(FLAGS_H) $(EXPR_H) $(BASIC_BLOCK_H) \ bitmap.h $(GGC_H) hard-reg-set.h $(OBSTACK_H) $(PARAMS_H) $(TARGET_H) +tree-switch-conversion.o : tree-switch-conversion.c $(CONFIG_H) $(SYSTEM_H) \ + $(TREE_H) $(TM_P_H) $(TREE_FLOW_H) $(DIAGNOSTIC_H) $(TREE_INLINE_H) \ + $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) $(TREE_GIMPLE_H) \ + tree-pass.h $(FLAGS_H) $(EXPR_H) $(BASIC_BLOCK_H) output.h \ + $(GGC_H) $(OBSTACK_H) $(PARAMS_H) $(CPPLIB_H) $(PARAMS_H) tree-complex.o : tree-complex.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TREE_H) \ $(TM_H) $(RTL_H) $(REAL_H) $(FLAGS_H) $(TREE_FLOW_H) $(TREE_GIMPLE_H) \ tree-iterator.h tree-pass.h tree-ssa-propagate.h $(DIAGNOSTIC_H) diff --git a/gcc/common.opt b/gcc/common.opt index 94f2c56..200425d 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -1088,6 +1088,10 @@ ftree-cselim Common Report Var(flag_tree_cselim) Init(2) Optimization Transform condition stores into unconditional ones +ftree-switch-conversion +Common Report Var(flag_tree_switch_conversion) Optimization +Perform conversions of switch initializations. + ftree-dce Common Report Var(flag_tree_dce) Optimization Enable SSA dead code elimination optimization on trees diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index c59d88e..ee3b1c1 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -359,10 +359,10 @@ Objective-C and Objective-C++ Dialects}. -ftree-loop-distribution @gol -ftree-loop-ivcanon -ftree-loop-linear -ftree-loop-optimize @gol -ftree-parallelize-loops=@var{n} -ftree-pre -ftree-reassoc @gol --ftree-sink -ftree-sra -ftree-store-ccp -ftree-ter @gol --ftree-vect-loop-version -ftree-vectorize -ftree-vrp -funit-at-a-time @gol --funroll-all-loops -funroll-loops -funsafe-loop-optimizations @gol --funsafe-math-optimizations -funswitch-loops @gol +-ftree-sink -ftree-sra -ftree-store-ccp -ftree-switch-conversion @gol +-ftree-ter -ftree-vect-loop-version -ftree-vectorize -ftree-vrp @gol +-funit-at-a-time -funroll-all-loops -funroll-loops @gol +-funsafe-loop-optimizations -funsafe-math-optimizations -funswitch-loops @gol -fvariable-expansion-in-unroller -fvect-cost-model -fvpt -fweb @gol -fwhole-program @gol --param @var{name}=@var{value} @@ -5194,6 +5194,7 @@ also turns on the following optimization flags: -fsched-interblock -fsched-spec @gol -fschedule-insns -fschedule-insns2 @gol -fstrict-aliasing -fstrict-overflow @gol +-ftree-switch-conversion @gol -ftree-pre @gol -ftree-vrp} @@ -5868,6 +5869,11 @@ pass operates on both local scalar variables and memory stores and loads (global variables, structures, arrays, etc). This flag is enabled by default at @option{-O2} and higher. +@item -ftree-switch-conversion +Perform conversion of simple initializations in a switch to +initializations from a scalar array. This flag is enabled by default +at @option{-O2} and higher. + @item -ftree-dce @opindex ftree-dce Perform dead code elimination (DCE) on trees. This flag is enabled by @@ -7344,6 +7350,11 @@ mechanism for comparing types in C++ and Objective-C++. However, if bugs in the canonical type system are causing compilation failures, set this value to 0 to disable canonical types. +@item switch-conversion-max-branch-ratio +Switch initialization conversion will refuse to create arrays that are +bigger than @option{cswtch-max-branch-ratio} times the number of +branches in the switch. + @item max-partial-antic-length Maximum length of the partial antic set computed during the tree partial redundancy elimination optimization (@option{-ftree-pre}) when diff --git a/gcc/opts.c b/gcc/opts.c index 226030b..0bea9e4 100644 --- a/gcc/opts.c +++ b/gcc/opts.c @@ -891,6 +891,7 @@ decode_options (unsigned int argc, const char **argv) flag_reorder_functions = 1; flag_tree_store_ccp = 1; flag_tree_vrp = 1; + flag_tree_switch_conversion = 1; if (!optimize_size) { diff --git a/gcc/params.def b/gcc/params.def index d80deff..d1f8fce 100644 --- a/gcc/params.def +++ b/gcc/params.def @@ -710,6 +710,15 @@ DEFPARAM (PARAM_DF_DOUBLE_QUEUE_THRESHOLD_FACTOR, "Multiplier used for determining the double-queueing threshold", 2, 0, 0) +/* Switch initialization conversion will refuse to create arrays that are + bigger than this parameter times the number of switch branches. */ + +DEFPARAM (PARAM_SWITCH_CONVERSION_BRANCH_RATIO, + "switch-conversion-max-branch-ratio", + "The maximum ratio between array size and switch branches for " + "a switch conversion to take place", + 8, 1, 0) + /* Local variables: mode:c diff --git a/gcc/params.h b/gcc/params.h index bb3afb3..7e08ec7 100644 --- a/gcc/params.h +++ b/gcc/params.h @@ -167,4 +167,6 @@ typedef enum compiler_param PARAM_VALUE (PARAM_L2_CACHE_SIZE) #define USE_CANONICAL_TYPES \ PARAM_VALUE (PARAM_USE_CANONICAL_TYPES) +#define SWITCH_CONVERSION_BRANCH_RATIO \ + PARAM_VALUE (PARAM_SWITCH_CONVERSION_BRANCH_RATIO) #endif /* ! GCC_PARAMS_H */ diff --git a/gcc/passes.c b/gcc/passes.c index ba6151a..e1d019f 100644 --- a/gcc/passes.c +++ b/gcc/passes.c @@ -572,6 +572,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); } diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cswtch.c b/gcc/testsuite/gcc.dg/tree-ssa/cswtch.c new file mode 100644 index 0000000..06710f2 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/cswtch.c @@ -0,0 +1,81 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-switchconv" } */ +/* { dg-do run } */ + +extern void abort (void); + +static int X, Y; + +int check(int param) +{ + int a = 0; + int b = 1; + + switch (param) + { + case -2: + a = 0; + b = -1; + break; + case 1: + case 2: + a = 8; + b = 6; + break; + case 3: + a = 9; + b = 5; + break; + case 6: + a = 10; + b = 4; + break; + default: + a = 16; + b = 1; + } + + X = a; + Y = b; + return 0; +} + +void assertions(int a, int b) +{ + if (X != a || Y != b) + abort(); + + return; +} + +int main () +{ + check (-10); + assertions (16, 1); + + check (-2); + assertions (0, -1); + + check(1); + assertions (8, 6); + + check(2); + assertions (8, 6); + + check(3); + assertions (9, 5); + + check(5); + assertions (16, 1); + + check(6); + assertions (10, 4); + + check(12); + assertions (16, 1); + + return 0; +} + +/* { dg-final { scan-tree-dump "Switch converted" "switchconv" } } */ +/* { dg-final { cleanup-tree-dump "switchconv" } } */ diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index d1f615a..c695863 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -508,6 +508,7 @@ extern struct gimple_opt_pass pass_O0_always_inline; extern struct gimple_opt_pass pass_inline_parameters; extern struct gimple_opt_pass pass_all_early_optimizations; extern struct gimple_opt_pass pass_update_address_taken; +extern struct gimple_opt_pass pass_convert_switch; /* The root of the compilation pass tree, once constructed. */ extern struct opt_pass *all_passes, *all_ipa_passes, *all_lowering_passes; diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c new file mode 100644 index 0000000..940801e --- /dev/null +++ b/gcc/tree-switch-conversion.c @@ -0,0 +1,878 @@ +/* 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 + +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 + b_5 = PHI + + +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 + b_b = PHI + +There are further constraints. Specifically, the range of values across all +case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default +eight) times the number of the actual switch branches. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include + +#include "line-map.h" +#include "params.h" +#include "flags.h" +#include "tree.h" +#include "basic-block.h" +#include "tree-flow.h" +#include "tree-flow-inline.h" +#include "tree-ssa-operands.h" +#include "output.h" +#include "input.h" +#include "tree-pass.h" +#include "diagnostic.h" +#include "tree-dump.h" + +/* The main structure of the pass. */ +struct switch_conv_info +{ + /* The expression used to decide the switch branch. (It is subsequently used + as the index to the created array.) */ + tree index_expr; + + /* The following integer constants store the minimum value covered by the + cases. */ + tree range_min; + + /* The difference of between the above two numbers, i.e. The size of the array + that would have to be created by the transformation. */ + tree range_size; + + /* Basic block that contains the actual SWITCH_EXPR. */ + basic_block switch_bb; + + /* All branches of the switch statement must have a single successor stored in + the following variable. */ + basic_block final_bb; + + /* Number of phi nodes in the final bb (that we'll be replacing). */ + int phi_count; + + /* Array of default values, n the same order as phi nodes. */ + tree *default_values; + + /* Constructors of new static arrays. */ + VEC (constructor_elt, gc) **constructors; + + /* Array of ssa names that are initialized with a value from a new static + array. */ + tree *target_inbound_names; + + /* Array of ssa names that are initialized with the default value if the + switch expression is out of range. */ + tree *target_outbound_names; + + /* The probability of the default edge in the replaced switch. */ + int default_prob; + + /* The count of the default edge in the replaced switch. */ + gcov_type default_count; + + /* Combined count of all other (non-default) edges in the replaced switch. */ + gcov_type other_count; + + /* The last load statement that loads a temporary from a new static array. */ + tree arr_ref_first; + + /* The last load statement that loads a temporary from a new static array. */ + tree arr_ref_last; + + /* String reason why the case wasn't a good candidate that is written to the + dump file, if there is one. */ + const char *reason; +}; + +/* Global pass info. */ +static struct switch_conv_info info; + + +/* Checks whether the range given by individual case statements of the SWTCH + switch statement isn't too big and whether the number of branches actually + satisfies the size of the new array. */ + +static bool +check_range (tree swtch) +{ + tree min_case, max_case; + tree cases = SWITCH_LABELS (swtch); + unsigned int branch_num = TREE_VEC_LENGTH (cases); + tree range_max; + + /* The gimplifier has already sorted the cases by CASE_LOW and ensured there + is a default label which is the last in the vector. */ + + min_case = TREE_VEC_ELT (cases, 0); + info.range_min = CASE_LOW (min_case); + + gcc_assert (branch_num > 1); + gcc_assert (CASE_LOW (TREE_VEC_ELT (cases, branch_num - 1)) == NULL_TREE); + max_case = TREE_VEC_ELT (cases, branch_num - 2); + if (CASE_HIGH (max_case) != NULL_TREE) + range_max = CASE_HIGH (max_case); + else + range_max = CASE_LOW (max_case); + + gcc_assert (info.range_min); + gcc_assert (range_max); + + info.range_size = int_const_binop (MINUS_EXPR, range_max, info.range_min, 0); + + gcc_assert (info.range_size); + if (!host_integerp (info.range_size, 1)) + { + info.reason = "index range way too large or otherwise unusable.\n"; + return false; + } + + if ((unsigned HOST_WIDE_INT) tree_low_cst (info.range_size, 1) + > ((unsigned) branch_num * SWITCH_CONVERSION_BRANCH_RATIO)) + { + info.reason = "the maximum range-branch ratio exceeded.\n"; + return false; + } + + return true; +} + +/* Checks the given CS switch case whether it is suitable for conversion + (whether all but the default basic blocks are empty and so on). If it is, + adds the case to the branch list along with values for the defined variables + and returns true. Otherwise returns false. */ + +static bool +check_process_case (tree cs) +{ + tree ldecl; + basic_block label_bb, following_bb; + edge e; + + ldecl = CASE_LABEL (cs); + label_bb = label_to_block (ldecl); + + e = find_edge (info.switch_bb, label_bb); + gcc_assert (e); + + if (CASE_LOW (cs) == NULL_TREE) + { + /* Default branch. */ + info.default_prob = e->probability; + info.default_count = e->count; + } + else + info.other_count += e->count; + + if (!label_bb) + { + info.reason = " Bad case - cs BB label is NULL\n"; + return false; + } + + if (!single_pred_p (label_bb)) + { + if (info.final_bb && info.final_bb != label_bb) + { + info.reason = " Bad case - a non-final BB has two predecessors\n"; + return false; /* sth complex going on in this branch */ + } + + following_bb = label_bb; + } + else + { + if (!empty_block_p (label_bb)) + { + info.reason = " Bad case - a non-final BB not empty\n"; + return false; + } + + e = single_succ_edge (label_bb); + following_bb = single_succ (label_bb); + } + + if (!info.final_bb) + info.final_bb = following_bb; + else if (info.final_bb != following_bb) + { + info.reason = " Bad case - different final BB\n"; + return false; /* the only successor is not common for all the branches */ + } + + return true; +} + +/* This function checks whether all required values in phi nodes in final_bb + are constants. Required values are those that correspond to a basic block + which is a part of the examined switch statement. It returns true if the + phi nodes are OK, otherwise false. */ + +static bool +check_final_bb (void) +{ + tree phi; + + info.phi_count = 0; + for (phi = phi_nodes (info.final_bb); phi; phi = PHI_CHAIN (phi)) + { + int i; + + info.phi_count++; + + for (i = 0; i < PHI_NUM_ARGS (phi); i++) + { + basic_block bb = PHI_ARG_EDGE (phi, i)->src; + + if ((bb == info.switch_bb + || (single_pred_p (bb) && single_pred (bb) == info.switch_bb)) + && !is_gimple_min_invariant (PHI_ARG_ELT (phi, i).def)) + { + info.reason = " Non-invariant value from a case\n"; + return false; /* non invariant argument */ + } + } + } + + return true; +} + +/* The following function allocates default_values, target_{in,out}_names and + constructors arrays. The last one is also populated with pointers to + vectors that will become constructors of new arrays. */ + +static void +create_temp_arrays (void) +{ + int i; + + info.default_values = (tree *) xcalloc (info.phi_count, sizeof (tree)); + info.constructors = (VEC (constructor_elt, gc) **) xcalloc (info.phi_count, + sizeof (tree)); + info.target_inbound_names = (tree *) xcalloc (info.phi_count, sizeof (tree)); + info.target_outbound_names = (tree *) xcalloc (info.phi_count, + sizeof (tree)); + + for (i = 0; i < info.phi_count; i++) + { + info.constructors[i] = VEC_alloc (constructor_elt, gc, + tree_low_cst (info.range_size, 1) + 1); + } +} + +/* Free 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 constructors and must be preserved. */ + +static void +free_temp_arrays (void) +{ + free (info.constructors); + free (info.default_values); + free (info.target_inbound_names); + free (info.target_outbound_names); +} + +/* Populate the array of default values in the order of phi nodes. + DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch. */ + +static void +gather_default_values (tree default_case) +{ + tree phi; + basic_block bb = label_to_block (CASE_LABEL (default_case)); + edge e; + int i; + + gcc_assert (CASE_LOW (default_case) == NULL_TREE); + + if (bb == info.final_bb) + e = find_edge (info.switch_bb, bb); + else + e = single_succ_edge (bb); + + for (phi = phi_nodes (info.final_bb), i = 0; phi; phi = PHI_CHAIN (phi), i++) + { + tree val = PHI_ARG_DEF_FROM_EDGE (phi, e); + gcc_assert (val); + info.default_values[i] = val; + } +} + +/* The following function populates the vectors in the constructors array with + future contents of the static arrays. The vectors are populated in the + order of phi nodes. SWTCH is the switch statement being converted. */ + +static void +build_constructors (tree swtch) +{ + int i; + tree cases = SWITCH_LABELS (swtch); + tree pos = info.range_min; + + for (i = 0; i < TREE_VEC_LENGTH (cases) - 1; i++) + { + tree cs = TREE_VEC_ELT (cases, i); + basic_block bb = label_to_block (CASE_LABEL (cs)); + edge e; + tree phi, high; + int j; + + if (bb == info.final_bb) + e = find_edge (info.switch_bb, bb); + else + e = single_succ_edge (bb); + gcc_assert (e); + + while (tree_int_cst_lt (pos, CASE_LOW (cs))) + { + int k; + for (k = 0; k < info.phi_count; k++) + { + constructor_elt *elt; + + elt = VEC_quick_push (constructor_elt, + info.constructors[k], NULL); + elt->index = int_const_binop (MINUS_EXPR, pos, info.range_min, 0); + elt->value = info.default_values[k]; + } + + pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0); + } + gcc_assert (tree_int_cst_equal (pos, CASE_LOW(cs))); + + j = 0; + if (CASE_HIGH (cs)) + high = CASE_HIGH (cs); + else + high = CASE_LOW(cs); + for (phi = phi_nodes (info.final_bb); phi; phi = PHI_CHAIN (phi)) + { + tree val = PHI_ARG_DEF_FROM_EDGE (phi, e); + pos = CASE_LOW (cs); + + while (!tree_int_cst_lt (high, pos)) + { + constructor_elt *elt; + + elt = VEC_quick_push (constructor_elt, + info.constructors[j], NULL); + elt->index = int_const_binop (MINUS_EXPR, pos, info.range_min, 0); + elt->value = val; + + pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0); + } + j++; + } + } +} + +/* Create an appropriate array type and declaration and assemble a static array + variable. Also create a load statement that initializes the variable in + question with a value from the static array. SWTCH is the switch statement + being converted, NUM is the index to arrays of constructors, default values + and target SSA names for this particular array. ARR_INDEX_TYPE is the type + of the index of the new array, PHI is the phi node of the final BB that + corresponds to the value that will be loaded from the created array. TIDX + is a temporary variable holding the index for loads from the new array. */ + +static void +build_one_array (tree swtch, int num, tree arr_index_type, tree phi, tree tidx) +{ + tree array_type; + tree ctor; + tree decl; + tree value_type; + tree name; + tree fetch, load; + block_stmt_iterator bsi; + + gcc_assert (info.default_values[num]); + value_type = TREE_TYPE (info.default_values[num]); + array_type = build_array_type (value_type, arr_index_type); + + ctor = build_constructor (array_type, info.constructors[num]); + TREE_CONSTANT (ctor) = true; + + decl = build_decl (VAR_DECL, NULL_TREE, array_type); + TREE_STATIC (decl) = 1; + DECL_INITIAL (decl) = ctor; + + DECL_NAME (decl) = create_tmp_var_name ("CSWTCH"); + DECL_ARTIFICIAL (decl) = 1; + TREE_CONSTANT (decl) = 1; + add_referenced_var (decl); + assemble_variable (decl, 0, 0, 0); + mark_sym_for_renaming (decl); + + name = make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi)), NULL_TREE); + info.target_inbound_names[num] = name; + + fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE, + NULL_TREE); + load = build2 (GIMPLE_MODIFY_STMT, void_type_node, name, fetch); + SSA_NAME_DEF_STMT (name) = load; + + bsi = bsi_for_stmt (swtch); + bsi_insert_before (&bsi, load, BSI_SAME_STMT); + mark_symbols_for_renaming (load); + + info.arr_ref_last = load; + + return; +} + +/* Builds and initializes static arrays initialized with values gathered from + the SWTCH switch statement. Also creates statements that load values from + them. */ + +static void +build_arrays (tree swtch) +{ + tree arr_index_type; + tree tidx, sub; + block_stmt_iterator bsi; + tree phi = phi_nodes (info.final_bb); + int i; + + arr_index_type = build_index_type (info.range_size); + tidx = make_rename_temp (arr_index_type, "csti"); + sub = build2 (MINUS_EXPR, TREE_TYPE (info.index_expr), info.index_expr, + fold_convert (TREE_TYPE (info.index_expr), info.range_min)); + sub = build2 (GIMPLE_MODIFY_STMT, void_type_node, tidx, sub); + + bsi = bsi_for_stmt (swtch); + bsi_insert_before (&bsi, sub, BSI_SAME_STMT); + mark_symbols_for_renaming (sub); + info.arr_ref_first = sub; + + for (phi = phi_nodes (info.final_bb), i = 0; phi; phi = PHI_CHAIN (phi), i++) + build_one_array (swtch, i, arr_index_type, phi, tidx); + + return; +} + +/* Generates and appropriately inserts loads of default values at the position + given by BSI. Returns the last inserted statement. */ + +static tree +gen_def_assigns (block_stmt_iterator *bsi) +{ + int i; + tree assign = NULL_TREE; + + for (i = 0; i < info.phi_count; i++) + { + tree name = make_ssa_name (SSA_NAME_VAR (info.target_inbound_names[i]), + NULL_TREE); + + info.target_outbound_names[i] = name; + assign = build2 (GIMPLE_MODIFY_STMT, void_type_node, name, + info.default_values[i]); + SSA_NAME_DEF_STMT (name) = assign; + bsi_insert_before (bsi, assign, BSI_SAME_STMT); + find_new_referenced_vars (&assign); + mark_symbols_for_renaming (assign); + } + return assign; +} + +/* Deletes the unused bbs and edges that now contain the switch statement and + its empty branch bbs. BBD is the now dead BB containing the original switch + statement, FINAL is the last BB of the converted switch statement (in terms + of succession). */ + +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); +} + +/* Add 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. BBF is the last switch basic block (see the + bbf description in the comment below). */ + +static void +fix_phi_nodes (edge e1f, edge e2f, basic_block bbf) +{ + tree phi; + int i; + + for (phi = phi_nodes (bbf), i = 0; phi; phi = PHI_CHAIN (phi), i++) + { + add_phi_arg (phi, info.target_inbound_names[i], e1f); + add_phi_arg (phi, info.target_outbound_names[i], e2f); + } + +} + +/* Creates a check whether the switch expression value actually falls into the + range given by all the cases. If it does not, the temporaries are loaded + with default values instead. SWTCH is the switch statement being converted. + + bb0 is the bb with the switch statement, however, we'll end it with a + condition instead. + + bb1 is the bb to be used when the range check went ok. It is derived from + the switch BB + + bb2 is the bb taken when the expression evaluated outside of the range + covered by the created arrays. It is populated by loads of default + values. + + bbF is a fall through for both bb1 and bb2 and contains exactly what + originally followed the switch statement. + + bbD contains the switch statement (in the end). It is unreachable but we + still need to strip off its edges. +*/ + +static void +gen_inbound_check (tree swtch) +{ + tree label_decl1 = create_artificial_label (); + tree label_decl2 = create_artificial_label (); + tree label_decl3 = create_artificial_label (); + tree label1, label2, label3; + + tree utype = unsigned_type_for (TREE_TYPE (info.index_expr)); + tree tmp_u; + tree cast, cast_assign; + tree ulb, minus, minus_assign; + tree bound; + + tree if_expr; + + tree last_assign; + block_stmt_iterator bsi; + basic_block bb0, bb1, bb2, bbf, bbd; + edge e01, e02, e21, e1d, e1f, e2f; + + gcc_assert (info.default_values); + bb0 = bb_for_stmt (swtch); + + /* (end of) block 0 */ + bsi = bsi_for_stmt (info.arr_ref_first); + tmp_u = make_rename_temp (utype, "csui"); + + cast = build1 (NOP_EXPR, utype, info.index_expr); + cast_assign = build2 (GIMPLE_MODIFY_STMT, void_type_node, tmp_u, cast); + find_new_referenced_vars (&cast_assign); + bsi_insert_before (&bsi, cast_assign, BSI_SAME_STMT); + mark_symbols_for_renaming (cast_assign); + + ulb = fold_convert (utype, info.range_min); + minus = build2 (MINUS_EXPR, utype, tmp_u, ulb); + minus_assign = build2 (GIMPLE_MODIFY_STMT, void_type_node, tmp_u, minus); + find_new_referenced_vars (&minus_assign); + bsi_insert_before (&bsi, minus_assign, BSI_SAME_STMT); + mark_symbols_for_renaming (minus_assign); + + bound = fold_convert (utype, info.range_size); + + if_expr = build3 (COND_EXPR, void_type_node, + build2 (LE_EXPR, boolean_type_node, tmp_u, bound), + NULL_TREE, NULL_TREE); + + find_new_referenced_vars (&if_expr); + bsi_insert_before (&bsi, if_expr, BSI_SAME_STMT); + mark_symbols_for_renaming (if_expr); + + /* block 2 */ + bsi = bsi_for_stmt (info.arr_ref_first); + label2 = build1 (LABEL_EXPR, void_type_node, label_decl2); + bsi_insert_before (&bsi, label2, BSI_SAME_STMT); + last_assign = gen_def_assigns (&bsi); + + /* block 1 */ + bsi = bsi_for_stmt (info.arr_ref_first); + label1 = build1 (LABEL_EXPR, void_type_node, label_decl1); + bsi_insert_before (&bsi, label1, BSI_SAME_STMT); + + /* block F */ + bsi = bsi_start (info.final_bb); + label3 = build1 (LABEL_EXPR, void_type_node, label_decl3); + bsi_insert_before (&bsi, label3, BSI_SAME_STMT); + + /* cfg fix */ + e02 = split_block (bb0, if_expr); + bb2 = e02->dest; + + e21 = split_block (bb2, last_assign); + bb1 = e21->dest; + remove_edge (e21); + + e1d = split_block (bb1, info.arr_ref_last); + bbd = e1d->dest; + remove_edge (e1d); + + /* flags and profiles of the edge for in-range values */ + e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE); + e01->probability = REG_BR_PROB_BASE - info.default_prob; + e01->count = info.other_count; + + /* flags and profiles of the edge taking care of out-of-range values */ + e02->flags &= ~EDGE_FALLTHRU; + e02->flags |= EDGE_FALSE_VALUE; + e02->probability = info.default_prob; + e02->count = info.default_count; + + bbf = info.final_bb; + + e1f = make_edge (bb1, bbf, EDGE_FALLTHRU); + e1f->probability = REG_BR_PROB_BASE; + e1f->count = info.other_count; + + e2f = make_edge (bb2, bbf, EDGE_FALLTHRU); + e2f->probability = REG_BR_PROB_BASE; + e2f->count = info.default_count; + + /* frequencies of the new BBs */ + bb1->frequency = EDGE_FREQUENCY (e01); + bb2->frequency = EDGE_FREQUENCY (e02); + bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f); + + prune_bbs (bbd, info.final_bb); /* to keep calc_dfs_tree() in dominance.c + happy */ + + fix_phi_nodes (e1f, e2f, bbf); + + free_dominance_info (CDI_DOMINATORS); + free_dominance_info (CDI_POST_DOMINATORS); +} + +/* The following function is invoked on every switch statement (the current one + is given in SWTCH) and runs the individual phases of switch conversion on it + one after another until one fails or the conversion is completed. */ + +static bool +process_switch (tree swtch) +{ + int i; + tree cases; + tree index_type; + + /* Operand 2 is either NULL_TREE or a vector of cases (stmt.c). */ + if (TREE_OPERAND (swtch, 2) == NULL_TREE) + { + info.reason = "swtch has no labels\n"; + return false; + } + + /* Comment from stmt.c: + The switch body is lowered in gimplify.c, we should never have switches + with a non-NULL SWITCH_BODY here. */ + gcc_assert (!SWITCH_BODY (swtch)); + + cases = SWITCH_LABELS (swtch); + info.final_bb = NULL; + info.switch_bb = bb_for_stmt (swtch); + info.index_expr = SWITCH_COND (swtch); + index_type = TREE_TYPE (info.index_expr); + info.arr_ref_first = NULL_TREE; + info.arr_ref_last = NULL_TREE; + info.default_prob = 0; + info.default_count = 0; + info.other_count = 0; + + /* An ERROR_MARK occurs for various reasons including invalid data type. + (comment from stmt.c) */ + if (index_type == error_mark_node) + { + info.reason = "index error.\n"; + return false; + } + + /* Check the case label values are within reasonable range: */ + if (!check_range (swtch)) + return false; + + /* For all the cases, see whether they are empty, the assignments they + represent constant and so on... */ + for (i = 0; i < TREE_VEC_LENGTH (cases); i++) + { + tree part_case = TREE_VEC_ELT (cases, i); + if (!check_process_case (part_case)) + { + if (dump_file) + fprintf (dump_file, "Processing of case %i failed\n", i); + return false; + } + } + + if (!check_final_bb ()) + return false; + + /* At this point all checks have passed and we can proceed with the + transformation. */ + + create_temp_arrays (); + gather_default_values (TREE_VEC_ELT (cases, TREE_VEC_LENGTH (cases) - 1)); + build_constructors (swtch); + + build_arrays (swtch); /* Build the static arrays and assignments. */ + gen_inbound_check (swtch); /* Build the bounds check. */ + + /* Cleanup: */ + free_temp_arrays (); + return true; +} + +/* The main function of the pass scans statements for switches and invokes + process_switch on them. */ + +static unsigned int +do_switchconv (void) +{ + basic_block bb; + + FOR_EACH_BB (bb) + { + tree stmt = last_stmt (bb); + if (stmt && TREE_CODE (stmt) == SWITCH_EXPR) + { + expanded_location loc = expand_location (EXPR_LOCATION (stmt)); + + if (dump_file) + { + fprintf (dump_file, "beginning to process the following " + "SWITCH statement (%s:%d) : ------- \n", + loc.file, loc.line); + print_generic_stmt (dump_file, stmt, 2); + fprintf (dump_file, "\n"); + } + + info.reason = NULL; + if (process_switch (stmt)) + { + if (dump_file) + { + fprintf (dump_file, "Switch converted\n"); + fprintf (dump_file, "--------------------------------\n"); + } + } + else + { + if (dump_file) + { + gcc_assert (info.reason); + fprintf (dump_file, "Bailing out - "); + fprintf (dump_file, info.reason); + fprintf (dump_file, "--------------------------------\n"); + } + } + } + } + + return 0; +} + +/* The pass gate. */ + +static bool +switchconv_gate (void) +{ + return flag_tree_switch_conversion != 0; +} + +struct gimple_opt_pass pass_convert_switch = +{ + { + GIMPLE_PASS, + "switchconv", /* name */ + switchconv_gate, /* gate */ + do_switchconv, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + 0, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_update_ssa | TODO_dump_func + | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */ + } +}; -- 2.7.4