/* Lower GIMPLE_SWITCH expressions to something more efficient than
a jump table.
- Copyright (C) 2006-2017 Free Software Foundation, Inc.
+ Copyright (C) 2006-2020 Free Software Foundation, Inc.
This file is part of GCC.
#include "optabs-tree.h"
#include "cgraph.h"
#include "gimple-pretty-print.h"
-#include "params.h"
#include "fold-const.h"
#include "varasm.h"
#include "stor-layout.h"
#include "gimplify.h"
#include "gimple-iterator.h"
#include "gimplify-me.h"
+#include "gimple-fold.h"
#include "tree-cfg.h"
#include "cfgloop.h"
#include "alloc-pool.h"
#include "target.h"
#include "tree-into-ssa.h"
+#include "omp-general.h"
/* ??? For lang_hooks.types.type_for_mode, but is there a word_mode
type in the GIMPLE type system that is language-independent? */
#include "langhooks.h"
+#include "tree-switch-conversion.h"
\f
-/* 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
+using namespace tree_switch_conversion;
-/* 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. */
+/* Constructor. */
-static basic_block
-hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
- tree cond, edge e_true,
- bool update_dominators)
+switch_conversion::switch_conversion (): m_final_bb (NULL),
+ 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)
{
- 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);
+/* Collection information about SWTCH statement. */
- if (update_dominators
- && get_immediate_dominator (CDI_DOMINATORS, e_true->dest) == split_bb)
- dominated_e_true = true;
+void
+switch_conversion::collect (gswitch *swtch)
+{
+ unsigned int branch_num = gimple_switch_num_labels (swtch);
+ tree min_case, max_case;
+ unsigned int i;
+ edge e, e_default, e_first;
+ edge_iterator ei;
- 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);
+ m_switch = swtch;
- e_false = split_block (split_bb, cond_stmt);
- new_bb = e_false->dest;
- redirect_edge_pred (e_true, split_bb);
+ /* 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. */
+ m_index_expr = gimple_switch_index (swtch);
+ m_switch_bb = gimple_bb (swtch);
+ e_default = gimple_switch_default_edge (cfun, swtch);
+ m_default_bb = e_default->dest;
+ m_default_prob = e_default->probability;
- e_true->flags &= ~EDGE_FALLTHRU;
- e_true->flags |= EDGE_TRUE_VALUE;
+ /* 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);
- e_false->flags &= ~EDGE_FALLTHRU;
- e_false->flags |= EDGE_FALSE_VALUE;
- e_false->probability = e_true->probability.invert ();
- e_false->count = split_bb->count - e_true->count;
- new_bb->count = e_false->count;
+ m_range_min = CASE_LOW (min_case);
+ if (CASE_HIGH (max_case) != NULL_TREE)
+ m_range_max = CASE_HIGH (max_case);
+ else
+ m_range_max = CASE_LOW (max_case);
- if (update_dominators)
+ m_contiguous_range = true;
+ tree last = CASE_HIGH (min_case) ? CASE_HIGH (min_case) : m_range_min;
+ for (i = 2; i < branch_num; i++)
{
- if (dominated_e_true)
- set_immediate_dominator (CDI_DOMINATORS, e_true->dest, split_bb);
- set_immediate_dominator (CDI_DOMINATORS, e_false->dest, split_bb);
+ tree elt = gimple_switch_label (swtch, i);
+ if (wi::to_wide (last) + 1 != wi::to_wide (CASE_LOW (elt)))
+ {
+ m_contiguous_range = false;
+ break;
+ }
+ last = CASE_HIGH (elt) ? CASE_HIGH (elt) : CASE_LOW (elt);
}
- return new_bb;
-}
+ if (m_contiguous_range)
+ e_first = gimple_switch_edge (cfun, swtch, 1);
+ else
+ e_first = e_default;
+
+ /* See if there is one common successor block for all branch
+ targets. If it exists, record it in FINAL_BB.
+ Start with the destination of the first non-default case
+ 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))
+ m_final_bb = e_first->dest;
+ else if (single_succ_p (e_first->dest)
+ && ! single_pred_p (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 (m_final_bb)
+ FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
+ {
+ if (e->dest == m_final_bb)
+ continue;
+
+ if (single_pred_p (e->dest)
+ && single_succ_p (e->dest)
+ && single_succ (e->dest) == m_final_bb)
+ continue;
+
+ if (e == e_default && m_contiguous_range)
+ {
+ m_default_case_nonstandard = true;
+ continue;
+ }
+ m_final_bb = NULL;
+ break;
+ }
-/* 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. */
+ m_range_size
+ = int_const_binop (MINUS_EXPR, m_range_max, m_range_min);
-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);
+ /* 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. */
+ m_count = 0;
+ for (i = 1; i < branch_num; i++)
+ {
+ tree elt = gimple_switch_label (swtch, i);
+ m_count++;
+ if (CASE_HIGH (elt)
+ && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt)))
+ m_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. */
+ m_uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1;
}
-\f
-/* 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:
+/* 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
+switch_conversion::check_range ()
+{
+ gcc_assert (m_range_size);
+ if (!tree_fits_uhwi_p (m_range_size))
+ {
+ m_reason = "index range way too large or otherwise unusable";
+ return false;
+ }
- if ((x==4) || (x==6) || (x==9) || (x==11))
+ if (tree_to_uhwi (m_range_size)
+ > ((unsigned) m_count * param_switch_conversion_branch_ratio))
+ {
+ m_reason = "the maximum range-branch ratio exceeded";
+ return false;
+ }
-as a single bit test:
+ return true;
+}
- if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11)))
+/* Checks whether all but the final BB basic blocks are empty. */
-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".
+bool
+switch_conversion::check_all_empty_except_final ()
+{
+ edge e, e_default = find_edge (m_switch_bb, m_default_bb);
+ edge_iterator ei;
-The following example shows the code the transformation generates:
+ FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
+ {
+ if (e->dest == m_final_bb)
+ continue;
- int bar(int x)
+ if (!empty_block_p (e->dest))
{
- 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;
+ if (m_contiguous_range && e == e_default)
+ {
+ m_default_case_nonstandard = true;
+ continue;
+ }
+
+ m_reason = "bad case - a non-final BB not empty";
+ return false;
}
+ }
-==>
+ return true;
+}
- 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;
- }
+/* 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. */
-TODO: There are still some improvements to this transformation that could
-be implemented:
+bool
+switch_conversion::check_final_bb ()
+{
+ gphi_iterator gsi;
-* 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.
+ 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;
-* 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.
+ if (virtual_operand_p (gimple_phi_result (phi)))
+ continue;
-This transformation was contributed by Roger Sayle, see this e-mail:
- http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html
-*/
+ m_phi_count++;
-/* 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. */
+ for (i = 0; i < gimple_phi_num_args (phi); i++)
+ {
+ basic_block bb = gimple_phi_arg_edge (phi, i)->src;
-struct case_bit_test
-{
- wide_int mask;
- edge target_edge;
- tree label;
- int bits;
-};
+ if (bb == m_switch_bb
+ || (single_pred_p (bb)
+ && single_pred (bb) == m_switch_bb
+ && (!m_default_case_nonstandard
+ || empty_block_p (bb))))
+ {
+ tree reloc, val;
+ const char *reason = NULL;
-/* 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;
+ val = gimple_phi_arg_def (phi, i);
+ if (!is_gimple_ip_invariant (val))
+ reason = "non-invariant value from a case";
+ else
+ {
+ reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
+ if ((flag_pic && reloc != null_pointer_node)
+ || (!flag_pic && reloc == NULL_TREE))
+ {
+ if (reloc)
+ reason
+ = "value from a case would need runtime relocations";
+ else
+ reason
+ = "value from a case is not a valid initializer";
+ }
+ }
+ if (reason)
+ {
+ /* 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 == m_switch_bb)
+ bb = m_final_bb;
+ if (!m_contiguous_range || bb != m_default_bb)
+ {
+ m_reason = reason;
+ return false;
+ }
- 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;
+ unsigned int branch_num = gimple_switch_num_labels (m_switch);
+ for (unsigned int i = 1; i < branch_num; i++)
+ {
+ if (gimple_switch_label_bb (cfun, m_switch, i) == bb)
+ {
+ m_reason = reason;
+ return false;
+ }
+ }
+ m_default_case_nonstandard = true;
+ }
+ }
+ }
+ }
- /* Stabilize the sort. */
- return LABEL_DECL_UID (d2->label) - LABEL_DECL_UID (d1->label);
+ return true;
}
-/* 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.
+/* 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. */
- INDEX_EXPR is the value being switched on.
+void
+switch_conversion::create_temp_arrays ()
+{
+ int i;
- 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.
+ 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;
+ 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);
+}
- There *MUST* be MAX_CASE_BIT_TESTS or less unique case
- node targets. */
+/* 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
-emit_case_bit_tests (gswitch *swtch, tree index_expr,
- tree minval, tree range, tree maxval)
+void
+switch_conversion::gather_default_values (tree default_case)
{
- 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);
+ gphi_iterator gsi;
+ basic_block bb = label_to_block (cfun, CASE_LABEL (default_case));
+ edge e;
+ int i = 0;
- vec<basic_block> bbs_to_fix_dom = vNULL;
+ gcc_assert (CASE_LOW (default_case) == NULL_TREE
+ || m_default_case_nonstandard);
- 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);
+ if (bb == m_final_bb)
+ e = find_edge (m_switch_bb, bb);
+ else
+ e = single_succ_edge (bb);
- gimple_stmt_iterator gsi;
- gassign *shift_stmt;
+ 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);
+ m_default_values[i++] = val;
+ }
+}
- 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);
+/* 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. */
- /* 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);
+void
+switch_conversion::build_constructors ()
+{
+ 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);
- /* 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;
+ tree cs = gimple_switch_label (m_switch, i);
+ basic_block bb = label_to_block (cfun, CASE_LABEL (cs));
+ edge e;
+ tree high;
+ gphi_iterator gsi;
+ int j;
- 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++;
- }
+ if (bb == m_final_bb)
+ e = find_edge (m_switch_bb, bb);
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));
+ e = single_succ_edge (bb);
+ gcc_assert (e);
- for (j = lo; j <= hi; j++)
- test[k].mask |= wi::lshift (wone, j);
- }
+ while (tree_int_cst_lt (pos, CASE_LOW (cs)))
+ {
+ int k;
+ for (k = 0; k < m_phi_count; k++)
+ {
+ constructor_elt elt;
- qsort (test, count, sizeof (*test), case_bit_test_cmp);
+ elt.index = int_const_binop (MINUS_EXPR, pos, m_range_min);
+ elt.value
+ = unshare_expr_without_location (m_default_values[k]);
+ m_constructors[k]->quick_push (elt);
+ }
- /* 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);
+ pos = int_const_binop (PLUS_EXPR, pos, pos_one);
}
- if (cost_diff > 0)
+ gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
+
+ j = 0;
+ if (CASE_HIGH (cs))
+ high = CASE_HIGH (cs);
+ else
+ high = CASE_LOW (cs);
+ for (gsi = gsi_start_phis (m_final_bb);
+ !gsi_end_p (gsi); gsi_next (&gsi))
{
- for (i = 0; i < count; i++)
- test[i].mask = wi::lshift (test[i].mask, m);
- minval = build_zero_cst (TREE_TYPE (minval));
- range = maxval;
- }
- }
+ gphi *phi = gsi.phi ();
+ if (virtual_operand_p (gimple_phi_result (phi)))
+ continue;
+ tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
+ tree low = CASE_LOW (cs);
+ pos = CASE_LOW (cs);
+
+ do
+ {
+ constructor_elt elt;
- /* 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);
+ elt.index = int_const_binop (MINUS_EXPR, pos, m_range_min);
+ elt.value = unshare_expr_without_location (val);
+ m_constructors[j]->quick_push (elt);
- 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);
+ pos = int_const_binop (PLUS_EXPR, pos, pos_one);
+ } while (!tree_int_cst_lt (high, pos)
+ && tree_int_cst_lt (low, pos));
+ j++;
+ }
}
+}
- /* Now build the test-and-branch code. */
+/* If all values in the constructor vector are products of a linear function
+ a * x + b, then return true. When true, COEFF_A and COEFF_B and
+ coefficients of the linear function. Note that equal values are special
+ case of a linear function with a and b equal to zero. */
- gsi = gsi_last_bb (switch_bb);
+bool
+switch_conversion::contains_linear_function_p (vec<constructor_elt, va_gc> *vec,
+ wide_int *coeff_a,
+ wide_int *coeff_b)
+{
+ unsigned int i;
+ constructor_elt *elt;
- /* 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);
+ gcc_assert (vec->length () >= 2);
- /* 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;
+ /* Let's try to find any linear function a * x + y that can apply to
+ given values. 'a' can be calculated as follows:
- 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 ();
- }
+ a = (y2 - y1) / (x2 - x1) where x2 - x1 = 1 (consecutive case indices)
+ a = y2 - y1
- /* 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);
+ and
- /* 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);
- }
+ b = y2 - a * x2
- /* 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);
+ tree elt0 = (*vec)[0].value;
+ tree elt1 = (*vec)[1].value;
- /* The GIMPLE_SWITCH is now redundant. */
- gsi_remove (&gsi, true);
+ if (TREE_CODE (elt0) != INTEGER_CST || TREE_CODE (elt1) != INTEGER_CST)
+ return false;
- if (update_dom)
- {
- /* Fix up the dominator tree. */
- iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
- bbs_to_fix_dom.release ();
- }
-}
-\f
-/*
- Switch initialization conversion
+ wide_int range_min
+ = wide_int::from (wi::to_wide (m_range_min),
+ TYPE_PRECISION (TREE_TYPE (elt0)),
+ TYPE_SIGN (TREE_TYPE (m_range_min)));
+ wide_int y1 = wi::to_wide (elt0);
+ wide_int y2 = wi::to_wide (elt1);
+ wide_int a = y2 - y1;
+ wide_int b = y2 - a * (range_min + 1);
-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:
+ /* Verify that all values fulfill the linear function. */
+ FOR_EACH_VEC_SAFE_ELT (vec, i, elt)
+ {
+ if (TREE_CODE (elt->value) != INTEGER_CST)
+ return false;
- int a,b;
+ wide_int value = wi::to_wide (elt->value);
+ if (a * range_min + b != value)
+ return false;
- 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>
+ ++range_min;
+ }
+ *coeff_a = a;
+ *coeff_b = b;
-is changed into:
+ return true;
+}
- 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};
+/* 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. */
- 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>
+tree
+switch_conversion::array_value_type (tree type, int num)
+{
+ unsigned int i, len = vec_safe_length (m_constructors[num]);
+ constructor_elt *elt;
+ int sign = 0;
+ tree smaller_type;
-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.
+ /* Types with alignments greater than their size can reach here, e.g. out of
+ SRA. We couldn't use these as an array component type so get back to the
+ main variant first, which, for our purposes, is fine for other types as
+ well. */
-This transformation was contributed by Martin Jambor, see this e-mail:
- http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */
+ type = TYPE_MAIN_VARIANT (type);
-/* The main structure of the pass. */
-struct switch_conv_info
-{
- /* The expression used to decide the switch branch. */
- tree index_expr;
+ if (!INTEGRAL_TYPE_P (type))
+ return type;
- /* The following integer constants store the minimum and maximum value
- covered by the case labels. */
- tree range_min;
- tree range_max;
+ scalar_int_mode type_mode = SCALAR_INT_TYPE_MODE (type);
+ scalar_int_mode mode = get_narrowest_mode (type_mode);
+ if (GET_MODE_SIZE (type_mode) <= GET_MODE_SIZE (mode))
+ return type;
- /* 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;
+ if (len < (optimize_bb_for_size_p (gimple_bb (m_switch)) ? 2 : 32))
+ return type;
- /* Basic block that contains the actual GIMPLE_SWITCH. */
- basic_block switch_bb;
+ FOR_EACH_VEC_SAFE_ELT (m_constructors[num], i, elt)
+ {
+ wide_int cst;
- /* Basic block that is the target of the default case. */
- basic_block default_bb;
+ if (TREE_CODE (elt->value) != INTEGER_CST)
+ return type;
- /* The single successor block of all branches out of the GIMPLE_SWITCH,
- if such a block exists. Otherwise NULL. */
- basic_block final_bb;
+ cst = wi::to_wide (elt->value);
+ while (1)
+ {
+ unsigned int prec = GET_MODE_BITSIZE (mode);
+ if (prec > HOST_BITS_PER_WIDE_INT)
+ return type;
- /* The probability of the default edge in the replaced switch. */
- profile_probability default_prob;
+ if (sign >= 0 && cst == wi::zext (cst, prec))
+ {
+ if (sign == 0 && cst == wi::sext (cst, prec))
+ break;
+ sign = 1;
+ break;
+ }
+ if (sign <= 0 && cst == wi::sext (cst, prec))
+ {
+ sign = -1;
+ break;
+ }
- /* The count of the default edge in the replaced switch. */
- profile_count default_count;
+ if (sign == 1)
+ sign = 0;
- /* Combined count of all other (non-default) edges in the replaced switch. */
- profile_count other_count;
+ if (!GET_MODE_WIDER_MODE (mode).exists (&mode)
+ || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (type_mode))
+ return type;
+ }
+ }
- /* Number of phi nodes in the final bb (that we'll be replacing). */
- int phi_count;
+ if (sign == 0)
+ sign = TYPE_UNSIGNED (type) ? 1 : -1;
+ smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0);
+ if (GET_MODE_SIZE (type_mode)
+ <= GET_MODE_SIZE (SCALAR_INT_TYPE_MODE (smaller_type)))
+ return type;
- /* Array of default values, in the same order as phi nodes. */
- tree *default_values;
+ return smaller_type;
+}
- /* Constructors of new static arrays. */
- vec<constructor_elt, va_gc> **constructors;
+/* 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. */
- /* Array of ssa names that are initialized with a value from a new static
- array. */
- tree *target_inbound_names;
+void
+switch_conversion::build_one_array (int num, tree arr_index_type,
+ gphi *phi, tree tidx)
+{
+ tree name;
+ gimple *load;
+ gimple_stmt_iterator gsi = gsi_for_stmt (m_switch);
+ location_t loc = gimple_location (m_switch);
- /* Array of ssa names that are initialized with the default value if the
- switch expression is out of range. */
- tree *target_outbound_names;
+ gcc_assert (m_default_values[num]);
- /* VOP SSA_NAME. */
- tree target_vop;
+ name = copy_ssa_name (PHI_RESULT (phi));
+ m_target_inbound_names[num] = name;
+
+ vec<constructor_elt, va_gc> *constructor = m_constructors[num];
+ wide_int coeff_a, coeff_b;
+ bool linear_p = contains_linear_function_p (constructor, &coeff_a, &coeff_b);
+ tree type;
+ if (linear_p
+ && (type = range_check_type (TREE_TYPE ((*constructor)[0].value))))
+ {
+ if (dump_file && coeff_a.to_uhwi () > 0)
+ fprintf (dump_file, "Linear transformation with A = %" PRId64
+ " and B = %" PRId64 "\n", coeff_a.to_shwi (),
+ coeff_b.to_shwi ());
+
+ /* We must use type of constructor values. */
+ gimple_seq seq = NULL;
+ tree tmp = gimple_convert (&seq, type, m_index_expr);
+ tree tmp2 = gimple_build (&seq, MULT_EXPR, type,
+ wide_int_to_tree (type, coeff_a), tmp);
+ tree tmp3 = gimple_build (&seq, PLUS_EXPR, type, tmp2,
+ wide_int_to_tree (type, coeff_b));
+ tree tmp4 = gimple_convert (&seq, TREE_TYPE (name), tmp3);
+ gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT);
+ load = gimple_build_assign (name, tmp4);
+ }
+ else
+ {
+ tree array_type, ctor, decl, value_type, fetch, default_type;
- /* The first load statement that loads a temporary from a new static array.
- */
- gimple *arr_ref_first;
+ 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;
- /* The last load statement that loads a temporary from a new static array. */
- gimple *arr_ref_last;
+ FOR_EACH_VEC_SAFE_ELT (constructor, i, elt)
+ elt->value = fold_convert (value_type, elt->value);
+ }
+ ctor = build_constructor (array_type, constructor);
+ TREE_CONSTANT (ctor) = true;
+ TREE_STATIC (ctor) = true;
- /* String reason why the case wasn't a good candidate that is written to the
- dump file, if there is one. */
- const char *reason;
+ decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type);
+ TREE_STATIC (decl) = 1;
+ DECL_INITIAL (decl) = ctor;
- /* True if default case is not used for any value between range_min and
- range_max inclusive. */
- bool contiguous_range;
+ DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
+ DECL_ARTIFICIAL (decl) = 1;
+ DECL_IGNORED_P (decl) = 1;
+ TREE_CONSTANT (decl) = 1;
+ TREE_READONLY (decl) = 1;
+ DECL_IGNORED_P (decl) = 1;
+ if (offloading_function_p (cfun->decl))
+ DECL_ATTRIBUTES (decl)
+ = tree_cons (get_identifier ("omp declare target"), NULL_TREE,
+ NULL_TREE);
+ varpool_node::finalize_decl (decl);
- /* True if default case does not have the required shape for other case
- labels. */
- bool default_case_nonstandard;
+ fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
+ NULL_TREE);
+ if (default_type != value_type)
+ {
+ fetch = fold_convert (default_type, fetch);
+ fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE,
+ true, GSI_SAME_STMT);
+ }
+ load = gimple_build_assign (name, fetch);
+ }
- /* Parameters for expand_switch_using_bit_tests. Should be computed
- the same way as in expand_case. */
- unsigned int uniq;
- unsigned int count;
-};
+ gsi_insert_before (&gsi, load, GSI_SAME_STMT);
+ update_stmt (load);
+ m_arr_ref_last = load;
+}
-/* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */
+/* Builds and initializes static arrays initialized with values gathered from
+ the switch statement. Also creates statements that load values from
+ them. */
-static void
-collect_switch_conv_info (gswitch *swtch, struct switch_conv_info *info)
+void
+switch_conversion::build_arrays ()
{
- unsigned int branch_num = gimple_switch_num_labels (swtch);
- tree min_case, max_case;
- unsigned int count, i;
- edge e, e_default, e_first;
- edge_iterator ei;
- basic_block first;
-
- memset (info, 0, sizeof (*info));
-
- /* 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
- = 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)
- if (e != e_default)
- info->other_count += e->count;
+ tree arr_index_type;
+ tree tidx, sub, utype;
+ gimple *stmt;
+ gimple_stmt_iterator gsi;
+ gphi_iterator gpi;
+ int i;
+ location_t loc = gimple_location (m_switch);
- /* 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);
+ gsi = gsi_for_stmt (m_switch);
- info->range_min = CASE_LOW (min_case);
- if (CASE_HIGH (max_case) != NULL_TREE)
- info->range_max = CASE_HIGH (max_case);
+ /* Make sure we do not generate arithmetics in a subrange. */
+ utype = TREE_TYPE (m_index_expr);
+ if (TREE_TYPE (utype))
+ utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1);
else
- info->range_max = CASE_LOW (max_case);
+ utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
- info->contiguous_range = true;
- tree last = CASE_HIGH (min_case) ? CASE_HIGH (min_case) : info->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;
- break;
- }
- last = CASE_HIGH (elt) ? CASE_HIGH (elt) : CASE_LOW (elt);
- }
-
- if (info->contiguous_range)
- {
- first = label_to_block (CASE_LABEL (gimple_switch_label (swtch, 1)));
- e_first = find_edge (info->switch_bb, first);
- }
- else
- {
- first = info->default_bb;
- e_first = e_default;
- }
-
- /* See if there is one common successor block for all branch
- targets. If it exists, record it in FINAL_BB.
- Start with the destination of the first non-default case
- 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;
- else if (single_succ_p (e_first->dest)
- && ! single_pred_p (single_succ (e_first->dest)))
- info->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 (e->dest == info->final_bb)
- continue;
-
- if (single_pred_p (e->dest)
- && single_succ_p (e->dest)
- && single_succ (e->dest) == info->final_bb)
- continue;
-
- if (e == e_default && info->contiguous_range)
- {
- info->default_case_nonstandard = true;
- continue;
- }
-
- info->final_bb = NULL;
- break;
- }
-
- info->range_size
- = int_const_binop (MINUS_EXPR, info->range_max, info->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;
- for (i = 1; i < branch_num; i++)
- {
- tree elt = gimple_switch_label (swtch, i);
- count++;
- if (CASE_HIGH (elt)
- && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt)))
- 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)
-{
- gcc_assert (info->range_size);
- if (!tree_fits_uhwi_p (info->range_size))
- {
- info->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))
- {
- info->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)
-{
- edge e, e_default = find_edge (info->switch_bb, info->default_bb);
- edge_iterator ei;
-
- FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
- {
- if (e->dest == info->final_bb)
- continue;
-
- if (!empty_block_p (e->dest))
- {
- if (info->contiguous_range && e == e_default)
- {
- info->default_case_nonstandard = true;
- continue;
- }
-
- info->reason = "bad case - a non-final BB not empty";
- return false;
- }
- }
-
- 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)
-{
- gphi_iterator gsi;
-
- info->phi_count = 0;
- for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
- {
- gphi *phi = gsi.phi ();
- unsigned int i;
-
- if (virtual_operand_p (gimple_phi_result (phi)))
- continue;
-
- info->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
- || (single_pred_p (bb)
- && single_pred (bb) == info->switch_bb
- && (!info->default_case_nonstandard
- || empty_block_p (bb))))
- {
- tree reloc, val;
- const char *reason = NULL;
-
- val = gimple_phi_arg_def (phi, i);
- if (!is_gimple_ip_invariant (val))
- reason = "non-invariant value from a case";
- else
- {
- reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
- if ((flag_pic && reloc != null_pointer_node)
- || (!flag_pic && reloc == NULL_TREE))
- {
- if (reloc)
- reason
- = "value from a case would need runtime relocations";
- else
- reason
- = "value from a case is not a valid initializer";
- }
- }
- if (reason)
- {
- /* 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)
- {
- info->reason = reason;
- return false;
- }
-
- unsigned int branch_num = gimple_switch_num_labels (swtch);
- for (unsigned int i = 1; i < branch_num; i++)
- {
- tree lab = CASE_LABEL (gimple_switch_label (swtch, i));
- if (label_to_block (lab) == bb)
- {
- info->reason = reason;
- return false;
- }
- }
- info->default_case_nonstandard = true;
- }
- }
- }
- }
-
- 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)
-{
- int i;
-
- info->default_values = XCNEWVEC (tree, info->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);
-}
-
-/* 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)
-{
- gphi_iterator gsi;
- basic_block bb = label_to_block (CASE_LABEL (default_case));
- edge e;
- int i = 0;
-
- gcc_assert (CASE_LOW (default_case) == NULL_TREE
- || info->default_case_nonstandard);
-
- if (bb == info->final_bb)
- e = find_edge (info->switch_bb, bb);
- else
- e = single_succ_edge (bb);
-
- for (gsi = gsi_start_phis (info->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;
- }
-}
-
-/* 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)
-{
- unsigned i, branch_num = gimple_switch_num_labels (swtch);
- tree pos = info->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);
- 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);
- else
- e = single_succ_edge (bb);
- gcc_assert (e);
-
- while (tree_int_cst_lt (pos, CASE_LOW (cs)))
- {
- int k;
- gcc_assert (!info->contiguous_range);
- for (k = 0; k < info->phi_count; k++)
- {
- constructor_elt elt;
-
- elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
- elt.value
- = unshare_expr_without_location (info->default_values[k]);
- info->constructors[k]->quick_push (elt);
- }
-
- pos = int_const_binop (PLUS_EXPR, pos, pos_one);
- }
- gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
-
- j = 0;
- if (CASE_HIGH (cs))
- high = CASE_HIGH (cs);
- else
- high = CASE_LOW (cs);
- for (gsi = gsi_start_phis (info->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);
- tree low = CASE_LOW (cs);
- pos = CASE_LOW (cs);
-
- do
- {
- constructor_elt elt;
-
- elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
- elt.value = unshare_expr_without_location (val);
- info->constructors[j]->quick_push (elt);
-
- pos = int_const_binop (PLUS_EXPR, pos, pos_one);
- } while (!tree_int_cst_lt (high, pos)
- && tree_int_cst_lt (low, pos));
- j++;
- }
- }
-}
-
-/* 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)
-{
- unsigned int i;
- tree prev = NULL_TREE;
- constructor_elt *elt;
-
- FOR_EACH_VEC_SAFE_ELT (vec, i, elt)
- {
- if (!prev)
- prev = elt->value;
- else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST))
- return NULL_TREE;
- }
- 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)
-{
- unsigned int i, len = vec_safe_length (info->constructors[num]);
- constructor_elt *elt;
- int sign = 0;
- tree smaller_type;
-
- /* Types with alignments greater than their size can reach here, e.g. out of
- SRA. We couldn't use these as an array component type so get back to the
- main variant first, which, for our purposes, is fine for other types as
- well. */
-
- type = TYPE_MAIN_VARIANT (type);
-
- if (!INTEGRAL_TYPE_P (type))
- return type;
-
- scalar_int_mode type_mode = SCALAR_INT_TYPE_MODE (type);
- scalar_int_mode mode = get_narrowest_mode (type_mode);
- if (GET_MODE_SIZE (type_mode) <= GET_MODE_SIZE (mode))
- return type;
-
- if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32))
- return type;
-
- FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
- {
- wide_int cst;
-
- if (TREE_CODE (elt->value) != INTEGER_CST)
- return type;
-
- cst = wi::to_wide (elt->value);
- while (1)
- {
- unsigned int prec = GET_MODE_BITSIZE (mode);
- if (prec > HOST_BITS_PER_WIDE_INT)
- return type;
-
- if (sign >= 0 && cst == wi::zext (cst, prec))
- {
- if (sign == 0 && cst == wi::sext (cst, prec))
- break;
- sign = 1;
- break;
- }
- if (sign <= 0 && cst == wi::sext (cst, prec))
- {
- sign = -1;
- break;
- }
-
- if (sign == 1)
- sign = 0;
-
- if (!GET_MODE_WIDER_MODE (mode).exists (&mode)
- || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (type_mode))
- return type;
- }
- }
-
- if (sign == 0)
- sign = TYPE_UNSIGNED (type) ? 1 : -1;
- smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0);
- if (GET_MODE_SIZE (type_mode)
- <= GET_MODE_SIZE (SCALAR_INT_TYPE_MODE (smaller_type)))
- return type;
-
- 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)
-{
- tree name, cst;
- gimple *load;
- gimple_stmt_iterator gsi = gsi_for_stmt (swtch);
- location_t loc = gimple_location (swtch);
-
- gcc_assert (info->default_values[num]);
-
- name = copy_ssa_name (PHI_RESULT (phi));
- info->target_inbound_names[num] = name;
-
- cst = constructor_contains_same_values_p (info->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);
- 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)
- elt->value = fold_convert (value_type, elt->value);
- }
- ctor = build_constructor (array_type, info->constructors[num]);
- TREE_CONSTANT (ctor) = true;
- TREE_STATIC (ctor) = true;
-
- decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type);
- TREE_STATIC (decl) = 1;
- DECL_INITIAL (decl) = ctor;
-
- DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
- DECL_ARTIFICIAL (decl) = 1;
- DECL_IGNORED_P (decl) = 1;
- TREE_CONSTANT (decl) = 1;
- TREE_READONLY (decl) = 1;
- DECL_IGNORED_P (decl) = 1;
- varpool_node::finalize_decl (decl);
-
- fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
- NULL_TREE);
- if (default_type != value_type)
- {
- fetch = fold_convert (default_type, fetch);
- fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE,
- true, GSI_SAME_STMT);
- }
- load = gimple_build_assign (name, fetch);
- }
-
- gsi_insert_before (&gsi, load, GSI_SAME_STMT);
- update_stmt (load);
- info->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)
-{
- tree arr_index_type;
- tree tidx, sub, utype;
- gimple *stmt;
- gimple_stmt_iterator gsi;
- gphi_iterator gpi;
- int i;
- location_t loc = gimple_location (swtch);
-
- gsi = gsi_for_stmt (swtch);
-
- /* Make sure we do not generate arithmetics in a subrange. */
- utype = TREE_TYPE (info->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. */
+ given by GSI. 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);
}
}
/* 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). */
+ 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;
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;
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
+ with default values instead. */
- 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);
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 */
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);
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);
remove_edge (e21);
}
- e1d = split_block (bb1, info->arr_ref_last);
- bbd = e1d->dest;
- remove_edge (e1d);
+ 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 (!m_default_case_nonstandard)
+ e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
+ e01->probability = m_default_prob.invert ();
+
+ /* Flags and profiles of the edge taking care of out-of-range values. */
+ e02->flags &= ~EDGE_FALLTHRU;
+ e02->flags |= EDGE_FALSE_VALUE;
+ e02->probability = m_default_prob;
+
+ bbf = m_final_bb;
+
+ e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
+ e1f->probability = profile_probability::always ();
+
+ if (m_default_case_nonstandard)
+ e2f = NULL;
+ else
+ {
+ e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
+ e2f->probability = profile_probability::always ();
+ }
+
+ /* frequencies of the new BBs */
+ bb1->count = e01->count ();
+ bb2->count = e02->count ();
+ if (!m_default_case_nonstandard)
+ bbf->count = e1f->count () + e2f->count ();
+
+ /* Tidy blocks that have become unreachable. */
+ 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);
+
+ /* Fix the dominator tree, if it is available. */
+ if (dom_info_available_p (CDI_DOMINATORS))
+ {
+ vec<basic_block> bbs_to_fix_dom;
+
+ set_immediate_dominator (CDI_DOMINATORS, bb1, bb0);
+ 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 ... */
+ set_immediate_dominator (CDI_DOMINATORS, bbf, bb0);
+
+ bbs_to_fix_dom.create (3 + (bb2 != bbf));
+ bbs_to_fix_dom.quick_push (bb0);
+ bbs_to_fix_dom.quick_push (bb1);
+ if (bb2 != bbf)
+ bbs_to_fix_dom.quick_push (bb2);
+ bbs_to_fix_dom.quick_push (bbf);
+
+ iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
+ bbs_to_fix_dom.release ();
+ }
+}
+
+/* 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
+switch_conversion::expand (gswitch *swtch)
+{
+ /* Group case labels so that we get the right results from the heuristics
+ that decide on the code generation approach for this switch. */
+ 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. */
+ if (gimple_switch_num_labels (swtch) < 2)
+ {
+ m_reason = "switch is a degenerate case";
+ return;
+ }
+
+ collect (swtch);
+
+ /* No error markers should reach here (they should be filtered out
+ during gimplification). */
+ 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 (m_index_expr));
+
+ /* Prefer bit test if possible. */
+ if (tree_fits_uhwi_p (m_range_size)
+ && bit_test_cluster::can_be_handled (tree_to_uhwi (m_range_size), m_uniq)
+ && bit_test_cluster::is_beneficial (m_count, m_uniq))
+ {
+ m_reason = "expanding as bit test is preferable";
+ return;
+ }
+
+ if (m_uniq <= 2)
+ {
+ /* This will be expanded as a decision tree . */
+ m_reason = "expanding as jumps is preferable";
+ return;
+ }
+
+ /* If there is no common successor, we cannot do the transformation. */
+ if (!m_final_bb)
+ {
+ m_reason = "no common successor to all case label target blocks found";
+ return;
+ }
+
+ /* Check the case label values are within reasonable range: */
+ if (!check_range ())
+ {
+ 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 ())
+ {
+ gcc_assert (m_reason);
+ return;
+ }
+ if (!check_final_bb ())
+ {
+ gcc_assert (m_reason);
+ return;
+ }
+
+ /* At this point all checks have passed and we can proceed with the
+ transformation. */
+
+ create_temp_arrays ();
+ gather_default_values (m_default_case_nonstandard
+ ? gimple_switch_label (swtch, 1)
+ : gimple_switch_default_label (swtch));
+ build_constructors ();
+
+ build_arrays (); /* Build the static arrays and assignments. */
+ gen_inbound_check (); /* Build the bounds check. */
+
+ m_cfg_altered = true;
+}
+
+/* Destructor. */
+
+switch_conversion::~switch_conversion ()
+{
+ XDELETEVEC (m_constructors);
+ XDELETEVEC (m_default_values);
+}
+
+/* Constructor. */
+
+group_cluster::group_cluster (vec<cluster *> &clusters,
+ unsigned start, unsigned end)
+{
+ gcc_checking_assert (end - start + 1 >= 1);
+ m_prob = profile_probability::never ();
+ m_cases.create (end - start + 1);
+ for (unsigned i = start; i <= end; i++)
+ {
+ m_cases.quick_push (static_cast<simple_cluster *> (clusters[i]));
+ m_prob += clusters[i]->m_prob;
+ }
+ m_subtree_prob = m_prob;
+}
+
+/* Destructor. */
+
+group_cluster::~group_cluster ()
+{
+ for (unsigned i = 0; i < m_cases.length (); i++)
+ delete m_cases[i];
+
+ m_cases.release ();
+}
+
+/* Dump content of a cluster. */
+
+void
+group_cluster::dump (FILE *f, bool details)
+{
+ unsigned total_values = 0;
+ for (unsigned i = 0; i < m_cases.length (); i++)
+ total_values += m_cases[i]->get_range (m_cases[i]->get_low (),
+ m_cases[i]->get_high ());
+
+ unsigned comparison_count = 0;
+ for (unsigned i = 0; i < m_cases.length (); i++)
+ {
+ simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
+ comparison_count += sc->m_range_p ? 2 : 1;
+ }
+
+ unsigned HOST_WIDE_INT range = get_range (get_low (), get_high ());
+ fprintf (f, "%s", get_type () == JUMP_TABLE ? "JT" : "BT");
+
+ if (details)
+ fprintf (f, "(values:%d comparisons:%d range:" HOST_WIDE_INT_PRINT_DEC
+ " density: %.2f%%)", total_values, comparison_count, range,
+ 100.0f * comparison_count / range);
+
+ fprintf (f, ":");
+ PRINT_CASE (f, get_low ());
+ fprintf (f, "-");
+ PRINT_CASE (f, get_high ());
+ fprintf (f, " ");
+}
+
+/* Emit GIMPLE code to handle the cluster. */
+
+void
+jump_table_cluster::emit (tree index_expr, tree,
+ tree default_label_expr, basic_block default_bb)
+{
+ unsigned HOST_WIDE_INT range = get_range (get_low (), get_high ());
+ unsigned HOST_WIDE_INT nondefault_range = 0;
+
+ /* For jump table we just emit a new gswitch statement that will
+ be latter lowered to jump table. */
+ auto_vec <tree> labels;
+ labels.create (m_cases.length ());
+
+ make_edge (m_case_bb, default_bb, 0);
+ for (unsigned i = 0; i < m_cases.length (); i++)
+ {
+ labels.quick_push (unshare_expr (m_cases[i]->m_case_label_expr));
+ make_edge (m_case_bb, m_cases[i]->m_case_bb, 0);
+ }
+
+ gswitch *s = gimple_build_switch (index_expr,
+ unshare_expr (default_label_expr), labels);
+ gimple_stmt_iterator gsi = gsi_start_bb (m_case_bb);
+ gsi_insert_after (&gsi, s, GSI_NEW_STMT);
+
+ /* Set up even probabilities for all cases. */
+ for (unsigned i = 0; i < m_cases.length (); i++)
+ {
+ simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
+ edge case_edge = find_edge (m_case_bb, sc->m_case_bb);
+ unsigned HOST_WIDE_INT case_range
+ = sc->get_range (sc->get_low (), sc->get_high ());
+ nondefault_range += case_range;
+
+ /* case_edge->aux is number of values in a jump-table that are covered
+ by the case_edge. */
+ case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + case_range);
+ }
+
+ edge default_edge = gimple_switch_default_edge (cfun, s);
+ default_edge->probability = profile_probability::never ();
+
+ for (unsigned i = 0; i < m_cases.length (); i++)
+ {
+ simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
+ edge case_edge = find_edge (m_case_bb, sc->m_case_bb);
+ case_edge->probability
+ = profile_probability::always ().apply_scale ((intptr_t)case_edge->aux,
+ range);
+ }
+
+ /* Number of non-default values is probability of default edge. */
+ default_edge->probability
+ += profile_probability::always ().apply_scale (nondefault_range,
+ range).invert ();
+
+ switch_decision_tree::reset_out_edges_aux (s);
+}
+
+/* Find jump tables of given CLUSTERS, where all members of the vector
+ are of type simple_cluster. New clusters are returned. */
+
+vec<cluster *>
+jump_table_cluster::find_jump_tables (vec<cluster *> &clusters)
+{
+ if (!is_enabled ())
+ return clusters.copy ();
+
+ unsigned l = clusters.length ();
+ auto_vec<min_cluster_item> min;
+ min.reserve (l + 1);
+
+ min.quick_push (min_cluster_item (0, 0, 0));
+
+ for (unsigned i = 1; i <= l; i++)
+ {
+ /* Set minimal # of clusters with i-th item to infinite. */
+ min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));
+
+ for (unsigned j = 0; j < i; j++)
+ {
+ unsigned HOST_WIDE_INT s = min[j].m_non_jt_cases;
+ if (i - j < case_values_threshold ())
+ s += i - j;
+
+ /* Prefer clusters with smaller number of numbers covered. */
+ if ((min[j].m_count + 1 < min[i].m_count
+ || (min[j].m_count + 1 == min[i].m_count
+ && s < min[i].m_non_jt_cases))
+ && can_be_handled (clusters, j, i - 1))
+ min[i] = min_cluster_item (min[j].m_count + 1, j, s);
+ }
+
+ gcc_checking_assert (min[i].m_count != INT_MAX);
+ }
+
+ /* No result. */
+ if (min[l].m_count == l)
+ return clusters.copy ();
+
+ vec<cluster *> output;
+ output.create (4);
+
+ /* Find and build the clusters. */
+ for (unsigned int end = l;;)
+ {
+ int start = min[end].m_start;
+
+ /* Do not allow clusters with small number of cases. */
+ if (is_beneficial (clusters, start, end - 1))
+ output.safe_push (new jump_table_cluster (clusters, start, end - 1));
+ else
+ for (int i = end - 1; i >= start; i--)
+ output.safe_push (clusters[i]);
+
+ end = start;
+
+ if (start <= 0)
+ break;
+ }
+
+ output.reverse ();
+ return output;
+}
+
+/* Return true when cluster starting at START and ending at END (inclusive)
+ can build a jump-table. */
+
+bool
+jump_table_cluster::can_be_handled (const vec<cluster *> &clusters,
+ unsigned start, unsigned end)
+{
+ /* If the switch is relatively small such that the cost of one
+ indirect jump on the target are higher than the cost of a
+ decision tree, go with the decision tree.
+
+ If range of values is much bigger than number of values,
+ or if it is too large to represent in a HOST_WIDE_INT,
+ make a sequence of conditional branches instead of a dispatch.
+
+ The definition of "much bigger" depends on whether we are
+ optimizing for size or for speed.
+
+ For algorithm correctness, jump table for a single case must return
+ true. We bail out in is_beneficial if it's called just for
+ a single case. */
+ if (start == end)
+ return true;
+
+ unsigned HOST_WIDE_INT max_ratio
+ = (optimize_insn_for_size_p ()
+ ? param_jump_table_max_growth_ratio_for_size
+ : param_jump_table_max_growth_ratio_for_speed);
+ unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (),
+ clusters[end]->get_high ());
+ /* Check overflow. */
+ if (range == 0)
+ return false;
+
+ unsigned HOST_WIDE_INT comparison_count = 0;
+ for (unsigned i = start; i <= end; i++)
+ {
+ simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]);
+ comparison_count += sc->m_range_p ? 2 : 1;
+ }
+
+ unsigned HOST_WIDE_INT lhs = 100 * range;
+ if (lhs < range)
+ return false;
+
+ return lhs <= max_ratio * comparison_count;
+}
- /* flags and profiles of the edge for in-range values */
- if (!info->default_case_nonstandard)
- e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
- e01->probability = info->default_prob.invert ();
- e01->count = info->other_count;
+/* Return true if cluster starting at START and ending at END (inclusive)
+ is profitable transformation. */
- /* flags and profiles of the edge taking care of out-of-range values */
- e02->flags &= ~EDGE_FALLTHRU;
- e02->flags |= EDGE_FALSE_VALUE;
- e02->probability = info->default_prob;
- e02->count = info->default_count;
+bool
+jump_table_cluster::is_beneficial (const vec<cluster *> &,
+ unsigned start, unsigned end)
+{
+ /* Single case bail out. */
+ if (start == end)
+ return false;
- bbf = info->final_bb;
+ return end - start + 1 >= case_values_threshold ();
+}
- e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
- e1f->probability = profile_probability::always ();
- e1f->count = info->other_count;
+/* Find bit tests of given CLUSTERS, where all members of the vector
+ are of type simple_cluster. New clusters are returned. */
- if (info->default_case_nonstandard)
- e2f = NULL;
- else
+vec<cluster *>
+bit_test_cluster::find_bit_tests (vec<cluster *> &clusters)
+{
+ unsigned l = clusters.length ();
+ auto_vec<min_cluster_item> min;
+ min.reserve (l + 1);
+
+ min.quick_push (min_cluster_item (0, 0, 0));
+
+ for (unsigned i = 1; i <= l; i++)
{
- e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
- e2f->probability = profile_probability::always ();
- e2f->count = info->default_count;
- }
+ /* Set minimal # of clusters with i-th item to infinite. */
+ min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));
- /* frequencies of the new BBs */
- bb1->frequency = EDGE_FREQUENCY (e01);
- bb2->frequency = EDGE_FREQUENCY (e02);
- if (!info->default_case_nonstandard)
- bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f);
+ for (unsigned j = 0; j < i; j++)
+ {
+ if (min[j].m_count + 1 < min[i].m_count
+ && can_be_handled (clusters, j, i - 1))
+ min[i] = min_cluster_item (min[j].m_count + 1, j, INT_MAX);
+ }
- /* Tidy blocks that have become unreachable. */
- prune_bbs (bbd, info->final_bb,
- info->default_case_nonstandard ? info->default_bb : NULL);
+ gcc_checking_assert (min[i].m_count != INT_MAX);
+ }
- /* Fixup the PHI nodes in bbF. */
- fix_phi_nodes (e1f, e2f, bbf, info);
+ /* No result. */
+ if (min[l].m_count == l)
+ return clusters.copy ();
- /* Fix the dominator tree, if it is available. */
- if (dom_info_available_p (CDI_DOMINATORS))
+ vec<cluster *> output;
+ output.create (4);
+
+ /* Find and build the clusters. */
+ for (unsigned end = l;;)
{
- vec<basic_block> bbs_to_fix_dom;
+ int start = min[end].m_start;
- set_immediate_dominator (CDI_DOMINATORS, bb1, bb0);
- if (!info->default_case_nonstandard)
- set_immediate_dominator (CDI_DOMINATORS, bb2, bb0);
- if (! get_immediate_dominator (CDI_DOMINATORS, bbf))
- /* If bbD was the immediate dominator ... */
- set_immediate_dominator (CDI_DOMINATORS, bbf, bb0);
+ if (is_beneficial (clusters, start, end - 1))
+ {
+ bool entire = start == 0 && end == clusters.length ();
+ output.safe_push (new bit_test_cluster (clusters, start, end - 1,
+ entire));
+ }
+ else
+ for (int i = end - 1; i >= start; i--)
+ output.safe_push (clusters[i]);
- bbs_to_fix_dom.create (3 + (bb2 != bbf));
- bbs_to_fix_dom.quick_push (bb0);
- bbs_to_fix_dom.quick_push (bb1);
- if (bb2 != bbf)
- bbs_to_fix_dom.quick_push (bb2);
- bbs_to_fix_dom.quick_push (bbf);
+ end = start;
- iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
- bbs_to_fix_dom.release ();
+ if (start <= 0)
+ break;
}
+
+ output.reverse ();
+ return output;
}
-/* 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. */
+/* Return true when RANGE of case values with UNIQ labels
+ can build a bit test. */
-static const char *
-process_switch (gswitch *swtch)
+bool
+bit_test_cluster::can_be_handled (unsigned HOST_WIDE_INT range,
+ unsigned int uniq)
{
- struct switch_conv_info info;
+ /* Check overflow. */
+ if (range == 0)
+ return 0;
- /* Group case labels so that we get the right results from the heuristics
- that decide on the code generation approach for this switch. */
- group_case_labels_stmt (swtch);
+ if (range >= GET_MODE_BITSIZE (word_mode))
+ return false;
- /* If this switch is now a degenerate case with only a default label,
- there is nothing left for us to do. */
- if (gimple_switch_num_labels (swtch) < 2)
- return "switch is a degenerate case";
+ return uniq <= 3;
+}
- collect_switch_conv_info (swtch, &info);
+/* Return true when cluster starting at START and ending at END (inclusive)
+ can build a bit test. */
- /* No error markers should reach here (they should be filtered out
- during gimplification). */
- gcc_checking_assert (TREE_TYPE (info.index_expr) != error_mark_node);
+bool
+bit_test_cluster::can_be_handled (const vec<cluster *> &clusters,
+ unsigned start, unsigned end)
+{
+ /* For algorithm correctness, bit test for a single case must return
+ true. We bail out in is_beneficial if it's called just for
+ a single case. */
+ if (start == end)
+ return true;
- /* A switch on a constant should have been optimized in tree-cfg-cleanup. */
- gcc_checking_assert (! TREE_CONSTANT (info.index_expr));
+ unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (),
+ clusters[end]->get_high ());
+ auto_bitmap dest_bbs;
- if (info.uniq <= MAX_CASE_BIT_TESTS)
+ for (unsigned i = start; i <= end; i++)
{
- 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";
+ simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]);
+ bitmap_set_bit (dest_bbs, sc->m_case_bb->index);
}
- /* 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";
+ return can_be_handled (range, bitmap_count_bits (dest_bbs));
+}
- /* Check the case label values are within reasonable range: */
- if (!check_range (&info))
- {
- gcc_assert (info.reason);
- return info.reason;
- }
+/* Return true when COUNT of cases of UNIQ labels is beneficial for bit test
+ transformation. */
- /* For all the cases, see whether they are empty, the assignments they
- represent constant and so on... */
- if (! check_all_empty_except_final (&info))
- {
- gcc_assert (info.reason);
- return info.reason;
- }
- if (!check_final_bb (swtch, &info))
+bool
+bit_test_cluster::is_beneficial (unsigned count, unsigned uniq)
+{
+ return (((uniq == 1 && count >= 3)
+ || (uniq == 2 && count >= 5)
+ || (uniq == 3 && count >= 6)));
+}
+
+/* Return true if cluster starting at START and ending at END (inclusive)
+ is profitable transformation. */
+
+bool
+bit_test_cluster::is_beneficial (const vec<cluster *> &clusters,
+ unsigned start, unsigned end)
+{
+ /* Single case bail out. */
+ if (start == end)
+ return false;
+
+ auto_bitmap dest_bbs;
+
+ for (unsigned i = start; i <= end; i++)
{
- gcc_assert (info.reason);
- return info.reason;
+ simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]);
+ bitmap_set_bit (dest_bbs, sc->m_case_bb->index);
}
- /* At this point all checks have passed and we can proceed with the
- transformation. */
+ unsigned uniq = bitmap_count_bits (dest_bbs);
+ unsigned count = end - start + 1;
+ return is_beneficial (count, uniq);
+}
- create_temp_arrays (&info);
- gather_default_values (info.default_case_nonstandard
- ? gimple_switch_label (swtch, 1)
- : gimple_switch_default_label (swtch), &info);
- build_constructors (swtch, &info);
+/* Comparison function for qsort to order bit tests by decreasing
+ probability of execution. */
+
+int
+case_bit_test::cmp (const void *p1, const void *p2)
+{
+ const case_bit_test *const d1 = (const case_bit_test *) p1;
+ const case_bit_test *const d2 = (const case_bit_test *) p2;
- build_arrays (swtch, &info); /* Build the static arrays and assignments. */
- gen_inbound_check (swtch, &info); /* Build the bounds check. */
+ if (d2->bits != d1->bits)
+ return d2->bits - d1->bits;
- /* Cleanup: */
- free_temp_arrays (&info);
- return NULL;
+ /* Stabilize the sort. */
+ return (LABEL_DECL_UID (CASE_LABEL (d2->label))
+ - LABEL_DECL_UID (CASE_LABEL (d1->label)));
}
-/* The main function of the pass scans statements for switches and invokes
- process_switch on them. */
+/* 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.
-namespace {
+ INDEX_EXPR is the value being switched on.
-const pass_data pass_data_convert_switch =
-{
- GIMPLE_PASS, /* type */
- "switchconv", /* name */
- OPTGROUP_NONE, /* optinfo_flags */
- TV_TREE_SWITCH_CONVERSION, /* tv_id */
- ( PROP_cfg | PROP_ssa ), /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_update_ssa, /* todo_flags_finish */
-};
+ 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.
-class pass_convert_switch : public gimple_opt_pass
+ There *MUST* be max_case_bit_tests or less unique case
+ node targets. */
+
+void
+bit_test_cluster::emit (tree index_expr, tree index_type,
+ tree, basic_block default_bb)
{
-public:
- pass_convert_switch (gcc::context *ctxt)
- : gimple_opt_pass (pass_data_convert_switch, ctxt)
- {}
+ case_bit_test test[m_max_case_bit_tests] = { {} };
+ unsigned int i, j, k;
+ unsigned int count;
- /* opt_pass methods: */
- virtual bool gate (function *) { return flag_tree_switch_conversion != 0; }
- virtual unsigned int execute (function *);
+ tree unsigned_index_type = range_check_type (index_type);
-}; // class pass_convert_switch
+ gimple_stmt_iterator gsi;
+ gassign *shift_stmt;
-unsigned int
-pass_convert_switch::execute (function *fun)
-{
- basic_block bb;
+ 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);
- FOR_EACH_BB_FN (bb, fun)
- {
- const char *failure_reason;
- gimple *stmt = last_stmt (bb);
- if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
- {
- if (dump_file)
- {
- expanded_location loc = expand_location (gimple_location (stmt));
+ tree minval = get_low ();
+ tree maxval = get_high ();
+ tree range = int_const_binop (MINUS_EXPR, maxval, minval);
+ unsigned HOST_WIDE_INT bt_range = get_range (minval, maxval);
- fprintf (dump_file, "beginning to process the following "
- "SWITCH statement (%s:%d) : ------- \n",
- loc.file, loc.line);
- print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
- putc ('\n', dump_file);
- }
+ /* 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 = 0; i < m_cases.length (); i++)
+ {
+ unsigned int lo, hi;
+ simple_cluster *n = static_cast<simple_cluster *> (m_cases[i]);
+ for (k = 0; k < count; k++)
+ if (n->m_case_bb == test[k].target_bb)
+ break;
- failure_reason = process_switch (as_a <gswitch *> (stmt));
- if (! failure_reason)
- {
- if (dump_file)
- {
- fputs ("Switch converted\n", dump_file);
- fputs ("--------------------------------\n", dump_file);
- }
+ if (k == count)
+ {
+ gcc_checking_assert (count < m_max_case_bit_tests);
+ test[k].mask = wi::zero (prec);
+ test[k].target_bb = n->m_case_bb;
+ test[k].label = n->m_case_label_expr;
+ test[k].bits = 0;
+ count++;
+ }
- /* 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
- {
- if (dump_file)
- {
- fputs ("Bailing out - ", dump_file);
- fputs (failure_reason, dump_file);
- fputs ("\n--------------------------------\n", dump_file);
- }
- }
- }
- }
+ test[k].bits += n->get_range (n->get_low (), n->get_high ());
- return 0;
-}
+ lo = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_low (), minval));
+ if (n->get_high () == NULL_TREE)
+ hi = lo;
+ else
+ hi = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_high (),
+ 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_insn_for_speed_p ();
+ 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;
+ }
+ }
+
+ /* Now build the test-and-branch code. */
+
+ gsi = gsi_last_bb (m_case_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 (m_handles_entire_switch)
+ {
+ /* 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);
+ basic_block new_bb
+ = hoist_edge_and_branch_if_true (&gsi, tmp, default_bb,
+ profile_probability::unlikely ());
+ gsi = gsi_last_bb (new_bb);
+ }
+
+ /* 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);
+
+ profile_probability prob = profile_probability::always ();
+
+ /* for each unique set of cases:
+ if (const & csui) goto target */
+ for (k = 0; k < count; k++)
+ {
+ prob = profile_probability::always ().apply_scale (test[k].bits,
+ bt_range);
+ bt_range -= test[k].bits;
+ 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);
+ basic_block new_bb
+ = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_bb, prob);
+ gsi = gsi_last_bb (new_bb);
+ }
-} // anon namespace
+ /* We should have removed all edges now. */
+ gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0);
-gimple_opt_pass *
-make_pass_convert_switch (gcc::context *ctxt)
-{
- return new pass_convert_switch (ctxt);
+ /* If nothing matched, go to the default label. */
+ edge e = make_edge (gsi_bb (gsi), default_bb, EDGE_FALLTHRU);
+ e->probability = profile_probability::always ();
}
-struct case_node
-{
- case_node *left; /* Left son in binary tree. */
- case_node *right; /* Right son in binary tree;
- also node chain. */
- case_node *parent; /* Parent of node in binary tree. */
- tree low; /* Lowest index value for this label. */
- tree high; /* Highest index value for this label. */
- basic_block case_bb; /* Label to jump to when node matches. */
- tree case_label; /* Label to jump to when node matches. */
- profile_probability prob; /* Probability of taking this case. */
- profile_probability subtree_prob; /* Probability of reaching subtree
- rooted at this node. */
-};
+/* 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.
-typedef case_node *case_node_ptr;
+ 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.
-static basic_block emit_case_nodes (basic_block, tree, case_node_ptr,
- basic_block, tree, profile_probability,
- tree, hash_map<tree, tree> *);
-static bool node_has_low_bound (case_node_ptr, tree);
-static bool node_has_high_bound (case_node_ptr, tree);
-static bool node_is_bounded (case_node_ptr, tree);
+ 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.
-/* Return the smallest number of different values for which it is best to use a
- jump-table instead of a tree of conditional branches. */
+ Returns the newly created basic block. */
-static unsigned int
-case_values_threshold (void)
+basic_block
+bit_test_cluster::hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
+ tree cond, basic_block case_bb,
+ profile_probability prob)
{
- unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
+ tree tmp;
+ gcond *cond_stmt;
+ edge e_false;
+ basic_block new_bb, split_bb = gsi_bb (*gsip);
- if (threshold == 0)
- threshold = targetm.case_values_threshold ();
+ edge e_true = make_edge (split_bb, case_bb, EDGE_TRUE_VALUE);
+ e_true->probability = prob;
+ gcc_assert (e_true->src == split_bb);
- return threshold;
-}
+ 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);
-/* Reset the aux field of all outgoing edges of basic block BB. */
+ e_false = split_block (split_bb, cond_stmt);
+ new_bb = e_false->dest;
+ redirect_edge_pred (e_true, split_bb);
-static inline void
-reset_out_edges_aux (basic_block bb)
-{
- edge e;
- edge_iterator ei;
- FOR_EACH_EDGE (e, ei, bb->succs)
- e->aux = (void *) 0;
+ e_false->flags &= ~EDGE_FALLTHRU;
+ e_false->flags |= EDGE_FALSE_VALUE;
+ e_false->probability = e_true->probability.invert ();
+ new_bb->count = e_false->count ();
+
+ return new_bb;
}
/* Compute the number of case labels that correspond to each outgoing edge of
- STMT. Record this information in the aux field of the edge. */
+ switch statement. Record this information in the aux field of the edge. */
-static inline void
-compute_cases_per_edge (gswitch *stmt)
+void
+switch_decision_tree::compute_cases_per_edge ()
{
- basic_block bb = gimple_bb (stmt);
- reset_out_edges_aux (bb);
- int ncases = gimple_switch_num_labels (stmt);
+ reset_out_edges_aux (m_switch);
+ int ncases = gimple_switch_num_labels (m_switch);
for (int i = ncases - 1; i >= 1; --i)
{
- tree elt = gimple_switch_label (stmt, i);
- tree lab = CASE_LABEL (elt);
- basic_block case_bb = label_to_block_fn (cfun, lab);
- edge case_edge = find_edge (bb, case_bb);
+ edge case_edge = gimple_switch_edge (cfun, m_switch, i);
case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + 1);
}
}
-/* Do the insertion of a case label into case_list. The labels are
- fed to us in descending order from the sorted vector of case labels used
- in the tree part of the middle end. So the list we construct is
- sorted in ascending order.
+/* Analyze switch statement and return true when the statement is expanded
+ as decision tree. */
- LABEL is the case label to be inserted. LOW and HIGH are the bounds
- against which the index is compared to jump to LABEL and PROB is the
- estimated probability LABEL is reached from the switch statement. */
-
-static case_node *
-add_case_node (case_node *head, tree low, tree high, basic_block case_bb,
- tree case_label, profile_probability prob,
- object_allocator<case_node> &case_node_pool)
+bool
+switch_decision_tree::analyze_switch_statement ()
{
- case_node *r;
-
- gcc_checking_assert (low);
- gcc_checking_assert (high && (TREE_TYPE (low) == TREE_TYPE (high)));
-
- /* Add this label to the chain. */
- r = case_node_pool.allocate ();
- r->low = low;
- r->high = high;
- r->case_bb = case_bb;
- r->case_label = case_label;
- r->parent = r->left = NULL;
- r->prob = prob;
- r->subtree_prob = prob;
- r->right = head;
- return r;
-}
+ unsigned l = gimple_switch_num_labels (m_switch);
+ basic_block bb = gimple_bb (m_switch);
+ auto_vec<cluster *> clusters;
+ clusters.create (l - 1);
-/* Dump ROOT, a list or tree of case nodes, to file. */
-
-static void
-dump_case_nodes (FILE *f, case_node *root, int indent_step, int indent_level)
-{
- if (root == 0)
- return;
- indent_level++;
+ basic_block default_bb = gimple_switch_default_bb (cfun, m_switch);
+ m_case_bbs.reserve (l);
+ m_case_bbs.quick_push (default_bb);
- dump_case_nodes (f, root->left, indent_step, indent_level);
+ compute_cases_per_edge ();
- fputs (";; ", f);
- fprintf (f, "%*s", indent_step * indent_level, "");
- print_dec (wi::to_wide (root->low), f, TYPE_SIGN (TREE_TYPE (root->low)));
- if (!tree_int_cst_equal (root->low, root->high))
+ for (unsigned i = 1; i < l; i++)
{
- fprintf (f, " ... ");
- print_dec (wi::to_wide (root->high), f,
- TYPE_SIGN (TREE_TYPE (root->high)));
- }
- fputs ("\n", f);
+ tree elt = gimple_switch_label (m_switch, i);
+ tree lab = CASE_LABEL (elt);
+ basic_block case_bb = label_to_block (cfun, lab);
+ edge case_edge = find_edge (bb, case_bb);
+ tree low = CASE_LOW (elt);
+ tree high = CASE_HIGH (elt);
- dump_case_nodes (f, root->right, indent_step, indent_level);
-}
+ profile_probability p
+ = case_edge->probability.apply_scale (1, (intptr_t) (case_edge->aux));
+ clusters.quick_push (new simple_cluster (low, high, elt, case_edge->dest,
+ p));
+ m_case_bbs.quick_push (case_edge->dest);
+ }
-/* Take an ordered list of case nodes
- and transform them into a near optimal binary tree,
- on the assumption that any target code selection value is as
- likely as any other.
+ reset_out_edges_aux (m_switch);
- The transformation is performed by splitting the ordered
- list into two equal sections plus a pivot. The parts are
- then attached to the pivot as left and right branches. Each
- branch is then transformed recursively. */
+ /* Find jump table clusters. */
+ vec<cluster *> output = jump_table_cluster::find_jump_tables (clusters);
-static void
-balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
-{
- case_node_ptr np;
+ /* Find bit test clusters. */
+ vec<cluster *> output2;
+ auto_vec<cluster *> tmp;
+ output2.create (1);
+ tmp.create (1);
- np = *head;
- if (np)
+ for (unsigned i = 0; i < output.length (); i++)
{
- int i = 0;
- int ranges = 0;
- case_node_ptr *npp;
- case_node_ptr left;
-
- /* Count the number of entries on branch. Also count the ranges. */
-
- while (np)
+ cluster *c = output[i];
+ if (c->get_type () != SIMPLE_CASE)
{
- if (!tree_int_cst_equal (np->low, np->high))
- ranges++;
-
- i++;
- np = np->right;
- }
-
- if (i > 2)
- {
- /* Split this list if it is long enough for that to help. */
- npp = head;
- left = *npp;
-
- /* If there are just three nodes, split at the middle one. */
- if (i == 3)
- npp = &(*npp)->right;
- else
+ if (!tmp.is_empty ())
{
- /* Find the place in the list that bisects the list's total cost,
- where ranges count as 2.
- Here I gets half the total cost. */
- i = (i + ranges + 1) / 2;
- while (1)
- {
- /* Skip nodes while their cost does not reach that amount. */
- if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
- i--;
- i--;
- if (i <= 0)
- break;
- npp = &(*npp)->right;
- }
+ vec<cluster *> n = bit_test_cluster::find_bit_tests (tmp);
+ output2.safe_splice (n);
+ n.release ();
+ tmp.truncate (0);
}
- *head = np = *npp;
- *npp = 0;
- np->parent = parent;
- np->left = left;
-
- /* Optimize each of the two split parts. */
- balance_case_nodes (&np->left, np);
- balance_case_nodes (&np->right, np);
- np->subtree_prob = np->prob;
- np->subtree_prob += np->left->subtree_prob;
- np->subtree_prob += np->right->subtree_prob;
+ output2.safe_push (c);
}
else
- {
- /* Else leave this branch as one level,
- but fill in `parent' fields. */
- np = *head;
- np->parent = parent;
- np->subtree_prob = np->prob;
- for (; np->right; np = np->right)
- {
- np->right->parent = np;
- (*head)->subtree_prob += np->right->subtree_prob;
- }
- }
+ tmp.safe_push (c);
}
-}
-/* Return true if a switch should be expanded as a decision tree.
- 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_as_decision_tree_p (tree range,
- unsigned int uniq ATTRIBUTE_UNUSED,
- unsigned int count)
-{
- int max_ratio;
-
- /* If neither casesi or tablejump is available, or flag_jump_tables
- over-ruled us, we really have no choice. */
- if (!targetm.have_casesi () && !targetm.have_tablejump ())
- return true;
- if (!flag_jump_tables)
- return true;
-#ifndef ASM_OUTPUT_ADDR_DIFF_ELT
- if (flag_pic)
- return true;
-#endif
+ /* We still can have a temporary vector to test. */
+ if (!tmp.is_empty ())
+ {
+ vec<cluster *> n = bit_test_cluster::find_bit_tests (tmp);
+ output2.safe_splice (n);
+ n.release ();
+ }
- /* If the switch is relatively small such that the cost of one
- indirect jump on the target are higher than the cost of a
- decision tree, go with the decision tree.
+ if (dump_file)
+ {
+ fprintf (dump_file, ";; GIMPLE switch case clusters: ");
+ for (unsigned i = 0; i < output2.length (); i++)
+ output2[i]->dump (dump_file, dump_flags & TDF_DETAILS);
+ fprintf (dump_file, "\n");
+ }
- If range of values is much bigger than number of values,
- or if it is too large to represent in a HOST_WIDE_INT,
- make a sequence of conditional branches instead of a dispatch.
+ output.release ();
- The definition of "much bigger" depends on whether we are
- optimizing for size or for speed. If the former, the maximum
- ratio range/count = 3, because this was found to be the optimal
- ratio for size on i686-pc-linux-gnu, see PR11823. The ratio
- 10 is much older, and was probably selected after an extensive
- benchmarking investigation on numerous platforms. Or maybe it
- just made sense to someone at some point in the history of GCC,
- who knows... */
- max_ratio = optimize_insn_for_size_p () ? 3 : 10;
- if (count < case_values_threshold () || !tree_fits_uhwi_p (range)
- || compare_tree_int (range, max_ratio * count) > 0)
- return true;
+ bool expanded = try_switch_expansion (output2);
- return false;
-}
+ for (unsigned i = 0; i < output2.length (); i++)
+ delete output2[i];
-static void
-fix_phi_operands_for_edge (edge e, hash_map<tree, tree> *phi_mapping)
-{
- basic_block bb = e->dest;
- gphi_iterator gsi;
- for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- {
- gphi *phi = gsi.phi ();
+ output2.release ();
- tree *definition = phi_mapping->get (gimple_phi_result (phi));
- if (definition)
- add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION);
- }
+ return expanded;
}
+/* Attempt to expand CLUSTERS as a decision tree. Return true when
+ expanded. */
-/* Add an unconditional jump to CASE_BB that happens in basic block BB. */
-
-static void
-emit_jump (basic_block bb, basic_block case_bb,
- hash_map<tree, tree> *phi_mapping)
+bool
+switch_decision_tree::try_switch_expansion (vec<cluster *> &clusters)
{
- edge e = single_succ_edge (bb);
- redirect_edge_succ (e, case_bb);
- fix_phi_operands_for_edge (e, phi_mapping);
-}
+ tree index_expr = gimple_switch_index (m_switch);
+ tree index_type = TREE_TYPE (index_expr);
+ basic_block bb = gimple_bb (m_switch);
-/* Generate a decision tree, switching on INDEX_EXPR and jumping to
- one of the labels in CASE_LIST or to the DEFAULT_LABEL.
- DEFAULT_PROB is the estimated probability that it jumps to
- DEFAULT_LABEL.
+ if (gimple_switch_num_labels (m_switch) == 1
+ || range_check_type (index_type) == NULL_TREE)
+ return false;
- We generate a binary decision tree to select the appropriate target
- code. */
+ /* Find the default case target label. */
+ edge default_edge = gimple_switch_default_edge (cfun, m_switch);
+ m_default_bb = default_edge->dest;
-static void
-emit_case_decision_tree (gswitch *s, tree index_expr, tree index_type,
- case_node_ptr case_list, basic_block default_bb,
- tree default_label, profile_probability default_prob,
- hash_map<tree, tree> *phi_mapping)
-{
- balance_case_nodes (&case_list, NULL);
+ /* Do the insertion of a case label into m_case_list. The labels are
+ fed to us in descending order from the sorted vector of case labels used
+ in the tree part of the middle end. So the list we construct is
+ sorted in ascending order. */
- if (dump_file)
- dump_function_to_file (current_function_decl, dump_file, dump_flags);
- if (dump_file && (dump_flags & TDF_DETAILS))
+ for (int i = clusters.length () - 1; i >= 0; i--)
{
- int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
- fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
- dump_case_nodes (dump_file, case_list, indent_step, 0);
+ case_tree_node *r = m_case_list;
+ m_case_list = m_case_node_pool.allocate ();
+ m_case_list->m_right = r;
+ m_case_list->m_c = clusters[i];
}
- basic_block bb = gimple_bb (s);
+ record_phi_operand_mapping ();
+
+ /* Split basic block that contains the gswitch statement. */
gimple_stmt_iterator gsi = gsi_last_bb (bb);
edge e;
if (gsi_end_p (gsi))
}
bb = split_edge (e);
- bb = emit_case_nodes (bb, index_expr, case_list, default_bb, default_label,
- default_prob, index_type, phi_mapping);
+ /* Create new basic blocks for non-case clusters where specific expansion
+ needs to happen. */
+ for (unsigned i = 0; i < clusters.length (); i++)
+ if (clusters[i]->get_type () != SIMPLE_CASE)
+ {
+ clusters[i]->m_case_bb = create_empty_bb (bb);
+ clusters[i]->m_case_bb->count = bb->count;
+ clusters[i]->m_case_bb->loop_father = bb->loop_father;
+ }
- if (bb)
- emit_jump (bb, default_bb, phi_mapping);
+ /* Do not do an extra work for a single cluster. */
+ if (clusters.length () == 1
+ && clusters[0]->get_type () != SIMPLE_CASE)
+ {
+ cluster *c = clusters[0];
+ c->emit (index_expr, index_type,
+ gimple_switch_default_label (m_switch), m_default_bb);
+ redirect_edge_succ (single_succ_edge (bb), c->m_case_bb);
+ }
+ else
+ {
+ emit (bb, index_expr, default_edge->probability, index_type);
+
+ /* Emit cluster-specific switch handling. */
+ for (unsigned i = 0; i < clusters.length (); i++)
+ if (clusters[i]->get_type () != SIMPLE_CASE)
+ clusters[i]->emit (index_expr, index_type,
+ gimple_switch_default_label (m_switch),
+ m_default_bb);
+ }
- /* Remove all edges and do just an edge that will reach default_bb. */
- gsi = gsi_last_bb (gimple_bb (s));
- gsi_remove (&gsi, true);
+ fix_phi_operands_for_edges ();
+
+ return true;
}
-static void
-record_phi_operand_mapping (const vec<basic_block> bbs, basic_block switch_bb,
- hash_map <tree, tree> *map)
+/* Before switch transformation, record all SSA_NAMEs defined in switch BB
+ and used in a label basic block. */
+
+void
+switch_decision_tree::record_phi_operand_mapping ()
{
+ basic_block switch_bb = gimple_bb (m_switch);
/* Record all PHI nodes that have to be fixed after conversion. */
- for (unsigned i = 0; i < bbs.length (); i++)
+ for (unsigned i = 0; i < m_case_bbs.length (); i++)
{
- basic_block bb = bbs[i];
-
gphi_iterator gsi;
+ basic_block bb = m_case_bbs[i];
for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
gphi *phi = gsi.phi ();
{
tree def = gimple_phi_arg_def (phi, i);
tree result = gimple_phi_result (phi);
- map->put (result, def);
+ m_phi_mapping.put (result, def);
break;
}
}
}
}
-/* Attempt to expand gimple switch STMT to a decision tree. */
+/* Append new operands to PHI statements that were introduced due to
+ addition of new edges to case labels. */
-static bool
-try_switch_expansion (gswitch *stmt)
+void
+switch_decision_tree::fix_phi_operands_for_edges ()
{
- tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
- basic_block default_bb;
- unsigned int count, uniq;
- int i;
- int ncases = gimple_switch_num_labels (stmt);
- tree index_expr = gimple_switch_index (stmt);
- tree index_type = TREE_TYPE (index_expr);
- tree elt;
- basic_block bb = gimple_bb (stmt);
-
- hash_map<tree, tree> phi_mapping;
- auto_vec<basic_block> case_bbs;
-
- /* A list of case labels; it is first built as a list and it may then
- be rearranged into a nearly balanced binary tree. */
- case_node *case_list = 0;
-
- /* A pool for case nodes. */
- object_allocator<case_node> case_node_pool ("struct case_node pool");
-
- /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
- expressions being INTEGER_CST. */
- gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
+ gphi_iterator gsi;
- if (ncases == 1)
- return false;
+ for (unsigned i = 0; i < m_case_bbs.length (); i++)
+ {
+ basic_block bb = m_case_bbs[i];
+ for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gphi *phi = gsi.phi ();
+ for (unsigned j = 0; j < gimple_phi_num_args (phi); j++)
+ {
+ tree def = gimple_phi_arg_def (phi, j);
+ if (def == NULL_TREE)
+ {
+ edge e = gimple_phi_arg_edge (phi, j);
+ tree *definition
+ = m_phi_mapping.get (gimple_phi_result (phi));
+ gcc_assert (definition);
+ add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION);
+ }
+ }
+ }
+ }
+}
- /* Find the default case target label. */
- tree default_label = CASE_LABEL (gimple_switch_default_label (stmt));
- default_bb = label_to_block_fn (cfun, default_label);
- edge default_edge = find_edge (bb, default_bb);
- profile_probability default_prob = default_edge->probability;
- case_bbs.safe_push (default_bb);
-
- /* Get upper and lower bounds of case values. */
- elt = gimple_switch_label (stmt, 1);
- minval = fold_convert (index_type, CASE_LOW (elt));
- elt = gimple_switch_label (stmt, ncases - 1);
- if (CASE_HIGH (elt))
- maxval = fold_convert (index_type, CASE_HIGH (elt));
- else
- maxval = fold_convert (index_type, CASE_LOW (elt));
+/* Generate a decision tree, switching on INDEX_EXPR and jumping to
+ one of the labels in CASE_LIST or to the DEFAULT_LABEL.
- /* Compute span of values. */
- range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
+ We generate a binary decision tree to select the appropriate target
+ code. */
- /* Listify the labels queue and gather some numbers to decide
- how to expand this switch. */
- uniq = 0;
- count = 0;
- hash_set<tree> seen_labels;
- compute_cases_per_edge (stmt);
+void
+switch_decision_tree::emit (basic_block bb, tree index_expr,
+ profile_probability default_prob, tree index_type)
+{
+ balance_case_nodes (&m_case_list, NULL);
- for (i = ncases - 1; i >= 1; --i)
+ if (dump_file)
+ dump_function_to_file (current_function_decl, dump_file, dump_flags);
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- elt = gimple_switch_label (stmt, i);
- tree low = CASE_LOW (elt);
- gcc_assert (low);
- tree high = CASE_HIGH (elt);
- gcc_assert (!high || tree_int_cst_lt (low, high));
- tree lab = CASE_LABEL (elt);
-
- /* Count the elements.
- A range counts double, since it requires two compares. */
- count++;
- if (high)
- count++;
-
- /* If we have not seen this label yet, then increase the
- number of unique case node targets seen. */
- if (!seen_labels.add (lab))
- uniq++;
-
- /* The bounds on the case range, LOW and HIGH, have to be converted
- to case's index type TYPE. Note that the original type of the
- case index in the source code is usually "lost" during
- gimplification due to type promotion, but the case labels retain the
- original type. Make sure to drop overflow flags. */
- low = fold_convert (index_type, low);
- if (TREE_OVERFLOW (low))
- low = wide_int_to_tree (index_type, wi::to_wide (low));
-
- /* The canonical from of a case label in GIMPLE is that a simple case
- has an empty CASE_HIGH. For the casesi and tablejump expanders,
- the back ends want simple cases to have high == low. */
- if (!high)
- high = low;
- high = fold_convert (index_type, high);
- if (TREE_OVERFLOW (high))
- high = wide_int_to_tree (index_type, wi::to_wide (high));
-
- basic_block case_bb = label_to_block_fn (cfun, lab);
- edge case_edge = find_edge (bb, case_bb);
- case_list = add_case_node (
- case_list, low, high, case_bb, lab,
- case_edge->probability.apply_scale (1, (intptr_t) (case_edge->aux)),
- case_node_pool);
-
- case_bbs.safe_push (case_bb);
+ int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
+ fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
+ gcc_assert (m_case_list != NULL);
+ dump_case_nodes (dump_file, m_case_list, indent_step, 0);
}
- reset_out_edges_aux (bb);
- record_phi_operand_mapping (case_bbs, bb, &phi_mapping);
- /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
- destination, such as one with a default case only.
- It also removes cases that are out of range for the switch
- type, so we should never get a zero here. */
- gcc_assert (count > 0);
+ bb = emit_case_nodes (bb, index_expr, m_case_list, default_prob, index_type,
+ gimple_location (m_switch));
- /* Decide how to expand this switch.
- The two options at this point are a dispatch table (casesi or
- tablejump) or a decision tree. */
+ if (bb)
+ emit_jump (bb, m_default_bb);
- if (expand_switch_as_decision_tree_p (range, uniq, count))
- {
- emit_case_decision_tree (stmt, index_expr, index_type, case_list,
- default_bb, default_label, default_prob,
- &phi_mapping);
- return true;
- }
+ /* Remove all edges and do just an edge that will reach default_bb. */
+ bb = gimple_bb (m_switch);
+ gimple_stmt_iterator gsi = gsi_last_bb (bb);
+ gsi_remove (&gsi, true);
- return false;
+ delete_basic_block (bb);
}
-/* The main function of the pass scans statements for switches and invokes
- process_switch on them. */
+/* Take an ordered list of case nodes
+ and transform them into a near optimal binary tree,
+ on the assumption that any target code selection value is as
+ likely as any other.
-namespace {
+ The transformation is performed by splitting the ordered
+ list into two equal sections plus a pivot. The parts are
+ then attached to the pivot as left and right branches. Each
+ branch is then transformed recursively. */
-const pass_data pass_data_lower_switch =
+void
+switch_decision_tree::balance_case_nodes (case_tree_node **head,
+ case_tree_node *parent)
{
- GIMPLE_PASS, /* type */
- "switchlower", /* name */
- OPTGROUP_NONE, /* optinfo_flags */
- TV_TREE_SWITCH_LOWERING, /* tv_id */
- ( PROP_cfg | PROP_ssa ), /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */
-};
+ case_tree_node *np;
-class pass_lower_switch : public gimple_opt_pass
-{
-public:
- pass_lower_switch (gcc::context *ctxt)
- : gimple_opt_pass (pass_data_lower_switch, ctxt)
- {}
+ np = *head;
+ if (np)
+ {
+ int i = 0;
+ int ranges = 0;
+ case_tree_node **npp;
+ case_tree_node *left;
+ profile_probability prob = profile_probability::never ();
- /* opt_pass methods: */
- virtual bool gate (function *) { return true; }
- virtual unsigned int execute (function *);
+ /* Count the number of entries on branch. Also count the ranges. */
+
+ while (np)
+ {
+ if (!tree_int_cst_equal (np->m_c->get_low (), np->m_c->get_high ()))
+ ranges++;
+
+ i++;
+ prob += np->m_c->m_prob;
+ np = np->m_right;
+ }
+
+ if (i > 2)
+ {
+ /* Split this list if it is long enough for that to help. */
+ npp = head;
+ left = *npp;
+ profile_probability pivot_prob = prob.apply_scale (1, 2);
-}; // class pass_lower_switch
+ /* Find the place in the list that bisects the list's total cost,
+ where ranges count as 2. */
+ while (1)
+ {
+ /* Skip nodes while their probability does not reach
+ that amount. */
+ prob -= (*npp)->m_c->m_prob;
+ if ((prob.initialized_p () && prob < pivot_prob)
+ || ! (*npp)->m_right)
+ break;
+ npp = &(*npp)->m_right;
+ }
-unsigned int
-pass_lower_switch::execute (function *fun)
-{
- basic_block bb;
- bool expanded = false;
+ np = *npp;
+ *npp = 0;
+ *head = np;
+ np->m_parent = parent;
+ np->m_left = left == np ? NULL : left;
- FOR_EACH_BB_FN (bb, fun)
- {
- gimple *stmt = last_stmt (bb);
- if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
+ /* Optimize each of the two split parts. */
+ balance_case_nodes (&np->m_left, np);
+ balance_case_nodes (&np->m_right, np);
+ np->m_c->m_subtree_prob = np->m_c->m_prob;
+ if (np->m_left)
+ np->m_c->m_subtree_prob += np->m_left->m_c->m_subtree_prob;
+ if (np->m_right)
+ np->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob;
+ }
+ else
{
- if (dump_file)
+ /* Else leave this branch as one level,
+ but fill in `parent' fields. */
+ np = *head;
+ np->m_parent = parent;
+ np->m_c->m_subtree_prob = np->m_c->m_prob;
+ for (; np->m_right; np = np->m_right)
{
- expanded_location loc = expand_location (gimple_location (stmt));
-
- fprintf (dump_file, "beginning to process the following "
- "SWITCH statement (%s:%d) : ------- \n",
- loc.file, loc.line);
- print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
- putc ('\n', dump_file);
+ np->m_right->m_parent = np;
+ (*head)->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob;
}
-
- expanded |= try_switch_expansion (as_a<gswitch *> (stmt));
}
}
+}
- if (expanded)
- {
- free_dominance_info (CDI_DOMINATORS);
- free_dominance_info (CDI_POST_DOMINATORS);
- mark_virtual_operands_for_renaming (cfun);
- }
+/* Dump ROOT, a list or tree of case nodes, to file. */
- return 0;
+void
+switch_decision_tree::dump_case_nodes (FILE *f, case_tree_node *root,
+ int indent_step, int indent_level)
+{
+ if (root == 0)
+ return;
+ indent_level++;
+
+ dump_case_nodes (f, root->m_left, indent_step, indent_level);
+
+ fputs (";; ", f);
+ fprintf (f, "%*s", indent_step * indent_level, "");
+ root->m_c->dump (f);
+ root->m_c->m_prob.dump (f);
+ fputs (" subtree: ", f);
+ root->m_c->m_subtree_prob.dump (f);
+ fputs (")\n", f);
+
+ dump_case_nodes (f, root->m_right, indent_step, indent_level);
}
-} // anon namespace
-gimple_opt_pass *
-make_pass_lower_switch (gcc::context *ctxt)
+/* Add an unconditional jump to CASE_BB that happens in basic block BB. */
+
+void
+switch_decision_tree::emit_jump (basic_block bb, basic_block case_bb)
{
- return new pass_lower_switch (ctxt);
+ edge e = single_succ_edge (bb);
+ redirect_edge_succ (e, case_bb);
}
-/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE.
- PROB is the probability of jumping to LABEL. */
-static basic_block
-do_jump_if_equal (basic_block bb, tree op0, tree op1, basic_block label_bb,
- profile_probability prob, hash_map<tree, tree> *phi_mapping)
+/* Generate code to compare OP0 with OP1 so that the condition codes are
+ set and to jump to LABEL_BB if the condition is true.
+ COMPARISON is the GIMPLE comparison (EQ, NE, GT, etc.).
+ PROB is the probability of jumping to LABEL_BB. */
+
+basic_block
+switch_decision_tree::emit_cmp_and_jump_insns (basic_block bb, tree op0,
+ tree op1, tree_code comparison,
+ basic_block label_bb,
+ profile_probability prob,
+ location_t loc)
{
- gcond *cond = gimple_build_cond (EQ_EXPR, op0, op1, NULL_TREE, NULL_TREE);
+ // TODO: it's once called with lhs != index.
+ op1 = fold_convert (TREE_TYPE (op0), op1);
+
+ gcond *cond = gimple_build_cond (comparison, op0, op1, NULL_TREE, NULL_TREE);
+ gimple_set_location (cond, loc);
gimple_stmt_iterator gsi = gsi_last_bb (bb);
- gsi_insert_before (&gsi, cond, GSI_SAME_STMT);
+ gsi_insert_after (&gsi, cond, GSI_NEW_STMT);
gcc_assert (single_succ_p (bb));
edge false_edge = split_block (bb, cond);
false_edge->flags = EDGE_FALSE_VALUE;
false_edge->probability = prob.invert ();
- false_edge->count = bb->count.apply_probability (false_edge->probability);
edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
- fix_phi_operands_for_edge (true_edge, phi_mapping);
true_edge->probability = prob;
- true_edge->count = bb->count.apply_probability (true_edge->probability);
return false_edge->dest;
}
-/* Generate code to compare X with Y so that the condition codes are
- set and to jump to LABEL if the condition is true. If X is a
- constant and Y is not a constant, then the comparison is swapped to
- ensure that the comparison RTL has the canonical form.
-
- UNSIGNEDP nonzero says that X and Y are unsigned; this matters if they
- need to be widened. UNSIGNEDP is also used to select the proper
- branch condition code.
-
- If X and Y have mode BLKmode, then SIZE specifies the size of both X and Y.
-
- MODE is the mode of the inputs (in case they are const_int).
-
- COMPARISON is the rtl operator to compare with (EQ, NE, GT, etc.).
- It will be potentially converted into an unsigned variant based on
- UNSIGNEDP to select a proper jump instruction.
-
- PROB is the probability of jumping to LABEL. */
+/* Generate code to jump to LABEL if OP0 and OP1 are equal.
+ PROB is the probability of jumping to LABEL_BB.
+ BB is a basic block where the new condition will be placed. */
-static basic_block
-emit_cmp_and_jump_insns (basic_block bb, tree op0, tree op1,
- tree_code comparison, basic_block label_bb,
- profile_probability prob,
- hash_map<tree, tree> *phi_mapping)
+basic_block
+switch_decision_tree::do_jump_if_equal (basic_block bb, tree op0, tree op1,
+ basic_block label_bb,
+ profile_probability prob,
+ location_t loc)
{
- gcond *cond = gimple_build_cond (comparison, op0, op1, NULL_TREE, NULL_TREE);
+ op1 = fold_convert (TREE_TYPE (op0), op1);
+
+ gcond *cond = gimple_build_cond (EQ_EXPR, op0, op1, NULL_TREE, NULL_TREE);
+ gimple_set_location (cond, loc);
gimple_stmt_iterator gsi = gsi_last_bb (bb);
- gsi_insert_after (&gsi, cond, GSI_NEW_STMT);
+ gsi_insert_before (&gsi, cond, GSI_SAME_STMT);
gcc_assert (single_succ_p (bb));
edge false_edge = split_block (bb, cond);
false_edge->flags = EDGE_FALSE_VALUE;
false_edge->probability = prob.invert ();
- false_edge->count = bb->count.apply_probability (false_edge->probability);
edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
- fix_phi_operands_for_edge (true_edge, phi_mapping);
true_edge->probability = prob;
- true_edge->count = bb->count.apply_probability (true_edge->probability);
return false_edge->dest;
}
-/* Computes the conditional probability of jumping to a target if the branch
- instruction is executed.
- TARGET_PROB is the estimated probability of jumping to a target relative
- to some basic block BB.
- BASE_PROB is the probability of reaching the branch instruction relative
- to the same basic block BB. */
-
-static inline profile_probability
-conditional_probability (profile_probability target_prob,
- profile_probability base_prob)
-{
- return target_prob / base_prob;
-}
-
/* Emit step-by-step code to select a case for the value of INDEX.
The thus generated decision tree follows the form of the
case-node binary tree NODE, whose nodes represent test conditions.
- INDEX_TYPE is the type of the index of the switch.
-
- Care is taken to prune redundant tests from the decision tree
- by detecting any boundary conditions already checked by
- emitted rtx. (See node_has_high_bound, node_has_low_bound
- and node_is_bounded, above.)
-
- Where the test conditions can be shown to be redundant we emit
- an unconditional jump to the target code. As a further
- optimization, the subordinates of a tree node are examined to
- check for bounded nodes. In this case conditional and/or
- unconditional jumps as a result of the boundary check for the
- current node are arranged to target the subordinates associated
- code for out of bound conditions on the current node.
-
- We can assume that when control reaches the code generated here,
- the index value has already been compared with the parents
- of this node, and determined to be on the same side of each parent
- as this node is. Thus, if this node tests for the value 51,
- and a parent tested for 52, we don't need to consider
- the possibility of a value greater than 51. If another parent
- tests for the value 50, then this node need not test anything. */
-
-static basic_block
-emit_case_nodes (basic_block bb, tree index, case_node_ptr node,
- basic_block default_bb, tree default_label,
- profile_probability default_prob, tree index_type,
- hash_map<tree, tree> *phi_mapping)
+ DEFAULT_PROB is probability of cases leading to default BB.
+ INDEX_TYPE is the type of the index of the switch. */
+
+basic_block
+switch_decision_tree::emit_case_nodes (basic_block bb, tree index,
+ case_tree_node *node,
+ profile_probability default_prob,
+ tree index_type, location_t loc)
{
- /* If INDEX has an unsigned type, we must make unsigned branches. */
- profile_probability probability;
- profile_probability prob = node->prob, subtree_prob = node->subtree_prob;
+ profile_probability p;
- /* See if our parents have already tested everything for us.
- If they have, emit an unconditional jump for this node. */
- if (node_is_bounded (node, index_type))
- {
- emit_jump (bb, node->case_bb, phi_mapping);
- return NULL;
- }
+ /* If node is null, we are done. */
+ if (node == NULL)
+ return bb;
- else if (tree_int_cst_equal (node->low, node->high))
+ /* Single value case. */
+ if (node->m_c->is_single_value_p ())
{
- probability = conditional_probability (prob, subtree_prob + default_prob);
/* Node is single valued. First see if the index expression matches
this node and then check our children, if any. */
- bb = do_jump_if_equal (bb, index, node->low, node->case_bb, probability,
- phi_mapping);
+ p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob);
+ bb = do_jump_if_equal (bb, index, node->m_c->get_low (),
+ node->m_c->m_case_bb, p, loc);
/* Since this case is taken at this point, reduce its weight from
subtree_weight. */
- subtree_prob -= prob;
- if (node->right != 0 && node->left != 0)
- {
- /* This node has children on both sides.
- Dispatch to one side or the other
- by comparing the index value with this node's value.
- If one subtree is bounded, check that one first,
- so we can avoid real branches in the tree. */
+ node->m_c->m_subtree_prob -= p;
- if (node_is_bounded (node->right, index_type))
- {
- probability
- = conditional_probability (node->right->prob,
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
- node->right->case_bb, probability,
- phi_mapping);
- bb = emit_case_nodes (bb, index, node->left, default_bb,
- default_label, default_prob, index_type,
- phi_mapping);
- }
-
- else if (node_is_bounded (node->left, index_type))
- {
- probability
- = conditional_probability (node->left->prob,
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR,
- node->left->case_bb, probability,
- phi_mapping);
- bb = emit_case_nodes (bb, index, node->right, default_bb,
- default_label, default_prob, index_type,
- phi_mapping);
- }
+ if (node->m_left != NULL && node->m_right != NULL)
+ {
+ /* 1) the node has both children
- /* If both children are single-valued cases with no
+ If both children are single-valued cases with no
children, finish up all the work. This way, we can save
one ordered comparison. */
- else if (tree_int_cst_equal (node->right->low, node->right->high)
- && node->right->left == 0 && node->right->right == 0
- && tree_int_cst_equal (node->left->low, node->left->high)
- && node->left->left == 0 && node->left->right == 0)
+
+ if (!node->m_left->has_child ()
+ && node->m_left->m_c->is_single_value_p ()
+ && !node->m_right->has_child ()
+ && node->m_right->m_c->is_single_value_p ())
{
- /* Neither node is bounded. First distinguish the two sides;
- then emit the code for one side at a time. */
-
- /* See if the value matches what the right hand side
- wants. */
- probability
- = conditional_probability (node->right->prob,
- subtree_prob + default_prob);
- bb = do_jump_if_equal (bb, index, node->right->low,
- node->right->case_bb, probability,
- phi_mapping);
-
- /* See if the value matches what the left hand side
- wants. */
- probability
- = conditional_probability (node->left->prob,
- subtree_prob + default_prob);
- bb = do_jump_if_equal (bb, index, node->left->low,
- node->left->case_bb, probability,
- phi_mapping);
+ p = (node->m_right->m_c->m_prob
+ / (node->m_c->m_subtree_prob + default_prob));
+ bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (),
+ node->m_right->m_c->m_case_bb, p, loc);
+
+ p = (node->m_left->m_c->m_prob
+ / (node->m_c->m_subtree_prob + default_prob));
+ bb = do_jump_if_equal (bb, index, node->m_left->m_c->get_low (),
+ node->m_left->m_c->m_case_bb, p, loc);
}
-
else
{
- /* Neither node is bounded. First distinguish the two sides;
- then emit the code for one side at a time. */
-
+ /* Branch to a label where we will handle it later. */
basic_block test_bb = split_edge (single_succ_edge (bb));
redirect_edge_succ (single_pred_edge (test_bb),
single_succ_edge (bb)->dest);
- /* The default label could be reached either through the right
- subtree or the left subtree. Divide the probability
- equally. */
- probability
- = conditional_probability (node->right->subtree_prob
- + default_prob.apply_scale (1, 2),
- subtree_prob + default_prob);
- /* See if the value is on the right. */
- bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
- test_bb, probability, phi_mapping);
+ p = ((node->m_right->m_c->m_subtree_prob
+ + default_prob.apply_scale (1, 2))
+ / (node->m_c->m_subtree_prob + default_prob));
+ bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
+ GT_EXPR, test_bb, p, loc);
default_prob = default_prob.apply_scale (1, 2);
- /* Value must be on the left.
- Handle the left-hand subtree. */
- bb = emit_case_nodes (bb, index, node->left, default_bb,
- default_label, default_prob, index_type,
- phi_mapping);
- /* If left-hand subtree does nothing,
- go to default. */
-
- if (bb && default_bb)
- emit_jump (bb, default_bb, phi_mapping);
-
- /* Code branches here for the right-hand subtree. */
- bb = emit_case_nodes (test_bb, index, node->right, default_bb,
- default_label, default_prob, index_type,
- phi_mapping);
+ /* Handle the left-hand subtree. */
+ bb = emit_case_nodes (bb, index, node->m_left,
+ default_prob, index_type, loc);
+
+ /* If the left-hand subtree fell through,
+ don't let it fall into the right-hand subtree. */
+ if (bb && m_default_bb)
+ emit_jump (bb, m_default_bb);
+
+ bb = emit_case_nodes (test_bb, index, node->m_right,
+ default_prob, index_type, loc);
}
}
- else if (node->right != 0 && node->left == 0)
+ else if (node->m_left == NULL && node->m_right != NULL)
{
+ /* 2) the node has only right child. */
+
/* Here we have a right child but no left so we issue a conditional
branch to default and process the right child.
does not have any children and is single valued; it would
cost too much space to save so little time. */
- if (node->right->right || node->right->left
- || !tree_int_cst_equal (node->right->low, node->right->high))
+ if (node->m_right->has_child ()
+ || !node->m_right->m_c->is_single_value_p ())
{
- if (!node_has_low_bound (node, index_type))
- {
- probability
- = conditional_probability (default_prob.apply_scale (1, 2),
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR,
- default_bb, probability,
- phi_mapping);
- default_prob = default_prob.apply_scale (1, 2);
- }
+ p = (default_prob.apply_scale (1, 2)
+ / (node->m_c->m_subtree_prob + default_prob));
+ bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (),
+ LT_EXPR, m_default_bb, p, loc);
+ default_prob = default_prob.apply_scale (1, 2);
- bb = emit_case_nodes (bb, index, node->right, default_bb,
- default_label, default_prob, index_type,
- phi_mapping);
+ bb = emit_case_nodes (bb, index, node->m_right, default_prob,
+ index_type, loc);
}
else
{
- probability
- = conditional_probability (node->right->subtree_prob,
- subtree_prob + default_prob);
/* We cannot process node->right normally
since we haven't ruled out the numbers less than
this node's value. So handle node->right explicitly. */
- bb = do_jump_if_equal (bb, index, node->right->low,
- node->right->case_bb, probability,
- phi_mapping);
+ p = (node->m_right->m_c->m_subtree_prob
+ / (node->m_c->m_subtree_prob + default_prob));
+ bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (),
+ node->m_right->m_c->m_case_bb, p, loc);
}
}
-
- else if (node->right == 0 && node->left != 0)
+ else if (node->m_left != NULL && node->m_right == NULL)
{
- /* Just one subtree, on the left. */
- if (node->left->left || node->left->right
- || !tree_int_cst_equal (node->left->low, node->left->high))
+ /* 3) just one subtree, on the left. Similar case as previous. */
+
+ if (node->m_left->has_child ()
+ || !node->m_left->m_c->is_single_value_p ())
{
- if (!node_has_high_bound (node, index_type))
- {
- probability
- = conditional_probability (default_prob.apply_scale (1, 2),
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
- default_bb, probability,
- phi_mapping);
+ p = (default_prob.apply_scale (1, 2)
+ / (node->m_c->m_subtree_prob + default_prob));
+ bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
+ GT_EXPR, m_default_bb, p, loc);
default_prob = default_prob.apply_scale (1, 2);
- }
- bb = emit_case_nodes (bb, index, node->left, default_bb,
- default_label, default_prob, index_type,
- phi_mapping);
+ bb = emit_case_nodes (bb, index, node->m_left, default_prob,
+ index_type, loc);
}
else
{
- probability
- = conditional_probability (node->left->subtree_prob,
- subtree_prob + default_prob);
/* We cannot process node->left normally
since we haven't ruled out the numbers less than
this node's value. So handle node->left explicitly. */
- do_jump_if_equal (bb, index, node->left->low, node->left->case_bb,
- probability, phi_mapping);
+ p = (node->m_left->m_c->m_subtree_prob
+ / (node->m_c->m_subtree_prob + default_prob));
+ bb = do_jump_if_equal (bb, index, node->m_left->m_c->get_low (),
+ node->m_left->m_c->m_case_bb, p, loc);
}
}
}
/* Node is a range. These cases are very similar to those for a single
value, except that we do not start by testing whether this node
is the one to branch to. */
-
- if (node->right != 0 && node->left != 0)
+ if (node->has_child () || node->m_c->get_type () != SIMPLE_CASE)
{
- /* Node has subtrees on both sides.
- If the right-hand subtree is bounded,
- test for it first, since we can go straight there.
- Otherwise, we need to make a branch in the control structure,
- then handle the two subtrees. */
- basic_block test_bb = NULL;
-
- if (node_is_bounded (node->right, index_type))
- {
- /* Right hand node is fully bounded so we can eliminate any
- testing and branch directly to the target code. */
- probability
- = conditional_probability (node->right->subtree_prob,
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
- node->right->case_bb, probability,
- phi_mapping);
- }
- else
- {
- /* Right hand node requires testing.
- Branch to a label where we will handle it later. */
+ /* Branch to a label where we will handle it later. */
+ basic_block test_bb = split_edge (single_succ_edge (bb));
+ redirect_edge_succ (single_pred_edge (test_bb),
+ single_succ_edge (bb)->dest);
- test_bb = split_edge (single_succ_edge (bb));
- redirect_edge_succ (single_pred_edge (test_bb),
- single_succ_edge (bb)->dest);
- probability
- = conditional_probability (node->right->subtree_prob
- + default_prob.apply_scale (1, 2),
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
- test_bb, probability, phi_mapping);
- default_prob = default_prob.apply_scale (1, 2);
- }
+ profile_probability right_prob = profile_probability::never ();
+ if (node->m_right)
+ right_prob = node->m_right->m_c->m_subtree_prob;
+ p = ((right_prob + default_prob.apply_scale (1, 2))
+ / (node->m_c->m_subtree_prob + default_prob));
- /* Value belongs to this node or to the left-hand subtree. */
+ bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
+ GT_EXPR, test_bb, p, loc);
+ default_prob = default_prob.apply_scale (1, 2);
- probability
- = conditional_probability (prob, subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR,
- node->case_bb, probability,
- phi_mapping);
+ /* Value belongs to this node or to the left-hand subtree. */
+ p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob);
+ bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (),
+ GE_EXPR, node->m_c->m_case_bb, p, loc);
/* Handle the left-hand subtree. */
- bb = emit_case_nodes (bb, index, node->left, default_bb,
- default_label, default_prob, index_type,
- phi_mapping);
-
- /* If right node had to be handled later, do that now. */
- if (test_bb)
- {
- /* If the left-hand subtree fell through,
- don't let it fall into the right-hand subtree. */
- if (bb && default_bb)
- emit_jump (bb, default_bb, phi_mapping);
-
- bb = emit_case_nodes (test_bb, index, node->right, default_bb,
- default_label, default_prob, index_type,
- phi_mapping);
- }
- }
-
- else if (node->right != 0 && node->left == 0)
- {
- /* Deal with values to the left of this node,
- if they are possible. */
- if (!node_has_low_bound (node, index_type))
- {
- probability
- = conditional_probability (default_prob.apply_scale (1, 2),
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR,
- default_bb, probability,
- phi_mapping);
- default_prob = default_prob.apply_scale (1, 2);
- }
-
- /* Value belongs to this node or to the right-hand subtree. */
-
- probability
- = conditional_probability (prob, subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->high, LE_EXPR,
- node->case_bb, probability,
- phi_mapping);
-
- bb = emit_case_nodes (bb, index, node->right, default_bb,
- default_label, default_prob, index_type,
- phi_mapping);
- }
-
- else if (node->right == 0 && node->left != 0)
- {
- /* Deal with values to the right of this node,
- if they are possible. */
- if (!node_has_high_bound (node, index_type))
- {
- probability
- = conditional_probability (default_prob.apply_scale (1, 2),
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
- default_bb, probability,
- phi_mapping);
- default_prob = default_prob.apply_scale (1, 2);
- }
-
- /* Value belongs to this node or to the left-hand subtree. */
+ bb = emit_case_nodes (bb, index, node->m_left,
+ default_prob, index_type, loc);
- probability
- = conditional_probability (prob, subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR,
- node->case_bb, probability,
- phi_mapping);
+ /* If the left-hand subtree fell through,
+ don't let it fall into the right-hand subtree. */
+ if (bb && m_default_bb)
+ emit_jump (bb, m_default_bb);
- bb = emit_case_nodes (bb, index, node->left, default_bb,
- default_label, default_prob, index_type,
- phi_mapping);
+ bb = emit_case_nodes (test_bb, index, node->m_right,
+ default_prob, index_type, loc);
}
-
else
{
/* Node has no children so we check low and high bounds to remove
redundant tests. Only one of the bounds can exist,
since otherwise this node is bounded--a case tested already. */
- bool high_bound = node_has_high_bound (node, index_type);
- bool low_bound = node_has_low_bound (node, index_type);
-
- if (!high_bound && low_bound)
- {
- probability
- = conditional_probability (default_prob,
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
- default_bb, probability,
- phi_mapping);
- }
+ tree lhs, rhs;
+ generate_range_test (bb, index, node->m_c->get_low (),
+ node->m_c->get_high (), &lhs, &rhs);
+ p = default_prob / (node->m_c->m_subtree_prob + default_prob);
- else if (!low_bound && high_bound)
- {
- probability
- = conditional_probability (default_prob,
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR,
- default_bb, probability,
- phi_mapping);
- }
- else if (!low_bound && !high_bound)
- {
- tree lhs, rhs;
- generate_range_test (bb, index, node->low, node->high,
- &lhs, &rhs);
- probability
- = conditional_probability (default_prob,
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR,
- default_bb, probability,
- phi_mapping);
- }
+ bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR,
+ m_default_bb, p, loc);
- emit_jump (bb, node->case_bb, phi_mapping);
+ emit_jump (bb, node->m_c->m_case_bb);
return NULL;
}
}
return bb;
}
-/* Search the parent sections of the case node tree
- to see if a test for the lower bound of NODE would be redundant.
- INDEX_TYPE is the type of the index expression.
+/* The main function of the pass scans statements for switches and invokes
+ process_switch on them. */
- The instructions to generate the case decision tree are
- output in the same order as nodes are processed so it is
- known that if a parent node checks the range of the current
- node minus one that the current node is bounded at its lower
- span. Thus the test would be redundant. */
+namespace {
-static bool
-node_has_low_bound (case_node_ptr node, tree index_type)
+const pass_data pass_data_convert_switch =
{
- tree low_minus_one;
- case_node_ptr pnode;
+ GIMPLE_PASS, /* type */
+ "switchconv", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_TREE_SWITCH_CONVERSION, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_update_ssa, /* todo_flags_finish */
+};
- /* If the lower bound of this node is the lowest value in the index type,
- we need not test it. */
+class pass_convert_switch : public gimple_opt_pass
+{
+public:
+ pass_convert_switch (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_convert_switch, ctxt)
+ {}
- if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
- return true;
+ /* opt_pass methods: */
+ virtual bool gate (function *) { return flag_tree_switch_conversion != 0; }
+ virtual unsigned int execute (function *);
- /* If this node has a left branch, the value at the left must be less
- than that at this node, so it cannot be bounded at the bottom and
- we need not bother testing any further. */
+}; // class pass_convert_switch
- if (node->left)
- return false;
+unsigned int
+pass_convert_switch::execute (function *fun)
+{
+ basic_block bb;
+ bool cfg_altered = false;
+
+ FOR_EACH_BB_FN (bb, fun)
+ {
+ gimple *stmt = last_stmt (bb);
+ if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
+ {
+ if (dump_file)
+ {
+ expanded_location loc = expand_location (gimple_location (stmt));
- low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low), node->low,
- build_int_cst (TREE_TYPE (node->low), 1));
+ fprintf (dump_file, "beginning to process the following "
+ "SWITCH statement (%s:%d) : ------- \n",
+ loc.file, loc.line);
+ print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+ putc ('\n', dump_file);
+ }
- /* If the subtraction above overflowed, we can't verify anything.
- Otherwise, look for a parent that tests our value - 1. */
+ switch_conversion sconv;
+ sconv.expand (as_a <gswitch *> (stmt));
+ cfg_altered |= sconv.m_cfg_altered;
+ if (!sconv.m_reason)
+ {
+ if (dump_file)
+ {
+ fputs ("Switch converted\n", dump_file);
+ fputs ("--------------------------------\n", dump_file);
+ }
- if (!tree_int_cst_lt (low_minus_one, node->low))
- return false;
+ /* 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
+ {
+ if (dump_file)
+ {
+ fputs ("Bailing out - ", dump_file);
+ fputs (sconv.m_reason, dump_file);
+ fputs ("\n--------------------------------\n", dump_file);
+ }
+ }
+ }
+ }
- for (pnode = node->parent; pnode; pnode = pnode->parent)
- if (tree_int_cst_equal (low_minus_one, pnode->high))
- return true;
+ return cfg_altered ? TODO_cleanup_cfg : 0;;
+}
+
+} // anon namespace
- return false;
+gimple_opt_pass *
+make_pass_convert_switch (gcc::context *ctxt)
+{
+ return new pass_convert_switch (ctxt);
}
-/* Search the parent sections of the case node tree
- to see if a test for the upper bound of NODE would be redundant.
- INDEX_TYPE is the type of the index expression.
+/* The main function of the pass scans statements for switches and invokes
+ process_switch on them. */
- The instructions to generate the case decision tree are
- output in the same order as nodes are processed so it is
- known that if a parent node checks the range of the current
- node plus one that the current node is bounded at its upper
- span. Thus the test would be redundant. */
+namespace {
-static bool
-node_has_high_bound (case_node_ptr node, tree index_type)
+template <bool O0> class pass_lower_switch: public gimple_opt_pass
{
- tree high_plus_one;
- case_node_ptr pnode;
+public:
+ pass_lower_switch (gcc::context *ctxt) : gimple_opt_pass (data, ctxt) {}
+
+ static const pass_data data;
+ opt_pass *
+ clone ()
+ {
+ return new pass_lower_switch<O0> (m_ctxt);
+ }
- /* If there is no upper bound, obviously no test is needed. */
+ virtual bool
+ gate (function *)
+ {
+ return !O0 || !optimize;
+ }
- if (TYPE_MAX_VALUE (index_type) == NULL)
- return true;
+ virtual unsigned int execute (function *fun);
+}; // class pass_lower_switch
- /* If the upper bound of this node is the highest value in the type
- of the index expression, we need not test against it. */
+template <bool O0>
+const pass_data pass_lower_switch<O0>::data = {
+ GIMPLE_PASS, /* type */
+ O0 ? "switchlower_O0" : "switchlower", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_TREE_SWITCH_LOWERING, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */
+};
- if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
- return true;
+template <bool O0>
+unsigned int
+pass_lower_switch<O0>::execute (function *fun)
+{
+ basic_block bb;
+ bool expanded = false;
- /* If this node has a right branch, the value at the right must be greater
- than that at this node, so it cannot be bounded at the top and
- we need not bother testing any further. */
+ auto_vec<gimple *> switch_statements;
+ switch_statements.create (1);
- if (node->right)
- return false;
+ FOR_EACH_BB_FN (bb, fun)
+ {
+ gimple *stmt = last_stmt (bb);
+ gswitch *swtch;
+ if (stmt && (swtch = dyn_cast<gswitch *> (stmt)))
+ {
+ if (!O0)
+ group_case_labels_stmt (swtch);
+ switch_statements.safe_push (swtch);
+ }
+ }
- high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high), node->high,
- build_int_cst (TREE_TYPE (node->high), 1));
+ for (unsigned i = 0; i < switch_statements.length (); i++)
+ {
+ gimple *stmt = switch_statements[i];
+ if (dump_file)
+ {
+ expanded_location loc = expand_location (gimple_location (stmt));
- /* If the addition above overflowed, we can't verify anything.
- Otherwise, look for a parent that tests our value + 1. */
+ fprintf (dump_file, "beginning to process the following "
+ "SWITCH statement (%s:%d) : ------- \n",
+ loc.file, loc.line);
+ print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+ putc ('\n', dump_file);
+ }
- if (!tree_int_cst_lt (node->high, high_plus_one))
- return false;
+ gswitch *swtch = dyn_cast<gswitch *> (stmt);
+ if (swtch)
+ {
+ switch_decision_tree dt (swtch);
+ expanded |= dt.analyze_switch_statement ();
+ }
+ }
- for (pnode = node->parent; pnode; pnode = pnode->parent)
- if (tree_int_cst_equal (high_plus_one, pnode->low))
- return true;
+ if (expanded)
+ {
+ free_dominance_info (CDI_DOMINATORS);
+ free_dominance_info (CDI_POST_DOMINATORS);
+ mark_virtual_operands_for_renaming (cfun);
+ }
- return false;
+ return 0;
}
-/* Search the parent sections of the
- case node tree to see if both tests for the upper and lower
- bounds of NODE would be redundant. */
+} // anon namespace
-static bool
-node_is_bounded (case_node_ptr node, tree index_type)
+gimple_opt_pass *
+make_pass_lower_switch_O0 (gcc::context *ctxt)
+{
+ return new pass_lower_switch<true> (ctxt);
+}
+gimple_opt_pass *
+make_pass_lower_switch (gcc::context *ctxt)
{
- return (node_has_low_bound (node, index_type)
- && node_has_high_bound (node, index_type));
+ return new pass_lower_switch<false> (ctxt);
}
+
+
projects / gcc.git / blobdiff