#include "config.h"#include "system.h"#include "coretypes.h"#include "tm.h"#include "line-map.h"#include "params.h"#include "flags.h"#include "tree.h"#include "basic-block.h"
Data Structures | |
| struct | case_bit_test |
| struct | switch_conv_info |
Function Documentation
|
static |
Return type which should be used for array elements, either TYPE, or for integral type some smaller integral type that can still hold all the constants.
References switch_conv_info::constructors, HOST_BITS_PER_WIDE_INT, len, optimize_bb_for_size_p(), double_int::sext(), type(), lang_hooks_for_types::type_for_mode, lang_hooks::types, constructor_elt_d::value, vec_safe_length(), and double_int::zext().
Referenced by build_one_array().
|
static |
Builds and initializes static arrays initialized with values gathered from the SWTCH switch statement. Also creates statements that load values from them.
References switch_conv_info::arr_ref_first, build_index_type(), build_one_array(), switch_conv_info::final_bb, fold_convert_loc(), force_gimple_operand_gsi(), gimple_location(), gsi_end_p(), gsi_for_stmt(), gsi_insert_before(), gsi_next(), GSI_SAME_STMT, gsi_start_phis(), gsi_stmt(), switch_conv_info::index_expr, make_ssa_name(), switch_conv_info::range_min, switch_conv_info::range_size, lang_hooks_for_types::type_for_mode, lang_hooks::types, and update_stmt().
Referenced by process_switch().
|
static |
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.
References switch_conv_info::constructors, switch_conv_info::default_values, switch_conv_info::final_bb, find_edge(), gimple_switch_label(), gimple_switch_num_labels(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), constructor_elt_d::index, int_const_binop(), switch_conv_info::phi_count, switch_conv_info::range_min, single_succ_edge(), switch_conv_info::switch_bb, tree_int_cst_equal(), tree_int_cst_lt(), unshare_expr_without_location(), and constructor_elt_d::value.
Referenced by process_switch().
|
static |
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 switch_conv_info::arr_ref_last, array_value_type(), build_array_type(), build_constructor(), constructor_contains_same_values_p(), switch_conv_info::constructors, copy_ssa_name(), create_tmp_var_name(), switch_conv_info::default_values, force_gimple_operand_gsi(), gimple_location(), gsi_for_stmt(), gsi_insert_before(), GSI_SAME_STMT, switch_conv_info::target_inbound_names, update_stmt(), constructor_elt_d::value, and varpool_finalize_decl().
Referenced by build_arrays().
|
static |
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...).
References case_bit_test::bits, edge_def::count, d1, d2, case_bit_test::label, and case_bit_test::target_edge.
Referenced by emit_case_bit_tests().
|
static |
Checks whether all but the FINAL_BB basic blocks are empty.
References edge_def::dest, empty_block_p(), switch_conv_info::final_bb, switch_conv_info::reason, basic_block_def::succs, and switch_conv_info::switch_bb.
Referenced by process_switch().
|
static |
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 switch_conv_info::final_bb, gimple_phi_arg_def(), gimple_phi_arg_edge(), gimple_phi_num_args(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), initializer_constant_valid_p(), is_gimple_ip_invariant(), switch_conv_info::phi_count, switch_conv_info::reason, single_pred(), single_pred_p(), edge_def::src, and switch_conv_info::switch_bb.
Referenced by process_switch().
|
static |
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.
References switch_conv_info::count, host_integerp(), HOST_WIDE_INT, switch_conv_info::range_size, switch_conv_info::reason, and tree_low_cst().
Referenced by process_switch().
|
static |
Collect information about GIMPLE_SWITCH statement SWTCH into INFO.
References count, edge_def::count, switch_conv_info::count, switch_conv_info::default_bb, switch_conv_info::default_count, switch_conv_info::default_prob, edge_def::dest, switch_conv_info::final_bb, find_edge(), gimple_bb(), gimple_switch_default_label(), gimple_switch_index(), gimple_switch_label(), gimple_switch_num_labels(), switch_conv_info::index_expr, int_const_binop(), memset(), switch_conv_info::other_count, edge_def::probability, switch_conv_info::range_max, switch_conv_info::range_min, switch_conv_info::range_size, single_pred_p(), single_succ(), single_succ_p(), basic_block_def::succs, switch_conv_info::switch_bb, tree_int_cst_equal(), and switch_conv_info::uniq.
Referenced by process_switch().
|
static |
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.
References OEP_ONLY_CONST, operand_equal_p(), and constructor_elt_d::value.
Referenced by build_one_array().
|
static |
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 switch_conv_info::constructors, switch_conv_info::default_values, switch_conv_info::phi_count, switch_conv_info::range_size, switch_conv_info::target_inbound_names, switch_conv_info::target_outbound_names, tree_low_cst(), and vec_alloc().
Referenced by process_switch().
|
static |
The main function of the pass scans statements for switches and invokes process_switch on them.
References CDI_POST_DOMINATORS, dump_file, expand_location(), free_dominance_info(), gimple_location(), last_stmt(), print_gimple_stmt(), and process_switch().
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).
There *MUST* be MAX_CASE_BIT_TESTS or less unique case
node targets.
References case_bit_test::bits, build_int_cst_wide(), case_bit_test_cmp(), CDI_DOMINATORS, count, edge_def::dest, dom_info_available_p(), find_edge(), force_gimple_operand_gsi(), get_dominated_by(), gimple_bb(), gimple_switch_default_label(), gimple_switch_label(), gimple_switch_num_labels(), gsi_bb(), gsi_insert_before(), gsi_last_bb(), gsi_remove(), GSI_SAME_STMT, case_bit_test::hi, hoist_edge_and_branch_if_true(), HOST_BITS_PER_INT, HOST_BITS_PER_WIDE_INT, HOST_WIDE_INT, int_const_binop(), iterate_fix_dominators(), case_bit_test::label, case_bit_test::lo, make_edge(), make_ssa_name(), memset(), set_immediate_dominator(), single_pred_p(), split_edge(), case_bit_test::target_edge, tree_low_cst(), lang_hooks_for_types::type_for_mode, lang_hooks::types, unsigned_type_for(), update_stmt(), vNULL, and word_mode.
Referenced by process_switch().
|
static |
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.
References compare_tree_int(), lshift_cheap_p(), and word_mode.
Referenced by process_switch().
|
static |
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(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), switch_conv_info::target_inbound_names, and switch_conv_info::target_outbound_names.
Referenced by gen_inbound_check().
|
static |
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.
References switch_conv_info::constructors, and switch_conv_info::default_values.
Referenced by process_switch().
|
static |
Populate the array of default values in the order of phi nodes. DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch.
References switch_conv_info::default_values, switch_conv_info::final_bb, find_edge(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), single_succ_edge(), and switch_conv_info::switch_bb.
Referenced by process_switch().
|
static |
Generates and appropriately inserts loads of default values at the position given by BSI. Returns the last inserted statement.
References copy_ssa_name(), switch_conv_info::default_values, gsi_insert_before(), GSI_SAME_STMT, switch_conv_info::phi_count, switch_conv_info::target_inbound_names, switch_conv_info::target_outbound_names, and update_stmt().
Referenced by gen_inbound_check().
|
static |
Creates a check whether the switch expression value actually falls into the
range given by all the cases. If it does not, the temporaries are loaded
with default values instead. SWTCH is the switch statement being converted.
bb0 is the bb with the switch statement, however, we'll end it with a
condition instead.
bb1 is the bb to be used when the range check went ok. It is derived from
the switch BB
bb2 is the bb taken when the expression evaluated outside of the range
covered by the created arrays. It is populated by loads of default
values.
bbF is a fall through for both bb1 and bb2 and contains exactly what
originally followed the switch statement.
bbD contains the switch statement (in the end). It is unreachable but we
still need to strip off its edges.
References switch_conv_info::arr_ref_first, switch_conv_info::arr_ref_last, bbd, CDI_DOMINATORS, edge_def::count, create_artificial_label(), switch_conv_info::default_count, switch_conv_info::default_prob, switch_conv_info::default_values, edge_def::dest, dom_info_available_p(), switch_conv_info::final_bb, fix_phi_nodes(), edge_def::flags, fold_convert_loc(), basic_block_def::frequency, gen_def_assigns(), get_immediate_dominator(), gimple_assign_lhs(), gimple_bb(), gimple_build_cond(), gimple_build_label(), gimple_location(), gsi_for_stmt(), gsi_insert_before(), gsi_next(), GSI_SAME_STMT, gsi_start_bb(), iterate_fix_dominators(), make_edge(), switch_conv_info::other_count, edge_def::probability, prune_bbs(), switch_conv_info::range_size, remove_edge(), set_immediate_dominator(), split_block(), and update_stmt().
Referenced by process_switch().
|
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 CDI_DOMINATORS, edge_def::count, basic_block_def::count, edge_def::dest, edge_def::flags, force_gimple_operand_gsi(), get_immediate_dominator(), gimple_build_cond_from_tree(), gsi_bb(), gsi_insert_before(), GSI_SAME_STMT, edge_def::probability, redirect_edge_pred(), set_immediate_dominator(), split_block(), and edge_def::src.
Referenced by emit_case_bit_tests().
|
static |
Determine whether "1 << x" is relatively cheap in word_mode.
FIXME: This is the function that we need rtl.h and optabs.h for. This function (and similar RTL-related cost code in e.g. IVOPTS) should be moved to some kind of interface file for GIMPLE/RTL interactions.
References gen_raw_REG(), optab_handler(), optimize_insn_for_speed_p(), set_src_cost(), and word_mode.
Referenced by expand_switch_using_bit_tests_p().
| gimple_opt_pass* make_pass_convert_switch | ( | ) |
|
static |
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.
References build_arrays(), build_constructors(), check_all_empty_except_final(), check_final_bb(), check_range(), collect_switch_conv_info(), switch_conv_info::count, create_temp_arrays(), dump_file, emit_case_bit_tests(), expand_switch_using_bit_tests_p(), switch_conv_info::final_bb, free_temp_arrays(), gather_default_values(), gen_inbound_check(), gimple_switch_default_label(), gimple_switch_num_labels(), group_case_labels_stmt(), switch_conv_info::index_expr, LOOPS_NEED_FIXUP, loops_state_set(), switch_conv_info::range_min, switch_conv_info::range_size, switch_conv_info::reason, and switch_conv_info::uniq.
Referenced by do_switchconv().
|
static |
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 delete_basic_block(), edge_def::dest, ei_safe_edge(), remove_edge(), and basic_block_def::succs.
Referenced by gen_inbound_check().
|
static |
The pass gate.
