Daily bump.
[official-gcc.git] / gcc / tree-switch-conversion.c
blob6b68a161c44d9f742f8146d12ce47f71a5b93889
1 /* Lower GIMPLE_SWITCH expressions to something more efficient than
2 a jump table.
3 Copyright (C) 2006-2015 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 "tm.h"
29 #include "line-map.h"
30 #include "params.h"
31 #include "flags.h"
32 #include "hash-set.h"
33 #include "machmode.h"
34 #include "vec.h"
35 #include "double-int.h"
36 #include "input.h"
37 #include "alias.h"
38 #include "symtab.h"
39 #include "wide-int.h"
40 #include "inchash.h"
41 #include "tree.h"
42 #include "fold-const.h"
43 #include "varasm.h"
44 #include "stor-layout.h"
45 #include "predict.h"
46 #include "hard-reg-set.h"
47 #include "function.h"
48 #include "dominance.h"
49 #include "cfg.h"
50 #include "cfganal.h"
51 #include "basic-block.h"
52 #include "tree-ssa-alias.h"
53 #include "internal-fn.h"
54 #include "gimple-expr.h"
55 #include "is-a.h"
56 #include "gimple.h"
57 #include "gimplify.h"
58 #include "gimple-iterator.h"
59 #include "gimplify-me.h"
60 #include "gimple-ssa.h"
61 #include "hash-map.h"
62 #include "plugin-api.h"
63 #include "ipa-ref.h"
64 #include "cgraph.h"
65 #include "tree-cfg.h"
66 #include "tree-phinodes.h"
67 #include "stringpool.h"
68 #include "tree-ssanames.h"
69 #include "tree-pass.h"
70 #include "gimple-pretty-print.h"
71 #include "cfgloop.h"
73 /* ??? For lang_hooks.types.type_for_mode, but is there a word_mode
74 type in the GIMPLE type system that is language-independent? */
75 #include "langhooks.h"
77 /* Need to include expr.h and optabs.h for lshift_cheap_p. */
78 #include "hashtab.h"
79 #include "rtl.h"
80 #include "statistics.h"
81 #include "real.h"
82 #include "fixed-value.h"
83 #include "insn-config.h"
84 #include "expmed.h"
85 #include "dojump.h"
86 #include "explow.h"
87 #include "calls.h"
88 #include "emit-rtl.h"
89 #include "stmt.h"
90 #include "expr.h"
91 #include "insn-codes.h"
92 #include "optabs.h"
94 /* Maximum number of case bit tests.
95 FIXME: This should be derived from PARAM_CASE_VALUES_THRESHOLD and
96 targetm.case_values_threshold(), or be its own param. */
97 #define MAX_CASE_BIT_TESTS 3
99 /* Split the basic block at the statement pointed to by GSIP, and insert
100 a branch to the target basic block of E_TRUE conditional on tree
101 expression COND.
103 It is assumed that there is already an edge from the to-be-split
104 basic block to E_TRUE->dest block. This edge is removed, and the
105 profile information on the edge is re-used for the new conditional
106 jump.
108 The CFG is updated. The dominator tree will not be valid after
109 this transformation, but the immediate dominators are updated if
110 UPDATE_DOMINATORS is true.
112 Returns the newly created basic block. */
114 static basic_block
115 hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
116 tree cond, edge e_true,
117 bool update_dominators)
119 tree tmp;
120 gcond *cond_stmt;
121 edge e_false;
122 basic_block new_bb, split_bb = gsi_bb (*gsip);
123 bool dominated_e_true = false;
125 gcc_assert (e_true->src == split_bb);
127 if (update_dominators
128 && get_immediate_dominator (CDI_DOMINATORS, e_true->dest) == split_bb)
129 dominated_e_true = true;
131 tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL,
132 /*before=*/true, GSI_SAME_STMT);
133 cond_stmt = gimple_build_cond_from_tree (tmp, NULL_TREE, NULL_TREE);
134 gsi_insert_before (gsip, cond_stmt, GSI_SAME_STMT);
136 e_false = split_block (split_bb, cond_stmt);
137 new_bb = e_false->dest;
138 redirect_edge_pred (e_true, split_bb);
140 e_true->flags &= ~EDGE_FALLTHRU;
141 e_true->flags |= EDGE_TRUE_VALUE;
143 e_false->flags &= ~EDGE_FALLTHRU;
144 e_false->flags |= EDGE_FALSE_VALUE;
145 e_false->probability = REG_BR_PROB_BASE - e_true->probability;
146 e_false->count = split_bb->count - e_true->count;
147 new_bb->count = e_false->count;
149 if (update_dominators)
151 if (dominated_e_true)
152 set_immediate_dominator (CDI_DOMINATORS, e_true->dest, split_bb);
153 set_immediate_dominator (CDI_DOMINATORS, e_false->dest, split_bb);
156 return new_bb;
160 /* Return true if a switch should be expanded as a bit test.
161 RANGE is the difference between highest and lowest case.
162 UNIQ is number of unique case node targets, not counting the default case.
163 COUNT is the number of comparisons needed, not counting the default case. */
165 static bool
166 expand_switch_using_bit_tests_p (tree range,
167 unsigned int uniq,
168 unsigned int count, bool speed_p)
170 return (((uniq == 1 && count >= 3)
171 || (uniq == 2 && count >= 5)
172 || (uniq == 3 && count >= 6))
173 && lshift_cheap_p (speed_p)
174 && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0
175 && compare_tree_int (range, 0) > 0);
178 /* Implement switch statements with bit tests
180 A GIMPLE switch statement can be expanded to a short sequence of bit-wise
181 comparisons. "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)"
182 where CST and MINVAL are integer constants. This is better than a series
183 of compare-and-banch insns in some cases, e.g. we can implement:
185 if ((x==4) || (x==6) || (x==9) || (x==11))
187 as a single bit test:
189 if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11)))
191 This transformation is only applied if the number of case targets is small,
192 if CST constains at least 3 bits, and "1 << x" is cheap. The bit tests are
193 performed in "word_mode".
195 The following example shows the code the transformation generates:
197 int bar(int x)
199 switch (x)
201 case '0': case '1': case '2': case '3': case '4':
202 case '5': case '6': case '7': case '8': case '9':
203 case 'A': case 'B': case 'C': case 'D': case 'E':
204 case 'F':
205 return 1;
207 return 0;
212 bar (int x)
214 tmp1 = x - 48;
215 if (tmp1 > (70 - 48)) goto L2;
216 tmp2 = 1 << tmp1;
217 tmp3 = 0b11111100000001111111111;
218 if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2;
220 return 1;
222 return 0;
225 TODO: There are still some improvements to this transformation that could
226 be implemented:
228 * A narrower mode than word_mode could be used if that is cheaper, e.g.
229 for x86_64 where a narrower-mode shift may result in smaller code.
231 * The compounded constant could be shifted rather than the one. The
232 test would be either on the sign bit or on the least significant bit,
233 depending on the direction of the shift. On some machines, the test
234 for the branch would be free if the bit to test is already set by the
235 shift operation.
237 This transformation was contributed by Roger Sayle, see this e-mail:
238 http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html
241 /* A case_bit_test represents a set of case nodes that may be
242 selected from using a bit-wise comparison. HI and LO hold
243 the integer to be tested against, TARGET_EDGE contains the
244 edge to the basic block to jump to upon success and BITS
245 counts the number of case nodes handled by this test,
246 typically the number of bits set in HI:LO. The LABEL field
247 is used to quickly identify all cases in this set without
248 looking at label_to_block for every case label. */
250 struct case_bit_test
252 wide_int mask;
253 edge target_edge;
254 tree label;
255 int bits;
258 /* Comparison function for qsort to order bit tests by decreasing
259 probability of execution. Our best guess comes from a measured
260 profile. If the profile counts are equal, break even on the
261 number of case nodes, i.e. the node with the most cases gets
262 tested first.
264 TODO: Actually this currently runs before a profile is available.
265 Therefore the case-as-bit-tests transformation should be done
266 later in the pass pipeline, or something along the lines of
267 "Efficient and effective branch reordering using profile data"
268 (Yang et. al., 2002) should be implemented (although, how good
269 is a paper is called "Efficient and effective ..." when the
270 latter is implied by the former, but oh well...). */
272 static int
273 case_bit_test_cmp (const void *p1, const void *p2)
275 const struct case_bit_test *const d1 = (const struct case_bit_test *) p1;
276 const struct case_bit_test *const d2 = (const struct case_bit_test *) p2;
278 if (d2->target_edge->count != d1->target_edge->count)
279 return d2->target_edge->count - d1->target_edge->count;
280 if (d2->bits != d1->bits)
281 return d2->bits - d1->bits;
283 /* Stabilize the sort. */
284 return LABEL_DECL_UID (d2->label) - LABEL_DECL_UID (d1->label);
287 /* Expand a switch statement by a short sequence of bit-wise
288 comparisons. "switch(x)" is effectively converted into
289 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
290 integer constants.
292 INDEX_EXPR is the value being switched on.
294 MINVAL is the lowest case value of in the case nodes,
295 and RANGE is highest value minus MINVAL. MINVAL and RANGE
296 are not guaranteed to be of the same type as INDEX_EXPR
297 (the gimplifier doesn't change the type of case label values,
298 and MINVAL and RANGE are derived from those values).
299 MAXVAL is MINVAL + RANGE.
301 There *MUST* be MAX_CASE_BIT_TESTS or less unique case
302 node targets. */
304 static void
305 emit_case_bit_tests (gswitch *swtch, tree index_expr,
306 tree minval, tree range, tree maxval)
308 struct case_bit_test test[MAX_CASE_BIT_TESTS];
309 unsigned int i, j, k;
310 unsigned int count;
312 basic_block switch_bb = gimple_bb (swtch);
313 basic_block default_bb, new_default_bb, new_bb;
314 edge default_edge;
315 bool update_dom = dom_info_available_p (CDI_DOMINATORS);
317 vec<basic_block> bbs_to_fix_dom = vNULL;
319 tree index_type = TREE_TYPE (index_expr);
320 tree unsigned_index_type = unsigned_type_for (index_type);
321 unsigned int branch_num = gimple_switch_num_labels (swtch);
323 gimple_stmt_iterator gsi;
324 gassign *shift_stmt;
326 tree idx, tmp, csui;
327 tree word_type_node = lang_hooks.types.type_for_mode (word_mode, 1);
328 tree word_mode_zero = fold_convert (word_type_node, integer_zero_node);
329 tree word_mode_one = fold_convert (word_type_node, integer_one_node);
330 int prec = TYPE_PRECISION (word_type_node);
331 wide_int wone = wi::one (prec);
333 memset (&test, 0, sizeof (test));
335 /* Get the edge for the default case. */
336 tmp = gimple_switch_default_label (swtch);
337 default_bb = label_to_block (CASE_LABEL (tmp));
338 default_edge = find_edge (switch_bb, default_bb);
340 /* Go through all case labels, and collect the case labels, profile
341 counts, and other information we need to build the branch tests. */
342 count = 0;
343 for (i = 1; i < branch_num; i++)
345 unsigned int lo, hi;
346 tree cs = gimple_switch_label (swtch, i);
347 tree label = CASE_LABEL (cs);
348 edge e = find_edge (switch_bb, label_to_block (label));
349 for (k = 0; k < count; k++)
350 if (e == test[k].target_edge)
351 break;
353 if (k == count)
355 gcc_checking_assert (count < MAX_CASE_BIT_TESTS);
356 test[k].mask = wi::zero (prec);
357 test[k].target_edge = e;
358 test[k].label = label;
359 test[k].bits = 1;
360 count++;
362 else
363 test[k].bits++;
365 lo = tree_to_uhwi (int_const_binop (MINUS_EXPR,
366 CASE_LOW (cs), minval));
367 if (CASE_HIGH (cs) == NULL_TREE)
368 hi = lo;
369 else
370 hi = tree_to_uhwi (int_const_binop (MINUS_EXPR,
371 CASE_HIGH (cs), minval));
373 for (j = lo; j <= hi; j++)
374 test[k].mask |= wi::lshift (wone, j);
377 qsort (test, count, sizeof (*test), case_bit_test_cmp);
379 /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of
380 the minval subtractions, but it might make the mask constants more
381 expensive. So, compare the costs. */
382 if (compare_tree_int (minval, 0) > 0
383 && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
385 int cost_diff;
386 HOST_WIDE_INT m = tree_to_uhwi (minval);
387 rtx reg = gen_raw_REG (word_mode, 10000);
388 bool speed_p = optimize_bb_for_speed_p (gimple_bb (swtch));
389 cost_diff = set_rtx_cost (gen_rtx_PLUS (word_mode, reg,
390 GEN_INT (-m)), speed_p);
391 for (i = 0; i < count; i++)
393 rtx r = immed_wide_int_const (test[i].mask, word_mode);
394 cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r), speed_p);
395 r = immed_wide_int_const (wi::lshift (test[i].mask, m), word_mode);
396 cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r), speed_p);
398 if (cost_diff > 0)
400 for (i = 0; i < count; i++)
401 test[i].mask = wi::lshift (test[i].mask, m);
402 minval = build_zero_cst (TREE_TYPE (minval));
403 range = maxval;
407 /* We generate two jumps to the default case label.
408 Split the default edge, so that we don't have to do any PHI node
409 updating. */
410 new_default_bb = split_edge (default_edge);
412 if (update_dom)
414 bbs_to_fix_dom.create (10);
415 bbs_to_fix_dom.quick_push (switch_bb);
416 bbs_to_fix_dom.quick_push (default_bb);
417 bbs_to_fix_dom.quick_push (new_default_bb);
420 /* Now build the test-and-branch code. */
422 gsi = gsi_last_bb (switch_bb);
424 /* idx = (unsigned)x - minval. */
425 idx = fold_convert (unsigned_index_type, index_expr);
426 idx = fold_build2 (MINUS_EXPR, unsigned_index_type, idx,
427 fold_convert (unsigned_index_type, minval));
428 idx = force_gimple_operand_gsi (&gsi, idx,
429 /*simple=*/true, NULL_TREE,
430 /*before=*/true, GSI_SAME_STMT);
432 /* if (idx > range) goto default */
433 range = force_gimple_operand_gsi (&gsi,
434 fold_convert (unsigned_index_type, range),
435 /*simple=*/true, NULL_TREE,
436 /*before=*/true, GSI_SAME_STMT);
437 tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range);
438 new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, default_edge, update_dom);
439 if (update_dom)
440 bbs_to_fix_dom.quick_push (new_bb);
441 gcc_assert (gimple_bb (swtch) == new_bb);
442 gsi = gsi_last_bb (new_bb);
444 /* Any blocks dominated by the GIMPLE_SWITCH, but that are not successors
445 of NEW_BB, are still immediately dominated by SWITCH_BB. Make it so. */
446 if (update_dom)
448 vec<basic_block> dom_bbs;
449 basic_block dom_son;
451 dom_bbs = get_dominated_by (CDI_DOMINATORS, new_bb);
452 FOR_EACH_VEC_ELT (dom_bbs, i, dom_son)
454 edge e = find_edge (new_bb, dom_son);
455 if (e && single_pred_p (e->dest))
456 continue;
457 set_immediate_dominator (CDI_DOMINATORS, dom_son, switch_bb);
458 bbs_to_fix_dom.safe_push (dom_son);
460 dom_bbs.release ();
463 /* csui = (1 << (word_mode) idx) */
464 csui = make_ssa_name (word_type_node);
465 tmp = fold_build2 (LSHIFT_EXPR, word_type_node, word_mode_one,
466 fold_convert (word_type_node, idx));
467 tmp = force_gimple_operand_gsi (&gsi, tmp,
468 /*simple=*/false, NULL_TREE,
469 /*before=*/true, GSI_SAME_STMT);
470 shift_stmt = gimple_build_assign (csui, tmp);
471 gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT);
472 update_stmt (shift_stmt);
474 /* for each unique set of cases:
475 if (const & csui) goto target */
476 for (k = 0; k < count; k++)
478 tmp = wide_int_to_tree (word_type_node, test[k].mask);
479 tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp);
480 tmp = force_gimple_operand_gsi (&gsi, tmp,
481 /*simple=*/true, NULL_TREE,
482 /*before=*/true, GSI_SAME_STMT);
483 tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero);
484 new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_edge,
485 update_dom);
486 if (update_dom)
487 bbs_to_fix_dom.safe_push (new_bb);
488 gcc_assert (gimple_bb (swtch) == new_bb);
489 gsi = gsi_last_bb (new_bb);
492 /* We should have removed all edges now. */
493 gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0);
495 /* If nothing matched, go to the default label. */
496 make_edge (gsi_bb (gsi), new_default_bb, EDGE_FALLTHRU);
498 /* The GIMPLE_SWITCH is now redundant. */
499 gsi_remove (&gsi, true);
501 if (update_dom)
503 /* Fix up the dominator tree. */
504 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
505 bbs_to_fix_dom.release ();
510 Switch initialization conversion
512 The following pass changes simple initializations of scalars in a switch
513 statement into initializations from a static array. Obviously, the values
514 must be constant and known at compile time and a default branch must be
515 provided. For example, the following code:
517 int a,b;
519 switch (argc)
521 case 1:
522 case 2:
523 a_1 = 8;
524 b_1 = 6;
525 break;
526 case 3:
527 a_2 = 9;
528 b_2 = 5;
529 break;
530 case 12:
531 a_3 = 10;
532 b_3 = 4;
533 break;
534 default:
535 a_4 = 16;
536 b_4 = 1;
537 break;
539 a_5 = PHI <a_1, a_2, a_3, a_4>
540 b_5 = PHI <b_1, b_2, b_3, b_4>
543 is changed into:
545 static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
546 static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
547 16, 16, 10};
549 if (((unsigned) argc) - 1 < 11)
551 a_6 = CSWTCH02[argc - 1];
552 b_6 = CSWTCH01[argc - 1];
554 else
556 a_7 = 16;
557 b_7 = 1;
559 a_5 = PHI <a_6, a_7>
560 b_b = PHI <b_6, b_7>
562 There are further constraints. Specifically, the range of values across all
563 case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
564 eight) times the number of the actual switch branches.
566 This transformation was contributed by Martin Jambor, see this e-mail:
567 http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */
569 /* The main structure of the pass. */
570 struct switch_conv_info
572 /* The expression used to decide the switch branch. */
573 tree index_expr;
575 /* The following integer constants store the minimum and maximum value
576 covered by the case labels. */
577 tree range_min;
578 tree range_max;
580 /* The difference between the above two numbers. Stored here because it
581 is used in all the conversion heuristics, as well as for some of the
582 transformation, and it is expensive to re-compute it all the time. */
583 tree range_size;
585 /* Basic block that contains the actual GIMPLE_SWITCH. */
586 basic_block switch_bb;
588 /* Basic block that is the target of the default case. */
589 basic_block default_bb;
591 /* The single successor block of all branches out of the GIMPLE_SWITCH,
592 if such a block exists. Otherwise NULL. */
593 basic_block final_bb;
595 /* The probability of the default edge in the replaced switch. */
596 int default_prob;
598 /* The count of the default edge in the replaced switch. */
599 gcov_type default_count;
601 /* Combined count of all other (non-default) edges in the replaced switch. */
602 gcov_type other_count;
604 /* Number of phi nodes in the final bb (that we'll be replacing). */
605 int phi_count;
607 /* Array of default values, in the same order as phi nodes. */
608 tree *default_values;
610 /* Constructors of new static arrays. */
611 vec<constructor_elt, va_gc> **constructors;
613 /* Array of ssa names that are initialized with a value from a new static
614 array. */
615 tree *target_inbound_names;
617 /* Array of ssa names that are initialized with the default value if the
618 switch expression is out of range. */
619 tree *target_outbound_names;
621 /* The first load statement that loads a temporary from a new static array.
623 gimple arr_ref_first;
625 /* The last load statement that loads a temporary from a new static array. */
626 gimple arr_ref_last;
628 /* String reason why the case wasn't a good candidate that is written to the
629 dump file, if there is one. */
630 const char *reason;
632 /* Parameters for expand_switch_using_bit_tests. Should be computed
633 the same way as in expand_case. */
634 unsigned int uniq;
635 unsigned int count;
638 /* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */
640 static void
641 collect_switch_conv_info (gswitch *swtch, struct switch_conv_info *info)
643 unsigned int branch_num = gimple_switch_num_labels (swtch);
644 tree min_case, max_case;
645 unsigned int count, i;
646 edge e, e_default;
647 edge_iterator ei;
649 memset (info, 0, sizeof (*info));
651 /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
652 is a default label which is the first in the vector.
653 Collect the bits we can deduce from the CFG. */
654 info->index_expr = gimple_switch_index (swtch);
655 info->switch_bb = gimple_bb (swtch);
656 info->default_bb =
657 label_to_block (CASE_LABEL (gimple_switch_default_label (swtch)));
658 e_default = find_edge (info->switch_bb, info->default_bb);
659 info->default_prob = e_default->probability;
660 info->default_count = e_default->count;
661 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
662 if (e != e_default)
663 info->other_count += e->count;
665 /* See if there is one common successor block for all branch
666 targets. If it exists, record it in FINAL_BB.
667 Start with the destination of the default case as guess
668 or its destination in case it is a forwarder block. */
669 if (! single_pred_p (e_default->dest))
670 info->final_bb = e_default->dest;
671 else if (single_succ_p (e_default->dest)
672 && ! single_pred_p (single_succ (e_default->dest)))
673 info->final_bb = single_succ (e_default->dest);
674 /* Require that all switch destinations are either that common
675 FINAL_BB or a forwarder to it. */
676 if (info->final_bb)
677 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
679 if (e->dest == info->final_bb)
680 continue;
682 if (single_pred_p (e->dest)
683 && single_succ_p (e->dest)
684 && single_succ (e->dest) == info->final_bb)
685 continue;
687 info->final_bb = NULL;
688 break;
691 /* Get upper and lower bounds of case values, and the covered range. */
692 min_case = gimple_switch_label (swtch, 1);
693 max_case = gimple_switch_label (swtch, branch_num - 1);
695 info->range_min = CASE_LOW (min_case);
696 if (CASE_HIGH (max_case) != NULL_TREE)
697 info->range_max = CASE_HIGH (max_case);
698 else
699 info->range_max = CASE_LOW (max_case);
701 info->range_size =
702 int_const_binop (MINUS_EXPR, info->range_max, info->range_min);
704 /* Get a count of the number of case labels. Single-valued case labels
705 simply count as one, but a case range counts double, since it may
706 require two compares if it gets lowered as a branching tree. */
707 count = 0;
708 for (i = 1; i < branch_num; i++)
710 tree elt = gimple_switch_label (swtch, i);
711 count++;
712 if (CASE_HIGH (elt)
713 && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt)))
714 count++;
716 info->count = count;
718 /* Get the number of unique non-default targets out of the GIMPLE_SWITCH
719 block. Assume a CFG cleanup would have already removed degenerate
720 switch statements, this allows us to just use EDGE_COUNT. */
721 info->uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1;
724 /* Checks whether the range given by individual case statements of the SWTCH
725 switch statement isn't too big and whether the number of branches actually
726 satisfies the size of the new array. */
728 static bool
729 check_range (struct switch_conv_info *info)
731 gcc_assert (info->range_size);
732 if (!tree_fits_uhwi_p (info->range_size))
734 info->reason = "index range way too large or otherwise unusable";
735 return false;
738 if (tree_to_uhwi (info->range_size)
739 > ((unsigned) info->count * SWITCH_CONVERSION_BRANCH_RATIO))
741 info->reason = "the maximum range-branch ratio exceeded";
742 return false;
745 return true;
748 /* Checks whether all but the FINAL_BB basic blocks are empty. */
750 static bool
751 check_all_empty_except_final (struct switch_conv_info *info)
753 edge e;
754 edge_iterator ei;
756 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
758 if (e->dest == info->final_bb)
759 continue;
761 if (!empty_block_p (e->dest))
763 info->reason = "bad case - a non-final BB not empty";
764 return false;
768 return true;
771 /* This function checks whether all required values in phi nodes in final_bb
772 are constants. Required values are those that correspond to a basic block
773 which is a part of the examined switch statement. It returns true if the
774 phi nodes are OK, otherwise false. */
776 static bool
777 check_final_bb (struct switch_conv_info *info)
779 gphi_iterator gsi;
781 info->phi_count = 0;
782 for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
784 gphi *phi = gsi.phi ();
785 unsigned int i;
787 info->phi_count++;
789 for (i = 0; i < gimple_phi_num_args (phi); i++)
791 basic_block bb = gimple_phi_arg_edge (phi, i)->src;
793 if (bb == info->switch_bb
794 || (single_pred_p (bb) && single_pred (bb) == info->switch_bb))
796 tree reloc, val;
798 val = gimple_phi_arg_def (phi, i);
799 if (!is_gimple_ip_invariant (val))
801 info->reason = "non-invariant value from a case";
802 return false; /* Non-invariant argument. */
804 reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
805 if ((flag_pic && reloc != null_pointer_node)
806 || (!flag_pic && reloc == NULL_TREE))
808 if (reloc)
809 info->reason
810 = "value from a case would need runtime relocations";
811 else
812 info->reason
813 = "value from a case is not a valid initializer";
814 return false;
820 return true;
823 /* The following function allocates default_values, target_{in,out}_names and
824 constructors arrays. The last one is also populated with pointers to
825 vectors that will become constructors of new arrays. */
827 static void
828 create_temp_arrays (struct switch_conv_info *info)
830 int i;
832 info->default_values = XCNEWVEC (tree, info->phi_count * 3);
833 /* ??? Macros do not support multi argument templates in their
834 argument list. We create a typedef to work around that problem. */
835 typedef vec<constructor_elt, va_gc> *vec_constructor_elt_gc;
836 info->constructors = XCNEWVEC (vec_constructor_elt_gc, info->phi_count);
837 info->target_inbound_names = info->default_values + info->phi_count;
838 info->target_outbound_names = info->target_inbound_names + info->phi_count;
839 for (i = 0; i < info->phi_count; i++)
840 vec_alloc (info->constructors[i], tree_to_uhwi (info->range_size) + 1);
843 /* Free the arrays created by create_temp_arrays(). The vectors that are
844 created by that function are not freed here, however, because they have
845 already become constructors and must be preserved. */
847 static void
848 free_temp_arrays (struct switch_conv_info *info)
850 XDELETEVEC (info->constructors);
851 XDELETEVEC (info->default_values);
854 /* Populate the array of default values in the order of phi nodes.
855 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch. */
857 static void
858 gather_default_values (tree default_case, struct switch_conv_info *info)
860 gphi_iterator gsi;
861 basic_block bb = label_to_block (CASE_LABEL (default_case));
862 edge e;
863 int i = 0;
865 gcc_assert (CASE_LOW (default_case) == NULL_TREE);
867 if (bb == info->final_bb)
868 e = find_edge (info->switch_bb, bb);
869 else
870 e = single_succ_edge (bb);
872 for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
874 gphi *phi = gsi.phi ();
875 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
876 gcc_assert (val);
877 info->default_values[i++] = val;
881 /* The following function populates the vectors in the constructors array with
882 future contents of the static arrays. The vectors are populated in the
883 order of phi nodes. SWTCH is the switch statement being converted. */
885 static void
886 build_constructors (gswitch *swtch, struct switch_conv_info *info)
888 unsigned i, branch_num = gimple_switch_num_labels (swtch);
889 tree pos = info->range_min;
891 for (i = 1; i < branch_num; i++)
893 tree cs = gimple_switch_label (swtch, i);
894 basic_block bb = label_to_block (CASE_LABEL (cs));
895 edge e;
896 tree high;
897 gphi_iterator gsi;
898 int j;
900 if (bb == info->final_bb)
901 e = find_edge (info->switch_bb, bb);
902 else
903 e = single_succ_edge (bb);
904 gcc_assert (e);
906 while (tree_int_cst_lt (pos, CASE_LOW (cs)))
908 int k;
909 for (k = 0; k < info->phi_count; k++)
911 constructor_elt elt;
913 elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
914 elt.value
915 = unshare_expr_without_location (info->default_values[k]);
916 info->constructors[k]->quick_push (elt);
919 pos = int_const_binop (PLUS_EXPR, pos,
920 build_int_cst (TREE_TYPE (pos), 1));
922 gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
924 j = 0;
925 if (CASE_HIGH (cs))
926 high = CASE_HIGH (cs);
927 else
928 high = CASE_LOW (cs);
929 for (gsi = gsi_start_phis (info->final_bb);
930 !gsi_end_p (gsi); gsi_next (&gsi))
932 gphi *phi = gsi.phi ();
933 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
934 tree low = CASE_LOW (cs);
935 pos = CASE_LOW (cs);
939 constructor_elt elt;
941 elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
942 elt.value = unshare_expr_without_location (val);
943 info->constructors[j]->quick_push (elt);
945 pos = int_const_binop (PLUS_EXPR, pos,
946 build_int_cst (TREE_TYPE (pos), 1));
947 } while (!tree_int_cst_lt (high, pos)
948 && tree_int_cst_lt (low, pos));
949 j++;
954 /* If all values in the constructor vector are the same, return the value.
955 Otherwise return NULL_TREE. Not supposed to be called for empty
956 vectors. */
958 static tree
959 constructor_contains_same_values_p (vec<constructor_elt, va_gc> *vec)
961 unsigned int i;
962 tree prev = NULL_TREE;
963 constructor_elt *elt;
965 FOR_EACH_VEC_SAFE_ELT (vec, i, elt)
967 if (!prev)
968 prev = elt->value;
969 else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST))
970 return NULL_TREE;
972 return prev;
975 /* Return type which should be used for array elements, either TYPE,
976 or for integral type some smaller integral type that can still hold
977 all the constants. */
979 static tree
980 array_value_type (gswitch *swtch, tree type, int num,
981 struct switch_conv_info *info)
983 unsigned int i, len = vec_safe_length (info->constructors[num]);
984 constructor_elt *elt;
985 machine_mode mode;
986 int sign = 0;
987 tree smaller_type;
989 if (!INTEGRAL_TYPE_P (type))
990 return type;
992 mode = GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type)));
993 if (GET_MODE_SIZE (TYPE_MODE (type)) <= GET_MODE_SIZE (mode))
994 return type;
996 if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32))
997 return type;
999 FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
1001 wide_int cst;
1003 if (TREE_CODE (elt->value) != INTEGER_CST)
1004 return type;
1006 cst = elt->value;
1007 while (1)
1009 unsigned int prec = GET_MODE_BITSIZE (mode);
1010 if (prec > HOST_BITS_PER_WIDE_INT)
1011 return type;
1013 if (sign >= 0 && cst == wi::zext (cst, prec))
1015 if (sign == 0 && cst == wi::sext (cst, prec))
1016 break;
1017 sign = 1;
1018 break;
1020 if (sign <= 0 && cst == wi::sext (cst, prec))
1022 sign = -1;
1023 break;
1026 if (sign == 1)
1027 sign = 0;
1029 mode = GET_MODE_WIDER_MODE (mode);
1030 if (mode == VOIDmode
1031 || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (TYPE_MODE (type)))
1032 return type;
1036 if (sign == 0)
1037 sign = TYPE_UNSIGNED (type) ? 1 : -1;
1038 smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0);
1039 if (GET_MODE_SIZE (TYPE_MODE (type))
1040 <= GET_MODE_SIZE (TYPE_MODE (smaller_type)))
1041 return type;
1043 return smaller_type;
1046 /* Create an appropriate array type and declaration and assemble a static array
1047 variable. Also create a load statement that initializes the variable in
1048 question with a value from the static array. SWTCH is the switch statement
1049 being converted, NUM is the index to arrays of constructors, default values
1050 and target SSA names for this particular array. ARR_INDEX_TYPE is the type
1051 of the index of the new array, PHI is the phi node of the final BB that
1052 corresponds to the value that will be loaded from the created array. TIDX
1053 is an ssa name of a temporary variable holding the index for loads from the
1054 new array. */
1056 static void
1057 build_one_array (gswitch *swtch, int num, tree arr_index_type,
1058 gphi *phi, tree tidx, struct switch_conv_info *info)
1060 tree name, cst;
1061 gimple load;
1062 gimple_stmt_iterator gsi = gsi_for_stmt (swtch);
1063 location_t loc = gimple_location (swtch);
1065 gcc_assert (info->default_values[num]);
1067 name = copy_ssa_name (PHI_RESULT (phi));
1068 info->target_inbound_names[num] = name;
1070 cst = constructor_contains_same_values_p (info->constructors[num]);
1071 if (cst)
1072 load = gimple_build_assign (name, cst);
1073 else
1075 tree array_type, ctor, decl, value_type, fetch, default_type;
1077 default_type = TREE_TYPE (info->default_values[num]);
1078 value_type = array_value_type (swtch, default_type, num, info);
1079 array_type = build_array_type (value_type, arr_index_type);
1080 if (default_type != value_type)
1082 unsigned int i;
1083 constructor_elt *elt;
1085 FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
1086 elt->value = fold_convert (value_type, elt->value);
1088 ctor = build_constructor (array_type, info->constructors[num]);
1089 TREE_CONSTANT (ctor) = true;
1090 TREE_STATIC (ctor) = true;
1092 decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type);
1093 TREE_STATIC (decl) = 1;
1094 DECL_INITIAL (decl) = ctor;
1096 DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
1097 DECL_ARTIFICIAL (decl) = 1;
1098 TREE_CONSTANT (decl) = 1;
1099 TREE_READONLY (decl) = 1;
1100 varpool_node::finalize_decl (decl);
1102 fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
1103 NULL_TREE);
1104 if (default_type != value_type)
1106 fetch = fold_convert (default_type, fetch);
1107 fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE,
1108 true, GSI_SAME_STMT);
1110 load = gimple_build_assign (name, fetch);
1113 gsi_insert_before (&gsi, load, GSI_SAME_STMT);
1114 update_stmt (load);
1115 info->arr_ref_last = load;
1118 /* Builds and initializes static arrays initialized with values gathered from
1119 the SWTCH switch statement. Also creates statements that load values from
1120 them. */
1122 static void
1123 build_arrays (gswitch *swtch, struct switch_conv_info *info)
1125 tree arr_index_type;
1126 tree tidx, sub, utype;
1127 gimple stmt;
1128 gimple_stmt_iterator gsi;
1129 gphi_iterator gpi;
1130 int i;
1131 location_t loc = gimple_location (swtch);
1133 gsi = gsi_for_stmt (swtch);
1135 /* Make sure we do not generate arithmetics in a subrange. */
1136 utype = TREE_TYPE (info->index_expr);
1137 if (TREE_TYPE (utype))
1138 utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1);
1139 else
1140 utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
1142 arr_index_type = build_index_type (info->range_size);
1143 tidx = make_ssa_name (utype);
1144 sub = fold_build2_loc (loc, MINUS_EXPR, utype,
1145 fold_convert_loc (loc, utype, info->index_expr),
1146 fold_convert_loc (loc, utype, info->range_min));
1147 sub = force_gimple_operand_gsi (&gsi, sub,
1148 false, NULL, true, GSI_SAME_STMT);
1149 stmt = gimple_build_assign (tidx, sub);
1151 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1152 update_stmt (stmt);
1153 info->arr_ref_first = stmt;
1155 for (gpi = gsi_start_phis (info->final_bb), i = 0;
1156 !gsi_end_p (gpi); gsi_next (&gpi), i++)
1157 build_one_array (swtch, i, arr_index_type, gpi.phi (), tidx, info);
1160 /* Generates and appropriately inserts loads of default values at the position
1161 given by BSI. Returns the last inserted statement. */
1163 static gassign *
1164 gen_def_assigns (gimple_stmt_iterator *gsi, struct switch_conv_info *info)
1166 int i;
1167 gassign *assign = NULL;
1169 for (i = 0; i < info->phi_count; i++)
1171 tree name = copy_ssa_name (info->target_inbound_names[i]);
1172 info->target_outbound_names[i] = name;
1173 assign = gimple_build_assign (name, info->default_values[i]);
1174 gsi_insert_before (gsi, assign, GSI_SAME_STMT);
1175 update_stmt (assign);
1177 return assign;
1180 /* Deletes the unused bbs and edges that now contain the switch statement and
1181 its empty branch bbs. BBD is the now dead BB containing the original switch
1182 statement, FINAL is the last BB of the converted switch statement (in terms
1183 of succession). */
1185 static void
1186 prune_bbs (basic_block bbd, basic_block final)
1188 edge_iterator ei;
1189 edge e;
1191 for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
1193 basic_block bb;
1194 bb = e->dest;
1195 remove_edge (e);
1196 if (bb != final)
1197 delete_basic_block (bb);
1199 delete_basic_block (bbd);
1202 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
1203 from the basic block loading values from an array and E2F from the basic
1204 block loading default values. BBF is the last switch basic block (see the
1205 bbf description in the comment below). */
1207 static void
1208 fix_phi_nodes (edge e1f, edge e2f, basic_block bbf,
1209 struct switch_conv_info *info)
1211 gphi_iterator gsi;
1212 int i;
1214 for (gsi = gsi_start_phis (bbf), i = 0;
1215 !gsi_end_p (gsi); gsi_next (&gsi), i++)
1217 gphi *phi = gsi.phi ();
1218 add_phi_arg (phi, info->target_inbound_names[i], e1f, UNKNOWN_LOCATION);
1219 add_phi_arg (phi, info->target_outbound_names[i], e2f, UNKNOWN_LOCATION);
1223 /* Creates a check whether the switch expression value actually falls into the
1224 range given by all the cases. If it does not, the temporaries are loaded
1225 with default values instead. SWTCH is the switch statement being converted.
1227 bb0 is the bb with the switch statement, however, we'll end it with a
1228 condition instead.
1230 bb1 is the bb to be used when the range check went ok. It is derived from
1231 the switch BB
1233 bb2 is the bb taken when the expression evaluated outside of the range
1234 covered by the created arrays. It is populated by loads of default
1235 values.
1237 bbF is a fall through for both bb1 and bb2 and contains exactly what
1238 originally followed the switch statement.
1240 bbD contains the switch statement (in the end). It is unreachable but we
1241 still need to strip off its edges.
1244 static void
1245 gen_inbound_check (gswitch *swtch, struct switch_conv_info *info)
1247 tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION);
1248 tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
1249 tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION);
1250 glabel *label1, *label2, *label3;
1251 tree utype, tidx;
1252 tree bound;
1254 gcond *cond_stmt;
1256 gassign *last_assign;
1257 gimple_stmt_iterator gsi;
1258 basic_block bb0, bb1, bb2, bbf, bbd;
1259 edge e01, e02, e21, e1d, e1f, e2f;
1260 location_t loc = gimple_location (swtch);
1262 gcc_assert (info->default_values);
1264 bb0 = gimple_bb (swtch);
1266 tidx = gimple_assign_lhs (info->arr_ref_first);
1267 utype = TREE_TYPE (tidx);
1269 /* (end of) block 0 */
1270 gsi = gsi_for_stmt (info->arr_ref_first);
1271 gsi_next (&gsi);
1273 bound = fold_convert_loc (loc, utype, info->range_size);
1274 cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
1275 gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1276 update_stmt (cond_stmt);
1278 /* block 2 */
1279 label2 = gimple_build_label (label_decl2);
1280 gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
1281 last_assign = gen_def_assigns (&gsi, info);
1283 /* block 1 */
1284 label1 = gimple_build_label (label_decl1);
1285 gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
1287 /* block F */
1288 gsi = gsi_start_bb (info->final_bb);
1289 label3 = gimple_build_label (label_decl3);
1290 gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
1292 /* cfg fix */
1293 e02 = split_block (bb0, cond_stmt);
1294 bb2 = e02->dest;
1296 e21 = split_block (bb2, last_assign);
1297 bb1 = e21->dest;
1298 remove_edge (e21);
1300 e1d = split_block (bb1, info->arr_ref_last);
1301 bbd = e1d->dest;
1302 remove_edge (e1d);
1304 /* flags and profiles of the edge for in-range values */
1305 e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
1306 e01->probability = REG_BR_PROB_BASE - info->default_prob;
1307 e01->count = info->other_count;
1309 /* flags and profiles of the edge taking care of out-of-range values */
1310 e02->flags &= ~EDGE_FALLTHRU;
1311 e02->flags |= EDGE_FALSE_VALUE;
1312 e02->probability = info->default_prob;
1313 e02->count = info->default_count;
1315 bbf = info->final_bb;
1317 e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
1318 e1f->probability = REG_BR_PROB_BASE;
1319 e1f->count = info->other_count;
1321 e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
1322 e2f->probability = REG_BR_PROB_BASE;
1323 e2f->count = info->default_count;
1325 /* frequencies of the new BBs */
1326 bb1->frequency = EDGE_FREQUENCY (e01);
1327 bb2->frequency = EDGE_FREQUENCY (e02);
1328 bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f);
1330 /* Tidy blocks that have become unreachable. */
1331 prune_bbs (bbd, info->final_bb);
1333 /* Fixup the PHI nodes in bbF. */
1334 fix_phi_nodes (e1f, e2f, bbf, info);
1336 /* Fix the dominator tree, if it is available. */
1337 if (dom_info_available_p (CDI_DOMINATORS))
1339 vec<basic_block> bbs_to_fix_dom;
1341 set_immediate_dominator (CDI_DOMINATORS, bb1, bb0);
1342 set_immediate_dominator (CDI_DOMINATORS, bb2, bb0);
1343 if (! get_immediate_dominator (CDI_DOMINATORS, bbf))
1344 /* If bbD was the immediate dominator ... */
1345 set_immediate_dominator (CDI_DOMINATORS, bbf, bb0);
1347 bbs_to_fix_dom.create (4);
1348 bbs_to_fix_dom.quick_push (bb0);
1349 bbs_to_fix_dom.quick_push (bb1);
1350 bbs_to_fix_dom.quick_push (bb2);
1351 bbs_to_fix_dom.quick_push (bbf);
1353 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
1354 bbs_to_fix_dom.release ();
1358 /* The following function is invoked on every switch statement (the current one
1359 is given in SWTCH) and runs the individual phases of switch conversion on it
1360 one after another until one fails or the conversion is completed.
1361 Returns NULL on success, or a pointer to a string with the reason why the
1362 conversion failed. */
1364 static const char *
1365 process_switch (gswitch *swtch)
1367 struct switch_conv_info info;
1369 /* Group case labels so that we get the right results from the heuristics
1370 that decide on the code generation approach for this switch. */
1371 group_case_labels_stmt (swtch);
1373 /* If this switch is now a degenerate case with only a default label,
1374 there is nothing left for us to do. */
1375 if (gimple_switch_num_labels (swtch) < 2)
1376 return "switch is a degenerate case";
1378 collect_switch_conv_info (swtch, &info);
1380 /* No error markers should reach here (they should be filtered out
1381 during gimplification). */
1382 gcc_checking_assert (TREE_TYPE (info.index_expr) != error_mark_node);
1384 /* A switch on a constant should have been optimized in tree-cfg-cleanup. */
1385 gcc_checking_assert (! TREE_CONSTANT (info.index_expr));
1387 if (info.uniq <= MAX_CASE_BIT_TESTS)
1389 if (expand_switch_using_bit_tests_p (info.range_size,
1390 info.uniq, info.count,
1391 optimize_bb_for_speed_p
1392 (gimple_bb (swtch))))
1394 if (dump_file)
1395 fputs (" expanding as bit test is preferable\n", dump_file);
1396 emit_case_bit_tests (swtch, info.index_expr, info.range_min,
1397 info.range_size, info.range_max);
1398 loops_state_set (LOOPS_NEED_FIXUP);
1399 return NULL;
1402 if (info.uniq <= 2)
1403 /* This will be expanded as a decision tree in stmt.c:expand_case. */
1404 return " expanding as jumps is preferable";
1407 /* If there is no common successor, we cannot do the transformation. */
1408 if (! info.final_bb)
1409 return "no common successor to all case label target blocks found";
1411 /* Check the case label values are within reasonable range: */
1412 if (!check_range (&info))
1414 gcc_assert (info.reason);
1415 return info.reason;
1418 /* For all the cases, see whether they are empty, the assignments they
1419 represent constant and so on... */
1420 if (! check_all_empty_except_final (&info))
1422 gcc_assert (info.reason);
1423 return info.reason;
1425 if (!check_final_bb (&info))
1427 gcc_assert (info.reason);
1428 return info.reason;
1431 /* At this point all checks have passed and we can proceed with the
1432 transformation. */
1434 create_temp_arrays (&info);
1435 gather_default_values (gimple_switch_default_label (swtch), &info);
1436 build_constructors (swtch, &info);
1438 build_arrays (swtch, &info); /* Build the static arrays and assignments. */
1439 gen_inbound_check (swtch, &info); /* Build the bounds check. */
1441 /* Cleanup: */
1442 free_temp_arrays (&info);
1443 return NULL;
1446 /* The main function of the pass scans statements for switches and invokes
1447 process_switch on them. */
1449 namespace {
1451 const pass_data pass_data_convert_switch =
1453 GIMPLE_PASS, /* type */
1454 "switchconv", /* name */
1455 OPTGROUP_NONE, /* optinfo_flags */
1456 TV_TREE_SWITCH_CONVERSION, /* tv_id */
1457 ( PROP_cfg | PROP_ssa ), /* properties_required */
1458 0, /* properties_provided */
1459 0, /* properties_destroyed */
1460 0, /* todo_flags_start */
1461 TODO_update_ssa, /* todo_flags_finish */
1464 class pass_convert_switch : public gimple_opt_pass
1466 public:
1467 pass_convert_switch (gcc::context *ctxt)
1468 : gimple_opt_pass (pass_data_convert_switch, ctxt)
1471 /* opt_pass methods: */
1472 virtual bool gate (function *) { return flag_tree_switch_conversion != 0; }
1473 virtual unsigned int execute (function *);
1475 }; // class pass_convert_switch
1477 unsigned int
1478 pass_convert_switch::execute (function *fun)
1480 basic_block bb;
1482 FOR_EACH_BB_FN (bb, fun)
1484 const char *failure_reason;
1485 gimple stmt = last_stmt (bb);
1486 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
1488 if (dump_file)
1490 expanded_location loc = expand_location (gimple_location (stmt));
1492 fprintf (dump_file, "beginning to process the following "
1493 "SWITCH statement (%s:%d) : ------- \n",
1494 loc.file, loc.line);
1495 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1496 putc ('\n', dump_file);
1499 failure_reason = process_switch (as_a <gswitch *> (stmt));
1500 if (! failure_reason)
1502 if (dump_file)
1504 fputs ("Switch converted\n", dump_file);
1505 fputs ("--------------------------------\n", dump_file);
1508 /* Make no effort to update the post-dominator tree. It is actually not
1509 that hard for the transformations we have performed, but it is not
1510 supported by iterate_fix_dominators. */
1511 free_dominance_info (CDI_POST_DOMINATORS);
1513 else
1515 if (dump_file)
1517 fputs ("Bailing out - ", dump_file);
1518 fputs (failure_reason, dump_file);
1519 fputs ("\n--------------------------------\n", dump_file);
1525 return 0;
1528 } // anon namespace
1530 gimple_opt_pass *
1531 make_pass_convert_switch (gcc::context *ctxt)
1533 return new pass_convert_switch (ctxt);