#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
gswitch *	m_switch

hash_map< tree, tree >	m_phi_mapping

auto_vec< basic_block >	m_case_bbs

basic_block	m_default_bb

object_allocator< case_tree_node >	m_case_node_pool

case_tree_node *	m_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()

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

Referenced by gimple_lower_bitint().

◆ 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(), ggc_alloc(), i, profile_probability::initialized_p(), 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, ggc_alloc(), 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, ggc_alloc(), 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()

void switch_decision_tree::dump_case_nodes	(	FILE *	f,
		case_tree_node *	root,
		int	indent_step,
		int	indent_level )

static

Dump ROOT, a list or tree of case nodes, to file.

References profile_probability::dump(), tree_switch_conversion::cluster::dump(), dump_case_nodes(), ggc_alloc(), 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().

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

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.

Referenced by emit(), and 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, ggc_alloc(), 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 ggc_alloc(), 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 ( )

Append new operands to PHI statements that were introduced due to
addition of new edges to case labels.

References add_phi_arg(), gcc_assert, hash_map< KeyId, Value, Traits >::get(), ggc_alloc(), 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().

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

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

◆ try_switch_expansion()

bool switch_decision_tree::try_switch_expansion ( vec< cluster * > & clusters )

Attempt to expand CLUSTERS as a decision tree.  Return true when
expanded.

References cfun, basic_block_def::count, create_empty_bb(), emit(), tree_switch_conversion::cluster::emit(), fix_phi_operands_for_edges(), ggc_alloc(), 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::case_tree_node::m_c, tree_switch_conversion::cluster::m_case_bb, m_case_list, m_case_node_pool, m_default_bb, tree_switch_conversion::case_tree_node::m_right, 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().

Field Documentation

◆ m_case_bbs

auto_vec<basic_block> tree_switch_conversion::switch_decision_tree::m_case_bbs

Referenced by analyze_switch_statement(), fix_phi_operands_for_edges(), and record_phi_operand_mapping().

◆ 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

Referenced by emit(), emit_case_nodes(), and try_switch_expansion().

◆ m_phi_mapping

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

Referenced by fix_phi_operands_for_edges(), and record_phi_operand_mapping().

◆ m_switch

gswitch* tree_switch_conversion::switch_decision_tree::m_switch

Referenced by analyze_switch_statement(), compute_cases_per_edge(), emit(), record_phi_operand_mapping(), and try_switch_expansion().

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

Public Member Functions

Static Public Member Functions

Data Fields

Constructor & Destructor Documentation

◆ switch_decision_tree()

Member Function Documentation

◆ analyze_switch_statement()

◆ balance_case_nodes()

◆ compute_cases_per_edge()

◆ do_jump_if_equal()

◆ dump_case_nodes()

◆ emit()

◆ emit_case_nodes()

◆ emit_cmp_and_jump_insns()

◆ emit_jump()

◆ fix_phi_operands_for_edges()

◆ record_phi_operand_mapping()

◆ reset_out_edges_aux()

◆ try_switch_expansion()

Field Documentation

◆ m_case_bbs

◆ m_case_list

◆ m_case_node_pool

◆ m_default_bb

◆ m_phi_mapping

◆ m_switch