GCC Middle and Back End API Reference
tree-switch-conversion.c File Reference
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "line-map.h"
#include "params.h"
#include "flags.h"
#include "tree.h"
#include "basic-block.h"
Include dependency graph for tree-switch-conversion.c:

Data Structures

struct  case_bit_test
struct  switch_conv_info


static basic_block hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip, tree cond, edge e_true, bool update_dominators)
static bool lshift_cheap_p ()
static bool expand_switch_using_bit_tests_p (tree range, unsigned int uniq, unsigned int count)
static int case_bit_test_cmp ()
static void emit_case_bit_tests (gimple swtch, tree index_expr, tree minval, tree range)
static void collect_switch_conv_info ()
static bool check_range ()
static bool check_all_empty_except_final ()
static bool check_final_bb ()
static void create_temp_arrays ()
static void free_temp_arrays ()
static void gather_default_values ()
static void build_constructors ()
static tree constructor_contains_same_values_p ()
static tree array_value_type (gimple swtch, tree type, int num, struct switch_conv_info *info)
static void build_one_array (gimple swtch, int num, tree arr_index_type, gimple phi, tree tidx, struct switch_conv_info *info)
static void build_arrays ()
static gimple gen_def_assigns ()
static void prune_bbs ()
static void fix_phi_nodes (edge e1f, edge e2f, basic_block bbf, struct switch_conv_info *info)
static void gen_inbound_check ()
static const char * process_switch ()
static unsigned int do_switchconv ()
static bool switchconv_gate ()
gimple_opt_passmake_pass_convert_switch ()

Function Documentation

static tree array_value_type ( gimple  swtch,
tree  type,
int  num,
struct switch_conv_info info 
   Return type which should be used for array elements, either TYPE,
   or for integral type some smaller integral type that can still hold
   all the constants.  
static void build_arrays ( )
   Builds and initializes static arrays initialized with values gathered from
   the SWTCH switch statement.  Also creates statements that load values from
     Make sure we do not generate arithmetics in a subrange.  

References delete_basic_block(), edge_def::dest, and remove_edge().

static void build_constructors ( )
   The following function populates the vectors in the constructors array with
   future contents of the static arrays.  The vectors are populated in the
   order of phi nodes.  SWTCH is the switch statement being converted.  
static void build_one_array ( gimple  swtch,
int  num,
tree  arr_index_type,
gimple  phi,
tree  tidx,
struct switch_conv_info info 
   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 switch_conv_info::arr_ref_first, build_index_type(), switch_conv_info::final_bb, fold_convert_loc(), force_gimple_operand_gsi(), gimple_location(), gsi_end_p(), gsi_for_stmt(), gsi_insert_before(), gsi_next(), GSI_SAME_STMT, gsi_start_phis(), gsi_stmt(), switch_conv_info::index_expr, make_ssa_name(), switch_conv_info::range_min, switch_conv_info::range_size, lang_hooks_for_types::type_for_mode, lang_hooks::types, and update_stmt().

static int case_bit_test_cmp ( )
   Comparison function for qsort to order bit tests by decreasing
   probability of execution.  Our best guess comes from a measured
   profile.  If the profile counts are equal, break even on the
   number of case nodes, i.e. the node with the most cases gets
   tested first.

   TODO: Actually this currently runs before a profile is available.
   Therefore the case-as-bit-tests transformation should be done
   later in the pass pipeline, or something along the lines of
   "Efficient and effective branch reordering using profile data"
   (Yang et. al., 2002) should be implemented (although, how good
   is a paper is called "Efficient and effective ..." when the
   latter is implied by the former, but oh well...).  
     Stabilize the sort.  

References CDI_DOMINATORS, count, dom_info_available_p(), gimple_bb(), unsigned_type_for(), and vNULL.

static bool check_all_empty_except_final ( )
   Checks whether all but the FINAL_BB basic blocks are empty.  

References switch_conv_info::reason.

static bool 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.  
static bool check_range ( )
   Checks whether the range given by individual case statements of the SWTCH
   switch statement isn't too big and whether the number of branches actually
   satisfies the size of the new array.  
static void collect_switch_conv_info ( )
   Collect information about GIMPLE_SWITCH statement SWTCH into INFO.  
     The gimplifier has already sorted the cases by CASE_LOW and ensured there
     is a default label which is the first in the vector.
     Collect the bits we can deduce from the CFG.  
     See if there is one common successor block for all branch
     targets.  If it exists, record it in FINAL_BB.  
     Get upper and lower bounds of case values, and the covered range.  
     Get a count of the number of case labels.  Single-valued case labels
     simply count as one, but a case range counts double, since it may
     require two compares if it gets lowered as a branching tree.  
     Get the number of unique non-default targets out of the GIMPLE_SWITCH
     block.  Assume a CFG cleanup would have already removed degenerate
     switch statements, this allows us to just use EDGE_COUNT.  
static tree constructor_contains_same_values_p ( )
   If all values in the constructor vector are the same, return the value.
   Otherwise return NULL_TREE.  Not supposed to be called for empty
static void 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.  
     ??? Macros do not support multi argument templates in their
     argument list.  We create a typedef to work around that problem.  

References switch_conv_info::final_bb, find_edge(), gimple_switch_label(), gimple_switch_num_labels(), switch_conv_info::range_min, single_succ_edge(), switch_conv_info::switch_bb, and tree_int_cst_lt().

static unsigned int do_switchconv ( )
   The main function of the pass scans statements for switches and invokes
   process_switch on them.  
               Make no effort to update the post-dominator tree.  It is actually not
               that hard for the transformations we have performed, but it is not
               supported by iterate_fix_dominators.  
static void emit_case_bit_tests ( gimple  swtch,
tree  index_expr,
tree  minval,
tree  range 
    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).

    There *MUST* be MAX_CASE_BIT_TESTS or less unique case
    node targets.  
     Get the edge for the default case.  
     Go through all case labels, and collect the case labels, profile
     counts, and other information we need to build the branch tests.  
     We generate two jumps to the default case label.
     Split the default edge, so that we don't have to do any PHI node
     Now build the test-and-branch code.  
     idx = (unsigned)x - minval.  
     if (idx > range) goto default 
     Any blocks dominated by the GIMPLE_SWITCH, but that are not successors
     of NEW_BB, are still immediately dominated by SWITCH_BB.  Make it so.  
     csui = (1 << (word_mode) idx) 
     for each unique set of cases:
        if (const & csui) goto target  
     We should have removed all edges now.  
     If nothing matched, go to the default label.  
     The GIMPLE_SWITCH is now redundant.  
         Fix up the dominator tree.  
static bool expand_switch_using_bit_tests_p ( tree  range,
unsigned int  uniq,
unsigned int  count 
   Return true if a switch should be expanded as a bit test.
   RANGE is the difference between highest and lowest case.
   UNIQ is number of unique case node targets, not counting the default case.
   COUNT is the number of comparisons needed, not counting the default case.  

References case_bit_test::bits, case_bit_test::hi, HOST_WIDE_INT, case_bit_test::label, case_bit_test::lo, and case_bit_test::target_edge.

static void fix_phi_nodes ( edge  e1f,
edge  e2f,
basic_block  bbf,
struct switch_conv_info info 
   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).  
static void free_temp_arrays ( )
   Free the arrays created by create_temp_arrays().  The vectors that are
   created by that function are not freed here, however, because they have
   already become constructors and must be preserved.  

References switch_conv_info::constructors, switch_conv_info::default_values, constructor_elt_d::index, int_const_binop(), switch_conv_info::range_min, unshare_expr_without_location(), and constructor_elt_d::value.

static void gather_default_values ( )
   Populate the array of default values in the order of phi nodes.
   DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch.  
static gimple gen_def_assigns ( )
   Generates and appropriately inserts loads of default values at the position
   given by BSI.  Returns the last inserted statement.  

References create_artificial_label().

static void gen_inbound_check ( )

Creates a check whether the switch expression value actually falls into the range given by all the cases. If it does not, the temporaries are loaded with default values instead. SWTCH is the switch statement being converted.

bb0 is the bb with the switch statement, however, we'll end it with a condition instead.

bb1 is the bb to be used when the range check went ok. It is derived from the switch BB

bb2 is the bb taken when the expression evaluated outside of the range covered by the created arrays. It is populated by loads of default values.

bbF is a fall through for both bb1 and bb2 and contains exactly what originally followed the switch statement.

bbD contains the switch statement (in the end). It is unreachable but we still need to strip off its edges.

     (end of) block 0 
     block 2 
     block 1 
     block F 
     cfg fix 
     flags and profiles of the edge for in-range values 
     flags and profiles of the edge taking care of out-of-range values 
     frequencies of the new BBs 
     Tidy blocks that have become unreachable.  
     Fixup the PHI nodes in bbF.  
     Fix the dominator tree, if it is available.  
           If bbD was the immediate dominator ...  
static basic_block hoist_edge_and_branch_if_true ( gimple_stmt_iterator gsip,
tree  cond,
edge  e_true,
bool  update_dominators 
   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
   The CFG is updated.  The dominator tree will not be valid after
   this transformation, but the immediate dominators are updated if
   Returns the newly created basic block.  
static bool lshift_cheap_p ( )
   Determine whether "1 << x" is relatively cheap in word_mode.  
   FIXME: This is the function that we need rtl.h and optabs.h for.
   This function (and similar RTL-related cost code in e.g. IVOPTS) should
   be moved to some kind of interface file for GIMPLE/RTL interactions.  
     FIXME: This should be made target dependent via this "this_target"
     mechanism, similar to e.g. can_copy_init_p in gcse.c.  
     If the targer has no lshift in word_mode, the operation will most
     probably not be cheap.  ??? Does GCC even work for such targets?  
gimple_opt_pass* make_pass_convert_switch ( )
static const char* process_switch ( )
   The following function is invoked on every switch statement (the current one
   is given in SWTCH) and runs the individual phases of switch conversion on it
   one after another until one fails or the conversion is completed.
   Returns NULL on success, or a pointer to a string with the reason why the
   conversion failed.  
     Group case labels so that we get the right results from the heuristics
     that decide on the code generation approach for this switch.  
     If this switch is now a degenerate case with only a default label,
     there is nothing left for us to do.   
     No error markers should reach here (they should be filtered out
     during gimplification).  
     A switch on a constant should have been optimized in tree-cfg-cleanup.  
           This will be expanded as a decision tree in stmt.c:expand_case.  
     If there is no common successor, we cannot do the transformation.  
     Check the case label values are within reasonable range:  
     For all the cases, see whether they are empty, the assignments they
     represent constant and so on...  
     At this point all checks have passed and we can proceed with the

References CDI_POST_DOMINATORS, dump_file, expand_location(), free_dominance_info(), gimple_location(), last_stmt(), and print_gimple_stmt().

static void prune_bbs ( )
   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).  
static bool switchconv_gate ( )
   The pass gate.