#include <tree-switch-conversion.h>

Collaboration diagram for tree_switch_conversion::switch_conversion:

Public Member Functions
	switch_conversion ()

	~switch_conversion ()

void	expand (gswitch *swtch)

void	collect (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 ()

Detailed Description

The main structure of the pass.

Constructor & Destructor Documentation

◆ switch_conversion()

switch_conversion::switch_conversion ( )

Constructor.

◆ ~switch_conversion()

switch_conversion::~switch_conversion ( )

Destructor.

References ggc_alloc(), m_constructors, and m_default_values.

Member Function Documentation

◆ array_value_type()

tree switch_conversion::array_value_type	(	tree	type,
		int	num )

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(), ggc_alloc(), 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().

◆ build_arrays()

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, ggc_alloc(), 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, 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().

◆ build_constructors()

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, ggc_alloc(), 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().

◆ build_one_array()

void switch_conversion::build_one_array	(	int	num,
		tree	arr_index_type,
		gphi *	phi,
		tree	tidx )

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(), ggc_alloc(), 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(), 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().

◆ check_all_empty_except_final()

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, ggc_alloc(), 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().

◆ check_final_bb()

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(), ggc_alloc(), 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().

◆ check_range()

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, ggc_alloc(), m_count, m_range_size, m_reason, tree_fits_uhwi_p(), and tree_to_uhwi().

Referenced by expand().

◆ collect()

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, ggc_alloc(), 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().

◆ contains_linear_function_p()

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, ggc_alloc(), i, m_range_min, wi::to_wide(), TREE_CODE, TREE_TYPE, TYPE_PRECISION, TYPE_SIGN, and constructor_elt::value.

Referenced by build_one_array().

◆ create_temp_arrays()

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 ggc_alloc(), 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().

◆ 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, 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(), 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.

◆ fix_phi_nodes()

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(), ggc_alloc(), 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().

◆ gather_default_values()

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, ggc_alloc(), 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().

◆ gen_def_assigns()

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(), ggc_alloc(), 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().

◆ 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, create_artificial_label(), dom_info_available_p(), find_edge(), fix_phi_nodes(), fold_convert_loc(), gcc_assert, gen_def_assigns(), get_immediate_dominator(), ggc_alloc(), 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_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().

◆ prune_bbs()

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, ggc_alloc(), and remove_edge().

Referenced by gen_inbound_check().

Field Documentation

◆ m_arr_ref_first

gimple* tree_switch_conversion::switch_conversion::m_arr_ref_first

Referenced by build_arrays(), and gen_inbound_check().

◆ m_arr_ref_last

gimple* tree_switch_conversion::switch_conversion::m_arr_ref_last

Referenced by build_one_array(), and gen_inbound_check().

◆ m_cfg_altered

bool tree_switch_conversion::switch_conversion::m_cfg_altered

Referenced by expand().

◆ m_constructors

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().

◆ m_contiguous_range

bool tree_switch_conversion::switch_conversion::m_contiguous_range

Referenced by check_all_empty_except_final(), check_final_bb(), and collect().

◆ m_count

unsigned int tree_switch_conversion::switch_conversion::m_count

Referenced by check_range(), collect(), and expand().

◆ m_default_bb

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().

◆ m_default_case_nonstandard

bool tree_switch_conversion::switch_conversion::m_default_case_nonstandard

Referenced by build_arrays(), check_all_empty_except_final(), check_final_bb(), collect(), expand(), fix_phi_nodes(), gather_default_values(), and gen_inbound_check().

◆ m_default_prob

profile_probability tree_switch_conversion::switch_conversion::m_default_prob

Referenced by collect(), and gen_inbound_check().

◆ m_default_values

tree* tree_switch_conversion::switch_conversion::m_default_values

Referenced by build_constructors(), build_one_array(), create_temp_arrays(), gather_default_values(), gen_def_assigns(), gen_inbound_check(), and ~switch_conversion().

◆ m_final_bb

basic_block tree_switch_conversion::switch_conversion::m_final_bb

Referenced by build_arrays(), build_constructors(), check_all_empty_except_final(), check_final_bb(), collect(), expand(), gather_default_values(), and gen_inbound_check().

◆ m_index_expr

tree tree_switch_conversion::switch_conversion::m_index_expr

Referenced by build_arrays(), build_one_array(), collect(), and expand().

◆ m_phi_count

int tree_switch_conversion::switch_conversion::m_phi_count

Referenced by build_constructors(), check_final_bb(), create_temp_arrays(), and gen_def_assigns().

◆ m_range_max

tree tree_switch_conversion::switch_conversion::m_range_max

Referenced by collect().

◆ m_range_min

tree tree_switch_conversion::switch_conversion::m_range_min

Referenced by build_arrays(), build_constructors(), collect(), and contains_linear_function_p().

◆ m_range_size

tree tree_switch_conversion::switch_conversion::m_range_size

Referenced by build_arrays(), check_range(), collect(), create_temp_arrays(), expand(), and gen_inbound_check().

◆ m_reason

const char* tree_switch_conversion::switch_conversion::m_reason

Referenced by check_all_empty_except_final(), check_final_bb(), check_range(), and expand().

◆ m_switch

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().

◆ m_switch_bb

basic_block tree_switch_conversion::switch_conversion::m_switch_bb

Referenced by build_arrays(), build_constructors(), check_all_empty_except_final(), check_final_bb(), collect(), and gather_default_values().

◆ m_target_inbound_names

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().

◆ m_target_outbound_names

tree* tree_switch_conversion::switch_conversion::m_target_outbound_names

Referenced by create_temp_arrays(), fix_phi_nodes(), and gen_def_assigns().

◆ m_target_vop

tree tree_switch_conversion::switch_conversion::m_target_vop

Referenced by build_arrays(), and fix_phi_nodes().

◆ m_uniq

unsigned int tree_switch_conversion::switch_conversion::m_uniq

Referenced by collect(), and expand().

The documentation for this class was generated from the following files:

Data Fields
gswitch *	m_switch

tree	m_index_expr

tree	m_range_min

tree	m_range_max

tree	m_range_size

basic_block	m_switch_bb

basic_block	m_default_bb

basic_block	m_final_bb

profile_probability	m_default_prob

int	m_phi_count

vec< constructor_elt, va_gc > **	m_constructors

tree *	m_default_values

tree *	m_target_inbound_names

tree *	m_target_outbound_names

tree	m_target_vop

gimple *	m_arr_ref_first

gimple *	m_arr_ref_last

const char *	m_reason

bool	m_contiguous_range

bool	m_default_case_nonstandard

unsigned int	m_uniq

unsigned int	m_count

bool	m_cfg_altered

Public Member Functions

Data Fields

Detailed Description

Constructor & Destructor Documentation

◆ switch_conversion()

◆ ~switch_conversion()

Member Function Documentation

◆ array_value_type()

◆ build_arrays()

◆ build_constructors()

◆ build_one_array()

◆ check_all_empty_except_final()

◆ check_final_bb()

◆ check_range()

◆ collect()

◆ contains_linear_function_p()

◆ create_temp_arrays()

◆ expand()

◆ fix_phi_nodes()

◆ gather_default_values()

◆ gen_def_assigns()

◆ gen_inbound_check()

◆ prune_bbs()

Field Documentation

◆ m_arr_ref_first

◆ m_arr_ref_last

◆ m_cfg_altered

◆ m_constructors

◆ m_contiguous_range

◆ m_count

◆ m_default_bb

◆ m_default_case_nonstandard

◆ m_default_prob

◆ m_default_values

◆ m_final_bb

◆ m_index_expr

◆ m_phi_count

◆ m_range_max

◆ m_range_min

◆ m_range_size

◆ m_reason

◆ m_switch

◆ m_switch_bb

◆ m_target_inbound_names

◆ m_target_outbound_names

◆ m_target_vop

◆ m_uniq