#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 "gimple.h"#include "gimple-ssa.h"#include "cgraph.h"#include "tree-cfg.h"#include "tree-phinodes.h"#include "tree-ssanames.h"#include "tree-pass.h"#include "gimple-pretty-print.h"#include "cfgloop.h"#include "langhooks.h"#include "expr.h"#include "optabs.h"
Data Structures | |
| struct | case_bit_test |
| struct | switch_conv_info |
Macros | |
| #define | MAX_CASE_BIT_TESTS 3 |
Macro Definition Documentation
| #define MAX_CASE_BIT_TESTS 3 |
Lower GIMPLE_SWITCH expressions to something more efficient than a jump table. Copyright (C) 2006-2013 Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not, write to the Free Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. This file handles the lowering of GIMPLE_SWITCH to an indexed load, or a series of bit-test-and-branch expressions. ??? For lang_hooks.types.type_for_mode, but is there a word_mode type in the GIMPLE type system that is language-independent? Need to include expr.h and optabs.h for lshift_cheap_p. Maximum number of case bit tests. FIXME: This should be derived from PARAM_CASE_VALUES_THRESHOLD and targetm.case_values_threshold(), or be its own param.
Function Documentation
|
static |
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 |
Builds and initializes static arrays initialized with values gathered from the SWTCH switch statement. Also creates statements that load values from them.
Make sure we do not generate arithmetics in a subrange.
References delete_basic_block(), edge_def::dest, and remove_edge().
|
static |
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 |
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_build2_loc, fold_convert_loc(), force_gimple_operand_gsi(), gimple_build_assign, 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(), NULL, switch_conv_info::range_min, switch_conv_info::range_size, TREE_TYPE, lang_hooks_for_types::type_for_mode, TYPE_MODE, lang_hooks::types, and update_stmt().
|
static |
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(), TREE_TYPE, unsigned_type_for(), and vNULL.
|
static |
Checks whether all but the FINAL_BB basic blocks are empty.
References switch_conv_info::reason.
|
static |
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 |
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 |
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 |
If all values in the constructor vector are the same, return the value. Otherwise return NULL_TREE. Not supposed to be called for empty vectors.
|
static |
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 CASE_LABEL, CASE_LOW, switch_conv_info::final_bb, find_edge(), gcc_assert, gimple_switch_label(), gimple_switch_num_labels(), label_to_block, switch_conv_info::range_min, single_succ_edge(), switch_conv_info::switch_bb, and tree_int_cst_lt().
|
static |
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.
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 updating.
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 |
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 |
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 |
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 |
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 |
Generates and appropriately inserts loads of default values at the position given by BSI. Returns the last inserted statement.
References create_artificial_label(), and UNKNOWN_LOCATION.
|
static |
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 |
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.
|
static |
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 |
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 transformation.
Cleanup:
References CDI_POST_DOMINATORS, dump_file, expand_location(), FOR_EACH_BB, free_dominance_info(), gimple_location(), last_stmt(), print_gimple_stmt(), and TDF_SLIM.
|
static |
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 |
The pass gate.
