-/* Switch Conversion converts variable initializations based on switch
- statements to initializations from a static array.
- Copyright (C) 2006, 2008 Free Software Foundation, Inc.
- Contributed by Martin Jambor <jamborm@suse.cz>
+/* Lower GIMPLE_SWITCH expressions to something more efficient than
+ a jump table.
+ Copyright (C) 2006-2015 Free Software Foundation, Inc.
This file is part of GCC.
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. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "params.h"
+#include "flags.h"
+#include "alias.h"
+#include "symtab.h"
+#include "tree.h"
+#include "fold-const.h"
+#include "varasm.h"
+#include "stor-layout.h"
+#include "predict.h"
+#include "hard-reg-set.h"
+#include "function.h"
+#include "dominance.h"
+#include "cfg.h"
+#include "cfganal.h"
+#include "basic-block.h"
+#include "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "gimple-expr.h"
+#include "gimple.h"
+#include "gimplify.h"
+#include "gimple-iterator.h"
+#include "gimplify-me.h"
+#include "gimple-ssa.h"
+#include "cgraph.h"
+#include "tree-cfg.h"
+#include "tree-phinodes.h"
+#include "stringpool.h"
+#include "tree-ssanames.h"
+#include "tree-pass.h"
+#include "gimple-pretty-print.h"
+#include "cfgloop.h"
+
+/* ??? For lang_hooks.types.type_for_mode, but is there a word_mode
+ type in the GIMPLE type system that is language-independent? */
+#include "langhooks.h"
+
+/* Need to include expr.h and optabs.h for lshift_cheap_p. */
+#include "rtl.h"
+#include "insn-config.h"
+#include "expmed.h"
+#include "dojump.h"
+#include "explow.h"
+#include "calls.h"
+#include "emit-rtl.h"
+#include "stmt.h"
+#include "expr.h"
+#include "insn-codes.h"
+#include "optabs.h"
+\f
+/* 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. */
+#define MAX_CASE_BIT_TESTS 3
+
+/* 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 basic_block
+hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
+ tree cond, edge e_true,
+ bool update_dominators)
+{
+ tree tmp;
+ gcond *cond_stmt;
+ edge e_false;
+ basic_block new_bb, split_bb = gsi_bb (*gsip);
+ bool dominated_e_true = false;
+
+ gcc_assert (e_true->src == split_bb);
+
+ if (update_dominators
+ && get_immediate_dominator (CDI_DOMINATORS, e_true->dest) == split_bb)
+ dominated_e_true = true;
+
+ tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL,
+ /*before=*/true, GSI_SAME_STMT);
+ cond_stmt = gimple_build_cond_from_tree (tmp, NULL_TREE, NULL_TREE);
+ gsi_insert_before (gsip, cond_stmt, GSI_SAME_STMT);
+
+ e_false = split_block (split_bb, cond_stmt);
+ new_bb = e_false->dest;
+ redirect_edge_pred (e_true, split_bb);
+
+ e_true->flags &= ~EDGE_FALLTHRU;
+ e_true->flags |= EDGE_TRUE_VALUE;
+
+ e_false->flags &= ~EDGE_FALLTHRU;
+ e_false->flags |= EDGE_FALSE_VALUE;
+ e_false->probability = REG_BR_PROB_BASE - e_true->probability;
+ e_false->count = split_bb->count - e_true->count;
+ new_bb->count = e_false->count;
+
+ if (update_dominators)
+ {
+ if (dominated_e_true)
+ set_immediate_dominator (CDI_DOMINATORS, e_true->dest, split_bb);
+ set_immediate_dominator (CDI_DOMINATORS, e_false->dest, split_bb);
+ }
+
+ return new_bb;
+}
+
+
+/* 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. */
+
+static bool
+expand_switch_using_bit_tests_p (tree range,
+ unsigned int uniq,
+ unsigned int count, bool speed_p)
+{
+ return (((uniq == 1 && count >= 3)
+ || (uniq == 2 && count >= 5)
+ || (uniq == 3 && count >= 6))
+ && lshift_cheap_p (speed_p)
+ && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0
+ && compare_tree_int (range, 0) > 0);
+}
+\f
+/* Implement switch statements with bit tests
+
+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-banch 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
+*/
+
+/* A case_bit_test represents a set of case nodes that may be
+ selected from using a bit-wise comparison. HI and LO hold
+ the integer to be tested against, TARGET_EDGE contains the
+ edge to the basic block to jump to upon success and BITS
+ counts the number of case nodes handled by this test,
+ typically the number of bits set in HI:LO. The LABEL field
+ is used to quickly identify all cases in this set without
+ looking at label_to_block for every case label. */
+
+struct case_bit_test
+{
+ wide_int mask;
+ edge target_edge;
+ tree label;
+ int bits;
+};
+
+/* 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...). */
+
+static int
+case_bit_test_cmp (const void *p1, const void *p2)
+{
+ const struct case_bit_test *const d1 = (const struct case_bit_test *) p1;
+ const struct case_bit_test *const d2 = (const struct case_bit_test *) p2;
+
+ if (d2->target_edge->count != d1->target_edge->count)
+ return d2->target_edge->count - d1->target_edge->count;
+ if (d2->bits != d1->bits)
+ return d2->bits - d1->bits;
+
+ /* Stabilize the sort. */
+ return LABEL_DECL_UID (d2->label) - LABEL_DECL_UID (d1->label);
+}
+
+/* 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. */
+
+static void
+emit_case_bit_tests (gswitch *swtch, tree index_expr,
+ tree minval, tree range, tree maxval)
+{
+ struct case_bit_test test[MAX_CASE_BIT_TESTS];
+ unsigned int i, j, k;
+ unsigned int count;
+
+ basic_block switch_bb = gimple_bb (swtch);
+ basic_block default_bb, new_default_bb, new_bb;
+ edge default_edge;
+ bool update_dom = dom_info_available_p (CDI_DOMINATORS);
+
+ vec<basic_block> bbs_to_fix_dom = vNULL;
+
+ tree index_type = TREE_TYPE (index_expr);
+ tree unsigned_index_type = unsigned_type_for (index_type);
+ unsigned int branch_num = gimple_switch_num_labels (swtch);
+
+ gimple_stmt_iterator gsi;
+ gassign *shift_stmt;
+
+ tree idx, tmp, csui;
+ tree word_type_node = lang_hooks.types.type_for_mode (word_mode, 1);
+ tree word_mode_zero = fold_convert (word_type_node, integer_zero_node);
+ tree word_mode_one = fold_convert (word_type_node, integer_one_node);
+ int prec = TYPE_PRECISION (word_type_node);
+ wide_int wone = wi::one (prec);
+
+ memset (&test, 0, sizeof (test));
+
+ /* Get the edge for the default case. */
+ tmp = gimple_switch_default_label (swtch);
+ default_bb = label_to_block (CASE_LABEL (tmp));
+ default_edge = find_edge (switch_bb, default_bb);
+
+ /* Go through all case labels, and collect the case labels, profile
+ counts, and other information we need to build the branch tests. */
+ count = 0;
+ for (i = 1; i < branch_num; i++)
+ {
+ unsigned int lo, hi;
+ tree cs = gimple_switch_label (swtch, i);
+ tree label = CASE_LABEL (cs);
+ edge e = find_edge (switch_bb, label_to_block (label));
+ for (k = 0; k < count; k++)
+ if (e == test[k].target_edge)
+ break;
+
+ if (k == count)
+ {
+ gcc_checking_assert (count < MAX_CASE_BIT_TESTS);
+ test[k].mask = wi::zero (prec);
+ test[k].target_edge = e;
+ test[k].label = label;
+ test[k].bits = 1;
+ count++;
+ }
+ else
+ test[k].bits++;
+
+ lo = tree_to_uhwi (int_const_binop (MINUS_EXPR,
+ CASE_LOW (cs), minval));
+ if (CASE_HIGH (cs) == NULL_TREE)
+ hi = lo;
+ else
+ hi = tree_to_uhwi (int_const_binop (MINUS_EXPR,
+ CASE_HIGH (cs), minval));
+
+ for (j = lo; j <= hi; j++)
+ test[k].mask |= wi::lshift (wone, j);
+ }
+
+ qsort (test, count, sizeof (*test), case_bit_test_cmp);
+
+ /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of
+ the minval subtractions, but it might make the mask constants more
+ expensive. So, compare the costs. */
+ if (compare_tree_int (minval, 0) > 0
+ && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
+ {
+ int cost_diff;
+ HOST_WIDE_INT m = tree_to_uhwi (minval);
+ rtx reg = gen_raw_REG (word_mode, 10000);
+ bool speed_p = optimize_bb_for_speed_p (gimple_bb (swtch));
+ cost_diff = set_rtx_cost (gen_rtx_PLUS (word_mode, reg,
+ GEN_INT (-m)), speed_p);
+ for (i = 0; i < count; i++)
+ {
+ rtx r = immed_wide_int_const (test[i].mask, word_mode);
+ cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r), speed_p);
+ r = immed_wide_int_const (wi::lshift (test[i].mask, m), word_mode);
+ cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r), speed_p);
+ }
+ if (cost_diff > 0)
+ {
+ for (i = 0; i < count; i++)
+ test[i].mask = wi::lshift (test[i].mask, m);
+ minval = build_zero_cst (TREE_TYPE (minval));
+ range = maxval;
+ }
+ }
+
+ /* 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. */
+ new_default_bb = split_edge (default_edge);
+
+ if (update_dom)
+ {
+ bbs_to_fix_dom.create (10);
+ bbs_to_fix_dom.quick_push (switch_bb);
+ bbs_to_fix_dom.quick_push (default_bb);
+ bbs_to_fix_dom.quick_push (new_default_bb);
+ }
+
+ /* Now build the test-and-branch code. */
+
+ gsi = gsi_last_bb (switch_bb);
+
+ /* idx = (unsigned)x - minval. */
+ idx = fold_convert (unsigned_index_type, index_expr);
+ idx = fold_build2 (MINUS_EXPR, unsigned_index_type, idx,
+ fold_convert (unsigned_index_type, minval));
+ idx = force_gimple_operand_gsi (&gsi, idx,
+ /*simple=*/true, NULL_TREE,
+ /*before=*/true, GSI_SAME_STMT);
+
+ /* if (idx > range) goto default */
+ range = force_gimple_operand_gsi (&gsi,
+ fold_convert (unsigned_index_type, range),
+ /*simple=*/true, NULL_TREE,
+ /*before=*/true, GSI_SAME_STMT);
+ tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range);
+ new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, default_edge, update_dom);
+ if (update_dom)
+ bbs_to_fix_dom.quick_push (new_bb);
+ gcc_assert (gimple_bb (swtch) == new_bb);
+ gsi = gsi_last_bb (new_bb);
+
+ /* 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. */
+ if (update_dom)
+ {
+ vec<basic_block> dom_bbs;
+ basic_block dom_son;
+
+ dom_bbs = get_dominated_by (CDI_DOMINATORS, new_bb);
+ FOR_EACH_VEC_ELT (dom_bbs, i, dom_son)
+ {
+ edge e = find_edge (new_bb, dom_son);
+ if (e && single_pred_p (e->dest))
+ continue;
+ set_immediate_dominator (CDI_DOMINATORS, dom_son, switch_bb);
+ bbs_to_fix_dom.safe_push (dom_son);
+ }
+ dom_bbs.release ();
+ }
+
+ /* csui = (1 << (word_mode) idx) */
+ csui = make_ssa_name (word_type_node);
+ tmp = fold_build2 (LSHIFT_EXPR, word_type_node, word_mode_one,
+ fold_convert (word_type_node, idx));
+ tmp = force_gimple_operand_gsi (&gsi, tmp,
+ /*simple=*/false, NULL_TREE,
+ /*before=*/true, GSI_SAME_STMT);
+ shift_stmt = gimple_build_assign (csui, tmp);
+ gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT);
+ update_stmt (shift_stmt);
+
+ /* for each unique set of cases:
+ if (const & csui) goto target */
+ for (k = 0; k < count; k++)
+ {
+ tmp = wide_int_to_tree (word_type_node, test[k].mask);
+ tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp);
+ tmp = force_gimple_operand_gsi (&gsi, tmp,
+ /*simple=*/true, NULL_TREE,
+ /*before=*/true, GSI_SAME_STMT);
+ tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero);
+ new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_edge,
+ update_dom);
+ if (update_dom)
+ bbs_to_fix_dom.safe_push (new_bb);
+ gcc_assert (gimple_bb (swtch) == new_bb);
+ gsi = gsi_last_bb (new_bb);
+ }
+
+ /* We should have removed all edges now. */
+ gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0);
+
+ /* If nothing matched, go to the default label. */
+ make_edge (gsi_bb (gsi), new_default_bb, EDGE_FALLTHRU);
+
+ /* The GIMPLE_SWITCH is now redundant. */
+ gsi_remove (&gsi, true);
+
+ if (update_dom)
+ {
+ /* Fix up the dominator tree. */
+ iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
+ bbs_to_fix_dom.release ();
+ }
+}
+\f
/*
Switch initialization conversion
The following pass changes simple initializations of scalars in a switch
-statement into initializations from a static array. Obviously, the values must
-be constant and known at compile time and a default branch must be
+statement into initializations from a static array. Obviously, the values
+must be constant and known at compile time and a default branch must be
provided. For example, the following code:
int a,b;
default:
a_4 = 16;
b_4 = 1;
+ break;
}
a_5 = PHI <a_1, a_2, a_3, a_4>
b_5 = PHI <b_1, b_2, b_3, b_4>
a_7 = 16;
b_7 = 1;
}
- b_b = PHI <b_6, b_7>
+ a_5 = PHI <a_6, a_7>
+ b_b = PHI <b_6, b_7>
There are further constraints. Specifically, the range of values across all
case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
-eight) times the number of the actual switch branches. */
+eight) times the number of the actual switch branches.
-#include "config.h"
-#include "system.h"
-#include "coretypes.h"
-#include "tm.h"
-#include <signal.h>
-
-#include "line-map.h"
-#include "params.h"
-#include "flags.h"
-#include "tree.h"
-#include "basic-block.h"
-#include "tree-flow.h"
-#include "tree-flow-inline.h"
-#include "tree-ssa-operands.h"
-#include "output.h"
-#include "input.h"
-#include "tree-pass.h"
-#include "diagnostic.h"
-#include "tree-dump.h"
-#include "timevar.h"
+This transformation was contributed by Martin Jambor, see this e-mail:
+ http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */
/* The main structure of the pass. */
struct switch_conv_info
{
- /* The expression used to decide the switch branch. (It is subsequently used
- as the index to the created array.) */
+ /* The expression used to decide the switch branch. */
tree index_expr;
- /* The following integer constants store the minimum value covered by the
- cases. */
+ /* The following integer constants store the minimum and maximum value
+ covered by the case labels. */
tree range_min;
+ tree range_max;
- /* The difference between the above two numbers, i.e. The size of the array
- that would have to be created by the transformation. */
+ /* The difference between the above two numbers. Stored here because it
+ is used in all the conversion heuristics, as well as for some of the
+ transformation, and it is expensive to re-compute it all the time. */
tree range_size;
- /* Basic block that contains the actual SWITCH_EXPR. */
+ /* Basic block that contains the actual GIMPLE_SWITCH. */
basic_block switch_bb;
- /* All branches of the switch statement must have a single successor stored in
- the following variable. */
+ /* Basic block that is the target of the default case. */
+ basic_block default_bb;
+
+ /* The single successor block of all branches out of the GIMPLE_SWITCH,
+ if such a block exists. Otherwise NULL. */
basic_block final_bb;
+ /* The probability of the default edge in the replaced switch. */
+ int default_prob;
+
+ /* The count of the default edge in the replaced switch. */
+ gcov_type default_count;
+
+ /* Combined count of all other (non-default) edges in the replaced switch. */
+ gcov_type other_count;
+
/* Number of phi nodes in the final bb (that we'll be replacing). */
int phi_count;
tree *default_values;
/* Constructors of new static arrays. */
- VEC (constructor_elt, gc) **constructors;
+ vec<constructor_elt, va_gc> **constructors;
/* Array of ssa names that are initialized with a value from a new static
array. */
switch expression is out of range. */
tree *target_outbound_names;
- /* The probability of the default edge in the replaced switch. */
- int default_prob;
-
- /* The count of the default edge in the replaced switch. */
- gcov_type default_count;
-
- /* Combined count of all other (non-default) edges in the replaced switch. */
- gcov_type other_count;
-
/* The first load statement that loads a temporary from a new static array.
*/
gimple arr_ref_first;
/* String reason why the case wasn't a good candidate that is written to the
dump file, if there is one. */
const char *reason;
-};
-
-/* Global pass info. */
-static struct switch_conv_info info;
+ /* Parameters for expand_switch_using_bit_tests. Should be computed
+ the same way as in expand_case. */
+ unsigned int uniq;
+ unsigned int count;
+};
-/* 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. */
+/* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */
-static bool
-check_range (gimple swtch)
+static void
+collect_switch_conv_info (gswitch *swtch, struct switch_conv_info *info)
{
- tree min_case, max_case;
unsigned int branch_num = gimple_switch_num_labels (swtch);
- tree range_max;
+ tree min_case, max_case;
+ unsigned int count, i;
+ edge e, e_default;
+ edge_iterator ei;
+
+ memset (info, 0, sizeof (*info));
/* The gimplifier has already sorted the cases by CASE_LOW and ensured there
- is a default label which is the last in the vector. */
+ is a default label which is the first in the vector.
+ Collect the bits we can deduce from the CFG. */
+ info->index_expr = gimple_switch_index (swtch);
+ info->switch_bb = gimple_bb (swtch);
+ info->default_bb =
+ label_to_block (CASE_LABEL (gimple_switch_default_label (swtch)));
+ e_default = find_edge (info->switch_bb, info->default_bb);
+ info->default_prob = e_default->probability;
+ info->default_count = e_default->count;
+ FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
+ if (e != e_default)
+ info->other_count += e->count;
+
+ /* See if there is one common successor block for all branch
+ targets. If it exists, record it in FINAL_BB.
+ Start with the destination of the default case as guess
+ or its destination in case it is a forwarder block. */
+ if (! single_pred_p (e_default->dest))
+ info->final_bb = e_default->dest;
+ else if (single_succ_p (e_default->dest)
+ && ! single_pred_p (single_succ (e_default->dest)))
+ info->final_bb = single_succ (e_default->dest);
+ /* Require that all switch destinations are either that common
+ FINAL_BB or a forwarder to it. */
+ if (info->final_bb)
+ FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
+ {
+ if (e->dest == info->final_bb)
+ continue;
- min_case = gimple_switch_label (swtch, 1);
- info.range_min = CASE_LOW (min_case);
+ if (single_pred_p (e->dest)
+ && single_succ_p (e->dest)
+ && single_succ (e->dest) == info->final_bb)
+ continue;
- gcc_assert (branch_num > 1);
- gcc_assert (CASE_LOW (gimple_switch_label (swtch, 0)) == NULL_TREE);
+ info->final_bb = NULL;
+ break;
+ }
+
+ /* Get upper and lower bounds of case values, and the covered range. */
+ min_case = gimple_switch_label (swtch, 1);
max_case = gimple_switch_label (swtch, branch_num - 1);
+
+ info->range_min = CASE_LOW (min_case);
if (CASE_HIGH (max_case) != NULL_TREE)
- range_max = CASE_HIGH (max_case);
+ info->range_max = CASE_HIGH (max_case);
else
- range_max = CASE_LOW (max_case);
+ info->range_max = CASE_LOW (max_case);
- gcc_assert (info.range_min);
- gcc_assert (range_max);
+ info->range_size =
+ int_const_binop (MINUS_EXPR, info->range_max, info->range_min);
- info.range_size = int_const_binop (MINUS_EXPR, range_max, info.range_min, 0);
+ /* 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. */
+ count = 0;
+ for (i = 1; i < branch_num; i++)
+ {
+ tree elt = gimple_switch_label (swtch, i);
+ count++;
+ if (CASE_HIGH (elt)
+ && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt)))
+ count++;
+ }
+ info->count = count;
+
+ /* 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. */
+ info->uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1;
+}
+
+/* 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. */
- gcc_assert (info.range_size);
- if (!host_integerp (info.range_size, 1))
+static bool
+check_range (struct switch_conv_info *info)
+{
+ gcc_assert (info->range_size);
+ if (!tree_fits_uhwi_p (info->range_size))
{
- info.reason = "index range way too large or otherwise unusable.\n";
+ info->reason = "index range way too large or otherwise unusable";
return false;
}
- if ((unsigned HOST_WIDE_INT) tree_low_cst (info.range_size, 1)
- > ((unsigned) branch_num * SWITCH_CONVERSION_BRANCH_RATIO))
+ if (tree_to_uhwi (info->range_size)
+ > ((unsigned) info->count * SWITCH_CONVERSION_BRANCH_RATIO))
{
- info.reason = "the maximum range-branch ratio exceeded.\n";
+ info->reason = "the maximum range-branch ratio exceeded";
return false;
}
return true;
}
-/* Checks the given CS switch case whether it is suitable for conversion
- (whether all but the default basic blocks are empty and so on). If it is,
- adds the case to the branch list along with values for the defined variables
- and returns true. Otherwise returns false. */
+/* Checks whether all but the FINAL_BB basic blocks are empty. */
static bool
-check_process_case (tree cs)
+check_all_empty_except_final (struct switch_conv_info *info)
{
- tree ldecl;
- basic_block label_bb, following_bb;
edge e;
+ edge_iterator ei;
- ldecl = CASE_LABEL (cs);
- label_bb = label_to_block (ldecl);
-
- e = find_edge (info.switch_bb, label_bb);
- gcc_assert (e);
-
- if (CASE_LOW (cs) == NULL_TREE)
- {
- /* Default branch. */
- info.default_prob = e->probability;
- info.default_count = e->count;
- }
- else
- info.other_count += e->count;
-
- if (!label_bb)
- {
- info.reason = " Bad case - cs BB label is NULL\n";
- return false;
- }
-
- if (!single_pred_p (label_bb))
+ FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
{
- if (info.final_bb && info.final_bb != label_bb)
- {
- info.reason = " Bad case - a non-final BB has two predecessors\n";
- return false; /* sth complex going on in this branch */
- }
+ if (e->dest == info->final_bb)
+ continue;
- following_bb = label_bb;
- }
- else
- {
- if (!empty_block_p (label_bb))
+ if (!empty_block_p (e->dest))
{
- info.reason = " Bad case - a non-final BB not empty\n";
+ info->reason = "bad case - a non-final BB not empty";
return false;
}
-
- e = single_succ_edge (label_bb);
- following_bb = single_succ (label_bb);
- }
-
- if (!info.final_bb)
- info.final_bb = following_bb;
- else if (info.final_bb != following_bb)
- {
- info.reason = " Bad case - different final BB\n";
- return false; /* the only successor is not common for all the branches */
}
return true;
phi nodes are OK, otherwise false. */
static bool
-check_final_bb (void)
+check_final_bb (struct switch_conv_info *info)
{
- gimple_stmt_iterator gsi;
+ gphi_iterator gsi;
- info.phi_count = 0;
- for (gsi = gsi_start_phis (info.final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ info->phi_count = 0;
+ for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
- gimple phi = gsi_stmt (gsi);
+ gphi *phi = gsi.phi ();
unsigned int i;
- info.phi_count++;
+ info->phi_count++;
for (i = 0; i < gimple_phi_num_args (phi); i++)
{
basic_block bb = gimple_phi_arg_edge (phi, i)->src;
- if (bb == info.switch_bb
- || (single_pred_p (bb) && single_pred (bb) == info.switch_bb))
+ if (bb == info->switch_bb
+ || (single_pred_p (bb) && single_pred (bb) == info->switch_bb))
{
tree reloc, val;
val = gimple_phi_arg_def (phi, i);
if (!is_gimple_ip_invariant (val))
{
- info.reason = " Non-invariant value from a case\n";
+ info->reason = "non-invariant value from a case";
return false; /* Non-invariant argument. */
}
reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
|| (!flag_pic && reloc == NULL_TREE))
{
if (reloc)
- info.reason
- = " Value from a case would need runtime relocations\n";
+ info->reason
+ = "value from a case would need runtime relocations";
else
- info.reason
- = " Value from a case is not a valid initializer\n";
+ info->reason
+ = "value from a case is not a valid initializer";
return false;
}
}
vectors that will become constructors of new arrays. */
static void
-create_temp_arrays (void)
+create_temp_arrays (struct switch_conv_info *info)
{
int i;
- info.default_values = (tree *) xcalloc (info.phi_count, sizeof (tree));
- info.constructors = (VEC (constructor_elt, gc) **) xcalloc (info.phi_count,
- sizeof (tree));
- info.target_inbound_names = (tree *) xcalloc (info.phi_count, sizeof (tree));
- info.target_outbound_names = (tree *) xcalloc (info.phi_count,
- sizeof (tree));
-
- for (i = 0; i < info.phi_count; i++)
- info.constructors[i]
- = VEC_alloc (constructor_elt, gc, tree_low_cst (info.range_size, 1) + 1);
+ info->default_values = XCNEWVEC (tree, info->phi_count * 3);
+ /* ??? Macros do not support multi argument templates in their
+ argument list. We create a typedef to work around that problem. */
+ typedef vec<constructor_elt, va_gc> *vec_constructor_elt_gc;
+ info->constructors = XCNEWVEC (vec_constructor_elt_gc, info->phi_count);
+ info->target_inbound_names = info->default_values + info->phi_count;
+ info->target_outbound_names = info->target_inbound_names + info->phi_count;
+ for (i = 0; i < info->phi_count; i++)
+ vec_alloc (info->constructors[i], tree_to_uhwi (info->range_size) + 1);
}
/* Free the arrays created by create_temp_arrays(). The vectors that are
already become constructors and must be preserved. */
static void
-free_temp_arrays (void)
+free_temp_arrays (struct switch_conv_info *info)
{
- free (info.constructors);
- free (info.default_values);
- free (info.target_inbound_names);
- free (info.target_outbound_names);
+ XDELETEVEC (info->constructors);
+ XDELETEVEC (info->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 void
-gather_default_values (tree default_case)
+gather_default_values (tree default_case, struct switch_conv_info *info)
{
- gimple_stmt_iterator gsi;
+ gphi_iterator gsi;
basic_block bb = label_to_block (CASE_LABEL (default_case));
edge e;
int i = 0;
gcc_assert (CASE_LOW (default_case) == NULL_TREE);
- if (bb == info.final_bb)
- e = find_edge (info.switch_bb, bb);
+ if (bb == info->final_bb)
+ e = find_edge (info->switch_bb, bb);
else
e = single_succ_edge (bb);
- for (gsi = gsi_start_phis (info.final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
- gimple phi = gsi_stmt (gsi);
+ gphi *phi = gsi.phi ();
tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
gcc_assert (val);
- info.default_values[i++] = val;
+ info->default_values[i++] = val;
}
}
order of phi nodes. SWTCH is the switch statement being converted. */
static void
-build_constructors (gimple swtch)
+build_constructors (gswitch *swtch, struct switch_conv_info *info)
{
unsigned i, branch_num = gimple_switch_num_labels (swtch);
- tree pos = info.range_min;
+ tree pos = info->range_min;
for (i = 1; i < branch_num; i++)
{
basic_block bb = label_to_block (CASE_LABEL (cs));
edge e;
tree high;
- gimple_stmt_iterator gsi;
+ gphi_iterator gsi;
int j;
- if (bb == info.final_bb)
- e = find_edge (info.switch_bb, bb);
+ if (bb == info->final_bb)
+ e = find_edge (info->switch_bb, bb);
else
e = single_succ_edge (bb);
gcc_assert (e);
while (tree_int_cst_lt (pos, CASE_LOW (cs)))
{
int k;
- for (k = 0; k < info.phi_count; k++)
+ for (k = 0; k < info->phi_count; k++)
{
- constructor_elt *elt;
+ constructor_elt elt;
- elt = VEC_quick_push (constructor_elt,
- info.constructors[k], NULL);
- elt->index = int_const_binop (MINUS_EXPR, pos,
- info.range_min, 0);
- elt->value = info.default_values[k];
+ elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
+ elt.value
+ = unshare_expr_without_location (info->default_values[k]);
+ info->constructors[k]->quick_push (elt);
}
- pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0);
+ pos = int_const_binop (PLUS_EXPR, pos,
+ build_int_cst (TREE_TYPE (pos), 1));
}
gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
high = CASE_HIGH (cs);
else
high = CASE_LOW (cs);
- for (gsi = gsi_start_phis (info.final_bb);
+ for (gsi = gsi_start_phis (info->final_bb);
!gsi_end_p (gsi); gsi_next (&gsi))
{
- gimple phi = gsi_stmt (gsi);
+ gphi *phi = gsi.phi ();
tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
tree low = CASE_LOW (cs);
pos = CASE_LOW (cs);
- do
+ do
{
- constructor_elt *elt;
+ constructor_elt elt;
- elt = VEC_quick_push (constructor_elt,
- info.constructors[j], NULL);
- elt->index = int_const_binop (MINUS_EXPR, pos, info.range_min, 0);
- elt->value = val;
+ elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
+ elt.value = unshare_expr_without_location (val);
+ info->constructors[j]->quick_push (elt);
- pos = int_const_binop (PLUS_EXPR, pos, integer_one_node, 0);
+ pos = int_const_binop (PLUS_EXPR, pos,
+ build_int_cst (TREE_TYPE (pos), 1));
} while (!tree_int_cst_lt (high, pos)
&& tree_int_cst_lt (low, pos));
j++;
vectors. */
static tree
-constructor_contains_same_values_p (VEC (constructor_elt, gc) *vec)
+constructor_contains_same_values_p (vec<constructor_elt, va_gc> *vec)
{
- int i, len = VEC_length (constructor_elt, vec);
+ unsigned int i;
tree prev = NULL_TREE;
+ constructor_elt *elt;
- for (i = 0; i < len; i++)
+ FOR_EACH_VEC_SAFE_ELT (vec, i, elt)
{
- constructor_elt *elt = VEC_index (constructor_elt, vec, i);
-
if (!prev)
prev = elt->value;
else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST))
return prev;
}
+/* 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 tree
+array_value_type (gswitch *swtch, tree type, int num,
+ struct switch_conv_info *info)
+{
+ unsigned int i, len = vec_safe_length (info->constructors[num]);
+ constructor_elt *elt;
+ machine_mode mode;
+ int sign = 0;
+ tree smaller_type;
+
+ if (!INTEGRAL_TYPE_P (type))
+ return type;
+
+ mode = GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type)));
+ if (GET_MODE_SIZE (TYPE_MODE (type)) <= GET_MODE_SIZE (mode))
+ return type;
+
+ if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32))
+ return type;
+
+ FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
+ {
+ wide_int cst;
+
+ if (TREE_CODE (elt->value) != INTEGER_CST)
+ return type;
+
+ cst = elt->value;
+ while (1)
+ {
+ unsigned int prec = GET_MODE_BITSIZE (mode);
+ if (prec > HOST_BITS_PER_WIDE_INT)
+ return type;
+
+ if (sign >= 0 && cst == wi::zext (cst, prec))
+ {
+ if (sign == 0 && cst == wi::sext (cst, prec))
+ break;
+ sign = 1;
+ break;
+ }
+ if (sign <= 0 && cst == wi::sext (cst, prec))
+ {
+ sign = -1;
+ break;
+ }
+
+ if (sign == 1)
+ sign = 0;
+
+ mode = GET_MODE_WIDER_MODE (mode);
+ if (mode == VOIDmode
+ || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (TYPE_MODE (type)))
+ return type;
+ }
+ }
+
+ if (sign == 0)
+ sign = TYPE_UNSIGNED (type) ? 1 : -1;
+ smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0);
+ if (GET_MODE_SIZE (TYPE_MODE (type))
+ <= GET_MODE_SIZE (TYPE_MODE (smaller_type)))
+ return type;
+
+ return smaller_type;
+}
+
/* 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
new array. */
static void
-build_one_array (gimple swtch, int num, tree arr_index_type, gimple phi,
- tree tidx)
+build_one_array (gswitch *swtch, int num, tree arr_index_type,
+ gphi *phi, tree tidx, struct switch_conv_info *info)
{
tree name, cst;
gimple load;
gimple_stmt_iterator gsi = gsi_for_stmt (swtch);
location_t loc = gimple_location (swtch);
- gcc_assert (info.default_values[num]);
+ gcc_assert (info->default_values[num]);
- name = make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi)), NULL);
- info.target_inbound_names[num] = name;
+ name = copy_ssa_name (PHI_RESULT (phi));
+ info->target_inbound_names[num] = name;
- cst = constructor_contains_same_values_p (info.constructors[num]);
+ cst = constructor_contains_same_values_p (info->constructors[num]);
if (cst)
load = gimple_build_assign (name, cst);
else
{
- tree array_type, ctor, decl, value_type, fetch;
+ tree array_type, ctor, decl, value_type, fetch, default_type;
- value_type = TREE_TYPE (info.default_values[num]);
+ default_type = TREE_TYPE (info->default_values[num]);
+ value_type = array_value_type (swtch, default_type, num, info);
array_type = build_array_type (value_type, arr_index_type);
- ctor = build_constructor (array_type, info.constructors[num]);
+ if (default_type != value_type)
+ {
+ unsigned int i;
+ constructor_elt *elt;
+
+ FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
+ elt->value = fold_convert (value_type, elt->value);
+ }
+ ctor = build_constructor (array_type, info->constructors[num]);
TREE_CONSTANT (ctor) = true;
+ TREE_STATIC (ctor) = true;
decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type);
TREE_STATIC (decl) = 1;
DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
DECL_ARTIFICIAL (decl) = 1;
+ DECL_IGNORED_P (decl) = 1;
TREE_CONSTANT (decl) = 1;
- add_referenced_var (decl);
- varpool_mark_needed_node (varpool_node (decl));
- varpool_finalize_decl (decl);
+ TREE_READONLY (decl) = 1;
+ DECL_IGNORED_P (decl) = 1;
+ varpool_node::finalize_decl (decl);
fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
NULL_TREE);
+ if (default_type != value_type)
+ {
+ fetch = fold_convert (default_type, fetch);
+ fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE,
+ true, GSI_SAME_STMT);
+ }
load = gimple_build_assign (name, fetch);
}
- SSA_NAME_DEF_STMT (name) = load;
gsi_insert_before (&gsi, load, GSI_SAME_STMT);
update_stmt (load);
- info.arr_ref_last = load;
+ info->arr_ref_last = load;
}
/* Builds and initializes static arrays initialized with values gathered from
them. */
static void
-build_arrays (gimple swtch)
+build_arrays (gswitch *swtch, struct switch_conv_info *info)
{
tree arr_index_type;
- tree tidx, sub, tmp;
+ tree tidx, sub, utype;
gimple stmt;
gimple_stmt_iterator gsi;
+ gphi_iterator gpi;
int i;
+ location_t loc = gimple_location (swtch);
gsi = gsi_for_stmt (swtch);
- arr_index_type = build_index_type (info.range_size);
- tmp = create_tmp_var (arr_index_type, "csti");
- add_referenced_var (tmp);
- tidx = make_ssa_name (tmp, NULL);
- sub = fold_build2 (MINUS_EXPR, TREE_TYPE (info.index_expr), info.index_expr,
- fold_convert (TREE_TYPE (info.index_expr),
- info.range_min));
- sub = force_gimple_operand_gsi (&gsi, fold_convert (arr_index_type, sub),
+ /* Make sure we do not generate arithmetics in a subrange. */
+ utype = TREE_TYPE (info->index_expr);
+ if (TREE_TYPE (utype))
+ utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1);
+ else
+ utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
+
+ arr_index_type = build_index_type (info->range_size);
+ tidx = make_ssa_name (utype);
+ sub = fold_build2_loc (loc, MINUS_EXPR, utype,
+ fold_convert_loc (loc, utype, info->index_expr),
+ fold_convert_loc (loc, utype, info->range_min));
+ sub = force_gimple_operand_gsi (&gsi, sub,
false, NULL, true, GSI_SAME_STMT);
stmt = gimple_build_assign (tidx, sub);
- SSA_NAME_DEF_STMT (tidx) = stmt;
gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
update_stmt (stmt);
- info.arr_ref_first = stmt;
+ info->arr_ref_first = stmt;
- for (gsi = gsi_start_phis (info.final_bb), i = 0;
- !gsi_end_p (gsi); gsi_next (&gsi), i++)
- build_one_array (swtch, i, arr_index_type, gsi_stmt (gsi), tidx);
+ for (gpi = gsi_start_phis (info->final_bb), i = 0;
+ !gsi_end_p (gpi); gsi_next (&gpi), i++)
+ build_one_array (swtch, i, arr_index_type, gpi.phi (), tidx, info);
}
/* Generates and appropriately inserts loads of default values at the position
given by BSI. Returns the last inserted statement. */
-static gimple
-gen_def_assigns (gimple_stmt_iterator *gsi)
+static gassign *
+gen_def_assigns (gimple_stmt_iterator *gsi, struct switch_conv_info *info)
{
int i;
- gimple assign = NULL;
+ gassign *assign = NULL;
- for (i = 0; i < info.phi_count; i++)
+ for (i = 0; i < info->phi_count; i++)
{
- tree name
- = make_ssa_name (SSA_NAME_VAR (info.target_inbound_names[i]), NULL);
-
- info.target_outbound_names[i] = name;
- assign = gimple_build_assign (name, info.default_values[i]);
- SSA_NAME_DEF_STMT (name) = assign;
+ tree name = copy_ssa_name (info->target_inbound_names[i]);
+ info->target_outbound_names[i] = name;
+ assign = gimple_build_assign (name, info->default_values[i]);
gsi_insert_before (gsi, assign, GSI_SAME_STMT);
update_stmt (assign);
}
bbf description in the comment below). */
static void
-fix_phi_nodes (edge e1f, edge e2f, basic_block bbf)
+fix_phi_nodes (edge e1f, edge e2f, basic_block bbf,
+ struct switch_conv_info *info)
{
- gimple_stmt_iterator gsi;
+ gphi_iterator gsi;
int i;
for (gsi = gsi_start_phis (bbf), i = 0;
!gsi_end_p (gsi); gsi_next (&gsi), i++)
{
- gimple phi = gsi_stmt (gsi);
- add_phi_arg (phi, info.target_inbound_names[i], e1f);
- add_phi_arg (phi, info.target_outbound_names[i], e2f);
+ gphi *phi = gsi.phi ();
+ add_phi_arg (phi, info->target_inbound_names[i], e1f, UNKNOWN_LOCATION);
+ add_phi_arg (phi, info->target_outbound_names[i], e2f, UNKNOWN_LOCATION);
}
-
}
/* Creates a check whether the switch expression value actually falls into the
*/
static void
-gen_inbound_check (gimple swtch)
+gen_inbound_check (gswitch *swtch, struct switch_conv_info *info)
{
tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION);
tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION);
- gimple label1, label2, label3;
-
- tree utype;
- tree tmp_u_1, tmp_u_2, tmp_u_var;
- tree cast;
- gimple cast_assign, minus_assign;
- tree ulb, minus;
+ glabel *label1, *label2, *label3;
+ tree utype, tidx;
tree bound;
- gimple cond_stmt;
+ gcond *cond_stmt;
- gimple last_assign;
+ gassign *last_assign;
gimple_stmt_iterator gsi;
basic_block bb0, bb1, bb2, bbf, bbd;
edge e01, e02, e21, e1d, e1f, e2f;
+ location_t loc = gimple_location (swtch);
+
+ gcc_assert (info->default_values);
- gcc_assert (info.default_values);
bb0 = gimple_bb (swtch);
- /* Make sure we do not generate arithmetics in a subrange. */
- if (TREE_TYPE (TREE_TYPE (info.index_expr)))
- utype = unsigned_type_for (TREE_TYPE (TREE_TYPE (info.index_expr)));
- else
- utype = unsigned_type_for (TREE_TYPE (info.index_expr));
+ tidx = gimple_assign_lhs (info->arr_ref_first);
+ utype = TREE_TYPE (tidx);
/* (end of) block 0 */
- gsi = gsi_for_stmt (info.arr_ref_first);
- tmp_u_var = create_tmp_var (utype, "csui");
- add_referenced_var (tmp_u_var);
- tmp_u_1 = make_ssa_name (tmp_u_var, NULL);
-
- cast = fold_convert (utype, info.index_expr);
- cast_assign = gimple_build_assign (tmp_u_1, cast);
- SSA_NAME_DEF_STMT (tmp_u_1) = cast_assign;
- gsi_insert_before (&gsi, cast_assign, GSI_SAME_STMT);
- update_stmt (cast_assign);
-
- ulb = fold_convert (utype, info.range_min);
- minus = fold_build2 (MINUS_EXPR, utype, tmp_u_1, ulb);
- minus = force_gimple_operand_gsi (&gsi, minus, false, NULL, true,
- GSI_SAME_STMT);
- tmp_u_2 = make_ssa_name (tmp_u_var, NULL);
- minus_assign = gimple_build_assign (tmp_u_2, minus);
- SSA_NAME_DEF_STMT (tmp_u_2) = minus_assign;
- gsi_insert_before (&gsi, minus_assign, GSI_SAME_STMT);
- update_stmt (minus_assign);
-
- bound = fold_convert (utype, info.range_size);
- cond_stmt = gimple_build_cond (LE_EXPR, tmp_u_2, bound, NULL_TREE, NULL_TREE);
+ gsi = gsi_for_stmt (info->arr_ref_first);
+ gsi_next (&gsi);
+
+ bound = fold_convert_loc (loc, utype, info->range_size);
+ cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
update_stmt (cond_stmt);
/* block 2 */
- gsi = gsi_for_stmt (info.arr_ref_first);
label2 = gimple_build_label (label_decl2);
gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
- last_assign = gen_def_assigns (&gsi);
+ last_assign = gen_def_assigns (&gsi, info);
/* block 1 */
- gsi = gsi_for_stmt (info.arr_ref_first);
label1 = gimple_build_label (label_decl1);
gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
/* block F */
- gsi = gsi_start_bb (info.final_bb);
+ gsi = gsi_start_bb (info->final_bb);
label3 = gimple_build_label (label_decl3);
gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
bb1 = e21->dest;
remove_edge (e21);
- e1d = split_block (bb1, info.arr_ref_last);
+ e1d = split_block (bb1, info->arr_ref_last);
bbd = e1d->dest;
remove_edge (e1d);
/* flags and profiles of the edge for in-range values */
e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
- e01->probability = REG_BR_PROB_BASE - info.default_prob;
- e01->count = info.other_count;
+ e01->probability = REG_BR_PROB_BASE - info->default_prob;
+ e01->count = info->other_count;
/* flags and profiles of the edge taking care of out-of-range values */
e02->flags &= ~EDGE_FALLTHRU;
e02->flags |= EDGE_FALSE_VALUE;
- e02->probability = info.default_prob;
- e02->count = info.default_count;
+ e02->probability = info->default_prob;
+ e02->count = info->default_count;
- bbf = info.final_bb;
+ bbf = info->final_bb;
e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
e1f->probability = REG_BR_PROB_BASE;
- e1f->count = info.other_count;
+ e1f->count = info->other_count;
e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
e2f->probability = REG_BR_PROB_BASE;
- e2f->count = info.default_count;
+ e2f->count = info->default_count;
/* frequencies of the new BBs */
bb1->frequency = EDGE_FREQUENCY (e01);
bb2->frequency = EDGE_FREQUENCY (e02);
bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f);
- prune_bbs (bbd, info.final_bb); /* To keep calc_dfs_tree() in dominance.c
- happy. */
+ /* Tidy blocks that have become unreachable. */
+ prune_bbs (bbd, info->final_bb);
- fix_phi_nodes (e1f, e2f, bbf);
+ /* Fixup the PHI nodes in bbF. */
+ fix_phi_nodes (e1f, e2f, bbf, info);
- free_dominance_info (CDI_DOMINATORS);
- free_dominance_info (CDI_POST_DOMINATORS);
+ /* Fix the dominator tree, if it is available. */
+ if (dom_info_available_p (CDI_DOMINATORS))
+ {
+ vec<basic_block> bbs_to_fix_dom;
+
+ set_immediate_dominator (CDI_DOMINATORS, bb1, bb0);
+ set_immediate_dominator (CDI_DOMINATORS, bb2, bb0);
+ if (! get_immediate_dominator (CDI_DOMINATORS, bbf))
+ /* If bbD was the immediate dominator ... */
+ set_immediate_dominator (CDI_DOMINATORS, bbf, bb0);
+
+ bbs_to_fix_dom.create (4);
+ bbs_to_fix_dom.quick_push (bb0);
+ bbs_to_fix_dom.quick_push (bb1);
+ bbs_to_fix_dom.quick_push (bb2);
+ bbs_to_fix_dom.quick_push (bbf);
+
+ iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
+ bbs_to_fix_dom.release ();
+ }
}
/* 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. */
+ 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. */
-static bool
-process_switch (gimple swtch)
+static const char *
+process_switch (gswitch *swtch)
{
- unsigned int i, branch_num = gimple_switch_num_labels (swtch);
- tree index_type;
+ struct switch_conv_info info;
- /* Operand 2 is either NULL_TREE or a vector of cases (stmt.c). */
- if (branch_num < 2)
- {
- info.reason = "switch has no labels\n";
- return false;
- }
+ /* Group case labels so that we get the right results from the heuristics
+ that decide on the code generation approach for this switch. */
+ group_case_labels_stmt (swtch);
+
+ /* If this switch is now a degenerate case with only a default label,
+ there is nothing left for us to do. */
+ if (gimple_switch_num_labels (swtch) < 2)
+ return "switch is a degenerate case";
+
+ collect_switch_conv_info (swtch, &info);
+
+ /* No error markers should reach here (they should be filtered out
+ during gimplification). */
+ gcc_checking_assert (TREE_TYPE (info.index_expr) != error_mark_node);
+
+ /* A switch on a constant should have been optimized in tree-cfg-cleanup. */
+ gcc_checking_assert (! TREE_CONSTANT (info.index_expr));
- info.final_bb = NULL;
- info.switch_bb = gimple_bb (swtch);
- info.index_expr = gimple_switch_index (swtch);
- index_type = TREE_TYPE (info.index_expr);
- info.arr_ref_first = NULL;
- info.arr_ref_last = NULL;
- info.default_prob = 0;
- info.default_count = 0;
- info.other_count = 0;
-
- /* An ERROR_MARK occurs for various reasons including invalid data type.
- (comment from stmt.c) */
- if (index_type == error_mark_node)
+ if (info.uniq <= MAX_CASE_BIT_TESTS)
{
- info.reason = "index error.\n";
- return false;
+ if (expand_switch_using_bit_tests_p (info.range_size,
+ info.uniq, info.count,
+ optimize_bb_for_speed_p
+ (gimple_bb (swtch))))
+ {
+ if (dump_file)
+ fputs (" expanding as bit test is preferable\n", dump_file);
+ emit_case_bit_tests (swtch, info.index_expr, info.range_min,
+ info.range_size, info.range_max);
+ loops_state_set (LOOPS_NEED_FIXUP);
+ return NULL;
+ }
+
+ if (info.uniq <= 2)
+ /* This will be expanded as a decision tree in stmt.c:expand_case. */
+ return " expanding as jumps is preferable";
}
+ /* If there is no common successor, we cannot do the transformation. */
+ if (! info.final_bb)
+ return "no common successor to all case label target blocks found";
+
/* Check the case label values are within reasonable range: */
- if (!check_range (swtch))
- return false;
+ if (!check_range (&info))
+ {
+ gcc_assert (info.reason);
+ return info.reason;
+ }
/* For all the cases, see whether they are empty, the assignments they
represent constant and so on... */
- for (i = 0; i < branch_num; i++)
- if (!check_process_case (gimple_switch_label (swtch, i)))
- {
- if (dump_file)
- fprintf (dump_file, "Processing of case %i failed\n", i);
- return false;
- }
-
- if (!check_final_bb ())
- return false;
+ if (! check_all_empty_except_final (&info))
+ {
+ gcc_assert (info.reason);
+ return info.reason;
+ }
+ if (!check_final_bb (&info))
+ {
+ gcc_assert (info.reason);
+ return info.reason;
+ }
/* At this point all checks have passed and we can proceed with the
transformation. */
- create_temp_arrays ();
- gather_default_values (gimple_switch_label (swtch, 0));
- build_constructors (swtch);
+ create_temp_arrays (&info);
+ gather_default_values (gimple_switch_default_label (swtch), &info);
+ build_constructors (swtch, &info);
- build_arrays (swtch); /* Build the static arrays and assignments. */
- gen_inbound_check (swtch); /* Build the bounds check. */
+ build_arrays (swtch, &info); /* Build the static arrays and assignments. */
+ gen_inbound_check (swtch, &info); /* Build the bounds check. */
/* Cleanup: */
- free_temp_arrays ();
- return true;
+ free_temp_arrays (&info);
+ return NULL;
}
/* The main function of the pass scans statements for switches and invokes
process_switch on them. */
-static unsigned int
-do_switchconv (void)
+namespace {
+
+const pass_data pass_data_convert_switch =
+{
+ GIMPLE_PASS, /* type */
+ "switchconv", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_TREE_SWITCH_CONVERSION, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_update_ssa, /* todo_flags_finish */
+};
+
+class pass_convert_switch : public gimple_opt_pass
+{
+public:
+ pass_convert_switch (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_convert_switch, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *) { return flag_tree_switch_conversion != 0; }
+ virtual unsigned int execute (function *);
+
+}; // class pass_convert_switch
+
+unsigned int
+pass_convert_switch::execute (function *fun)
{
basic_block bb;
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, fun)
{
+ const char *failure_reason;
gimple stmt = last_stmt (bb);
if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
{
"SWITCH statement (%s:%d) : ------- \n",
loc.file, loc.line);
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
- fprintf (dump_file, "\n");
+ putc ('\n', dump_file);
}
- info.reason = NULL;
- if (process_switch (stmt))
+ failure_reason = process_switch (as_a <gswitch *> (stmt));
+ if (! failure_reason)
{
if (dump_file)
{
- fprintf (dump_file, "Switch converted\n");
- fprintf (dump_file, "--------------------------------\n");
+ fputs ("Switch converted\n", dump_file);
+ fputs ("--------------------------------\n", dump_file);
}
+
+ /* 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. */
+ free_dominance_info (CDI_POST_DOMINATORS);
}
else
{
if (dump_file)
{
- gcc_assert (info.reason);
- fprintf (dump_file, "Bailing out - ");
- fprintf (dump_file, info.reason);
- fprintf (dump_file, "--------------------------------\n");
+ fputs ("Bailing out - ", dump_file);
+ fputs (failure_reason, dump_file);
+ fputs ("\n--------------------------------\n", dump_file);
}
}
}
return 0;
}
-/* The pass gate. */
+} // anon namespace
-static bool
-switchconv_gate (void)
+gimple_opt_pass *
+make_pass_convert_switch (gcc::context *ctxt)
{
- return flag_tree_switch_conversion != 0;
+ return new pass_convert_switch (ctxt);
}
-
-struct gimple_opt_pass pass_convert_switch =
-{
- {
- GIMPLE_PASS,
- "switchconv", /* name */
- switchconv_gate, /* gate */
- do_switchconv, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_TREE_SWITCH_CONVERSION, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_update_ssa | TODO_dump_func
- | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
- }
-};
projects / gcc.git / blobdiff