2018-04-24 Steven G. Kargl <kargl@gcc.gnu.org>
[official-gcc.git] / gcc / tree-switch-conversion.c
blobb0470ef1b5e6a46afd89b57fad4547ea8e103b48
1 /* Lower GIMPLE_SWITCH expressions to something more efficient than
2 a jump table.
3 Copyright (C) 2006-2018 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
10 later version.
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
15 for more details.
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
20 02110-1301, USA. */
22 /* This file handles the lowering of GIMPLE_SWITCH to an indexed
23 load, or a series of bit-test-and-branch expressions. */
25 #include "config.h"
26 #include "system.h"
27 #include "coretypes.h"
28 #include "backend.h"
29 #include "insn-codes.h"
30 #include "rtl.h"
31 #include "tree.h"
32 #include "gimple.h"
33 #include "cfghooks.h"
34 #include "tree-pass.h"
35 #include "ssa.h"
36 #include "optabs-tree.h"
37 #include "cgraph.h"
38 #include "gimple-pretty-print.h"
39 #include "params.h"
40 #include "fold-const.h"
41 #include "varasm.h"
42 #include "stor-layout.h"
43 #include "cfganal.h"
44 #include "gimplify.h"
45 #include "gimple-iterator.h"
46 #include "gimplify-me.h"
47 #include "tree-cfg.h"
48 #include "cfgloop.h"
49 #include "alloc-pool.h"
50 #include "target.h"
51 #include "tree-into-ssa.h"
52 #include "omp-general.h"
54 /* ??? For lang_hooks.types.type_for_mode, but is there a word_mode
55 type in the GIMPLE type system that is language-independent? */
56 #include "langhooks.h"
59 /* Maximum number of case bit tests.
60 FIXME: This should be derived from PARAM_CASE_VALUES_THRESHOLD and
61 targetm.case_values_threshold(), or be its own param. */
62 #define MAX_CASE_BIT_TESTS 3
64 /* Track whether or not we have altered the CFG and thus may need to
65 cleanup the CFG when complete. */
66 bool cfg_altered;
68 /* Split the basic block at the statement pointed to by GSIP, and insert
69 a branch to the target basic block of E_TRUE conditional on tree
70 expression COND.
72 It is assumed that there is already an edge from the to-be-split
73 basic block to E_TRUE->dest block. This edge is removed, and the
74 profile information on the edge is re-used for the new conditional
75 jump.
77 The CFG is updated. The dominator tree will not be valid after
78 this transformation, but the immediate dominators are updated if
79 UPDATE_DOMINATORS is true.
81 Returns the newly created basic block. */
83 static basic_block
84 hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
85 tree cond, edge e_true,
86 bool update_dominators)
88 tree tmp;
89 gcond *cond_stmt;
90 edge e_false;
91 basic_block new_bb, split_bb = gsi_bb (*gsip);
92 bool dominated_e_true = false;
94 gcc_assert (e_true->src == split_bb);
96 if (update_dominators
97 && get_immediate_dominator (CDI_DOMINATORS, e_true->dest) == split_bb)
98 dominated_e_true = true;
100 tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL,
101 /*before=*/true, GSI_SAME_STMT);
102 cond_stmt = gimple_build_cond_from_tree (tmp, NULL_TREE, NULL_TREE);
103 gsi_insert_before (gsip, cond_stmt, GSI_SAME_STMT);
105 e_false = split_block (split_bb, cond_stmt);
106 new_bb = e_false->dest;
107 redirect_edge_pred (e_true, split_bb);
109 e_true->flags &= ~EDGE_FALLTHRU;
110 e_true->flags |= EDGE_TRUE_VALUE;
112 e_false->flags &= ~EDGE_FALLTHRU;
113 e_false->flags |= EDGE_FALSE_VALUE;
114 e_false->probability = e_true->probability.invert ();
115 new_bb->count = e_false->count ();
117 if (update_dominators)
119 if (dominated_e_true)
120 set_immediate_dominator (CDI_DOMINATORS, e_true->dest, split_bb);
121 set_immediate_dominator (CDI_DOMINATORS, e_false->dest, split_bb);
124 return new_bb;
128 /* Return true if a switch should be expanded as a bit test.
129 RANGE is the difference between highest and lowest case.
130 UNIQ is number of unique case node targets, not counting the default case.
131 COUNT is the number of comparisons needed, not counting the default case. */
133 static bool
134 expand_switch_using_bit_tests_p (tree range,
135 unsigned int uniq,
136 unsigned int count, bool speed_p)
138 return (((uniq == 1 && count >= 3)
139 || (uniq == 2 && count >= 5)
140 || (uniq == 3 && count >= 6))
141 && lshift_cheap_p (speed_p)
142 && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0
143 && compare_tree_int (range, 0) > 0);
146 /* Implement switch statements with bit tests
148 A GIMPLE switch statement can be expanded to a short sequence of bit-wise
149 comparisons. "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)"
150 where CST and MINVAL are integer constants. This is better than a series
151 of compare-and-banch insns in some cases, e.g. we can implement:
153 if ((x==4) || (x==6) || (x==9) || (x==11))
155 as a single bit test:
157 if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11)))
159 This transformation is only applied if the number of case targets is small,
160 if CST constains at least 3 bits, and "1 << x" is cheap. The bit tests are
161 performed in "word_mode".
163 The following example shows the code the transformation generates:
165 int bar(int x)
167 switch (x)
169 case '0': case '1': case '2': case '3': case '4':
170 case '5': case '6': case '7': case '8': case '9':
171 case 'A': case 'B': case 'C': case 'D': case 'E':
172 case 'F':
173 return 1;
175 return 0;
180 bar (int x)
182 tmp1 = x - 48;
183 if (tmp1 > (70 - 48)) goto L2;
184 tmp2 = 1 << tmp1;
185 tmp3 = 0b11111100000001111111111;
186 if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2;
188 return 1;
190 return 0;
193 TODO: There are still some improvements to this transformation that could
194 be implemented:
196 * A narrower mode than word_mode could be used if that is cheaper, e.g.
197 for x86_64 where a narrower-mode shift may result in smaller code.
199 * The compounded constant could be shifted rather than the one. The
200 test would be either on the sign bit or on the least significant bit,
201 depending on the direction of the shift. On some machines, the test
202 for the branch would be free if the bit to test is already set by the
203 shift operation.
205 This transformation was contributed by Roger Sayle, see this e-mail:
206 http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html
209 /* A case_bit_test represents a set of case nodes that may be
210 selected from using a bit-wise comparison. HI and LO hold
211 the integer to be tested against, TARGET_EDGE contains the
212 edge to the basic block to jump to upon success and BITS
213 counts the number of case nodes handled by this test,
214 typically the number of bits set in HI:LO. The LABEL field
215 is used to quickly identify all cases in this set without
216 looking at label_to_block for every case label. */
218 struct case_bit_test
220 wide_int mask;
221 edge target_edge;
222 tree label;
223 int bits;
226 /* Comparison function for qsort to order bit tests by decreasing
227 probability of execution. Our best guess comes from a measured
228 profile. If the profile counts are equal, break even on the
229 number of case nodes, i.e. the node with the most cases gets
230 tested first.
232 TODO: Actually this currently runs before a profile is available.
233 Therefore the case-as-bit-tests transformation should be done
234 later in the pass pipeline, or something along the lines of
235 "Efficient and effective branch reordering using profile data"
236 (Yang et. al., 2002) should be implemented (although, how good
237 is a paper is called "Efficient and effective ..." when the
238 latter is implied by the former, but oh well...). */
240 static int
241 case_bit_test_cmp (const void *p1, const void *p2)
243 const struct case_bit_test *const d1 = (const struct case_bit_test *) p1;
244 const struct case_bit_test *const d2 = (const struct case_bit_test *) p2;
246 if (d2->target_edge->count () < d1->target_edge->count ())
247 return -1;
248 if (d2->target_edge->count () > d1->target_edge->count ())
249 return 1;
250 if (d2->bits != d1->bits)
251 return d2->bits - d1->bits;
253 /* Stabilize the sort. */
254 return LABEL_DECL_UID (d2->label) - LABEL_DECL_UID (d1->label);
257 /* Expand a switch statement by a short sequence of bit-wise
258 comparisons. "switch(x)" is effectively converted into
259 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
260 integer constants.
262 INDEX_EXPR is the value being switched on.
264 MINVAL is the lowest case value of in the case nodes,
265 and RANGE is highest value minus MINVAL. MINVAL and RANGE
266 are not guaranteed to be of the same type as INDEX_EXPR
267 (the gimplifier doesn't change the type of case label values,
268 and MINVAL and RANGE are derived from those values).
269 MAXVAL is MINVAL + RANGE.
271 There *MUST* be MAX_CASE_BIT_TESTS or less unique case
272 node targets. */
274 static void
275 emit_case_bit_tests (gswitch *swtch, tree index_expr,
276 tree minval, tree range, tree maxval)
278 struct case_bit_test test[MAX_CASE_BIT_TESTS] = { {} };
279 unsigned int i, j, k;
280 unsigned int count;
282 basic_block switch_bb = gimple_bb (swtch);
283 basic_block default_bb, new_default_bb, new_bb;
284 edge default_edge;
285 bool update_dom = dom_info_available_p (CDI_DOMINATORS);
287 vec<basic_block> bbs_to_fix_dom = vNULL;
289 tree index_type = TREE_TYPE (index_expr);
290 tree unsigned_index_type = unsigned_type_for (index_type);
291 unsigned int branch_num = gimple_switch_num_labels (swtch);
293 gimple_stmt_iterator gsi;
294 gassign *shift_stmt;
296 tree idx, tmp, csui;
297 tree word_type_node = lang_hooks.types.type_for_mode (word_mode, 1);
298 tree word_mode_zero = fold_convert (word_type_node, integer_zero_node);
299 tree word_mode_one = fold_convert (word_type_node, integer_one_node);
300 int prec = TYPE_PRECISION (word_type_node);
301 wide_int wone = wi::one (prec);
303 /* Get the edge for the default case. */
304 tmp = gimple_switch_default_label (swtch);
305 default_bb = label_to_block (CASE_LABEL (tmp));
306 default_edge = find_edge (switch_bb, default_bb);
308 /* Go through all case labels, and collect the case labels, profile
309 counts, and other information we need to build the branch tests. */
310 count = 0;
311 for (i = 1; i < branch_num; i++)
313 unsigned int lo, hi;
314 tree cs = gimple_switch_label (swtch, i);
315 tree label = CASE_LABEL (cs);
316 edge e = find_edge (switch_bb, label_to_block (label));
317 for (k = 0; k < count; k++)
318 if (e == test[k].target_edge)
319 break;
321 if (k == count)
323 gcc_checking_assert (count < MAX_CASE_BIT_TESTS);
324 test[k].mask = wi::zero (prec);
325 test[k].target_edge = e;
326 test[k].label = label;
327 test[k].bits = 1;
328 count++;
330 else
331 test[k].bits++;
333 lo = tree_to_uhwi (int_const_binop (MINUS_EXPR,
334 CASE_LOW (cs), minval));
335 if (CASE_HIGH (cs) == NULL_TREE)
336 hi = lo;
337 else
338 hi = tree_to_uhwi (int_const_binop (MINUS_EXPR,
339 CASE_HIGH (cs), minval));
341 for (j = lo; j <= hi; j++)
342 test[k].mask |= wi::lshift (wone, j);
345 qsort (test, count, sizeof (*test), case_bit_test_cmp);
347 /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of
348 the minval subtractions, but it might make the mask constants more
349 expensive. So, compare the costs. */
350 if (compare_tree_int (minval, 0) > 0
351 && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
353 int cost_diff;
354 HOST_WIDE_INT m = tree_to_uhwi (minval);
355 rtx reg = gen_raw_REG (word_mode, 10000);
356 bool speed_p = optimize_bb_for_speed_p (gimple_bb (swtch));
357 cost_diff = set_rtx_cost (gen_rtx_PLUS (word_mode, reg,
358 GEN_INT (-m)), speed_p);
359 for (i = 0; i < count; i++)
361 rtx r = immed_wide_int_const (test[i].mask, word_mode);
362 cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r),
363 word_mode, speed_p);
364 r = immed_wide_int_const (wi::lshift (test[i].mask, m), word_mode);
365 cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r),
366 word_mode, speed_p);
368 if (cost_diff > 0)
370 for (i = 0; i < count; i++)
371 test[i].mask = wi::lshift (test[i].mask, m);
372 minval = build_zero_cst (TREE_TYPE (minval));
373 range = maxval;
377 /* We generate two jumps to the default case label.
378 Split the default edge, so that we don't have to do any PHI node
379 updating. */
380 new_default_bb = split_edge (default_edge);
382 if (update_dom)
384 bbs_to_fix_dom.create (10);
385 bbs_to_fix_dom.quick_push (switch_bb);
386 bbs_to_fix_dom.quick_push (default_bb);
387 bbs_to_fix_dom.quick_push (new_default_bb);
390 /* Now build the test-and-branch code. */
392 gsi = gsi_last_bb (switch_bb);
394 /* idx = (unsigned)x - minval. */
395 idx = fold_convert (unsigned_index_type, index_expr);
396 idx = fold_build2 (MINUS_EXPR, unsigned_index_type, idx,
397 fold_convert (unsigned_index_type, minval));
398 idx = force_gimple_operand_gsi (&gsi, idx,
399 /*simple=*/true, NULL_TREE,
400 /*before=*/true, GSI_SAME_STMT);
402 /* if (idx > range) goto default */
403 range = force_gimple_operand_gsi (&gsi,
404 fold_convert (unsigned_index_type, range),
405 /*simple=*/true, NULL_TREE,
406 /*before=*/true, GSI_SAME_STMT);
407 tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range);
408 new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, default_edge, update_dom);
409 if (update_dom)
410 bbs_to_fix_dom.quick_push (new_bb);
411 gcc_assert (gimple_bb (swtch) == new_bb);
412 gsi = gsi_last_bb (new_bb);
414 /* Any blocks dominated by the GIMPLE_SWITCH, but that are not successors
415 of NEW_BB, are still immediately dominated by SWITCH_BB. Make it so. */
416 if (update_dom)
418 vec<basic_block> dom_bbs;
419 basic_block dom_son;
421 dom_bbs = get_dominated_by (CDI_DOMINATORS, new_bb);
422 FOR_EACH_VEC_ELT (dom_bbs, i, dom_son)
424 edge e = find_edge (new_bb, dom_son);
425 if (e && single_pred_p (e->dest))
426 continue;
427 set_immediate_dominator (CDI_DOMINATORS, dom_son, switch_bb);
428 bbs_to_fix_dom.safe_push (dom_son);
430 dom_bbs.release ();
433 /* csui = (1 << (word_mode) idx) */
434 csui = make_ssa_name (word_type_node);
435 tmp = fold_build2 (LSHIFT_EXPR, word_type_node, word_mode_one,
436 fold_convert (word_type_node, idx));
437 tmp = force_gimple_operand_gsi (&gsi, tmp,
438 /*simple=*/false, NULL_TREE,
439 /*before=*/true, GSI_SAME_STMT);
440 shift_stmt = gimple_build_assign (csui, tmp);
441 gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT);
442 update_stmt (shift_stmt);
444 /* for each unique set of cases:
445 if (const & csui) goto target */
446 for (k = 0; k < count; k++)
448 tmp = wide_int_to_tree (word_type_node, test[k].mask);
449 tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp);
450 tmp = force_gimple_operand_gsi (&gsi, tmp,
451 /*simple=*/true, NULL_TREE,
452 /*before=*/true, GSI_SAME_STMT);
453 tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero);
454 new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_edge,
455 update_dom);
456 if (update_dom)
457 bbs_to_fix_dom.safe_push (new_bb);
458 gcc_assert (gimple_bb (swtch) == new_bb);
459 gsi = gsi_last_bb (new_bb);
462 /* We should have removed all edges now. */
463 gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0);
465 /* If nothing matched, go to the default label. */
466 make_edge (gsi_bb (gsi), new_default_bb, EDGE_FALLTHRU);
468 /* The GIMPLE_SWITCH is now redundant. */
469 gsi_remove (&gsi, true);
471 if (update_dom)
473 /* Fix up the dominator tree. */
474 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
475 bbs_to_fix_dom.release ();
480 Switch initialization conversion
482 The following pass changes simple initializations of scalars in a switch
483 statement into initializations from a static array. Obviously, the values
484 must be constant and known at compile time and a default branch must be
485 provided. For example, the following code:
487 int a,b;
489 switch (argc)
491 case 1:
492 case 2:
493 a_1 = 8;
494 b_1 = 6;
495 break;
496 case 3:
497 a_2 = 9;
498 b_2 = 5;
499 break;
500 case 12:
501 a_3 = 10;
502 b_3 = 4;
503 break;
504 default:
505 a_4 = 16;
506 b_4 = 1;
507 break;
509 a_5 = PHI <a_1, a_2, a_3, a_4>
510 b_5 = PHI <b_1, b_2, b_3, b_4>
513 is changed into:
515 static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
516 static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
517 16, 16, 10};
519 if (((unsigned) argc) - 1 < 11)
521 a_6 = CSWTCH02[argc - 1];
522 b_6 = CSWTCH01[argc - 1];
524 else
526 a_7 = 16;
527 b_7 = 1;
529 a_5 = PHI <a_6, a_7>
530 b_b = PHI <b_6, b_7>
532 There are further constraints. Specifically, the range of values across all
533 case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
534 eight) times the number of the actual switch branches.
536 This transformation was contributed by Martin Jambor, see this e-mail:
537 http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */
539 /* The main structure of the pass. */
540 struct switch_conv_info
542 /* The expression used to decide the switch branch. */
543 tree index_expr;
545 /* The following integer constants store the minimum and maximum value
546 covered by the case labels. */
547 tree range_min;
548 tree range_max;
550 /* The difference between the above two numbers. Stored here because it
551 is used in all the conversion heuristics, as well as for some of the
552 transformation, and it is expensive to re-compute it all the time. */
553 tree range_size;
555 /* Basic block that contains the actual GIMPLE_SWITCH. */
556 basic_block switch_bb;
558 /* Basic block that is the target of the default case. */
559 basic_block default_bb;
561 /* The single successor block of all branches out of the GIMPLE_SWITCH,
562 if such a block exists. Otherwise NULL. */
563 basic_block final_bb;
565 /* The probability of the default edge in the replaced switch. */
566 profile_probability default_prob;
568 /* The count of the default edge in the replaced switch. */
569 profile_count default_count;
571 /* Combined count of all other (non-default) edges in the replaced switch. */
572 profile_count other_count;
574 /* Number of phi nodes in the final bb (that we'll be replacing). */
575 int phi_count;
577 /* Array of default values, in the same order as phi nodes. */
578 tree *default_values;
580 /* Constructors of new static arrays. */
581 vec<constructor_elt, va_gc> **constructors;
583 /* Array of ssa names that are initialized with a value from a new static
584 array. */
585 tree *target_inbound_names;
587 /* Array of ssa names that are initialized with the default value if the
588 switch expression is out of range. */
589 tree *target_outbound_names;
591 /* VOP SSA_NAME. */
592 tree target_vop;
594 /* The first load statement that loads a temporary from a new static array.
596 gimple *arr_ref_first;
598 /* The last load statement that loads a temporary from a new static array. */
599 gimple *arr_ref_last;
601 /* String reason why the case wasn't a good candidate that is written to the
602 dump file, if there is one. */
603 const char *reason;
605 /* True if default case is not used for any value between range_min and
606 range_max inclusive. */
607 bool contiguous_range;
609 /* True if default case does not have the required shape for other case
610 labels. */
611 bool default_case_nonstandard;
613 /* Parameters for expand_switch_using_bit_tests. Should be computed
614 the same way as in expand_case. */
615 unsigned int uniq;
616 unsigned int count;
619 /* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */
621 static void
622 collect_switch_conv_info (gswitch *swtch, struct switch_conv_info *info)
624 unsigned int branch_num = gimple_switch_num_labels (swtch);
625 tree min_case, max_case;
626 unsigned int count, i;
627 edge e, e_default, e_first;
628 edge_iterator ei;
629 basic_block first;
631 memset (info, 0, sizeof (*info));
633 /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
634 is a default label which is the first in the vector.
635 Collect the bits we can deduce from the CFG. */
636 info->index_expr = gimple_switch_index (swtch);
637 info->switch_bb = gimple_bb (swtch);
638 info->default_bb
639 = label_to_block (CASE_LABEL (gimple_switch_default_label (swtch)));
640 e_default = find_edge (info->switch_bb, info->default_bb);
641 info->default_prob = e_default->probability;
642 info->default_count = e_default->count ();
643 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
644 if (e != e_default)
645 info->other_count += e->count ();
647 /* Get upper and lower bounds of case values, and the covered range. */
648 min_case = gimple_switch_label (swtch, 1);
649 max_case = gimple_switch_label (swtch, branch_num - 1);
651 info->range_min = CASE_LOW (min_case);
652 if (CASE_HIGH (max_case) != NULL_TREE)
653 info->range_max = CASE_HIGH (max_case);
654 else
655 info->range_max = CASE_LOW (max_case);
657 info->contiguous_range = true;
658 tree last = CASE_HIGH (min_case) ? CASE_HIGH (min_case) : info->range_min;
659 for (i = 2; i < branch_num; i++)
661 tree elt = gimple_switch_label (swtch, i);
662 if (wi::to_wide (last) + 1 != wi::to_wide (CASE_LOW (elt)))
664 info->contiguous_range = false;
665 break;
667 last = CASE_HIGH (elt) ? CASE_HIGH (elt) : CASE_LOW (elt);
670 if (info->contiguous_range)
672 first = label_to_block (CASE_LABEL (gimple_switch_label (swtch, 1)));
673 e_first = find_edge (info->switch_bb, first);
675 else
677 first = info->default_bb;
678 e_first = e_default;
681 /* See if there is one common successor block for all branch
682 targets. If it exists, record it in FINAL_BB.
683 Start with the destination of the first non-default case
684 if the range is contiguous and default case otherwise as
685 guess or its destination in case it is a forwarder block. */
686 if (! single_pred_p (e_first->dest))
687 info->final_bb = e_first->dest;
688 else if (single_succ_p (e_first->dest)
689 && ! single_pred_p (single_succ (e_first->dest)))
690 info->final_bb = single_succ (e_first->dest);
691 /* Require that all switch destinations are either that common
692 FINAL_BB or a forwarder to it, except for the default
693 case if contiguous range. */
694 if (info->final_bb)
695 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
697 if (e->dest == info->final_bb)
698 continue;
700 if (single_pred_p (e->dest)
701 && single_succ_p (e->dest)
702 && single_succ (e->dest) == info->final_bb)
703 continue;
705 if (e == e_default && info->contiguous_range)
707 info->default_case_nonstandard = true;
708 continue;
711 info->final_bb = NULL;
712 break;
715 info->range_size
716 = int_const_binop (MINUS_EXPR, info->range_max, info->range_min);
718 /* Get a count of the number of case labels. Single-valued case labels
719 simply count as one, but a case range counts double, since it may
720 require two compares if it gets lowered as a branching tree. */
721 count = 0;
722 for (i = 1; i < branch_num; i++)
724 tree elt = gimple_switch_label (swtch, i);
725 count++;
726 if (CASE_HIGH (elt)
727 && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt)))
728 count++;
730 info->count = count;
732 /* Get the number of unique non-default targets out of the GIMPLE_SWITCH
733 block. Assume a CFG cleanup would have already removed degenerate
734 switch statements, this allows us to just use EDGE_COUNT. */
735 info->uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1;
738 /* Checks whether the range given by individual case statements of the SWTCH
739 switch statement isn't too big and whether the number of branches actually
740 satisfies the size of the new array. */
742 static bool
743 check_range (struct switch_conv_info *info)
745 gcc_assert (info->range_size);
746 if (!tree_fits_uhwi_p (info->range_size))
748 info->reason = "index range way too large or otherwise unusable";
749 return false;
752 if (tree_to_uhwi (info->range_size)
753 > ((unsigned) info->count * SWITCH_CONVERSION_BRANCH_RATIO))
755 info->reason = "the maximum range-branch ratio exceeded";
756 return false;
759 return true;
762 /* Checks whether all but the FINAL_BB basic blocks are empty. */
764 static bool
765 check_all_empty_except_final (struct switch_conv_info *info)
767 edge e, e_default = find_edge (info->switch_bb, info->default_bb);
768 edge_iterator ei;
770 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
772 if (e->dest == info->final_bb)
773 continue;
775 if (!empty_block_p (e->dest))
777 if (info->contiguous_range && e == e_default)
779 info->default_case_nonstandard = true;
780 continue;
783 info->reason = "bad case - a non-final BB not empty";
784 return false;
788 return true;
791 /* This function checks whether all required values in phi nodes in final_bb
792 are constants. Required values are those that correspond to a basic block
793 which is a part of the examined switch statement. It returns true if the
794 phi nodes are OK, otherwise false. */
796 static bool
797 check_final_bb (gswitch *swtch, struct switch_conv_info *info)
799 gphi_iterator gsi;
801 info->phi_count = 0;
802 for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
804 gphi *phi = gsi.phi ();
805 unsigned int i;
807 if (virtual_operand_p (gimple_phi_result (phi)))
808 continue;
810 info->phi_count++;
812 for (i = 0; i < gimple_phi_num_args (phi); i++)
814 basic_block bb = gimple_phi_arg_edge (phi, i)->src;
816 if (bb == info->switch_bb
817 || (single_pred_p (bb)
818 && single_pred (bb) == info->switch_bb
819 && (!info->default_case_nonstandard
820 || empty_block_p (bb))))
822 tree reloc, val;
823 const char *reason = NULL;
825 val = gimple_phi_arg_def (phi, i);
826 if (!is_gimple_ip_invariant (val))
827 reason = "non-invariant value from a case";
828 else
830 reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
831 if ((flag_pic && reloc != null_pointer_node)
832 || (!flag_pic && reloc == NULL_TREE))
834 if (reloc)
835 reason
836 = "value from a case would need runtime relocations";
837 else
838 reason
839 = "value from a case is not a valid initializer";
842 if (reason)
844 /* For contiguous range, we can allow non-constant
845 or one that needs relocation, as long as it is
846 only reachable from the default case. */
847 if (bb == info->switch_bb)
848 bb = info->final_bb;
849 if (!info->contiguous_range || bb != info->default_bb)
851 info->reason = reason;
852 return false;
855 unsigned int branch_num = gimple_switch_num_labels (swtch);
856 for (unsigned int i = 1; i < branch_num; i++)
858 tree lab = CASE_LABEL (gimple_switch_label (swtch, i));
859 if (label_to_block (lab) == bb)
861 info->reason = reason;
862 return false;
865 info->default_case_nonstandard = true;
871 return true;
874 /* The following function allocates default_values, target_{in,out}_names and
875 constructors arrays. The last one is also populated with pointers to
876 vectors that will become constructors of new arrays. */
878 static void
879 create_temp_arrays (struct switch_conv_info *info)
881 int i;
883 info->default_values = XCNEWVEC (tree, info->phi_count * 3);
884 /* ??? Macros do not support multi argument templates in their
885 argument list. We create a typedef to work around that problem. */
886 typedef vec<constructor_elt, va_gc> *vec_constructor_elt_gc;
887 info->constructors = XCNEWVEC (vec_constructor_elt_gc, info->phi_count);
888 info->target_inbound_names = info->default_values + info->phi_count;
889 info->target_outbound_names = info->target_inbound_names + info->phi_count;
890 for (i = 0; i < info->phi_count; i++)
891 vec_alloc (info->constructors[i], tree_to_uhwi (info->range_size) + 1);
894 /* Free the arrays created by create_temp_arrays(). The vectors that are
895 created by that function are not freed here, however, because they have
896 already become constructors and must be preserved. */
898 static void
899 free_temp_arrays (struct switch_conv_info *info)
901 XDELETEVEC (info->constructors);
902 XDELETEVEC (info->default_values);
905 /* Populate the array of default values in the order of phi nodes.
906 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch
907 if the range is non-contiguous or the default case has standard
908 structure, otherwise it is the first non-default case instead. */
910 static void
911 gather_default_values (tree default_case, struct switch_conv_info *info)
913 gphi_iterator gsi;
914 basic_block bb = label_to_block (CASE_LABEL (default_case));
915 edge e;
916 int i = 0;
918 gcc_assert (CASE_LOW (default_case) == NULL_TREE
919 || info->default_case_nonstandard);
921 if (bb == info->final_bb)
922 e = find_edge (info->switch_bb, bb);
923 else
924 e = single_succ_edge (bb);
926 for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
928 gphi *phi = gsi.phi ();
929 if (virtual_operand_p (gimple_phi_result (phi)))
930 continue;
931 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
932 gcc_assert (val);
933 info->default_values[i++] = val;
937 /* The following function populates the vectors in the constructors array with
938 future contents of the static arrays. The vectors are populated in the
939 order of phi nodes. SWTCH is the switch statement being converted. */
941 static void
942 build_constructors (gswitch *swtch, struct switch_conv_info *info)
944 unsigned i, branch_num = gimple_switch_num_labels (swtch);
945 tree pos = info->range_min;
946 tree pos_one = build_int_cst (TREE_TYPE (pos), 1);
948 for (i = 1; i < branch_num; i++)
950 tree cs = gimple_switch_label (swtch, i);
951 basic_block bb = label_to_block (CASE_LABEL (cs));
952 edge e;
953 tree high;
954 gphi_iterator gsi;
955 int j;
957 if (bb == info->final_bb)
958 e = find_edge (info->switch_bb, bb);
959 else
960 e = single_succ_edge (bb);
961 gcc_assert (e);
963 while (tree_int_cst_lt (pos, CASE_LOW (cs)))
965 int k;
966 gcc_assert (!info->contiguous_range);
967 for (k = 0; k < info->phi_count; k++)
969 constructor_elt elt;
971 elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
972 elt.value
973 = unshare_expr_without_location (info->default_values[k]);
974 info->constructors[k]->quick_push (elt);
977 pos = int_const_binop (PLUS_EXPR, pos, pos_one);
979 gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
981 j = 0;
982 if (CASE_HIGH (cs))
983 high = CASE_HIGH (cs);
984 else
985 high = CASE_LOW (cs);
986 for (gsi = gsi_start_phis (info->final_bb);
987 !gsi_end_p (gsi); gsi_next (&gsi))
989 gphi *phi = gsi.phi ();
990 if (virtual_operand_p (gimple_phi_result (phi)))
991 continue;
992 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
993 tree low = CASE_LOW (cs);
994 pos = CASE_LOW (cs);
998 constructor_elt elt;
1000 elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
1001 elt.value = unshare_expr_without_location (val);
1002 info->constructors[j]->quick_push (elt);
1004 pos = int_const_binop (PLUS_EXPR, pos, pos_one);
1005 } while (!tree_int_cst_lt (high, pos)
1006 && tree_int_cst_lt (low, pos));
1007 j++;
1012 /* If all values in the constructor vector are the same, return the value.
1013 Otherwise return NULL_TREE. Not supposed to be called for empty
1014 vectors. */
1016 static tree
1017 constructor_contains_same_values_p (vec<constructor_elt, va_gc> *vec)
1019 unsigned int i;
1020 tree prev = NULL_TREE;
1021 constructor_elt *elt;
1023 FOR_EACH_VEC_SAFE_ELT (vec, i, elt)
1025 if (!prev)
1026 prev = elt->value;
1027 else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST))
1028 return NULL_TREE;
1030 return prev;
1033 /* Return type which should be used for array elements, either TYPE's
1034 main variant or, for integral types, some smaller integral type
1035 that can still hold all the constants. */
1037 static tree
1038 array_value_type (gswitch *swtch, tree type, int num,
1039 struct switch_conv_info *info)
1041 unsigned int i, len = vec_safe_length (info->constructors[num]);
1042 constructor_elt *elt;
1043 int sign = 0;
1044 tree smaller_type;
1046 /* Types with alignments greater than their size can reach here, e.g. out of
1047 SRA. We couldn't use these as an array component type so get back to the
1048 main variant first, which, for our purposes, is fine for other types as
1049 well. */
1051 type = TYPE_MAIN_VARIANT (type);
1053 if (!INTEGRAL_TYPE_P (type))
1054 return type;
1056 scalar_int_mode type_mode = SCALAR_INT_TYPE_MODE (type);
1057 scalar_int_mode mode = get_narrowest_mode (type_mode);
1058 if (GET_MODE_SIZE (type_mode) <= GET_MODE_SIZE (mode))
1059 return type;
1061 if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32))
1062 return type;
1064 FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
1066 wide_int cst;
1068 if (TREE_CODE (elt->value) != INTEGER_CST)
1069 return type;
1071 cst = wi::to_wide (elt->value);
1072 while (1)
1074 unsigned int prec = GET_MODE_BITSIZE (mode);
1075 if (prec > HOST_BITS_PER_WIDE_INT)
1076 return type;
1078 if (sign >= 0 && cst == wi::zext (cst, prec))
1080 if (sign == 0 && cst == wi::sext (cst, prec))
1081 break;
1082 sign = 1;
1083 break;
1085 if (sign <= 0 && cst == wi::sext (cst, prec))
1087 sign = -1;
1088 break;
1091 if (sign == 1)
1092 sign = 0;
1094 if (!GET_MODE_WIDER_MODE (mode).exists (&mode)
1095 || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (type_mode))
1096 return type;
1100 if (sign == 0)
1101 sign = TYPE_UNSIGNED (type) ? 1 : -1;
1102 smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0);
1103 if (GET_MODE_SIZE (type_mode)
1104 <= GET_MODE_SIZE (SCALAR_INT_TYPE_MODE (smaller_type)))
1105 return type;
1107 return smaller_type;
1110 /* Create an appropriate array type and declaration and assemble a static array
1111 variable. Also create a load statement that initializes the variable in
1112 question with a value from the static array. SWTCH is the switch statement
1113 being converted, NUM is the index to arrays of constructors, default values
1114 and target SSA names for this particular array. ARR_INDEX_TYPE is the type
1115 of the index of the new array, PHI is the phi node of the final BB that
1116 corresponds to the value that will be loaded from the created array. TIDX
1117 is an ssa name of a temporary variable holding the index for loads from the
1118 new array. */
1120 static void
1121 build_one_array (gswitch *swtch, int num, tree arr_index_type,
1122 gphi *phi, tree tidx, struct switch_conv_info *info)
1124 tree name, cst;
1125 gimple *load;
1126 gimple_stmt_iterator gsi = gsi_for_stmt (swtch);
1127 location_t loc = gimple_location (swtch);
1129 gcc_assert (info->default_values[num]);
1131 name = copy_ssa_name (PHI_RESULT (phi));
1132 info->target_inbound_names[num] = name;
1134 cst = constructor_contains_same_values_p (info->constructors[num]);
1135 if (cst)
1136 load = gimple_build_assign (name, cst);
1137 else
1139 tree array_type, ctor, decl, value_type, fetch, default_type;
1141 default_type = TREE_TYPE (info->default_values[num]);
1142 value_type = array_value_type (swtch, default_type, num, info);
1143 array_type = build_array_type (value_type, arr_index_type);
1144 if (default_type != value_type)
1146 unsigned int i;
1147 constructor_elt *elt;
1149 FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
1150 elt->value = fold_convert (value_type, elt->value);
1152 ctor = build_constructor (array_type, info->constructors[num]);
1153 TREE_CONSTANT (ctor) = true;
1154 TREE_STATIC (ctor) = true;
1156 decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type);
1157 TREE_STATIC (decl) = 1;
1158 DECL_INITIAL (decl) = ctor;
1160 DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
1161 DECL_ARTIFICIAL (decl) = 1;
1162 DECL_IGNORED_P (decl) = 1;
1163 TREE_CONSTANT (decl) = 1;
1164 TREE_READONLY (decl) = 1;
1165 DECL_IGNORED_P (decl) = 1;
1166 if (offloading_function_p (cfun->decl))
1167 DECL_ATTRIBUTES (decl)
1168 = tree_cons (get_identifier ("omp declare target"), NULL_TREE,
1169 NULL_TREE);
1170 varpool_node::finalize_decl (decl);
1172 fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
1173 NULL_TREE);
1174 if (default_type != value_type)
1176 fetch = fold_convert (default_type, fetch);
1177 fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE,
1178 true, GSI_SAME_STMT);
1180 load = gimple_build_assign (name, fetch);
1183 gsi_insert_before (&gsi, load, GSI_SAME_STMT);
1184 update_stmt (load);
1185 info->arr_ref_last = load;
1188 /* Builds and initializes static arrays initialized with values gathered from
1189 the SWTCH switch statement. Also creates statements that load values from
1190 them. */
1192 static void
1193 build_arrays (gswitch *swtch, struct switch_conv_info *info)
1195 tree arr_index_type;
1196 tree tidx, sub, utype;
1197 gimple *stmt;
1198 gimple_stmt_iterator gsi;
1199 gphi_iterator gpi;
1200 int i;
1201 location_t loc = gimple_location (swtch);
1203 gsi = gsi_for_stmt (swtch);
1205 /* Make sure we do not generate arithmetics in a subrange. */
1206 utype = TREE_TYPE (info->index_expr);
1207 if (TREE_TYPE (utype))
1208 utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1);
1209 else
1210 utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
1212 arr_index_type = build_index_type (info->range_size);
1213 tidx = make_ssa_name (utype);
1214 sub = fold_build2_loc (loc, MINUS_EXPR, utype,
1215 fold_convert_loc (loc, utype, info->index_expr),
1216 fold_convert_loc (loc, utype, info->range_min));
1217 sub = force_gimple_operand_gsi (&gsi, sub,
1218 false, NULL, true, GSI_SAME_STMT);
1219 stmt = gimple_build_assign (tidx, sub);
1221 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1222 update_stmt (stmt);
1223 info->arr_ref_first = stmt;
1225 for (gpi = gsi_start_phis (info->final_bb), i = 0;
1226 !gsi_end_p (gpi); gsi_next (&gpi))
1228 gphi *phi = gpi.phi ();
1229 if (!virtual_operand_p (gimple_phi_result (phi)))
1230 build_one_array (swtch, i++, arr_index_type, phi, tidx, info);
1231 else
1233 edge e;
1234 edge_iterator ei;
1235 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
1237 if (e->dest == info->final_bb)
1238 break;
1239 if (!info->default_case_nonstandard
1240 || e->dest != info->default_bb)
1242 e = single_succ_edge (e->dest);
1243 break;
1246 gcc_assert (e && e->dest == info->final_bb);
1247 info->target_vop = PHI_ARG_DEF_FROM_EDGE (phi, e);
1252 /* Generates and appropriately inserts loads of default values at the position
1253 given by BSI. Returns the last inserted statement. */
1255 static gassign *
1256 gen_def_assigns (gimple_stmt_iterator *gsi, struct switch_conv_info *info)
1258 int i;
1259 gassign *assign = NULL;
1261 for (i = 0; i < info->phi_count; i++)
1263 tree name = copy_ssa_name (info->target_inbound_names[i]);
1264 info->target_outbound_names[i] = name;
1265 assign = gimple_build_assign (name, info->default_values[i]);
1266 gsi_insert_before (gsi, assign, GSI_SAME_STMT);
1267 update_stmt (assign);
1269 return assign;
1272 /* Deletes the unused bbs and edges that now contain the switch statement and
1273 its empty branch bbs. BBD is the now dead BB containing the original switch
1274 statement, FINAL is the last BB of the converted switch statement (in terms
1275 of succession). */
1277 static void
1278 prune_bbs (basic_block bbd, basic_block final, basic_block default_bb)
1280 edge_iterator ei;
1281 edge e;
1283 for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
1285 basic_block bb;
1286 bb = e->dest;
1287 remove_edge (e);
1288 if (bb != final && bb != default_bb)
1289 delete_basic_block (bb);
1291 delete_basic_block (bbd);
1294 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
1295 from the basic block loading values from an array and E2F from the basic
1296 block loading default values. BBF is the last switch basic block (see the
1297 bbf description in the comment below). */
1299 static void
1300 fix_phi_nodes (edge e1f, edge e2f, basic_block bbf,
1301 struct switch_conv_info *info)
1303 gphi_iterator gsi;
1304 int i;
1306 for (gsi = gsi_start_phis (bbf), i = 0;
1307 !gsi_end_p (gsi); gsi_next (&gsi))
1309 gphi *phi = gsi.phi ();
1310 tree inbound, outbound;
1311 if (virtual_operand_p (gimple_phi_result (phi)))
1312 inbound = outbound = info->target_vop;
1313 else
1315 inbound = info->target_inbound_names[i];
1316 outbound = info->target_outbound_names[i++];
1318 add_phi_arg (phi, inbound, e1f, UNKNOWN_LOCATION);
1319 if (!info->default_case_nonstandard)
1320 add_phi_arg (phi, outbound, e2f, UNKNOWN_LOCATION);
1324 /* Creates a check whether the switch expression value actually falls into the
1325 range given by all the cases. If it does not, the temporaries are loaded
1326 with default values instead. SWTCH is the switch statement being converted.
1328 bb0 is the bb with the switch statement, however, we'll end it with a
1329 condition instead.
1331 bb1 is the bb to be used when the range check went ok. It is derived from
1332 the switch BB
1334 bb2 is the bb taken when the expression evaluated outside of the range
1335 covered by the created arrays. It is populated by loads of default
1336 values.
1338 bbF is a fall through for both bb1 and bb2 and contains exactly what
1339 originally followed the switch statement.
1341 bbD contains the switch statement (in the end). It is unreachable but we
1342 still need to strip off its edges.
1345 static void
1346 gen_inbound_check (gswitch *swtch, struct switch_conv_info *info)
1348 tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION);
1349 tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
1350 tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION);
1351 glabel *label1, *label2, *label3;
1352 tree utype, tidx;
1353 tree bound;
1355 gcond *cond_stmt;
1357 gassign *last_assign = NULL;
1358 gimple_stmt_iterator gsi;
1359 basic_block bb0, bb1, bb2, bbf, bbd;
1360 edge e01 = NULL, e02, e21, e1d, e1f, e2f;
1361 location_t loc = gimple_location (swtch);
1363 gcc_assert (info->default_values);
1365 bb0 = gimple_bb (swtch);
1367 tidx = gimple_assign_lhs (info->arr_ref_first);
1368 utype = TREE_TYPE (tidx);
1370 /* (end of) block 0 */
1371 gsi = gsi_for_stmt (info->arr_ref_first);
1372 gsi_next (&gsi);
1374 bound = fold_convert_loc (loc, utype, info->range_size);
1375 cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
1376 gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1377 update_stmt (cond_stmt);
1379 /* block 2 */
1380 if (!info->default_case_nonstandard)
1382 label2 = gimple_build_label (label_decl2);
1383 gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
1384 last_assign = gen_def_assigns (&gsi, info);
1387 /* block 1 */
1388 label1 = gimple_build_label (label_decl1);
1389 gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
1391 /* block F */
1392 gsi = gsi_start_bb (info->final_bb);
1393 label3 = gimple_build_label (label_decl3);
1394 gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
1396 /* cfg fix */
1397 e02 = split_block (bb0, cond_stmt);
1398 bb2 = e02->dest;
1400 if (info->default_case_nonstandard)
1402 bb1 = bb2;
1403 bb2 = info->default_bb;
1404 e01 = e02;
1405 e01->flags = EDGE_TRUE_VALUE;
1406 e02 = make_edge (bb0, bb2, EDGE_FALSE_VALUE);
1407 edge e_default = find_edge (bb1, bb2);
1408 for (gphi_iterator gsi = gsi_start_phis (bb2);
1409 !gsi_end_p (gsi); gsi_next (&gsi))
1411 gphi *phi = gsi.phi ();
1412 tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e_default);
1413 add_phi_arg (phi, arg, e02,
1414 gimple_phi_arg_location_from_edge (phi, e_default));
1416 /* Partially fix the dominator tree, if it is available. */
1417 if (dom_info_available_p (CDI_DOMINATORS))
1418 redirect_immediate_dominators (CDI_DOMINATORS, bb1, bb0);
1420 else
1422 e21 = split_block (bb2, last_assign);
1423 bb1 = e21->dest;
1424 remove_edge (e21);
1427 e1d = split_block (bb1, info->arr_ref_last);
1428 bbd = e1d->dest;
1429 remove_edge (e1d);
1431 /* flags and profiles of the edge for in-range values */
1432 if (!info->default_case_nonstandard)
1433 e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
1434 e01->probability = info->default_prob.invert ();
1436 /* flags and profiles of the edge taking care of out-of-range values */
1437 e02->flags &= ~EDGE_FALLTHRU;
1438 e02->flags |= EDGE_FALSE_VALUE;
1439 e02->probability = info->default_prob;
1441 bbf = info->final_bb;
1443 e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
1444 e1f->probability = profile_probability::always ();
1446 if (info->default_case_nonstandard)
1447 e2f = NULL;
1448 else
1450 e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
1451 e2f->probability = profile_probability::always ();
1454 /* frequencies of the new BBs */
1455 bb1->count = e01->count ();
1456 bb2->count = e02->count ();
1457 if (!info->default_case_nonstandard)
1458 bbf->count = e1f->count () + e2f->count ();
1460 /* Tidy blocks that have become unreachable. */
1461 prune_bbs (bbd, info->final_bb,
1462 info->default_case_nonstandard ? info->default_bb : NULL);
1464 /* Fixup the PHI nodes in bbF. */
1465 fix_phi_nodes (e1f, e2f, bbf, info);
1467 /* Fix the dominator tree, if it is available. */
1468 if (dom_info_available_p (CDI_DOMINATORS))
1470 vec<basic_block> bbs_to_fix_dom;
1472 set_immediate_dominator (CDI_DOMINATORS, bb1, bb0);
1473 if (!info->default_case_nonstandard)
1474 set_immediate_dominator (CDI_DOMINATORS, bb2, bb0);
1475 if (! get_immediate_dominator (CDI_DOMINATORS, bbf))
1476 /* If bbD was the immediate dominator ... */
1477 set_immediate_dominator (CDI_DOMINATORS, bbf, bb0);
1479 bbs_to_fix_dom.create (3 + (bb2 != bbf));
1480 bbs_to_fix_dom.quick_push (bb0);
1481 bbs_to_fix_dom.quick_push (bb1);
1482 if (bb2 != bbf)
1483 bbs_to_fix_dom.quick_push (bb2);
1484 bbs_to_fix_dom.quick_push (bbf);
1486 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
1487 bbs_to_fix_dom.release ();
1491 /* The following function is invoked on every switch statement (the current one
1492 is given in SWTCH) and runs the individual phases of switch conversion on it
1493 one after another until one fails or the conversion is completed.
1494 Returns NULL on success, or a pointer to a string with the reason why the
1495 conversion failed. */
1497 static const char *
1498 process_switch (gswitch *swtch)
1500 struct switch_conv_info info;
1502 /* Group case labels so that we get the right results from the heuristics
1503 that decide on the code generation approach for this switch. */
1504 cfg_altered |= group_case_labels_stmt (swtch);
1506 /* If this switch is now a degenerate case with only a default label,
1507 there is nothing left for us to do. */
1508 if (gimple_switch_num_labels (swtch) < 2)
1509 return "switch is a degenerate case";
1511 collect_switch_conv_info (swtch, &info);
1513 /* No error markers should reach here (they should be filtered out
1514 during gimplification). */
1515 gcc_checking_assert (TREE_TYPE (info.index_expr) != error_mark_node);
1517 /* A switch on a constant should have been optimized in tree-cfg-cleanup. */
1518 gcc_checking_assert (! TREE_CONSTANT (info.index_expr));
1520 if (info.uniq <= MAX_CASE_BIT_TESTS)
1522 if (expand_switch_using_bit_tests_p (info.range_size,
1523 info.uniq, info.count,
1524 optimize_bb_for_speed_p
1525 (gimple_bb (swtch))))
1527 if (dump_file)
1528 fputs (" expanding as bit test is preferable\n", dump_file);
1529 emit_case_bit_tests (swtch, info.index_expr, info.range_min,
1530 info.range_size, info.range_max);
1531 loops_state_set (LOOPS_NEED_FIXUP);
1532 return NULL;
1535 if (info.uniq <= 2)
1536 /* This will be expanded as a decision tree in stmt.c:expand_case. */
1537 return " expanding as jumps is preferable";
1540 /* If there is no common successor, we cannot do the transformation. */
1541 if (! info.final_bb)
1542 return "no common successor to all case label target blocks found";
1544 /* Check the case label values are within reasonable range: */
1545 if (!check_range (&info))
1547 gcc_assert (info.reason);
1548 return info.reason;
1551 /* For all the cases, see whether they are empty, the assignments they
1552 represent constant and so on... */
1553 if (! check_all_empty_except_final (&info))
1555 gcc_assert (info.reason);
1556 return info.reason;
1558 if (!check_final_bb (swtch, &info))
1560 gcc_assert (info.reason);
1561 return info.reason;
1564 /* At this point all checks have passed and we can proceed with the
1565 transformation. */
1567 create_temp_arrays (&info);
1568 gather_default_values (info.default_case_nonstandard
1569 ? gimple_switch_label (swtch, 1)
1570 : gimple_switch_default_label (swtch), &info);
1571 if (info.phi_count)
1572 build_constructors (swtch, &info);
1574 build_arrays (swtch, &info); /* Build the static arrays and assignments. */
1575 gen_inbound_check (swtch, &info); /* Build the bounds check. */
1577 /* Cleanup: */
1578 free_temp_arrays (&info);
1579 return NULL;
1582 /* The main function of the pass scans statements for switches and invokes
1583 process_switch on them. */
1585 namespace {
1587 const pass_data pass_data_convert_switch =
1589 GIMPLE_PASS, /* type */
1590 "switchconv", /* name */
1591 OPTGROUP_NONE, /* optinfo_flags */
1592 TV_TREE_SWITCH_CONVERSION, /* tv_id */
1593 ( PROP_cfg | PROP_ssa ), /* properties_required */
1594 0, /* properties_provided */
1595 0, /* properties_destroyed */
1596 0, /* todo_flags_start */
1597 TODO_update_ssa, /* todo_flags_finish */
1600 class pass_convert_switch : public gimple_opt_pass
1602 public:
1603 pass_convert_switch (gcc::context *ctxt)
1604 : gimple_opt_pass (pass_data_convert_switch, ctxt)
1607 /* opt_pass methods: */
1608 virtual bool gate (function *) { return flag_tree_switch_conversion != 0; }
1609 virtual unsigned int execute (function *);
1611 }; // class pass_convert_switch
1613 unsigned int
1614 pass_convert_switch::execute (function *fun)
1616 basic_block bb;
1618 cfg_altered = false;
1619 FOR_EACH_BB_FN (bb, fun)
1621 const char *failure_reason;
1622 gimple *stmt = last_stmt (bb);
1623 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
1625 if (dump_file)
1627 expanded_location loc = expand_location (gimple_location (stmt));
1629 fprintf (dump_file, "beginning to process the following "
1630 "SWITCH statement (%s:%d) : ------- \n",
1631 loc.file, loc.line);
1632 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1633 putc ('\n', dump_file);
1636 failure_reason = process_switch (as_a <gswitch *> (stmt));
1637 if (! failure_reason)
1639 cfg_altered = true;
1640 if (dump_file)
1642 fputs ("Switch converted\n", dump_file);
1643 fputs ("--------------------------------\n", dump_file);
1646 /* Make no effort to update the post-dominator tree. It is actually not
1647 that hard for the transformations we have performed, but it is not
1648 supported by iterate_fix_dominators. */
1649 free_dominance_info (CDI_POST_DOMINATORS);
1651 else
1653 if (dump_file)
1655 fputs ("Bailing out - ", dump_file);
1656 fputs (failure_reason, dump_file);
1657 fputs ("\n--------------------------------\n", dump_file);
1663 return cfg_altered ? TODO_cleanup_cfg : 0;
1666 } // anon namespace
1668 gimple_opt_pass *
1669 make_pass_convert_switch (gcc::context *ctxt)
1671 return new pass_convert_switch (ctxt);
1674 struct case_node
1676 case_node *left; /* Left son in binary tree. */
1677 case_node *right; /* Right son in binary tree;
1678 also node chain. */
1679 case_node *parent; /* Parent of node in binary tree. */
1680 tree low; /* Lowest index value for this label. */
1681 tree high; /* Highest index value for this label. */
1682 basic_block case_bb; /* Label to jump to when node matches. */
1683 tree case_label; /* Label to jump to when node matches. */
1684 profile_probability prob; /* Probability of taking this case. */
1685 profile_probability subtree_prob; /* Probability of reaching subtree
1686 rooted at this node. */
1689 typedef case_node *case_node_ptr;
1691 static basic_block emit_case_nodes (basic_block, tree, case_node_ptr,
1692 basic_block, tree, profile_probability,
1693 tree, hash_map<tree, tree> *);
1694 static bool node_has_low_bound (case_node_ptr, tree);
1695 static bool node_has_high_bound (case_node_ptr, tree);
1696 static bool node_is_bounded (case_node_ptr, tree);
1698 /* Return the smallest number of different values for which it is best to use a
1699 jump-table instead of a tree of conditional branches. */
1701 static unsigned int
1702 case_values_threshold (void)
1704 unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
1706 if (threshold == 0)
1707 threshold = targetm.case_values_threshold ();
1709 return threshold;
1712 /* Reset the aux field of all outgoing edges of basic block BB. */
1714 static inline void
1715 reset_out_edges_aux (basic_block bb)
1717 edge e;
1718 edge_iterator ei;
1719 FOR_EACH_EDGE (e, ei, bb->succs)
1720 e->aux = (void *) 0;
1723 /* Compute the number of case labels that correspond to each outgoing edge of
1724 STMT. Record this information in the aux field of the edge. */
1726 static inline void
1727 compute_cases_per_edge (gswitch *stmt)
1729 basic_block bb = gimple_bb (stmt);
1730 reset_out_edges_aux (bb);
1731 int ncases = gimple_switch_num_labels (stmt);
1732 for (int i = ncases - 1; i >= 1; --i)
1734 tree elt = gimple_switch_label (stmt, i);
1735 tree lab = CASE_LABEL (elt);
1736 basic_block case_bb = label_to_block_fn (cfun, lab);
1737 edge case_edge = find_edge (bb, case_bb);
1738 case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + 1);
1742 /* Do the insertion of a case label into case_list. The labels are
1743 fed to us in descending order from the sorted vector of case labels used
1744 in the tree part of the middle end. So the list we construct is
1745 sorted in ascending order.
1747 LABEL is the case label to be inserted. LOW and HIGH are the bounds
1748 against which the index is compared to jump to LABEL and PROB is the
1749 estimated probability LABEL is reached from the switch statement. */
1751 static case_node *
1752 add_case_node (case_node *head, tree low, tree high, basic_block case_bb,
1753 tree case_label, profile_probability prob,
1754 object_allocator<case_node> &case_node_pool)
1756 case_node *r;
1758 gcc_checking_assert (low);
1759 gcc_checking_assert (high && (TREE_TYPE (low) == TREE_TYPE (high)));
1761 /* Add this label to the chain. */
1762 r = case_node_pool.allocate ();
1763 r->low = low;
1764 r->high = high;
1765 r->case_bb = case_bb;
1766 r->case_label = case_label;
1767 r->parent = r->left = NULL;
1768 r->prob = prob;
1769 r->subtree_prob = prob;
1770 r->right = head;
1771 return r;
1774 /* Dump ROOT, a list or tree of case nodes, to file. */
1776 static void
1777 dump_case_nodes (FILE *f, case_node *root, int indent_step, int indent_level)
1779 if (root == 0)
1780 return;
1781 indent_level++;
1783 dump_case_nodes (f, root->left, indent_step, indent_level);
1785 fputs (";; ", f);
1786 fprintf (f, "%*s", indent_step * indent_level, "");
1787 print_dec (wi::to_wide (root->low), f, TYPE_SIGN (TREE_TYPE (root->low)));
1788 if (!tree_int_cst_equal (root->low, root->high))
1790 fprintf (f, " ... ");
1791 print_dec (wi::to_wide (root->high), f,
1792 TYPE_SIGN (TREE_TYPE (root->high)));
1794 fputs ("\n", f);
1796 dump_case_nodes (f, root->right, indent_step, indent_level);
1799 /* Take an ordered list of case nodes
1800 and transform them into a near optimal binary tree,
1801 on the assumption that any target code selection value is as
1802 likely as any other.
1804 The transformation is performed by splitting the ordered
1805 list into two equal sections plus a pivot. The parts are
1806 then attached to the pivot as left and right branches. Each
1807 branch is then transformed recursively. */
1809 static void
1810 balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
1812 case_node_ptr np;
1814 np = *head;
1815 if (np)
1817 int i = 0;
1818 int ranges = 0;
1819 case_node_ptr *npp;
1820 case_node_ptr left;
1822 /* Count the number of entries on branch. Also count the ranges. */
1824 while (np)
1826 if (!tree_int_cst_equal (np->low, np->high))
1827 ranges++;
1829 i++;
1830 np = np->right;
1833 if (i > 2)
1835 /* Split this list if it is long enough for that to help. */
1836 npp = head;
1837 left = *npp;
1839 /* If there are just three nodes, split at the middle one. */
1840 if (i == 3)
1841 npp = &(*npp)->right;
1842 else
1844 /* Find the place in the list that bisects the list's total cost,
1845 where ranges count as 2.
1846 Here I gets half the total cost. */
1847 i = (i + ranges + 1) / 2;
1848 while (1)
1850 /* Skip nodes while their cost does not reach that amount. */
1851 if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
1852 i--;
1853 i--;
1854 if (i <= 0)
1855 break;
1856 npp = &(*npp)->right;
1859 *head = np = *npp;
1860 *npp = 0;
1861 np->parent = parent;
1862 np->left = left;
1864 /* Optimize each of the two split parts. */
1865 balance_case_nodes (&np->left, np);
1866 balance_case_nodes (&np->right, np);
1867 np->subtree_prob = np->prob;
1868 np->subtree_prob += np->left->subtree_prob;
1869 np->subtree_prob += np->right->subtree_prob;
1871 else
1873 /* Else leave this branch as one level,
1874 but fill in `parent' fields. */
1875 np = *head;
1876 np->parent = parent;
1877 np->subtree_prob = np->prob;
1878 for (; np->right; np = np->right)
1880 np->right->parent = np;
1881 (*head)->subtree_prob += np->right->subtree_prob;
1887 /* Return true if a switch should be expanded as a decision tree.
1888 RANGE is the difference between highest and lowest case.
1889 UNIQ is number of unique case node targets, not counting the default case.
1890 COUNT is the number of comparisons needed, not counting the default case. */
1892 static bool
1893 expand_switch_as_decision_tree_p (tree range,
1894 unsigned int uniq ATTRIBUTE_UNUSED,
1895 unsigned int count)
1897 int max_ratio;
1899 /* If neither casesi or tablejump is available, or flag_jump_tables
1900 over-ruled us, we really have no choice. */
1901 if (!targetm.have_casesi () && !targetm.have_tablejump ())
1902 return true;
1903 if (!flag_jump_tables)
1904 return true;
1905 #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
1906 if (flag_pic)
1907 return true;
1908 #endif
1910 /* If the switch is relatively small such that the cost of one
1911 indirect jump on the target are higher than the cost of a
1912 decision tree, go with the decision tree.
1914 If range of values is much bigger than number of values,
1915 or if it is too large to represent in a HOST_WIDE_INT,
1916 make a sequence of conditional branches instead of a dispatch.
1918 The definition of "much bigger" depends on whether we are
1919 optimizing for size or for speed. If the former, the maximum
1920 ratio range/count = 3, because this was found to be the optimal
1921 ratio for size on i686-pc-linux-gnu, see PR11823. The ratio
1922 10 is much older, and was probably selected after an extensive
1923 benchmarking investigation on numerous platforms. Or maybe it
1924 just made sense to someone at some point in the history of GCC,
1925 who knows... */
1926 max_ratio = optimize_insn_for_size_p () ? 3 : 10;
1927 if (count < case_values_threshold () || !tree_fits_uhwi_p (range)
1928 || compare_tree_int (range, max_ratio * count) > 0)
1929 return true;
1931 return false;
1934 static void
1935 fix_phi_operands_for_edge (edge e, hash_map<tree, tree> *phi_mapping)
1937 basic_block bb = e->dest;
1938 gphi_iterator gsi;
1939 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1941 gphi *phi = gsi.phi ();
1943 tree *definition = phi_mapping->get (gimple_phi_result (phi));
1944 if (definition)
1945 add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION);
1950 /* Add an unconditional jump to CASE_BB that happens in basic block BB. */
1952 static void
1953 emit_jump (basic_block bb, basic_block case_bb,
1954 hash_map<tree, tree> *phi_mapping)
1956 edge e = single_succ_edge (bb);
1957 redirect_edge_succ (e, case_bb);
1958 fix_phi_operands_for_edge (e, phi_mapping);
1961 /* Generate a decision tree, switching on INDEX_EXPR and jumping to
1962 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
1963 DEFAULT_PROB is the estimated probability that it jumps to
1964 DEFAULT_LABEL.
1966 We generate a binary decision tree to select the appropriate target
1967 code. */
1969 static void
1970 emit_case_decision_tree (gswitch *s, tree index_expr, tree index_type,
1971 case_node_ptr case_list, basic_block default_bb,
1972 tree default_label, profile_probability default_prob,
1973 hash_map<tree, tree> *phi_mapping)
1975 balance_case_nodes (&case_list, NULL);
1977 if (dump_file)
1978 dump_function_to_file (current_function_decl, dump_file, dump_flags);
1979 if (dump_file && (dump_flags & TDF_DETAILS))
1981 int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
1982 fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
1983 dump_case_nodes (dump_file, case_list, indent_step, 0);
1986 basic_block bb = gimple_bb (s);
1987 gimple_stmt_iterator gsi = gsi_last_bb (bb);
1988 edge e;
1989 if (gsi_end_p (gsi))
1990 e = split_block_after_labels (bb);
1991 else
1993 gsi_prev (&gsi);
1994 e = split_block (bb, gsi_stmt (gsi));
1996 bb = split_edge (e);
1998 bb = emit_case_nodes (bb, index_expr, case_list, default_bb, default_label,
1999 default_prob, index_type, phi_mapping);
2001 if (bb)
2002 emit_jump (bb, default_bb, phi_mapping);
2004 /* Remove all edges and do just an edge that will reach default_bb. */
2005 gsi = gsi_last_bb (gimple_bb (s));
2006 gsi_remove (&gsi, true);
2009 static void
2010 record_phi_operand_mapping (const vec<basic_block> bbs, basic_block switch_bb,
2011 hash_map <tree, tree> *map)
2013 /* Record all PHI nodes that have to be fixed after conversion. */
2014 for (unsigned i = 0; i < bbs.length (); i++)
2016 basic_block bb = bbs[i];
2018 gphi_iterator gsi;
2019 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2021 gphi *phi = gsi.phi ();
2023 for (unsigned i = 0; i < gimple_phi_num_args (phi); i++)
2025 basic_block phi_src_bb = gimple_phi_arg_edge (phi, i)->src;
2026 if (phi_src_bb == switch_bb)
2028 tree def = gimple_phi_arg_def (phi, i);
2029 tree result = gimple_phi_result (phi);
2030 map->put (result, def);
2031 break;
2038 /* Attempt to expand gimple switch STMT to a decision tree. */
2040 static bool
2041 try_switch_expansion (gswitch *stmt)
2043 tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
2044 basic_block default_bb;
2045 unsigned int count, uniq;
2046 int i;
2047 int ncases = gimple_switch_num_labels (stmt);
2048 tree index_expr = gimple_switch_index (stmt);
2049 tree index_type = TREE_TYPE (index_expr);
2050 tree elt;
2051 basic_block bb = gimple_bb (stmt);
2053 hash_map<tree, tree> phi_mapping;
2054 auto_vec<basic_block> case_bbs;
2056 /* A list of case labels; it is first built as a list and it may then
2057 be rearranged into a nearly balanced binary tree. */
2058 case_node *case_list = 0;
2060 /* A pool for case nodes. */
2061 object_allocator<case_node> case_node_pool ("struct case_node pool");
2063 /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
2064 expressions being INTEGER_CST. */
2065 gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
2067 if (ncases == 1)
2068 return false;
2070 /* Find the default case target label. */
2071 tree default_label = CASE_LABEL (gimple_switch_default_label (stmt));
2072 default_bb = label_to_block_fn (cfun, default_label);
2073 edge default_edge = find_edge (bb, default_bb);
2074 profile_probability default_prob = default_edge->probability;
2075 case_bbs.safe_push (default_bb);
2077 /* Get upper and lower bounds of case values. */
2078 elt = gimple_switch_label (stmt, 1);
2079 minval = fold_convert (index_type, CASE_LOW (elt));
2080 elt = gimple_switch_label (stmt, ncases - 1);
2081 if (CASE_HIGH (elt))
2082 maxval = fold_convert (index_type, CASE_HIGH (elt));
2083 else
2084 maxval = fold_convert (index_type, CASE_LOW (elt));
2086 /* Compute span of values. */
2087 range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
2089 /* Listify the labels queue and gather some numbers to decide
2090 how to expand this switch. */
2091 uniq = 0;
2092 count = 0;
2093 hash_set<tree> seen_labels;
2094 compute_cases_per_edge (stmt);
2096 for (i = ncases - 1; i >= 1; --i)
2098 elt = gimple_switch_label (stmt, i);
2099 tree low = CASE_LOW (elt);
2100 gcc_assert (low);
2101 tree high = CASE_HIGH (elt);
2102 gcc_assert (!high || tree_int_cst_lt (low, high));
2103 tree lab = CASE_LABEL (elt);
2105 /* Count the elements.
2106 A range counts double, since it requires two compares. */
2107 count++;
2108 if (high)
2109 count++;
2111 /* If we have not seen this label yet, then increase the
2112 number of unique case node targets seen. */
2113 if (!seen_labels.add (lab))
2114 uniq++;
2116 /* The bounds on the case range, LOW and HIGH, have to be converted
2117 to case's index type TYPE. Note that the original type of the
2118 case index in the source code is usually "lost" during
2119 gimplification due to type promotion, but the case labels retain the
2120 original type. Make sure to drop overflow flags. */
2121 low = fold_convert (index_type, low);
2122 if (TREE_OVERFLOW (low))
2123 low = wide_int_to_tree (index_type, wi::to_wide (low));
2125 /* The canonical from of a case label in GIMPLE is that a simple case
2126 has an empty CASE_HIGH. For the casesi and tablejump expanders,
2127 the back ends want simple cases to have high == low. */
2128 if (!high)
2129 high = low;
2130 high = fold_convert (index_type, high);
2131 if (TREE_OVERFLOW (high))
2132 high = wide_int_to_tree (index_type, wi::to_wide (high));
2134 basic_block case_bb = label_to_block_fn (cfun, lab);
2135 edge case_edge = find_edge (bb, case_bb);
2136 case_list = add_case_node (
2137 case_list, low, high, case_bb, lab,
2138 case_edge->probability.apply_scale (1, (intptr_t) (case_edge->aux)),
2139 case_node_pool);
2141 case_bbs.safe_push (case_bb);
2143 reset_out_edges_aux (bb);
2144 record_phi_operand_mapping (case_bbs, bb, &phi_mapping);
2146 /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
2147 destination, such as one with a default case only.
2148 It also removes cases that are out of range for the switch
2149 type, so we should never get a zero here. */
2150 gcc_assert (count > 0);
2152 /* Decide how to expand this switch.
2153 The two options at this point are a dispatch table (casesi or
2154 tablejump) or a decision tree. */
2156 if (expand_switch_as_decision_tree_p (range, uniq, count))
2158 emit_case_decision_tree (stmt, index_expr, index_type, case_list,
2159 default_bb, default_label, default_prob,
2160 &phi_mapping);
2161 return true;
2164 return false;
2167 /* The main function of the pass scans statements for switches and invokes
2168 process_switch on them. */
2170 namespace {
2172 const pass_data pass_data_lower_switch =
2174 GIMPLE_PASS, /* type */
2175 "switchlower", /* name */
2176 OPTGROUP_NONE, /* optinfo_flags */
2177 TV_TREE_SWITCH_LOWERING, /* tv_id */
2178 ( PROP_cfg | PROP_ssa ), /* properties_required */
2179 0, /* properties_provided */
2180 0, /* properties_destroyed */
2181 0, /* todo_flags_start */
2182 TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */
2185 class pass_lower_switch : public gimple_opt_pass
2187 public:
2188 pass_lower_switch (gcc::context *ctxt)
2189 : gimple_opt_pass (pass_data_lower_switch, ctxt)
2192 /* opt_pass methods: */
2193 virtual bool gate (function *) { return true; }
2194 virtual unsigned int execute (function *);
2196 }; // class pass_lower_switch
2198 unsigned int
2199 pass_lower_switch::execute (function *fun)
2201 basic_block bb;
2202 bool expanded = false;
2204 FOR_EACH_BB_FN (bb, fun)
2206 gimple *stmt = last_stmt (bb);
2207 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
2209 if (dump_file)
2211 expanded_location loc = expand_location (gimple_location (stmt));
2213 fprintf (dump_file, "beginning to process the following "
2214 "SWITCH statement (%s:%d) : ------- \n",
2215 loc.file, loc.line);
2216 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2217 putc ('\n', dump_file);
2220 expanded |= try_switch_expansion (as_a<gswitch *> (stmt));
2224 if (expanded)
2226 free_dominance_info (CDI_DOMINATORS);
2227 free_dominance_info (CDI_POST_DOMINATORS);
2228 mark_virtual_operands_for_renaming (cfun);
2231 return 0;
2234 } // anon namespace
2236 gimple_opt_pass *
2237 make_pass_lower_switch (gcc::context *ctxt)
2239 return new pass_lower_switch (ctxt);
2242 /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE.
2243 PROB is the probability of jumping to LABEL. */
2244 static basic_block
2245 do_jump_if_equal (basic_block bb, tree op0, tree op1, basic_block label_bb,
2246 profile_probability prob, hash_map<tree, tree> *phi_mapping)
2248 gcond *cond = gimple_build_cond (EQ_EXPR, op0, op1, NULL_TREE, NULL_TREE);
2249 gimple_stmt_iterator gsi = gsi_last_bb (bb);
2250 gsi_insert_before (&gsi, cond, GSI_SAME_STMT);
2252 gcc_assert (single_succ_p (bb));
2254 /* Make a new basic block where false branch will take place. */
2255 edge false_edge = split_block (bb, cond);
2256 false_edge->flags = EDGE_FALSE_VALUE;
2257 false_edge->probability = prob.invert ();
2259 edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
2260 fix_phi_operands_for_edge (true_edge, phi_mapping);
2261 true_edge->probability = prob;
2263 return false_edge->dest;
2266 /* Generate code to compare X with Y so that the condition codes are
2267 set and to jump to LABEL if the condition is true. If X is a
2268 constant and Y is not a constant, then the comparison is swapped to
2269 ensure that the comparison RTL has the canonical form.
2271 UNSIGNEDP nonzero says that X and Y are unsigned; this matters if they
2272 need to be widened. UNSIGNEDP is also used to select the proper
2273 branch condition code.
2275 If X and Y have mode BLKmode, then SIZE specifies the size of both X and Y.
2277 MODE is the mode of the inputs (in case they are const_int).
2279 COMPARISON is the rtl operator to compare with (EQ, NE, GT, etc.).
2280 It will be potentially converted into an unsigned variant based on
2281 UNSIGNEDP to select a proper jump instruction.
2283 PROB is the probability of jumping to LABEL. */
2285 static basic_block
2286 emit_cmp_and_jump_insns (basic_block bb, tree op0, tree op1,
2287 tree_code comparison, basic_block label_bb,
2288 profile_probability prob,
2289 hash_map<tree, tree> *phi_mapping)
2291 gcond *cond = gimple_build_cond (comparison, op0, op1, NULL_TREE, NULL_TREE);
2292 gimple_stmt_iterator gsi = gsi_last_bb (bb);
2293 gsi_insert_after (&gsi, cond, GSI_NEW_STMT);
2295 gcc_assert (single_succ_p (bb));
2297 /* Make a new basic block where false branch will take place. */
2298 edge false_edge = split_block (bb, cond);
2299 false_edge->flags = EDGE_FALSE_VALUE;
2300 false_edge->probability = prob.invert ();
2302 edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
2303 fix_phi_operands_for_edge (true_edge, phi_mapping);
2304 true_edge->probability = prob;
2306 return false_edge->dest;
2309 /* Computes the conditional probability of jumping to a target if the branch
2310 instruction is executed.
2311 TARGET_PROB is the estimated probability of jumping to a target relative
2312 to some basic block BB.
2313 BASE_PROB is the probability of reaching the branch instruction relative
2314 to the same basic block BB. */
2316 static inline profile_probability
2317 conditional_probability (profile_probability target_prob,
2318 profile_probability base_prob)
2320 return target_prob / base_prob;
2323 /* Emit step-by-step code to select a case for the value of INDEX.
2324 The thus generated decision tree follows the form of the
2325 case-node binary tree NODE, whose nodes represent test conditions.
2326 INDEX_TYPE is the type of the index of the switch.
2328 Care is taken to prune redundant tests from the decision tree
2329 by detecting any boundary conditions already checked by
2330 emitted rtx. (See node_has_high_bound, node_has_low_bound
2331 and node_is_bounded, above.)
2333 Where the test conditions can be shown to be redundant we emit
2334 an unconditional jump to the target code. As a further
2335 optimization, the subordinates of a tree node are examined to
2336 check for bounded nodes. In this case conditional and/or
2337 unconditional jumps as a result of the boundary check for the
2338 current node are arranged to target the subordinates associated
2339 code for out of bound conditions on the current node.
2341 We can assume that when control reaches the code generated here,
2342 the index value has already been compared with the parents
2343 of this node, and determined to be on the same side of each parent
2344 as this node is. Thus, if this node tests for the value 51,
2345 and a parent tested for 52, we don't need to consider
2346 the possibility of a value greater than 51. If another parent
2347 tests for the value 50, then this node need not test anything. */
2349 static basic_block
2350 emit_case_nodes (basic_block bb, tree index, case_node_ptr node,
2351 basic_block default_bb, tree default_label,
2352 profile_probability default_prob, tree index_type,
2353 hash_map<tree, tree> *phi_mapping)
2355 /* If INDEX has an unsigned type, we must make unsigned branches. */
2356 profile_probability probability;
2357 profile_probability prob = node->prob, subtree_prob = node->subtree_prob;
2359 /* See if our parents have already tested everything for us.
2360 If they have, emit an unconditional jump for this node. */
2361 if (node_is_bounded (node, index_type))
2363 emit_jump (bb, node->case_bb, phi_mapping);
2364 return NULL;
2367 else if (tree_int_cst_equal (node->low, node->high))
2369 probability = conditional_probability (prob, subtree_prob + default_prob);
2370 /* Node is single valued. First see if the index expression matches
2371 this node and then check our children, if any. */
2372 bb = do_jump_if_equal (bb, index, node->low, node->case_bb, probability,
2373 phi_mapping);
2374 /* Since this case is taken at this point, reduce its weight from
2375 subtree_weight. */
2376 subtree_prob -= prob;
2377 if (node->right != 0 && node->left != 0)
2379 /* This node has children on both sides.
2380 Dispatch to one side or the other
2381 by comparing the index value with this node's value.
2382 If one subtree is bounded, check that one first,
2383 so we can avoid real branches in the tree. */
2385 if (node_is_bounded (node->right, index_type))
2387 probability
2388 = conditional_probability (node->right->prob,
2389 subtree_prob + default_prob);
2390 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
2391 node->right->case_bb, probability,
2392 phi_mapping);
2393 bb = emit_case_nodes (bb, index, node->left, default_bb,
2394 default_label, default_prob, index_type,
2395 phi_mapping);
2398 else if (node_is_bounded (node->left, index_type))
2400 probability
2401 = conditional_probability (node->left->prob,
2402 subtree_prob + default_prob);
2403 bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR,
2404 node->left->case_bb, probability,
2405 phi_mapping);
2406 bb = emit_case_nodes (bb, index, node->right, default_bb,
2407 default_label, default_prob, index_type,
2408 phi_mapping);
2411 /* If both children are single-valued cases with no
2412 children, finish up all the work. This way, we can save
2413 one ordered comparison. */
2414 else if (tree_int_cst_equal (node->right->low, node->right->high)
2415 && node->right->left == 0 && node->right->right == 0
2416 && tree_int_cst_equal (node->left->low, node->left->high)
2417 && node->left->left == 0 && node->left->right == 0)
2419 /* Neither node is bounded. First distinguish the two sides;
2420 then emit the code for one side at a time. */
2422 /* See if the value matches what the right hand side
2423 wants. */
2424 probability
2425 = conditional_probability (node->right->prob,
2426 subtree_prob + default_prob);
2427 bb = do_jump_if_equal (bb, index, node->right->low,
2428 node->right->case_bb, probability,
2429 phi_mapping);
2431 /* See if the value matches what the left hand side
2432 wants. */
2433 probability
2434 = conditional_probability (node->left->prob,
2435 subtree_prob + default_prob);
2436 bb = do_jump_if_equal (bb, index, node->left->low,
2437 node->left->case_bb, probability,
2438 phi_mapping);
2441 else
2443 /* Neither node is bounded. First distinguish the two sides;
2444 then emit the code for one side at a time. */
2446 basic_block test_bb = split_edge (single_succ_edge (bb));
2447 redirect_edge_succ (single_pred_edge (test_bb),
2448 single_succ_edge (bb)->dest);
2450 /* The default label could be reached either through the right
2451 subtree or the left subtree. Divide the probability
2452 equally. */
2453 probability
2454 = conditional_probability (node->right->subtree_prob
2455 + default_prob.apply_scale (1, 2),
2456 subtree_prob + default_prob);
2457 /* See if the value is on the right. */
2458 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
2459 test_bb, probability, phi_mapping);
2460 default_prob = default_prob.apply_scale (1, 2);
2462 /* Value must be on the left.
2463 Handle the left-hand subtree. */
2464 bb = emit_case_nodes (bb, index, node->left, default_bb,
2465 default_label, default_prob, index_type,
2466 phi_mapping);
2467 /* If left-hand subtree does nothing,
2468 go to default. */
2470 if (bb && default_bb)
2471 emit_jump (bb, default_bb, phi_mapping);
2473 /* Code branches here for the right-hand subtree. */
2474 bb = emit_case_nodes (test_bb, index, node->right, default_bb,
2475 default_label, default_prob, index_type,
2476 phi_mapping);
2479 else if (node->right != 0 && node->left == 0)
2481 /* Here we have a right child but no left so we issue a conditional
2482 branch to default and process the right child.
2484 Omit the conditional branch to default if the right child
2485 does not have any children and is single valued; it would
2486 cost too much space to save so little time. */
2488 if (node->right->right || node->right->left
2489 || !tree_int_cst_equal (node->right->low, node->right->high))
2491 if (!node_has_low_bound (node, index_type))
2493 probability
2494 = conditional_probability (default_prob.apply_scale (1, 2),
2495 subtree_prob + default_prob);
2496 bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR,
2497 default_bb, probability,
2498 phi_mapping);
2499 default_prob = default_prob.apply_scale (1, 2);
2502 bb = emit_case_nodes (bb, index, node->right, default_bb,
2503 default_label, default_prob, index_type,
2504 phi_mapping);
2506 else
2508 probability
2509 = conditional_probability (node->right->subtree_prob,
2510 subtree_prob + default_prob);
2511 /* We cannot process node->right normally
2512 since we haven't ruled out the numbers less than
2513 this node's value. So handle node->right explicitly. */
2514 bb = do_jump_if_equal (bb, index, node->right->low,
2515 node->right->case_bb, probability,
2516 phi_mapping);
2520 else if (node->right == 0 && node->left != 0)
2522 /* Just one subtree, on the left. */
2523 if (node->left->left || node->left->right
2524 || !tree_int_cst_equal (node->left->low, node->left->high))
2526 if (!node_has_high_bound (node, index_type))
2528 probability
2529 = conditional_probability (default_prob.apply_scale (1, 2),
2530 subtree_prob + default_prob);
2531 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
2532 default_bb, probability,
2533 phi_mapping);
2534 default_prob = default_prob.apply_scale (1, 2);
2537 bb = emit_case_nodes (bb, index, node->left, default_bb,
2538 default_label, default_prob, index_type,
2539 phi_mapping);
2541 else
2543 probability
2544 = conditional_probability (node->left->subtree_prob,
2545 subtree_prob + default_prob);
2546 /* We cannot process node->left normally
2547 since we haven't ruled out the numbers less than
2548 this node's value. So handle node->left explicitly. */
2549 do_jump_if_equal (bb, index, node->left->low, node->left->case_bb,
2550 probability, phi_mapping);
2554 else
2556 /* Node is a range. These cases are very similar to those for a single
2557 value, except that we do not start by testing whether this node
2558 is the one to branch to. */
2560 if (node->right != 0 && node->left != 0)
2562 /* Node has subtrees on both sides.
2563 If the right-hand subtree is bounded,
2564 test for it first, since we can go straight there.
2565 Otherwise, we need to make a branch in the control structure,
2566 then handle the two subtrees. */
2567 basic_block test_bb = NULL;
2569 if (node_is_bounded (node->right, index_type))
2571 /* Right hand node is fully bounded so we can eliminate any
2572 testing and branch directly to the target code. */
2573 probability
2574 = conditional_probability (node->right->subtree_prob,
2575 subtree_prob + default_prob);
2576 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
2577 node->right->case_bb, probability,
2578 phi_mapping);
2580 else
2582 /* Right hand node requires testing.
2583 Branch to a label where we will handle it later. */
2585 test_bb = split_edge (single_succ_edge (bb));
2586 redirect_edge_succ (single_pred_edge (test_bb),
2587 single_succ_edge (bb)->dest);
2589 probability
2590 = conditional_probability (node->right->subtree_prob
2591 + default_prob.apply_scale (1, 2),
2592 subtree_prob + default_prob);
2593 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
2594 test_bb, probability, phi_mapping);
2595 default_prob = default_prob.apply_scale (1, 2);
2598 /* Value belongs to this node or to the left-hand subtree. */
2600 probability
2601 = conditional_probability (prob, subtree_prob + default_prob);
2602 bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR,
2603 node->case_bb, probability,
2604 phi_mapping);
2606 /* Handle the left-hand subtree. */
2607 bb = emit_case_nodes (bb, index, node->left, default_bb,
2608 default_label, default_prob, index_type,
2609 phi_mapping);
2611 /* If right node had to be handled later, do that now. */
2612 if (test_bb)
2614 /* If the left-hand subtree fell through,
2615 don't let it fall into the right-hand subtree. */
2616 if (bb && default_bb)
2617 emit_jump (bb, default_bb, phi_mapping);
2619 bb = emit_case_nodes (test_bb, index, node->right, default_bb,
2620 default_label, default_prob, index_type,
2621 phi_mapping);
2625 else if (node->right != 0 && node->left == 0)
2627 /* Deal with values to the left of this node,
2628 if they are possible. */
2629 if (!node_has_low_bound (node, index_type))
2631 probability
2632 = conditional_probability (default_prob.apply_scale (1, 2),
2633 subtree_prob + default_prob);
2634 bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR,
2635 default_bb, probability,
2636 phi_mapping);
2637 default_prob = default_prob.apply_scale (1, 2);
2640 /* Value belongs to this node or to the right-hand subtree. */
2642 probability
2643 = conditional_probability (prob, subtree_prob + default_prob);
2644 bb = emit_cmp_and_jump_insns (bb, index, node->high, LE_EXPR,
2645 node->case_bb, probability,
2646 phi_mapping);
2648 bb = emit_case_nodes (bb, index, node->right, default_bb,
2649 default_label, default_prob, index_type,
2650 phi_mapping);
2653 else if (node->right == 0 && node->left != 0)
2655 /* Deal with values to the right of this node,
2656 if they are possible. */
2657 if (!node_has_high_bound (node, index_type))
2659 probability
2660 = conditional_probability (default_prob.apply_scale (1, 2),
2661 subtree_prob + default_prob);
2662 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
2663 default_bb, probability,
2664 phi_mapping);
2665 default_prob = default_prob.apply_scale (1, 2);
2668 /* Value belongs to this node or to the left-hand subtree. */
2670 probability
2671 = conditional_probability (prob, subtree_prob + default_prob);
2672 bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR,
2673 node->case_bb, probability,
2674 phi_mapping);
2676 bb = emit_case_nodes (bb, index, node->left, default_bb,
2677 default_label, default_prob, index_type,
2678 phi_mapping);
2681 else
2683 /* Node has no children so we check low and high bounds to remove
2684 redundant tests. Only one of the bounds can exist,
2685 since otherwise this node is bounded--a case tested already. */
2686 bool high_bound = node_has_high_bound (node, index_type);
2687 bool low_bound = node_has_low_bound (node, index_type);
2689 if (!high_bound && low_bound)
2691 probability
2692 = conditional_probability (default_prob,
2693 subtree_prob + default_prob);
2694 bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
2695 default_bb, probability,
2696 phi_mapping);
2699 else if (!low_bound && high_bound)
2701 probability
2702 = conditional_probability (default_prob,
2703 subtree_prob + default_prob);
2704 bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR,
2705 default_bb, probability,
2706 phi_mapping);
2708 else if (!low_bound && !high_bound)
2710 tree lhs, rhs;
2711 generate_range_test (bb, index, node->low, node->high,
2712 &lhs, &rhs);
2713 probability
2714 = conditional_probability (default_prob,
2715 subtree_prob + default_prob);
2716 bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR,
2717 default_bb, probability,
2718 phi_mapping);
2721 emit_jump (bb, node->case_bb, phi_mapping);
2722 return NULL;
2726 return bb;
2729 /* Search the parent sections of the case node tree
2730 to see if a test for the lower bound of NODE would be redundant.
2731 INDEX_TYPE is the type of the index expression.
2733 The instructions to generate the case decision tree are
2734 output in the same order as nodes are processed so it is
2735 known that if a parent node checks the range of the current
2736 node minus one that the current node is bounded at its lower
2737 span. Thus the test would be redundant. */
2739 static bool
2740 node_has_low_bound (case_node_ptr node, tree index_type)
2742 tree low_minus_one;
2743 case_node_ptr pnode;
2745 /* If the lower bound of this node is the lowest value in the index type,
2746 we need not test it. */
2748 if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
2749 return true;
2751 /* If this node has a left branch, the value at the left must be less
2752 than that at this node, so it cannot be bounded at the bottom and
2753 we need not bother testing any further. */
2755 if (node->left)
2756 return false;
2758 low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low), node->low,
2759 build_int_cst (TREE_TYPE (node->low), 1));
2761 /* If the subtraction above overflowed, we can't verify anything.
2762 Otherwise, look for a parent that tests our value - 1. */
2764 if (!tree_int_cst_lt (low_minus_one, node->low))
2765 return false;
2767 for (pnode = node->parent; pnode; pnode = pnode->parent)
2768 if (tree_int_cst_equal (low_minus_one, pnode->high))
2769 return true;
2771 return false;
2774 /* Search the parent sections of the case node tree
2775 to see if a test for the upper bound of NODE would be redundant.
2776 INDEX_TYPE is the type of the index expression.
2778 The instructions to generate the case decision tree are
2779 output in the same order as nodes are processed so it is
2780 known that if a parent node checks the range of the current
2781 node plus one that the current node is bounded at its upper
2782 span. Thus the test would be redundant. */
2784 static bool
2785 node_has_high_bound (case_node_ptr node, tree index_type)
2787 tree high_plus_one;
2788 case_node_ptr pnode;
2790 /* If there is no upper bound, obviously no test is needed. */
2792 if (TYPE_MAX_VALUE (index_type) == NULL)
2793 return true;
2795 /* If the upper bound of this node is the highest value in the type
2796 of the index expression, we need not test against it. */
2798 if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
2799 return true;
2801 /* If this node has a right branch, the value at the right must be greater
2802 than that at this node, so it cannot be bounded at the top and
2803 we need not bother testing any further. */
2805 if (node->right)
2806 return false;
2808 high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high), node->high,
2809 build_int_cst (TREE_TYPE (node->high), 1));
2811 /* If the addition above overflowed, we can't verify anything.
2812 Otherwise, look for a parent that tests our value + 1. */
2814 if (!tree_int_cst_lt (node->high, high_plus_one))
2815 return false;
2817 for (pnode = node->parent; pnode; pnode = pnode->parent)
2818 if (tree_int_cst_equal (high_plus_one, pnode->low))
2819 return true;
2821 return false;
2824 /* Search the parent sections of the
2825 case node tree to see if both tests for the upper and lower
2826 bounds of NODE would be redundant. */
2828 static bool
2829 node_is_bounded (case_node_ptr node, tree index_type)
2831 return (node_has_low_bound (node, index_type)
2832 && node_has_high_bound (node, index_type));