GCC Middle and Back End API Reference
tree_switch_conversion::switch_conversion Class Reference

#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 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 ()
 
gassigngen_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 ()
 

Data Fields

gswitchm_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
 
treem_default_values
 
treem_target_inbound_names
 
treem_target_outbound_names
 
tree m_target_vop
 
gimplem_arr_ref_first
 
gimplem_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
 
bool m_exp_index_transform_applied
 
tree m_exp_index_transform_log2_type
 

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 m_constructors, and m_default_values.

Member Function Documentation

◆ array_value_type()

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

◆ build_arrays()

◆ build_constructors()

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

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

Referenced by expand().

◆ collect()

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

◆ exp_index_transform()

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

◆ expand()

void switch_conversion::expand ( gswitch * swtch)

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

◆ is_exp_index_transform_viable()

bool switch_conversion::is_exp_index_transform_viable ( gswitch * swtch)
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().

◆ 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, 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

◆ m_cfg_altered

bool tree_switch_conversion::switch_conversion::m_cfg_altered

Referenced by exp_index_transform(), and expand().

◆ m_constructors

vec<constructor_elt, va_gc>** tree_switch_conversion::switch_conversion::m_constructors

◆ m_contiguous_range

bool tree_switch_conversion::switch_conversion::m_contiguous_range

◆ 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

◆ m_default_case_nonstandard

bool tree_switch_conversion::switch_conversion::m_default_case_nonstandard

◆ 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

◆ m_exp_index_transform_applied

bool tree_switch_conversion::switch_conversion::m_exp_index_transform_applied

◆ m_exp_index_transform_log2_type

tree tree_switch_conversion::switch_conversion::m_exp_index_transform_log2_type

◆ m_final_bb

◆ m_index_expr

tree tree_switch_conversion::switch_conversion::m_index_expr

◆ m_phi_count

int tree_switch_conversion::switch_conversion::m_phi_count

◆ m_range_max

tree tree_switch_conversion::switch_conversion::m_range_max

Referenced by collect(), and exp_index_transform().

◆ m_range_min

tree tree_switch_conversion::switch_conversion::m_range_min

◆ m_range_size

tree tree_switch_conversion::switch_conversion::m_range_size

◆ m_reason

const char* tree_switch_conversion::switch_conversion::m_reason

◆ m_switch

gswitch* tree_switch_conversion::switch_conversion::m_switch

◆ m_switch_bb

◆ m_target_inbound_names

tree* tree_switch_conversion::switch_conversion::m_target_inbound_names

◆ m_target_outbound_names

tree* tree_switch_conversion::switch_conversion::m_target_outbound_names

◆ 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: