GCC Middle and Back End API Reference
|
#include <tree-switch-conversion.h>
Public Member Functions | |
switch_decision_tree (gswitch *swtch) | |
bool | analyze_switch_statement () |
bool | try_switch_expansion (vec< cluster * > &clusters) |
int | 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) |
|
inline |
References m_case_bbs, m_case_list, m_case_node_pool, m_phi_mapping, m_switch, and NULL.
bool switch_decision_tree::analyze_switch_statement | ( | ) |
Analyze switch statement and return true when the statement is expanded as decision tree.
References CASE_HIGH, CASE_LABEL, CASE_LOW, cfun, compute_cases_per_edge(), dump_file, dump_flags, tree_switch_conversion::bit_test_cluster::find_bit_tests(), find_edge(), tree_switch_conversion::jump_table_cluster::find_jump_tables(), tree_switch_conversion::cluster::get_type(), gimple_bb(), gimple_location(), gimple_switch_default_bb(), gimple_switch_label(), gimple_switch_num_labels(), i, label_to_block(), m_case_bbs, m_switch, tree_switch_conversion::release_clusters(), reset_out_edges_aux(), tree_switch_conversion::SIMPLE_CASE, TDF_DETAILS, try_switch_expansion(), and warning_at().
Referenced by gimple_lower_bitint().
|
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().
int 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. Return the approx max number of cases per edge.
References CASE_HIGH, cfun, gimple_switch_edge(), gimple_switch_label(), gimple_switch_num_labels(), i, m_switch, and reset_out_edges_aux().
Referenced by analyze_switch_statement().
|
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().
|
static |
Dump ROOT, a list or tree of case nodes, to file.
References profile_probability::dump(), tree_switch_conversion::cluster::dump(), dump_case_nodes(), tree_switch_conversion::case_tree_node::m_c, tree_switch_conversion::case_tree_node::m_left, tree_switch_conversion::cluster::m_prob, tree_switch_conversion::case_tree_node::m_right, and tree_switch_conversion::cluster::m_subtree_prob.
Referenced by dump_case_nodes(), and 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().
basic_block switch_decision_tree::emit_case_nodes | ( | basic_block | bb, |
tree | index, | ||
case_tree_node * | node, | ||
profile_probability | default_prob, | ||
tree | index_type, | ||
location_t | loc ) |
Emit step-by-step code to select a case for the value of INDEX. The thus generated decision tree follows the form of the case-node binary tree NODE, whose nodes represent test conditions. DEFAULT_PROB is probability of cases leading to default BB. INDEX_TYPE is the type of the index of the switch.
References profile_count::apply_probability(), tree_switch_conversion::BIT_TEST, basic_block_def::count, do_jump_if_equal(), emit_case_nodes(), emit_cmp_and_jump_insns(), emit_jump(), generate_range_test(), tree_switch_conversion::cluster::get_high(), tree_switch_conversion::cluster::get_low(), tree_switch_conversion::cluster::get_type(), tree_switch_conversion::case_tree_node::has_child(), tree_switch_conversion::cluster::is_single_value_p(), tree_switch_conversion::case_tree_node::m_c, tree_switch_conversion::cluster::m_case_bb, m_default_bb, tree_switch_conversion::cluster::m_default_prob, tree_switch_conversion::case_tree_node::m_left, tree_switch_conversion::cluster::m_prob, tree_switch_conversion::case_tree_node::m_right, tree_switch_conversion::cluster::m_subtree_prob, profile_probability::never(), NULL, redirect_edge_succ(), tree_switch_conversion::SIMPLE_CASE, single_pred_edge(), single_succ_edge(), and split_edge().
Referenced by emit(), and emit_case_nodes().
|
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().
|
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().
void switch_decision_tree::fix_phi_operands_for_edges | ( | ) |
Append new operands to PHI statements that were introduced due to addition of new edges to case labels.
References add_phi_arg(), gcc_assert, 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, NULL_TREE, gphi_iterator::phi(), and UNKNOWN_LOCATION.
Referenced by try_switch_expansion().
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, and gphi_iterator::phi().
Referenced by try_switch_expansion().
|
inlinestatic |
References FOR_EACH_EDGE, gimple_bb(), and basic_block_def::succs.
Referenced by analyze_switch_statement(), compute_cases_per_edge(), and tree_switch_conversion::jump_table_cluster::emit().
Attempt to expand CLUSTERS as a decision tree. Return true when expanded.
References cfun, basic_block_def::count, create_empty_bb(), tree_switch_conversion::cluster::emit(), emit(), fix_phi_operands_for_edges(), gimple_bb(), gimple_location(), gimple_switch_default_edge(), gimple_switch_default_label(), gimple_switch_index(), gimple_switch_num_labels(), gsi_end_p(), gsi_last_bb(), gsi_prev(), gsi_stmt(), i, basic_block_def::loop_father, tree_switch_conversion::cluster::m_case_bb, m_case_list, m_case_node_pool, m_default_bb, m_switch, NULL_TREE, r, range_check_type(), record_phi_operand_mapping(), redirect_edge_succ(), tree_switch_conversion::SIMPLE_CASE, single_pred_edge(), single_succ_edge(), split_block(), split_block_after_labels(), split_edge(), and TREE_TYPE.
Referenced by analyze_switch_statement().
auto_vec<basic_block> tree_switch_conversion::switch_decision_tree::m_case_bbs |
case_tree_node* tree_switch_conversion::switch_decision_tree::m_case_list |
Referenced by emit(), switch_decision_tree(), and try_switch_expansion().
object_allocator<case_tree_node> tree_switch_conversion::switch_decision_tree::m_case_node_pool |
Referenced by switch_decision_tree(), and try_switch_expansion().
basic_block tree_switch_conversion::switch_decision_tree::m_default_bb |
Referenced by emit(), emit_case_nodes(), and try_switch_expansion().
Referenced by fix_phi_operands_for_edges(), record_phi_operand_mapping(), and switch_decision_tree().
gswitch* tree_switch_conversion::switch_decision_tree::m_switch |