GCC Middle and Back End API Reference
|
#include <tree-switch-conversion.h>
Public Member Functions | |
switch_conversion () | |
~switch_conversion () | |
void | expand (gswitch *swtch) |
void | collect (gswitch *swtch) |
bool | is_exp_index_transform_viable (gswitch *swtch) |
void | exp_index_transform (gswitch *swtch) |
bool | check_range () |
bool | check_all_empty_except_final () |
bool | check_final_bb () |
void | create_temp_arrays () |
void | gather_default_values (tree default_case) |
void | build_constructors () |
bool | contains_linear_function_p (vec< constructor_elt, va_gc > *vec, wide_int *coeff_a, wide_int *coeff_b) |
tree | array_value_type (tree type, int num) |
void | build_one_array (int num, tree arr_index_type, gphi *phi, tree tidx) |
void | build_arrays () |
gassign * | gen_def_assigns (gimple_stmt_iterator *gsi) |
void | prune_bbs (basic_block bbd, basic_block final, basic_block default_bb) |
void | fix_phi_nodes (edge e1f, edge e2f, basic_block bbf) |
void | gen_inbound_check () |
The main structure of the pass.
switch_conversion::switch_conversion | ( | ) |
Constructor.
switch_conversion::~switch_conversion | ( | ) |
Destructor.
References m_constructors, and m_default_values.
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.
References FOR_EACH_VEC_SAFE_ELT, GET_MODE_BITSIZE(), GET_MODE_SIZE(), GET_MODE_WIDER_MODE(), get_narrowest_mode(), gimple_bb(), HOST_BITS_PER_WIDE_INT, i, INTEGRAL_TYPE_P, m_constructors, m_switch, MAX_FIXED_MODE_SIZE, optimize_bb_for_size_p(), SCALAR_INT_TYPE_MODE, wi::sext(), wi::to_wide(), TREE_CODE, type(), lang_hooks_for_types::type_for_mode, TYPE_MAIN_VARIANT, TYPE_MODE, TYPE_PRECISION, TYPE_UNSIGNED, lang_hooks::types, constructor_elt::value, vec_safe_length(), and wi::zext().
Referenced by build_one_array().
void switch_conversion::build_arrays | ( | ) |
Builds and initializes static arrays initialized with values gathered from the switch statement. Also creates statements that load values from them.
References build_index_type(), build_one_array(), fold_build2_loc(), fold_convert, fold_convert_loc(), FOR_EACH_EDGE, force_gimple_operand_gsi(), gcc_assert, gimple_build_assign(), gimple_location(), gimple_phi_result(), gsi_end_p(), gsi_for_stmt(), gsi_insert_before(), gsi_next(), GSI_SAME_STMT, gsi_start_phis(), i, m_arr_ref_first, m_default_bb, m_default_case_nonstandard, m_final_bb, m_index_expr, m_range_min, m_range_size, m_switch, m_switch_bb, m_target_vop, make_ssa_name(), MAX_FIXED_MODE_SIZE, NULL, gphi_iterator::phi(), PHI_ARG_DEF_FROM_EDGE, single_succ_edge(), sizetype, basic_block_def::succs, TREE_CODE, TREE_TYPE, lang_hooks_for_types::type_for_mode, TYPE_MODE, TYPE_PRECISION, lang_hooks::types, unsigned_type_for(), update_stmt(), and virtual_operand_p().
Referenced by expand().
void switch_conversion::build_constructors | ( | ) |
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.
References build_int_cst(), CASE_HIGH, CASE_LABEL, CASE_LOW, cfun, find_edge(), fold_convert, gcc_assert, gimple_phi_result(), gimple_switch_label(), gimple_switch_num_labels(), gsi_end_p(), gsi_next(), gsi_start_phis(), i, constructor_elt::index, int_const_binop(), label_to_block(), m_constructors, m_default_values, m_final_bb, m_phi_count, m_range_min, m_switch, m_switch_bb, gphi_iterator::phi(), PHI_ARG_DEF_FROM_EDGE, single_succ_edge(), sizetype, tree_int_cst_equal(), tree_int_cst_lt(), TREE_TYPE, TYPE_PRECISION, unshare_expr_without_location(), constructor_elt::value, and virtual_operand_p().
Referenced by expand().
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.
References array_value_type(), build4(), build_array_type(), build_constructor(), build_decl(), cfun, contains_linear_function_p(), copy_ssa_name(), create_tmp_var_name(), DECL_ARTIFICIAL, DECL_ATTRIBUTES, DECL_IGNORED_P, DECL_INITIAL, DECL_NAME, dump_file, varpool_node::finalize_decl(), fold_convert, FOR_EACH_VEC_SAFE_ELT, force_gimple_operand_gsi(), gcc_assert, get_identifier(), gimple_build(), gimple_build_assign(), gimple_convert(), gimple_location(), gsi_for_stmt(), gsi_insert_before(), gsi_insert_seq_before(), GSI_SAME_STMT, i, m_arr_ref_last, m_constructors, m_default_values, m_index_expr, m_switch, m_target_inbound_names, NULL, NULL_TREE, offloading_function_p(), PHI_RESULT, PRId64, range_check_type(), generic_wide_int< storage >::to_shwi(), generic_wide_int< storage >::to_uhwi(), tree_cons(), TREE_CONSTANT, TREE_READONLY, TREE_STATIC, TREE_TYPE, type(), update_stmt(), constructor_elt::value, and wide_int_to_tree().
Referenced by build_arrays().
bool switch_conversion::check_all_empty_except_final | ( | ) |
Checks whether all but the final BB basic blocks are empty.
References empty_block_p(), find_edge(), FOR_EACH_EDGE, m_contiguous_range, m_default_bb, m_default_case_nonstandard, m_final_bb, m_reason, m_switch_bb, and basic_block_def::succs.
Referenced by expand().
bool switch_conversion::check_final_bb | ( | ) |
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.
References cfun, empty_block_p(), gimple_phi_arg_def(), gimple_phi_arg_edge(), gimple_phi_num_args(), gimple_phi_result(), gimple_switch_label_bb(), gimple_switch_num_labels(), gsi_end_p(), gsi_next(), gsi_start_phis(), i, initializer_constant_valid_p(), is_gimple_ip_invariant(), m_contiguous_range, m_default_bb, m_default_case_nonstandard, m_final_bb, m_phi_count, m_reason, m_switch, m_switch_bb, NULL, null_pointer_node, NULL_TREE, gphi_iterator::phi(), single_pred(), single_pred_p(), TREE_TYPE, and virtual_operand_p().
Referenced by expand().
bool switch_conversion::check_range | ( | ) |
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.
References gcc_assert, m_count, m_range_size, m_reason, tree_fits_uhwi_p(), and tree_to_uhwi().
Referenced by expand().
void switch_conversion::collect | ( | gswitch * | swtch | ) |
Collection information about SWTCH statement.
References CASE_HIGH, CASE_LOW, cfun, EDGE_COUNT, empty_block_p(), FOR_EACH_EDGE, gimple_bb(), gimple_switch_default_edge(), gimple_switch_edge(), gimple_switch_index(), gimple_switch_label(), gimple_switch_num_labels(), i, int_const_binop(), last, m_contiguous_range, m_count, m_default_bb, m_default_case_nonstandard, m_default_prob, m_final_bb, m_index_expr, m_range_max, m_range_min, m_range_size, m_switch, m_switch_bb, m_uniq, NULL, NULL_TREE, phi_alternatives_equal(), single_pred_p(), single_succ(), single_succ_edge(), single_succ_p(), basic_block_def::succs, wi::to_wide(), and tree_int_cst_equal().
Referenced by expand().
bool switch_conversion::contains_linear_function_p | ( | vec< constructor_elt, va_gc > * | vec, |
wide_int * | coeff_a, | ||
wide_int * | coeff_b ) |
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.
References a, b, FOR_EACH_VEC_SAFE_ELT, wide_int_storage::from(), gcc_assert, i, m_range_min, wi::to_wide(), TREE_CODE, TREE_TYPE, TYPE_PRECISION, TYPE_SIGN, and constructor_elt::value.
Referenced by build_one_array().
void switch_conversion::create_temp_arrays | ( | ) |
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.
References i, m_constructors, m_default_values, m_phi_count, m_range_size, m_target_inbound_names, m_target_outbound_names, tree_to_uhwi(), and vec_alloc().
Referenced by expand().
void switch_conversion::exp_index_transform | ( | gswitch * | swtch | ) |
Perform the "exponential index transform". Assume that cases of SWTCH are powers of 2. The transformation replaces the cases by their exponents (2^k -> k). It also inserts a statement that computes the exponent of the original index variable (basically taking the logarithm) and then sets the result as the new index variable. The transformation also inserts a conditional statement checking that the incoming original index variable is a power of 2 with the false edge leading to the default case. The exponential index transform shrinks the range of case numbers which helps switch conversion convert switches it otherwise could not. Consider for example: switch (i) { case (1 << 0): return 0; case (1 << 1): return 1; case (1 << 2): return 2; ... case (1 << 30): return 30; default: return 31; } First, exponential index transform gets applied. Since each case becomes case x: return x;, the rest of switch conversion is then able to get rid of the switch statement. if (i is power of 2) return log2 (i); else return 31;
References wi::add(), add_phi_arg(), boolean_false_node, build_int_cst(), CASE_LOW, CDI_DOMINATORS, cfun, dom_info_available_p(), dump_file, wi::eq_p(), profile_probability::even(), find_edge(), basic_block_def::flags, FOR_EACH_EDGE, gen_log2(), gen_pow2p(), gimple_bb(), gimple_build_cond(), gimple_phi_arg_location_from_edge(), gimple_switch_default_bb(), gimple_switch_index(), gimple_switch_label(), gimple_switch_num_labels(), gimple_switch_set_index(), gsi_after_labels(), gsi_end_p(), gsi_for_stmt(), gsi_insert_after(), gsi_insert_seq_after(), gsi_insert_seq_before(), gsi_last_bb(), GSI_LAST_NEW_STMT, GSI_NEW_STMT, gsi_next(), gsi_prev(), GSI_SAME_STMT, gsi_start_phis(), gsi_stmt(), i, int_const_binop(), iterate_fix_dominators(), m_cfg_altered, m_contiguous_range, m_exp_index_transform_applied, m_exp_index_transform_log2_type, m_final_bb, m_index_expr, m_range_max, m_range_min, m_range_size, m_switch_bb, make_edge(), NULL, num_labels, PHI_ARG_DEF_FROM_EDGE, redirect_immediate_dominators(), set_immediate_dominator(), split_block(), basic_block_def::succs, wi::to_wide(), tree_log2(), TREE_TYPE, UNKNOWN_LOCATION, and update_stmt().
Referenced by expand().
void switch_conversion::expand | ( | gswitch * | swtch | ) |
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.
References build_arrays(), build_constructors(), tree_switch_conversion::bit_test_cluster::can_be_handled(), check_all_empty_except_final(), check_final_bb(), check_range(), collect(), create_temp_arrays(), error_mark_node, exp_index_transform(), gather_default_values(), gcc_assert, gcc_checking_assert, gen_inbound_check(), gimple_switch_default_label(), gimple_switch_label(), gimple_switch_num_labels(), group_case_labels_stmt(), tree_switch_conversion::bit_test_cluster::is_beneficial(), is_exp_index_transform_viable(), m_cfg_altered, m_count, m_default_case_nonstandard, m_final_bb, m_index_expr, m_range_size, m_reason, m_uniq, tree_fits_uhwi_p(), tree_to_uhwi(), and TREE_TYPE.
void switch_conversion::fix_phi_nodes | ( | edge | e1f, |
edge | e2f, | ||
basic_block | bbf ) |
Add values to phi nodes in final_bb for the two new edges. E1F is the edge from the basic block loading values from an array and E2F from the basic block loading default values. BBF is the last switch basic block (see the bbf description in the comment below).
References add_phi_arg(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), i, m_default_case_nonstandard, m_target_inbound_names, m_target_outbound_names, m_target_vop, gphi_iterator::phi(), UNKNOWN_LOCATION, and virtual_operand_p().
Referenced by gen_inbound_check().
void switch_conversion::gather_default_values | ( | tree | default_case | ) |
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.
References CASE_LABEL, CASE_LOW, cfun, find_edge(), gcc_assert, gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), i, label_to_block(), m_default_case_nonstandard, m_default_values, m_final_bb, m_switch_bb, NULL_TREE, gphi_iterator::phi(), PHI_ARG_DEF_FROM_EDGE, single_succ_edge(), and virtual_operand_p().
Referenced by expand().
gassign * switch_conversion::gen_def_assigns | ( | gimple_stmt_iterator * | gsi | ) |
Generates and appropriately inserts loads of default values at the position given by GSI. Returns the last inserted statement.
References copy_ssa_name(), gimple_build_assign(), gsi_insert_before(), GSI_SAME_STMT, i, m_default_values, m_phi_count, m_target_inbound_names, m_target_outbound_names, NULL, and update_stmt().
Referenced by gen_inbound_check().
void switch_conversion::gen_inbound_check | ( | ) |
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.
References add_phi_arg(), profile_probability::always(), bbd, CDI_DOMINATORS, basic_block_def::count, create_artificial_label(), dom_info_available_p(), find_edge(), fix_phi_nodes(), basic_block_def::flags, fold_convert_loc(), gcc_assert, gen_def_assigns(), get_immediate_dominator(), gimple_assign_lhs(), gimple_bb(), gimple_build_cond(), gimple_build_label(), gimple_location(), gimple_phi_arg_location_from_edge(), gsi_end_p(), gsi_for_stmt(), gsi_insert_before(), gsi_next(), GSI_SAME_STMT, gsi_start_bb(), gsi_start_phis(), profile_probability::invert(), iterate_fix_dominators(), m_arr_ref_first, m_arr_ref_last, m_default_bb, m_default_case_nonstandard, m_default_prob, m_default_values, m_exp_index_transform_applied, m_final_bb, m_range_size, m_switch, make_edge(), NULL, NULL_TREE, PHI_ARG_DEF_FROM_EDGE, prune_bbs(), redirect_immediate_dominators(), remove_edge(), set_immediate_dominator(), split_block(), TREE_TYPE, UNKNOWN_LOCATION, and update_stmt().
Referenced by expand().
Check that the "exponential index transform" can be applied to this switch. See comment of the exp_index_transform function for details about this transformation. We want: - This form of the switch is more efficient - Cases are powers of 2 Expects that SWTCH has at least one case.
References bb_optimization_type(), can_log2(), CASE_HIGH, CASE_LOW, dump_file, wi::exact_log2(), wi::ge_p(), gimple_bb(), gimple_switch_index(), gimple_switch_label(), gimple_switch_num_labels(), i, m_exp_index_transform_log2_type, num_labels, wi::to_wide(), TREE_TYPE, and TYPE_SIGN.
Referenced by expand().
void switch_conversion::prune_bbs | ( | basic_block | bbd, |
basic_block | final, | ||
basic_block | default_bb ) |
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).
References bbd, delete_basic_block(), ei_safe_edge(), ei_start, and remove_edge().
Referenced by gen_inbound_check().
gimple* tree_switch_conversion::switch_conversion::m_arr_ref_first |
Referenced by build_arrays(), and gen_inbound_check().
gimple* tree_switch_conversion::switch_conversion::m_arr_ref_last |
Referenced by build_one_array(), and gen_inbound_check().
bool tree_switch_conversion::switch_conversion::m_cfg_altered |
Referenced by exp_index_transform(), and expand().
vec<constructor_elt, va_gc>** tree_switch_conversion::switch_conversion::m_constructors |
Referenced by array_value_type(), build_constructors(), build_one_array(), create_temp_arrays(), and ~switch_conversion().
bool tree_switch_conversion::switch_conversion::m_contiguous_range |
Referenced by check_all_empty_except_final(), check_final_bb(), collect(), and exp_index_transform().
unsigned int tree_switch_conversion::switch_conversion::m_count |
Referenced by check_range(), collect(), and expand().
basic_block tree_switch_conversion::switch_conversion::m_default_bb |
Referenced by build_arrays(), check_all_empty_except_final(), check_final_bb(), collect(), and gen_inbound_check().
bool tree_switch_conversion::switch_conversion::m_default_case_nonstandard |
profile_probability tree_switch_conversion::switch_conversion::m_default_prob |
Referenced by collect(), and gen_inbound_check().
tree* tree_switch_conversion::switch_conversion::m_default_values |
bool tree_switch_conversion::switch_conversion::m_exp_index_transform_applied |
Referenced by exp_index_transform(), and gen_inbound_check().
tree tree_switch_conversion::switch_conversion::m_exp_index_transform_log2_type |
Referenced by exp_index_transform(), and is_exp_index_transform_viable().
basic_block tree_switch_conversion::switch_conversion::m_final_bb |
tree tree_switch_conversion::switch_conversion::m_index_expr |
Referenced by build_arrays(), build_one_array(), collect(), exp_index_transform(), and expand().
int tree_switch_conversion::switch_conversion::m_phi_count |
Referenced by build_constructors(), check_final_bb(), create_temp_arrays(), and gen_def_assigns().
tree tree_switch_conversion::switch_conversion::m_range_max |
Referenced by collect(), and exp_index_transform().
tree tree_switch_conversion::switch_conversion::m_range_min |
Referenced by build_arrays(), build_constructors(), collect(), contains_linear_function_p(), and exp_index_transform().
tree tree_switch_conversion::switch_conversion::m_range_size |
Referenced by build_arrays(), check_range(), collect(), create_temp_arrays(), exp_index_transform(), expand(), and gen_inbound_check().
const char* tree_switch_conversion::switch_conversion::m_reason |
Referenced by check_all_empty_except_final(), check_final_bb(), check_range(), and expand().
gswitch* tree_switch_conversion::switch_conversion::m_switch |
Referenced by array_value_type(), build_arrays(), build_constructors(), build_one_array(), check_final_bb(), collect(), and gen_inbound_check().
basic_block tree_switch_conversion::switch_conversion::m_switch_bb |
tree* tree_switch_conversion::switch_conversion::m_target_inbound_names |
Referenced by build_one_array(), create_temp_arrays(), fix_phi_nodes(), and gen_def_assigns().
tree* tree_switch_conversion::switch_conversion::m_target_outbound_names |
Referenced by create_temp_arrays(), fix_phi_nodes(), and gen_def_assigns().
tree tree_switch_conversion::switch_conversion::m_target_vop |
Referenced by build_arrays(), and fix_phi_nodes().
unsigned int tree_switch_conversion::switch_conversion::m_uniq |