gcc/ChangeLog:
2018-06-07 Martin Liska <[email protected]>
* tree-switch-conversion.c (MAX_CASE_BIT_TESTS): Remove.
(hoist_edge_and_branch_if_true): Likewise.
(expand_switch_using_bit_tests_p): Likewise.
(struct case_bit_test): Likewise.
(case_bit_test_cmp): Likewise.
(emit_case_bit_tests): Likewise.
(switch_conversion::switch_conversion): New class.
(struct switch_conv_info): Remove old struct.
(collect_switch_conv_info): More to ...
(switch_conversion::collect): ... this.
(check_range): Likewise.
(switch_conversion::check_range): Likewise.
(check_all_empty_except_final): Likewise.
(switch_conversion::check_all_empty_except_final): Likewise.
(check_final_bb): Likewise.
(switch_conversion::check_final_bb): Likewise.
(create_temp_arrays): Likewise.
(switch_conversion::create_temp_arrays): Likewise.
(free_temp_arrays): Likewise.
(gather_default_values): Likewise.
(switch_conversion::gather_default_values): Likewise.
(build_constructors): Likewise.
(switch_conversion::build_constructors): Likewise.
(constructor_contains_same_values_p): Likewise.
(switch_conversion::contains_same_values_p): Likewise.
(array_value_type): Likewise.
(switch_conversion::array_value_type): Likewise.
(build_one_array): Likewise.
(switch_conversion::build_one_array): Likewise.
(build_arrays): Likewise.
(switch_conversion::build_arrays): Likewise.
(gen_def_assigns): Likewise.
(switch_conversion::gen_def_assigns): Likewise.
(prune_bbs): Likewise.
(switch_conversion::prune_bbs): Likewise.
(fix_phi_nodes): Likewise.
(switch_conversion::fix_phi_nodes): Likewise.
(gen_inbound_check): Likewise.
(switch_conversion::gen_inbound_check): Likewise.
(process_switch): Use the newly created class.
(switch_conversion::expand): New.
(switch_conversion::~switch_conversion): New.
* tree-switch-conversion.h: New file.
---
gcc/tree-switch-conversion.c | 1125 +++++++---------------------------
gcc/tree-switch-conversion.h | 283 +++++++++
2 files changed, 511 insertions(+), 897 deletions(-)
create mode 100644 gcc/tree-switch-conversion.h
diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
index dc60b34f506..2f848fcb6aa 100644
--- a/gcc/tree-switch-conversion.c
+++ b/gcc/tree-switch-conversion.c
@@ -55,626 +55,74 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
type in the GIMPLE type system that is language-independent? */
#include "langhooks.h"
+#include "tree-switch-conversion.h"
-/* Maximum number of case bit tests.
- FIXME: This should be derived from PARAM_CASE_VALUES_THRESHOLD and
- targetm.case_values_threshold(), or be its own param. */
-#define MAX_CASE_BIT_TESTS 3
-
-/* Track whether or not we have altered the CFG and thus may need to
- cleanup the CFG when complete. */
-bool cfg_altered;
-
-/* Split the basic block at the statement pointed to by GSIP, and insert
- a branch to the target basic block of E_TRUE conditional on tree
- expression COND.
-
- It is assumed that there is already an edge from the to-be-split
- basic block to E_TRUE->dest block. This edge is removed, and the
- profile information on the edge is re-used for the new conditional
- jump.
-
- The CFG is updated. The dominator tree will not be valid after
- this transformation, but the immediate dominators are updated if
- UPDATE_DOMINATORS is true.
-
- Returns the newly created basic block. */
+using namespace tree_switch_conversion;
-static basic_block
-hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
- tree cond, edge e_true,
- bool update_dominators)
-{
- tree tmp;
- gcond *cond_stmt;
- edge e_false;
- basic_block new_bb, split_bb = gsi_bb (*gsip);
- bool dominated_e_true = false;
-
- gcc_assert (e_true->src == split_bb);
-
- if (update_dominators
- && get_immediate_dominator (CDI_DOMINATORS, e_true->dest) == split_bb)
- dominated_e_true = true;
-
- tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL,
- /*before=*/true, GSI_SAME_STMT);
- cond_stmt = gimple_build_cond_from_tree (tmp, NULL_TREE, NULL_TREE);
- gsi_insert_before (gsip, cond_stmt, GSI_SAME_STMT);
-
- e_false = split_block (split_bb, cond_stmt);
- new_bb = e_false->dest;
- redirect_edge_pred (e_true, split_bb);
-
- e_true->flags &= ~EDGE_FALLTHRU;
- e_true->flags |= EDGE_TRUE_VALUE;
-
- e_false->flags &= ~EDGE_FALLTHRU;
- e_false->flags |= EDGE_FALSE_VALUE;
- e_false->probability = e_true->probability.invert ();
- new_bb->count = e_false->count ();
-
- if (update_dominators)
- {
- if (dominated_e_true)
- set_immediate_dominator (CDI_DOMINATORS, e_true->dest, split_bb);
- set_immediate_dominator (CDI_DOMINATORS, e_false->dest, split_bb);
- }
-
- return new_bb;
-}
-
-
-/* Return true if a switch should be expanded as a bit test.
- RANGE is the difference between highest and lowest case.
- UNIQ is number of unique case node targets, not counting the default case.
- COUNT is the number of comparisons needed, not counting the default case. */
-
-static bool
-expand_switch_using_bit_tests_p (tree range,
- unsigned int uniq,
- unsigned int count, bool speed_p)
-{
- return (((uniq == 1 && count >= 3)
- || (uniq == 2 && count >= 5)
- || (uniq == 3 && count >= 6))
- && lshift_cheap_p (speed_p)
- && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0
- && compare_tree_int (range, 0) > 0);
-}
-
-/* Implement switch statements with bit tests
-
-A GIMPLE switch statement can be expanded to a short sequence of bit-wise
-comparisons. "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)"
-where CST and MINVAL are integer constants. This is better than a series
-of compare-and-banch insns in some cases, e.g. we can implement:
-
- if ((x==4) || (x==6) || (x==9) || (x==11))
-
-as a single bit test:
-
- if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11)))
-
-This transformation is only applied if the number of case targets is small,
-if CST constains at least 3 bits, and "1 << x" is cheap. The bit tests are
-performed in "word_mode".
-
-The following example shows the code the transformation generates:
-
- int bar(int x)
- {
- switch (x)
- {
- case '0': case '1': case '2': case '3': case '4':
- case '5': case '6': case '7': case '8': case '9':
- case 'A': case 'B': case 'C': case 'D': case 'E':
- case 'F':
- return 1;
- }
- return 0;
- }
-
-==>
-
- bar (int x)
- {
- tmp1 = x - 48;
- if (tmp1 > (70 - 48)) goto L2;
- tmp2 = 1 << tmp1;
- tmp3 = 0b11111100000001111111111;
- if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2;
- L1:
- return 1;
- L2:
- return 0;
- }
-
-TODO: There are still some improvements to this transformation that could
-be implemented:
-
-* A narrower mode than word_mode could be used if that is cheaper, e.g.
- for x86_64 where a narrower-mode shift may result in smaller code.
-
-* The compounded constant could be shifted rather than the one. The
- test would be either on the sign bit or on the least significant bit,
- depending on the direction of the shift. On some machines, the test
- for the branch would be free if the bit to test is already set by the
- shift operation.
-
-This transformation was contributed by Roger Sayle, see this e-mail:
- http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html
-*/
-
-/* A case_bit_test represents a set of case nodes that may be
- selected from using a bit-wise comparison. HI and LO hold
- the integer to be tested against, TARGET_EDGE contains the
- edge to the basic block to jump to upon success and BITS
- counts the number of case nodes handled by this test,
- typically the number of bits set in HI:LO. The LABEL field
- is used to quickly identify all cases in this set without
- looking at label_to_block for every case label. */
-
-struct case_bit_test
-{
- wide_int mask;
- edge target_edge;
- tree label;
- int bits;
-};
-
-/* Comparison function for qsort to order bit tests by decreasing
- probability of execution. Our best guess comes from a measured
- profile. If the profile counts are equal, break even on the
- number of case nodes, i.e. the node with the most cases gets
- tested first.
-
- TODO: Actually this currently runs before a profile is available.
- Therefore the case-as-bit-tests transformation should be done
- later in the pass pipeline, or something along the lines of
- "Efficient and effective branch reordering using profile data"
- (Yang et. al., 2002) should be implemented (although, how good
- is a paper is called "Efficient and effective ..." when the
- latter is implied by the former, but oh well...). */
-
-static int
-case_bit_test_cmp (const void *p1, const void *p2)
-{
- const struct case_bit_test *const d1 = (const struct case_bit_test *) p1;
- const struct case_bit_test *const d2 = (const struct case_bit_test *) p2;
-
- if (d2->target_edge->count () < d1->target_edge->count ())
- return -1;
- if (d2->target_edge->count () > d1->target_edge->count ())
- return 1;
- if (d2->bits != d1->bits)
- return d2->bits - d1->bits;
-
- /* Stabilize the sort. */
- return LABEL_DECL_UID (d2->label) - LABEL_DECL_UID (d1->label);
-}
-
-/* Expand a switch statement by a short sequence of bit-wise
- comparisons. "switch(x)" is effectively converted into
- "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
- integer constants.
-
- INDEX_EXPR is the value being switched on.
-
- MINVAL is the lowest case value of in the case nodes,
- and RANGE is highest value minus MINVAL. MINVAL and RANGE
- are not guaranteed to be of the same type as INDEX_EXPR
- (the gimplifier doesn't change the type of case label values,
- and MINVAL and RANGE are derived from those values).
- MAXVAL is MINVAL + RANGE.
-
- There *MUST* be MAX_CASE_BIT_TESTS or less unique case
- node targets. */
-
-static void
-emit_case_bit_tests (gswitch *swtch, tree index_expr,
- tree minval, tree range, tree maxval)
+switch_conversion::switch_conversion (): m_final_bb (NULL), m_other_count (),
+ m_constructors (NULL), m_default_values (NULL),
+ m_arr_ref_first (NULL), m_arr_ref_last (NULL),
+ m_reason (NULL), m_default_case_nonstandard (false), m_cfg_altered (false)
{
- struct case_bit_test test[MAX_CASE_BIT_TESTS] = { {} };
- unsigned int i, j, k;
- unsigned int count;
-
- basic_block switch_bb = gimple_bb (swtch);
- basic_block default_bb, new_default_bb, new_bb;
- edge default_edge;
- bool update_dom = dom_info_available_p (CDI_DOMINATORS);
-
- vec<basic_block> bbs_to_fix_dom = vNULL;
-
- tree index_type = TREE_TYPE (index_expr);
- tree unsigned_index_type = unsigned_type_for (index_type);
- unsigned int branch_num = gimple_switch_num_labels (swtch);
-
- gimple_stmt_iterator gsi;
- gassign *shift_stmt;
-
- tree idx, tmp, csui;
- tree word_type_node = lang_hooks.types.type_for_mode (word_mode, 1);
- tree word_mode_zero = fold_convert (word_type_node, integer_zero_node);
- tree word_mode_one = fold_convert (word_type_node, integer_one_node);
- int prec = TYPE_PRECISION (word_type_node);
- wide_int wone = wi::one (prec);
-
- /* Get the edge for the default case. */
- tmp = gimple_switch_default_label (swtch);
- default_bb = label_to_block (CASE_LABEL (tmp));
- default_edge = find_edge (switch_bb, default_bb);
-
- /* Go through all case labels, and collect the case labels, profile
- counts, and other information we need to build the branch tests. */
- count = 0;
- for (i = 1; i < branch_num; i++)
- {
- unsigned int lo, hi;
- tree cs = gimple_switch_label (swtch, i);
- tree label = CASE_LABEL (cs);
- edge e = find_edge (switch_bb, label_to_block (label));
- for (k = 0; k < count; k++)
- if (e == test[k].target_edge)
- break;
-
- if (k == count)
- {
- gcc_checking_assert (count < MAX_CASE_BIT_TESTS);
- test[k].mask = wi::zero (prec);
- test[k].target_edge = e;
- test[k].label = label;
- test[k].bits = 1;
- count++;
- }
- else
- test[k].bits++;
-
- lo = tree_to_uhwi (int_const_binop (MINUS_EXPR,
- CASE_LOW (cs), minval));
- if (CASE_HIGH (cs) == NULL_TREE)
- hi = lo;
- else
- hi = tree_to_uhwi (int_const_binop (MINUS_EXPR,
- CASE_HIGH (cs), minval));
-
- for (j = lo; j <= hi; j++)
- test[k].mask |= wi::lshift (wone, j);
- }
-
- qsort (test, count, sizeof (*test), case_bit_test_cmp);
-
- /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of
- the minval subtractions, but it might make the mask constants more
- expensive. So, compare the costs. */
- if (compare_tree_int (minval, 0) > 0
- && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
- {
- int cost_diff;
- HOST_WIDE_INT m = tree_to_uhwi (minval);
- rtx reg = gen_raw_REG (word_mode, 10000);
- bool speed_p = optimize_bb_for_speed_p (gimple_bb (swtch));
- cost_diff = set_rtx_cost (gen_rtx_PLUS (word_mode, reg,
- GEN_INT (-m)), speed_p);
- for (i = 0; i < count; i++)
- {
- rtx r = immed_wide_int_const (test[i].mask, word_mode);
- cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r),
- word_mode, speed_p);
- r = immed_wide_int_const (wi::lshift (test[i].mask, m), word_mode);
- cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r),
- word_mode, speed_p);
- }
- if (cost_diff > 0)
- {
- for (i = 0; i < count; i++)
- test[i].mask = wi::lshift (test[i].mask, m);
- minval = build_zero_cst (TREE_TYPE (minval));
- range = maxval;
- }
- }
-
- /* We generate two jumps to the default case label.
- Split the default edge, so that we don't have to do any PHI node
- updating. */
- new_default_bb = split_edge (default_edge);
-
- if (update_dom)
- {
- bbs_to_fix_dom.create (10);
- bbs_to_fix_dom.quick_push (switch_bb);
- bbs_to_fix_dom.quick_push (default_bb);
- bbs_to_fix_dom.quick_push (new_default_bb);
- }
-
- /* Now build the test-and-branch code. */
-
- gsi = gsi_last_bb (switch_bb);
-
- /* idx = (unsigned)x - minval. */
- idx = fold_convert (unsigned_index_type, index_expr);
- idx = fold_build2 (MINUS_EXPR, unsigned_index_type, idx,
- fold_convert (unsigned_index_type, minval));
- idx = force_gimple_operand_gsi (&gsi, idx,
- /*simple=*/true, NULL_TREE,
- /*before=*/true, GSI_SAME_STMT);
-
- /* if (idx > range) goto default */
- range = force_gimple_operand_gsi (&gsi,
- fold_convert (unsigned_index_type, range),
- /*simple=*/true, NULL_TREE,
- /*before=*/true, GSI_SAME_STMT);
- tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range);
- new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, default_edge, update_dom);
- if (update_dom)
- bbs_to_fix_dom.quick_push (new_bb);
- gcc_assert (gimple_bb (swtch) == new_bb);
- gsi = gsi_last_bb (new_bb);
-
- /* Any blocks dominated by the GIMPLE_SWITCH, but that are not successors
- of NEW_BB, are still immediately dominated by SWITCH_BB. Make it so. */
- if (update_dom)
- {
- vec<basic_block> dom_bbs;
- basic_block dom_son;
-
- dom_bbs = get_dominated_by (CDI_DOMINATORS, new_bb);
- FOR_EACH_VEC_ELT (dom_bbs, i, dom_son)
- {
- edge e = find_edge (new_bb, dom_son);
- if (e && single_pred_p (e->dest))
- continue;
- set_immediate_dominator (CDI_DOMINATORS, dom_son, switch_bb);
- bbs_to_fix_dom.safe_push (dom_son);
- }
- dom_bbs.release ();
- }
-
- /* csui = (1 << (word_mode) idx) */
- csui = make_ssa_name (word_type_node);
- tmp = fold_build2 (LSHIFT_EXPR, word_type_node, word_mode_one,
- fold_convert (word_type_node, idx));
- tmp = force_gimple_operand_gsi (&gsi, tmp,
- /*simple=*/false, NULL_TREE,
- /*before=*/true, GSI_SAME_STMT);
- shift_stmt = gimple_build_assign (csui, tmp);
- gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT);
- update_stmt (shift_stmt);
-
- /* for each unique set of cases:
- if (const & csui) goto target */
- for (k = 0; k < count; k++)
- {
- tmp = wide_int_to_tree (word_type_node, test[k].mask);
- tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp);
- tmp = force_gimple_operand_gsi (&gsi, tmp,
- /*simple=*/true, NULL_TREE,
- /*before=*/true, GSI_SAME_STMT);
- tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero);
- new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_edge,
- update_dom);
- if (update_dom)
- bbs_to_fix_dom.safe_push (new_bb);
- gcc_assert (gimple_bb (swtch) == new_bb);
- gsi = gsi_last_bb (new_bb);
- }
-
- /* We should have removed all edges now. */
- gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0);
-
- /* If nothing matched, go to the default label. */
- make_edge (gsi_bb (gsi), new_default_bb, EDGE_FALLTHRU);
-
- /* The GIMPLE_SWITCH is now redundant. */
- gsi_remove (&gsi, true);
-
- if (update_dom)
- {
- /* Fix up the dominator tree. */
- iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
- bbs_to_fix_dom.release ();
- }
}
-
-/*
- 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;
- break;
- }
- a_5 = PHI <a_1, a_2, a_3, a_4>
- b_5 = PHI <b_1, b_2, b_3, b_4>
-
-
-is changed into:
-
- static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
- static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
- 16, 16, 10};
-
- if (((unsigned) argc) - 1 < 11)
- {
- a_6 = CSWTCH02[argc - 1];
- b_6 = CSWTCH01[argc - 1];
- }
- else
- {
- a_7 = 16;
- b_7 = 1;
- }
- a_5 = PHI <a_6, a_7>
- b_b = PHI <b_6, b_7>
-
-There are further constraints. Specifically, the range of values across all
-case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
-eight) times the number of the actual switch branches.
-
-This transformation was contributed by Martin Jambor, see this e-mail:
- http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */
-
-/* The main structure of the pass. */
-struct switch_conv_info
-{
- /* The expression used to decide the switch branch. */
- tree index_expr;
-
- /* The following integer constants store the minimum and maximum value
- covered by the case labels. */
- tree range_min;
- tree range_max;
-
- /* The difference between the above two numbers. Stored here because it
- is used in all the conversion heuristics, as well as for some of the
- transformation, and it is expensive to re-compute it all the time. */
- tree range_size;
- /* Basic block that contains the actual GIMPLE_SWITCH. */
- basic_block switch_bb;
-
- /* Basic block that is the target of the default case. */
- basic_block default_bb;
-
- /* The single successor block of all branches out of the GIMPLE_SWITCH,
- if such a block exists. Otherwise NULL. */
- basic_block final_bb;
-
- /* The probability of the default edge in the replaced switch. */
- profile_probability default_prob;
-
- /* The count of the default edge in the replaced switch. */
- profile_count default_count;
-
- /* Combined count of all other (non-default) edges in the replaced switch. */
- profile_count other_count;
-
- /* Number of phi nodes in the final bb (that we'll be replacing). */
- int phi_count;
-
- /* Array of default values, in the same order as phi nodes. */
- tree *default_values;
-
- /* Constructors of new static arrays. */
- vec<constructor_elt, va_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;
-
- /* VOP SSA_NAME. */
- tree target_vop;
-
- /* The first load statement that loads a temporary from a new static array.
- */
- gimple *arr_ref_first;
-
- /* The last load statement that loads a temporary from a new static array. */
- gimple *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;
-
- /* True if default case is not used for any value between range_min and
- range_max inclusive. */
- bool contiguous_range;
-
- /* True if default case does not have the required shape for other case
- labels. */
- bool default_case_nonstandard;
-
- /* Parameters for expand_switch_using_bit_tests. Should be computed
- the same way as in expand_case. */
- unsigned int uniq;
- unsigned int count;
-};
-
-/* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */
-
-static void
-collect_switch_conv_info (gswitch *swtch, struct switch_conv_info *info)
+void
+switch_conversion::collect (gswitch *swtch)
{
unsigned int branch_num = gimple_switch_num_labels (swtch);
tree min_case, max_case;
- unsigned int count, i;
+ unsigned int i;
edge e, e_default, e_first;
edge_iterator ei;
basic_block first;
- memset (info, 0, sizeof (*info));
+ m_switch = swtch;
/* The gimplifier has already sorted the cases by CASE_LOW and ensured there
is a default label which is the first in the vector.
Collect the bits we can deduce from the CFG. */
- info->index_expr = gimple_switch_index (swtch);
- info->switch_bb = gimple_bb (swtch);
- info->default_bb
+ m_index_expr = gimple_switch_index (swtch);
+ m_switch_bb = gimple_bb (swtch);
+ m_default_bb
= label_to_block (CASE_LABEL (gimple_switch_default_label (swtch)));
- e_default = find_edge (info->switch_bb, info->default_bb);
- info->default_prob = e_default->probability;
- info->default_count = e_default->count ();
- FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
+ e_default = find_edge (m_switch_bb, m_default_bb);
+ m_default_prob = e_default->probability;
+ m_default_count = e_default->count ();
+ FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
if (e != e_default)
- info->other_count += e->count ();
+ m_other_count += e->count ();
/* Get upper and lower bounds of case values, and the covered range. */
min_case = gimple_switch_label (swtch, 1);
max_case = gimple_switch_label (swtch, branch_num - 1);
- info->range_min = CASE_LOW (min_case);
+ m_range_min = CASE_LOW (min_case);
if (CASE_HIGH (max_case) != NULL_TREE)
- info->range_max = CASE_HIGH (max_case);
+ m_range_max = CASE_HIGH (max_case);
else
- info->range_max = CASE_LOW (max_case);
+ m_range_max = CASE_LOW (max_case);
- info->contiguous_range = true;
- tree last = CASE_HIGH (min_case) ? CASE_HIGH (min_case) : info->range_min;
+ m_contiguous_range = true;
+ tree last = CASE_HIGH (min_case) ? CASE_HIGH (min_case) : m_range_min;
for (i = 2; i < branch_num; i++)
{
tree elt = gimple_switch_label (swtch, i);
if (wi::to_wide (last) + 1 != wi::to_wide (CASE_LOW (elt)))
{
- info->contiguous_range = false;
+ m_contiguous_range = false;
break;
}
last = CASE_HIGH (elt) ? CASE_HIGH (elt) : CASE_LOW (elt);
}
- if (info->contiguous_range)
+ if (m_contiguous_range)
{
first = label_to_block (CASE_LABEL (gimple_switch_label (swtch, 1)));
- e_first = find_edge (info->switch_bb, first);
+ e_first = find_edge (m_switch_bb, first);
}
else
{
- first = info->default_bb;
+ first = m_default_bb;
e_first = e_default;
}
@@ -684,103 +132,91 @@ collect_switch_conv_info (gswitch *swtch, struct switch_conv_info *info)
if the range is contiguous and default case otherwise as
guess or its destination in case it is a forwarder block. */
if (! single_pred_p (e_first->dest))
- info->final_bb = e_first->dest;
+ m_final_bb = e_first->dest;
else if (single_succ_p (e_first->dest)
&& ! single_pred_p (single_succ (e_first->dest)))
- info->final_bb = single_succ (e_first->dest);
+ m_final_bb = single_succ (e_first->dest);
/* Require that all switch destinations are either that common
FINAL_BB or a forwarder to it, except for the default
case if contiguous range. */
- if (info->final_bb)
- FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
+ if (m_final_bb)
+ FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
{
- if (e->dest == info->final_bb)
+ if (e->dest == m_final_bb)
continue;
if (single_pred_p (e->dest)
&& single_succ_p (e->dest)
- && single_succ (e->dest) == info->final_bb)
+ && single_succ (e->dest) == m_final_bb)
continue;
- if (e == e_default && info->contiguous_range)
+ if (e == e_default && m_contiguous_range)
{
- info->default_case_nonstandard = true;
+ m_default_case_nonstandard = true;
continue;
}
- info->final_bb = NULL;
+ m_final_bb = NULL;
break;
}
- info->range_size
- = int_const_binop (MINUS_EXPR, info->range_max, info->range_min);
+ m_range_size
+ = int_const_binop (MINUS_EXPR, m_range_max, m_range_min);
/* Get a count of the number of case labels. Single-valued case labels
simply count as one, but a case range counts double, since it may
require two compares if it gets lowered as a branching tree. */
- count = 0;
+ m_count = 0;
for (i = 1; i < branch_num; i++)
{
tree elt = gimple_switch_label (swtch, i);
- count++;
+ m_count++;
if (CASE_HIGH (elt)
&& ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt)))
- count++;
+ m_count++;
}
- info->count = count;
-
- /* Get the number of unique non-default targets out of the GIMPLE_SWITCH
- block. Assume a CFG cleanup would have already removed degenerate
- switch statements, this allows us to just use EDGE_COUNT. */
- info->uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1;
}
-/* 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 (struct switch_conv_info *info)
+bool
+switch_conversion::check_range ()
{
- gcc_assert (info->range_size);
- if (!tree_fits_uhwi_p (info->range_size))
+ gcc_assert (m_range_size);
+ if (!tree_fits_uhwi_p (m_range_size))
{
- info->reason = "index range way too large or otherwise unusable";
+ m_reason = "index range way too large or otherwise unusable";
return false;
}
- if (tree_to_uhwi (info->range_size)
- > ((unsigned) info->count * SWITCH_CONVERSION_BRANCH_RATIO))
+ if (tree_to_uhwi (m_range_size)
+ > ((unsigned) m_count * SWITCH_CONVERSION_BRANCH_RATIO))
{
- info->reason = "the maximum range-branch ratio exceeded";
+ m_reason = "the maximum range-branch ratio exceeded";
return false;
}
return true;
}
-/* Checks whether all but the FINAL_BB basic blocks are empty. */
-
-static bool
-check_all_empty_except_final (struct switch_conv_info *info)
+bool
+switch_conversion::check_all_empty_except_final ()
{
- edge e, e_default = find_edge (info->switch_bb, info->default_bb);
+ edge e, e_default = find_edge (m_switch_bb, m_default_bb);
edge_iterator ei;
- FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
+ FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
{
- if (e->dest == info->final_bb)
+ if (e->dest == m_final_bb)
continue;
if (!empty_block_p (e->dest))
{
- if (info->contiguous_range && e == e_default)
+ if (m_contiguous_range && e == e_default)
{
- info->default_case_nonstandard = true;
+ m_default_case_nonstandard = true;
continue;
}
- info->reason = "bad case - a non-final BB not empty";
+ m_reason = "bad case - a non-final BB not empty";
return false;
}
}
@@ -788,18 +224,13 @@ check_all_empty_except_final (struct switch_conv_info *info)
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 (gswitch *swtch, struct switch_conv_info *info)
+bool
+switch_conversion::check_final_bb ()
{
gphi_iterator gsi;
- info->phi_count = 0;
- for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ m_phi_count = 0;
+ for (gsi = gsi_start_phis (m_final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
gphi *phi = gsi.phi ();
unsigned int i;
@@ -807,16 +238,16 @@ check_final_bb (gswitch *swtch, struct switch_conv_info *info)
if (virtual_operand_p (gimple_phi_result (phi)))
continue;
- info->phi_count++;
+ m_phi_count++;
for (i = 0; i < gimple_phi_num_args (phi); i++)
{
basic_block bb = gimple_phi_arg_edge (phi, i)->src;
- if (bb == info->switch_bb
+ if (bb == m_switch_bb
|| (single_pred_p (bb)
- && single_pred (bb) == info->switch_bb
- && (!info->default_case_nonstandard
+ && single_pred (bb) == m_switch_bb
+ && (!m_default_case_nonstandard
|| empty_block_p (bb))))
{
tree reloc, val;
@@ -844,25 +275,25 @@ check_final_bb (gswitch *swtch, struct switch_conv_info *info)
/* For contiguous range, we can allow non-constant
or one that needs relocation, as long as it is
only reachable from the default case. */
- if (bb == info->switch_bb)
- bb = info->final_bb;
- if (!info->contiguous_range || bb != info->default_bb)
+ if (bb == m_switch_bb)
+ bb = m_final_bb;
+ if (!m_contiguous_range || bb != m_default_bb)
{
- info->reason = reason;
+ m_reason = reason;
return false;
}
- unsigned int branch_num = gimple_switch_num_labels (swtch);
+ unsigned int branch_num = gimple_switch_num_labels (m_switch);
for (unsigned int i = 1; i < branch_num; i++)
{
- tree lab = CASE_LABEL (gimple_switch_label (swtch, i));
+ tree lab = CASE_LABEL (gimple_switch_label (m_switch, i));
if (label_to_block (lab) == bb)
{
- info->reason = reason;
+ m_reason = reason;
return false;
}
}
- info->default_case_nonstandard = true;
+ m_default_case_nonstandard = true;
}
}
}
@@ -871,44 +302,24 @@ check_final_bb (gswitch *swtch, struct switch_conv_info *info)
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 (struct switch_conv_info *info)
+void
+switch_conversion::create_temp_arrays ()
{
int i;
- info->default_values = XCNEWVEC (tree, info->phi_count * 3);
+ m_default_values = XCNEWVEC (tree, m_phi_count * 3);
/* ??? Macros do not support multi argument templates in their
argument list. We create a typedef to work around that problem. */
typedef vec<constructor_elt, va_gc> *vec_constructor_elt_gc;
- info->constructors = XCNEWVEC (vec_constructor_elt_gc, info->phi_count);
- info->target_inbound_names = info->default_values + info->phi_count;
- info->target_outbound_names = info->target_inbound_names + info->phi_count;
- for (i = 0; i < info->phi_count; i++)
- vec_alloc (info->constructors[i], tree_to_uhwi (info->range_size) + 1);
+ m_constructors = XCNEWVEC (vec_constructor_elt_gc, m_phi_count);
+ m_target_inbound_names = m_default_values + m_phi_count;
+ m_target_outbound_names = m_target_inbound_names + m_phi_count;
+ for (i = 0; i < m_phi_count; i++)
+ vec_alloc (m_constructors[i], tree_to_uhwi (m_range_size) + 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 (struct switch_conv_info *info)
-{
- XDELETEVEC (info->constructors);
- XDELETEVEC (info->default_values);
-}
-
-/* Populate the array of default values in the order of phi nodes.
- DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch
- if the range is non-contiguous or the default case has standard
- structure, otherwise it is the first non-default case instead. */
-
-static void
-gather_default_values (tree default_case, struct switch_conv_info *info)
+void
+switch_conversion::gather_default_values (tree default_case)
{
gphi_iterator gsi;
basic_block bb = label_to_block (CASE_LABEL (default_case));
@@ -916,46 +327,42 @@ gather_default_values (tree default_case, struct switch_conv_info *info)
int i = 0;
gcc_assert (CASE_LOW (default_case) == NULL_TREE
- || info->default_case_nonstandard);
+ || m_default_case_nonstandard);
- if (bb == info->final_bb)
- e = find_edge (info->switch_bb, bb);
+ if (bb == m_final_bb)
+ e = find_edge (m_switch_bb, bb);
else
e = single_succ_edge (bb);
- for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ for (gsi = gsi_start_phis (m_final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
gphi *phi = gsi.phi ();
if (virtual_operand_p (gimple_phi_result (phi)))
continue;
tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
gcc_assert (val);
- info->default_values[i++] = val;
+ m_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 (gswitch *swtch, struct switch_conv_info *info)
+void
+switch_conversion::build_constructors ()
{
- unsigned i, branch_num = gimple_switch_num_labels (swtch);
- tree pos = info->range_min;
+ unsigned i, branch_num = gimple_switch_num_labels (m_switch);
+ tree pos = m_range_min;
tree pos_one = build_int_cst (TREE_TYPE (pos), 1);
for (i = 1; i < branch_num; i++)
{
- tree cs = gimple_switch_label (swtch, i);
+ tree cs = gimple_switch_label (m_switch, i);
basic_block bb = label_to_block (CASE_LABEL (cs));
edge e;
tree high;
gphi_iterator gsi;
int j;
- if (bb == info->final_bb)
- e = find_edge (info->switch_bb, bb);
+ if (bb == m_final_bb)
+ e = find_edge (m_switch_bb, bb);
else
e = single_succ_edge (bb);
gcc_assert (e);
@@ -963,15 +370,14 @@ build_constructors (gswitch *swtch, struct switch_conv_info *info)
while (tree_int_cst_lt (pos, CASE_LOW (cs)))
{
int k;
- gcc_assert (!info->contiguous_range);
- for (k = 0; k < info->phi_count; k++)
+ for (k = 0; k < m_phi_count; k++)
{
constructor_elt elt;
- elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
+ elt.index = int_const_binop (MINUS_EXPR, pos, m_range_min);
elt.value
- = unshare_expr_without_location (info->default_values[k]);
- info->constructors[k]->quick_push (elt);
+ = unshare_expr_without_location (m_default_values[k]);
+ m_constructors[k]->quick_push (elt);
}
pos = int_const_binop (PLUS_EXPR, pos, pos_one);
@@ -983,7 +389,7 @@ build_constructors (gswitch *swtch, struct switch_conv_info *info)
high = CASE_HIGH (cs);
else
high = CASE_LOW (cs);
- for (gsi = gsi_start_phis (info->final_bb);
+ for (gsi = gsi_start_phis (m_final_bb);
!gsi_end_p (gsi); gsi_next (&gsi))
{
gphi *phi = gsi.phi ();
@@ -997,9 +403,9 @@ build_constructors (gswitch *swtch, struct switch_conv_info *info)
{
constructor_elt elt;
- elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
+ elt.index = int_const_binop (MINUS_EXPR, pos, m_range_min);
elt.value = unshare_expr_without_location (val);
- info->constructors[j]->quick_push (elt);
+ m_constructors[j]->quick_push (elt);
pos = int_const_binop (PLUS_EXPR, pos, pos_one);
} while (!tree_int_cst_lt (high, pos)
@@ -1009,12 +415,8 @@ build_constructors (gswitch *swtch, struct switch_conv_info *info)
}
}
-/* If all values in the constructor vector are the same, return the value.
- Otherwise return NULL_TREE. Not supposed to be called for empty
- vectors. */
-
-static tree
-constructor_contains_same_values_p (vec<constructor_elt, va_gc> *vec)
+tree
+switch_conversion::contains_same_values_p (vec<constructor_elt, va_gc> *vec)
{
unsigned int i;
tree prev = NULL_TREE;
@@ -1030,15 +432,10 @@ constructor_contains_same_values_p (vec<constructor_elt, va_gc> *vec)
return prev;
}
-/* Return type which should be used for array elements, either TYPE's
- main variant or, for integral types, some smaller integral type
- that can still hold all the constants. */
-
-static tree
-array_value_type (gswitch *swtch, tree type, int num,
- struct switch_conv_info *info)
+tree
+switch_conversion::array_value_type (tree type, int num)
{
- unsigned int i, len = vec_safe_length (info->constructors[num]);
+ unsigned int i, len = vec_safe_length (m_constructors[num]);
constructor_elt *elt;
int sign = 0;
tree smaller_type;
@@ -1058,10 +455,10 @@ array_value_type (gswitch *swtch, tree type, int num,
if (GET_MODE_SIZE (type_mode) <= GET_MODE_SIZE (mode))
return type;
- if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32))
+ if (len < (optimize_bb_for_size_p (gimple_bb (m_switch)) ? 2 : 32))
return type;
- FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
+ FOR_EACH_VEC_SAFE_ELT (m_constructors[num], i, elt)
{
wide_int cst;
@@ -1107,49 +504,39 @@ array_value_type (gswitch *swtch, tree type, int num,
return smaller_type;
}
-/* 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 an ssa name of a temporary variable holding the index for loads from the
- new array. */
-
-static void
-build_one_array (gswitch *swtch, int num, tree arr_index_type,
- gphi *phi, tree tidx, struct switch_conv_info *info)
+void
+switch_conversion::build_one_array (int num, tree arr_index_type,
+ gphi *phi, tree tidx)
{
tree name, cst;
gimple *load;
- gimple_stmt_iterator gsi = gsi_for_stmt (swtch);
- location_t loc = gimple_location (swtch);
+ gimple_stmt_iterator gsi = gsi_for_stmt (m_switch);
+ location_t loc = gimple_location (m_switch);
- gcc_assert (info->default_values[num]);
+ gcc_assert (m_default_values[num]);
name = copy_ssa_name (PHI_RESULT (phi));
- info->target_inbound_names[num] = name;
+ m_target_inbound_names[num] = name;
- cst = constructor_contains_same_values_p (info->constructors[num]);
+ cst = contains_same_values_p (m_constructors[num]);
if (cst)
load = gimple_build_assign (name, cst);
else
{
tree array_type, ctor, decl, value_type, fetch, default_type;
- default_type = TREE_TYPE (info->default_values[num]);
- value_type = array_value_type (swtch, default_type, num, info);
+ default_type = TREE_TYPE (m_default_values[num]);
+ value_type = array_value_type (default_type, num);
array_type = build_array_type (value_type, arr_index_type);
if (default_type != value_type)
{
unsigned int i;
constructor_elt *elt;
- FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
+ FOR_EACH_VEC_SAFE_ELT (m_constructors[num], i, elt)
elt->value = fold_convert (value_type, elt->value);
}
- ctor = build_constructor (array_type, info->constructors[num]);
+ ctor = build_constructor (array_type, m_constructors[num]);
TREE_CONSTANT (ctor) = true;
TREE_STATIC (ctor) = true;
@@ -1182,15 +569,11 @@ build_one_array (gswitch *swtch, int num, tree arr_index_type,
gsi_insert_before (&gsi, load, GSI_SAME_STMT);
update_stmt (load);
- info->arr_ref_last = load;
+ m_arr_ref_last = load;
}
-/* 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 (gswitch *swtch, struct switch_conv_info *info)
+void
+switch_conversion::build_arrays ()
{
tree arr_index_type;
tree tidx, sub, utype;
@@ -1198,84 +581,77 @@ build_arrays (gswitch *swtch, struct switch_conv_info *info)
gimple_stmt_iterator gsi;
gphi_iterator gpi;
int i;
- location_t loc = gimple_location (swtch);
+ location_t loc = gimple_location (m_switch);
- gsi = gsi_for_stmt (swtch);
+ gsi = gsi_for_stmt (m_switch);
/* Make sure we do not generate arithmetics in a subrange. */
- utype = TREE_TYPE (info->index_expr);
+ utype = TREE_TYPE (m_index_expr);
if (TREE_TYPE (utype))
utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1);
else
utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
- arr_index_type = build_index_type (info->range_size);
+ arr_index_type = build_index_type (m_range_size);
tidx = make_ssa_name (utype);
sub = fold_build2_loc (loc, MINUS_EXPR, utype,
- fold_convert_loc (loc, utype, info->index_expr),
- fold_convert_loc (loc, utype, info->range_min));
+ fold_convert_loc (loc, utype, m_index_expr),
+ fold_convert_loc (loc, utype, m_range_min));
sub = force_gimple_operand_gsi (&gsi, sub,
false, NULL, true, GSI_SAME_STMT);
stmt = gimple_build_assign (tidx, sub);
gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
update_stmt (stmt);
- info->arr_ref_first = stmt;
+ m_arr_ref_first = stmt;
- for (gpi = gsi_start_phis (info->final_bb), i = 0;
+ for (gpi = gsi_start_phis (m_final_bb), i = 0;
!gsi_end_p (gpi); gsi_next (&gpi))
{
gphi *phi = gpi.phi ();
if (!virtual_operand_p (gimple_phi_result (phi)))
- build_one_array (swtch, i++, arr_index_type, phi, tidx, info);
+ build_one_array (i++, arr_index_type, phi, tidx);
else
{
edge e;
edge_iterator ei;
- FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
+ FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
{
- if (e->dest == info->final_bb)
+ if (e->dest == m_final_bb)
break;
- if (!info->default_case_nonstandard
- || e->dest != info->default_bb)
+ if (!m_default_case_nonstandard
+ || e->dest != m_default_bb)
{
e = single_succ_edge (e->dest);
break;
}
}
- gcc_assert (e && e->dest == info->final_bb);
- info->target_vop = PHI_ARG_DEF_FROM_EDGE (phi, e);
+ gcc_assert (e && e->dest == m_final_bb);
+ m_target_vop = PHI_ARG_DEF_FROM_EDGE (phi, e);
}
}
}
-/* Generates and appropriately inserts loads of default values at the position
- given by BSI. Returns the last inserted statement. */
-
-static gassign *
-gen_def_assigns (gimple_stmt_iterator *gsi, struct switch_conv_info *info)
+gassign *
+switch_conversion::gen_def_assigns (gimple_stmt_iterator *gsi)
{
int i;
gassign *assign = NULL;
- for (i = 0; i < info->phi_count; i++)
+ for (i = 0; i < m_phi_count; i++)
{
- tree name = copy_ssa_name (info->target_inbound_names[i]);
- info->target_outbound_names[i] = name;
- assign = gimple_build_assign (name, info->default_values[i]);
+ tree name = copy_ssa_name (m_target_inbound_names[i]);
+ m_target_outbound_names[i] = name;
+ assign = gimple_build_assign (name, m_default_values[i]);
gsi_insert_before (gsi, assign, GSI_SAME_STMT);
update_stmt (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, basic_block default_bb)
+void
+switch_conversion::prune_bbs (basic_block bbd, basic_block final,
+ basic_block default_bb)
{
edge_iterator ei;
edge e;
@@ -1291,14 +667,8 @@ prune_bbs (basic_block bbd, basic_block final, basic_block default_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,
- struct switch_conv_info *info)
+void
+switch_conversion::fix_phi_nodes (edge e1f, edge e2f, basic_block bbf)
{
gphi_iterator gsi;
int i;
@@ -1309,41 +679,20 @@ fix_phi_nodes (edge e1f, edge e2f, basic_block bbf,
gphi *phi = gsi.phi ();
tree inbound, outbound;
if (virtual_operand_p (gimple_phi_result (phi)))
- inbound = outbound = info->target_vop;
+ inbound = outbound = m_target_vop;
else
{
- inbound = info->target_inbound_names[i];
- outbound = info->target_outbound_names[i++];
+ inbound = m_target_inbound_names[i];
+ outbound = m_target_outbound_names[i++];
}
add_phi_arg (phi, inbound, e1f, UNKNOWN_LOCATION);
- if (!info->default_case_nonstandard)
+ if (!m_default_case_nonstandard)
add_phi_arg (phi, outbound, e2f, UNKNOWN_LOCATION);
}
}
-/* 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 (gswitch *swtch, struct switch_conv_info *info)
+void
+switch_conversion::gen_inbound_check ()
{
tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION);
tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
@@ -1358,30 +707,30 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info)
gimple_stmt_iterator gsi;
basic_block bb0, bb1, bb2, bbf, bbd;
edge e01 = NULL, e02, e21, e1d, e1f, e2f;
- location_t loc = gimple_location (swtch);
+ location_t loc = gimple_location (m_switch);
- gcc_assert (info->default_values);
+ gcc_assert (m_default_values);
- bb0 = gimple_bb (swtch);
+ bb0 = gimple_bb (m_switch);
- tidx = gimple_assign_lhs (info->arr_ref_first);
+ tidx = gimple_assign_lhs (m_arr_ref_first);
utype = TREE_TYPE (tidx);
/* (end of) block 0 */
- gsi = gsi_for_stmt (info->arr_ref_first);
+ gsi = gsi_for_stmt (m_arr_ref_first);
gsi_next (&gsi);
- bound = fold_convert_loc (loc, utype, info->range_size);
+ bound = fold_convert_loc (loc, utype, m_range_size);
cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
update_stmt (cond_stmt);
/* block 2 */
- if (!info->default_case_nonstandard)
+ if (!m_default_case_nonstandard)
{
label2 = gimple_build_label (label_decl2);
gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
- last_assign = gen_def_assigns (&gsi, info);
+ last_assign = gen_def_assigns (&gsi);
}
/* block 1 */
@@ -1389,7 +738,7 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info)
gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
/* block F */
- gsi = gsi_start_bb (info->final_bb);
+ gsi = gsi_start_bb (m_final_bb);
label3 = gimple_build_label (label_decl3);
gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
@@ -1397,10 +746,10 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info)
e02 = split_block (bb0, cond_stmt);
bb2 = e02->dest;
- if (info->default_case_nonstandard)
+ if (m_default_case_nonstandard)
{
bb1 = bb2;
- bb2 = info->default_bb;
+ bb2 = m_default_bb;
e01 = e02;
e01->flags = EDGE_TRUE_VALUE;
e02 = make_edge (bb0, bb2, EDGE_FALSE_VALUE);
@@ -1424,26 +773,26 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info)
remove_edge (e21);
}
- e1d = split_block (bb1, info->arr_ref_last);
+ e1d = split_block (bb1, m_arr_ref_last);
bbd = e1d->dest;
remove_edge (e1d);
- /* flags and profiles of the edge for in-range values */
- if (!info->default_case_nonstandard)
+ /* Flags and profiles of the edge for in-range values. */
+ if (!m_default_case_nonstandard)
e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
- e01->probability = info->default_prob.invert ();
+ e01->probability = m_default_prob.invert ();
- /* flags and profiles of the edge taking care of out-of-range values */
+ /* 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->probability = m_default_prob;
- bbf = info->final_bb;
+ bbf = m_final_bb;
e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
e1f->probability = profile_probability::always ();
- if (info->default_case_nonstandard)
+ if (m_default_case_nonstandard)
e2f = NULL;
else
{
@@ -1454,15 +803,15 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info)
/* frequencies of the new BBs */
bb1->count = e01->count ();
bb2->count = e02->count ();
- if (!info->default_case_nonstandard)
+ if (!m_default_case_nonstandard)
bbf->count = e1f->count () + e2f->count ();
/* Tidy blocks that have become unreachable. */
- prune_bbs (bbd, info->final_bb,
- info->default_case_nonstandard ? info->default_bb : NULL);
+ prune_bbs (bbd, m_final_bb,
+ m_default_case_nonstandard ? m_default_bb : NULL);
/* Fixup the PHI nodes in bbF. */
- fix_phi_nodes (e1f, e2f, bbf, info);
+ fix_phi_nodes (e1f, e2f, bbf);
/* Fix the dominator tree, if it is available. */
if (dom_info_available_p (CDI_DOMINATORS))
@@ -1470,7 +819,7 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info)
vec<basic_block> bbs_to_fix_dom;
set_immediate_dominator (CDI_DOMINATORS, bb1, bb0);
- if (!info->default_case_nonstandard)
+ if (!m_default_case_nonstandard)
set_immediate_dominator (CDI_DOMINATORS, bb2, bb0);
if (! get_immediate_dominator (CDI_DOMINATORS, bbf))
/* If bbD was the immediate dominator ... */
@@ -1488,95 +837,76 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info)
}
}
-/* 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.
- Returns NULL on success, or a pointer to a string with the reason why the
- conversion failed. */
-
-static const char *
-process_switch (gswitch *swtch)
+void
+switch_conversion::expand (gswitch *swtch)
{
- struct switch_conv_info info;
-
/* Group case labels so that we get the right results from the heuristics
that decide on the code generation approach for this switch. */
- cfg_altered |= group_case_labels_stmt (swtch);
+ m_cfg_altered |= group_case_labels_stmt (swtch);
/* If this switch is now a degenerate case with only a default label,
- there is nothing left for us to do. */
+ there is nothing left for us to do. */
if (gimple_switch_num_labels (swtch) < 2)
- return "switch is a degenerate case";
+ {
+ m_reason = "switch is a degenerate case";
+ return;
+ }
- collect_switch_conv_info (swtch, &info);
+ collect (swtch);
/* No error markers should reach here (they should be filtered out
during gimplification). */
- gcc_checking_assert (TREE_TYPE (info.index_expr) != error_mark_node);
+ gcc_checking_assert (TREE_TYPE (m_index_expr) != error_mark_node);
/* A switch on a constant should have been optimized in tree-cfg-cleanup. */
- gcc_checking_assert (! TREE_CONSTANT (info.index_expr));
+ gcc_checking_assert (!TREE_CONSTANT (m_index_expr));
- if (info.uniq <= MAX_CASE_BIT_TESTS)
+ /* If there is no common successor, we cannot do the transformation. */
+ if (!m_final_bb)
{
- if (expand_switch_using_bit_tests_p (info.range_size,
- info.uniq, info.count,
- optimize_bb_for_speed_p
- (gimple_bb (swtch))))
- {
- if (dump_file)
- fputs (" expanding as bit test is preferable\n", dump_file);
- emit_case_bit_tests (swtch, info.index_expr, info.range_min,
- info.range_size, info.range_max);
- loops_state_set (LOOPS_NEED_FIXUP);
- return NULL;
- }
-
- if (info.uniq <= 2)
- /* This will be expanded as a decision tree in stmt.c:expand_case. */
- return " expanding as jumps is preferable";
+ m_reason = "no common successor to all case label target blocks found";
+ return;
}
- /* If there is no common successor, we cannot do the transformation. */
- if (! info.final_bb)
- return "no common successor to all case label target blocks found";
-
/* Check the case label values are within reasonable range: */
- if (!check_range (&info))
+ if (!check_range ())
{
- gcc_assert (info.reason);
- return info.reason;
+ gcc_assert (m_reason);
+ return;
}
/* For all the cases, see whether they are empty, the assignments they
represent constant and so on... */
- if (! check_all_empty_except_final (&info))
+ if (!check_all_empty_except_final ())
{
- gcc_assert (info.reason);
- return info.reason;
+ gcc_assert (m_reason);
+ return;
}
- if (!check_final_bb (swtch, &info))
+ if (!check_final_bb ())
{
- gcc_assert (info.reason);
- return info.reason;
+ gcc_assert (m_reason);
+ return;
}
/* At this point all checks have passed and we can proceed with the
transformation. */
- create_temp_arrays (&info);
- gather_default_values (info.default_case_nonstandard
+ create_temp_arrays ();
+ gather_default_values (m_default_case_nonstandard
? gimple_switch_label (swtch, 1)
- : gimple_switch_default_label (swtch), &info);
- if (info.phi_count)
- build_constructors (swtch, &info);
+ : gimple_switch_default_label (swtch));
+ build_constructors ();
- build_arrays (swtch, &info); /* Build the static arrays and assignments. */
- gen_inbound_check (swtch, &info); /* Build the bounds check. */
+ build_arrays (); /* Build the static arrays and assignments. */
+ gen_inbound_check (); /* Build the bounds check. */
- /* Cleanup: */
- free_temp_arrays (&info);
- return NULL;
+ m_cfg_altered = true;
+}
+
+switch_conversion::~switch_conversion ()
+{
+ XDELETEVEC (m_constructors);
+ XDELETEVEC (m_default_values);
}
/* The main function of the pass scans statements for switches and invokes
@@ -1614,11 +944,10 @@ unsigned int
pass_convert_switch::execute (function *fun)
{
basic_block bb;
+ bool cfg_altered = false;
- cfg_altered = false;
FOR_EACH_BB_FN (bb, fun)
{
- const char *failure_reason;
gimple *stmt = last_stmt (bb);
if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
{
@@ -1633,19 +962,21 @@ pass_convert_switch::execute (function *fun)
putc ('\n', dump_file);
}
- failure_reason = process_switch (as_a <gswitch *> (stmt));
- if (! failure_reason)
+ switch_conversion sconv;
+ sconv.expand (as_a <gswitch *> (stmt));
+ cfg_altered |= sconv.m_cfg_altered;
+ if (!sconv.m_reason)
{
- cfg_altered = true;
if (dump_file)
{
fputs ("Switch converted\n", dump_file);
fputs ("--------------------------------\n", dump_file);
}
- /* Make no effort to update the post-dominator tree. It is actually not
- that hard for the transformations we have performed, but it is not
- supported by iterate_fix_dominators. */
+ /* Make no effort to update the post-dominator tree.
+ It is actually not that hard for the transformations
+ we have performed, but it is not supported
+ by iterate_fix_dominators. */
free_dominance_info (CDI_POST_DOMINATORS);
}
else
@@ -1653,14 +984,14 @@ pass_convert_switch::execute (function *fun)
if (dump_file)
{
fputs ("Bailing out - ", dump_file);
- fputs (failure_reason, dump_file);
+ fputs (sconv.m_reason, dump_file);
fputs ("\n--------------------------------\n", dump_file);
}
}
}
}
- return cfg_altered ? TODO_cleanup_cfg : 0;
+ return cfg_altered ? TODO_cleanup_cfg : 0;;
}
} // anon namespace
diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h
new file mode 100644
index 00000000000..297faec119f
--- /dev/null
+++ b/gcc/tree-switch-conversion.h
@@ -0,0 +1,283 @@
+/* Tree switch conversion for GNU compiler.
+ Copyright (C) 2017 Free Software Foundation, Inc.
+
+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 see
+<http://www.gnu.org/licenses/>. */
+
+#ifndef TREE_SWITCH_CONVERSION_H
+#define TREE_SWITCH_CONVERSION_H
+
+namespace tree_switch_conversion {
+
+/*
+ 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;
+ break;
+ }
+ a_5 = PHI <a_1, a_2, a_3, a_4>
+ b_5 = PHI <b_1, b_2, b_3, b_4>
+
+
+is changed into:
+
+ static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
+ static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
+ 16, 16, 10};
+
+ if (((unsigned) argc) - 1 < 11)
+ {
+ a_6 = CSWTCH02[argc - 1];
+ b_6 = CSWTCH01[argc - 1];
+ }
+ else
+ {
+ a_7 = 16;
+ b_7 = 1;
+ }
+ a_5 = PHI <a_6, a_7>
+ b_b = PHI <b_6, b_7>
+
+There are further constraints. Specifically, the range of values across all
+case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
+eight) times the number of the actual switch branches.
+
+This transformation was contributed by Martin Jambor, see this e-mail:
+ http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */
+
+/* The main structure of the pass. */
+struct switch_conversion
+{
+ /* Constructor. */
+ switch_conversion ();
+
+ /* Destructor. */
+ ~switch_conversion ();
+
+ /* 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. On success, NULL is in m_reason, otherwise points
+ to a string with the reason why the conversion failed. */
+ void expand (gswitch *swtch);
+
+ /* Collection information about SWTCH statement. */
+ void collect (gswitch *swtch);
+
+ /* Checks whether the range given by individual case statements of the switch
+ switch statement isn't too big and whether the number of branches actually
+ satisfies the size of the new array. */
+ bool check_range ();
+
+ /* Checks whether all but the final BB basic blocks are empty. */
+ bool check_all_empty_except_final ();
+
+ /* 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. */
+ bool check_final_bb ();
+
+ /* 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. */
+ void create_temp_arrays ();
+
+ /* Populate the array of default values in the order of phi nodes.
+ DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch
+ if the range is non-contiguous or the default case has standard
+ structure, otherwise it is the first non-default case instead. */
+ void gather_default_values (tree default_case);
+
+ /* 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. */
+ void build_constructors ();
+
+ /* If all values in the constructor vector are the same, return the value.
+ Otherwise return NULL_TREE. Not supposed to be called for empty
+ vectors. */
+ tree contains_same_values_p (vec<constructor_elt, va_gc> *vec);
+
+ /* Return type which should be used for array elements, either TYPE's
+ main variant or, for integral types, some smaller integral type
+ that can still hold all the constants. */
+ tree array_value_type (tree type, int num);
+
+ /* 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 an ssa name of a temporary variable holding the index for loads from the
+ new array. */
+ void build_one_array (int num, tree arr_index_type,
+ gphi *phi, tree tidx);
+
+ /* Builds and initializes static arrays initialized with values gathered from
+ the switch statement. Also creates statements that load values from
+ them. */
+ void build_arrays ();
+
+ /* Generates and appropriately inserts loads of default values at the position
+ given by GSI. Returns the last inserted statement. */
+ gassign *gen_def_assigns (gimple_stmt_iterator *gsi);
+
+ /* 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). */
+ void prune_bbs (basic_block bbd, basic_block final, basic_block default_bb);
+
+ /* 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). */
+ void fix_phi_nodes (edge e1f, edge e2f, basic_block bbf);
+
+ /* 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. */
+ void gen_inbound_check ();
+
+ /* Switch statement for which switch conversion takes place. */
+ gswitch *m_switch;
+
+ /* The expression used to decide the switch branch. */
+ tree m_index_expr;
+
+ /* The following integer constants store the minimum and maximum value
+ covered by the case labels. */
+ tree m_range_min;
+ tree m_range_max;
+
+ /* The difference between the above two numbers. Stored here because it
+ is used in all the conversion heuristics, as well as for some of the
+ transformation, and it is expensive to re-compute it all the time. */
+ tree m_range_size;
+
+ /* Basic block that contains the actual GIMPLE_SWITCH. */
+ basic_block m_switch_bb;
+
+ /* Basic block that is the target of the default case. */
+ basic_block m_default_bb;
+
+ /* The single successor block of all branches out of the GIMPLE_SWITCH,
+ if such a block exists. Otherwise NULL. */
+ basic_block m_final_bb;
+
+ /* The probability of the default edge in the replaced switch. */
+ profile_probability m_default_prob;
+
+ /* The count of the default edge in the replaced switch. */
+ profile_count m_default_count;
+
+ /* Combined count of all other (non-default) edges in the replaced switch. */
+ profile_count m_other_count;
+
+ /* Number of phi nodes in the final bb (that we'll be replacing). */
+ int m_phi_count;
+
+ /* Constructors of new static arrays. */
+ vec<constructor_elt, va_gc> **m_constructors;
+
+ /* Array of default values, in the same order as phi nodes. */
+ tree *m_default_values;
+
+ /* Array of ssa names that are initialized with a value from a new static
+ array. */
+ tree *m_target_inbound_names;
+
+ /* Array of ssa names that are initialized with the default value if the
+ switch expression is out of range. */
+ tree *m_target_outbound_names;
+
+ /* VOP SSA_NAME. */
+ tree m_target_vop;
+
+ /* The first load statement that loads a temporary from a new static array.
+ */
+ gimple *m_arr_ref_first;
+
+ /* The last load statement that loads a temporary from a new static array. */
+ gimple *m_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 *m_reason;
+
+ /* True if default case is not used for any value between range_min and
+ range_max inclusive. */
+ bool m_contiguous_range;
+
+ /* True if default case does not have the required shape for other case
+ labels. */
+ bool m_default_case_nonstandard;
+
+ /* Count is number of non-default edges. */
+ unsigned int m_count;
+
+ /* True if CFG has been changed. */
+ bool m_cfg_altered;
+};
+
+} // tree_switch_conversion namespace
+
+#endif // TREE_SWITCH_CONVERSION_H
