-/* Switch Conversion converts variable initializations based on switch
- statements to initializations from a static array.
- Copyright (C) 2006, 2008, 2009, 2010, 2011 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
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 "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 "gimple-pretty-print.h"
-#include "tree-dump.h"
-#include "timevar.h"
-#include "langhooks.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
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. */
/* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */
static void
-collect_switch_conv_info (gimple swtch, struct switch_conv_info *info)
+collect_switch_conv_info (gswitch *swtch, struct switch_conv_info *info)
{
unsigned int branch_num = gimple_switch_num_labels (swtch);
tree min_case, max_case;
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 first in the vector. */
- gcc_assert (CASE_LOW (gimple_switch_label (swtch, 0)) == NULL_TREE);
-
- /* Collect the bits we can deduce from the CFG. */
+ 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_label (swtch, 0)));
+ 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;
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. */
- FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
- {
- if (! single_pred_p (e->dest))
- {
- info->final_bb = e->dest;
- break;
- }
- }
+ 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)
{
check_range (struct switch_conv_info *info)
{
gcc_assert (info->range_size);
- if (!host_integerp (info->range_size, 1))
+ if (!tree_fits_uhwi_p (info->range_size))
{
info->reason = "index range way too large or otherwise unusable";
return false;
}
- if ((unsigned HOST_WIDE_INT) tree_low_cst (info->range_size, 1)
+ if (tree_to_uhwi (info->range_size)
> ((unsigned) info->count * SWITCH_CONVERSION_BRANCH_RATIO))
{
info->reason = "the maximum range-branch ratio exceeded";
static bool
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))
{
- gimple phi = gsi_stmt (gsi);
+ gphi *phi = gsi.phi ();
unsigned int i;
info->phi_count++;
int i;
info->default_values = XCNEWVEC (tree, info->phi_count * 3);
- info->constructors = XCNEWVEC (VEC (constructor_elt, gc) *, info->phi_count);
+ /* ??? 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++)
- info->constructors[i]
- = VEC_alloc (constructor_elt, gc, tree_low_cst (info->range_size, 1) + 1);
+ vec_alloc (info->constructors[i], tree_to_uhwi (info->range_size) + 1);
}
/* Free the arrays created by create_temp_arrays(). The vectors that are
static void
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;
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;
order of phi nodes. SWTCH is the switch statement being converted. */
static void
-build_constructors (gimple swtch, struct switch_conv_info *info)
+build_constructors (gswitch *swtch, struct switch_conv_info *info)
{
unsigned i, branch_num = gimple_switch_num_labels (swtch);
tree pos = info->range_min;
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)
int 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);
- 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);
+ pos = int_const_binop (PLUS_EXPR, pos,
+ build_int_cst (TREE_TYPE (pos), 1));
}
gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
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
{
- 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);
- 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);
+ 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)
{
unsigned int i;
tree prev = NULL_TREE;
constructor_elt *elt;
- FOR_EACH_VEC_ELT (constructor_elt, vec, i, elt)
+ FOR_EACH_VEC_SAFE_ELT (vec, i, elt)
{
if (!prev)
prev = elt->value;
all the constants. */
static tree
-array_value_type (gimple swtch, tree type, int num,
+array_value_type (gswitch *swtch, tree type, int num,
struct switch_conv_info *info)
{
- unsigned int i, len = VEC_length (constructor_elt, info->constructors[num]);
+ unsigned int i, len = vec_safe_length (info->constructors[num]);
constructor_elt *elt;
- enum machine_mode mode;
+ machine_mode mode;
int sign = 0;
tree smaller_type;
if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32))
return type;
- FOR_EACH_VEC_ELT (constructor_elt, info->constructors[num], i, elt)
+ FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
{
- double_int cst;
+ wide_int cst;
if (TREE_CODE (elt->value) != INTEGER_CST)
return type;
- cst = TREE_INT_CST (elt->value);
+ cst = elt->value;
while (1)
{
unsigned int prec = GET_MODE_BITSIZE (mode);
if (prec > HOST_BITS_PER_WIDE_INT)
return type;
- if (sign >= 0
- && double_int_equal_p (cst, double_int_zext (cst, prec)))
+ if (sign >= 0 && cst == wi::zext (cst, prec))
{
- if (sign == 0
- && double_int_equal_p (cst, double_int_sext (cst, prec)))
+ if (sign == 0 && cst == wi::sext (cst, prec))
break;
sign = 1;
break;
}
- if (sign <= 0
- && double_int_equal_p (cst, double_int_sext (cst, prec)))
+ if (sign <= 0 && cst == wi::sext (cst, prec))
{
sign = -1;
break;
new array. */
static void
-build_one_array (gimple swtch, int num, tree arr_index_type, gimple phi,
- tree tidx, struct switch_conv_info *info)
+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;
gcc_assert (info->default_values[num]);
- name = make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi)), NULL);
+ name = copy_ssa_name (PHI_RESULT (phi));
info->target_inbound_names[num] = name;
cst = constructor_contains_same_values_p (info->constructors[num]);
unsigned int i;
constructor_elt *elt;
- FOR_EACH_VEC_ELT (constructor_elt, info->constructors[num], i, 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]);
DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
DECL_ARTIFICIAL (decl) = 1;
+ DECL_IGNORED_P (decl) = 1;
TREE_CONSTANT (decl) = 1;
TREE_READONLY (decl) = 1;
- add_referenced_var (decl);
- varpool_finalize_decl (decl);
+ DECL_IGNORED_P (decl) = 1;
+ varpool_node::finalize_decl (decl);
fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
NULL_TREE);
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;
them. */
static void
-build_arrays (gimple swtch, struct switch_conv_info *info)
+build_arrays (gswitch *swtch, struct switch_conv_info *info)
{
tree arr_index_type;
- tree tidx, sub, tmp, utype;
+ tree tidx, sub, utype;
gimple stmt;
gimple_stmt_iterator gsi;
+ gphi_iterator gpi;
int i;
location_t loc = gimple_location (swtch);
utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
arr_index_type = build_index_type (info->range_size);
- tmp = create_tmp_var (utype, "csui");
- add_referenced_var (tmp);
- tidx = make_ssa_name (tmp, NULL);
+ 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;
- 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, info);
+ 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
+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++)
{
- tree name
- = make_ssa_name (SSA_NAME_VAR (info->target_inbound_names[i]), NULL);
-
+ 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]);
- SSA_NAME_DEF_STMT (name) = assign;
gsi_insert_before (gsi, assign, GSI_SAME_STMT);
update_stmt (assign);
}
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);
+ 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);
}
*/
static void
-gen_inbound_check (gimple swtch, struct switch_conv_info *info)
+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;
+ 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;
gcc_assert (info->default_values);
- /* 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.
- Freeing post-dominance info is dome early to avoid pointless work in
- create_basic_block, which is called when we split SWITCH_BB. */
- free_dominance_info (CDI_POST_DOMINATORS);
-
bb0 = gimple_bb (swtch);
tidx = gimple_assign_lhs (info->arr_ref_first);
/* Fix the dominator tree, if it is available. */
if (dom_info_available_p (CDI_DOMINATORS))
{
- VEC (basic_block, heap) *bbs_to_fix_dom;
+ 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 (! get_immediate_dominator (CDI_DOMINATORS, bbf))
/* If bbD was the immediate dominator ... */
set_immediate_dominator (CDI_DOMINATORS, bbf, bb0);
- bbs_to_fix_dom = VEC_alloc (basic_block, heap, 4);
- VEC_quick_push (basic_block, bbs_to_fix_dom, bb0);
- VEC_quick_push (basic_block, bbs_to_fix_dom, bb1);
- VEC_quick_push (basic_block, bbs_to_fix_dom, bb2);
- VEC_quick_push (basic_block, bbs_to_fix_dom, bbf);
+ 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);
- VEC_free (basic_block, heap, bbs_to_fix_dom);
+ bbs_to_fix_dom.release ();
}
}
conversion failed. */
static const char *
-process_switch (gimple swtch)
+process_switch (gswitch *swtch)
{
struct switch_conv_info info;
- /* Degenerate case with only a default label should never happen. */
- gcc_checking_assert (gimple_switch_num_labels (swtch) > 1);
+ /* 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);
during gimplification). */
gcc_checking_assert (TREE_TYPE (info.index_expr) != error_mark_node);
- /* 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";
+ /* A switch on a constant should have been optimized in tree-cfg-cleanup. */
+ gcc_checking_assert (! TREE_CONSTANT (info.index_expr));
- if (info.uniq <= 2)
+ if (info.uniq <= MAX_CASE_BIT_TESTS)
{
- if (expand_switch_using_bit_tests_p (info.index_expr, info.range_size,
- info.uniq, info.count))
- return "expanding as bit test is preferable";
+ 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 (&info))
{
transformation. */
create_temp_arrays (&info);
- gather_default_values (gimple_switch_label (swtch, 0), &info);
+ gather_default_values (gimple_switch_default_label (swtch), &info);
build_constructors (swtch, &info);
build_arrays (swtch, &info); /* Build the static arrays and assignments. */
/* 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);
putc ('\n', dump_file);
}
- failure_reason = process_switch (stmt);
+ failure_reason = process_switch (as_a <gswitch *> (stmt));
if (! failure_reason)
{
if (dump_file)
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
{
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_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
- }
-};