1 /* Lower GIMPLE_SWITCH expressions to something more efficient than
3 Copyright (C) 2006-2013 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
22 /* This file handles the lowering of GIMPLE_SWITCH to an indexed
23 load, or a series of bit-test-and-branch expressions. */
27 #include "coretypes.h"
33 #include "basic-block.h"
36 #include "gimple-iterator.h"
37 #include "gimplify-me.h"
38 #include "gimple-ssa.h"
41 #include "tree-phinodes.h"
42 #include "tree-ssanames.h"
43 #include "tree-pass.h"
44 #include "gimple-pretty-print.h"
47 /* ??? For lang_hooks.types.type_for_mode, but is there a word_mode
48 type in the GIMPLE type system that is language-independent? */
49 #include "langhooks.h"
51 /* Need to include expr.h and optabs.h for lshift_cheap_p. */
55 /* Maximum number of case bit tests.
56 FIXME: This should be derived from PARAM_CASE_VALUES_THRESHOLD and
57 targetm.case_values_threshold(), or be its own param. */
58 #define MAX_CASE_BIT_TESTS 3
60 /* Split the basic block at the statement pointed to by GSIP, and insert
61 a branch to the target basic block of E_TRUE conditional on tree
64 It is assumed that there is already an edge from the to-be-split
65 basic block to E_TRUE->dest block. This edge is removed, and the
66 profile information on the edge is re-used for the new conditional
69 The CFG is updated. The dominator tree will not be valid after
70 this transformation, but the immediate dominators are updated if
71 UPDATE_DOMINATORS is true.
73 Returns the newly created basic block. */
76 hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
77 tree cond, edge e_true,
78 bool update_dominators)
83 basic_block new_bb, split_bb = gsi_bb (*gsip);
84 bool dominated_e_true = false;
86 gcc_assert (e_true->src == split_bb);
89 && get_immediate_dominator (CDI_DOMINATORS, e_true->dest) == split_bb)
90 dominated_e_true = true;
92 tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL,
93 /*before=*/true, GSI_SAME_STMT);
94 cond_stmt = gimple_build_cond_from_tree (tmp, NULL_TREE, NULL_TREE);
95 gsi_insert_before (gsip, cond_stmt, GSI_SAME_STMT);
97 e_false = split_block (split_bb, cond_stmt);
98 new_bb = e_false->dest;
99 redirect_edge_pred (e_true, split_bb);
101 e_true->flags &= ~EDGE_FALLTHRU;
102 e_true->flags |= EDGE_TRUE_VALUE;
104 e_false->flags &= ~EDGE_FALLTHRU;
105 e_false->flags |= EDGE_FALSE_VALUE;
106 e_false->probability = REG_BR_PROB_BASE - e_true->probability;
107 e_false->count = split_bb->count - e_true->count;
108 new_bb->count = e_false->count;
110 if (update_dominators)
112 if (dominated_e_true)
113 set_immediate_dominator (CDI_DOMINATORS, e_true->dest, split_bb);
114 set_immediate_dominator (CDI_DOMINATORS, e_false->dest, split_bb);
121 /* Determine whether "1 << x" is relatively cheap in word_mode. */
122 /* FIXME: This is the function that we need rtl.h and optabs.h for.
123 This function (and similar RTL-related cost code in e.g. IVOPTS) should
124 be moved to some kind of interface file for GIMPLE/RTL interactions. */
126 lshift_cheap_p (void)
128 /* FIXME: This should be made target dependent via this "this_target"
129 mechanism, similar to e.g. can_copy_init_p in gcse.c. */
130 static bool init[2] = {false, false};
131 static bool cheap[2] = {true, true};
134 /* If the targer has no lshift in word_mode, the operation will most
135 probably not be cheap. ??? Does GCC even work for such targets? */
136 if (optab_handler (ashl_optab, word_mode) == CODE_FOR_nothing)
139 speed_p = optimize_insn_for_speed_p ();
143 rtx reg = gen_raw_REG (word_mode, 10000);
144 int cost = set_src_cost (gen_rtx_ASHIFT (word_mode, const1_rtx, reg),
146 cheap[speed_p] = cost < COSTS_N_INSNS (MAX_CASE_BIT_TESTS);
147 init[speed_p] = true;
150 return cheap[speed_p];
153 /* Return true if a switch should be expanded as a bit test.
154 RANGE is the difference between highest and lowest case.
155 UNIQ is number of unique case node targets, not counting the default case.
156 COUNT is the number of comparisons needed, not counting the default case. */
159 expand_switch_using_bit_tests_p (tree range,
163 return (((uniq == 1 && count >= 3)
164 || (uniq == 2 && count >= 5)
165 || (uniq == 3 && count >= 6))
167 && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0
168 && compare_tree_int (range, 0) > 0);
171 /* Implement switch statements with bit tests
173 A GIMPLE switch statement can be expanded to a short sequence of bit-wise
174 comparisons. "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)"
175 where CST and MINVAL are integer constants. This is better than a series
176 of compare-and-banch insns in some cases, e.g. we can implement:
178 if ((x==4) || (x==6) || (x==9) || (x==11))
180 as a single bit test:
182 if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11)))
184 This transformation is only applied if the number of case targets is small,
185 if CST constains at least 3 bits, and "1 << x" is cheap. The bit tests are
186 performed in "word_mode".
188 The following example shows the code the transformation generates:
194 case '0': case '1': case '2': case '3': case '4':
195 case '5': case '6': case '7': case '8': case '9':
196 case 'A': case 'B': case 'C': case 'D': case 'E':
208 if (tmp1 > (70 - 48)) goto L2;
210 tmp3 = 0b11111100000001111111111;
211 if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2;
218 TODO: There are still some improvements to this transformation that could
221 * A narrower mode than word_mode could be used if that is cheaper, e.g.
222 for x86_64 where a narrower-mode shift may result in smaller code.
224 * The compounded constant could be shifted rather than the one. The
225 test would be either on the sign bit or on the least significant bit,
226 depending on the direction of the shift. On some machines, the test
227 for the branch would be free if the bit to test is already set by the
230 This transformation was contributed by Roger Sayle, see this e-mail:
231 http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html
234 /* A case_bit_test represents a set of case nodes that may be
235 selected from using a bit-wise comparison. HI and LO hold
236 the integer to be tested against, TARGET_EDGE contains the
237 edge to the basic block to jump to upon success and BITS
238 counts the number of case nodes handled by this test,
239 typically the number of bits set in HI:LO. The LABEL field
240 is used to quickly identify all cases in this set without
241 looking at label_to_block for every case label. */
252 /* Comparison function for qsort to order bit tests by decreasing
253 probability of execution. Our best guess comes from a measured
254 profile. If the profile counts are equal, break even on the
255 number of case nodes, i.e. the node with the most cases gets
258 TODO: Actually this currently runs before a profile is available.
259 Therefore the case-as-bit-tests transformation should be done
260 later in the pass pipeline, or something along the lines of
261 "Efficient and effective branch reordering using profile data"
262 (Yang et. al., 2002) should be implemented (although, how good
263 is a paper is called "Efficient and effective ..." when the
264 latter is implied by the former, but oh well...). */
267 case_bit_test_cmp (const void *p1, const void *p2)
269 const struct case_bit_test *const d1 = (const struct case_bit_test *) p1;
270 const struct case_bit_test *const d2 = (const struct case_bit_test *) p2;
272 if (d2->target_edge->count != d1->target_edge->count)
273 return d2->target_edge->count - d1->target_edge->count;
274 if (d2->bits != d1->bits)
275 return d2->bits - d1->bits;
277 /* Stabilize the sort. */
278 return LABEL_DECL_UID (d2->label) - LABEL_DECL_UID (d1->label);
281 /* Expand a switch statement by a short sequence of bit-wise
282 comparisons. "switch(x)" is effectively converted into
283 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
286 INDEX_EXPR is the value being switched on.
288 MINVAL is the lowest case value of in the case nodes,
289 and RANGE is highest value minus MINVAL. MINVAL and RANGE
290 are not guaranteed to be of the same type as INDEX_EXPR
291 (the gimplifier doesn't change the type of case label values,
292 and MINVAL and RANGE are derived from those values).
294 There *MUST* be MAX_CASE_BIT_TESTS or less unique case
298 emit_case_bit_tests (gimple swtch, tree index_expr,
299 tree minval, tree range)
301 struct case_bit_test test[MAX_CASE_BIT_TESTS];
302 unsigned int i, j, k;
305 basic_block switch_bb = gimple_bb (swtch);
306 basic_block default_bb, new_default_bb, new_bb;
308 bool update_dom = dom_info_available_p (CDI_DOMINATORS);
310 vec<basic_block> bbs_to_fix_dom = vNULL;
312 tree index_type = TREE_TYPE (index_expr);
313 tree unsigned_index_type = unsigned_type_for (index_type);
314 unsigned int branch_num = gimple_switch_num_labels (swtch);
316 gimple_stmt_iterator gsi;
320 tree word_type_node = lang_hooks.types.type_for_mode (word_mode, 1);
321 tree word_mode_zero = fold_convert (word_type_node, integer_zero_node);
322 tree word_mode_one = fold_convert (word_type_node, integer_one_node);
324 memset (&test, 0, sizeof (test));
326 /* Get the edge for the default case. */
327 tmp = gimple_switch_default_label (swtch);
328 default_bb = label_to_block (CASE_LABEL (tmp));
329 default_edge = find_edge (switch_bb, default_bb);
331 /* Go through all case labels, and collect the case labels, profile
332 counts, and other information we need to build the branch tests. */
334 for (i = 1; i < branch_num; i++)
337 tree cs = gimple_switch_label (swtch, i);
338 tree label = CASE_LABEL (cs);
339 edge e = find_edge (switch_bb, label_to_block (label));
340 for (k = 0; k < count; k++)
341 if (e == test[k].target_edge)
346 gcc_checking_assert (count < MAX_CASE_BIT_TESTS);
349 test[k].target_edge = e;
350 test[k].label = label;
357 lo = tree_low_cst (int_const_binop (MINUS_EXPR,
358 CASE_LOW (cs), minval),
360 if (CASE_HIGH (cs) == NULL_TREE)
363 hi = tree_low_cst (int_const_binop (MINUS_EXPR,
364 CASE_HIGH (cs), minval),
367 for (j = lo; j <= hi; j++)
368 if (j >= HOST_BITS_PER_WIDE_INT)
369 test[k].hi |= (HOST_WIDE_INT) 1 << (j - HOST_BITS_PER_INT);
371 test[k].lo |= (HOST_WIDE_INT) 1 << j;
374 qsort (test, count, sizeof (*test), case_bit_test_cmp);
376 /* We generate two jumps to the default case label.
377 Split the default edge, so that we don't have to do any PHI node
379 new_default_bb = split_edge (default_edge);
383 bbs_to_fix_dom.create (10);
384 bbs_to_fix_dom.quick_push (switch_bb);
385 bbs_to_fix_dom.quick_push (default_bb);
386 bbs_to_fix_dom.quick_push (new_default_bb);
389 /* Now build the test-and-branch code. */
391 gsi = gsi_last_bb (switch_bb);
393 /* idx = (unsigned)x - minval. */
394 idx = fold_convert (unsigned_index_type, index_expr);
395 idx = fold_build2 (MINUS_EXPR, unsigned_index_type, idx,
396 fold_convert (unsigned_index_type, minval));
397 idx = force_gimple_operand_gsi (&gsi, idx,
398 /*simple=*/true, NULL_TREE,
399 /*before=*/true, GSI_SAME_STMT);
401 /* if (idx > range) goto default */
402 range = force_gimple_operand_gsi (&gsi,
403 fold_convert (unsigned_index_type, range),
404 /*simple=*/true, NULL_TREE,
405 /*before=*/true, GSI_SAME_STMT);
406 tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range);
407 new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, default_edge, update_dom);
409 bbs_to_fix_dom.quick_push (new_bb);
410 gcc_assert (gimple_bb (swtch) == new_bb);
411 gsi = gsi_last_bb (new_bb);
413 /* Any blocks dominated by the GIMPLE_SWITCH, but that are not successors
414 of NEW_BB, are still immediately dominated by SWITCH_BB. Make it so. */
417 vec<basic_block> dom_bbs;
420 dom_bbs = get_dominated_by (CDI_DOMINATORS, new_bb);
421 FOR_EACH_VEC_ELT (dom_bbs, i, dom_son)
423 edge e = find_edge (new_bb, dom_son);
424 if (e && single_pred_p (e->dest))
426 set_immediate_dominator (CDI_DOMINATORS, dom_son, switch_bb);
427 bbs_to_fix_dom.safe_push (dom_son);
432 /* csui = (1 << (word_mode) idx) */
433 csui = make_ssa_name (word_type_node, NULL);
434 tmp = fold_build2 (LSHIFT_EXPR, word_type_node, word_mode_one,
435 fold_convert (word_type_node, idx));
436 tmp = force_gimple_operand_gsi (&gsi, tmp,
437 /*simple=*/false, NULL_TREE,
438 /*before=*/true, GSI_SAME_STMT);
439 shift_stmt = gimple_build_assign (csui, tmp);
440 gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT);
441 update_stmt (shift_stmt);
443 /* for each unique set of cases:
444 if (const & csui) goto target */
445 for (k = 0; k < count; k++)
447 tmp = build_int_cst_wide (word_type_node, test[k].lo, test[k].hi);
448 tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp);
449 tmp = force_gimple_operand_gsi (&gsi, tmp,
450 /*simple=*/true, NULL_TREE,
451 /*before=*/true, GSI_SAME_STMT);
452 tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero);
453 new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_edge,
456 bbs_to_fix_dom.safe_push (new_bb);
457 gcc_assert (gimple_bb (swtch) == new_bb);
458 gsi = gsi_last_bb (new_bb);
461 /* We should have removed all edges now. */
462 gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0);
464 /* If nothing matched, go to the default label. */
465 make_edge (gsi_bb (gsi), new_default_bb, EDGE_FALLTHRU);
467 /* The GIMPLE_SWITCH is now redundant. */
468 gsi_remove (&gsi, true);
472 /* Fix up the dominator tree. */
473 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
474 bbs_to_fix_dom.release ();
479 Switch initialization conversion
481 The following pass changes simple initializations of scalars in a switch
482 statement into initializations from a static array. Obviously, the values
483 must be constant and known at compile time and a default branch must be
484 provided. For example, the following code:
508 a_5 = PHI <a_1, a_2, a_3, a_4>
509 b_5 = PHI <b_1, b_2, b_3, b_4>
514 static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
515 static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
518 if (((unsigned) argc) - 1 < 11)
520 a_6 = CSWTCH02[argc - 1];
521 b_6 = CSWTCH01[argc - 1];
531 There are further constraints. Specifically, the range of values across all
532 case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
533 eight) times the number of the actual switch branches.
535 This transformation was contributed by Martin Jambor, see this e-mail:
536 http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */
538 /* The main structure of the pass. */
539 struct switch_conv_info
541 /* The expression used to decide the switch branch. */
544 /* The following integer constants store the minimum and maximum value
545 covered by the case labels. */
549 /* The difference between the above two numbers. Stored here because it
550 is used in all the conversion heuristics, as well as for some of the
551 transformation, and it is expensive to re-compute it all the time. */
554 /* Basic block that contains the actual GIMPLE_SWITCH. */
555 basic_block switch_bb;
557 /* Basic block that is the target of the default case. */
558 basic_block default_bb;
560 /* The single successor block of all branches out of the GIMPLE_SWITCH,
561 if such a block exists. Otherwise NULL. */
562 basic_block final_bb;
564 /* The probability of the default edge in the replaced switch. */
567 /* The count of the default edge in the replaced switch. */
568 gcov_type default_count;
570 /* Combined count of all other (non-default) edges in the replaced switch. */
571 gcov_type other_count;
573 /* Number of phi nodes in the final bb (that we'll be replacing). */
576 /* Array of default values, in the same order as phi nodes. */
577 tree *default_values;
579 /* Constructors of new static arrays. */
580 vec<constructor_elt, va_gc> **constructors;
582 /* Array of ssa names that are initialized with a value from a new static
584 tree *target_inbound_names;
586 /* Array of ssa names that are initialized with the default value if the
587 switch expression is out of range. */
588 tree *target_outbound_names;
590 /* The first load statement that loads a temporary from a new static array.
592 gimple arr_ref_first;
594 /* The last load statement that loads a temporary from a new static array. */
597 /* String reason why the case wasn't a good candidate that is written to the
598 dump file, if there is one. */
601 /* Parameters for expand_switch_using_bit_tests. Should be computed
602 the same way as in expand_case. */
607 /* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */
610 collect_switch_conv_info (gimple swtch, struct switch_conv_info *info)
612 unsigned int branch_num = gimple_switch_num_labels (swtch);
613 tree min_case, max_case;
614 unsigned int count, i;
618 memset (info, 0, sizeof (*info));
620 /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
621 is a default label which is the first in the vector.
622 Collect the bits we can deduce from the CFG. */
623 info->index_expr = gimple_switch_index (swtch);
624 info->switch_bb = gimple_bb (swtch);
626 label_to_block (CASE_LABEL (gimple_switch_default_label (swtch)));
627 e_default = find_edge (info->switch_bb, info->default_bb);
628 info->default_prob = e_default->probability;
629 info->default_count = e_default->count;
630 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
632 info->other_count += e->count;
634 /* See if there is one common successor block for all branch
635 targets. If it exists, record it in FINAL_BB. */
636 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
638 if (! single_pred_p (e->dest))
640 info->final_bb = e->dest;
645 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
647 if (e->dest == info->final_bb)
650 if (single_pred_p (e->dest)
651 && single_succ_p (e->dest)
652 && single_succ (e->dest) == info->final_bb)
655 info->final_bb = NULL;
659 /* Get upper and lower bounds of case values, and the covered range. */
660 min_case = gimple_switch_label (swtch, 1);
661 max_case = gimple_switch_label (swtch, branch_num - 1);
663 info->range_min = CASE_LOW (min_case);
664 if (CASE_HIGH (max_case) != NULL_TREE)
665 info->range_max = CASE_HIGH (max_case);
667 info->range_max = CASE_LOW (max_case);
670 int_const_binop (MINUS_EXPR, info->range_max, info->range_min);
672 /* Get a count of the number of case labels. Single-valued case labels
673 simply count as one, but a case range counts double, since it may
674 require two compares if it gets lowered as a branching tree. */
676 for (i = 1; i < branch_num; i++)
678 tree elt = gimple_switch_label (swtch, i);
681 && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt)))
686 /* Get the number of unique non-default targets out of the GIMPLE_SWITCH
687 block. Assume a CFG cleanup would have already removed degenerate
688 switch statements, this allows us to just use EDGE_COUNT. */
689 info->uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1;
692 /* Checks whether the range given by individual case statements of the SWTCH
693 switch statement isn't too big and whether the number of branches actually
694 satisfies the size of the new array. */
697 check_range (struct switch_conv_info *info)
699 gcc_assert (info->range_size);
700 if (!host_integerp (info->range_size, 1))
702 info->reason = "index range way too large or otherwise unusable";
706 if ((unsigned HOST_WIDE_INT) tree_low_cst (info->range_size, 1)
707 > ((unsigned) info->count * SWITCH_CONVERSION_BRANCH_RATIO))
709 info->reason = "the maximum range-branch ratio exceeded";
716 /* Checks whether all but the FINAL_BB basic blocks are empty. */
719 check_all_empty_except_final (struct switch_conv_info *info)
724 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
726 if (e->dest == info->final_bb)
729 if (!empty_block_p (e->dest))
731 info->reason = "bad case - a non-final BB not empty";
739 /* This function checks whether all required values in phi nodes in final_bb
740 are constants. Required values are those that correspond to a basic block
741 which is a part of the examined switch statement. It returns true if the
742 phi nodes are OK, otherwise false. */
745 check_final_bb (struct switch_conv_info *info)
747 gimple_stmt_iterator gsi;
750 for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
752 gimple phi = gsi_stmt (gsi);
757 for (i = 0; i < gimple_phi_num_args (phi); i++)
759 basic_block bb = gimple_phi_arg_edge (phi, i)->src;
761 if (bb == info->switch_bb
762 || (single_pred_p (bb) && single_pred (bb) == info->switch_bb))
766 val = gimple_phi_arg_def (phi, i);
767 if (!is_gimple_ip_invariant (val))
769 info->reason = "non-invariant value from a case";
770 return false; /* Non-invariant argument. */
772 reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
773 if ((flag_pic && reloc != null_pointer_node)
774 || (!flag_pic && reloc == NULL_TREE))
778 = "value from a case would need runtime relocations";
781 = "value from a case is not a valid initializer";
791 /* The following function allocates default_values, target_{in,out}_names and
792 constructors arrays. The last one is also populated with pointers to
793 vectors that will become constructors of new arrays. */
796 create_temp_arrays (struct switch_conv_info *info)
800 info->default_values = XCNEWVEC (tree, info->phi_count * 3);
801 /* ??? Macros do not support multi argument templates in their
802 argument list. We create a typedef to work around that problem. */
803 typedef vec<constructor_elt, va_gc> *vec_constructor_elt_gc;
804 info->constructors = XCNEWVEC (vec_constructor_elt_gc, info->phi_count);
805 info->target_inbound_names = info->default_values + info->phi_count;
806 info->target_outbound_names = info->target_inbound_names + info->phi_count;
807 for (i = 0; i < info->phi_count; i++)
808 vec_alloc (info->constructors[i], tree_low_cst (info->range_size, 1) + 1);
811 /* Free the arrays created by create_temp_arrays(). The vectors that are
812 created by that function are not freed here, however, because they have
813 already become constructors and must be preserved. */
816 free_temp_arrays (struct switch_conv_info *info)
818 XDELETEVEC (info->constructors);
819 XDELETEVEC (info->default_values);
822 /* Populate the array of default values in the order of phi nodes.
823 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch. */
826 gather_default_values (tree default_case, struct switch_conv_info *info)
828 gimple_stmt_iterator gsi;
829 basic_block bb = label_to_block (CASE_LABEL (default_case));
833 gcc_assert (CASE_LOW (default_case) == NULL_TREE);
835 if (bb == info->final_bb)
836 e = find_edge (info->switch_bb, bb);
838 e = single_succ_edge (bb);
840 for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
842 gimple phi = gsi_stmt (gsi);
843 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
845 info->default_values[i++] = val;
849 /* The following function populates the vectors in the constructors array with
850 future contents of the static arrays. The vectors are populated in the
851 order of phi nodes. SWTCH is the switch statement being converted. */
854 build_constructors (gimple swtch, struct switch_conv_info *info)
856 unsigned i, branch_num = gimple_switch_num_labels (swtch);
857 tree pos = info->range_min;
859 for (i = 1; i < branch_num; i++)
861 tree cs = gimple_switch_label (swtch, i);
862 basic_block bb = label_to_block (CASE_LABEL (cs));
865 gimple_stmt_iterator gsi;
868 if (bb == info->final_bb)
869 e = find_edge (info->switch_bb, bb);
871 e = single_succ_edge (bb);
874 while (tree_int_cst_lt (pos, CASE_LOW (cs)))
877 for (k = 0; k < info->phi_count; k++)
881 elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
883 = unshare_expr_without_location (info->default_values[k]);
884 info->constructors[k]->quick_push (elt);
887 pos = int_const_binop (PLUS_EXPR, pos, integer_one_node);
889 gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
893 high = CASE_HIGH (cs);
895 high = CASE_LOW (cs);
896 for (gsi = gsi_start_phis (info->final_bb);
897 !gsi_end_p (gsi); gsi_next (&gsi))
899 gimple phi = gsi_stmt (gsi);
900 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
901 tree low = CASE_LOW (cs);
908 elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
909 elt.value = unshare_expr_without_location (val);
910 info->constructors[j]->quick_push (elt);
912 pos = int_const_binop (PLUS_EXPR, pos, integer_one_node);
913 } while (!tree_int_cst_lt (high, pos)
914 && tree_int_cst_lt (low, pos));
920 /* If all values in the constructor vector are the same, return the value.
921 Otherwise return NULL_TREE. Not supposed to be called for empty
925 constructor_contains_same_values_p (vec<constructor_elt, va_gc> *vec)
928 tree prev = NULL_TREE;
929 constructor_elt *elt;
931 FOR_EACH_VEC_SAFE_ELT (vec, i, elt)
935 else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST))
941 /* Return type which should be used for array elements, either TYPE,
942 or for integral type some smaller integral type that can still hold
943 all the constants. */
946 array_value_type (gimple swtch, tree type, int num,
947 struct switch_conv_info *info)
949 unsigned int i, len = vec_safe_length (info->constructors[num]);
950 constructor_elt *elt;
951 enum machine_mode mode;
955 if (!INTEGRAL_TYPE_P (type))
958 mode = GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type)));
959 if (GET_MODE_SIZE (TYPE_MODE (type)) <= GET_MODE_SIZE (mode))
962 if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32))
965 FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
969 if (TREE_CODE (elt->value) != INTEGER_CST)
972 cst = TREE_INT_CST (elt->value);
975 unsigned int prec = GET_MODE_BITSIZE (mode);
976 if (prec > HOST_BITS_PER_WIDE_INT)
979 if (sign >= 0 && cst == cst.zext (prec))
981 if (sign == 0 && cst == cst.sext (prec))
986 if (sign <= 0 && cst == cst.sext (prec))
995 mode = GET_MODE_WIDER_MODE (mode);
997 || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (TYPE_MODE (type)))
1003 sign = TYPE_UNSIGNED (type) ? 1 : -1;
1004 smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0);
1005 if (GET_MODE_SIZE (TYPE_MODE (type))
1006 <= GET_MODE_SIZE (TYPE_MODE (smaller_type)))
1009 return smaller_type;
1012 /* Create an appropriate array type and declaration and assemble a static array
1013 variable. Also create a load statement that initializes the variable in
1014 question with a value from the static array. SWTCH is the switch statement
1015 being converted, NUM is the index to arrays of constructors, default values
1016 and target SSA names for this particular array. ARR_INDEX_TYPE is the type
1017 of the index of the new array, PHI is the phi node of the final BB that
1018 corresponds to the value that will be loaded from the created array. TIDX
1019 is an ssa name of a temporary variable holding the index for loads from the
1023 build_one_array (gimple swtch, int num, tree arr_index_type, gimple phi,
1024 tree tidx, struct switch_conv_info *info)
1028 gimple_stmt_iterator gsi = gsi_for_stmt (swtch);
1029 location_t loc = gimple_location (swtch);
1031 gcc_assert (info->default_values[num]);
1033 name = copy_ssa_name (PHI_RESULT (phi), NULL);
1034 info->target_inbound_names[num] = name;
1036 cst = constructor_contains_same_values_p (info->constructors[num]);
1038 load = gimple_build_assign (name, cst);
1041 tree array_type, ctor, decl, value_type, fetch, default_type;
1043 default_type = TREE_TYPE (info->default_values[num]);
1044 value_type = array_value_type (swtch, default_type, num, info);
1045 array_type = build_array_type (value_type, arr_index_type);
1046 if (default_type != value_type)
1049 constructor_elt *elt;
1051 FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
1052 elt->value = fold_convert (value_type, elt->value);
1054 ctor = build_constructor (array_type, info->constructors[num]);
1055 TREE_CONSTANT (ctor) = true;
1056 TREE_STATIC (ctor) = true;
1058 decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type);
1059 TREE_STATIC (decl) = 1;
1060 DECL_INITIAL (decl) = ctor;
1062 DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
1063 DECL_ARTIFICIAL (decl) = 1;
1064 TREE_CONSTANT (decl) = 1;
1065 TREE_READONLY (decl) = 1;
1066 varpool_finalize_decl (decl);
1068 fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
1070 if (default_type != value_type)
1072 fetch = fold_convert (default_type, fetch);
1073 fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE,
1074 true, GSI_SAME_STMT);
1076 load = gimple_build_assign (name, fetch);
1079 gsi_insert_before (&gsi, load, GSI_SAME_STMT);
1081 info->arr_ref_last = load;
1084 /* Builds and initializes static arrays initialized with values gathered from
1085 the SWTCH switch statement. Also creates statements that load values from
1089 build_arrays (gimple swtch, struct switch_conv_info *info)
1091 tree arr_index_type;
1092 tree tidx, sub, utype;
1094 gimple_stmt_iterator gsi;
1096 location_t loc = gimple_location (swtch);
1098 gsi = gsi_for_stmt (swtch);
1100 /* Make sure we do not generate arithmetics in a subrange. */
1101 utype = TREE_TYPE (info->index_expr);
1102 if (TREE_TYPE (utype))
1103 utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1);
1105 utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
1107 arr_index_type = build_index_type (info->range_size);
1108 tidx = make_ssa_name (utype, NULL);
1109 sub = fold_build2_loc (loc, MINUS_EXPR, utype,
1110 fold_convert_loc (loc, utype, info->index_expr),
1111 fold_convert_loc (loc, utype, info->range_min));
1112 sub = force_gimple_operand_gsi (&gsi, sub,
1113 false, NULL, true, GSI_SAME_STMT);
1114 stmt = gimple_build_assign (tidx, sub);
1116 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1118 info->arr_ref_first = stmt;
1120 for (gsi = gsi_start_phis (info->final_bb), i = 0;
1121 !gsi_end_p (gsi); gsi_next (&gsi), i++)
1122 build_one_array (swtch, i, arr_index_type, gsi_stmt (gsi), tidx, info);
1125 /* Generates and appropriately inserts loads of default values at the position
1126 given by BSI. Returns the last inserted statement. */
1129 gen_def_assigns (gimple_stmt_iterator *gsi, struct switch_conv_info *info)
1132 gimple assign = NULL;
1134 for (i = 0; i < info->phi_count; i++)
1136 tree name = copy_ssa_name (info->target_inbound_names[i], NULL);
1137 info->target_outbound_names[i] = name;
1138 assign = gimple_build_assign (name, info->default_values[i]);
1139 gsi_insert_before (gsi, assign, GSI_SAME_STMT);
1140 update_stmt (assign);
1145 /* Deletes the unused bbs and edges that now contain the switch statement and
1146 its empty branch bbs. BBD is the now dead BB containing the original switch
1147 statement, FINAL is the last BB of the converted switch statement (in terms
1151 prune_bbs (basic_block bbd, basic_block final)
1156 for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
1162 delete_basic_block (bb);
1164 delete_basic_block (bbd);
1167 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
1168 from the basic block loading values from an array and E2F from the basic
1169 block loading default values. BBF is the last switch basic block (see the
1170 bbf description in the comment below). */
1173 fix_phi_nodes (edge e1f, edge e2f, basic_block bbf,
1174 struct switch_conv_info *info)
1176 gimple_stmt_iterator gsi;
1179 for (gsi = gsi_start_phis (bbf), i = 0;
1180 !gsi_end_p (gsi); gsi_next (&gsi), i++)
1182 gimple phi = gsi_stmt (gsi);
1183 add_phi_arg (phi, info->target_inbound_names[i], e1f, UNKNOWN_LOCATION);
1184 add_phi_arg (phi, info->target_outbound_names[i], e2f, UNKNOWN_LOCATION);
1188 /* Creates a check whether the switch expression value actually falls into the
1189 range given by all the cases. If it does not, the temporaries are loaded
1190 with default values instead. SWTCH is the switch statement being converted.
1192 bb0 is the bb with the switch statement, however, we'll end it with a
1195 bb1 is the bb to be used when the range check went ok. It is derived from
1198 bb2 is the bb taken when the expression evaluated outside of the range
1199 covered by the created arrays. It is populated by loads of default
1202 bbF is a fall through for both bb1 and bb2 and contains exactly what
1203 originally followed the switch statement.
1205 bbD contains the switch statement (in the end). It is unreachable but we
1206 still need to strip off its edges.
1210 gen_inbound_check (gimple swtch, struct switch_conv_info *info)
1212 tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION);
1213 tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
1214 tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION);
1215 gimple label1, label2, label3;
1222 gimple_stmt_iterator gsi;
1223 basic_block bb0, bb1, bb2, bbf, bbd;
1224 edge e01, e02, e21, e1d, e1f, e2f;
1225 location_t loc = gimple_location (swtch);
1227 gcc_assert (info->default_values);
1229 bb0 = gimple_bb (swtch);
1231 tidx = gimple_assign_lhs (info->arr_ref_first);
1232 utype = TREE_TYPE (tidx);
1234 /* (end of) block 0 */
1235 gsi = gsi_for_stmt (info->arr_ref_first);
1238 bound = fold_convert_loc (loc, utype, info->range_size);
1239 cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
1240 gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1241 update_stmt (cond_stmt);
1244 label2 = gimple_build_label (label_decl2);
1245 gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
1246 last_assign = gen_def_assigns (&gsi, info);
1249 label1 = gimple_build_label (label_decl1);
1250 gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
1253 gsi = gsi_start_bb (info->final_bb);
1254 label3 = gimple_build_label (label_decl3);
1255 gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
1258 e02 = split_block (bb0, cond_stmt);
1261 e21 = split_block (bb2, last_assign);
1265 e1d = split_block (bb1, info->arr_ref_last);
1269 /* flags and profiles of the edge for in-range values */
1270 e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
1271 e01->probability = REG_BR_PROB_BASE - info->default_prob;
1272 e01->count = info->other_count;
1274 /* flags and profiles of the edge taking care of out-of-range values */
1275 e02->flags &= ~EDGE_FALLTHRU;
1276 e02->flags |= EDGE_FALSE_VALUE;
1277 e02->probability = info->default_prob;
1278 e02->count = info->default_count;
1280 bbf = info->final_bb;
1282 e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
1283 e1f->probability = REG_BR_PROB_BASE;
1284 e1f->count = info->other_count;
1286 e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
1287 e2f->probability = REG_BR_PROB_BASE;
1288 e2f->count = info->default_count;
1290 /* frequencies of the new BBs */
1291 bb1->frequency = EDGE_FREQUENCY (e01);
1292 bb2->frequency = EDGE_FREQUENCY (e02);
1293 bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f);
1295 /* Tidy blocks that have become unreachable. */
1296 prune_bbs (bbd, info->final_bb);
1298 /* Fixup the PHI nodes in bbF. */
1299 fix_phi_nodes (e1f, e2f, bbf, info);
1301 /* Fix the dominator tree, if it is available. */
1302 if (dom_info_available_p (CDI_DOMINATORS))
1304 vec<basic_block> bbs_to_fix_dom;
1306 set_immediate_dominator (CDI_DOMINATORS, bb1, bb0);
1307 set_immediate_dominator (CDI_DOMINATORS, bb2, bb0);
1308 if (! get_immediate_dominator (CDI_DOMINATORS, bbf))
1309 /* If bbD was the immediate dominator ... */
1310 set_immediate_dominator (CDI_DOMINATORS, bbf, bb0);
1312 bbs_to_fix_dom.create (4);
1313 bbs_to_fix_dom.quick_push (bb0);
1314 bbs_to_fix_dom.quick_push (bb1);
1315 bbs_to_fix_dom.quick_push (bb2);
1316 bbs_to_fix_dom.quick_push (bbf);
1318 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
1319 bbs_to_fix_dom.release ();
1323 /* The following function is invoked on every switch statement (the current one
1324 is given in SWTCH) and runs the individual phases of switch conversion on it
1325 one after another until one fails or the conversion is completed.
1326 Returns NULL on success, or a pointer to a string with the reason why the
1327 conversion failed. */
1330 process_switch (gimple swtch)
1332 struct switch_conv_info info;
1334 /* Group case labels so that we get the right results from the heuristics
1335 that decide on the code generation approach for this switch. */
1336 group_case_labels_stmt (swtch);
1338 /* If this switch is now a degenerate case with only a default label,
1339 there is nothing left for us to do. */
1340 if (gimple_switch_num_labels (swtch) < 2)
1341 return "switch is a degenerate case";
1343 collect_switch_conv_info (swtch, &info);
1345 /* No error markers should reach here (they should be filtered out
1346 during gimplification). */
1347 gcc_checking_assert (TREE_TYPE (info.index_expr) != error_mark_node);
1349 /* A switch on a constant should have been optimized in tree-cfg-cleanup. */
1350 gcc_checking_assert (! TREE_CONSTANT (info.index_expr));
1352 if (info.uniq <= MAX_CASE_BIT_TESTS)
1354 if (expand_switch_using_bit_tests_p (info.range_size,
1355 info.uniq, info.count))
1358 fputs (" expanding as bit test is preferable\n", dump_file);
1359 emit_case_bit_tests (swtch, info.index_expr,
1360 info.range_min, info.range_size);
1362 loops_state_set (LOOPS_NEED_FIXUP);
1367 /* This will be expanded as a decision tree in stmt.c:expand_case. */
1368 return " expanding as jumps is preferable";
1371 /* If there is no common successor, we cannot do the transformation. */
1372 if (! info.final_bb)
1373 return "no common successor to all case label target blocks found";
1375 /* Check the case label values are within reasonable range: */
1376 if (!check_range (&info))
1378 gcc_assert (info.reason);
1382 /* For all the cases, see whether they are empty, the assignments they
1383 represent constant and so on... */
1384 if (! check_all_empty_except_final (&info))
1386 gcc_assert (info.reason);
1389 if (!check_final_bb (&info))
1391 gcc_assert (info.reason);
1395 /* At this point all checks have passed and we can proceed with the
1398 create_temp_arrays (&info);
1399 gather_default_values (gimple_switch_default_label (swtch), &info);
1400 build_constructors (swtch, &info);
1402 build_arrays (swtch, &info); /* Build the static arrays and assignments. */
1403 gen_inbound_check (swtch, &info); /* Build the bounds check. */
1406 free_temp_arrays (&info);
1410 /* The main function of the pass scans statements for switches and invokes
1411 process_switch on them. */
1414 do_switchconv (void)
1420 const char *failure_reason;
1421 gimple stmt = last_stmt (bb);
1422 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
1426 expanded_location loc = expand_location (gimple_location (stmt));
1428 fprintf (dump_file, "beginning to process the following "
1429 "SWITCH statement (%s:%d) : ------- \n",
1430 loc.file, loc.line);
1431 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1432 putc ('\n', dump_file);
1435 failure_reason = process_switch (stmt);
1436 if (! failure_reason)
1440 fputs ("Switch converted\n", dump_file);
1441 fputs ("--------------------------------\n", dump_file);
1444 /* Make no effort to update the post-dominator tree. It is actually not
1445 that hard for the transformations we have performed, but it is not
1446 supported by iterate_fix_dominators. */
1447 free_dominance_info (CDI_POST_DOMINATORS);
1453 fputs ("Bailing out - ", dump_file);
1454 fputs (failure_reason, dump_file);
1455 fputs ("\n--------------------------------\n", dump_file);
1464 /* The pass gate. */
1467 switchconv_gate (void)
1469 return flag_tree_switch_conversion != 0;
1474 const pass_data pass_data_convert_switch =
1476 GIMPLE_PASS, /* type */
1477 "switchconv", /* name */
1478 OPTGROUP_NONE, /* optinfo_flags */
1479 true, /* has_gate */
1480 true, /* has_execute */
1481 TV_TREE_SWITCH_CONVERSION, /* tv_id */
1482 ( PROP_cfg | PROP_ssa ), /* properties_required */
1483 0, /* properties_provided */
1484 0, /* properties_destroyed */
1485 0, /* todo_flags_start */
1486 ( TODO_update_ssa | TODO_verify_ssa
1488 | TODO_verify_flow ), /* todo_flags_finish */
1491 class pass_convert_switch : public gimple_opt_pass
1494 pass_convert_switch (gcc::context *ctxt)
1495 : gimple_opt_pass (pass_data_convert_switch, ctxt)
1498 /* opt_pass methods: */
1499 bool gate () { return switchconv_gate (); }
1500 unsigned int execute () { return do_switchconv (); }
1502 }; // class pass_convert_switch
1507 make_pass_convert_switch (gcc::context *ctxt)
1509 return new pass_convert_switch (ctxt);