tree_switch_conversion::bit_test_cluster Class Reference

#include <tree-switch-conversion.h>

Inheritance diagram for tree_switch_conversion::bit_test_cluster:

Collaboration diagram for tree_switch_conversion::bit_test_cluster:

Public Member Functions
	bit_test_cluster (vec< cluster * > &clusters, unsigned start, unsigned end, bool handles_entire_switch)
cluster_type	get_type () final override
void	emit (tree index_expr, tree index_type, tree default_label_expr, basic_block default_bb, location_t loc) final override
tree	get_low () final override
tree	get_high () final override
void	debug () final override
void	dump (FILE *f, bool details=false) final override
virtual bool	is_single_value_p ()

Static Public Member Functions
static vec< cluster * >	find_bit_tests (vec< cluster * > &clusters)
static bool	can_be_handled (unsigned HOST_WIDE_INT range, unsigned uniq)
static bool	can_be_handled (const vec< cluster * > &clusters, unsigned start, unsigned end)
static bool	is_beneficial (unsigned count, unsigned uniq)
static bool	is_beneficial (const vec< cluster * > &clusters, unsigned start, unsigned end)
static basic_block	hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip, tree cond, basic_block case_bb, profile_probability prob, location_t)
static bool	is_enabled (void)
static unsigned HOST_WIDE_INT	get_range (tree low, tree high)

Data Fields
bool	m_handles_entire_switch
vec< simple_cluster * >	m_cases
tree	m_case_label_expr
basic_block	m_case_bb
profile_probability	m_prob
profile_probability	m_subtree_prob
profile_probability	m_default_prob

Static Public Attributes
static const int	m_max_case_bit_tests = 3

Detailed Description

A GIMPLE switch statement can be expanded to a short sequence of bit-wise
comparisons.  "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)"
where CST and MINVAL are integer constants.  This is better than a series
of compare-and-branch insns in some cases,  e.g. we can implement:

        if ((x==4) || (x==6) || (x==9) || (x==11))

as a single bit test:

        if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11)))

This transformation is only applied if the number of case targets is small,
if CST constains at least 3 bits, and "1 << x" is cheap.  The bit tests are
performed in "word_mode".

The following example shows the code the transformation generates:

        int bar(int x)
        {
                switch (x)
                {
                case '0':  case '1':  case '2':  case '3':  case '4':
                case '5':  case '6':  case '7':  case '8':  case '9':
                case 'A':  case 'B':  case 'C':  case 'D':  case 'E':
                case 'F':
                        return 1;
                }
                return 0;
        }

==>

        bar (int x)
        {
                tmp1 = x - 48;
                if (tmp1 > (70 - 48)) goto L2;
                tmp2 = 1 << tmp1;
                tmp3 = 0b11111100000001111111111;
                if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2;
        L1:
                return 1;
        L2:
                return 0;
        }

TODO: There are still some improvements to this transformation that could
be implemented:

* A narrower mode than word_mode could be used if that is cheaper, e.g.
  for x86_64 where a narrower-mode shift may result in smaller code.

* The compounded constant could be shifted rather than the one.  The
  test would be either on the sign bit or on the least significant bit,
  depending on the direction of the shift.  On some machines, the test
  for the branch would be free if the bit to test is already set by the
  shift operation.

This transformation was contributed by Roger Sayle, see this e-mail:
   http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html

Constructor & Destructor Documentation

bit_test_cluster()

tree_switch_conversion::bit_test_cluster::bit_test_cluster ( vec< cluster * > & clusters, unsigned start, unsigned end, bool handles_entire_switch )

inline

Member Function Documentation

can_be_handled() [1/2]

bool bit_test_cluster::can_be_handled ( const vec< cluster * > & clusters, unsigned start, unsigned end )

static

Return true when cluster starting at START and ending at END (inclusive)
can build a bit test.   

References can_be_handled(), end(), tree_switch_conversion::group_cluster::get_high(), tree_switch_conversion::group_cluster::get_low(), tree_switch_conversion::cluster::get_range(), ggc_alloc(), i, m_max_case_bit_tests, and sc.

can_be_handled() [2/2]

static bool tree_switch_conversion::bit_test_cluster::can_be_handled ( unsigned HOST_WIDE_INT range, unsigned uniq )

static

Referenced by can_be_handled(), tree_switch_conversion::switch_conversion::expand(), and find_bit_tests().

debug()

void tree_switch_conversion::group_cluster::debug ( )

inlinefinaloverridevirtualinherited

Implements tree_switch_conversion::cluster.

References tree_switch_conversion::group_cluster::dump(), and ggc_alloc().

dump()

void group_cluster::dump ( FILE * f, bool details = false )

finaloverridevirtualinherited

Dump content of a cluster.   

Implements tree_switch_conversion::cluster.

References tree_switch_conversion::group_cluster::get_high(), tree_switch_conversion::group_cluster::get_low(), tree_switch_conversion::cluster::get_range(), tree_switch_conversion::cluster::get_type(), ggc_alloc(), HOST_WIDE_INT_PRINT_DEC, i, tree_switch_conversion::JUMP_TABLE, tree_switch_conversion::group_cluster::m_cases, PRINT_CASE, and sc.

Referenced by tree_switch_conversion::group_cluster::debug().

emit()

void bit_test_cluster::emit ( tree index_expr, tree index_type, tree default_label_expr, basic_block default_bb, location_t loc )

finaloverridevirtual

Expand a switch statement by a short sequence of bit-wise
comparisons.  "switch(x)" is effectively converted into
"if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
integer constants.

INDEX_EXPR is the value being switched on.

MINVAL is the lowest case value of in the case nodes,
and RANGE is highest value minus MINVAL.  MINVAL and RANGE
are not guaranteed to be of the same type as INDEX_EXPR
(the gimplifier doesn't change the type of case label values,
and MINVAL and RANGE are derived from those values).
MAXVAL is MINVAL + RANGE.

There *MUST* be max_case_bit_tests or less unique case
node targets.   

Implements tree_switch_conversion::cluster.

References profile_probability::always(), tree_switch_conversion::case_bit_test::bits, boolean_type_node, build_zero_cst(), cfun, tree_switch_conversion::case_bit_test::cmp(), compare_tree_int(), count, EDGE_COUNT, fold_build2, fold_build2_loc(), fold_convert, fold_convert_loc(), force_gimple_operand_gsi(), gcc_assert, gcc_checking_assert, GEN_INT, gen_raw_REG(), tree_switch_conversion::simple_cluster::get_high(), tree_switch_conversion::group_cluster::get_high(), tree_switch_conversion::simple_cluster::get_low(), tree_switch_conversion::group_cluster::get_low(), tree_switch_conversion::cluster::get_range(), get_range_query(), ggc_alloc(), gimple_build_assign(), gsi_bb(), gsi_insert_before(), gsi_last_bb(), GSI_SAME_STMT, wi::gt_p(), hoist_edge_and_branch_if_true(), i, immed_wide_int_const(), int_const_binop(), integer_one_node, integer_zero_node, profile_probability::invert(), tree_switch_conversion::case_bit_test::label, wi::leu_p(), wi::lrshift(), wi::lshift(), wi::lt_p(), tree_switch_conversion::cluster::m_case_bb, tree_switch_conversion::cluster::m_case_label_expr, tree_switch_conversion::group_cluster::m_cases, tree_switch_conversion::cluster::m_default_prob, m_handles_entire_switch, m_max_case_bit_tests, tree_switch_conversion::cluster::m_prob, tree_switch_conversion::cluster::m_subtree_prob, make_edge(), make_ssa_name(), tree_switch_conversion::case_bit_test::mask, profile_probability::never(), NULL_TREE, wi::one(), optimize_insn_for_speed_p(), tree_switch_conversion::case_bit_test::prob, qsort, r, range_check_type(), set_src_cost(), tree_switch_conversion::case_bit_test::target_bb, wi::to_wide(), TREE_CODE, tree_to_uhwi(), TREE_TYPE, lang_hooks_for_types::type_for_mode, TYPE_PRECISION, TYPE_SIGN, lang_hooks::types, update_stmt(), wide_int_to_tree(), word_mode, and wi::zero().

find_bit_tests()

vec< cluster * > bit_test_cluster::find_bit_tests ( vec< cluster * > & clusters )

static

Find bit tests of given CLUSTERS, where all members of the vector
are of type simple_cluster.  New clusters are returned.   

References can_be_handled(), end(), gcc_checking_assert, ggc_alloc(), i, INT_MAX, is_beneficial(), and is_enabled().

Referenced by tree_switch_conversion::switch_decision_tree::analyze_switch_statement(), and if_chain::is_beneficial().

get_high()

tree tree_switch_conversion::group_cluster::get_high ( )

inlinefinaloverridevirtualinherited

Implements tree_switch_conversion::cluster.

References tree_switch_conversion::group_cluster::m_cases.

Referenced by can_be_handled(), tree_switch_conversion::jump_table_cluster::can_be_handled(), tree_switch_conversion::group_cluster::dump(), tree_switch_conversion::jump_table_cluster::emit(), and emit().

get_low()

tree tree_switch_conversion::group_cluster::get_low ( )

inlinefinaloverridevirtualinherited

Implements tree_switch_conversion::cluster.

References tree_switch_conversion::group_cluster::m_cases.

Referenced by can_be_handled(), tree_switch_conversion::jump_table_cluster::can_be_handled(), tree_switch_conversion::group_cluster::dump(), tree_switch_conversion::jump_table_cluster::emit(), and emit().

get_range()

static unsigned HOST_WIDE_INT tree_switch_conversion::cluster::get_range ( tree low, tree high )

inlinestaticinherited

References wi::fits_uhwi_p(), ggc_alloc(), wi::neg_p(), wi::to_wide(), TREE_TYPE, and TYPE_SIGN.

Referenced by can_be_handled(), tree_switch_conversion::jump_table_cluster::can_be_handled(), tree_switch_conversion::group_cluster::dump(), tree_switch_conversion::jump_table_cluster::emit(), and emit().

get_type()

cluster_type tree_switch_conversion::bit_test_cluster::get_type ( )

inlinefinaloverridevirtual

Implements tree_switch_conversion::cluster.

References tree_switch_conversion::BIT_TEST.

hoist_edge_and_branch_if_true()

basic_block bit_test_cluster::hoist_edge_and_branch_if_true ( gimple_stmt_iterator * gsip, tree cond, basic_block case_bb, profile_probability prob, location_t loc )

static

Split the basic block at the statement pointed to by GSIP, and insert
a branch to the target basic block of E_TRUE conditional on tree
expression COND.

It is assumed that there is already an edge from the to-be-split
basic block to E_TRUE->dest block.  This edge is removed, and the
profile information on the edge is re-used for the new conditional
jump.

The CFG is updated.  The dominator tree will not be valid after
this transformation, but the immediate dominators are updated if
UPDATE_DOMINATORS is true.

Returns the newly created basic block.   

References basic_block_def::count, force_gimple_operand_gsi(), gcc_assert, ggc_alloc(), gimple_build_cond_from_tree(), gimple_set_location(), gsi_bb(), gsi_insert_before(), GSI_SAME_STMT, make_edge(), NULL, NULL_TREE, redirect_edge_pred(), and split_block().

Referenced by emit().

is_beneficial() [1/2]

bool bit_test_cluster::is_beneficial ( const vec< cluster * > & clusters, unsigned start, unsigned end )

static

Return true if cluster starting at START and ending at END (inclusive)
is profitable transformation.   

References bitmap_count_bits(), bitmap_set_bit, count, end(), ggc_alloc(), i, is_beneficial(), and sc.

is_beneficial() [2/2]

bool bit_test_cluster::is_beneficial ( unsigned count, unsigned uniq )

static

Return true when COUNT of cases of UNIQ labels is beneficial for bit test
transformation.   

References count, and ggc_alloc().

Referenced by tree_switch_conversion::switch_conversion::expand(), find_bit_tests(), and is_beneficial().

is_enabled()

static bool tree_switch_conversion::bit_test_cluster::is_enabled ( void )

inlinestatic

References ggc_alloc().

Referenced by find_bit_tests().

is_single_value_p()

virtual bool tree_switch_conversion::cluster::is_single_value_p ( )

inlinevirtualinherited

Reimplemented in tree_switch_conversion::simple_cluster.

Referenced by tree_switch_conversion::switch_decision_tree::emit_case_nodes().

Field Documentation

m_case_bb

basic_block tree_switch_conversion::cluster::m_case_bb

inherited

Referenced by tree_switch_conversion::jump_table_cluster::emit(), emit(), tree_switch_conversion::switch_decision_tree::emit_case_nodes(), if_chain::is_beneficial(), and tree_switch_conversion::switch_decision_tree::try_switch_expansion().

m_case_label_expr

tree tree_switch_conversion::cluster::m_case_label_expr

inherited

Referenced by tree_switch_conversion::jump_table_cluster::emit(), and emit().

m_cases

vec<simple_cluster *> tree_switch_conversion::group_cluster::m_cases

inherited

Referenced by tree_switch_conversion::group_cluster::dump(), tree_switch_conversion::jump_table_cluster::emit(), emit(), tree_switch_conversion::group_cluster::get_high(), tree_switch_conversion::group_cluster::get_low(), tree_switch_conversion::group_cluster::group_cluster(), and tree_switch_conversion::group_cluster::~group_cluster().

m_default_prob

profile_probability tree_switch_conversion::cluster::m_default_prob

inherited

Referenced by emit(), and tree_switch_conversion::switch_decision_tree::emit_case_nodes().

m_handles_entire_switch

bool tree_switch_conversion::bit_test_cluster::m_handles_entire_switch

Referenced by emit().

m_max_case_bit_tests

const int tree_switch_conversion::bit_test_cluster::m_max_case_bit_tests = 3

static

Referenced by can_be_handled(), and emit().

m_prob

profile_probability tree_switch_conversion::cluster::m_prob

inherited

Referenced by tree_switch_conversion::switch_decision_tree::dump_case_nodes(), emit(), tree_switch_conversion::switch_decision_tree::emit_case_nodes(), and tree_switch_conversion::group_cluster::group_cluster().

m_subtree_prob

profile_probability tree_switch_conversion::cluster::m_subtree_prob

inherited

Referenced by tree_switch_conversion::switch_decision_tree::dump_case_nodes(), emit(), tree_switch_conversion::switch_decision_tree::emit_case_nodes(), and tree_switch_conversion::group_cluster::group_cluster().

---

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

• tree-switch-conversion.h
• tree-switch-conversion.cc