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

#include <tree-switch-conversion.h>

Collaboration diagram for tree_switch_conversion::switch_decision_tree:

Public Member Functions

 switch_decision_tree (gswitch *swtch)
 
bool analyze_switch_statement ()
 
bool try_switch_expansion (vec< cluster * > &clusters)
 
void compute_cases_per_edge ()
 
void record_phi_operand_mapping ()
 
void fix_phi_operands_for_edges ()
 
void emit (basic_block bb, tree index_expr, profile_probability default_prob, tree index_type)
 
basic_block emit_case_nodes (basic_block bb, tree index, case_tree_node *node, profile_probability default_prob, tree index_type, location_t)
 

Static Public Member Functions

static void balance_case_nodes (case_tree_node **head, case_tree_node *parent)
 
static void dump_case_nodes (FILE *f, case_tree_node *root, int indent_step, int indent_level)
 
static void emit_jump (basic_block bb, basic_block case_bb)
 
static basic_block emit_cmp_and_jump_insns (basic_block bb, tree op0, tree op1, tree_code comparison, basic_block label_bb, profile_probability prob, location_t)
 
static basic_block do_jump_if_equal (basic_block bb, tree op0, tree op1, basic_block label_bb, profile_probability prob, location_t)
 
static void reset_out_edges_aux (gswitch *swtch)
 

Data Fields

gswitchm_switch
 
hash_map< tree, treem_phi_mapping
 
auto_vec< basic_blockm_case_bbs
 
basic_block m_default_bb
 
object_allocator< case_tree_nodem_case_node_pool
 
case_tree_nodem_case_list
 

Constructor & Destructor Documentation

◆ switch_decision_tree()

tree_switch_conversion::switch_decision_tree::switch_decision_tree ( gswitch * swtch)
inline

Member Function Documentation

◆ analyze_switch_statement()

◆ balance_case_nodes()

void switch_decision_tree::balance_case_nodes ( case_tree_node ** head,
case_tree_node * parent )
static
Take an ordered list of case nodes
and transform them into a near optimal binary tree,
on the assumption that any target code selection value is as
likely as any other.

The transformation is performed by splitting the ordered
list into two equal sections plus a pivot.  The parts are
then attached to the pivot as left and right branches.  Each
branch is then transformed recursively.   

References balance_case_nodes(), i, profile_probability::initialized_p(), tree_switch_conversion::case_tree_node::m_c, tree_switch_conversion::case_tree_node::m_left, tree_switch_conversion::case_tree_node::m_parent, tree_switch_conversion::cluster::m_prob, tree_switch_conversion::case_tree_node::m_right, tree_switch_conversion::cluster::m_subtree_prob, profile_probability::never(), and NULL.

Referenced by balance_case_nodes(), and emit().

◆ compute_cases_per_edge()

void switch_decision_tree::compute_cases_per_edge ( )
Compute the number of case labels that correspond to each outgoing edge of
switch statement.  Record this information in the aux field of the edge.   

References cfun, gimple_switch_edge(), gimple_switch_num_labels(), i, m_switch, and reset_out_edges_aux().

Referenced by analyze_switch_statement().

◆ do_jump_if_equal()

basic_block switch_decision_tree::do_jump_if_equal ( basic_block bb,
tree op0,
tree op1,
basic_block label_bb,
profile_probability prob,
location_t loc )
static
Generate code to jump to LABEL if OP0 and OP1 are equal.
PROB is the probability of jumping to LABEL_BB.
BB is a basic block where the new condition will be placed.   

References profile_count::apply_probability(), basic_block_def::count, fold_convert, gcc_assert, gimple_build_cond(), gimple_set_location(), gsi_insert_before(), gsi_last_bb(), GSI_SAME_STMT, profile_probability::invert(), make_edge(), NULL_TREE, single_succ_p(), split_block(), and TREE_TYPE.

Referenced by emit_case_nodes().

◆ dump_case_nodes()

◆ emit()

void switch_decision_tree::emit ( basic_block bb,
tree index_expr,
profile_probability default_prob,
tree index_type )
Generate a decision tree, switching on INDEX_EXPR and jumping to
one of the labels in CASE_LIST or to the DEFAULT_LABEL.

We generate a binary decision tree to select the appropriate target
code.   

References balance_case_nodes(), ceil_log2(), current_function_decl, delete_basic_block(), dump_case_nodes(), dump_file, dump_flags, dump_function_to_file(), emit_case_nodes(), emit_jump(), gcc_assert, gimple_bb(), gimple_location(), gsi_last_bb(), gsi_remove(), m_case_list, m_default_bb, m_switch, NULL, TDF_DETAILS, and TYPE_PRECISION.

Referenced by try_switch_expansion().

◆ emit_case_nodes()

◆ emit_cmp_and_jump_insns()

basic_block switch_decision_tree::emit_cmp_and_jump_insns ( basic_block bb,
tree op0,
tree op1,
tree_code comparison,
basic_block label_bb,
profile_probability prob,
location_t loc )
static
Generate code to compare OP0 with OP1 so that the condition codes are
set and to jump to LABEL_BB if the condition is true.
COMPARISON is the GIMPLE comparison (EQ, NE, GT, etc.).
PROB is the probability of jumping to LABEL_BB.   

References profile_count::apply_probability(), basic_block_def::count, fold_convert, gcc_assert, gimple_build_cond(), gimple_set_location(), gsi_insert_after(), gsi_last_bb(), GSI_NEW_STMT, profile_probability::invert(), make_edge(), NULL_TREE, single_succ_p(), split_block(), and TREE_TYPE.

Referenced by emit_case_nodes().

◆ emit_jump()

void switch_decision_tree::emit_jump ( basic_block bb,
basic_block case_bb )
static
Add an unconditional jump to CASE_BB that happens in basic block BB.   

References redirect_edge_succ(), and single_succ_edge().

Referenced by emit(), and emit_case_nodes().

◆ fix_phi_operands_for_edges()

void switch_decision_tree::fix_phi_operands_for_edges ( )

◆ record_phi_operand_mapping()

void switch_decision_tree::record_phi_operand_mapping ( )
Before switch transformation, record all SSA_NAMEs defined in switch BB
and used in a label basic block.   

References gimple_bb(), gimple_phi_arg_def(), gimple_phi_arg_edge(), gimple_phi_num_args(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), i, m_case_bbs, m_phi_mapping, m_switch, gphi_iterator::phi(), and hash_map< KeyId, Value, Traits >::put().

Referenced by try_switch_expansion().

◆ reset_out_edges_aux()

void tree_switch_conversion::switch_decision_tree::reset_out_edges_aux ( gswitch * swtch)
inlinestatic

◆ try_switch_expansion()

Field Documentation

◆ m_case_bbs

auto_vec<basic_block> tree_switch_conversion::switch_decision_tree::m_case_bbs

◆ m_case_list

case_tree_node* tree_switch_conversion::switch_decision_tree::m_case_list

Referenced by emit(), and try_switch_expansion().

◆ m_case_node_pool

object_allocator<case_tree_node> tree_switch_conversion::switch_decision_tree::m_case_node_pool

Referenced by try_switch_expansion().

◆ m_default_bb

basic_block tree_switch_conversion::switch_decision_tree::m_default_bb

◆ m_phi_mapping

hash_map<tree, tree> tree_switch_conversion::switch_decision_tree::m_phi_mapping

◆ m_switch

gswitch* tree_switch_conversion::switch_decision_tree::m_switch

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