This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH, middle-end] Switch initializations conversion
- From: Martin Jambor <jamborm at matfyz dot cz>
- To: GCC Patches <gcc-patches at gcc dot gnu dot org>
- Date: Tue, 11 Sep 2007 14:23:00 +0200
- Subject: Re: [PATCH, middle-end] Switch initializations conversion
- References: <20070824111742.GA12389@matfyz.cz> <20070828091225.GA11047@matfyz.cz> <20070828093037.GT2063@devserv.devel.redhat.com> <20070904133528.GA14194@matfyz.cz>
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