Daily bump.
[official-gcc.git] / gcc / tree-switch-conversion.c
blob547ac9e3b581a8b14a729aaca45895f1347b2a58
1 /* Lower GIMPLE_SWITCH expressions to something more efficient than
2 a jump table.
3 Copyright (C) 2006-2014 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 "tree.h"
33 #include "varasm.h"
34 #include "stor-layout.h"
35 #include "basic-block.h"
36 #include "tree-ssa-alias.h"
37 #include "internal-fn.h"
38 #include "gimple-expr.h"
39 #include "is-a.h"
40 #include "gimple.h"
41 #include "gimplify.h"
42 #include "gimple-iterator.h"
43 #include "gimplify-me.h"
44 #include "gimple-ssa.h"
45 #include "cgraph.h"
46 #include "tree-cfg.h"
47 #include "tree-phinodes.h"
48 #include "stringpool.h"
49 #include "tree-ssanames.h"
50 #include "tree-pass.h"
51 #include "gimple-pretty-print.h"
52 #include "cfgloop.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"
58 /* Need to include expr.h and optabs.h for lshift_cheap_p. */
59 #include "expr.h"
60 #include "optabs.h"
62 /* Maximum number of case bit tests.
63 FIXME: This should be derived from PARAM_CASE_VALUES_THRESHOLD and
64 targetm.case_values_threshold(), or be its own param. */
65 #define MAX_CASE_BIT_TESTS 3
67 /* Split the basic block at the statement pointed to by GSIP, and insert
68 a branch to the target basic block of E_TRUE conditional on tree
69 expression COND.
71 It is assumed that there is already an edge from the to-be-split
72 basic block to E_TRUE->dest block. This edge is removed, and the
73 profile information on the edge is re-used for the new conditional
74 jump.
76 The CFG is updated. The dominator tree will not be valid after
77 this transformation, but the immediate dominators are updated if
78 UPDATE_DOMINATORS is true.
80 Returns the newly created basic block. */
82 static basic_block
83 hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
84 tree cond, edge e_true,
85 bool update_dominators)
87 tree tmp;
88 gimple cond_stmt;
89 edge e_false;
90 basic_block new_bb, split_bb = gsi_bb (*gsip);
91 bool dominated_e_true = false;
93 gcc_assert (e_true->src == split_bb);
95 if (update_dominators
96 && get_immediate_dominator (CDI_DOMINATORS, e_true->dest) == split_bb)
97 dominated_e_true = true;
99 tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL,
100 /*before=*/true, GSI_SAME_STMT);
101 cond_stmt = gimple_build_cond_from_tree (tmp, NULL_TREE, NULL_TREE);
102 gsi_insert_before (gsip, cond_stmt, GSI_SAME_STMT);
104 e_false = split_block (split_bb, cond_stmt);
105 new_bb = e_false->dest;
106 redirect_edge_pred (e_true, split_bb);
108 e_true->flags &= ~EDGE_FALLTHRU;
109 e_true->flags |= EDGE_TRUE_VALUE;
111 e_false->flags &= ~EDGE_FALLTHRU;
112 e_false->flags |= EDGE_FALSE_VALUE;
113 e_false->probability = REG_BR_PROB_BASE - e_true->probability;
114 e_false->count = split_bb->count - e_true->count;
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 /* Determine whether "1 << x" is relatively cheap in word_mode. */
129 /* FIXME: This is the function that we need rtl.h and optabs.h for.
130 This function (and similar RTL-related cost code in e.g. IVOPTS) should
131 be moved to some kind of interface file for GIMPLE/RTL interactions. */
132 static bool
133 lshift_cheap_p (void)
135 /* FIXME: This should be made target dependent via this "this_target"
136 mechanism, similar to e.g. can_copy_init_p in gcse.c. */
137 static bool init[2] = {false, false};
138 static bool cheap[2] = {true, true};
139 bool speed_p;
141 /* If the targer has no lshift in word_mode, the operation will most
142 probably not be cheap. ??? Does GCC even work for such targets? */
143 if (optab_handler (ashl_optab, word_mode) == CODE_FOR_nothing)
144 return false;
146 speed_p = optimize_insn_for_speed_p ();
148 if (!init[speed_p])
150 rtx reg = gen_raw_REG (word_mode, 10000);
151 int cost = set_src_cost (gen_rtx_ASHIFT (word_mode, const1_rtx, reg),
152 speed_p);
153 cheap[speed_p] = cost < COSTS_N_INSNS (MAX_CASE_BIT_TESTS);
154 init[speed_p] = true;
157 return cheap[speed_p];
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)
170 return (((uniq == 1 && count >= 3)
171 || (uniq == 2 && count >= 5)
172 || (uniq == 3 && count >= 6))
173 && lshift_cheap_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 HOST_WIDE_INT hi;
253 HOST_WIDE_INT lo;
254 edge target_edge;
255 tree label;
256 int bits;
259 /* Comparison function for qsort to order bit tests by decreasing
260 probability of execution. Our best guess comes from a measured
261 profile. If the profile counts are equal, break even on the
262 number of case nodes, i.e. the node with the most cases gets
263 tested first.
265 TODO: Actually this currently runs before a profile is available.
266 Therefore the case-as-bit-tests transformation should be done
267 later in the pass pipeline, or something along the lines of
268 "Efficient and effective branch reordering using profile data"
269 (Yang et. al., 2002) should be implemented (although, how good
270 is a paper is called "Efficient and effective ..." when the
271 latter is implied by the former, but oh well...). */
273 static int
274 case_bit_test_cmp (const void *p1, const void *p2)
276 const struct case_bit_test *const d1 = (const struct case_bit_test *) p1;
277 const struct case_bit_test *const d2 = (const struct case_bit_test *) p2;
279 if (d2->target_edge->count != d1->target_edge->count)
280 return d2->target_edge->count - d1->target_edge->count;
281 if (d2->bits != d1->bits)
282 return d2->bits - d1->bits;
284 /* Stabilize the sort. */
285 return LABEL_DECL_UID (d2->label) - LABEL_DECL_UID (d1->label);
288 /* Expand a switch statement by a short sequence of bit-wise
289 comparisons. "switch(x)" is effectively converted into
290 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
291 integer constants.
293 INDEX_EXPR is the value being switched on.
295 MINVAL is the lowest case value of in the case nodes,
296 and RANGE is highest value minus MINVAL. MINVAL and RANGE
297 are not guaranteed to be of the same type as INDEX_EXPR
298 (the gimplifier doesn't change the type of case label values,
299 and MINVAL and RANGE are derived from those values).
301 There *MUST* be MAX_CASE_BIT_TESTS or less unique case
302 node targets. */
304 static void
305 emit_case_bit_tests (gimple swtch, tree index_expr,
306 tree minval, tree range)
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 gimple 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);
331 memset (&test, 0, sizeof (test));
333 /* Get the edge for the default case. */
334 tmp = gimple_switch_default_label (swtch);
335 default_bb = label_to_block (CASE_LABEL (tmp));
336 default_edge = find_edge (switch_bb, default_bb);
338 /* Go through all case labels, and collect the case labels, profile
339 counts, and other information we need to build the branch tests. */
340 count = 0;
341 for (i = 1; i < branch_num; i++)
343 unsigned int lo, hi;
344 tree cs = gimple_switch_label (swtch, i);
345 tree label = CASE_LABEL (cs);
346 edge e = find_edge (switch_bb, label_to_block (label));
347 for (k = 0; k < count; k++)
348 if (e == test[k].target_edge)
349 break;
351 if (k == count)
353 gcc_checking_assert (count < MAX_CASE_BIT_TESTS);
354 test[k].hi = 0;
355 test[k].lo = 0;
356 test[k].target_edge = e;
357 test[k].label = label;
358 test[k].bits = 1;
359 count++;
361 else
362 test[k].bits++;
364 lo = tree_to_uhwi (int_const_binop (MINUS_EXPR,
365 CASE_LOW (cs), minval));
366 if (CASE_HIGH (cs) == NULL_TREE)
367 hi = lo;
368 else
369 hi = tree_to_uhwi (int_const_binop (MINUS_EXPR,
370 CASE_HIGH (cs), minval));
372 for (j = lo; j <= hi; j++)
373 if (j >= HOST_BITS_PER_WIDE_INT)
374 test[k].hi |= (HOST_WIDE_INT) 1 << (j - HOST_BITS_PER_INT);
375 else
376 test[k].lo |= (HOST_WIDE_INT) 1 << j;
379 qsort (test, count, sizeof (*test), case_bit_test_cmp);
381 /* We generate two jumps to the default case label.
382 Split the default edge, so that we don't have to do any PHI node
383 updating. */
384 new_default_bb = split_edge (default_edge);
386 if (update_dom)
388 bbs_to_fix_dom.create (10);
389 bbs_to_fix_dom.quick_push (switch_bb);
390 bbs_to_fix_dom.quick_push (default_bb);
391 bbs_to_fix_dom.quick_push (new_default_bb);
394 /* Now build the test-and-branch code. */
396 gsi = gsi_last_bb (switch_bb);
398 /* idx = (unsigned)x - minval. */
399 idx = fold_convert (unsigned_index_type, index_expr);
400 idx = fold_build2 (MINUS_EXPR, unsigned_index_type, idx,
401 fold_convert (unsigned_index_type, minval));
402 idx = force_gimple_operand_gsi (&gsi, idx,
403 /*simple=*/true, NULL_TREE,
404 /*before=*/true, GSI_SAME_STMT);
406 /* if (idx > range) goto default */
407 range = force_gimple_operand_gsi (&gsi,
408 fold_convert (unsigned_index_type, range),
409 /*simple=*/true, NULL_TREE,
410 /*before=*/true, GSI_SAME_STMT);
411 tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range);
412 new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, default_edge, update_dom);
413 if (update_dom)
414 bbs_to_fix_dom.quick_push (new_bb);
415 gcc_assert (gimple_bb (swtch) == new_bb);
416 gsi = gsi_last_bb (new_bb);
418 /* Any blocks dominated by the GIMPLE_SWITCH, but that are not successors
419 of NEW_BB, are still immediately dominated by SWITCH_BB. Make it so. */
420 if (update_dom)
422 vec<basic_block> dom_bbs;
423 basic_block dom_son;
425 dom_bbs = get_dominated_by (CDI_DOMINATORS, new_bb);
426 FOR_EACH_VEC_ELT (dom_bbs, i, dom_son)
428 edge e = find_edge (new_bb, dom_son);
429 if (e && single_pred_p (e->dest))
430 continue;
431 set_immediate_dominator (CDI_DOMINATORS, dom_son, switch_bb);
432 bbs_to_fix_dom.safe_push (dom_son);
434 dom_bbs.release ();
437 /* csui = (1 << (word_mode) idx) */
438 csui = make_ssa_name (word_type_node, NULL);
439 tmp = fold_build2 (LSHIFT_EXPR, word_type_node, word_mode_one,
440 fold_convert (word_type_node, idx));
441 tmp = force_gimple_operand_gsi (&gsi, tmp,
442 /*simple=*/false, NULL_TREE,
443 /*before=*/true, GSI_SAME_STMT);
444 shift_stmt = gimple_build_assign (csui, tmp);
445 gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT);
446 update_stmt (shift_stmt);
448 /* for each unique set of cases:
449 if (const & csui) goto target */
450 for (k = 0; k < count; k++)
452 tmp = build_int_cst_wide (word_type_node, test[k].lo, test[k].hi);
453 tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp);
454 tmp = force_gimple_operand_gsi (&gsi, tmp,
455 /*simple=*/true, NULL_TREE,
456 /*before=*/true, GSI_SAME_STMT);
457 tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero);
458 new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_edge,
459 update_dom);
460 if (update_dom)
461 bbs_to_fix_dom.safe_push (new_bb);
462 gcc_assert (gimple_bb (swtch) == new_bb);
463 gsi = gsi_last_bb (new_bb);
466 /* We should have removed all edges now. */
467 gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0);
469 /* If nothing matched, go to the default label. */
470 make_edge (gsi_bb (gsi), new_default_bb, EDGE_FALLTHRU);
472 /* The GIMPLE_SWITCH is now redundant. */
473 gsi_remove (&gsi, true);
475 if (update_dom)
477 /* Fix up the dominator tree. */
478 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
479 bbs_to_fix_dom.release ();
484 Switch initialization conversion
486 The following pass changes simple initializations of scalars in a switch
487 statement into initializations from a static array. Obviously, the values
488 must be constant and known at compile time and a default branch must be
489 provided. For example, the following code:
491 int a,b;
493 switch (argc)
495 case 1:
496 case 2:
497 a_1 = 8;
498 b_1 = 6;
499 break;
500 case 3:
501 a_2 = 9;
502 b_2 = 5;
503 break;
504 case 12:
505 a_3 = 10;
506 b_3 = 4;
507 break;
508 default:
509 a_4 = 16;
510 b_4 = 1;
511 break;
513 a_5 = PHI <a_1, a_2, a_3, a_4>
514 b_5 = PHI <b_1, b_2, b_3, b_4>
517 is changed into:
519 static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
520 static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
521 16, 16, 10};
523 if (((unsigned) argc) - 1 < 11)
525 a_6 = CSWTCH02[argc - 1];
526 b_6 = CSWTCH01[argc - 1];
528 else
530 a_7 = 16;
531 b_7 = 1;
533 a_5 = PHI <a_6, a_7>
534 b_b = PHI <b_6, b_7>
536 There are further constraints. Specifically, the range of values across all
537 case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
538 eight) times the number of the actual switch branches.
540 This transformation was contributed by Martin Jambor, see this e-mail:
541 http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */
543 /* The main structure of the pass. */
544 struct switch_conv_info
546 /* The expression used to decide the switch branch. */
547 tree index_expr;
549 /* The following integer constants store the minimum and maximum value
550 covered by the case labels. */
551 tree range_min;
552 tree range_max;
554 /* The difference between the above two numbers. Stored here because it
555 is used in all the conversion heuristics, as well as for some of the
556 transformation, and it is expensive to re-compute it all the time. */
557 tree range_size;
559 /* Basic block that contains the actual GIMPLE_SWITCH. */
560 basic_block switch_bb;
562 /* Basic block that is the target of the default case. */
563 basic_block default_bb;
565 /* The single successor block of all branches out of the GIMPLE_SWITCH,
566 if such a block exists. Otherwise NULL. */
567 basic_block final_bb;
569 /* The probability of the default edge in the replaced switch. */
570 int default_prob;
572 /* The count of the default edge in the replaced switch. */
573 gcov_type default_count;
575 /* Combined count of all other (non-default) edges in the replaced switch. */
576 gcov_type other_count;
578 /* Number of phi nodes in the final bb (that we'll be replacing). */
579 int phi_count;
581 /* Array of default values, in the same order as phi nodes. */
582 tree *default_values;
584 /* Constructors of new static arrays. */
585 vec<constructor_elt, va_gc> **constructors;
587 /* Array of ssa names that are initialized with a value from a new static
588 array. */
589 tree *target_inbound_names;
591 /* Array of ssa names that are initialized with the default value if the
592 switch expression is out of range. */
593 tree *target_outbound_names;
595 /* The first load statement that loads a temporary from a new static array.
597 gimple arr_ref_first;
599 /* The last load statement that loads a temporary from a new static array. */
600 gimple arr_ref_last;
602 /* String reason why the case wasn't a good candidate that is written to the
603 dump file, if there is one. */
604 const char *reason;
606 /* Parameters for expand_switch_using_bit_tests. Should be computed
607 the same way as in expand_case. */
608 unsigned int uniq;
609 unsigned int count;
612 /* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */
614 static void
615 collect_switch_conv_info (gimple swtch, struct switch_conv_info *info)
617 unsigned int branch_num = gimple_switch_num_labels (swtch);
618 tree min_case, max_case;
619 unsigned int count, i;
620 edge e, e_default;
621 edge_iterator ei;
623 memset (info, 0, sizeof (*info));
625 /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
626 is a default label which is the first in the vector.
627 Collect the bits we can deduce from the CFG. */
628 info->index_expr = gimple_switch_index (swtch);
629 info->switch_bb = gimple_bb (swtch);
630 info->default_bb =
631 label_to_block (CASE_LABEL (gimple_switch_default_label (swtch)));
632 e_default = find_edge (info->switch_bb, info->default_bb);
633 info->default_prob = e_default->probability;
634 info->default_count = e_default->count;
635 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
636 if (e != e_default)
637 info->other_count += e->count;
639 /* See if there is one common successor block for all branch
640 targets. If it exists, record it in FINAL_BB. */
641 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
643 if (! single_pred_p (e->dest))
645 info->final_bb = e->dest;
646 break;
649 if (info->final_bb)
650 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
652 if (e->dest == info->final_bb)
653 continue;
655 if (single_pred_p (e->dest)
656 && single_succ_p (e->dest)
657 && single_succ (e->dest) == info->final_bb)
658 continue;
660 info->final_bb = NULL;
661 break;
664 /* Get upper and lower bounds of case values, and the covered range. */
665 min_case = gimple_switch_label (swtch, 1);
666 max_case = gimple_switch_label (swtch, branch_num - 1);
668 info->range_min = CASE_LOW (min_case);
669 if (CASE_HIGH (max_case) != NULL_TREE)
670 info->range_max = CASE_HIGH (max_case);
671 else
672 info->range_max = CASE_LOW (max_case);
674 info->range_size =
675 int_const_binop (MINUS_EXPR, info->range_max, info->range_min);
677 /* Get a count of the number of case labels. Single-valued case labels
678 simply count as one, but a case range counts double, since it may
679 require two compares if it gets lowered as a branching tree. */
680 count = 0;
681 for (i = 1; i < branch_num; i++)
683 tree elt = gimple_switch_label (swtch, i);
684 count++;
685 if (CASE_HIGH (elt)
686 && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt)))
687 count++;
689 info->count = count;
691 /* Get the number of unique non-default targets out of the GIMPLE_SWITCH
692 block. Assume a CFG cleanup would have already removed degenerate
693 switch statements, this allows us to just use EDGE_COUNT. */
694 info->uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1;
697 /* Checks whether the range given by individual case statements of the SWTCH
698 switch statement isn't too big and whether the number of branches actually
699 satisfies the size of the new array. */
701 static bool
702 check_range (struct switch_conv_info *info)
704 gcc_assert (info->range_size);
705 if (!tree_fits_uhwi_p (info->range_size))
707 info->reason = "index range way too large or otherwise unusable";
708 return false;
711 if (tree_to_uhwi (info->range_size)
712 > ((unsigned) info->count * SWITCH_CONVERSION_BRANCH_RATIO))
714 info->reason = "the maximum range-branch ratio exceeded";
715 return false;
718 return true;
721 /* Checks whether all but the FINAL_BB basic blocks are empty. */
723 static bool
724 check_all_empty_except_final (struct switch_conv_info *info)
726 edge e;
727 edge_iterator ei;
729 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
731 if (e->dest == info->final_bb)
732 continue;
734 if (!empty_block_p (e->dest))
736 info->reason = "bad case - a non-final BB not empty";
737 return false;
741 return true;
744 /* This function checks whether all required values in phi nodes in final_bb
745 are constants. Required values are those that correspond to a basic block
746 which is a part of the examined switch statement. It returns true if the
747 phi nodes are OK, otherwise false. */
749 static bool
750 check_final_bb (struct switch_conv_info *info)
752 gimple_stmt_iterator gsi;
754 info->phi_count = 0;
755 for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
757 gimple phi = gsi_stmt (gsi);
758 unsigned int i;
760 info->phi_count++;
762 for (i = 0; i < gimple_phi_num_args (phi); i++)
764 basic_block bb = gimple_phi_arg_edge (phi, i)->src;
766 if (bb == info->switch_bb
767 || (single_pred_p (bb) && single_pred (bb) == info->switch_bb))
769 tree reloc, val;
771 val = gimple_phi_arg_def (phi, i);
772 if (!is_gimple_ip_invariant (val))
774 info->reason = "non-invariant value from a case";
775 return false; /* Non-invariant argument. */
777 reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
778 if ((flag_pic && reloc != null_pointer_node)
779 || (!flag_pic && reloc == NULL_TREE))
781 if (reloc)
782 info->reason
783 = "value from a case would need runtime relocations";
784 else
785 info->reason
786 = "value from a case is not a valid initializer";
787 return false;
793 return true;
796 /* The following function allocates default_values, target_{in,out}_names and
797 constructors arrays. The last one is also populated with pointers to
798 vectors that will become constructors of new arrays. */
800 static void
801 create_temp_arrays (struct switch_conv_info *info)
803 int i;
805 info->default_values = XCNEWVEC (tree, info->phi_count * 3);
806 /* ??? Macros do not support multi argument templates in their
807 argument list. We create a typedef to work around that problem. */
808 typedef vec<constructor_elt, va_gc> *vec_constructor_elt_gc;
809 info->constructors = XCNEWVEC (vec_constructor_elt_gc, info->phi_count);
810 info->target_inbound_names = info->default_values + info->phi_count;
811 info->target_outbound_names = info->target_inbound_names + info->phi_count;
812 for (i = 0; i < info->phi_count; i++)
813 vec_alloc (info->constructors[i], tree_to_uhwi (info->range_size) + 1);
816 /* Free the arrays created by create_temp_arrays(). The vectors that are
817 created by that function are not freed here, however, because they have
818 already become constructors and must be preserved. */
820 static void
821 free_temp_arrays (struct switch_conv_info *info)
823 XDELETEVEC (info->constructors);
824 XDELETEVEC (info->default_values);
827 /* Populate the array of default values in the order of phi nodes.
828 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch. */
830 static void
831 gather_default_values (tree default_case, struct switch_conv_info *info)
833 gimple_stmt_iterator gsi;
834 basic_block bb = label_to_block (CASE_LABEL (default_case));
835 edge e;
836 int i = 0;
838 gcc_assert (CASE_LOW (default_case) == NULL_TREE);
840 if (bb == info->final_bb)
841 e = find_edge (info->switch_bb, bb);
842 else
843 e = single_succ_edge (bb);
845 for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
847 gimple phi = gsi_stmt (gsi);
848 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
849 gcc_assert (val);
850 info->default_values[i++] = val;
854 /* The following function populates the vectors in the constructors array with
855 future contents of the static arrays. The vectors are populated in the
856 order of phi nodes. SWTCH is the switch statement being converted. */
858 static void
859 build_constructors (gimple swtch, struct switch_conv_info *info)
861 unsigned i, branch_num = gimple_switch_num_labels (swtch);
862 tree pos = info->range_min;
864 for (i = 1; i < branch_num; i++)
866 tree cs = gimple_switch_label (swtch, i);
867 basic_block bb = label_to_block (CASE_LABEL (cs));
868 edge e;
869 tree high;
870 gimple_stmt_iterator gsi;
871 int j;
873 if (bb == info->final_bb)
874 e = find_edge (info->switch_bb, bb);
875 else
876 e = single_succ_edge (bb);
877 gcc_assert (e);
879 while (tree_int_cst_lt (pos, CASE_LOW (cs)))
881 int k;
882 for (k = 0; k < info->phi_count; k++)
884 constructor_elt elt;
886 elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
887 elt.value
888 = unshare_expr_without_location (info->default_values[k]);
889 info->constructors[k]->quick_push (elt);
892 pos = int_const_binop (PLUS_EXPR, pos, integer_one_node);
894 gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
896 j = 0;
897 if (CASE_HIGH (cs))
898 high = CASE_HIGH (cs);
899 else
900 high = CASE_LOW (cs);
901 for (gsi = gsi_start_phis (info->final_bb);
902 !gsi_end_p (gsi); gsi_next (&gsi))
904 gimple phi = gsi_stmt (gsi);
905 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
906 tree low = CASE_LOW (cs);
907 pos = CASE_LOW (cs);
911 constructor_elt elt;
913 elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
914 elt.value = unshare_expr_without_location (val);
915 info->constructors[j]->quick_push (elt);
917 pos = int_const_binop (PLUS_EXPR, pos, integer_one_node);
918 } while (!tree_int_cst_lt (high, pos)
919 && tree_int_cst_lt (low, pos));
920 j++;
925 /* If all values in the constructor vector are the same, return the value.
926 Otherwise return NULL_TREE. Not supposed to be called for empty
927 vectors. */
929 static tree
930 constructor_contains_same_values_p (vec<constructor_elt, va_gc> *vec)
932 unsigned int i;
933 tree prev = NULL_TREE;
934 constructor_elt *elt;
936 FOR_EACH_VEC_SAFE_ELT (vec, i, elt)
938 if (!prev)
939 prev = elt->value;
940 else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST))
941 return NULL_TREE;
943 return prev;
946 /* Return type which should be used for array elements, either TYPE,
947 or for integral type some smaller integral type that can still hold
948 all the constants. */
950 static tree
951 array_value_type (gimple swtch, tree type, int num,
952 struct switch_conv_info *info)
954 unsigned int i, len = vec_safe_length (info->constructors[num]);
955 constructor_elt *elt;
956 enum machine_mode mode;
957 int sign = 0;
958 tree smaller_type;
960 if (!INTEGRAL_TYPE_P (type))
961 return type;
963 mode = GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type)));
964 if (GET_MODE_SIZE (TYPE_MODE (type)) <= GET_MODE_SIZE (mode))
965 return type;
967 if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32))
968 return type;
970 FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
972 double_int cst;
974 if (TREE_CODE (elt->value) != INTEGER_CST)
975 return type;
977 cst = TREE_INT_CST (elt->value);
978 while (1)
980 unsigned int prec = GET_MODE_BITSIZE (mode);
981 if (prec > HOST_BITS_PER_WIDE_INT)
982 return type;
984 if (sign >= 0 && cst == cst.zext (prec))
986 if (sign == 0 && cst == cst.sext (prec))
987 break;
988 sign = 1;
989 break;
991 if (sign <= 0 && cst == cst.sext (prec))
993 sign = -1;
994 break;
997 if (sign == 1)
998 sign = 0;
1000 mode = GET_MODE_WIDER_MODE (mode);
1001 if (mode == VOIDmode
1002 || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (TYPE_MODE (type)))
1003 return type;
1007 if (sign == 0)
1008 sign = TYPE_UNSIGNED (type) ? 1 : -1;
1009 smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0);
1010 if (GET_MODE_SIZE (TYPE_MODE (type))
1011 <= GET_MODE_SIZE (TYPE_MODE (smaller_type)))
1012 return type;
1014 return smaller_type;
1017 /* Create an appropriate array type and declaration and assemble a static array
1018 variable. Also create a load statement that initializes the variable in
1019 question with a value from the static array. SWTCH is the switch statement
1020 being converted, NUM is the index to arrays of constructors, default values
1021 and target SSA names for this particular array. ARR_INDEX_TYPE is the type
1022 of the index of the new array, PHI is the phi node of the final BB that
1023 corresponds to the value that will be loaded from the created array. TIDX
1024 is an ssa name of a temporary variable holding the index for loads from the
1025 new array. */
1027 static void
1028 build_one_array (gimple swtch, int num, tree arr_index_type, gimple phi,
1029 tree tidx, struct switch_conv_info *info)
1031 tree name, cst;
1032 gimple load;
1033 gimple_stmt_iterator gsi = gsi_for_stmt (swtch);
1034 location_t loc = gimple_location (swtch);
1036 gcc_assert (info->default_values[num]);
1038 name = copy_ssa_name (PHI_RESULT (phi), NULL);
1039 info->target_inbound_names[num] = name;
1041 cst = constructor_contains_same_values_p (info->constructors[num]);
1042 if (cst)
1043 load = gimple_build_assign (name, cst);
1044 else
1046 tree array_type, ctor, decl, value_type, fetch, default_type;
1048 default_type = TREE_TYPE (info->default_values[num]);
1049 value_type = array_value_type (swtch, default_type, num, info);
1050 array_type = build_array_type (value_type, arr_index_type);
1051 if (default_type != value_type)
1053 unsigned int i;
1054 constructor_elt *elt;
1056 FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
1057 elt->value = fold_convert (value_type, elt->value);
1059 ctor = build_constructor (array_type, info->constructors[num]);
1060 TREE_CONSTANT (ctor) = true;
1061 TREE_STATIC (ctor) = true;
1063 decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type);
1064 TREE_STATIC (decl) = 1;
1065 DECL_INITIAL (decl) = ctor;
1067 DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
1068 DECL_ARTIFICIAL (decl) = 1;
1069 TREE_CONSTANT (decl) = 1;
1070 TREE_READONLY (decl) = 1;
1071 varpool_finalize_decl (decl);
1073 fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
1074 NULL_TREE);
1075 if (default_type != value_type)
1077 fetch = fold_convert (default_type, fetch);
1078 fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE,
1079 true, GSI_SAME_STMT);
1081 load = gimple_build_assign (name, fetch);
1084 gsi_insert_before (&gsi, load, GSI_SAME_STMT);
1085 update_stmt (load);
1086 info->arr_ref_last = load;
1089 /* Builds and initializes static arrays initialized with values gathered from
1090 the SWTCH switch statement. Also creates statements that load values from
1091 them. */
1093 static void
1094 build_arrays (gimple swtch, struct switch_conv_info *info)
1096 tree arr_index_type;
1097 tree tidx, sub, utype;
1098 gimple stmt;
1099 gimple_stmt_iterator gsi;
1100 int i;
1101 location_t loc = gimple_location (swtch);
1103 gsi = gsi_for_stmt (swtch);
1105 /* Make sure we do not generate arithmetics in a subrange. */
1106 utype = TREE_TYPE (info->index_expr);
1107 if (TREE_TYPE (utype))
1108 utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1);
1109 else
1110 utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
1112 arr_index_type = build_index_type (info->range_size);
1113 tidx = make_ssa_name (utype, NULL);
1114 sub = fold_build2_loc (loc, MINUS_EXPR, utype,
1115 fold_convert_loc (loc, utype, info->index_expr),
1116 fold_convert_loc (loc, utype, info->range_min));
1117 sub = force_gimple_operand_gsi (&gsi, sub,
1118 false, NULL, true, GSI_SAME_STMT);
1119 stmt = gimple_build_assign (tidx, sub);
1121 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1122 update_stmt (stmt);
1123 info->arr_ref_first = stmt;
1125 for (gsi = gsi_start_phis (info->final_bb), i = 0;
1126 !gsi_end_p (gsi); gsi_next (&gsi), i++)
1127 build_one_array (swtch, i, arr_index_type, gsi_stmt (gsi), tidx, info);
1130 /* Generates and appropriately inserts loads of default values at the position
1131 given by BSI. Returns the last inserted statement. */
1133 static gimple
1134 gen_def_assigns (gimple_stmt_iterator *gsi, struct switch_conv_info *info)
1136 int i;
1137 gimple assign = NULL;
1139 for (i = 0; i < info->phi_count; i++)
1141 tree name = copy_ssa_name (info->target_inbound_names[i], NULL);
1142 info->target_outbound_names[i] = name;
1143 assign = gimple_build_assign (name, info->default_values[i]);
1144 gsi_insert_before (gsi, assign, GSI_SAME_STMT);
1145 update_stmt (assign);
1147 return assign;
1150 /* Deletes the unused bbs and edges that now contain the switch statement and
1151 its empty branch bbs. BBD is the now dead BB containing the original switch
1152 statement, FINAL is the last BB of the converted switch statement (in terms
1153 of succession). */
1155 static void
1156 prune_bbs (basic_block bbd, basic_block final)
1158 edge_iterator ei;
1159 edge e;
1161 for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
1163 basic_block bb;
1164 bb = e->dest;
1165 remove_edge (e);
1166 if (bb != final)
1167 delete_basic_block (bb);
1169 delete_basic_block (bbd);
1172 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
1173 from the basic block loading values from an array and E2F from the basic
1174 block loading default values. BBF is the last switch basic block (see the
1175 bbf description in the comment below). */
1177 static void
1178 fix_phi_nodes (edge e1f, edge e2f, basic_block bbf,
1179 struct switch_conv_info *info)
1181 gimple_stmt_iterator gsi;
1182 int i;
1184 for (gsi = gsi_start_phis (bbf), i = 0;
1185 !gsi_end_p (gsi); gsi_next (&gsi), i++)
1187 gimple phi = gsi_stmt (gsi);
1188 add_phi_arg (phi, info->target_inbound_names[i], e1f, UNKNOWN_LOCATION);
1189 add_phi_arg (phi, info->target_outbound_names[i], e2f, UNKNOWN_LOCATION);
1193 /* Creates a check whether the switch expression value actually falls into the
1194 range given by all the cases. If it does not, the temporaries are loaded
1195 with default values instead. SWTCH is the switch statement being converted.
1197 bb0 is the bb with the switch statement, however, we'll end it with a
1198 condition instead.
1200 bb1 is the bb to be used when the range check went ok. It is derived from
1201 the switch BB
1203 bb2 is the bb taken when the expression evaluated outside of the range
1204 covered by the created arrays. It is populated by loads of default
1205 values.
1207 bbF is a fall through for both bb1 and bb2 and contains exactly what
1208 originally followed the switch statement.
1210 bbD contains the switch statement (in the end). It is unreachable but we
1211 still need to strip off its edges.
1214 static void
1215 gen_inbound_check (gimple swtch, struct switch_conv_info *info)
1217 tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION);
1218 tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
1219 tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION);
1220 gimple label1, label2, label3;
1221 tree utype, tidx;
1222 tree bound;
1224 gimple cond_stmt;
1226 gimple last_assign;
1227 gimple_stmt_iterator gsi;
1228 basic_block bb0, bb1, bb2, bbf, bbd;
1229 edge e01, e02, e21, e1d, e1f, e2f;
1230 location_t loc = gimple_location (swtch);
1232 gcc_assert (info->default_values);
1234 bb0 = gimple_bb (swtch);
1236 tidx = gimple_assign_lhs (info->arr_ref_first);
1237 utype = TREE_TYPE (tidx);
1239 /* (end of) block 0 */
1240 gsi = gsi_for_stmt (info->arr_ref_first);
1241 gsi_next (&gsi);
1243 bound = fold_convert_loc (loc, utype, info->range_size);
1244 cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
1245 gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1246 update_stmt (cond_stmt);
1248 /* block 2 */
1249 label2 = gimple_build_label (label_decl2);
1250 gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
1251 last_assign = gen_def_assigns (&gsi, info);
1253 /* block 1 */
1254 label1 = gimple_build_label (label_decl1);
1255 gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
1257 /* block F */
1258 gsi = gsi_start_bb (info->final_bb);
1259 label3 = gimple_build_label (label_decl3);
1260 gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
1262 /* cfg fix */
1263 e02 = split_block (bb0, cond_stmt);
1264 bb2 = e02->dest;
1266 e21 = split_block (bb2, last_assign);
1267 bb1 = e21->dest;
1268 remove_edge (e21);
1270 e1d = split_block (bb1, info->arr_ref_last);
1271 bbd = e1d->dest;
1272 remove_edge (e1d);
1274 /* flags and profiles of the edge for in-range values */
1275 e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
1276 e01->probability = REG_BR_PROB_BASE - info->default_prob;
1277 e01->count = info->other_count;
1279 /* flags and profiles of the edge taking care of out-of-range values */
1280 e02->flags &= ~EDGE_FALLTHRU;
1281 e02->flags |= EDGE_FALSE_VALUE;
1282 e02->probability = info->default_prob;
1283 e02->count = info->default_count;
1285 bbf = info->final_bb;
1287 e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
1288 e1f->probability = REG_BR_PROB_BASE;
1289 e1f->count = info->other_count;
1291 e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
1292 e2f->probability = REG_BR_PROB_BASE;
1293 e2f->count = info->default_count;
1295 /* frequencies of the new BBs */
1296 bb1->frequency = EDGE_FREQUENCY (e01);
1297 bb2->frequency = EDGE_FREQUENCY (e02);
1298 bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f);
1300 /* Tidy blocks that have become unreachable. */
1301 prune_bbs (bbd, info->final_bb);
1303 /* Fixup the PHI nodes in bbF. */
1304 fix_phi_nodes (e1f, e2f, bbf, info);
1306 /* Fix the dominator tree, if it is available. */
1307 if (dom_info_available_p (CDI_DOMINATORS))
1309 vec<basic_block> bbs_to_fix_dom;
1311 set_immediate_dominator (CDI_DOMINATORS, bb1, bb0);
1312 set_immediate_dominator (CDI_DOMINATORS, bb2, bb0);
1313 if (! get_immediate_dominator (CDI_DOMINATORS, bbf))
1314 /* If bbD was the immediate dominator ... */
1315 set_immediate_dominator (CDI_DOMINATORS, bbf, bb0);
1317 bbs_to_fix_dom.create (4);
1318 bbs_to_fix_dom.quick_push (bb0);
1319 bbs_to_fix_dom.quick_push (bb1);
1320 bbs_to_fix_dom.quick_push (bb2);
1321 bbs_to_fix_dom.quick_push (bbf);
1323 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
1324 bbs_to_fix_dom.release ();
1328 /* The following function is invoked on every switch statement (the current one
1329 is given in SWTCH) and runs the individual phases of switch conversion on it
1330 one after another until one fails or the conversion is completed.
1331 Returns NULL on success, or a pointer to a string with the reason why the
1332 conversion failed. */
1334 static const char *
1335 process_switch (gimple swtch)
1337 struct switch_conv_info info;
1339 /* Group case labels so that we get the right results from the heuristics
1340 that decide on the code generation approach for this switch. */
1341 group_case_labels_stmt (swtch);
1343 /* If this switch is now a degenerate case with only a default label,
1344 there is nothing left for us to do. */
1345 if (gimple_switch_num_labels (swtch) < 2)
1346 return "switch is a degenerate case";
1348 collect_switch_conv_info (swtch, &info);
1350 /* No error markers should reach here (they should be filtered out
1351 during gimplification). */
1352 gcc_checking_assert (TREE_TYPE (info.index_expr) != error_mark_node);
1354 /* A switch on a constant should have been optimized in tree-cfg-cleanup. */
1355 gcc_checking_assert (! TREE_CONSTANT (info.index_expr));
1357 if (info.uniq <= MAX_CASE_BIT_TESTS)
1359 if (expand_switch_using_bit_tests_p (info.range_size,
1360 info.uniq, info.count))
1362 if (dump_file)
1363 fputs (" expanding as bit test is preferable\n", dump_file);
1364 emit_case_bit_tests (swtch, info.index_expr,
1365 info.range_min, info.range_size);
1366 if (current_loops)
1367 loops_state_set (LOOPS_NEED_FIXUP);
1368 return NULL;
1371 if (info.uniq <= 2)
1372 /* This will be expanded as a decision tree in stmt.c:expand_case. */
1373 return " expanding as jumps is preferable";
1376 /* If there is no common successor, we cannot do the transformation. */
1377 if (! info.final_bb)
1378 return "no common successor to all case label target blocks found";
1380 /* Check the case label values are within reasonable range: */
1381 if (!check_range (&info))
1383 gcc_assert (info.reason);
1384 return info.reason;
1387 /* For all the cases, see whether they are empty, the assignments they
1388 represent constant and so on... */
1389 if (! check_all_empty_except_final (&info))
1391 gcc_assert (info.reason);
1392 return info.reason;
1394 if (!check_final_bb (&info))
1396 gcc_assert (info.reason);
1397 return info.reason;
1400 /* At this point all checks have passed and we can proceed with the
1401 transformation. */
1403 create_temp_arrays (&info);
1404 gather_default_values (gimple_switch_default_label (swtch), &info);
1405 build_constructors (swtch, &info);
1407 build_arrays (swtch, &info); /* Build the static arrays and assignments. */
1408 gen_inbound_check (swtch, &info); /* Build the bounds check. */
1410 /* Cleanup: */
1411 free_temp_arrays (&info);
1412 return NULL;
1415 /* The main function of the pass scans statements for switches and invokes
1416 process_switch on them. */
1418 static unsigned int
1419 do_switchconv (void)
1421 basic_block bb;
1423 FOR_EACH_BB_FN (bb, cfun)
1425 const char *failure_reason;
1426 gimple stmt = last_stmt (bb);
1427 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
1429 if (dump_file)
1431 expanded_location loc = expand_location (gimple_location (stmt));
1433 fprintf (dump_file, "beginning to process the following "
1434 "SWITCH statement (%s:%d) : ------- \n",
1435 loc.file, loc.line);
1436 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1437 putc ('\n', dump_file);
1440 failure_reason = process_switch (stmt);
1441 if (! failure_reason)
1443 if (dump_file)
1445 fputs ("Switch converted\n", dump_file);
1446 fputs ("--------------------------------\n", dump_file);
1449 /* Make no effort to update the post-dominator tree. It is actually not
1450 that hard for the transformations we have performed, but it is not
1451 supported by iterate_fix_dominators. */
1452 free_dominance_info (CDI_POST_DOMINATORS);
1454 else
1456 if (dump_file)
1458 fputs ("Bailing out - ", dump_file);
1459 fputs (failure_reason, dump_file);
1460 fputs ("\n--------------------------------\n", dump_file);
1466 return 0;
1469 /* The pass gate. */
1471 static bool
1472 switchconv_gate (void)
1474 return flag_tree_switch_conversion != 0;
1477 namespace {
1479 const pass_data pass_data_convert_switch =
1481 GIMPLE_PASS, /* type */
1482 "switchconv", /* name */
1483 OPTGROUP_NONE, /* optinfo_flags */
1484 true, /* has_gate */
1485 true, /* has_execute */
1486 TV_TREE_SWITCH_CONVERSION, /* tv_id */
1487 ( PROP_cfg | PROP_ssa ), /* properties_required */
1488 0, /* properties_provided */
1489 0, /* properties_destroyed */
1490 0, /* todo_flags_start */
1491 ( TODO_update_ssa | TODO_verify_ssa
1492 | TODO_verify_stmts
1493 | TODO_verify_flow ), /* todo_flags_finish */
1496 class pass_convert_switch : public gimple_opt_pass
1498 public:
1499 pass_convert_switch (gcc::context *ctxt)
1500 : gimple_opt_pass (pass_data_convert_switch, ctxt)
1503 /* opt_pass methods: */
1504 bool gate () { return switchconv_gate (); }
1505 unsigned int execute () { return do_switchconv (); }
1507 }; // class pass_convert_switch
1509 } // anon namespace
1511 gimple_opt_pass *
1512 make_pass_convert_switch (gcc::context *ctxt)
1514 return new pass_convert_switch (ctxt);