#include <tree-switch-conversion.h>
Public Member Functions | |
bit_test_cluster (vec< cluster * > &clusters, unsigned start, unsigned end, bool handles_entire_switch) | |
cluster_type | get_type () final override |
void | emit (tree index_expr, tree index_type, tree default_label_expr, basic_block default_bb, location_t loc) final override |
tree | get_low () final override |
tree | get_high () final override |
void | debug () final override |
void | dump (FILE *f, bool details=false) final override |
virtual bool | is_single_value_p () |
Static Public Member Functions | |
static vec< cluster * > | find_bit_tests_fast (vec< cluster * > &clusters) |
static vec< cluster * > | find_bit_tests_slow (vec< cluster * > &clusters) |
static vec< cluster * > | find_bit_tests (vec< cluster * > &clusters, int max_c) |
static bool | can_be_handled (unsigned HOST_WIDE_INT range, unsigned uniq) |
static bool | is_beneficial (unsigned count, unsigned uniq) |
static basic_block | hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip, tree cond, basic_block case_bb, profile_probability prob, location_t) |
static bool | is_enabled (void) |
static unsigned HOST_WIDE_INT | get_range (tree low, tree high) |
Static Public Attributes | |
static const int | m_max_case_bit_tests = 3 |
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-branch insns in some cases, e.g. we can implement: if ((x==4) || (x==6) || (x==9) || (x==11)) as a single bit test: if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11))) This transformation is only applied if the number of case targets is small, if CST constains at least 3 bits, and "1 << x" is cheap. The bit tests are performed in "word_mode". The following example shows the code the transformation generates: int bar(int x) { switch (x) { case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': case 'A': case 'B': case 'C': case 'D': case 'E': case 'F': return 1; } return 0; } ==> bar (int x) { tmp1 = x - 48; if (tmp1 > (70 - 48)) goto L2; tmp2 = 1 << tmp1; tmp3 = 0b11111100000001111111111; if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2; L1: return 1; L2: return 0; } TODO: There are still some improvements to this transformation that could be implemented: * A narrower mode than word_mode could be used if that is cheaper, e.g. for x86_64 where a narrower-mode shift may result in smaller code. * The compounded constant could be shifted rather than the one. The test would be either on the sign bit or on the least significant bit, depending on the direction of the shift. On some machines, the test for the branch would be free if the bit to test is already set by the shift operation. This transformation was contributed by Roger Sayle, see this e-mail: http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html
|
inline |
References end(), tree_switch_conversion::group_cluster::group_cluster(), and m_handles_entire_switch.
Referenced by find_bit_tests().
|
static |
Return true when RANGE of case values with UNIQ labels can build a bit test.
References GET_MODE_BITSIZE(), m_max_case_bit_tests, and word_mode.
Referenced by tree_switch_conversion::switch_conversion::expand(), find_bit_tests(), and find_bit_tests_slow().
|
inlinefinaloverridevirtualinherited |
Implements tree_switch_conversion::cluster.
Dump content of a cluster.
Implements tree_switch_conversion::cluster.
References get_high(), get_low(), tree_switch_conversion::cluster::get_range(), tree_switch_conversion::cluster::get_type(), HOST_WIDE_INT_PRINT_DEC, i, tree_switch_conversion::JUMP_TABLE, m_cases, PRINT_CASE, and sc.
Referenced by debug().
|
finaloverridevirtual |
Expand a switch statement by a short sequence of bit-wise comparisons. "switch(x)" is effectively converted into "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are integer constants. INDEX_EXPR is the value being switched on. MINVAL is the lowest case value of in the case nodes, and RANGE is highest value minus MINVAL. MINVAL and RANGE are not guaranteed to be of the same type as INDEX_EXPR (the gimplifier doesn't change the type of case label values, and MINVAL and RANGE are derived from those values). MAXVAL is MINVAL + RANGE. There *MUST* be max_case_bit_tests or less unique case node targets.
Implements tree_switch_conversion::cluster.
References profile_probability::always(), tree_switch_conversion::case_bit_test::bits, boolean_type_node, build_zero_cst(), cfun, tree_switch_conversion::case_bit_test::cmp(), compare_tree_int(), count, EDGE_COUNT, fold_build2, fold_build2_loc(), fold_convert, fold_convert_loc(), force_gimple_operand_gsi(), gcc_assert, gcc_checking_assert, GEN_INT, gen_raw_REG(), tree_switch_conversion::group_cluster::get_high(), tree_switch_conversion::simple_cluster::get_high(), tree_switch_conversion::group_cluster::get_low(), tree_switch_conversion::simple_cluster::get_low(), tree_switch_conversion::cluster::get_range(), get_range_query(), gimple_build_assign(), gsi_bb(), gsi_insert_before(), gsi_last_bb(), GSI_SAME_STMT, wi::gt_p(), hoist_edge_and_branch_if_true(), i, immed_wide_int_const(), profile_probability::initialized_p(), int_const_binop(), integer_one_node, integer_zero_node, tree_switch_conversion::case_bit_test::label, wi::leu_p(), wi::lrshift(), wi::lshift(), wi::lt_p(), tree_switch_conversion::cluster::m_case_bb, tree_switch_conversion::cluster::m_case_label_expr, tree_switch_conversion::group_cluster::m_cases, tree_switch_conversion::cluster::m_default_prob, m_handles_entire_switch, m_max_case_bit_tests, tree_switch_conversion::cluster::m_prob, tree_switch_conversion::cluster::m_subtree_prob, make_edge(), make_ssa_name(), tree_switch_conversion::case_bit_test::mask, profile_probability::never(), NULL_TREE, wi::one(), optimize_insn_for_speed_p(), tree_switch_conversion::case_bit_test::prob, qsort, r, range_check_type(), set_src_cost(), tree_switch_conversion::case_bit_test::target_bb, wi::to_wide(), TREE_CODE, tree_to_uhwi(), TREE_TYPE, lang_hooks_for_types::type_for_mode, TYPE_PRECISION, TYPE_SIGN, lang_hooks::types, update_stmt(), wide_int_to_tree(), word_mode, and wi::zero().
Find bit tests of given CLUSTERS, where all members of the vector are of type simple_cluster. MAX_C is the approx max number of cases per label. New clusters are returned.
References bit_test_cluster(), can_be_handled(), end(), gcc_checking_assert, tree_switch_conversion::group_cluster::get_high(), tree_switch_conversion::group_cluster::get_low(), GET_MODE_BITSIZE(), tree_switch_conversion::cluster::get_range(), i, INT_MAX, is_beneficial(), is_enabled(), m_max_case_bit_tests, sc, and word_mode.
Referenced by tree_switch_conversion::switch_decision_tree::analyze_switch_statement(), find_bit_tests_slow(), and if_chain::is_beneficial().
|
static |
|
static |
References can_be_handled(), count, find_bit_tests(), hoist_edge_and_branch_if_true(), and is_beneficial().
|
inlinefinaloverridevirtualinherited |
Implements tree_switch_conversion::cluster.
References final(), and m_cases.
Referenced by tree_switch_conversion::jump_table_cluster::can_be_handled(), dump(), tree_switch_conversion::bit_test_cluster::emit(), tree_switch_conversion::jump_table_cluster::emit(), and tree_switch_conversion::bit_test_cluster::find_bit_tests().
|
inlinefinaloverridevirtualinherited |
Implements tree_switch_conversion::cluster.
References final(), and m_cases.
Referenced by tree_switch_conversion::jump_table_cluster::can_be_handled(), dump(), tree_switch_conversion::bit_test_cluster::emit(), tree_switch_conversion::jump_table_cluster::emit(), and tree_switch_conversion::bit_test_cluster::find_bit_tests().
|
inlinestaticinherited |
References wi::fits_uhwi_p(), wi::neg_p(), generic_wide_int< storage >::to_uhwi(), wi::to_wide(), TREE_TYPE, and TYPE_SIGN.
Referenced by tree_switch_conversion::jump_table_cluster::can_be_handled(), tree_switch_conversion::group_cluster::dump(), tree_switch_conversion::bit_test_cluster::emit(), tree_switch_conversion::jump_table_cluster::emit(), and tree_switch_conversion::bit_test_cluster::find_bit_tests().
|
inlinefinaloverridevirtual |
Implements tree_switch_conversion::cluster.
References tree_switch_conversion::BIT_TEST, and final().
|
static |
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.
References basic_block_def::count, force_gimple_operand_gsi(), gcc_assert, gimple_build_cond_from_tree(), gimple_set_location(), gsi_bb(), gsi_insert_before(), GSI_SAME_STMT, make_edge(), NULL, NULL_TREE, redirect_edge_pred(), and split_block().
Referenced by emit(), and find_bit_tests_slow().
|
static |
Return true when COUNT of cases of UNIQ labels is beneficial for bit test transformation.
References count.
Referenced by tree_switch_conversion::switch_conversion::expand(), find_bit_tests(), and find_bit_tests_slow().
|
inlinestatic |
Referenced by find_bit_tests().
|
inlinevirtualinherited |
Reimplemented in tree_switch_conversion::simple_cluster.
Referenced by tree_switch_conversion::switch_decision_tree::emit_case_nodes().
|
inherited |
|
inherited |
|
inherited |
|
inherited |
bool tree_switch_conversion::bit_test_cluster::m_handles_entire_switch |
Referenced by bit_test_cluster(), and emit().
|
static |
Referenced by can_be_handled(), emit(), and find_bit_tests().
|
inherited |
Referenced by tree_switch_conversion::switch_decision_tree::balance_case_nodes(), cluster(), tree_switch_conversion::switch_decision_tree::dump_case_nodes(), tree_switch_conversion::bit_test_cluster::emit(), tree_switch_conversion::switch_decision_tree::emit_case_nodes(), and tree_switch_conversion::group_cluster::group_cluster().
|
inherited |
Referenced by tree_switch_conversion::switch_decision_tree::balance_case_nodes(), cluster(), tree_switch_conversion::switch_decision_tree::dump_case_nodes(), tree_switch_conversion::bit_test_cluster::emit(), tree_switch_conversion::switch_decision_tree::emit_case_nodes(), and tree_switch_conversion::group_cluster::group_cluster().