138fd1498Szrj /* Lower GIMPLE_SWITCH expressions to something more efficient than
238fd1498Szrj a jump table.
338fd1498Szrj Copyright (C) 2006-2018 Free Software Foundation, Inc.
438fd1498Szrj
538fd1498Szrj This file is part of GCC.
638fd1498Szrj
738fd1498Szrj GCC is free software; you can redistribute it and/or modify it
838fd1498Szrj under the terms of the GNU General Public License as published by the
938fd1498Szrj Free Software Foundation; either version 3, or (at your option) any
1038fd1498Szrj later version.
1138fd1498Szrj
1238fd1498Szrj GCC is distributed in the hope that it will be useful, but WITHOUT
1338fd1498Szrj ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1438fd1498Szrj FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1538fd1498Szrj for more details.
1638fd1498Szrj
1738fd1498Szrj You should have received a copy of the GNU General Public License
1838fd1498Szrj along with GCC; see the file COPYING3. If not, write to the Free
1938fd1498Szrj Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
2038fd1498Szrj 02110-1301, USA. */
2138fd1498Szrj
2238fd1498Szrj /* This file handles the lowering of GIMPLE_SWITCH to an indexed
2338fd1498Szrj load, or a series of bit-test-and-branch expressions. */
2438fd1498Szrj
2538fd1498Szrj #include "config.h"
2638fd1498Szrj #include "system.h"
2738fd1498Szrj #include "coretypes.h"
2838fd1498Szrj #include "backend.h"
2938fd1498Szrj #include "insn-codes.h"
3038fd1498Szrj #include "rtl.h"
3138fd1498Szrj #include "tree.h"
3238fd1498Szrj #include "gimple.h"
3338fd1498Szrj #include "cfghooks.h"
3438fd1498Szrj #include "tree-pass.h"
3538fd1498Szrj #include "ssa.h"
3638fd1498Szrj #include "optabs-tree.h"
3738fd1498Szrj #include "cgraph.h"
3838fd1498Szrj #include "gimple-pretty-print.h"
3938fd1498Szrj #include "params.h"
4038fd1498Szrj #include "fold-const.h"
4138fd1498Szrj #include "varasm.h"
4238fd1498Szrj #include "stor-layout.h"
4338fd1498Szrj #include "cfganal.h"
4438fd1498Szrj #include "gimplify.h"
4538fd1498Szrj #include "gimple-iterator.h"
4638fd1498Szrj #include "gimplify-me.h"
4738fd1498Szrj #include "tree-cfg.h"
4838fd1498Szrj #include "cfgloop.h"
4938fd1498Szrj #include "alloc-pool.h"
5038fd1498Szrj #include "target.h"
5138fd1498Szrj #include "tree-into-ssa.h"
5238fd1498Szrj #include "omp-general.h"
5338fd1498Szrj
5438fd1498Szrj /* ??? For lang_hooks.types.type_for_mode, but is there a word_mode
5538fd1498Szrj type in the GIMPLE type system that is language-independent? */
5638fd1498Szrj #include "langhooks.h"
5738fd1498Szrj
5838fd1498Szrj
5938fd1498Szrj /* Maximum number of case bit tests.
6038fd1498Szrj FIXME: This should be derived from PARAM_CASE_VALUES_THRESHOLD and
6138fd1498Szrj targetm.case_values_threshold(), or be its own param. */
6238fd1498Szrj #define MAX_CASE_BIT_TESTS 3
6338fd1498Szrj
6438fd1498Szrj /* Track whether or not we have altered the CFG and thus may need to
6538fd1498Szrj cleanup the CFG when complete. */
6638fd1498Szrj bool cfg_altered;
6738fd1498Szrj
6838fd1498Szrj /* Split the basic block at the statement pointed to by GSIP, and insert
6938fd1498Szrj a branch to the target basic block of E_TRUE conditional on tree
7038fd1498Szrj expression COND.
7138fd1498Szrj
7238fd1498Szrj It is assumed that there is already an edge from the to-be-split
7338fd1498Szrj basic block to E_TRUE->dest block. This edge is removed, and the
7438fd1498Szrj profile information on the edge is re-used for the new conditional
7538fd1498Szrj jump.
7638fd1498Szrj
7738fd1498Szrj The CFG is updated. The dominator tree will not be valid after
7838fd1498Szrj this transformation, but the immediate dominators are updated if
7938fd1498Szrj UPDATE_DOMINATORS is true.
8038fd1498Szrj
8138fd1498Szrj Returns the newly created basic block. */
8238fd1498Szrj
8338fd1498Szrj static basic_block
hoist_edge_and_branch_if_true(gimple_stmt_iterator * gsip,tree cond,edge e_true,bool update_dominators)8438fd1498Szrj hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
8538fd1498Szrj tree cond, edge e_true,
8638fd1498Szrj bool update_dominators)
8738fd1498Szrj {
8838fd1498Szrj tree tmp;
8938fd1498Szrj gcond *cond_stmt;
9038fd1498Szrj edge e_false;
9138fd1498Szrj basic_block new_bb, split_bb = gsi_bb (*gsip);
9238fd1498Szrj bool dominated_e_true = false;
9338fd1498Szrj
9438fd1498Szrj gcc_assert (e_true->src == split_bb);
9538fd1498Szrj
9638fd1498Szrj if (update_dominators
9738fd1498Szrj && get_immediate_dominator (CDI_DOMINATORS, e_true->dest) == split_bb)
9838fd1498Szrj dominated_e_true = true;
9938fd1498Szrj
10038fd1498Szrj tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL,
10138fd1498Szrj /*before=*/true, GSI_SAME_STMT);
10238fd1498Szrj cond_stmt = gimple_build_cond_from_tree (tmp, NULL_TREE, NULL_TREE);
10338fd1498Szrj gsi_insert_before (gsip, cond_stmt, GSI_SAME_STMT);
10438fd1498Szrj
10538fd1498Szrj e_false = split_block (split_bb, cond_stmt);
10638fd1498Szrj new_bb = e_false->dest;
10738fd1498Szrj redirect_edge_pred (e_true, split_bb);
10838fd1498Szrj
10938fd1498Szrj e_true->flags &= ~EDGE_FALLTHRU;
11038fd1498Szrj e_true->flags |= EDGE_TRUE_VALUE;
11138fd1498Szrj
11238fd1498Szrj e_false->flags &= ~EDGE_FALLTHRU;
11338fd1498Szrj e_false->flags |= EDGE_FALSE_VALUE;
11438fd1498Szrj e_false->probability = e_true->probability.invert ();
11538fd1498Szrj new_bb->count = e_false->count ();
11638fd1498Szrj
11738fd1498Szrj if (update_dominators)
11838fd1498Szrj {
11938fd1498Szrj if (dominated_e_true)
12038fd1498Szrj set_immediate_dominator (CDI_DOMINATORS, e_true->dest, split_bb);
12138fd1498Szrj set_immediate_dominator (CDI_DOMINATORS, e_false->dest, split_bb);
12238fd1498Szrj }
12338fd1498Szrj
12438fd1498Szrj return new_bb;
12538fd1498Szrj }
12638fd1498Szrj
12738fd1498Szrj
12838fd1498Szrj /* Return true if a switch should be expanded as a bit test.
12938fd1498Szrj RANGE is the difference between highest and lowest case.
13038fd1498Szrj UNIQ is number of unique case node targets, not counting the default case.
13138fd1498Szrj COUNT is the number of comparisons needed, not counting the default case. */
13238fd1498Szrj
13338fd1498Szrj static bool
expand_switch_using_bit_tests_p(tree range,unsigned int uniq,unsigned int count,bool speed_p)13438fd1498Szrj expand_switch_using_bit_tests_p (tree range,
13538fd1498Szrj unsigned int uniq,
13638fd1498Szrj unsigned int count, bool speed_p)
13738fd1498Szrj {
13838fd1498Szrj return (((uniq == 1 && count >= 3)
13938fd1498Szrj || (uniq == 2 && count >= 5)
14038fd1498Szrj || (uniq == 3 && count >= 6))
14138fd1498Szrj && lshift_cheap_p (speed_p)
14238fd1498Szrj && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0
14338fd1498Szrj && compare_tree_int (range, 0) > 0);
14438fd1498Szrj }
14538fd1498Szrj
14638fd1498Szrj /* Implement switch statements with bit tests
14738fd1498Szrj
14838fd1498Szrj A GIMPLE switch statement can be expanded to a short sequence of bit-wise
14938fd1498Szrj comparisons. "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)"
15038fd1498Szrj where CST and MINVAL are integer constants. This is better than a series
15138fd1498Szrj of compare-and-banch insns in some cases, e.g. we can implement:
15238fd1498Szrj
15338fd1498Szrj if ((x==4) || (x==6) || (x==9) || (x==11))
15438fd1498Szrj
15538fd1498Szrj as a single bit test:
15638fd1498Szrj
15738fd1498Szrj if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11)))
15838fd1498Szrj
15938fd1498Szrj This transformation is only applied if the number of case targets is small,
16038fd1498Szrj if CST constains at least 3 bits, and "1 << x" is cheap. The bit tests are
16138fd1498Szrj performed in "word_mode".
16238fd1498Szrj
16338fd1498Szrj The following example shows the code the transformation generates:
16438fd1498Szrj
16538fd1498Szrj int bar(int x)
16638fd1498Szrj {
16738fd1498Szrj switch (x)
16838fd1498Szrj {
16938fd1498Szrj case '0': case '1': case '2': case '3': case '4':
17038fd1498Szrj case '5': case '6': case '7': case '8': case '9':
17138fd1498Szrj case 'A': case 'B': case 'C': case 'D': case 'E':
17238fd1498Szrj case 'F':
17338fd1498Szrj return 1;
17438fd1498Szrj }
17538fd1498Szrj return 0;
17638fd1498Szrj }
17738fd1498Szrj
17838fd1498Szrj ==>
17938fd1498Szrj
18038fd1498Szrj bar (int x)
18138fd1498Szrj {
18238fd1498Szrj tmp1 = x - 48;
18338fd1498Szrj if (tmp1 > (70 - 48)) goto L2;
18438fd1498Szrj tmp2 = 1 << tmp1;
18538fd1498Szrj tmp3 = 0b11111100000001111111111;
18638fd1498Szrj if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2;
18738fd1498Szrj L1:
18838fd1498Szrj return 1;
18938fd1498Szrj L2:
19038fd1498Szrj return 0;
19138fd1498Szrj }
19238fd1498Szrj
19338fd1498Szrj TODO: There are still some improvements to this transformation that could
19438fd1498Szrj be implemented:
19538fd1498Szrj
19638fd1498Szrj * A narrower mode than word_mode could be used if that is cheaper, e.g.
19738fd1498Szrj for x86_64 where a narrower-mode shift may result in smaller code.
19838fd1498Szrj
19938fd1498Szrj * The compounded constant could be shifted rather than the one. The
20038fd1498Szrj test would be either on the sign bit or on the least significant bit,
20138fd1498Szrj depending on the direction of the shift. On some machines, the test
20238fd1498Szrj for the branch would be free if the bit to test is already set by the
20338fd1498Szrj shift operation.
20438fd1498Szrj
20538fd1498Szrj This transformation was contributed by Roger Sayle, see this e-mail:
20638fd1498Szrj http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html
20738fd1498Szrj */
20838fd1498Szrj
20938fd1498Szrj /* A case_bit_test represents a set of case nodes that may be
21038fd1498Szrj selected from using a bit-wise comparison. HI and LO hold
21138fd1498Szrj the integer to be tested against, TARGET_EDGE contains the
21238fd1498Szrj edge to the basic block to jump to upon success and BITS
21338fd1498Szrj counts the number of case nodes handled by this test,
21438fd1498Szrj typically the number of bits set in HI:LO. The LABEL field
21538fd1498Szrj is used to quickly identify all cases in this set without
21638fd1498Szrj looking at label_to_block for every case label. */
21738fd1498Szrj
21838fd1498Szrj struct case_bit_test
21938fd1498Szrj {
22038fd1498Szrj wide_int mask;
22138fd1498Szrj edge target_edge;
22238fd1498Szrj tree label;
22338fd1498Szrj int bits;
22438fd1498Szrj };
22538fd1498Szrj
22638fd1498Szrj /* Comparison function for qsort to order bit tests by decreasing
22738fd1498Szrj probability of execution. Our best guess comes from a measured
22838fd1498Szrj profile. If the profile counts are equal, break even on the
22938fd1498Szrj number of case nodes, i.e. the node with the most cases gets
23038fd1498Szrj tested first.
23138fd1498Szrj
23238fd1498Szrj TODO: Actually this currently runs before a profile is available.
23338fd1498Szrj Therefore the case-as-bit-tests transformation should be done
23438fd1498Szrj later in the pass pipeline, or something along the lines of
23538fd1498Szrj "Efficient and effective branch reordering using profile data"
23638fd1498Szrj (Yang et. al., 2002) should be implemented (although, how good
23738fd1498Szrj is a paper is called "Efficient and effective ..." when the
23838fd1498Szrj latter is implied by the former, but oh well...). */
23938fd1498Szrj
24038fd1498Szrj static int
case_bit_test_cmp(const void * p1,const void * p2)24138fd1498Szrj case_bit_test_cmp (const void *p1, const void *p2)
24238fd1498Szrj {
24338fd1498Szrj const struct case_bit_test *const d1 = (const struct case_bit_test *) p1;
24438fd1498Szrj const struct case_bit_test *const d2 = (const struct case_bit_test *) p2;
24538fd1498Szrj
24638fd1498Szrj if (d2->target_edge->count () < d1->target_edge->count ())
24738fd1498Szrj return -1;
24838fd1498Szrj if (d2->target_edge->count () > d1->target_edge->count ())
24938fd1498Szrj return 1;
25038fd1498Szrj if (d2->bits != d1->bits)
25138fd1498Szrj return d2->bits - d1->bits;
25238fd1498Szrj
25338fd1498Szrj /* Stabilize the sort. */
25438fd1498Szrj return LABEL_DECL_UID (d2->label) - LABEL_DECL_UID (d1->label);
25538fd1498Szrj }
25638fd1498Szrj
25738fd1498Szrj /* Expand a switch statement by a short sequence of bit-wise
25838fd1498Szrj comparisons. "switch(x)" is effectively converted into
25938fd1498Szrj "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
26038fd1498Szrj integer constants.
26138fd1498Szrj
26238fd1498Szrj INDEX_EXPR is the value being switched on.
26338fd1498Szrj
26438fd1498Szrj MINVAL is the lowest case value of in the case nodes,
26538fd1498Szrj and RANGE is highest value minus MINVAL. MINVAL and RANGE
26638fd1498Szrj are not guaranteed to be of the same type as INDEX_EXPR
26738fd1498Szrj (the gimplifier doesn't change the type of case label values,
26838fd1498Szrj and MINVAL and RANGE are derived from those values).
26938fd1498Szrj MAXVAL is MINVAL + RANGE.
27038fd1498Szrj
27138fd1498Szrj There *MUST* be MAX_CASE_BIT_TESTS or less unique case
27238fd1498Szrj node targets. */
27338fd1498Szrj
27438fd1498Szrj static void
emit_case_bit_tests(gswitch * swtch,tree index_expr,tree minval,tree range,tree maxval)27538fd1498Szrj emit_case_bit_tests (gswitch *swtch, tree index_expr,
27638fd1498Szrj tree minval, tree range, tree maxval)
27738fd1498Szrj {
27838fd1498Szrj struct case_bit_test test[MAX_CASE_BIT_TESTS] = { {} };
27938fd1498Szrj unsigned int i, j, k;
28038fd1498Szrj unsigned int count;
28138fd1498Szrj
28238fd1498Szrj basic_block switch_bb = gimple_bb (swtch);
28338fd1498Szrj basic_block default_bb, new_default_bb, new_bb;
28438fd1498Szrj edge default_edge;
28538fd1498Szrj bool update_dom = dom_info_available_p (CDI_DOMINATORS);
28638fd1498Szrj
28738fd1498Szrj vec<basic_block> bbs_to_fix_dom = vNULL;
28838fd1498Szrj
28938fd1498Szrj tree index_type = TREE_TYPE (index_expr);
29038fd1498Szrj tree unsigned_index_type = unsigned_type_for (index_type);
29138fd1498Szrj unsigned int branch_num = gimple_switch_num_labels (swtch);
29238fd1498Szrj
29338fd1498Szrj gimple_stmt_iterator gsi;
29438fd1498Szrj gassign *shift_stmt;
29538fd1498Szrj
29638fd1498Szrj tree idx, tmp, csui;
29738fd1498Szrj tree word_type_node = lang_hooks.types.type_for_mode (word_mode, 1);
29838fd1498Szrj tree word_mode_zero = fold_convert (word_type_node, integer_zero_node);
29938fd1498Szrj tree word_mode_one = fold_convert (word_type_node, integer_one_node);
30038fd1498Szrj int prec = TYPE_PRECISION (word_type_node);
30138fd1498Szrj wide_int wone = wi::one (prec);
30238fd1498Szrj
30338fd1498Szrj /* Get the edge for the default case. */
30438fd1498Szrj tmp = gimple_switch_default_label (swtch);
30538fd1498Szrj default_bb = label_to_block (CASE_LABEL (tmp));
30638fd1498Szrj default_edge = find_edge (switch_bb, default_bb);
30738fd1498Szrj
30838fd1498Szrj /* Go through all case labels, and collect the case labels, profile
30938fd1498Szrj counts, and other information we need to build the branch tests. */
31038fd1498Szrj count = 0;
31138fd1498Szrj for (i = 1; i < branch_num; i++)
31238fd1498Szrj {
31338fd1498Szrj unsigned int lo, hi;
31438fd1498Szrj tree cs = gimple_switch_label (swtch, i);
31538fd1498Szrj tree label = CASE_LABEL (cs);
31638fd1498Szrj edge e = find_edge (switch_bb, label_to_block (label));
31738fd1498Szrj for (k = 0; k < count; k++)
31838fd1498Szrj if (e == test[k].target_edge)
31938fd1498Szrj break;
32038fd1498Szrj
32138fd1498Szrj if (k == count)
32238fd1498Szrj {
32338fd1498Szrj gcc_checking_assert (count < MAX_CASE_BIT_TESTS);
32438fd1498Szrj test[k].mask = wi::zero (prec);
32538fd1498Szrj test[k].target_edge = e;
32638fd1498Szrj test[k].label = label;
32738fd1498Szrj test[k].bits = 1;
32838fd1498Szrj count++;
32938fd1498Szrj }
33038fd1498Szrj else
33138fd1498Szrj test[k].bits++;
33238fd1498Szrj
33338fd1498Szrj lo = tree_to_uhwi (int_const_binop (MINUS_EXPR,
33438fd1498Szrj CASE_LOW (cs), minval));
33538fd1498Szrj if (CASE_HIGH (cs) == NULL_TREE)
33638fd1498Szrj hi = lo;
33738fd1498Szrj else
33838fd1498Szrj hi = tree_to_uhwi (int_const_binop (MINUS_EXPR,
33938fd1498Szrj CASE_HIGH (cs), minval));
34038fd1498Szrj
34138fd1498Szrj for (j = lo; j <= hi; j++)
34238fd1498Szrj test[k].mask |= wi::lshift (wone, j);
34338fd1498Szrj }
34438fd1498Szrj
34538fd1498Szrj qsort (test, count, sizeof (*test), case_bit_test_cmp);
34638fd1498Szrj
34738fd1498Szrj /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of
34838fd1498Szrj the minval subtractions, but it might make the mask constants more
34938fd1498Szrj expensive. So, compare the costs. */
35038fd1498Szrj if (compare_tree_int (minval, 0) > 0
35138fd1498Szrj && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
35238fd1498Szrj {
35338fd1498Szrj int cost_diff;
35438fd1498Szrj HOST_WIDE_INT m = tree_to_uhwi (minval);
35538fd1498Szrj rtx reg = gen_raw_REG (word_mode, 10000);
35638fd1498Szrj bool speed_p = optimize_bb_for_speed_p (gimple_bb (swtch));
35738fd1498Szrj cost_diff = set_rtx_cost (gen_rtx_PLUS (word_mode, reg,
35838fd1498Szrj GEN_INT (-m)), speed_p);
35938fd1498Szrj for (i = 0; i < count; i++)
36038fd1498Szrj {
36138fd1498Szrj rtx r = immed_wide_int_const (test[i].mask, word_mode);
36238fd1498Szrj cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r),
36338fd1498Szrj word_mode, speed_p);
36438fd1498Szrj r = immed_wide_int_const (wi::lshift (test[i].mask, m), word_mode);
36538fd1498Szrj cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r),
36638fd1498Szrj word_mode, speed_p);
36738fd1498Szrj }
36838fd1498Szrj if (cost_diff > 0)
36938fd1498Szrj {
37038fd1498Szrj for (i = 0; i < count; i++)
37138fd1498Szrj test[i].mask = wi::lshift (test[i].mask, m);
37238fd1498Szrj minval = build_zero_cst (TREE_TYPE (minval));
37338fd1498Szrj range = maxval;
37438fd1498Szrj }
37538fd1498Szrj }
37638fd1498Szrj
37738fd1498Szrj /* We generate two jumps to the default case label.
37838fd1498Szrj Split the default edge, so that we don't have to do any PHI node
37938fd1498Szrj updating. */
38038fd1498Szrj new_default_bb = split_edge (default_edge);
38138fd1498Szrj
38238fd1498Szrj if (update_dom)
38338fd1498Szrj {
38438fd1498Szrj bbs_to_fix_dom.create (10);
38538fd1498Szrj bbs_to_fix_dom.quick_push (switch_bb);
38638fd1498Szrj bbs_to_fix_dom.quick_push (default_bb);
38738fd1498Szrj bbs_to_fix_dom.quick_push (new_default_bb);
38838fd1498Szrj }
38938fd1498Szrj
39038fd1498Szrj /* Now build the test-and-branch code. */
39138fd1498Szrj
39238fd1498Szrj gsi = gsi_last_bb (switch_bb);
39338fd1498Szrj
39438fd1498Szrj /* idx = (unsigned)x - minval. */
39538fd1498Szrj idx = fold_convert (unsigned_index_type, index_expr);
39638fd1498Szrj idx = fold_build2 (MINUS_EXPR, unsigned_index_type, idx,
39738fd1498Szrj fold_convert (unsigned_index_type, minval));
39838fd1498Szrj idx = force_gimple_operand_gsi (&gsi, idx,
39938fd1498Szrj /*simple=*/true, NULL_TREE,
40038fd1498Szrj /*before=*/true, GSI_SAME_STMT);
40138fd1498Szrj
40238fd1498Szrj /* if (idx > range) goto default */
40338fd1498Szrj range = force_gimple_operand_gsi (&gsi,
40438fd1498Szrj fold_convert (unsigned_index_type, range),
40538fd1498Szrj /*simple=*/true, NULL_TREE,
40638fd1498Szrj /*before=*/true, GSI_SAME_STMT);
40738fd1498Szrj tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range);
40838fd1498Szrj new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, default_edge, update_dom);
40938fd1498Szrj if (update_dom)
41038fd1498Szrj bbs_to_fix_dom.quick_push (new_bb);
41138fd1498Szrj gcc_assert (gimple_bb (swtch) == new_bb);
41238fd1498Szrj gsi = gsi_last_bb (new_bb);
41338fd1498Szrj
41438fd1498Szrj /* Any blocks dominated by the GIMPLE_SWITCH, but that are not successors
41538fd1498Szrj of NEW_BB, are still immediately dominated by SWITCH_BB. Make it so. */
41638fd1498Szrj if (update_dom)
41738fd1498Szrj {
41838fd1498Szrj vec<basic_block> dom_bbs;
41938fd1498Szrj basic_block dom_son;
42038fd1498Szrj
42138fd1498Szrj dom_bbs = get_dominated_by (CDI_DOMINATORS, new_bb);
42238fd1498Szrj FOR_EACH_VEC_ELT (dom_bbs, i, dom_son)
42338fd1498Szrj {
42438fd1498Szrj edge e = find_edge (new_bb, dom_son);
42538fd1498Szrj if (e && single_pred_p (e->dest))
42638fd1498Szrj continue;
42738fd1498Szrj set_immediate_dominator (CDI_DOMINATORS, dom_son, switch_bb);
42838fd1498Szrj bbs_to_fix_dom.safe_push (dom_son);
42938fd1498Szrj }
43038fd1498Szrj dom_bbs.release ();
43138fd1498Szrj }
43238fd1498Szrj
43338fd1498Szrj /* csui = (1 << (word_mode) idx) */
43438fd1498Szrj csui = make_ssa_name (word_type_node);
43538fd1498Szrj tmp = fold_build2 (LSHIFT_EXPR, word_type_node, word_mode_one,
43638fd1498Szrj fold_convert (word_type_node, idx));
43738fd1498Szrj tmp = force_gimple_operand_gsi (&gsi, tmp,
43838fd1498Szrj /*simple=*/false, NULL_TREE,
43938fd1498Szrj /*before=*/true, GSI_SAME_STMT);
44038fd1498Szrj shift_stmt = gimple_build_assign (csui, tmp);
44138fd1498Szrj gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT);
44238fd1498Szrj update_stmt (shift_stmt);
44338fd1498Szrj
44438fd1498Szrj /* for each unique set of cases:
44538fd1498Szrj if (const & csui) goto target */
44638fd1498Szrj for (k = 0; k < count; k++)
44738fd1498Szrj {
44838fd1498Szrj tmp = wide_int_to_tree (word_type_node, test[k].mask);
44938fd1498Szrj tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp);
45038fd1498Szrj tmp = force_gimple_operand_gsi (&gsi, tmp,
45138fd1498Szrj /*simple=*/true, NULL_TREE,
45238fd1498Szrj /*before=*/true, GSI_SAME_STMT);
45338fd1498Szrj tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero);
45438fd1498Szrj new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_edge,
45538fd1498Szrj update_dom);
45638fd1498Szrj if (update_dom)
45738fd1498Szrj bbs_to_fix_dom.safe_push (new_bb);
45838fd1498Szrj gcc_assert (gimple_bb (swtch) == new_bb);
45938fd1498Szrj gsi = gsi_last_bb (new_bb);
46038fd1498Szrj }
46138fd1498Szrj
46238fd1498Szrj /* We should have removed all edges now. */
46338fd1498Szrj gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0);
46438fd1498Szrj
46538fd1498Szrj /* If nothing matched, go to the default label. */
46638fd1498Szrj make_edge (gsi_bb (gsi), new_default_bb, EDGE_FALLTHRU);
46738fd1498Szrj
46838fd1498Szrj /* The GIMPLE_SWITCH is now redundant. */
46938fd1498Szrj gsi_remove (&gsi, true);
47038fd1498Szrj
47138fd1498Szrj if (update_dom)
47238fd1498Szrj {
47338fd1498Szrj /* Fix up the dominator tree. */
47438fd1498Szrj iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
47538fd1498Szrj bbs_to_fix_dom.release ();
47638fd1498Szrj }
47738fd1498Szrj }
47838fd1498Szrj
47938fd1498Szrj /*
48038fd1498Szrj Switch initialization conversion
48138fd1498Szrj
48238fd1498Szrj The following pass changes simple initializations of scalars in a switch
48338fd1498Szrj statement into initializations from a static array. Obviously, the values
48438fd1498Szrj must be constant and known at compile time and a default branch must be
48538fd1498Szrj provided. For example, the following code:
48638fd1498Szrj
48738fd1498Szrj int a,b;
48838fd1498Szrj
48938fd1498Szrj switch (argc)
49038fd1498Szrj {
49138fd1498Szrj case 1:
49238fd1498Szrj case 2:
49338fd1498Szrj a_1 = 8;
49438fd1498Szrj b_1 = 6;
49538fd1498Szrj break;
49638fd1498Szrj case 3:
49738fd1498Szrj a_2 = 9;
49838fd1498Szrj b_2 = 5;
49938fd1498Szrj break;
50038fd1498Szrj case 12:
50138fd1498Szrj a_3 = 10;
50238fd1498Szrj b_3 = 4;
50338fd1498Szrj break;
50438fd1498Szrj default:
50538fd1498Szrj a_4 = 16;
50638fd1498Szrj b_4 = 1;
50738fd1498Szrj break;
50838fd1498Szrj }
50938fd1498Szrj a_5 = PHI <a_1, a_2, a_3, a_4>
51038fd1498Szrj b_5 = PHI <b_1, b_2, b_3, b_4>
51138fd1498Szrj
51238fd1498Szrj
51338fd1498Szrj is changed into:
51438fd1498Szrj
51538fd1498Szrj static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
51638fd1498Szrj static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
51738fd1498Szrj 16, 16, 10};
51838fd1498Szrj
51938fd1498Szrj if (((unsigned) argc) - 1 < 11)
52038fd1498Szrj {
52138fd1498Szrj a_6 = CSWTCH02[argc - 1];
52238fd1498Szrj b_6 = CSWTCH01[argc - 1];
52338fd1498Szrj }
52438fd1498Szrj else
52538fd1498Szrj {
52638fd1498Szrj a_7 = 16;
52738fd1498Szrj b_7 = 1;
52838fd1498Szrj }
52938fd1498Szrj a_5 = PHI <a_6, a_7>
53038fd1498Szrj b_b = PHI <b_6, b_7>
53138fd1498Szrj
53238fd1498Szrj There are further constraints. Specifically, the range of values across all
53338fd1498Szrj case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
53438fd1498Szrj eight) times the number of the actual switch branches.
53538fd1498Szrj
53638fd1498Szrj This transformation was contributed by Martin Jambor, see this e-mail:
53738fd1498Szrj http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */
53838fd1498Szrj
53938fd1498Szrj /* The main structure of the pass. */
54038fd1498Szrj struct switch_conv_info
54138fd1498Szrj {
54238fd1498Szrj /* The expression used to decide the switch branch. */
54338fd1498Szrj tree index_expr;
54438fd1498Szrj
54538fd1498Szrj /* The following integer constants store the minimum and maximum value
54638fd1498Szrj covered by the case labels. */
54738fd1498Szrj tree range_min;
54838fd1498Szrj tree range_max;
54938fd1498Szrj
55038fd1498Szrj /* The difference between the above two numbers. Stored here because it
55138fd1498Szrj is used in all the conversion heuristics, as well as for some of the
55238fd1498Szrj transformation, and it is expensive to re-compute it all the time. */
55338fd1498Szrj tree range_size;
55438fd1498Szrj
55538fd1498Szrj /* Basic block that contains the actual GIMPLE_SWITCH. */
55638fd1498Szrj basic_block switch_bb;
55738fd1498Szrj
55838fd1498Szrj /* Basic block that is the target of the default case. */
55938fd1498Szrj basic_block default_bb;
56038fd1498Szrj
56138fd1498Szrj /* The single successor block of all branches out of the GIMPLE_SWITCH,
56238fd1498Szrj if such a block exists. Otherwise NULL. */
56338fd1498Szrj basic_block final_bb;
56438fd1498Szrj
56538fd1498Szrj /* The probability of the default edge in the replaced switch. */
56638fd1498Szrj profile_probability default_prob;
56738fd1498Szrj
56838fd1498Szrj /* The count of the default edge in the replaced switch. */
56938fd1498Szrj profile_count default_count;
57038fd1498Szrj
57138fd1498Szrj /* Combined count of all other (non-default) edges in the replaced switch. */
57238fd1498Szrj profile_count other_count;
57338fd1498Szrj
57438fd1498Szrj /* Number of phi nodes in the final bb (that we'll be replacing). */
57538fd1498Szrj int phi_count;
57638fd1498Szrj
57738fd1498Szrj /* Array of default values, in the same order as phi nodes. */
57838fd1498Szrj tree *default_values;
57938fd1498Szrj
58038fd1498Szrj /* Constructors of new static arrays. */
58138fd1498Szrj vec<constructor_elt, va_gc> **constructors;
58238fd1498Szrj
58338fd1498Szrj /* Array of ssa names that are initialized with a value from a new static
58438fd1498Szrj array. */
58538fd1498Szrj tree *target_inbound_names;
58638fd1498Szrj
58738fd1498Szrj /* Array of ssa names that are initialized with the default value if the
58838fd1498Szrj switch expression is out of range. */
58938fd1498Szrj tree *target_outbound_names;
59038fd1498Szrj
59138fd1498Szrj /* VOP SSA_NAME. */
59238fd1498Szrj tree target_vop;
59338fd1498Szrj
59438fd1498Szrj /* The first load statement that loads a temporary from a new static array.
59538fd1498Szrj */
59638fd1498Szrj gimple *arr_ref_first;
59738fd1498Szrj
59838fd1498Szrj /* The last load statement that loads a temporary from a new static array. */
59938fd1498Szrj gimple *arr_ref_last;
60038fd1498Szrj
60138fd1498Szrj /* String reason why the case wasn't a good candidate that is written to the
60238fd1498Szrj dump file, if there is one. */
60338fd1498Szrj const char *reason;
60438fd1498Szrj
60538fd1498Szrj /* True if default case is not used for any value between range_min and
60638fd1498Szrj range_max inclusive. */
60738fd1498Szrj bool contiguous_range;
60838fd1498Szrj
60938fd1498Szrj /* True if default case does not have the required shape for other case
61038fd1498Szrj labels. */
61138fd1498Szrj bool default_case_nonstandard;
61238fd1498Szrj
61338fd1498Szrj /* Parameters for expand_switch_using_bit_tests. Should be computed
61438fd1498Szrj the same way as in expand_case. */
61538fd1498Szrj unsigned int uniq;
61638fd1498Szrj unsigned int count;
61738fd1498Szrj };
61838fd1498Szrj
61938fd1498Szrj /* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */
62038fd1498Szrj
62138fd1498Szrj static void
collect_switch_conv_info(gswitch * swtch,struct switch_conv_info * info)62238fd1498Szrj collect_switch_conv_info (gswitch *swtch, struct switch_conv_info *info)
62338fd1498Szrj {
62438fd1498Szrj unsigned int branch_num = gimple_switch_num_labels (swtch);
62538fd1498Szrj tree min_case, max_case;
62638fd1498Szrj unsigned int count, i;
62738fd1498Szrj edge e, e_default, e_first;
62838fd1498Szrj edge_iterator ei;
62938fd1498Szrj basic_block first;
63038fd1498Szrj
63138fd1498Szrj memset (info, 0, sizeof (*info));
63238fd1498Szrj
63338fd1498Szrj /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
63438fd1498Szrj is a default label which is the first in the vector.
63538fd1498Szrj Collect the bits we can deduce from the CFG. */
63638fd1498Szrj info->index_expr = gimple_switch_index (swtch);
63738fd1498Szrj info->switch_bb = gimple_bb (swtch);
63838fd1498Szrj info->default_bb
63938fd1498Szrj = label_to_block (CASE_LABEL (gimple_switch_default_label (swtch)));
64038fd1498Szrj e_default = find_edge (info->switch_bb, info->default_bb);
64138fd1498Szrj info->default_prob = e_default->probability;
64238fd1498Szrj info->default_count = e_default->count ();
64338fd1498Szrj FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
64438fd1498Szrj if (e != e_default)
64538fd1498Szrj info->other_count += e->count ();
64638fd1498Szrj
64738fd1498Szrj /* Get upper and lower bounds of case values, and the covered range. */
64838fd1498Szrj min_case = gimple_switch_label (swtch, 1);
64938fd1498Szrj max_case = gimple_switch_label (swtch, branch_num - 1);
65038fd1498Szrj
65138fd1498Szrj info->range_min = CASE_LOW (min_case);
65238fd1498Szrj if (CASE_HIGH (max_case) != NULL_TREE)
65338fd1498Szrj info->range_max = CASE_HIGH (max_case);
65438fd1498Szrj else
65538fd1498Szrj info->range_max = CASE_LOW (max_case);
65638fd1498Szrj
65738fd1498Szrj info->contiguous_range = true;
65838fd1498Szrj tree last = CASE_HIGH (min_case) ? CASE_HIGH (min_case) : info->range_min;
65938fd1498Szrj for (i = 2; i < branch_num; i++)
66038fd1498Szrj {
66138fd1498Szrj tree elt = gimple_switch_label (swtch, i);
66238fd1498Szrj if (wi::to_wide (last) + 1 != wi::to_wide (CASE_LOW (elt)))
66338fd1498Szrj {
66438fd1498Szrj info->contiguous_range = false;
66538fd1498Szrj break;
66638fd1498Szrj }
66738fd1498Szrj last = CASE_HIGH (elt) ? CASE_HIGH (elt) : CASE_LOW (elt);
66838fd1498Szrj }
66938fd1498Szrj
67038fd1498Szrj if (info->contiguous_range)
67138fd1498Szrj {
67238fd1498Szrj first = label_to_block (CASE_LABEL (gimple_switch_label (swtch, 1)));
67338fd1498Szrj e_first = find_edge (info->switch_bb, first);
67438fd1498Szrj }
67538fd1498Szrj else
67638fd1498Szrj {
67738fd1498Szrj first = info->default_bb;
67838fd1498Szrj e_first = e_default;
67938fd1498Szrj }
68038fd1498Szrj
68138fd1498Szrj /* See if there is one common successor block for all branch
68238fd1498Szrj targets. If it exists, record it in FINAL_BB.
68338fd1498Szrj Start with the destination of the first non-default case
68438fd1498Szrj if the range is contiguous and default case otherwise as
68538fd1498Szrj guess or its destination in case it is a forwarder block. */
68638fd1498Szrj if (! single_pred_p (e_first->dest))
68738fd1498Szrj info->final_bb = e_first->dest;
68838fd1498Szrj else if (single_succ_p (e_first->dest)
68938fd1498Szrj && ! single_pred_p (single_succ (e_first->dest)))
69038fd1498Szrj info->final_bb = single_succ (e_first->dest);
69138fd1498Szrj /* Require that all switch destinations are either that common
69238fd1498Szrj FINAL_BB or a forwarder to it, except for the default
69338fd1498Szrj case if contiguous range. */
69438fd1498Szrj if (info->final_bb)
69538fd1498Szrj FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
69638fd1498Szrj {
69738fd1498Szrj if (e->dest == info->final_bb)
69838fd1498Szrj continue;
69938fd1498Szrj
70038fd1498Szrj if (single_pred_p (e->dest)
70138fd1498Szrj && single_succ_p (e->dest)
70238fd1498Szrj && single_succ (e->dest) == info->final_bb)
70338fd1498Szrj continue;
70438fd1498Szrj
70538fd1498Szrj if (e == e_default && info->contiguous_range)
70638fd1498Szrj {
70738fd1498Szrj info->default_case_nonstandard = true;
70838fd1498Szrj continue;
70938fd1498Szrj }
71038fd1498Szrj
71138fd1498Szrj info->final_bb = NULL;
71238fd1498Szrj break;
71338fd1498Szrj }
71438fd1498Szrj
71538fd1498Szrj info->range_size
71638fd1498Szrj = int_const_binop (MINUS_EXPR, info->range_max, info->range_min);
71738fd1498Szrj
71838fd1498Szrj /* Get a count of the number of case labels. Single-valued case labels
71938fd1498Szrj simply count as one, but a case range counts double, since it may
72038fd1498Szrj require two compares if it gets lowered as a branching tree. */
72138fd1498Szrj count = 0;
72238fd1498Szrj for (i = 1; i < branch_num; i++)
72338fd1498Szrj {
72438fd1498Szrj tree elt = gimple_switch_label (swtch, i);
72538fd1498Szrj count++;
72638fd1498Szrj if (CASE_HIGH (elt)
72738fd1498Szrj && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt)))
72838fd1498Szrj count++;
72938fd1498Szrj }
73038fd1498Szrj info->count = count;
73138fd1498Szrj
73238fd1498Szrj /* Get the number of unique non-default targets out of the GIMPLE_SWITCH
73338fd1498Szrj block. Assume a CFG cleanup would have already removed degenerate
73438fd1498Szrj switch statements, this allows us to just use EDGE_COUNT. */
73538fd1498Szrj info->uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1;
73638fd1498Szrj }
73738fd1498Szrj
73838fd1498Szrj /* Checks whether the range given by individual case statements of the SWTCH
73938fd1498Szrj switch statement isn't too big and whether the number of branches actually
74038fd1498Szrj satisfies the size of the new array. */
74138fd1498Szrj
74238fd1498Szrj static bool
check_range(struct switch_conv_info * info)74338fd1498Szrj check_range (struct switch_conv_info *info)
74438fd1498Szrj {
74538fd1498Szrj gcc_assert (info->range_size);
74638fd1498Szrj if (!tree_fits_uhwi_p (info->range_size))
74738fd1498Szrj {
74838fd1498Szrj info->reason = "index range way too large or otherwise unusable";
74938fd1498Szrj return false;
75038fd1498Szrj }
75138fd1498Szrj
75238fd1498Szrj if (tree_to_uhwi (info->range_size)
75338fd1498Szrj > ((unsigned) info->count * SWITCH_CONVERSION_BRANCH_RATIO))
75438fd1498Szrj {
75538fd1498Szrj info->reason = "the maximum range-branch ratio exceeded";
75638fd1498Szrj return false;
75738fd1498Szrj }
75838fd1498Szrj
75938fd1498Szrj return true;
76038fd1498Szrj }
76138fd1498Szrj
76238fd1498Szrj /* Checks whether all but the FINAL_BB basic blocks are empty. */
76338fd1498Szrj
76438fd1498Szrj static bool
check_all_empty_except_final(struct switch_conv_info * info)76538fd1498Szrj check_all_empty_except_final (struct switch_conv_info *info)
76638fd1498Szrj {
76738fd1498Szrj edge e, e_default = find_edge (info->switch_bb, info->default_bb);
76838fd1498Szrj edge_iterator ei;
76938fd1498Szrj
77038fd1498Szrj FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
77138fd1498Szrj {
77238fd1498Szrj if (e->dest == info->final_bb)
77338fd1498Szrj continue;
77438fd1498Szrj
77538fd1498Szrj if (!empty_block_p (e->dest))
77638fd1498Szrj {
77738fd1498Szrj if (info->contiguous_range && e == e_default)
77838fd1498Szrj {
77938fd1498Szrj info->default_case_nonstandard = true;
78038fd1498Szrj continue;
78138fd1498Szrj }
78238fd1498Szrj
78338fd1498Szrj info->reason = "bad case - a non-final BB not empty";
78438fd1498Szrj return false;
78538fd1498Szrj }
78638fd1498Szrj }
78738fd1498Szrj
78838fd1498Szrj return true;
78938fd1498Szrj }
79038fd1498Szrj
79138fd1498Szrj /* This function checks whether all required values in phi nodes in final_bb
79238fd1498Szrj are constants. Required values are those that correspond to a basic block
79338fd1498Szrj which is a part of the examined switch statement. It returns true if the
79438fd1498Szrj phi nodes are OK, otherwise false. */
79538fd1498Szrj
79638fd1498Szrj static bool
check_final_bb(gswitch * swtch,struct switch_conv_info * info)79738fd1498Szrj check_final_bb (gswitch *swtch, struct switch_conv_info *info)
79838fd1498Szrj {
79938fd1498Szrj gphi_iterator gsi;
80038fd1498Szrj
80138fd1498Szrj info->phi_count = 0;
80238fd1498Szrj for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
80338fd1498Szrj {
80438fd1498Szrj gphi *phi = gsi.phi ();
80538fd1498Szrj unsigned int i;
80638fd1498Szrj
80738fd1498Szrj if (virtual_operand_p (gimple_phi_result (phi)))
80838fd1498Szrj continue;
80938fd1498Szrj
81038fd1498Szrj info->phi_count++;
81138fd1498Szrj
81238fd1498Szrj for (i = 0; i < gimple_phi_num_args (phi); i++)
81338fd1498Szrj {
81438fd1498Szrj basic_block bb = gimple_phi_arg_edge (phi, i)->src;
81538fd1498Szrj
81638fd1498Szrj if (bb == info->switch_bb
81738fd1498Szrj || (single_pred_p (bb)
81838fd1498Szrj && single_pred (bb) == info->switch_bb
81938fd1498Szrj && (!info->default_case_nonstandard
82038fd1498Szrj || empty_block_p (bb))))
82138fd1498Szrj {
82238fd1498Szrj tree reloc, val;
82338fd1498Szrj const char *reason = NULL;
82438fd1498Szrj
82538fd1498Szrj val = gimple_phi_arg_def (phi, i);
82638fd1498Szrj if (!is_gimple_ip_invariant (val))
82738fd1498Szrj reason = "non-invariant value from a case";
82838fd1498Szrj else
82938fd1498Szrj {
83038fd1498Szrj reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
83138fd1498Szrj if ((flag_pic && reloc != null_pointer_node)
83238fd1498Szrj || (!flag_pic && reloc == NULL_TREE))
83338fd1498Szrj {
83438fd1498Szrj if (reloc)
83538fd1498Szrj reason
83638fd1498Szrj = "value from a case would need runtime relocations";
83738fd1498Szrj else
83838fd1498Szrj reason
83938fd1498Szrj = "value from a case is not a valid initializer";
84038fd1498Szrj }
84138fd1498Szrj }
84238fd1498Szrj if (reason)
84338fd1498Szrj {
84438fd1498Szrj /* For contiguous range, we can allow non-constant
84538fd1498Szrj or one that needs relocation, as long as it is
84638fd1498Szrj only reachable from the default case. */
84738fd1498Szrj if (bb == info->switch_bb)
84838fd1498Szrj bb = info->final_bb;
84938fd1498Szrj if (!info->contiguous_range || bb != info->default_bb)
85038fd1498Szrj {
85138fd1498Szrj info->reason = reason;
85238fd1498Szrj return false;
85338fd1498Szrj }
85438fd1498Szrj
85538fd1498Szrj unsigned int branch_num = gimple_switch_num_labels (swtch);
85638fd1498Szrj for (unsigned int i = 1; i < branch_num; i++)
85738fd1498Szrj {
85838fd1498Szrj tree lab = CASE_LABEL (gimple_switch_label (swtch, i));
85938fd1498Szrj if (label_to_block (lab) == bb)
86038fd1498Szrj {
86138fd1498Szrj info->reason = reason;
86238fd1498Szrj return false;
86338fd1498Szrj }
86438fd1498Szrj }
86538fd1498Szrj info->default_case_nonstandard = true;
86638fd1498Szrj }
86738fd1498Szrj }
86838fd1498Szrj }
86938fd1498Szrj }
87038fd1498Szrj
87138fd1498Szrj return true;
87238fd1498Szrj }
87338fd1498Szrj
87438fd1498Szrj /* The following function allocates default_values, target_{in,out}_names and
87538fd1498Szrj constructors arrays. The last one is also populated with pointers to
87638fd1498Szrj vectors that will become constructors of new arrays. */
87738fd1498Szrj
87838fd1498Szrj static void
create_temp_arrays(struct switch_conv_info * info)87938fd1498Szrj create_temp_arrays (struct switch_conv_info *info)
88038fd1498Szrj {
88138fd1498Szrj int i;
88238fd1498Szrj
88338fd1498Szrj info->default_values = XCNEWVEC (tree, info->phi_count * 3);
88438fd1498Szrj /* ??? Macros do not support multi argument templates in their
88538fd1498Szrj argument list. We create a typedef to work around that problem. */
88638fd1498Szrj typedef vec<constructor_elt, va_gc> *vec_constructor_elt_gc;
88738fd1498Szrj info->constructors = XCNEWVEC (vec_constructor_elt_gc, info->phi_count);
88838fd1498Szrj info->target_inbound_names = info->default_values + info->phi_count;
88938fd1498Szrj info->target_outbound_names = info->target_inbound_names + info->phi_count;
89038fd1498Szrj for (i = 0; i < info->phi_count; i++)
89138fd1498Szrj vec_alloc (info->constructors[i], tree_to_uhwi (info->range_size) + 1);
89238fd1498Szrj }
89338fd1498Szrj
89438fd1498Szrj /* Free the arrays created by create_temp_arrays(). The vectors that are
89538fd1498Szrj created by that function are not freed here, however, because they have
89638fd1498Szrj already become constructors and must be preserved. */
89738fd1498Szrj
89838fd1498Szrj static void
free_temp_arrays(struct switch_conv_info * info)89938fd1498Szrj free_temp_arrays (struct switch_conv_info *info)
90038fd1498Szrj {
90138fd1498Szrj XDELETEVEC (info->constructors);
90238fd1498Szrj XDELETEVEC (info->default_values);
90338fd1498Szrj }
90438fd1498Szrj
90538fd1498Szrj /* Populate the array of default values in the order of phi nodes.
90638fd1498Szrj DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch
90738fd1498Szrj if the range is non-contiguous or the default case has standard
90838fd1498Szrj structure, otherwise it is the first non-default case instead. */
90938fd1498Szrj
91038fd1498Szrj static void
gather_default_values(tree default_case,struct switch_conv_info * info)91138fd1498Szrj gather_default_values (tree default_case, struct switch_conv_info *info)
91238fd1498Szrj {
91338fd1498Szrj gphi_iterator gsi;
91438fd1498Szrj basic_block bb = label_to_block (CASE_LABEL (default_case));
91538fd1498Szrj edge e;
91638fd1498Szrj int i = 0;
91738fd1498Szrj
91838fd1498Szrj gcc_assert (CASE_LOW (default_case) == NULL_TREE
91938fd1498Szrj || info->default_case_nonstandard);
92038fd1498Szrj
92138fd1498Szrj if (bb == info->final_bb)
92238fd1498Szrj e = find_edge (info->switch_bb, bb);
92338fd1498Szrj else
92438fd1498Szrj e = single_succ_edge (bb);
92538fd1498Szrj
92638fd1498Szrj for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
92738fd1498Szrj {
92838fd1498Szrj gphi *phi = gsi.phi ();
92938fd1498Szrj if (virtual_operand_p (gimple_phi_result (phi)))
93038fd1498Szrj continue;
93138fd1498Szrj tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
93238fd1498Szrj gcc_assert (val);
93338fd1498Szrj info->default_values[i++] = val;
93438fd1498Szrj }
93538fd1498Szrj }
93638fd1498Szrj
93738fd1498Szrj /* The following function populates the vectors in the constructors array with
93838fd1498Szrj future contents of the static arrays. The vectors are populated in the
93938fd1498Szrj order of phi nodes. SWTCH is the switch statement being converted. */
94038fd1498Szrj
94138fd1498Szrj static void
build_constructors(gswitch * swtch,struct switch_conv_info * info)94238fd1498Szrj build_constructors (gswitch *swtch, struct switch_conv_info *info)
94338fd1498Szrj {
94438fd1498Szrj unsigned i, branch_num = gimple_switch_num_labels (swtch);
94538fd1498Szrj tree pos = info->range_min;
94638fd1498Szrj tree pos_one = build_int_cst (TREE_TYPE (pos), 1);
94738fd1498Szrj
94838fd1498Szrj for (i = 1; i < branch_num; i++)
94938fd1498Szrj {
95038fd1498Szrj tree cs = gimple_switch_label (swtch, i);
95138fd1498Szrj basic_block bb = label_to_block (CASE_LABEL (cs));
95238fd1498Szrj edge e;
95338fd1498Szrj tree high;
95438fd1498Szrj gphi_iterator gsi;
95538fd1498Szrj int j;
95638fd1498Szrj
95738fd1498Szrj if (bb == info->final_bb)
95838fd1498Szrj e = find_edge (info->switch_bb, bb);
95938fd1498Szrj else
96038fd1498Szrj e = single_succ_edge (bb);
96138fd1498Szrj gcc_assert (e);
96238fd1498Szrj
96338fd1498Szrj while (tree_int_cst_lt (pos, CASE_LOW (cs)))
96438fd1498Szrj {
96538fd1498Szrj int k;
96638fd1498Szrj gcc_assert (!info->contiguous_range);
96738fd1498Szrj for (k = 0; k < info->phi_count; k++)
96838fd1498Szrj {
96938fd1498Szrj constructor_elt elt;
97038fd1498Szrj
97138fd1498Szrj elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
97238fd1498Szrj elt.value
97338fd1498Szrj = unshare_expr_without_location (info->default_values[k]);
97438fd1498Szrj info->constructors[k]->quick_push (elt);
97538fd1498Szrj }
97638fd1498Szrj
97738fd1498Szrj pos = int_const_binop (PLUS_EXPR, pos, pos_one);
97838fd1498Szrj }
97938fd1498Szrj gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
98038fd1498Szrj
98138fd1498Szrj j = 0;
98238fd1498Szrj if (CASE_HIGH (cs))
98338fd1498Szrj high = CASE_HIGH (cs);
98438fd1498Szrj else
98538fd1498Szrj high = CASE_LOW (cs);
98638fd1498Szrj for (gsi = gsi_start_phis (info->final_bb);
98738fd1498Szrj !gsi_end_p (gsi); gsi_next (&gsi))
98838fd1498Szrj {
98938fd1498Szrj gphi *phi = gsi.phi ();
99038fd1498Szrj if (virtual_operand_p (gimple_phi_result (phi)))
99138fd1498Szrj continue;
99238fd1498Szrj tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
99338fd1498Szrj tree low = CASE_LOW (cs);
99438fd1498Szrj pos = CASE_LOW (cs);
99538fd1498Szrj
99638fd1498Szrj do
99738fd1498Szrj {
99838fd1498Szrj constructor_elt elt;
99938fd1498Szrj
100038fd1498Szrj elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
100138fd1498Szrj elt.value = unshare_expr_without_location (val);
100238fd1498Szrj info->constructors[j]->quick_push (elt);
100338fd1498Szrj
100438fd1498Szrj pos = int_const_binop (PLUS_EXPR, pos, pos_one);
100538fd1498Szrj } while (!tree_int_cst_lt (high, pos)
100638fd1498Szrj && tree_int_cst_lt (low, pos));
100738fd1498Szrj j++;
100838fd1498Szrj }
100938fd1498Szrj }
101038fd1498Szrj }
101138fd1498Szrj
101238fd1498Szrj /* If all values in the constructor vector are the same, return the value.
101338fd1498Szrj Otherwise return NULL_TREE. Not supposed to be called for empty
101438fd1498Szrj vectors. */
101538fd1498Szrj
101638fd1498Szrj static tree
constructor_contains_same_values_p(vec<constructor_elt,va_gc> * vec)101738fd1498Szrj constructor_contains_same_values_p (vec<constructor_elt, va_gc> *vec)
101838fd1498Szrj {
101938fd1498Szrj unsigned int i;
102038fd1498Szrj tree prev = NULL_TREE;
102138fd1498Szrj constructor_elt *elt;
102238fd1498Szrj
102338fd1498Szrj FOR_EACH_VEC_SAFE_ELT (vec, i, elt)
102438fd1498Szrj {
102538fd1498Szrj if (!prev)
102638fd1498Szrj prev = elt->value;
102738fd1498Szrj else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST))
102838fd1498Szrj return NULL_TREE;
102938fd1498Szrj }
103038fd1498Szrj return prev;
103138fd1498Szrj }
103238fd1498Szrj
103338fd1498Szrj /* Return type which should be used for array elements, either TYPE's
103438fd1498Szrj main variant or, for integral types, some smaller integral type
103538fd1498Szrj that can still hold all the constants. */
103638fd1498Szrj
103738fd1498Szrj static tree
array_value_type(gswitch * swtch,tree type,int num,struct switch_conv_info * info)103838fd1498Szrj array_value_type (gswitch *swtch, tree type, int num,
103938fd1498Szrj struct switch_conv_info *info)
104038fd1498Szrj {
104138fd1498Szrj unsigned int i, len = vec_safe_length (info->constructors[num]);
104238fd1498Szrj constructor_elt *elt;
104338fd1498Szrj int sign = 0;
104438fd1498Szrj tree smaller_type;
104538fd1498Szrj
104638fd1498Szrj /* Types with alignments greater than their size can reach here, e.g. out of
104738fd1498Szrj SRA. We couldn't use these as an array component type so get back to the
104838fd1498Szrj main variant first, which, for our purposes, is fine for other types as
104938fd1498Szrj well. */
105038fd1498Szrj
105138fd1498Szrj type = TYPE_MAIN_VARIANT (type);
105238fd1498Szrj
105338fd1498Szrj if (!INTEGRAL_TYPE_P (type))
105438fd1498Szrj return type;
105538fd1498Szrj
105638fd1498Szrj scalar_int_mode type_mode = SCALAR_INT_TYPE_MODE (type);
105738fd1498Szrj scalar_int_mode mode = get_narrowest_mode (type_mode);
105838fd1498Szrj if (GET_MODE_SIZE (type_mode) <= GET_MODE_SIZE (mode))
105938fd1498Szrj return type;
106038fd1498Szrj
106138fd1498Szrj if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32))
106238fd1498Szrj return type;
106338fd1498Szrj
106438fd1498Szrj FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
106538fd1498Szrj {
106638fd1498Szrj wide_int cst;
106738fd1498Szrj
106838fd1498Szrj if (TREE_CODE (elt->value) != INTEGER_CST)
106938fd1498Szrj return type;
107038fd1498Szrj
107138fd1498Szrj cst = wi::to_wide (elt->value);
107238fd1498Szrj while (1)
107338fd1498Szrj {
107438fd1498Szrj unsigned int prec = GET_MODE_BITSIZE (mode);
107538fd1498Szrj if (prec > HOST_BITS_PER_WIDE_INT)
107638fd1498Szrj return type;
107738fd1498Szrj
107838fd1498Szrj if (sign >= 0 && cst == wi::zext (cst, prec))
107938fd1498Szrj {
108038fd1498Szrj if (sign == 0 && cst == wi::sext (cst, prec))
108138fd1498Szrj break;
108238fd1498Szrj sign = 1;
108338fd1498Szrj break;
108438fd1498Szrj }
108538fd1498Szrj if (sign <= 0 && cst == wi::sext (cst, prec))
108638fd1498Szrj {
108738fd1498Szrj sign = -1;
108838fd1498Szrj break;
108938fd1498Szrj }
109038fd1498Szrj
109138fd1498Szrj if (sign == 1)
109238fd1498Szrj sign = 0;
109338fd1498Szrj
109438fd1498Szrj if (!GET_MODE_WIDER_MODE (mode).exists (&mode)
109538fd1498Szrj || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (type_mode))
109638fd1498Szrj return type;
109738fd1498Szrj }
109838fd1498Szrj }
109938fd1498Szrj
110038fd1498Szrj if (sign == 0)
110138fd1498Szrj sign = TYPE_UNSIGNED (type) ? 1 : -1;
110238fd1498Szrj smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0);
110338fd1498Szrj if (GET_MODE_SIZE (type_mode)
110438fd1498Szrj <= GET_MODE_SIZE (SCALAR_INT_TYPE_MODE (smaller_type)))
110538fd1498Szrj return type;
110638fd1498Szrj
110738fd1498Szrj return smaller_type;
110838fd1498Szrj }
110938fd1498Szrj
111038fd1498Szrj /* Create an appropriate array type and declaration and assemble a static array
111138fd1498Szrj variable. Also create a load statement that initializes the variable in
111238fd1498Szrj question with a value from the static array. SWTCH is the switch statement
111338fd1498Szrj being converted, NUM is the index to arrays of constructors, default values
111438fd1498Szrj and target SSA names for this particular array. ARR_INDEX_TYPE is the type
111538fd1498Szrj of the index of the new array, PHI is the phi node of the final BB that
111638fd1498Szrj corresponds to the value that will be loaded from the created array. TIDX
111738fd1498Szrj is an ssa name of a temporary variable holding the index for loads from the
111838fd1498Szrj new array. */
111938fd1498Szrj
112038fd1498Szrj static void
build_one_array(gswitch * swtch,int num,tree arr_index_type,gphi * phi,tree tidx,struct switch_conv_info * info)112138fd1498Szrj build_one_array (gswitch *swtch, int num, tree arr_index_type,
112238fd1498Szrj gphi *phi, tree tidx, struct switch_conv_info *info)
112338fd1498Szrj {
112438fd1498Szrj tree name, cst;
112538fd1498Szrj gimple *load;
112638fd1498Szrj gimple_stmt_iterator gsi = gsi_for_stmt (swtch);
112738fd1498Szrj location_t loc = gimple_location (swtch);
112838fd1498Szrj
112938fd1498Szrj gcc_assert (info->default_values[num]);
113038fd1498Szrj
113138fd1498Szrj name = copy_ssa_name (PHI_RESULT (phi));
113238fd1498Szrj info->target_inbound_names[num] = name;
113338fd1498Szrj
113438fd1498Szrj cst = constructor_contains_same_values_p (info->constructors[num]);
113538fd1498Szrj if (cst)
113638fd1498Szrj load = gimple_build_assign (name, cst);
113738fd1498Szrj else
113838fd1498Szrj {
113938fd1498Szrj tree array_type, ctor, decl, value_type, fetch, default_type;
114038fd1498Szrj
114138fd1498Szrj default_type = TREE_TYPE (info->default_values[num]);
114238fd1498Szrj value_type = array_value_type (swtch, default_type, num, info);
114338fd1498Szrj array_type = build_array_type (value_type, arr_index_type);
114438fd1498Szrj if (default_type != value_type)
114538fd1498Szrj {
114638fd1498Szrj unsigned int i;
114738fd1498Szrj constructor_elt *elt;
114838fd1498Szrj
114938fd1498Szrj FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
115038fd1498Szrj elt->value = fold_convert (value_type, elt->value);
115138fd1498Szrj }
115238fd1498Szrj ctor = build_constructor (array_type, info->constructors[num]);
115338fd1498Szrj TREE_CONSTANT (ctor) = true;
115438fd1498Szrj TREE_STATIC (ctor) = true;
115538fd1498Szrj
115638fd1498Szrj decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type);
115738fd1498Szrj TREE_STATIC (decl) = 1;
115838fd1498Szrj DECL_INITIAL (decl) = ctor;
115938fd1498Szrj
116038fd1498Szrj DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
116138fd1498Szrj DECL_ARTIFICIAL (decl) = 1;
116238fd1498Szrj DECL_IGNORED_P (decl) = 1;
116338fd1498Szrj TREE_CONSTANT (decl) = 1;
116438fd1498Szrj TREE_READONLY (decl) = 1;
116538fd1498Szrj DECL_IGNORED_P (decl) = 1;
116638fd1498Szrj if (offloading_function_p (cfun->decl))
116738fd1498Szrj DECL_ATTRIBUTES (decl)
116838fd1498Szrj = tree_cons (get_identifier ("omp declare target"), NULL_TREE,
116938fd1498Szrj NULL_TREE);
117038fd1498Szrj varpool_node::finalize_decl (decl);
117138fd1498Szrj
117238fd1498Szrj fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
117338fd1498Szrj NULL_TREE);
117438fd1498Szrj if (default_type != value_type)
117538fd1498Szrj {
117638fd1498Szrj fetch = fold_convert (default_type, fetch);
117738fd1498Szrj fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE,
117838fd1498Szrj true, GSI_SAME_STMT);
117938fd1498Szrj }
118038fd1498Szrj load = gimple_build_assign (name, fetch);
118138fd1498Szrj }
118238fd1498Szrj
118338fd1498Szrj gsi_insert_before (&gsi, load, GSI_SAME_STMT);
118438fd1498Szrj update_stmt (load);
118538fd1498Szrj info->arr_ref_last = load;
118638fd1498Szrj }
118738fd1498Szrj
118838fd1498Szrj /* Builds and initializes static arrays initialized with values gathered from
118938fd1498Szrj the SWTCH switch statement. Also creates statements that load values from
119038fd1498Szrj them. */
119138fd1498Szrj
119238fd1498Szrj static void
build_arrays(gswitch * swtch,struct switch_conv_info * info)119338fd1498Szrj build_arrays (gswitch *swtch, struct switch_conv_info *info)
119438fd1498Szrj {
119538fd1498Szrj tree arr_index_type;
119638fd1498Szrj tree tidx, sub, utype;
119738fd1498Szrj gimple *stmt;
119838fd1498Szrj gimple_stmt_iterator gsi;
119938fd1498Szrj gphi_iterator gpi;
120038fd1498Szrj int i;
120138fd1498Szrj location_t loc = gimple_location (swtch);
120238fd1498Szrj
120338fd1498Szrj gsi = gsi_for_stmt (swtch);
120438fd1498Szrj
120538fd1498Szrj /* Make sure we do not generate arithmetics in a subrange. */
120638fd1498Szrj utype = TREE_TYPE (info->index_expr);
120738fd1498Szrj if (TREE_TYPE (utype))
120838fd1498Szrj utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1);
120938fd1498Szrj else
121038fd1498Szrj utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
121138fd1498Szrj
121238fd1498Szrj arr_index_type = build_index_type (info->range_size);
121338fd1498Szrj tidx = make_ssa_name (utype);
121438fd1498Szrj sub = fold_build2_loc (loc, MINUS_EXPR, utype,
121538fd1498Szrj fold_convert_loc (loc, utype, info->index_expr),
121638fd1498Szrj fold_convert_loc (loc, utype, info->range_min));
121738fd1498Szrj sub = force_gimple_operand_gsi (&gsi, sub,
121838fd1498Szrj false, NULL, true, GSI_SAME_STMT);
121938fd1498Szrj stmt = gimple_build_assign (tidx, sub);
122038fd1498Szrj
122138fd1498Szrj gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
122238fd1498Szrj update_stmt (stmt);
122338fd1498Szrj info->arr_ref_first = stmt;
122438fd1498Szrj
122538fd1498Szrj for (gpi = gsi_start_phis (info->final_bb), i = 0;
122638fd1498Szrj !gsi_end_p (gpi); gsi_next (&gpi))
122738fd1498Szrj {
122838fd1498Szrj gphi *phi = gpi.phi ();
122938fd1498Szrj if (!virtual_operand_p (gimple_phi_result (phi)))
123038fd1498Szrj build_one_array (swtch, i++, arr_index_type, phi, tidx, info);
123138fd1498Szrj else
123238fd1498Szrj {
123338fd1498Szrj edge e;
123438fd1498Szrj edge_iterator ei;
123538fd1498Szrj FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
123638fd1498Szrj {
123738fd1498Szrj if (e->dest == info->final_bb)
123838fd1498Szrj break;
123938fd1498Szrj if (!info->default_case_nonstandard
124038fd1498Szrj || e->dest != info->default_bb)
124138fd1498Szrj {
124238fd1498Szrj e = single_succ_edge (e->dest);
124338fd1498Szrj break;
124438fd1498Szrj }
124538fd1498Szrj }
124638fd1498Szrj gcc_assert (e && e->dest == info->final_bb);
124738fd1498Szrj info->target_vop = PHI_ARG_DEF_FROM_EDGE (phi, e);
124838fd1498Szrj }
124938fd1498Szrj }
125038fd1498Szrj }
125138fd1498Szrj
125238fd1498Szrj /* Generates and appropriately inserts loads of default values at the position
125338fd1498Szrj given by BSI. Returns the last inserted statement. */
125438fd1498Szrj
125538fd1498Szrj static gassign *
gen_def_assigns(gimple_stmt_iterator * gsi,struct switch_conv_info * info)125638fd1498Szrj gen_def_assigns (gimple_stmt_iterator *gsi, struct switch_conv_info *info)
125738fd1498Szrj {
125838fd1498Szrj int i;
125938fd1498Szrj gassign *assign = NULL;
126038fd1498Szrj
126138fd1498Szrj for (i = 0; i < info->phi_count; i++)
126238fd1498Szrj {
126338fd1498Szrj tree name = copy_ssa_name (info->target_inbound_names[i]);
126438fd1498Szrj info->target_outbound_names[i] = name;
126538fd1498Szrj assign = gimple_build_assign (name, info->default_values[i]);
126638fd1498Szrj gsi_insert_before (gsi, assign, GSI_SAME_STMT);
126738fd1498Szrj update_stmt (assign);
126838fd1498Szrj }
126938fd1498Szrj return assign;
127038fd1498Szrj }
127138fd1498Szrj
127238fd1498Szrj /* Deletes the unused bbs and edges that now contain the switch statement and
127338fd1498Szrj its empty branch bbs. BBD is the now dead BB containing the original switch
127438fd1498Szrj statement, FINAL is the last BB of the converted switch statement (in terms
127538fd1498Szrj of succession). */
127638fd1498Szrj
127738fd1498Szrj static void
prune_bbs(basic_block bbd,basic_block final,basic_block default_bb)127838fd1498Szrj prune_bbs (basic_block bbd, basic_block final, basic_block default_bb)
127938fd1498Szrj {
128038fd1498Szrj edge_iterator ei;
128138fd1498Szrj edge e;
128238fd1498Szrj
128338fd1498Szrj for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
128438fd1498Szrj {
128538fd1498Szrj basic_block bb;
128638fd1498Szrj bb = e->dest;
128738fd1498Szrj remove_edge (e);
128838fd1498Szrj if (bb != final && bb != default_bb)
128938fd1498Szrj delete_basic_block (bb);
129038fd1498Szrj }
129138fd1498Szrj delete_basic_block (bbd);
129238fd1498Szrj }
129338fd1498Szrj
129438fd1498Szrj /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
129538fd1498Szrj from the basic block loading values from an array and E2F from the basic
129638fd1498Szrj block loading default values. BBF is the last switch basic block (see the
129738fd1498Szrj bbf description in the comment below). */
129838fd1498Szrj
129938fd1498Szrj static void
fix_phi_nodes(edge e1f,edge e2f,basic_block bbf,struct switch_conv_info * info)130038fd1498Szrj fix_phi_nodes (edge e1f, edge e2f, basic_block bbf,
130138fd1498Szrj struct switch_conv_info *info)
130238fd1498Szrj {
130338fd1498Szrj gphi_iterator gsi;
130438fd1498Szrj int i;
130538fd1498Szrj
130638fd1498Szrj for (gsi = gsi_start_phis (bbf), i = 0;
130738fd1498Szrj !gsi_end_p (gsi); gsi_next (&gsi))
130838fd1498Szrj {
130938fd1498Szrj gphi *phi = gsi.phi ();
131038fd1498Szrj tree inbound, outbound;
131138fd1498Szrj if (virtual_operand_p (gimple_phi_result (phi)))
131238fd1498Szrj inbound = outbound = info->target_vop;
131338fd1498Szrj else
131438fd1498Szrj {
131538fd1498Szrj inbound = info->target_inbound_names[i];
131638fd1498Szrj outbound = info->target_outbound_names[i++];
131738fd1498Szrj }
131838fd1498Szrj add_phi_arg (phi, inbound, e1f, UNKNOWN_LOCATION);
131938fd1498Szrj if (!info->default_case_nonstandard)
132038fd1498Szrj add_phi_arg (phi, outbound, e2f, UNKNOWN_LOCATION);
132138fd1498Szrj }
132238fd1498Szrj }
132338fd1498Szrj
132438fd1498Szrj /* Creates a check whether the switch expression value actually falls into the
132538fd1498Szrj range given by all the cases. If it does not, the temporaries are loaded
132638fd1498Szrj with default values instead. SWTCH is the switch statement being converted.
132738fd1498Szrj
132838fd1498Szrj bb0 is the bb with the switch statement, however, we'll end it with a
132938fd1498Szrj condition instead.
133038fd1498Szrj
133138fd1498Szrj bb1 is the bb to be used when the range check went ok. It is derived from
133238fd1498Szrj the switch BB
133338fd1498Szrj
133438fd1498Szrj bb2 is the bb taken when the expression evaluated outside of the range
133538fd1498Szrj covered by the created arrays. It is populated by loads of default
133638fd1498Szrj values.
133738fd1498Szrj
133838fd1498Szrj bbF is a fall through for both bb1 and bb2 and contains exactly what
133938fd1498Szrj originally followed the switch statement.
134038fd1498Szrj
134138fd1498Szrj bbD contains the switch statement (in the end). It is unreachable but we
134238fd1498Szrj still need to strip off its edges.
134338fd1498Szrj */
134438fd1498Szrj
134538fd1498Szrj static void
gen_inbound_check(gswitch * swtch,struct switch_conv_info * info)134638fd1498Szrj gen_inbound_check (gswitch *swtch, struct switch_conv_info *info)
134738fd1498Szrj {
134838fd1498Szrj tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION);
134938fd1498Szrj tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
135038fd1498Szrj tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION);
135138fd1498Szrj glabel *label1, *label2, *label3;
135238fd1498Szrj tree utype, tidx;
135338fd1498Szrj tree bound;
135438fd1498Szrj
135538fd1498Szrj gcond *cond_stmt;
135638fd1498Szrj
135738fd1498Szrj gassign *last_assign = NULL;
135838fd1498Szrj gimple_stmt_iterator gsi;
135938fd1498Szrj basic_block bb0, bb1, bb2, bbf, bbd;
136038fd1498Szrj edge e01 = NULL, e02, e21, e1d, e1f, e2f;
136138fd1498Szrj location_t loc = gimple_location (swtch);
136238fd1498Szrj
136338fd1498Szrj gcc_assert (info->default_values);
136438fd1498Szrj
136538fd1498Szrj bb0 = gimple_bb (swtch);
136638fd1498Szrj
136738fd1498Szrj tidx = gimple_assign_lhs (info->arr_ref_first);
136838fd1498Szrj utype = TREE_TYPE (tidx);
136938fd1498Szrj
137038fd1498Szrj /* (end of) block 0 */
137138fd1498Szrj gsi = gsi_for_stmt (info->arr_ref_first);
137238fd1498Szrj gsi_next (&gsi);
137338fd1498Szrj
137438fd1498Szrj bound = fold_convert_loc (loc, utype, info->range_size);
137538fd1498Szrj cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
137638fd1498Szrj gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
137738fd1498Szrj update_stmt (cond_stmt);
137838fd1498Szrj
137938fd1498Szrj /* block 2 */
138038fd1498Szrj if (!info->default_case_nonstandard)
138138fd1498Szrj {
138238fd1498Szrj label2 = gimple_build_label (label_decl2);
138338fd1498Szrj gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
138438fd1498Szrj last_assign = gen_def_assigns (&gsi, info);
138538fd1498Szrj }
138638fd1498Szrj
138738fd1498Szrj /* block 1 */
138838fd1498Szrj label1 = gimple_build_label (label_decl1);
138938fd1498Szrj gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
139038fd1498Szrj
139138fd1498Szrj /* block F */
139238fd1498Szrj gsi = gsi_start_bb (info->final_bb);
139338fd1498Szrj label3 = gimple_build_label (label_decl3);
139438fd1498Szrj gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
139538fd1498Szrj
139638fd1498Szrj /* cfg fix */
139738fd1498Szrj e02 = split_block (bb0, cond_stmt);
139838fd1498Szrj bb2 = e02->dest;
139938fd1498Szrj
140038fd1498Szrj if (info->default_case_nonstandard)
140138fd1498Szrj {
140238fd1498Szrj bb1 = bb2;
140338fd1498Szrj bb2 = info->default_bb;
140438fd1498Szrj e01 = e02;
140538fd1498Szrj e01->flags = EDGE_TRUE_VALUE;
140638fd1498Szrj e02 = make_edge (bb0, bb2, EDGE_FALSE_VALUE);
140738fd1498Szrj edge e_default = find_edge (bb1, bb2);
140838fd1498Szrj for (gphi_iterator gsi = gsi_start_phis (bb2);
140938fd1498Szrj !gsi_end_p (gsi); gsi_next (&gsi))
141038fd1498Szrj {
141138fd1498Szrj gphi *phi = gsi.phi ();
141238fd1498Szrj tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e_default);
141338fd1498Szrj add_phi_arg (phi, arg, e02,
141438fd1498Szrj gimple_phi_arg_location_from_edge (phi, e_default));
141538fd1498Szrj }
141638fd1498Szrj /* Partially fix the dominator tree, if it is available. */
141738fd1498Szrj if (dom_info_available_p (CDI_DOMINATORS))
141838fd1498Szrj redirect_immediate_dominators (CDI_DOMINATORS, bb1, bb0);
141938fd1498Szrj }
142038fd1498Szrj else
142138fd1498Szrj {
142238fd1498Szrj e21 = split_block (bb2, last_assign);
142338fd1498Szrj bb1 = e21->dest;
142438fd1498Szrj remove_edge (e21);
142538fd1498Szrj }
142638fd1498Szrj
142738fd1498Szrj e1d = split_block (bb1, info->arr_ref_last);
142838fd1498Szrj bbd = e1d->dest;
142938fd1498Szrj remove_edge (e1d);
143038fd1498Szrj
143138fd1498Szrj /* flags and profiles of the edge for in-range values */
143238fd1498Szrj if (!info->default_case_nonstandard)
143338fd1498Szrj e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
143438fd1498Szrj e01->probability = info->default_prob.invert ();
143538fd1498Szrj
143638fd1498Szrj /* flags and profiles of the edge taking care of out-of-range values */
143738fd1498Szrj e02->flags &= ~EDGE_FALLTHRU;
143838fd1498Szrj e02->flags |= EDGE_FALSE_VALUE;
143938fd1498Szrj e02->probability = info->default_prob;
144038fd1498Szrj
144138fd1498Szrj bbf = info->final_bb;
144238fd1498Szrj
144338fd1498Szrj e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
144438fd1498Szrj e1f->probability = profile_probability::always ();
144538fd1498Szrj
144638fd1498Szrj if (info->default_case_nonstandard)
144738fd1498Szrj e2f = NULL;
144838fd1498Szrj else
144938fd1498Szrj {
145038fd1498Szrj e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
145138fd1498Szrj e2f->probability = profile_probability::always ();
145238fd1498Szrj }
145338fd1498Szrj
145438fd1498Szrj /* frequencies of the new BBs */
145538fd1498Szrj bb1->count = e01->count ();
145638fd1498Szrj bb2->count = e02->count ();
145738fd1498Szrj if (!info->default_case_nonstandard)
145838fd1498Szrj bbf->count = e1f->count () + e2f->count ();
145938fd1498Szrj
146038fd1498Szrj /* Tidy blocks that have become unreachable. */
146138fd1498Szrj prune_bbs (bbd, info->final_bb,
146238fd1498Szrj info->default_case_nonstandard ? info->default_bb : NULL);
146338fd1498Szrj
146438fd1498Szrj /* Fixup the PHI nodes in bbF. */
146538fd1498Szrj fix_phi_nodes (e1f, e2f, bbf, info);
146638fd1498Szrj
146738fd1498Szrj /* Fix the dominator tree, if it is available. */
146838fd1498Szrj if (dom_info_available_p (CDI_DOMINATORS))
146938fd1498Szrj {
147038fd1498Szrj vec<basic_block> bbs_to_fix_dom;
147138fd1498Szrj
147238fd1498Szrj set_immediate_dominator (CDI_DOMINATORS, bb1, bb0);
147338fd1498Szrj if (!info->default_case_nonstandard)
147438fd1498Szrj set_immediate_dominator (CDI_DOMINATORS, bb2, bb0);
147538fd1498Szrj if (! get_immediate_dominator (CDI_DOMINATORS, bbf))
147638fd1498Szrj /* If bbD was the immediate dominator ... */
147738fd1498Szrj set_immediate_dominator (CDI_DOMINATORS, bbf, bb0);
147838fd1498Szrj
147938fd1498Szrj bbs_to_fix_dom.create (3 + (bb2 != bbf));
148038fd1498Szrj bbs_to_fix_dom.quick_push (bb0);
148138fd1498Szrj bbs_to_fix_dom.quick_push (bb1);
148238fd1498Szrj if (bb2 != bbf)
148338fd1498Szrj bbs_to_fix_dom.quick_push (bb2);
148438fd1498Szrj bbs_to_fix_dom.quick_push (bbf);
148538fd1498Szrj
148638fd1498Szrj iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
148738fd1498Szrj bbs_to_fix_dom.release ();
148838fd1498Szrj }
148938fd1498Szrj }
149038fd1498Szrj
149138fd1498Szrj /* The following function is invoked on every switch statement (the current one
149238fd1498Szrj is given in SWTCH) and runs the individual phases of switch conversion on it
149338fd1498Szrj one after another until one fails or the conversion is completed.
149438fd1498Szrj Returns NULL on success, or a pointer to a string with the reason why the
149538fd1498Szrj conversion failed. */
149638fd1498Szrj
149738fd1498Szrj static const char *
process_switch(gswitch * swtch)149838fd1498Szrj process_switch (gswitch *swtch)
149938fd1498Szrj {
150038fd1498Szrj struct switch_conv_info info;
150138fd1498Szrj
150238fd1498Szrj /* Group case labels so that we get the right results from the heuristics
150338fd1498Szrj that decide on the code generation approach for this switch. */
150438fd1498Szrj cfg_altered |= group_case_labels_stmt (swtch);
150538fd1498Szrj
150638fd1498Szrj /* If this switch is now a degenerate case with only a default label,
150738fd1498Szrj there is nothing left for us to do. */
150838fd1498Szrj if (gimple_switch_num_labels (swtch) < 2)
150938fd1498Szrj return "switch is a degenerate case";
151038fd1498Szrj
151138fd1498Szrj collect_switch_conv_info (swtch, &info);
151238fd1498Szrj
151338fd1498Szrj /* No error markers should reach here (they should be filtered out
151438fd1498Szrj during gimplification). */
151538fd1498Szrj gcc_checking_assert (TREE_TYPE (info.index_expr) != error_mark_node);
151638fd1498Szrj
151738fd1498Szrj /* A switch on a constant should have been optimized in tree-cfg-cleanup. */
151838fd1498Szrj gcc_checking_assert (! TREE_CONSTANT (info.index_expr));
151938fd1498Szrj
152038fd1498Szrj if (info.uniq <= MAX_CASE_BIT_TESTS)
152138fd1498Szrj {
152238fd1498Szrj if (expand_switch_using_bit_tests_p (info.range_size,
152338fd1498Szrj info.uniq, info.count,
152438fd1498Szrj optimize_bb_for_speed_p
152538fd1498Szrj (gimple_bb (swtch))))
152638fd1498Szrj {
152738fd1498Szrj if (dump_file)
152838fd1498Szrj fputs (" expanding as bit test is preferable\n", dump_file);
152938fd1498Szrj emit_case_bit_tests (swtch, info.index_expr, info.range_min,
153038fd1498Szrj info.range_size, info.range_max);
153138fd1498Szrj loops_state_set (LOOPS_NEED_FIXUP);
153238fd1498Szrj return NULL;
153338fd1498Szrj }
153438fd1498Szrj
153538fd1498Szrj if (info.uniq <= 2)
153638fd1498Szrj /* This will be expanded as a decision tree in stmt.c:expand_case. */
153738fd1498Szrj return " expanding as jumps is preferable";
153838fd1498Szrj }
153938fd1498Szrj
154038fd1498Szrj /* If there is no common successor, we cannot do the transformation. */
154138fd1498Szrj if (! info.final_bb)
154238fd1498Szrj return "no common successor to all case label target blocks found";
154338fd1498Szrj
154438fd1498Szrj /* Check the case label values are within reasonable range: */
154538fd1498Szrj if (!check_range (&info))
154638fd1498Szrj {
154738fd1498Szrj gcc_assert (info.reason);
154838fd1498Szrj return info.reason;
154938fd1498Szrj }
155038fd1498Szrj
155138fd1498Szrj /* For all the cases, see whether they are empty, the assignments they
155238fd1498Szrj represent constant and so on... */
155338fd1498Szrj if (! check_all_empty_except_final (&info))
155438fd1498Szrj {
155538fd1498Szrj gcc_assert (info.reason);
155638fd1498Szrj return info.reason;
155738fd1498Szrj }
155838fd1498Szrj if (!check_final_bb (swtch, &info))
155938fd1498Szrj {
156038fd1498Szrj gcc_assert (info.reason);
156138fd1498Szrj return info.reason;
156238fd1498Szrj }
156338fd1498Szrj
156438fd1498Szrj /* At this point all checks have passed and we can proceed with the
156538fd1498Szrj transformation. */
156638fd1498Szrj
156738fd1498Szrj create_temp_arrays (&info);
156838fd1498Szrj gather_default_values (info.default_case_nonstandard
156938fd1498Szrj ? gimple_switch_label (swtch, 1)
157038fd1498Szrj : gimple_switch_default_label (swtch), &info);
157138fd1498Szrj if (info.phi_count)
157238fd1498Szrj build_constructors (swtch, &info);
157338fd1498Szrj
157438fd1498Szrj build_arrays (swtch, &info); /* Build the static arrays and assignments. */
157538fd1498Szrj gen_inbound_check (swtch, &info); /* Build the bounds check. */
157638fd1498Szrj
157738fd1498Szrj /* Cleanup: */
157838fd1498Szrj free_temp_arrays (&info);
157938fd1498Szrj return NULL;
158038fd1498Szrj }
158138fd1498Szrj
158238fd1498Szrj /* The main function of the pass scans statements for switches and invokes
158338fd1498Szrj process_switch on them. */
158438fd1498Szrj
158538fd1498Szrj namespace {
158638fd1498Szrj
158738fd1498Szrj const pass_data pass_data_convert_switch =
158838fd1498Szrj {
158938fd1498Szrj GIMPLE_PASS, /* type */
159038fd1498Szrj "switchconv", /* name */
159138fd1498Szrj OPTGROUP_NONE, /* optinfo_flags */
159238fd1498Szrj TV_TREE_SWITCH_CONVERSION, /* tv_id */
159338fd1498Szrj ( PROP_cfg | PROP_ssa ), /* properties_required */
159438fd1498Szrj 0, /* properties_provided */
159538fd1498Szrj 0, /* properties_destroyed */
159638fd1498Szrj 0, /* todo_flags_start */
159738fd1498Szrj TODO_update_ssa, /* todo_flags_finish */
159838fd1498Szrj };
159938fd1498Szrj
160038fd1498Szrj class pass_convert_switch : public gimple_opt_pass
160138fd1498Szrj {
160238fd1498Szrj public:
pass_convert_switch(gcc::context * ctxt)160338fd1498Szrj pass_convert_switch (gcc::context *ctxt)
160438fd1498Szrj : gimple_opt_pass (pass_data_convert_switch, ctxt)
160538fd1498Szrj {}
160638fd1498Szrj
160738fd1498Szrj /* opt_pass methods: */
gate(function *)160838fd1498Szrj virtual bool gate (function *) { return flag_tree_switch_conversion != 0; }
160938fd1498Szrj virtual unsigned int execute (function *);
161038fd1498Szrj
161138fd1498Szrj }; // class pass_convert_switch
161238fd1498Szrj
161338fd1498Szrj unsigned int
execute(function * fun)161438fd1498Szrj pass_convert_switch::execute (function *fun)
161538fd1498Szrj {
161638fd1498Szrj basic_block bb;
161738fd1498Szrj
161838fd1498Szrj cfg_altered = false;
161938fd1498Szrj FOR_EACH_BB_FN (bb, fun)
162038fd1498Szrj {
162138fd1498Szrj const char *failure_reason;
162238fd1498Szrj gimple *stmt = last_stmt (bb);
162338fd1498Szrj if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
162438fd1498Szrj {
162538fd1498Szrj if (dump_file)
162638fd1498Szrj {
162738fd1498Szrj expanded_location loc = expand_location (gimple_location (stmt));
162838fd1498Szrj
162938fd1498Szrj fprintf (dump_file, "beginning to process the following "
163038fd1498Szrj "SWITCH statement (%s:%d) : ------- \n",
163138fd1498Szrj loc.file, loc.line);
163238fd1498Szrj print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
163338fd1498Szrj putc ('\n', dump_file);
163438fd1498Szrj }
163538fd1498Szrj
163638fd1498Szrj failure_reason = process_switch (as_a <gswitch *> (stmt));
163738fd1498Szrj if (! failure_reason)
163838fd1498Szrj {
163938fd1498Szrj cfg_altered = true;
164038fd1498Szrj if (dump_file)
164138fd1498Szrj {
164238fd1498Szrj fputs ("Switch converted\n", dump_file);
164338fd1498Szrj fputs ("--------------------------------\n", dump_file);
164438fd1498Szrj }
164538fd1498Szrj
164638fd1498Szrj /* Make no effort to update the post-dominator tree. It is actually not
164738fd1498Szrj that hard for the transformations we have performed, but it is not
164838fd1498Szrj supported by iterate_fix_dominators. */
164938fd1498Szrj free_dominance_info (CDI_POST_DOMINATORS);
165038fd1498Szrj }
165138fd1498Szrj else
165238fd1498Szrj {
165338fd1498Szrj if (dump_file)
165438fd1498Szrj {
165538fd1498Szrj fputs ("Bailing out - ", dump_file);
165638fd1498Szrj fputs (failure_reason, dump_file);
165738fd1498Szrj fputs ("\n--------------------------------\n", dump_file);
165838fd1498Szrj }
165938fd1498Szrj }
166038fd1498Szrj }
166138fd1498Szrj }
166238fd1498Szrj
166338fd1498Szrj return cfg_altered ? TODO_cleanup_cfg : 0;
166438fd1498Szrj }
166538fd1498Szrj
166638fd1498Szrj } // anon namespace
166738fd1498Szrj
166838fd1498Szrj gimple_opt_pass *
make_pass_convert_switch(gcc::context * ctxt)166938fd1498Szrj make_pass_convert_switch (gcc::context *ctxt)
167038fd1498Szrj {
167138fd1498Szrj return new pass_convert_switch (ctxt);
167238fd1498Szrj }
167338fd1498Szrj
167438fd1498Szrj struct case_node
167538fd1498Szrj {
167638fd1498Szrj case_node *left; /* Left son in binary tree. */
167738fd1498Szrj case_node *right; /* Right son in binary tree;
167838fd1498Szrj also node chain. */
167938fd1498Szrj case_node *parent; /* Parent of node in binary tree. */
168038fd1498Szrj tree low; /* Lowest index value for this label. */
168138fd1498Szrj tree high; /* Highest index value for this label. */
168238fd1498Szrj basic_block case_bb; /* Label to jump to when node matches. */
168338fd1498Szrj tree case_label; /* Label to jump to when node matches. */
168438fd1498Szrj profile_probability prob; /* Probability of taking this case. */
168538fd1498Szrj profile_probability subtree_prob; /* Probability of reaching subtree
168638fd1498Szrj rooted at this node. */
168738fd1498Szrj };
168838fd1498Szrj
168938fd1498Szrj typedef case_node *case_node_ptr;
169038fd1498Szrj
169138fd1498Szrj static basic_block emit_case_nodes (basic_block, tree, case_node_ptr,
169238fd1498Szrj basic_block, tree, profile_probability,
1693*58e805e6Szrj tree, hash_map<tree, tree> *, location_t);
169438fd1498Szrj static bool node_has_low_bound (case_node_ptr, tree);
169538fd1498Szrj static bool node_has_high_bound (case_node_ptr, tree);
169638fd1498Szrj static bool node_is_bounded (case_node_ptr, tree);
169738fd1498Szrj
169838fd1498Szrj /* Return the smallest number of different values for which it is best to use a
169938fd1498Szrj jump-table instead of a tree of conditional branches. */
170038fd1498Szrj
170138fd1498Szrj static unsigned int
case_values_threshold(void)170238fd1498Szrj case_values_threshold (void)
170338fd1498Szrj {
170438fd1498Szrj unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
170538fd1498Szrj
170638fd1498Szrj if (threshold == 0)
170738fd1498Szrj threshold = targetm.case_values_threshold ();
170838fd1498Szrj
170938fd1498Szrj return threshold;
171038fd1498Szrj }
171138fd1498Szrj
171238fd1498Szrj /* Reset the aux field of all outgoing edges of basic block BB. */
171338fd1498Szrj
171438fd1498Szrj static inline void
reset_out_edges_aux(basic_block bb)171538fd1498Szrj reset_out_edges_aux (basic_block bb)
171638fd1498Szrj {
171738fd1498Szrj edge e;
171838fd1498Szrj edge_iterator ei;
171938fd1498Szrj FOR_EACH_EDGE (e, ei, bb->succs)
172038fd1498Szrj e->aux = (void *) 0;
172138fd1498Szrj }
172238fd1498Szrj
172338fd1498Szrj /* Compute the number of case labels that correspond to each outgoing edge of
172438fd1498Szrj STMT. Record this information in the aux field of the edge. */
172538fd1498Szrj
172638fd1498Szrj static inline void
compute_cases_per_edge(gswitch * stmt)172738fd1498Szrj compute_cases_per_edge (gswitch *stmt)
172838fd1498Szrj {
172938fd1498Szrj basic_block bb = gimple_bb (stmt);
173038fd1498Szrj reset_out_edges_aux (bb);
173138fd1498Szrj int ncases = gimple_switch_num_labels (stmt);
173238fd1498Szrj for (int i = ncases - 1; i >= 1; --i)
173338fd1498Szrj {
173438fd1498Szrj tree elt = gimple_switch_label (stmt, i);
173538fd1498Szrj tree lab = CASE_LABEL (elt);
173638fd1498Szrj basic_block case_bb = label_to_block_fn (cfun, lab);
173738fd1498Szrj edge case_edge = find_edge (bb, case_bb);
173838fd1498Szrj case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + 1);
173938fd1498Szrj }
174038fd1498Szrj }
174138fd1498Szrj
174238fd1498Szrj /* Do the insertion of a case label into case_list. The labels are
174338fd1498Szrj fed to us in descending order from the sorted vector of case labels used
174438fd1498Szrj in the tree part of the middle end. So the list we construct is
174538fd1498Szrj sorted in ascending order.
174638fd1498Szrj
174738fd1498Szrj LABEL is the case label to be inserted. LOW and HIGH are the bounds
174838fd1498Szrj against which the index is compared to jump to LABEL and PROB is the
174938fd1498Szrj estimated probability LABEL is reached from the switch statement. */
175038fd1498Szrj
175138fd1498Szrj static case_node *
add_case_node(case_node * head,tree low,tree high,basic_block case_bb,tree case_label,profile_probability prob,object_allocator<case_node> & case_node_pool)175238fd1498Szrj add_case_node (case_node *head, tree low, tree high, basic_block case_bb,
175338fd1498Szrj tree case_label, profile_probability prob,
175438fd1498Szrj object_allocator<case_node> &case_node_pool)
175538fd1498Szrj {
175638fd1498Szrj case_node *r;
175738fd1498Szrj
175838fd1498Szrj gcc_checking_assert (low);
175938fd1498Szrj gcc_checking_assert (high && (TREE_TYPE (low) == TREE_TYPE (high)));
176038fd1498Szrj
176138fd1498Szrj /* Add this label to the chain. */
176238fd1498Szrj r = case_node_pool.allocate ();
176338fd1498Szrj r->low = low;
176438fd1498Szrj r->high = high;
176538fd1498Szrj r->case_bb = case_bb;
176638fd1498Szrj r->case_label = case_label;
176738fd1498Szrj r->parent = r->left = NULL;
176838fd1498Szrj r->prob = prob;
176938fd1498Szrj r->subtree_prob = prob;
177038fd1498Szrj r->right = head;
177138fd1498Szrj return r;
177238fd1498Szrj }
177338fd1498Szrj
177438fd1498Szrj /* Dump ROOT, a list or tree of case nodes, to file. */
177538fd1498Szrj
177638fd1498Szrj static void
dump_case_nodes(FILE * f,case_node * root,int indent_step,int indent_level)177738fd1498Szrj dump_case_nodes (FILE *f, case_node *root, int indent_step, int indent_level)
177838fd1498Szrj {
177938fd1498Szrj if (root == 0)
178038fd1498Szrj return;
178138fd1498Szrj indent_level++;
178238fd1498Szrj
178338fd1498Szrj dump_case_nodes (f, root->left, indent_step, indent_level);
178438fd1498Szrj
178538fd1498Szrj fputs (";; ", f);
178638fd1498Szrj fprintf (f, "%*s", indent_step * indent_level, "");
178738fd1498Szrj print_dec (wi::to_wide (root->low), f, TYPE_SIGN (TREE_TYPE (root->low)));
178838fd1498Szrj if (!tree_int_cst_equal (root->low, root->high))
178938fd1498Szrj {
179038fd1498Szrj fprintf (f, " ... ");
179138fd1498Szrj print_dec (wi::to_wide (root->high), f,
179238fd1498Szrj TYPE_SIGN (TREE_TYPE (root->high)));
179338fd1498Szrj }
179438fd1498Szrj fputs ("\n", f);
179538fd1498Szrj
179638fd1498Szrj dump_case_nodes (f, root->right, indent_step, indent_level);
179738fd1498Szrj }
179838fd1498Szrj
179938fd1498Szrj /* Take an ordered list of case nodes
180038fd1498Szrj and transform them into a near optimal binary tree,
180138fd1498Szrj on the assumption that any target code selection value is as
180238fd1498Szrj likely as any other.
180338fd1498Szrj
180438fd1498Szrj The transformation is performed by splitting the ordered
180538fd1498Szrj list into two equal sections plus a pivot. The parts are
180638fd1498Szrj then attached to the pivot as left and right branches. Each
180738fd1498Szrj branch is then transformed recursively. */
180838fd1498Szrj
180938fd1498Szrj static void
balance_case_nodes(case_node_ptr * head,case_node_ptr parent)181038fd1498Szrj balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
181138fd1498Szrj {
181238fd1498Szrj case_node_ptr np;
181338fd1498Szrj
181438fd1498Szrj np = *head;
181538fd1498Szrj if (np)
181638fd1498Szrj {
181738fd1498Szrj int i = 0;
181838fd1498Szrj int ranges = 0;
181938fd1498Szrj case_node_ptr *npp;
182038fd1498Szrj case_node_ptr left;
182138fd1498Szrj
182238fd1498Szrj /* Count the number of entries on branch. Also count the ranges. */
182338fd1498Szrj
182438fd1498Szrj while (np)
182538fd1498Szrj {
182638fd1498Szrj if (!tree_int_cst_equal (np->low, np->high))
182738fd1498Szrj ranges++;
182838fd1498Szrj
182938fd1498Szrj i++;
183038fd1498Szrj np = np->right;
183138fd1498Szrj }
183238fd1498Szrj
183338fd1498Szrj if (i > 2)
183438fd1498Szrj {
183538fd1498Szrj /* Split this list if it is long enough for that to help. */
183638fd1498Szrj npp = head;
183738fd1498Szrj left = *npp;
183838fd1498Szrj
183938fd1498Szrj /* If there are just three nodes, split at the middle one. */
184038fd1498Szrj if (i == 3)
184138fd1498Szrj npp = &(*npp)->right;
184238fd1498Szrj else
184338fd1498Szrj {
184438fd1498Szrj /* Find the place in the list that bisects the list's total cost,
184538fd1498Szrj where ranges count as 2.
184638fd1498Szrj Here I gets half the total cost. */
184738fd1498Szrj i = (i + ranges + 1) / 2;
184838fd1498Szrj while (1)
184938fd1498Szrj {
185038fd1498Szrj /* Skip nodes while their cost does not reach that amount. */
185138fd1498Szrj if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
185238fd1498Szrj i--;
185338fd1498Szrj i--;
185438fd1498Szrj if (i <= 0)
185538fd1498Szrj break;
185638fd1498Szrj npp = &(*npp)->right;
185738fd1498Szrj }
185838fd1498Szrj }
185938fd1498Szrj *head = np = *npp;
186038fd1498Szrj *npp = 0;
186138fd1498Szrj np->parent = parent;
186238fd1498Szrj np->left = left;
186338fd1498Szrj
186438fd1498Szrj /* Optimize each of the two split parts. */
186538fd1498Szrj balance_case_nodes (&np->left, np);
186638fd1498Szrj balance_case_nodes (&np->right, np);
186738fd1498Szrj np->subtree_prob = np->prob;
186838fd1498Szrj np->subtree_prob += np->left->subtree_prob;
186938fd1498Szrj np->subtree_prob += np->right->subtree_prob;
187038fd1498Szrj }
187138fd1498Szrj else
187238fd1498Szrj {
187338fd1498Szrj /* Else leave this branch as one level,
187438fd1498Szrj but fill in `parent' fields. */
187538fd1498Szrj np = *head;
187638fd1498Szrj np->parent = parent;
187738fd1498Szrj np->subtree_prob = np->prob;
187838fd1498Szrj for (; np->right; np = np->right)
187938fd1498Szrj {
188038fd1498Szrj np->right->parent = np;
188138fd1498Szrj (*head)->subtree_prob += np->right->subtree_prob;
188238fd1498Szrj }
188338fd1498Szrj }
188438fd1498Szrj }
188538fd1498Szrj }
188638fd1498Szrj
188738fd1498Szrj /* Return true if a switch should be expanded as a decision tree.
188838fd1498Szrj RANGE is the difference between highest and lowest case.
188938fd1498Szrj UNIQ is number of unique case node targets, not counting the default case.
189038fd1498Szrj COUNT is the number of comparisons needed, not counting the default case. */
189138fd1498Szrj
189238fd1498Szrj static bool
expand_switch_as_decision_tree_p(tree range,unsigned int uniq ATTRIBUTE_UNUSED,unsigned int count)189338fd1498Szrj expand_switch_as_decision_tree_p (tree range,
189438fd1498Szrj unsigned int uniq ATTRIBUTE_UNUSED,
189538fd1498Szrj unsigned int count)
189638fd1498Szrj {
189738fd1498Szrj int max_ratio;
189838fd1498Szrj
189938fd1498Szrj /* If neither casesi or tablejump is available, or flag_jump_tables
190038fd1498Szrj over-ruled us, we really have no choice. */
190138fd1498Szrj if (!targetm.have_casesi () && !targetm.have_tablejump ())
190238fd1498Szrj return true;
190338fd1498Szrj if (!flag_jump_tables)
190438fd1498Szrj return true;
190538fd1498Szrj #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
190638fd1498Szrj if (flag_pic)
190738fd1498Szrj return true;
190838fd1498Szrj #endif
190938fd1498Szrj
191038fd1498Szrj /* If the switch is relatively small such that the cost of one
191138fd1498Szrj indirect jump on the target are higher than the cost of a
191238fd1498Szrj decision tree, go with the decision tree.
191338fd1498Szrj
191438fd1498Szrj If range of values is much bigger than number of values,
191538fd1498Szrj or if it is too large to represent in a HOST_WIDE_INT,
191638fd1498Szrj make a sequence of conditional branches instead of a dispatch.
191738fd1498Szrj
191838fd1498Szrj The definition of "much bigger" depends on whether we are
191938fd1498Szrj optimizing for size or for speed. If the former, the maximum
192038fd1498Szrj ratio range/count = 3, because this was found to be the optimal
192138fd1498Szrj ratio for size on i686-pc-linux-gnu, see PR11823. The ratio
192238fd1498Szrj 10 is much older, and was probably selected after an extensive
192338fd1498Szrj benchmarking investigation on numerous platforms. Or maybe it
192438fd1498Szrj just made sense to someone at some point in the history of GCC,
192538fd1498Szrj who knows... */
192638fd1498Szrj max_ratio = optimize_insn_for_size_p () ? 3 : 10;
192738fd1498Szrj if (count < case_values_threshold () || !tree_fits_uhwi_p (range)
192838fd1498Szrj || compare_tree_int (range, max_ratio * count) > 0)
192938fd1498Szrj return true;
193038fd1498Szrj
193138fd1498Szrj return false;
193238fd1498Szrj }
193338fd1498Szrj
193438fd1498Szrj static void
fix_phi_operands_for_edge(edge e,hash_map<tree,tree> * phi_mapping)193538fd1498Szrj fix_phi_operands_for_edge (edge e, hash_map<tree, tree> *phi_mapping)
193638fd1498Szrj {
193738fd1498Szrj basic_block bb = e->dest;
193838fd1498Szrj gphi_iterator gsi;
193938fd1498Szrj for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
194038fd1498Szrj {
194138fd1498Szrj gphi *phi = gsi.phi ();
194238fd1498Szrj
194338fd1498Szrj tree *definition = phi_mapping->get (gimple_phi_result (phi));
194438fd1498Szrj if (definition)
194538fd1498Szrj add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION);
194638fd1498Szrj }
194738fd1498Szrj }
194838fd1498Szrj
194938fd1498Szrj
195038fd1498Szrj /* Add an unconditional jump to CASE_BB that happens in basic block BB. */
195138fd1498Szrj
195238fd1498Szrj static void
emit_jump(basic_block bb,basic_block case_bb,hash_map<tree,tree> * phi_mapping)195338fd1498Szrj emit_jump (basic_block bb, basic_block case_bb,
195438fd1498Szrj hash_map<tree, tree> *phi_mapping)
195538fd1498Szrj {
195638fd1498Szrj edge e = single_succ_edge (bb);
195738fd1498Szrj redirect_edge_succ (e, case_bb);
195838fd1498Szrj fix_phi_operands_for_edge (e, phi_mapping);
195938fd1498Szrj }
196038fd1498Szrj
196138fd1498Szrj /* Generate a decision tree, switching on INDEX_EXPR and jumping to
196238fd1498Szrj one of the labels in CASE_LIST or to the DEFAULT_LABEL.
196338fd1498Szrj DEFAULT_PROB is the estimated probability that it jumps to
196438fd1498Szrj DEFAULT_LABEL.
196538fd1498Szrj
196638fd1498Szrj We generate a binary decision tree to select the appropriate target
196738fd1498Szrj code. */
196838fd1498Szrj
196938fd1498Szrj static void
emit_case_decision_tree(gswitch * s,tree index_expr,tree index_type,case_node_ptr case_list,basic_block default_bb,tree default_label,profile_probability default_prob,hash_map<tree,tree> * phi_mapping)197038fd1498Szrj emit_case_decision_tree (gswitch *s, tree index_expr, tree index_type,
197138fd1498Szrj case_node_ptr case_list, basic_block default_bb,
197238fd1498Szrj tree default_label, profile_probability default_prob,
197338fd1498Szrj hash_map<tree, tree> *phi_mapping)
197438fd1498Szrj {
197538fd1498Szrj balance_case_nodes (&case_list, NULL);
197638fd1498Szrj
197738fd1498Szrj if (dump_file)
197838fd1498Szrj dump_function_to_file (current_function_decl, dump_file, dump_flags);
197938fd1498Szrj if (dump_file && (dump_flags & TDF_DETAILS))
198038fd1498Szrj {
198138fd1498Szrj int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
198238fd1498Szrj fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
198338fd1498Szrj dump_case_nodes (dump_file, case_list, indent_step, 0);
198438fd1498Szrj }
198538fd1498Szrj
198638fd1498Szrj basic_block bb = gimple_bb (s);
198738fd1498Szrj gimple_stmt_iterator gsi = gsi_last_bb (bb);
198838fd1498Szrj edge e;
198938fd1498Szrj if (gsi_end_p (gsi))
199038fd1498Szrj e = split_block_after_labels (bb);
199138fd1498Szrj else
199238fd1498Szrj {
199338fd1498Szrj gsi_prev (&gsi);
199438fd1498Szrj e = split_block (bb, gsi_stmt (gsi));
199538fd1498Szrj }
199638fd1498Szrj bb = split_edge (e);
199738fd1498Szrj
199838fd1498Szrj bb = emit_case_nodes (bb, index_expr, case_list, default_bb, default_label,
1999*58e805e6Szrj default_prob, index_type, phi_mapping,
2000*58e805e6Szrj gimple_location (s));
200138fd1498Szrj
200238fd1498Szrj if (bb)
200338fd1498Szrj emit_jump (bb, default_bb, phi_mapping);
200438fd1498Szrj
200538fd1498Szrj /* Remove all edges and do just an edge that will reach default_bb. */
200638fd1498Szrj gsi = gsi_last_bb (gimple_bb (s));
200738fd1498Szrj gsi_remove (&gsi, true);
200838fd1498Szrj }
200938fd1498Szrj
201038fd1498Szrj static void
record_phi_operand_mapping(const vec<basic_block> bbs,basic_block switch_bb,hash_map<tree,tree> * map)201138fd1498Szrj record_phi_operand_mapping (const vec<basic_block> bbs, basic_block switch_bb,
201238fd1498Szrj hash_map <tree, tree> *map)
201338fd1498Szrj {
201438fd1498Szrj /* Record all PHI nodes that have to be fixed after conversion. */
201538fd1498Szrj for (unsigned i = 0; i < bbs.length (); i++)
201638fd1498Szrj {
201738fd1498Szrj basic_block bb = bbs[i];
201838fd1498Szrj
201938fd1498Szrj gphi_iterator gsi;
202038fd1498Szrj for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
202138fd1498Szrj {
202238fd1498Szrj gphi *phi = gsi.phi ();
202338fd1498Szrj
202438fd1498Szrj for (unsigned i = 0; i < gimple_phi_num_args (phi); i++)
202538fd1498Szrj {
202638fd1498Szrj basic_block phi_src_bb = gimple_phi_arg_edge (phi, i)->src;
202738fd1498Szrj if (phi_src_bb == switch_bb)
202838fd1498Szrj {
202938fd1498Szrj tree def = gimple_phi_arg_def (phi, i);
203038fd1498Szrj tree result = gimple_phi_result (phi);
203138fd1498Szrj map->put (result, def);
203238fd1498Szrj break;
203338fd1498Szrj }
203438fd1498Szrj }
203538fd1498Szrj }
203638fd1498Szrj }
203738fd1498Szrj }
203838fd1498Szrj
203938fd1498Szrj /* Attempt to expand gimple switch STMT to a decision tree. */
204038fd1498Szrj
204138fd1498Szrj static bool
try_switch_expansion(gswitch * stmt)204238fd1498Szrj try_switch_expansion (gswitch *stmt)
204338fd1498Szrj {
204438fd1498Szrj tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
204538fd1498Szrj basic_block default_bb;
204638fd1498Szrj unsigned int count, uniq;
204738fd1498Szrj int i;
204838fd1498Szrj int ncases = gimple_switch_num_labels (stmt);
204938fd1498Szrj tree index_expr = gimple_switch_index (stmt);
205038fd1498Szrj tree index_type = TREE_TYPE (index_expr);
205138fd1498Szrj tree elt;
205238fd1498Szrj basic_block bb = gimple_bb (stmt);
205338fd1498Szrj
205438fd1498Szrj hash_map<tree, tree> phi_mapping;
205538fd1498Szrj auto_vec<basic_block> case_bbs;
205638fd1498Szrj
205738fd1498Szrj /* A list of case labels; it is first built as a list and it may then
205838fd1498Szrj be rearranged into a nearly balanced binary tree. */
205938fd1498Szrj case_node *case_list = 0;
206038fd1498Szrj
206138fd1498Szrj /* A pool for case nodes. */
206238fd1498Szrj object_allocator<case_node> case_node_pool ("struct case_node pool");
206338fd1498Szrj
206438fd1498Szrj /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
206538fd1498Szrj expressions being INTEGER_CST. */
206638fd1498Szrj gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
206738fd1498Szrj
206838fd1498Szrj if (ncases == 1)
206938fd1498Szrj return false;
207038fd1498Szrj
207138fd1498Szrj /* Find the default case target label. */
207238fd1498Szrj tree default_label = CASE_LABEL (gimple_switch_default_label (stmt));
207338fd1498Szrj default_bb = label_to_block_fn (cfun, default_label);
207438fd1498Szrj edge default_edge = find_edge (bb, default_bb);
207538fd1498Szrj profile_probability default_prob = default_edge->probability;
207638fd1498Szrj case_bbs.safe_push (default_bb);
207738fd1498Szrj
207838fd1498Szrj /* Get upper and lower bounds of case values. */
207938fd1498Szrj elt = gimple_switch_label (stmt, 1);
208038fd1498Szrj minval = fold_convert (index_type, CASE_LOW (elt));
208138fd1498Szrj elt = gimple_switch_label (stmt, ncases - 1);
208238fd1498Szrj if (CASE_HIGH (elt))
208338fd1498Szrj maxval = fold_convert (index_type, CASE_HIGH (elt));
208438fd1498Szrj else
208538fd1498Szrj maxval = fold_convert (index_type, CASE_LOW (elt));
208638fd1498Szrj
208738fd1498Szrj /* Compute span of values. */
208838fd1498Szrj range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
208938fd1498Szrj
209038fd1498Szrj /* Listify the labels queue and gather some numbers to decide
209138fd1498Szrj how to expand this switch. */
209238fd1498Szrj uniq = 0;
209338fd1498Szrj count = 0;
209438fd1498Szrj hash_set<tree> seen_labels;
209538fd1498Szrj compute_cases_per_edge (stmt);
209638fd1498Szrj
209738fd1498Szrj for (i = ncases - 1; i >= 1; --i)
209838fd1498Szrj {
209938fd1498Szrj elt = gimple_switch_label (stmt, i);
210038fd1498Szrj tree low = CASE_LOW (elt);
210138fd1498Szrj gcc_assert (low);
210238fd1498Szrj tree high = CASE_HIGH (elt);
210338fd1498Szrj gcc_assert (!high || tree_int_cst_lt (low, high));
210438fd1498Szrj tree lab = CASE_LABEL (elt);
210538fd1498Szrj
210638fd1498Szrj /* Count the elements.
210738fd1498Szrj A range counts double, since it requires two compares. */
210838fd1498Szrj count++;
210938fd1498Szrj if (high)
211038fd1498Szrj count++;
211138fd1498Szrj
211238fd1498Szrj /* If we have not seen this label yet, then increase the
211338fd1498Szrj number of unique case node targets seen. */
211438fd1498Szrj if (!seen_labels.add (lab))
211538fd1498Szrj uniq++;
211638fd1498Szrj
211738fd1498Szrj /* The bounds on the case range, LOW and HIGH, have to be converted
211838fd1498Szrj to case's index type TYPE. Note that the original type of the
211938fd1498Szrj case index in the source code is usually "lost" during
212038fd1498Szrj gimplification due to type promotion, but the case labels retain the
212138fd1498Szrj original type. Make sure to drop overflow flags. */
212238fd1498Szrj low = fold_convert (index_type, low);
212338fd1498Szrj if (TREE_OVERFLOW (low))
212438fd1498Szrj low = wide_int_to_tree (index_type, wi::to_wide (low));
212538fd1498Szrj
212638fd1498Szrj /* The canonical from of a case label in GIMPLE is that a simple case
212738fd1498Szrj has an empty CASE_HIGH. For the casesi and tablejump expanders,
212838fd1498Szrj the back ends want simple cases to have high == low. */
212938fd1498Szrj if (!high)
213038fd1498Szrj high = low;
213138fd1498Szrj high = fold_convert (index_type, high);
213238fd1498Szrj if (TREE_OVERFLOW (high))
213338fd1498Szrj high = wide_int_to_tree (index_type, wi::to_wide (high));
213438fd1498Szrj
213538fd1498Szrj basic_block case_bb = label_to_block_fn (cfun, lab);
213638fd1498Szrj edge case_edge = find_edge (bb, case_bb);
213738fd1498Szrj case_list = add_case_node (
213838fd1498Szrj case_list, low, high, case_bb, lab,
213938fd1498Szrj case_edge->probability.apply_scale (1, (intptr_t) (case_edge->aux)),
214038fd1498Szrj case_node_pool);
214138fd1498Szrj
214238fd1498Szrj case_bbs.safe_push (case_bb);
214338fd1498Szrj }
214438fd1498Szrj reset_out_edges_aux (bb);
214538fd1498Szrj record_phi_operand_mapping (case_bbs, bb, &phi_mapping);
214638fd1498Szrj
214738fd1498Szrj /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
214838fd1498Szrj destination, such as one with a default case only.
214938fd1498Szrj It also removes cases that are out of range for the switch
215038fd1498Szrj type, so we should never get a zero here. */
215138fd1498Szrj gcc_assert (count > 0);
215238fd1498Szrj
215338fd1498Szrj /* Decide how to expand this switch.
215438fd1498Szrj The two options at this point are a dispatch table (casesi or
215538fd1498Szrj tablejump) or a decision tree. */
215638fd1498Szrj
215738fd1498Szrj if (expand_switch_as_decision_tree_p (range, uniq, count))
215838fd1498Szrj {
215938fd1498Szrj emit_case_decision_tree (stmt, index_expr, index_type, case_list,
216038fd1498Szrj default_bb, default_label, default_prob,
216138fd1498Szrj &phi_mapping);
216238fd1498Szrj return true;
216338fd1498Szrj }
216438fd1498Szrj
216538fd1498Szrj return false;
216638fd1498Szrj }
216738fd1498Szrj
216838fd1498Szrj /* The main function of the pass scans statements for switches and invokes
216938fd1498Szrj process_switch on them. */
217038fd1498Szrj
217138fd1498Szrj namespace {
217238fd1498Szrj
217338fd1498Szrj const pass_data pass_data_lower_switch =
217438fd1498Szrj {
217538fd1498Szrj GIMPLE_PASS, /* type */
217638fd1498Szrj "switchlower", /* name */
217738fd1498Szrj OPTGROUP_NONE, /* optinfo_flags */
217838fd1498Szrj TV_TREE_SWITCH_LOWERING, /* tv_id */
217938fd1498Szrj ( PROP_cfg | PROP_ssa ), /* properties_required */
218038fd1498Szrj 0, /* properties_provided */
218138fd1498Szrj 0, /* properties_destroyed */
218238fd1498Szrj 0, /* todo_flags_start */
218338fd1498Szrj TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */
218438fd1498Szrj };
218538fd1498Szrj
218638fd1498Szrj class pass_lower_switch : public gimple_opt_pass
218738fd1498Szrj {
218838fd1498Szrj public:
pass_lower_switch(gcc::context * ctxt)218938fd1498Szrj pass_lower_switch (gcc::context *ctxt)
219038fd1498Szrj : gimple_opt_pass (pass_data_lower_switch, ctxt)
219138fd1498Szrj {}
219238fd1498Szrj
219338fd1498Szrj /* opt_pass methods: */
gate(function *)219438fd1498Szrj virtual bool gate (function *) { return true; }
219538fd1498Szrj virtual unsigned int execute (function *);
219638fd1498Szrj
219738fd1498Szrj }; // class pass_lower_switch
219838fd1498Szrj
219938fd1498Szrj unsigned int
execute(function * fun)220038fd1498Szrj pass_lower_switch::execute (function *fun)
220138fd1498Szrj {
220238fd1498Szrj basic_block bb;
220338fd1498Szrj bool expanded = false;
220438fd1498Szrj
220538fd1498Szrj FOR_EACH_BB_FN (bb, fun)
220638fd1498Szrj {
220738fd1498Szrj gimple *stmt = last_stmt (bb);
220838fd1498Szrj if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
220938fd1498Szrj {
221038fd1498Szrj if (dump_file)
221138fd1498Szrj {
221238fd1498Szrj expanded_location loc = expand_location (gimple_location (stmt));
221338fd1498Szrj
221438fd1498Szrj fprintf (dump_file, "beginning to process the following "
221538fd1498Szrj "SWITCH statement (%s:%d) : ------- \n",
221638fd1498Szrj loc.file, loc.line);
221738fd1498Szrj print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
221838fd1498Szrj putc ('\n', dump_file);
221938fd1498Szrj }
222038fd1498Szrj
222138fd1498Szrj expanded |= try_switch_expansion (as_a<gswitch *> (stmt));
222238fd1498Szrj }
222338fd1498Szrj }
222438fd1498Szrj
222538fd1498Szrj if (expanded)
222638fd1498Szrj {
222738fd1498Szrj free_dominance_info (CDI_DOMINATORS);
222838fd1498Szrj free_dominance_info (CDI_POST_DOMINATORS);
222938fd1498Szrj mark_virtual_operands_for_renaming (cfun);
223038fd1498Szrj }
223138fd1498Szrj
223238fd1498Szrj return 0;
223338fd1498Szrj }
223438fd1498Szrj
223538fd1498Szrj } // anon namespace
223638fd1498Szrj
223738fd1498Szrj gimple_opt_pass *
make_pass_lower_switch(gcc::context * ctxt)223838fd1498Szrj make_pass_lower_switch (gcc::context *ctxt)
223938fd1498Szrj {
224038fd1498Szrj return new pass_lower_switch (ctxt);
224138fd1498Szrj }
224238fd1498Szrj
224338fd1498Szrj /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE.
224438fd1498Szrj PROB is the probability of jumping to LABEL. */
224538fd1498Szrj static basic_block
do_jump_if_equal(basic_block bb,tree op0,tree op1,basic_block label_bb,profile_probability prob,hash_map<tree,tree> * phi_mapping,location_t loc)224638fd1498Szrj do_jump_if_equal (basic_block bb, tree op0, tree op1, basic_block label_bb,
2247*58e805e6Szrj profile_probability prob, hash_map<tree, tree> *phi_mapping,
2248*58e805e6Szrj location_t loc)
224938fd1498Szrj {
225038fd1498Szrj gcond *cond = gimple_build_cond (EQ_EXPR, op0, op1, NULL_TREE, NULL_TREE);
2251*58e805e6Szrj gimple_set_location (cond, loc);
225238fd1498Szrj gimple_stmt_iterator gsi = gsi_last_bb (bb);
225338fd1498Szrj gsi_insert_before (&gsi, cond, GSI_SAME_STMT);
225438fd1498Szrj
225538fd1498Szrj gcc_assert (single_succ_p (bb));
225638fd1498Szrj
225738fd1498Szrj /* Make a new basic block where false branch will take place. */
225838fd1498Szrj edge false_edge = split_block (bb, cond);
225938fd1498Szrj false_edge->flags = EDGE_FALSE_VALUE;
226038fd1498Szrj false_edge->probability = prob.invert ();
226138fd1498Szrj
226238fd1498Szrj edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
226338fd1498Szrj fix_phi_operands_for_edge (true_edge, phi_mapping);
226438fd1498Szrj true_edge->probability = prob;
226538fd1498Szrj
226638fd1498Szrj return false_edge->dest;
226738fd1498Szrj }
226838fd1498Szrj
226938fd1498Szrj /* Generate code to compare X with Y so that the condition codes are
227038fd1498Szrj set and to jump to LABEL if the condition is true. If X is a
227138fd1498Szrj constant and Y is not a constant, then the comparison is swapped to
227238fd1498Szrj ensure that the comparison RTL has the canonical form.
227338fd1498Szrj
227438fd1498Szrj UNSIGNEDP nonzero says that X and Y are unsigned; this matters if they
227538fd1498Szrj need to be widened. UNSIGNEDP is also used to select the proper
227638fd1498Szrj branch condition code.
227738fd1498Szrj
227838fd1498Szrj If X and Y have mode BLKmode, then SIZE specifies the size of both X and Y.
227938fd1498Szrj
228038fd1498Szrj MODE is the mode of the inputs (in case they are const_int).
228138fd1498Szrj
228238fd1498Szrj COMPARISON is the rtl operator to compare with (EQ, NE, GT, etc.).
228338fd1498Szrj It will be potentially converted into an unsigned variant based on
228438fd1498Szrj UNSIGNEDP to select a proper jump instruction.
228538fd1498Szrj
228638fd1498Szrj PROB is the probability of jumping to LABEL. */
228738fd1498Szrj
228838fd1498Szrj static basic_block
emit_cmp_and_jump_insns(basic_block bb,tree op0,tree op1,tree_code comparison,basic_block label_bb,profile_probability prob,hash_map<tree,tree> * phi_mapping,location_t loc)228938fd1498Szrj emit_cmp_and_jump_insns (basic_block bb, tree op0, tree op1,
229038fd1498Szrj tree_code comparison, basic_block label_bb,
229138fd1498Szrj profile_probability prob,
2292*58e805e6Szrj hash_map<tree, tree> *phi_mapping,
2293*58e805e6Szrj location_t loc)
229438fd1498Szrj {
229538fd1498Szrj gcond *cond = gimple_build_cond (comparison, op0, op1, NULL_TREE, NULL_TREE);
2296*58e805e6Szrj gimple_set_location (cond, loc);
229738fd1498Szrj gimple_stmt_iterator gsi = gsi_last_bb (bb);
229838fd1498Szrj gsi_insert_after (&gsi, cond, GSI_NEW_STMT);
229938fd1498Szrj
230038fd1498Szrj gcc_assert (single_succ_p (bb));
230138fd1498Szrj
230238fd1498Szrj /* Make a new basic block where false branch will take place. */
230338fd1498Szrj edge false_edge = split_block (bb, cond);
230438fd1498Szrj false_edge->flags = EDGE_FALSE_VALUE;
230538fd1498Szrj false_edge->probability = prob.invert ();
230638fd1498Szrj
230738fd1498Szrj edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
230838fd1498Szrj fix_phi_operands_for_edge (true_edge, phi_mapping);
230938fd1498Szrj true_edge->probability = prob;
231038fd1498Szrj
231138fd1498Szrj return false_edge->dest;
231238fd1498Szrj }
231338fd1498Szrj
231438fd1498Szrj /* Computes the conditional probability of jumping to a target if the branch
231538fd1498Szrj instruction is executed.
231638fd1498Szrj TARGET_PROB is the estimated probability of jumping to a target relative
231738fd1498Szrj to some basic block BB.
231838fd1498Szrj BASE_PROB is the probability of reaching the branch instruction relative
231938fd1498Szrj to the same basic block BB. */
232038fd1498Szrj
232138fd1498Szrj static inline profile_probability
conditional_probability(profile_probability target_prob,profile_probability base_prob)232238fd1498Szrj conditional_probability (profile_probability target_prob,
232338fd1498Szrj profile_probability base_prob)
232438fd1498Szrj {
232538fd1498Szrj return target_prob / base_prob;
232638fd1498Szrj }
232738fd1498Szrj
232838fd1498Szrj /* Emit step-by-step code to select a case for the value of INDEX.
232938fd1498Szrj The thus generated decision tree follows the form of the
233038fd1498Szrj case-node binary tree NODE, whose nodes represent test conditions.
233138fd1498Szrj INDEX_TYPE is the type of the index of the switch.
233238fd1498Szrj
233338fd1498Szrj Care is taken to prune redundant tests from the decision tree
233438fd1498Szrj by detecting any boundary conditions already checked by
233538fd1498Szrj emitted rtx. (See node_has_high_bound, node_has_low_bound
233638fd1498Szrj and node_is_bounded, above.)
233738fd1498Szrj
233838fd1498Szrj Where the test conditions can be shown to be redundant we emit
233938fd1498Szrj an unconditional jump to the target code. As a further
234038fd1498Szrj optimization, the subordinates of a tree node are examined to
234138fd1498Szrj check for bounded nodes. In this case conditional and/or
234238fd1498Szrj unconditional jumps as a result of the boundary check for the
234338fd1498Szrj current node are arranged to target the subordinates associated
234438fd1498Szrj code for out of bound conditions on the current node.
234538fd1498Szrj
234638fd1498Szrj We can assume that when control reaches the code generated here,
234738fd1498Szrj the index value has already been compared with the parents
234838fd1498Szrj of this node, and determined to be on the same side of each parent
234938fd1498Szrj as this node is. Thus, if this node tests for the value 51,
235038fd1498Szrj and a parent tested for 52, we don't need to consider
235138fd1498Szrj the possibility of a value greater than 51. If another parent
235238fd1498Szrj tests for the value 50, then this node need not test anything. */
235338fd1498Szrj
235438fd1498Szrj static basic_block
emit_case_nodes(basic_block bb,tree index,case_node_ptr node,basic_block default_bb,tree default_label,profile_probability default_prob,tree index_type,hash_map<tree,tree> * phi_mapping,location_t loc)235538fd1498Szrj emit_case_nodes (basic_block bb, tree index, case_node_ptr node,
235638fd1498Szrj basic_block default_bb, tree default_label,
235738fd1498Szrj profile_probability default_prob, tree index_type,
2358*58e805e6Szrj hash_map<tree, tree> *phi_mapping,
2359*58e805e6Szrj location_t loc)
236038fd1498Szrj {
236138fd1498Szrj /* If INDEX has an unsigned type, we must make unsigned branches. */
236238fd1498Szrj profile_probability probability;
236338fd1498Szrj profile_probability prob = node->prob, subtree_prob = node->subtree_prob;
236438fd1498Szrj
236538fd1498Szrj /* See if our parents have already tested everything for us.
236638fd1498Szrj If they have, emit an unconditional jump for this node. */
236738fd1498Szrj if (node_is_bounded (node, index_type))
236838fd1498Szrj {
236938fd1498Szrj emit_jump (bb, node->case_bb, phi_mapping);
237038fd1498Szrj return NULL;
237138fd1498Szrj }
237238fd1498Szrj
237338fd1498Szrj else if (tree_int_cst_equal (node->low, node->high))
237438fd1498Szrj {
237538fd1498Szrj probability = conditional_probability (prob, subtree_prob + default_prob);
237638fd1498Szrj /* Node is single valued. First see if the index expression matches
237738fd1498Szrj this node and then check our children, if any. */
237838fd1498Szrj bb = do_jump_if_equal (bb, index, node->low, node->case_bb, probability,
2379*58e805e6Szrj phi_mapping, loc);
238038fd1498Szrj /* Since this case is taken at this point, reduce its weight from
238138fd1498Szrj subtree_weight. */
238238fd1498Szrj subtree_prob -= prob;
238338fd1498Szrj if (node->right != 0 && node->left != 0)
238438fd1498Szrj {
238538fd1498Szrj /* This node has children on both sides.
238638fd1498Szrj Dispatch to one side or the other
238738fd1498Szrj by comparing the index value with this node's value.
238838fd1498Szrj If one subtree is bounded, check that one first,
238938fd1498Szrj so we can avoid real branches in the tree. */
239038fd1498Szrj
239138fd1498Szrj if (node_is_bounded (node->right, index_type))
239238fd1498Szrj {
239338fd1498Szrj probability
239438fd1498Szrj = conditional_probability (node->right->prob,
239538fd1498Szrj subtree_prob + default_prob);
239638fd1498Szrj bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
239738fd1498Szrj node->right->case_bb, probability,
2398*58e805e6Szrj phi_mapping, loc);
239938fd1498Szrj bb = emit_case_nodes (bb, index, node->left, default_bb,
240038fd1498Szrj default_label, default_prob, index_type,
2401*58e805e6Szrj phi_mapping, loc);
240238fd1498Szrj }
240338fd1498Szrj
240438fd1498Szrj else if (node_is_bounded (node->left, index_type))
240538fd1498Szrj {
240638fd1498Szrj probability
240738fd1498Szrj = conditional_probability (node->left->prob,
240838fd1498Szrj subtree_prob + default_prob);
240938fd1498Szrj bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR,
241038fd1498Szrj node->left->case_bb, probability,
2411*58e805e6Szrj phi_mapping, loc);
241238fd1498Szrj bb = emit_case_nodes (bb, index, node->right, default_bb,
241338fd1498Szrj default_label, default_prob, index_type,
2414*58e805e6Szrj phi_mapping, loc);
241538fd1498Szrj }
241638fd1498Szrj
241738fd1498Szrj /* If both children are single-valued cases with no
241838fd1498Szrj children, finish up all the work. This way, we can save
241938fd1498Szrj one ordered comparison. */
242038fd1498Szrj else if (tree_int_cst_equal (node->right->low, node->right->high)
242138fd1498Szrj && node->right->left == 0 && node->right->right == 0
242238fd1498Szrj && tree_int_cst_equal (node->left->low, node->left->high)
242338fd1498Szrj && node->left->left == 0 && node->left->right == 0)
242438fd1498Szrj {
242538fd1498Szrj /* Neither node is bounded. First distinguish the two sides;
242638fd1498Szrj then emit the code for one side at a time. */
242738fd1498Szrj
242838fd1498Szrj /* See if the value matches what the right hand side
242938fd1498Szrj wants. */
243038fd1498Szrj probability
243138fd1498Szrj = conditional_probability (node->right->prob,
243238fd1498Szrj subtree_prob + default_prob);
243338fd1498Szrj bb = do_jump_if_equal (bb, index, node->right->low,
243438fd1498Szrj node->right->case_bb, probability,
2435*58e805e6Szrj phi_mapping, loc);
243638fd1498Szrj
243738fd1498Szrj /* See if the value matches what the left hand side
243838fd1498Szrj wants. */
243938fd1498Szrj probability
244038fd1498Szrj = conditional_probability (node->left->prob,
244138fd1498Szrj subtree_prob + default_prob);
244238fd1498Szrj bb = do_jump_if_equal (bb, index, node->left->low,
244338fd1498Szrj node->left->case_bb, probability,
2444*58e805e6Szrj phi_mapping, loc);
244538fd1498Szrj }
244638fd1498Szrj
244738fd1498Szrj else
244838fd1498Szrj {
244938fd1498Szrj /* Neither node is bounded. First distinguish the two sides;
245038fd1498Szrj then emit the code for one side at a time. */
245138fd1498Szrj
245238fd1498Szrj basic_block test_bb = split_edge (single_succ_edge (bb));
245338fd1498Szrj redirect_edge_succ (single_pred_edge (test_bb),
245438fd1498Szrj single_succ_edge (bb)->dest);
245538fd1498Szrj
245638fd1498Szrj /* The default label could be reached either through the right
245738fd1498Szrj subtree or the left subtree. Divide the probability
245838fd1498Szrj equally. */
245938fd1498Szrj probability
246038fd1498Szrj = conditional_probability (node->right->subtree_prob
246138fd1498Szrj + default_prob.apply_scale (1, 2),
246238fd1498Szrj subtree_prob + default_prob);
246338fd1498Szrj /* See if the value is on the right. */
246438fd1498Szrj bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
2465*58e805e6Szrj test_bb, probability, phi_mapping,
2466*58e805e6Szrj loc);
246738fd1498Szrj default_prob = default_prob.apply_scale (1, 2);
246838fd1498Szrj
246938fd1498Szrj /* Value must be on the left.
247038fd1498Szrj Handle the left-hand subtree. */
247138fd1498Szrj bb = emit_case_nodes (bb, index, node->left, default_bb,
247238fd1498Szrj default_label, default_prob, index_type,
2473*58e805e6Szrj phi_mapping, loc);
247438fd1498Szrj /* If left-hand subtree does nothing,
247538fd1498Szrj go to default. */
247638fd1498Szrj
247738fd1498Szrj if (bb && default_bb)
247838fd1498Szrj emit_jump (bb, default_bb, phi_mapping);
247938fd1498Szrj
248038fd1498Szrj /* Code branches here for the right-hand subtree. */
248138fd1498Szrj bb = emit_case_nodes (test_bb, index, node->right, default_bb,
248238fd1498Szrj default_label, default_prob, index_type,
2483*58e805e6Szrj phi_mapping, loc);
248438fd1498Szrj }
248538fd1498Szrj }
248638fd1498Szrj else if (node->right != 0 && node->left == 0)
248738fd1498Szrj {
248838fd1498Szrj /* Here we have a right child but no left so we issue a conditional
248938fd1498Szrj branch to default and process the right child.
249038fd1498Szrj
249138fd1498Szrj Omit the conditional branch to default if the right child
249238fd1498Szrj does not have any children and is single valued; it would
249338fd1498Szrj cost too much space to save so little time. */
249438fd1498Szrj
249538fd1498Szrj if (node->right->right || node->right->left
249638fd1498Szrj || !tree_int_cst_equal (node->right->low, node->right->high))
249738fd1498Szrj {
249838fd1498Szrj if (!node_has_low_bound (node, index_type))
249938fd1498Szrj {
250038fd1498Szrj probability
250138fd1498Szrj = conditional_probability (default_prob.apply_scale (1, 2),
250238fd1498Szrj subtree_prob + default_prob);
250338fd1498Szrj bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR,
250438fd1498Szrj default_bb, probability,
2505*58e805e6Szrj phi_mapping, loc);
250638fd1498Szrj default_prob = default_prob.apply_scale (1, 2);
250738fd1498Szrj }
250838fd1498Szrj
250938fd1498Szrj bb = emit_case_nodes (bb, index, node->right, default_bb,
251038fd1498Szrj default_label, default_prob, index_type,
2511*58e805e6Szrj phi_mapping, loc);
251238fd1498Szrj }
251338fd1498Szrj else
251438fd1498Szrj {
251538fd1498Szrj probability
251638fd1498Szrj = conditional_probability (node->right->subtree_prob,
251738fd1498Szrj subtree_prob + default_prob);
251838fd1498Szrj /* We cannot process node->right normally
251938fd1498Szrj since we haven't ruled out the numbers less than
252038fd1498Szrj this node's value. So handle node->right explicitly. */
252138fd1498Szrj bb = do_jump_if_equal (bb, index, node->right->low,
252238fd1498Szrj node->right->case_bb, probability,
2523*58e805e6Szrj phi_mapping, loc);
252438fd1498Szrj }
252538fd1498Szrj }
252638fd1498Szrj
252738fd1498Szrj else if (node->right == 0 && node->left != 0)
252838fd1498Szrj {
252938fd1498Szrj /* Just one subtree, on the left. */
253038fd1498Szrj if (node->left->left || node->left->right
253138fd1498Szrj || !tree_int_cst_equal (node->left->low, node->left->high))
253238fd1498Szrj {
253338fd1498Szrj if (!node_has_high_bound (node, index_type))
253438fd1498Szrj {
253538fd1498Szrj probability
253638fd1498Szrj = conditional_probability (default_prob.apply_scale (1, 2),
253738fd1498Szrj subtree_prob + default_prob);
253838fd1498Szrj bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
253938fd1498Szrj default_bb, probability,
2540*58e805e6Szrj phi_mapping, loc);
254138fd1498Szrj default_prob = default_prob.apply_scale (1, 2);
254238fd1498Szrj }
254338fd1498Szrj
254438fd1498Szrj bb = emit_case_nodes (bb, index, node->left, default_bb,
254538fd1498Szrj default_label, default_prob, index_type,
2546*58e805e6Szrj phi_mapping, loc);
254738fd1498Szrj }
254838fd1498Szrj else
254938fd1498Szrj {
255038fd1498Szrj probability
255138fd1498Szrj = conditional_probability (node->left->subtree_prob,
255238fd1498Szrj subtree_prob + default_prob);
255338fd1498Szrj /* We cannot process node->left normally
255438fd1498Szrj since we haven't ruled out the numbers less than
255538fd1498Szrj this node's value. So handle node->left explicitly. */
255638fd1498Szrj do_jump_if_equal (bb, index, node->left->low, node->left->case_bb,
2557*58e805e6Szrj probability, phi_mapping, loc);
255838fd1498Szrj }
255938fd1498Szrj }
256038fd1498Szrj }
256138fd1498Szrj else
256238fd1498Szrj {
256338fd1498Szrj /* Node is a range. These cases are very similar to those for a single
256438fd1498Szrj value, except that we do not start by testing whether this node
256538fd1498Szrj is the one to branch to. */
256638fd1498Szrj
256738fd1498Szrj if (node->right != 0 && node->left != 0)
256838fd1498Szrj {
256938fd1498Szrj /* Node has subtrees on both sides.
257038fd1498Szrj If the right-hand subtree is bounded,
257138fd1498Szrj test for it first, since we can go straight there.
257238fd1498Szrj Otherwise, we need to make a branch in the control structure,
257338fd1498Szrj then handle the two subtrees. */
257438fd1498Szrj basic_block test_bb = NULL;
257538fd1498Szrj
257638fd1498Szrj if (node_is_bounded (node->right, index_type))
257738fd1498Szrj {
257838fd1498Szrj /* Right hand node is fully bounded so we can eliminate any
257938fd1498Szrj testing and branch directly to the target code. */
258038fd1498Szrj probability
258138fd1498Szrj = conditional_probability (node->right->subtree_prob,
258238fd1498Szrj subtree_prob + default_prob);
258338fd1498Szrj bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
258438fd1498Szrj node->right->case_bb, probability,
2585*58e805e6Szrj phi_mapping, loc);
258638fd1498Szrj }
258738fd1498Szrj else
258838fd1498Szrj {
258938fd1498Szrj /* Right hand node requires testing.
259038fd1498Szrj Branch to a label where we will handle it later. */
259138fd1498Szrj
259238fd1498Szrj test_bb = split_edge (single_succ_edge (bb));
259338fd1498Szrj redirect_edge_succ (single_pred_edge (test_bb),
259438fd1498Szrj single_succ_edge (bb)->dest);
259538fd1498Szrj
259638fd1498Szrj probability
259738fd1498Szrj = conditional_probability (node->right->subtree_prob
259838fd1498Szrj + default_prob.apply_scale (1, 2),
259938fd1498Szrj subtree_prob + default_prob);
260038fd1498Szrj bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
2601*58e805e6Szrj test_bb, probability, phi_mapping,
2602*58e805e6Szrj loc);
260338fd1498Szrj default_prob = default_prob.apply_scale (1, 2);
260438fd1498Szrj }
260538fd1498Szrj
260638fd1498Szrj /* Value belongs to this node or to the left-hand subtree. */
260738fd1498Szrj
260838fd1498Szrj probability
260938fd1498Szrj = conditional_probability (prob, subtree_prob + default_prob);
261038fd1498Szrj bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR,
261138fd1498Szrj node->case_bb, probability,
2612*58e805e6Szrj phi_mapping, loc);
261338fd1498Szrj
261438fd1498Szrj /* Handle the left-hand subtree. */
261538fd1498Szrj bb = emit_case_nodes (bb, index, node->left, default_bb,
261638fd1498Szrj default_label, default_prob, index_type,
2617*58e805e6Szrj phi_mapping, loc);
261838fd1498Szrj
261938fd1498Szrj /* If right node had to be handled later, do that now. */
262038fd1498Szrj if (test_bb)
262138fd1498Szrj {
262238fd1498Szrj /* If the left-hand subtree fell through,
262338fd1498Szrj don't let it fall into the right-hand subtree. */
262438fd1498Szrj if (bb && default_bb)
262538fd1498Szrj emit_jump (bb, default_bb, phi_mapping);
262638fd1498Szrj
262738fd1498Szrj bb = emit_case_nodes (test_bb, index, node->right, default_bb,
262838fd1498Szrj default_label, default_prob, index_type,
2629*58e805e6Szrj phi_mapping, loc);
263038fd1498Szrj }
263138fd1498Szrj }
263238fd1498Szrj
263338fd1498Szrj else if (node->right != 0 && node->left == 0)
263438fd1498Szrj {
263538fd1498Szrj /* Deal with values to the left of this node,
263638fd1498Szrj if they are possible. */
263738fd1498Szrj if (!node_has_low_bound (node, index_type))
263838fd1498Szrj {
263938fd1498Szrj probability
264038fd1498Szrj = conditional_probability (default_prob.apply_scale (1, 2),
264138fd1498Szrj subtree_prob + default_prob);
264238fd1498Szrj bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR,
264338fd1498Szrj default_bb, probability,
2644*58e805e6Szrj phi_mapping, loc);
264538fd1498Szrj default_prob = default_prob.apply_scale (1, 2);
264638fd1498Szrj }
264738fd1498Szrj
264838fd1498Szrj /* Value belongs to this node or to the right-hand subtree. */
264938fd1498Szrj
265038fd1498Szrj probability
265138fd1498Szrj = conditional_probability (prob, subtree_prob + default_prob);
265238fd1498Szrj bb = emit_cmp_and_jump_insns (bb, index, node->high, LE_EXPR,
265338fd1498Szrj node->case_bb, probability,
2654*58e805e6Szrj phi_mapping, loc);
265538fd1498Szrj
265638fd1498Szrj bb = emit_case_nodes (bb, index, node->right, default_bb,
265738fd1498Szrj default_label, default_prob, index_type,
2658*58e805e6Szrj phi_mapping, loc);
265938fd1498Szrj }
266038fd1498Szrj
266138fd1498Szrj else if (node->right == 0 && node->left != 0)
266238fd1498Szrj {
266338fd1498Szrj /* Deal with values to the right of this node,
266438fd1498Szrj if they are possible. */
266538fd1498Szrj if (!node_has_high_bound (node, index_type))
266638fd1498Szrj {
266738fd1498Szrj probability
266838fd1498Szrj = conditional_probability (default_prob.apply_scale (1, 2),
266938fd1498Szrj subtree_prob + default_prob);
267038fd1498Szrj bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
267138fd1498Szrj default_bb, probability,
2672*58e805e6Szrj phi_mapping, loc);
267338fd1498Szrj default_prob = default_prob.apply_scale (1, 2);
267438fd1498Szrj }
267538fd1498Szrj
267638fd1498Szrj /* Value belongs to this node or to the left-hand subtree. */
267738fd1498Szrj
267838fd1498Szrj probability
267938fd1498Szrj = conditional_probability (prob, subtree_prob + default_prob);
268038fd1498Szrj bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR,
268138fd1498Szrj node->case_bb, probability,
2682*58e805e6Szrj phi_mapping, loc);
268338fd1498Szrj
268438fd1498Szrj bb = emit_case_nodes (bb, index, node->left, default_bb,
268538fd1498Szrj default_label, default_prob, index_type,
2686*58e805e6Szrj phi_mapping, loc);
268738fd1498Szrj }
268838fd1498Szrj
268938fd1498Szrj else
269038fd1498Szrj {
269138fd1498Szrj /* Node has no children so we check low and high bounds to remove
269238fd1498Szrj redundant tests. Only one of the bounds can exist,
269338fd1498Szrj since otherwise this node is bounded--a case tested already. */
269438fd1498Szrj bool high_bound = node_has_high_bound (node, index_type);
269538fd1498Szrj bool low_bound = node_has_low_bound (node, index_type);
269638fd1498Szrj
269738fd1498Szrj if (!high_bound && low_bound)
269838fd1498Szrj {
269938fd1498Szrj probability
270038fd1498Szrj = conditional_probability (default_prob,
270138fd1498Szrj subtree_prob + default_prob);
270238fd1498Szrj bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
270338fd1498Szrj default_bb, probability,
2704*58e805e6Szrj phi_mapping, loc);
270538fd1498Szrj }
270638fd1498Szrj
270738fd1498Szrj else if (!low_bound && high_bound)
270838fd1498Szrj {
270938fd1498Szrj probability
271038fd1498Szrj = conditional_probability (default_prob,
271138fd1498Szrj subtree_prob + default_prob);
271238fd1498Szrj bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR,
271338fd1498Szrj default_bb, probability,
2714*58e805e6Szrj phi_mapping, loc);
271538fd1498Szrj }
271638fd1498Szrj else if (!low_bound && !high_bound)
271738fd1498Szrj {
271838fd1498Szrj tree lhs, rhs;
271938fd1498Szrj generate_range_test (bb, index, node->low, node->high,
272038fd1498Szrj &lhs, &rhs);
272138fd1498Szrj probability
272238fd1498Szrj = conditional_probability (default_prob,
272338fd1498Szrj subtree_prob + default_prob);
272438fd1498Szrj bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR,
272538fd1498Szrj default_bb, probability,
2726*58e805e6Szrj phi_mapping, loc);
272738fd1498Szrj }
272838fd1498Szrj
272938fd1498Szrj emit_jump (bb, node->case_bb, phi_mapping);
273038fd1498Szrj return NULL;
273138fd1498Szrj }
273238fd1498Szrj }
273338fd1498Szrj
273438fd1498Szrj return bb;
273538fd1498Szrj }
273638fd1498Szrj
273738fd1498Szrj /* Search the parent sections of the case node tree
273838fd1498Szrj to see if a test for the lower bound of NODE would be redundant.
273938fd1498Szrj INDEX_TYPE is the type of the index expression.
274038fd1498Szrj
274138fd1498Szrj The instructions to generate the case decision tree are
274238fd1498Szrj output in the same order as nodes are processed so it is
274338fd1498Szrj known that if a parent node checks the range of the current
274438fd1498Szrj node minus one that the current node is bounded at its lower
274538fd1498Szrj span. Thus the test would be redundant. */
274638fd1498Szrj
274738fd1498Szrj static bool
node_has_low_bound(case_node_ptr node,tree index_type)274838fd1498Szrj node_has_low_bound (case_node_ptr node, tree index_type)
274938fd1498Szrj {
275038fd1498Szrj tree low_minus_one;
275138fd1498Szrj case_node_ptr pnode;
275238fd1498Szrj
275338fd1498Szrj /* If the lower bound of this node is the lowest value in the index type,
275438fd1498Szrj we need not test it. */
275538fd1498Szrj
275638fd1498Szrj if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
275738fd1498Szrj return true;
275838fd1498Szrj
275938fd1498Szrj /* If this node has a left branch, the value at the left must be less
276038fd1498Szrj than that at this node, so it cannot be bounded at the bottom and
276138fd1498Szrj we need not bother testing any further. */
276238fd1498Szrj
276338fd1498Szrj if (node->left)
276438fd1498Szrj return false;
276538fd1498Szrj
276638fd1498Szrj low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low), node->low,
276738fd1498Szrj build_int_cst (TREE_TYPE (node->low), 1));
276838fd1498Szrj
276938fd1498Szrj /* If the subtraction above overflowed, we can't verify anything.
277038fd1498Szrj Otherwise, look for a parent that tests our value - 1. */
277138fd1498Szrj
277238fd1498Szrj if (!tree_int_cst_lt (low_minus_one, node->low))
277338fd1498Szrj return false;
277438fd1498Szrj
277538fd1498Szrj for (pnode = node->parent; pnode; pnode = pnode->parent)
277638fd1498Szrj if (tree_int_cst_equal (low_minus_one, pnode->high))
277738fd1498Szrj return true;
277838fd1498Szrj
277938fd1498Szrj return false;
278038fd1498Szrj }
278138fd1498Szrj
278238fd1498Szrj /* Search the parent sections of the case node tree
278338fd1498Szrj to see if a test for the upper bound of NODE would be redundant.
278438fd1498Szrj INDEX_TYPE is the type of the index expression.
278538fd1498Szrj
278638fd1498Szrj The instructions to generate the case decision tree are
278738fd1498Szrj output in the same order as nodes are processed so it is
278838fd1498Szrj known that if a parent node checks the range of the current
278938fd1498Szrj node plus one that the current node is bounded at its upper
279038fd1498Szrj span. Thus the test would be redundant. */
279138fd1498Szrj
279238fd1498Szrj static bool
node_has_high_bound(case_node_ptr node,tree index_type)279338fd1498Szrj node_has_high_bound (case_node_ptr node, tree index_type)
279438fd1498Szrj {
279538fd1498Szrj tree high_plus_one;
279638fd1498Szrj case_node_ptr pnode;
279738fd1498Szrj
279838fd1498Szrj /* If there is no upper bound, obviously no test is needed. */
279938fd1498Szrj
280038fd1498Szrj if (TYPE_MAX_VALUE (index_type) == NULL)
280138fd1498Szrj return true;
280238fd1498Szrj
280338fd1498Szrj /* If the upper bound of this node is the highest value in the type
280438fd1498Szrj of the index expression, we need not test against it. */
280538fd1498Szrj
280638fd1498Szrj if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
280738fd1498Szrj return true;
280838fd1498Szrj
280938fd1498Szrj /* If this node has a right branch, the value at the right must be greater
281038fd1498Szrj than that at this node, so it cannot be bounded at the top and
281138fd1498Szrj we need not bother testing any further. */
281238fd1498Szrj
281338fd1498Szrj if (node->right)
281438fd1498Szrj return false;
281538fd1498Szrj
281638fd1498Szrj high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high), node->high,
281738fd1498Szrj build_int_cst (TREE_TYPE (node->high), 1));
281838fd1498Szrj
281938fd1498Szrj /* If the addition above overflowed, we can't verify anything.
282038fd1498Szrj Otherwise, look for a parent that tests our value + 1. */
282138fd1498Szrj
282238fd1498Szrj if (!tree_int_cst_lt (node->high, high_plus_one))
282338fd1498Szrj return false;
282438fd1498Szrj
282538fd1498Szrj for (pnode = node->parent; pnode; pnode = pnode->parent)
282638fd1498Szrj if (tree_int_cst_equal (high_plus_one, pnode->low))
282738fd1498Szrj return true;
282838fd1498Szrj
282938fd1498Szrj return false;
283038fd1498Szrj }
283138fd1498Szrj
283238fd1498Szrj /* Search the parent sections of the
283338fd1498Szrj case node tree to see if both tests for the upper and lower
283438fd1498Szrj bounds of NODE would be redundant. */
283538fd1498Szrj
283638fd1498Szrj static bool
node_is_bounded(case_node_ptr node,tree index_type)283738fd1498Szrj node_is_bounded (case_node_ptr node, tree index_type)
283838fd1498Szrj {
283938fd1498Szrj return (node_has_low_bound (node, index_type)
284038fd1498Szrj && node_has_high_bound (node, index_type));
284138fd1498Szrj }
2842