[PATCH, middle-end] Switch initializations conversion
Martin Jambor
jamborm@matfyz.cz
Tue Aug 28 09:20:00 GMT 2007
Hi,
this is a new version of the same pass. The improvements/amendments
were rather minor:
1) I added a testcase.
2) I have changed the comment at the beginning of the file to sat GPL
version 3 rather than 2.
3) I have corrected the comments (and only the comments) at various
other places.
For further information, please see the previous posting (at
http://gcc.gnu.org/ml/gcc-patches/2007-08/msg01638.html)
As promised, I have collected at least some the information about how
much conversions are performed by the pass. Perhaps not surprisingly I
have counted the number of converted switches when bootstrapping gcc
with respect to the MAX_RANGE_BRANCH_RATIO constant. The results are
summarised in the following table:
MAX_RANGE_BRANCH_RATIO Converted switches
--------------------------------------------------
4 96
8 116
16 124
I have then decided to leave the constant as it was (i.e. 8). The
time overhead was not really measurable (i.e. All compilations took
about 247 minutes of user time and the unpatched version did so too).
The patch was regtested on x86_64-unknown-linux-gnu and bootsrapped
and regtested on i686-linux with all languages except Ada and with
"all,fold" checking.
I would therefore like to ask you to review it and consider applying.
I am still of course accepting any comments and indeed grateful for
them.
Thank you very much in advance,
Martin
:ADDPATCH middle-end:
Changelog:
2007-08-28 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.
Index: gcc/tree-pass.h
===================================================================
--- gcc/tree-pass.h (revision 127704)
+++ gcc/tree-pass.h (working copy)
@@ -438,6 +438,7 @@ extern struct tree_opt_pass pass_shorten
extern struct tree_opt_pass pass_set_nothrow_function_flags;
extern struct tree_opt_pass pass_final;
extern struct tree_opt_pass pass_rtl_seqabstr;
+extern struct tree_opt_pass pass_convert_switch;
extern struct tree_opt_pass pass_release_ssa_names;
extern struct tree_opt_pass pass_early_inline;
extern struct tree_opt_pass pass_inline_parameters;
Index: gcc/testsuite/gcc.dg/tree-ssa/cswtch.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/cswtch.c (revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/cswtch.c (revision 0)
@@ -0,0 +1,35 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-cswtch" } */
+
+extern int printf (const char *, ...);
+
+int main(int argc, int *argv[])
+{
+ int a = 0;
+ int b = 1;
+
+ 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;
+ }
+
+ printf("Result (for %d): %d - %d\n", argc, a, b);
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "Switch converted" "cswtch" } } */
+/* { dg-final { cleanup-tree-dump "cswtch" } } */
Index: gcc/tree-cswtch.c
===================================================================
--- gcc/tree-cswtch.c (revision 0)
+++ gcc/tree-cswtch.c (revision 0)
@@ -0,0 +1,907 @@
+/* Switch Conversion converts variable initializations based on switch
+ statements to initializations from a static array. Copyright (C) 2006, 2007
+ Free Software Foundation, Inc. Contributed by Martin Jambor
+ <jamborm@matfyz.cz>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 3, or (at your option) any
+later version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3. If not, write to the Free
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
+
+/*
+ Switch initialization conversion
+
+The following pass changes simple initializations of scalars in a switch
+statement into initializations from a static array. Obviously, the values must
+be constant and known at compile time and a default branch must be
+provided. For example, the following code:
+
+ int a,b;
+
+ switch (argc) {
+ case 1:
+ case 2:
+ a = 8;
+ b = 6;
+ break;
+ case 3:
+ a = 9;
+ b = 5;
+ break;
+ case 12:
+ a = 10;
+ b = 4;
+ break;
+ default:
+ a = 16;
+ b = 1;
+ }
+
+is changed into:
+
+ static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
+ static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
+ 16, 16, 10};
+
+ if (((unsigned) argc) - 1 < 11)
+ {
+ tmp1 = CSWTCH01[argc - 1];
+ tmp2 = CSWTCH02[argc - 1];
+ }
+ else
+ {
+ tmp1 = 1;
+ tmp2 = 16;
+ }
+
+And all subsequent occurrences of a and b where these values are used is
+replaced by tmp2 and tmp1 respectively.
+
+There are further constraints. Specifically, the range of values across all
+case labels must be smaller than 0x2000 and must not be bigger than eight times
+the number of the actual switch branches. Both of these constants are rather
+arbitrary but I do not believe they should be set by a compiler switch as no
+one would really bother to tweak them. Instead, they should be set to any
+fairly permissible value known not to cause trouble.
+
+*/
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include <signal.h>
+
+#include "line-map.h"
+
+#include "flags.h"
+#include "tree.h"
+#include "basic-block.h"
+#include "tree-flow.h"
+#include "tree-flow-inline.h"
+#include "tree-ssa-operands.h"
+#include "output.h"
+#include "tree-pass.h"
+#include "diagnostic.h"
+
+
+/* We never create arrays larger than the following constant (given in number
+ of elements). */
+#define MAX_ARRAY_RANGE 0x2000
+
+/* We never create arrays if the number of branches is not at least the range
+ divided by the following constant. */
+#define MAX_RANGE_BRANCH_RATIO 8
+
+/* The expression used to decide the switch branch. (It is subsequently used as
+ the index to the created array.) */
+static tree index_expr;
+
+/* The type of the above expression. */
+static tree index_type;
+
+/* The following integer constants store the minimum and the maximum covered by
+ the cases. */
+static tree range_min, range_max;
+
+/* The difference of between the above two numbers, i.e. the size of the array
+ that would have to be created by the transformation. */
+static tree range_size;
+
+/* Basic block that contains the actual SWITCH_EXPR. */
+static basic_block switch_bb;
+
+/* All branches of the switch statement must have a single successor stored in
+ the following variable. */
+static basic_block final_bb;
+
+/* A bitmap of BBs. The BB of the switch statement itself and the BBs of the
+ cases are signalled by one, bits corresponding to all other BBs are
+ zero. */
+static sbitmap rel_bbs;
+
+/* List of cases and associated assigned values. Each element's purpose is the
+ corresponding case of the switch, the value contains a list of values for
+ individual variables. The list is sorted in descending order by the switch
+ case ranges. */
+static tree branch_list;
+
+/* List of values that are assigned to individual variables when the default
+ branch is taken. */
+static tree default_values;
+
+/* List of temporary variables that are either initialized with a value from a
+ new static array or the default value if the switch expression is out of
+ range. */
+static tree target_list;
+
+/* The probability of the default edge in the replaced switch. */
+static int default_prob;
+
+/* The count of the default edge in the replaced switch. */
+static gcov_type default_count;
+
+/* Combined count of all other (non-default) edges in the replaced switch. */
+static gcov_type other_count;
+
+/* The last load statement that loads a temporary from a new static array. */
+static tree arr_ref_end;
+
+/* String reason why the case wasn't a good candidate that is written to the
+ dump file, if there is one. */
+static const char *reason;
+
+/* The following three functions evaluate "equal to" "less then," and "less
+ than or equal to" (receptively) of two integers represented by
+ INTEGER_CSTs. */
+static int folder_evaluate_rel (enum tree_code code, tree arg1, tree arg2)
+{
+ tree res;
+
+ res = fold_build2 (code, integer_type_node, arg1, arg2);
+ return integer_nonzerop (res);
+}
+
+static int folder_evaluate_eq (tree arg1, tree arg2)
+{
+ return folder_evaluate_rel (EQ_EXPR, arg1, arg2);
+}
+
+static int folder_evaluate_lt (tree arg1, tree arg2)
+{
+ return folder_evaluate_rel (LT_EXPR, arg1, arg2);
+}
+
+static int folder_evaluate_le (tree arg1, tree arg2)
+{
+ return folder_evaluate_rel (LE_EXPR, arg1, arg2);
+}
+
+/* Checks whether the range given by individual case statements isn't too big
+ and whether the number of branches actually satisfy the size of the new
+ array. */
+static bool
+check_range (tree swtch)
+{
+ int i;
+ tree min = NULL_TREE;
+ tree max = NULL_TREE;
+ tree cases = SWITCH_LABELS (swtch);
+ int branch_num = TREE_VEC_LENGTH (cases);
+ bool default_present = false;
+
+ /* loop over all switch labels */
+ for (i = 0; i < branch_num; i++)
+ {
+ tree lbound, hbound;
+ tree label = TREE_VEC_ELT (cases, i);
+
+ if (CASE_LOW (label) == NULL_TREE)
+ {
+ /* the default case */
+ default_present = true;
+ continue;
+ }
+
+ lbound = CASE_LOW (label);
+
+ if (TREE_CODE (lbound) != INTEGER_CST
+ || (CASE_HIGH (label) != NULL_TREE
+ && TREE_CODE (CASE_HIGH (label)) != INTEGER_CST))
+ {
+ reason = "non-cst label.\n";
+ return false;
+ }
+
+ if (CASE_HIGH (label) == NULL_TREE)
+ hbound = lbound;
+ else
+ hbound = CASE_HIGH (label);
+
+ if (min == NULL_TREE
+ || folder_evaluate_lt (lbound, min))
+ min = lbound;
+
+ if (max == NULL_TREE
+ || folder_evaluate_lt (max, hbound))
+ max = hbound;
+ }
+
+ if (!default_present)
+ {
+ reason = "there is no default case.\n";
+ return false;
+ }
+
+ gcc_assert (min != NULL_TREE); /* switch statements should not be empty */
+
+ range_min = min;
+ range_max = max;
+
+ range_size = fold_build2 (MINUS_EXPR, index_type, max, min);
+ if (TREE_INT_CST_HIGH (range_size)
+ || (TREE_INT_CST_LOW (range_size) > MAX_ARRAY_RANGE))
+ {
+ reason = "index range way too large.\n";
+ return false;
+ }
+
+ if (TREE_INT_CST_LOW (range_size) > ((unsigned) branch_num *
+ MAX_RANGE_BRANCH_RATIO))
+ {
+ reason = "the maximum range-branch ratio exceeded.";
+ return false;
+ }
+
+ return true;
+}
+
+/* Creates a list of values for all assigned variables given by the PHI nodes
+ of the given basic block and the edge. The list is in the order of the PHI
+ nodes. */
+static tree
+create_val_list (basic_block bb, edge e)
+{
+ tree phi;
+ tree list = NULL_TREE;
+
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ {
+ tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
+ list = tree_cons (NULL_TREE, val, list);
+ }
+
+ return nreverse (list);
+}
+
+/* Adds the given cs switch case and its list of values to the branch_list. */
+static void
+insert_val_list (tree cs, tree vals)
+{
+ tree *t;
+ tree node;
+
+ for (t = &branch_list;
+ (*t != NULL_TREE)
+ && (folder_evaluate_lt (CASE_LOW (cs), CASE_LOW (TREE_PURPOSE (*t))));
+ t = &TREE_CHAIN (*t))
+ ; /* empty loop body */
+
+ 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))
+ {
+ /* must not underflow unsigned types */
+ break;
+ }
+ 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 optimize >= 2;
+}
+
+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/Makefile.in
===================================================================
--- gcc/Makefile.in (revision 127704)
+++ gcc/Makefile.in (working copy)
@@ -1157,6 +1157,7 @@ OBJS-common = \
tree-profile.o \
tree-scalar-evolution.o \
tree-sra.o \
+ tree-cswtch.o \
tree-ssa-address.o \
tree-ssa-alias.o \
tree-ssa-alias-warnings.o \
@@ -2566,6 +2567,11 @@ tree-sra.o : tree-sra.c $(CONFIG_H) $(SY
$(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) $(TREE_GIMPLE_H) \
langhooks.h tree-pass.h $(FLAGS_H) $(EXPR_H) $(BASIC_BLOCK_H) \
bitmap.h $(GGC_H) hard-reg-set.h $(OBSTACK_H) $(PARAMS_H) $(TARGET_H)
+tree-cswtch.o : tree-cswtch.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) \
+ $(TM_P_H) $(TREE_FLOW_H) $(DIAGNOSTIC_H) $(TREE_INLINE_H) \
+ $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) $(TREE_GIMPLE_H) \
+ tree-pass.h $(FLAGS_H) $(EXPR_H) $(BASIC_BLOCK_H) output.h \
+ $(GGC_H) $(OBSTACK_H) $(PARAMS_H)
tree-complex.o : tree-complex.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TREE_H) \
$(TM_H) $(RTL_H) $(REAL_H) $(FLAGS_H) $(TREE_FLOW_H) $(TREE_GIMPLE_H) \
tree-iterator.h tree-pass.h tree-ssa-propagate.h $(DIAGNOSTIC_H)
Index: gcc/passes.c
===================================================================
--- gcc/passes.c (revision 127704)
+++ gcc/passes.c (working copy)
@@ -550,6 +550,7 @@ init_optimization_passes (void)
NEXT_PASS (pass_all_optimizations);
{
struct tree_opt_pass **p = &pass_all_optimizations.sub;
+ NEXT_PASS (pass_convert_switch);
NEXT_PASS (pass_create_structure_vars);
NEXT_PASS (pass_return_slot);
NEXT_PASS (pass_rename_ssa_copies);
@@ -564,6 +565,8 @@ init_optimization_passes (void)
NEXT_PASS (pass_merge_phi);
NEXT_PASS (pass_vrp);
NEXT_PASS (pass_dce);
+
+
NEXT_PASS (pass_dominator);
/* The only const/copy propagation opportunities left after
DOM should be due to degenerate PHI nodes. So rather than
More information about the Gcc-patches
mailing list