PR c/79855: add full stop to store merging param descriptions
[official-gcc.git] / gcc / tree-switch-conversion.c
blobce1d11dca39f4400ff2438c51d3c081381ad245e
1 /* Lower GIMPLE_SWITCH expressions to something more efficient than
2 a jump table.
3 Copyright (C) 2006-2017 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
10 later version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA. */
22 /* This file handles the lowering of GIMPLE_SWITCH to an indexed
23 load, or a series of bit-test-and-branch expressions. */
25 #include "config.h"
26 #include "system.h"
27 #include "coretypes.h"
28 #include "backend.h"
29 #include "insn-codes.h"
30 #include "rtl.h"
31 #include "tree.h"
32 #include "gimple.h"
33 #include "cfghooks.h"
34 #include "tree-pass.h"
35 #include "ssa.h"
36 #include "optabs-tree.h"
37 #include "cgraph.h"
38 #include "gimple-pretty-print.h"
39 #include "params.h"
40 #include "fold-const.h"
41 #include "varasm.h"
42 #include "stor-layout.h"
43 #include "cfganal.h"
44 #include "gimplify.h"
45 #include "gimple-iterator.h"
46 #include "gimplify-me.h"
47 #include "tree-cfg.h"
48 #include "cfgloop.h"
50 /* ??? For lang_hooks.types.type_for_mode, but is there a word_mode
51 type in the GIMPLE type system that is language-independent? */
52 #include "langhooks.h"
55 /* Maximum number of case bit tests.
56 FIXME: This should be derived from PARAM_CASE_VALUES_THRESHOLD and
57 targetm.case_values_threshold(), or be its own param. */
58 #define MAX_CASE_BIT_TESTS 3
60 /* Split the basic block at the statement pointed to by GSIP, and insert
61 a branch to the target basic block of E_TRUE conditional on tree
62 expression COND.
64 It is assumed that there is already an edge from the to-be-split
65 basic block to E_TRUE->dest block. This edge is removed, and the
66 profile information on the edge is re-used for the new conditional
67 jump.
69 The CFG is updated. The dominator tree will not be valid after
70 this transformation, but the immediate dominators are updated if
71 UPDATE_DOMINATORS is true.
73 Returns the newly created basic block. */
75 static basic_block
76 hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
77 tree cond, edge e_true,
78 bool update_dominators)
80 tree tmp;
81 gcond *cond_stmt;
82 edge e_false;
83 basic_block new_bb, split_bb = gsi_bb (*gsip);
84 bool dominated_e_true = false;
86 gcc_assert (e_true->src == split_bb);
88 if (update_dominators
89 && get_immediate_dominator (CDI_DOMINATORS, e_true->dest) == split_bb)
90 dominated_e_true = true;
92 tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL,
93 /*before=*/true, GSI_SAME_STMT);
94 cond_stmt = gimple_build_cond_from_tree (tmp, NULL_TREE, NULL_TREE);
95 gsi_insert_before (gsip, cond_stmt, GSI_SAME_STMT);
97 e_false = split_block (split_bb, cond_stmt);
98 new_bb = e_false->dest;
99 redirect_edge_pred (e_true, split_bb);
101 e_true->flags &= ~EDGE_FALLTHRU;
102 e_true->flags |= EDGE_TRUE_VALUE;
104 e_false->flags &= ~EDGE_FALLTHRU;
105 e_false->flags |= EDGE_FALSE_VALUE;
106 e_false->probability = REG_BR_PROB_BASE - e_true->probability;
107 e_false->count = split_bb->count - e_true->count;
108 new_bb->count = e_false->count;
110 if (update_dominators)
112 if (dominated_e_true)
113 set_immediate_dominator (CDI_DOMINATORS, e_true->dest, split_bb);
114 set_immediate_dominator (CDI_DOMINATORS, e_false->dest, split_bb);
117 return new_bb;
121 /* Return true if a switch should be expanded as a bit test.
122 RANGE is the difference between highest and lowest case.
123 UNIQ is number of unique case node targets, not counting the default case.
124 COUNT is the number of comparisons needed, not counting the default case. */
126 static bool
127 expand_switch_using_bit_tests_p (tree range,
128 unsigned int uniq,
129 unsigned int count, bool speed_p)
131 return (((uniq == 1 && count >= 3)
132 || (uniq == 2 && count >= 5)
133 || (uniq == 3 && count >= 6))
134 && lshift_cheap_p (speed_p)
135 && compare_tree_int (range, GET_MODE_BITSIZE (word_mode)) < 0
136 && compare_tree_int (range, 0) > 0);
139 /* Implement switch statements with bit tests
141 A GIMPLE switch statement can be expanded to a short sequence of bit-wise
142 comparisons. "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)"
143 where CST and MINVAL are integer constants. This is better than a series
144 of compare-and-banch insns in some cases, e.g. we can implement:
146 if ((x==4) || (x==6) || (x==9) || (x==11))
148 as a single bit test:
150 if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11)))
152 This transformation is only applied if the number of case targets is small,
153 if CST constains at least 3 bits, and "1 << x" is cheap. The bit tests are
154 performed in "word_mode".
156 The following example shows the code the transformation generates:
158 int bar(int x)
160 switch (x)
162 case '0': case '1': case '2': case '3': case '4':
163 case '5': case '6': case '7': case '8': case '9':
164 case 'A': case 'B': case 'C': case 'D': case 'E':
165 case 'F':
166 return 1;
168 return 0;
173 bar (int x)
175 tmp1 = x - 48;
176 if (tmp1 > (70 - 48)) goto L2;
177 tmp2 = 1 << tmp1;
178 tmp3 = 0b11111100000001111111111;
179 if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2;
181 return 1;
183 return 0;
186 TODO: There are still some improvements to this transformation that could
187 be implemented:
189 * A narrower mode than word_mode could be used if that is cheaper, e.g.
190 for x86_64 where a narrower-mode shift may result in smaller code.
192 * The compounded constant could be shifted rather than the one. The
193 test would be either on the sign bit or on the least significant bit,
194 depending on the direction of the shift. On some machines, the test
195 for the branch would be free if the bit to test is already set by the
196 shift operation.
198 This transformation was contributed by Roger Sayle, see this e-mail:
199 http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html
202 /* A case_bit_test represents a set of case nodes that may be
203 selected from using a bit-wise comparison. HI and LO hold
204 the integer to be tested against, TARGET_EDGE contains the
205 edge to the basic block to jump to upon success and BITS
206 counts the number of case nodes handled by this test,
207 typically the number of bits set in HI:LO. The LABEL field
208 is used to quickly identify all cases in this set without
209 looking at label_to_block for every case label. */
211 struct case_bit_test
213 wide_int mask;
214 edge target_edge;
215 tree label;
216 int bits;
219 /* Comparison function for qsort to order bit tests by decreasing
220 probability of execution. Our best guess comes from a measured
221 profile. If the profile counts are equal, break even on the
222 number of case nodes, i.e. the node with the most cases gets
223 tested first.
225 TODO: Actually this currently runs before a profile is available.
226 Therefore the case-as-bit-tests transformation should be done
227 later in the pass pipeline, or something along the lines of
228 "Efficient and effective branch reordering using profile data"
229 (Yang et. al., 2002) should be implemented (although, how good
230 is a paper is called "Efficient and effective ..." when the
231 latter is implied by the former, but oh well...). */
233 static int
234 case_bit_test_cmp (const void *p1, const void *p2)
236 const struct case_bit_test *const d1 = (const struct case_bit_test *) p1;
237 const struct case_bit_test *const d2 = (const struct case_bit_test *) p2;
239 if (d2->target_edge->count != d1->target_edge->count)
240 return d2->target_edge->count - d1->target_edge->count;
241 if (d2->bits != d1->bits)
242 return d2->bits - d1->bits;
244 /* Stabilize the sort. */
245 return LABEL_DECL_UID (d2->label) - LABEL_DECL_UID (d1->label);
248 /* Expand a switch statement by a short sequence of bit-wise
249 comparisons. "switch(x)" is effectively converted into
250 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
251 integer constants.
253 INDEX_EXPR is the value being switched on.
255 MINVAL is the lowest case value of in the case nodes,
256 and RANGE is highest value minus MINVAL. MINVAL and RANGE
257 are not guaranteed to be of the same type as INDEX_EXPR
258 (the gimplifier doesn't change the type of case label values,
259 and MINVAL and RANGE are derived from those values).
260 MAXVAL is MINVAL + RANGE.
262 There *MUST* be MAX_CASE_BIT_TESTS or less unique case
263 node targets. */
265 static void
266 emit_case_bit_tests (gswitch *swtch, tree index_expr,
267 tree minval, tree range, tree maxval)
269 struct case_bit_test test[MAX_CASE_BIT_TESTS];
270 unsigned int i, j, k;
271 unsigned int count;
273 basic_block switch_bb = gimple_bb (swtch);
274 basic_block default_bb, new_default_bb, new_bb;
275 edge default_edge;
276 bool update_dom = dom_info_available_p (CDI_DOMINATORS);
278 vec<basic_block> bbs_to_fix_dom = vNULL;
280 tree index_type = TREE_TYPE (index_expr);
281 tree unsigned_index_type = unsigned_type_for (index_type);
282 unsigned int branch_num = gimple_switch_num_labels (swtch);
284 gimple_stmt_iterator gsi;
285 gassign *shift_stmt;
287 tree idx, tmp, csui;
288 tree word_type_node = lang_hooks.types.type_for_mode (word_mode, 1);
289 tree word_mode_zero = fold_convert (word_type_node, integer_zero_node);
290 tree word_mode_one = fold_convert (word_type_node, integer_one_node);
291 int prec = TYPE_PRECISION (word_type_node);
292 wide_int wone = wi::one (prec);
294 memset (&test, 0, sizeof (test));
296 /* Get the edge for the default case. */
297 tmp = gimple_switch_default_label (swtch);
298 default_bb = label_to_block (CASE_LABEL (tmp));
299 default_edge = find_edge (switch_bb, default_bb);
301 /* Go through all case labels, and collect the case labels, profile
302 counts, and other information we need to build the branch tests. */
303 count = 0;
304 for (i = 1; i < branch_num; i++)
306 unsigned int lo, hi;
307 tree cs = gimple_switch_label (swtch, i);
308 tree label = CASE_LABEL (cs);
309 edge e = find_edge (switch_bb, label_to_block (label));
310 for (k = 0; k < count; k++)
311 if (e == test[k].target_edge)
312 break;
314 if (k == count)
316 gcc_checking_assert (count < MAX_CASE_BIT_TESTS);
317 test[k].mask = wi::zero (prec);
318 test[k].target_edge = e;
319 test[k].label = label;
320 test[k].bits = 1;
321 count++;
323 else
324 test[k].bits++;
326 lo = tree_to_uhwi (int_const_binop (MINUS_EXPR,
327 CASE_LOW (cs), minval));
328 if (CASE_HIGH (cs) == NULL_TREE)
329 hi = lo;
330 else
331 hi = tree_to_uhwi (int_const_binop (MINUS_EXPR,
332 CASE_HIGH (cs), minval));
334 for (j = lo; j <= hi; j++)
335 test[k].mask |= wi::lshift (wone, j);
338 qsort (test, count, sizeof (*test), case_bit_test_cmp);
340 /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of
341 the minval subtractions, but it might make the mask constants more
342 expensive. So, compare the costs. */
343 if (compare_tree_int (minval, 0) > 0
344 && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
346 int cost_diff;
347 HOST_WIDE_INT m = tree_to_uhwi (minval);
348 rtx reg = gen_raw_REG (word_mode, 10000);
349 bool speed_p = optimize_bb_for_speed_p (gimple_bb (swtch));
350 cost_diff = set_rtx_cost (gen_rtx_PLUS (word_mode, reg,
351 GEN_INT (-m)), speed_p);
352 for (i = 0; i < count; i++)
354 rtx r = immed_wide_int_const (test[i].mask, word_mode);
355 cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r),
356 word_mode, speed_p);
357 r = immed_wide_int_const (wi::lshift (test[i].mask, m), word_mode);
358 cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r),
359 word_mode, speed_p);
361 if (cost_diff > 0)
363 for (i = 0; i < count; i++)
364 test[i].mask = wi::lshift (test[i].mask, m);
365 minval = build_zero_cst (TREE_TYPE (minval));
366 range = maxval;
370 /* We generate two jumps to the default case label.
371 Split the default edge, so that we don't have to do any PHI node
372 updating. */
373 new_default_bb = split_edge (default_edge);
375 if (update_dom)
377 bbs_to_fix_dom.create (10);
378 bbs_to_fix_dom.quick_push (switch_bb);
379 bbs_to_fix_dom.quick_push (default_bb);
380 bbs_to_fix_dom.quick_push (new_default_bb);
383 /* Now build the test-and-branch code. */
385 gsi = gsi_last_bb (switch_bb);
387 /* idx = (unsigned)x - minval. */
388 idx = fold_convert (unsigned_index_type, index_expr);
389 idx = fold_build2 (MINUS_EXPR, unsigned_index_type, idx,
390 fold_convert (unsigned_index_type, minval));
391 idx = force_gimple_operand_gsi (&gsi, idx,
392 /*simple=*/true, NULL_TREE,
393 /*before=*/true, GSI_SAME_STMT);
395 /* if (idx > range) goto default */
396 range = force_gimple_operand_gsi (&gsi,
397 fold_convert (unsigned_index_type, range),
398 /*simple=*/true, NULL_TREE,
399 /*before=*/true, GSI_SAME_STMT);
400 tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range);
401 new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, default_edge, update_dom);
402 if (update_dom)
403 bbs_to_fix_dom.quick_push (new_bb);
404 gcc_assert (gimple_bb (swtch) == new_bb);
405 gsi = gsi_last_bb (new_bb);
407 /* Any blocks dominated by the GIMPLE_SWITCH, but that are not successors
408 of NEW_BB, are still immediately dominated by SWITCH_BB. Make it so. */
409 if (update_dom)
411 vec<basic_block> dom_bbs;
412 basic_block dom_son;
414 dom_bbs = get_dominated_by (CDI_DOMINATORS, new_bb);
415 FOR_EACH_VEC_ELT (dom_bbs, i, dom_son)
417 edge e = find_edge (new_bb, dom_son);
418 if (e && single_pred_p (e->dest))
419 continue;
420 set_immediate_dominator (CDI_DOMINATORS, dom_son, switch_bb);
421 bbs_to_fix_dom.safe_push (dom_son);
423 dom_bbs.release ();
426 /* csui = (1 << (word_mode) idx) */
427 csui = make_ssa_name (word_type_node);
428 tmp = fold_build2 (LSHIFT_EXPR, word_type_node, word_mode_one,
429 fold_convert (word_type_node, idx));
430 tmp = force_gimple_operand_gsi (&gsi, tmp,
431 /*simple=*/false, NULL_TREE,
432 /*before=*/true, GSI_SAME_STMT);
433 shift_stmt = gimple_build_assign (csui, tmp);
434 gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT);
435 update_stmt (shift_stmt);
437 /* for each unique set of cases:
438 if (const & csui) goto target */
439 for (k = 0; k < count; k++)
441 tmp = wide_int_to_tree (word_type_node, test[k].mask);
442 tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp);
443 tmp = force_gimple_operand_gsi (&gsi, tmp,
444 /*simple=*/true, NULL_TREE,
445 /*before=*/true, GSI_SAME_STMT);
446 tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero);
447 new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_edge,
448 update_dom);
449 if (update_dom)
450 bbs_to_fix_dom.safe_push (new_bb);
451 gcc_assert (gimple_bb (swtch) == new_bb);
452 gsi = gsi_last_bb (new_bb);
455 /* We should have removed all edges now. */
456 gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0);
458 /* If nothing matched, go to the default label. */
459 make_edge (gsi_bb (gsi), new_default_bb, EDGE_FALLTHRU);
461 /* The GIMPLE_SWITCH is now redundant. */
462 gsi_remove (&gsi, true);
464 if (update_dom)
466 /* Fix up the dominator tree. */
467 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
468 bbs_to_fix_dom.release ();
473 Switch initialization conversion
475 The following pass changes simple initializations of scalars in a switch
476 statement into initializations from a static array. Obviously, the values
477 must be constant and known at compile time and a default branch must be
478 provided. For example, the following code:
480 int a,b;
482 switch (argc)
484 case 1:
485 case 2:
486 a_1 = 8;
487 b_1 = 6;
488 break;
489 case 3:
490 a_2 = 9;
491 b_2 = 5;
492 break;
493 case 12:
494 a_3 = 10;
495 b_3 = 4;
496 break;
497 default:
498 a_4 = 16;
499 b_4 = 1;
500 break;
502 a_5 = PHI <a_1, a_2, a_3, a_4>
503 b_5 = PHI <b_1, b_2, b_3, b_4>
506 is changed into:
508 static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
509 static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
510 16, 16, 10};
512 if (((unsigned) argc) - 1 < 11)
514 a_6 = CSWTCH02[argc - 1];
515 b_6 = CSWTCH01[argc - 1];
517 else
519 a_7 = 16;
520 b_7 = 1;
522 a_5 = PHI <a_6, a_7>
523 b_b = PHI <b_6, b_7>
525 There are further constraints. Specifically, the range of values across all
526 case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
527 eight) times the number of the actual switch branches.
529 This transformation was contributed by Martin Jambor, see this e-mail:
530 http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */
532 /* The main structure of the pass. */
533 struct switch_conv_info
535 /* The expression used to decide the switch branch. */
536 tree index_expr;
538 /* The following integer constants store the minimum and maximum value
539 covered by the case labels. */
540 tree range_min;
541 tree range_max;
543 /* The difference between the above two numbers. Stored here because it
544 is used in all the conversion heuristics, as well as for some of the
545 transformation, and it is expensive to re-compute it all the time. */
546 tree range_size;
548 /* Basic block that contains the actual GIMPLE_SWITCH. */
549 basic_block switch_bb;
551 /* Basic block that is the target of the default case. */
552 basic_block default_bb;
554 /* The single successor block of all branches out of the GIMPLE_SWITCH,
555 if such a block exists. Otherwise NULL. */
556 basic_block final_bb;
558 /* The probability of the default edge in the replaced switch. */
559 int default_prob;
561 /* The count of the default edge in the replaced switch. */
562 gcov_type default_count;
564 /* Combined count of all other (non-default) edges in the replaced switch. */
565 gcov_type other_count;
567 /* Number of phi nodes in the final bb (that we'll be replacing). */
568 int phi_count;
570 /* Array of default values, in the same order as phi nodes. */
571 tree *default_values;
573 /* Constructors of new static arrays. */
574 vec<constructor_elt, va_gc> **constructors;
576 /* Array of ssa names that are initialized with a value from a new static
577 array. */
578 tree *target_inbound_names;
580 /* Array of ssa names that are initialized with the default value if the
581 switch expression is out of range. */
582 tree *target_outbound_names;
584 /* The first load statement that loads a temporary from a new static array.
586 gimple *arr_ref_first;
588 /* The last load statement that loads a temporary from a new static array. */
589 gimple *arr_ref_last;
591 /* String reason why the case wasn't a good candidate that is written to the
592 dump file, if there is one. */
593 const char *reason;
595 /* Parameters for expand_switch_using_bit_tests. Should be computed
596 the same way as in expand_case. */
597 unsigned int uniq;
598 unsigned int count;
601 /* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */
603 static void
604 collect_switch_conv_info (gswitch *swtch, struct switch_conv_info *info)
606 unsigned int branch_num = gimple_switch_num_labels (swtch);
607 tree min_case, max_case;
608 unsigned int count, i;
609 edge e, e_default;
610 edge_iterator ei;
612 memset (info, 0, sizeof (*info));
614 /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
615 is a default label which is the first in the vector.
616 Collect the bits we can deduce from the CFG. */
617 info->index_expr = gimple_switch_index (swtch);
618 info->switch_bb = gimple_bb (swtch);
619 info->default_bb =
620 label_to_block (CASE_LABEL (gimple_switch_default_label (swtch)));
621 e_default = find_edge (info->switch_bb, info->default_bb);
622 info->default_prob = e_default->probability;
623 info->default_count = e_default->count;
624 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
625 if (e != e_default)
626 info->other_count += e->count;
628 /* See if there is one common successor block for all branch
629 targets. If it exists, record it in FINAL_BB.
630 Start with the destination of the default case as guess
631 or its destination in case it is a forwarder block. */
632 if (! single_pred_p (e_default->dest))
633 info->final_bb = e_default->dest;
634 else if (single_succ_p (e_default->dest)
635 && ! single_pred_p (single_succ (e_default->dest)))
636 info->final_bb = single_succ (e_default->dest);
637 /* Require that all switch destinations are either that common
638 FINAL_BB or a forwarder to it. */
639 if (info->final_bb)
640 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
642 if (e->dest == info->final_bb)
643 continue;
645 if (single_pred_p (e->dest)
646 && single_succ_p (e->dest)
647 && single_succ (e->dest) == info->final_bb)
648 continue;
650 info->final_bb = NULL;
651 break;
654 /* Get upper and lower bounds of case values, and the covered range. */
655 min_case = gimple_switch_label (swtch, 1);
656 max_case = gimple_switch_label (swtch, branch_num - 1);
658 info->range_min = CASE_LOW (min_case);
659 if (CASE_HIGH (max_case) != NULL_TREE)
660 info->range_max = CASE_HIGH (max_case);
661 else
662 info->range_max = CASE_LOW (max_case);
664 info->range_size =
665 int_const_binop (MINUS_EXPR, info->range_max, info->range_min);
667 /* Get a count of the number of case labels. Single-valued case labels
668 simply count as one, but a case range counts double, since it may
669 require two compares if it gets lowered as a branching tree. */
670 count = 0;
671 for (i = 1; i < branch_num; i++)
673 tree elt = gimple_switch_label (swtch, i);
674 count++;
675 if (CASE_HIGH (elt)
676 && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt)))
677 count++;
679 info->count = count;
681 /* Get the number of unique non-default targets out of the GIMPLE_SWITCH
682 block. Assume a CFG cleanup would have already removed degenerate
683 switch statements, this allows us to just use EDGE_COUNT. */
684 info->uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1;
687 /* Checks whether the range given by individual case statements of the SWTCH
688 switch statement isn't too big and whether the number of branches actually
689 satisfies the size of the new array. */
691 static bool
692 check_range (struct switch_conv_info *info)
694 gcc_assert (info->range_size);
695 if (!tree_fits_uhwi_p (info->range_size))
697 info->reason = "index range way too large or otherwise unusable";
698 return false;
701 if (tree_to_uhwi (info->range_size)
702 > ((unsigned) info->count * SWITCH_CONVERSION_BRANCH_RATIO))
704 info->reason = "the maximum range-branch ratio exceeded";
705 return false;
708 return true;
711 /* Checks whether all but the FINAL_BB basic blocks are empty. */
713 static bool
714 check_all_empty_except_final (struct switch_conv_info *info)
716 edge e;
717 edge_iterator ei;
719 FOR_EACH_EDGE (e, ei, info->switch_bb->succs)
721 if (e->dest == info->final_bb)
722 continue;
724 if (!empty_block_p (e->dest))
726 info->reason = "bad case - a non-final BB not empty";
727 return false;
731 return true;
734 /* This function checks whether all required values in phi nodes in final_bb
735 are constants. Required values are those that correspond to a basic block
736 which is a part of the examined switch statement. It returns true if the
737 phi nodes are OK, otherwise false. */
739 static bool
740 check_final_bb (struct switch_conv_info *info)
742 gphi_iterator gsi;
744 info->phi_count = 0;
745 for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
747 gphi *phi = gsi.phi ();
748 unsigned int i;
750 info->phi_count++;
752 for (i = 0; i < gimple_phi_num_args (phi); i++)
754 basic_block bb = gimple_phi_arg_edge (phi, i)->src;
756 if (bb == info->switch_bb
757 || (single_pred_p (bb) && single_pred (bb) == info->switch_bb))
759 tree reloc, val;
761 val = gimple_phi_arg_def (phi, i);
762 if (!is_gimple_ip_invariant (val))
764 info->reason = "non-invariant value from a case";
765 return false; /* Non-invariant argument. */
767 reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
768 if ((flag_pic && reloc != null_pointer_node)
769 || (!flag_pic && reloc == NULL_TREE))
771 if (reloc)
772 info->reason
773 = "value from a case would need runtime relocations";
774 else
775 info->reason
776 = "value from a case is not a valid initializer";
777 return false;
783 return true;
786 /* The following function allocates default_values, target_{in,out}_names and
787 constructors arrays. The last one is also populated with pointers to
788 vectors that will become constructors of new arrays. */
790 static void
791 create_temp_arrays (struct switch_conv_info *info)
793 int i;
795 info->default_values = XCNEWVEC (tree, info->phi_count * 3);
796 /* ??? Macros do not support multi argument templates in their
797 argument list. We create a typedef to work around that problem. */
798 typedef vec<constructor_elt, va_gc> *vec_constructor_elt_gc;
799 info->constructors = XCNEWVEC (vec_constructor_elt_gc, info->phi_count);
800 info->target_inbound_names = info->default_values + info->phi_count;
801 info->target_outbound_names = info->target_inbound_names + info->phi_count;
802 for (i = 0; i < info->phi_count; i++)
803 vec_alloc (info->constructors[i], tree_to_uhwi (info->range_size) + 1);
806 /* Free the arrays created by create_temp_arrays(). The vectors that are
807 created by that function are not freed here, however, because they have
808 already become constructors and must be preserved. */
810 static void
811 free_temp_arrays (struct switch_conv_info *info)
813 XDELETEVEC (info->constructors);
814 XDELETEVEC (info->default_values);
817 /* Populate the array of default values in the order of phi nodes.
818 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch. */
820 static void
821 gather_default_values (tree default_case, struct switch_conv_info *info)
823 gphi_iterator gsi;
824 basic_block bb = label_to_block (CASE_LABEL (default_case));
825 edge e;
826 int i = 0;
828 gcc_assert (CASE_LOW (default_case) == NULL_TREE);
830 if (bb == info->final_bb)
831 e = find_edge (info->switch_bb, bb);
832 else
833 e = single_succ_edge (bb);
835 for (gsi = gsi_start_phis (info->final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
837 gphi *phi = gsi.phi ();
838 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
839 gcc_assert (val);
840 info->default_values[i++] = val;
844 /* The following function populates the vectors in the constructors array with
845 future contents of the static arrays. The vectors are populated in the
846 order of phi nodes. SWTCH is the switch statement being converted. */
848 static void
849 build_constructors (gswitch *swtch, struct switch_conv_info *info)
851 unsigned i, branch_num = gimple_switch_num_labels (swtch);
852 tree pos = info->range_min;
854 for (i = 1; i < branch_num; i++)
856 tree cs = gimple_switch_label (swtch, i);
857 basic_block bb = label_to_block (CASE_LABEL (cs));
858 edge e;
859 tree high;
860 gphi_iterator gsi;
861 int j;
863 if (bb == info->final_bb)
864 e = find_edge (info->switch_bb, bb);
865 else
866 e = single_succ_edge (bb);
867 gcc_assert (e);
869 while (tree_int_cst_lt (pos, CASE_LOW (cs)))
871 int k;
872 for (k = 0; k < info->phi_count; k++)
874 constructor_elt elt;
876 elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
877 elt.value
878 = unshare_expr_without_location (info->default_values[k]);
879 info->constructors[k]->quick_push (elt);
882 pos = int_const_binop (PLUS_EXPR, pos,
883 build_int_cst (TREE_TYPE (pos), 1));
885 gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
887 j = 0;
888 if (CASE_HIGH (cs))
889 high = CASE_HIGH (cs);
890 else
891 high = CASE_LOW (cs);
892 for (gsi = gsi_start_phis (info->final_bb);
893 !gsi_end_p (gsi); gsi_next (&gsi))
895 gphi *phi = gsi.phi ();
896 tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
897 tree low = CASE_LOW (cs);
898 pos = CASE_LOW (cs);
902 constructor_elt elt;
904 elt.index = int_const_binop (MINUS_EXPR, pos, info->range_min);
905 elt.value = unshare_expr_without_location (val);
906 info->constructors[j]->quick_push (elt);
908 pos = int_const_binop (PLUS_EXPR, pos,
909 build_int_cst (TREE_TYPE (pos), 1));
910 } while (!tree_int_cst_lt (high, pos)
911 && tree_int_cst_lt (low, pos));
912 j++;
917 /* If all values in the constructor vector are the same, return the value.
918 Otherwise return NULL_TREE. Not supposed to be called for empty
919 vectors. */
921 static tree
922 constructor_contains_same_values_p (vec<constructor_elt, va_gc> *vec)
924 unsigned int i;
925 tree prev = NULL_TREE;
926 constructor_elt *elt;
928 FOR_EACH_VEC_SAFE_ELT (vec, i, elt)
930 if (!prev)
931 prev = elt->value;
932 else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST))
933 return NULL_TREE;
935 return prev;
938 /* Return type which should be used for array elements, either TYPE,
939 or for integral type some smaller integral type that can still hold
940 all the constants. */
942 static tree
943 array_value_type (gswitch *swtch, tree type, int num,
944 struct switch_conv_info *info)
946 unsigned int i, len = vec_safe_length (info->constructors[num]);
947 constructor_elt *elt;
948 machine_mode mode;
949 int sign = 0;
950 tree smaller_type;
952 if (!INTEGRAL_TYPE_P (type))
953 return type;
955 mode = GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type)));
956 if (GET_MODE_SIZE (TYPE_MODE (type)) <= GET_MODE_SIZE (mode))
957 return type;
959 if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32))
960 return type;
962 FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
964 wide_int cst;
966 if (TREE_CODE (elt->value) != INTEGER_CST)
967 return type;
969 cst = elt->value;
970 while (1)
972 unsigned int prec = GET_MODE_BITSIZE (mode);
973 if (prec > HOST_BITS_PER_WIDE_INT)
974 return type;
976 if (sign >= 0 && cst == wi::zext (cst, prec))
978 if (sign == 0 && cst == wi::sext (cst, prec))
979 break;
980 sign = 1;
981 break;
983 if (sign <= 0 && cst == wi::sext (cst, prec))
985 sign = -1;
986 break;
989 if (sign == 1)
990 sign = 0;
992 mode = GET_MODE_WIDER_MODE (mode);
993 if (mode == VOIDmode
994 || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (TYPE_MODE (type)))
995 return type;
999 if (sign == 0)
1000 sign = TYPE_UNSIGNED (type) ? 1 : -1;
1001 smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0);
1002 if (GET_MODE_SIZE (TYPE_MODE (type))
1003 <= GET_MODE_SIZE (TYPE_MODE (smaller_type)))
1004 return type;
1006 return smaller_type;
1009 /* Create an appropriate array type and declaration and assemble a static array
1010 variable. Also create a load statement that initializes the variable in
1011 question with a value from the static array. SWTCH is the switch statement
1012 being converted, NUM is the index to arrays of constructors, default values
1013 and target SSA names for this particular array. ARR_INDEX_TYPE is the type
1014 of the index of the new array, PHI is the phi node of the final BB that
1015 corresponds to the value that will be loaded from the created array. TIDX
1016 is an ssa name of a temporary variable holding the index for loads from the
1017 new array. */
1019 static void
1020 build_one_array (gswitch *swtch, int num, tree arr_index_type,
1021 gphi *phi, tree tidx, struct switch_conv_info *info)
1023 tree name, cst;
1024 gimple *load;
1025 gimple_stmt_iterator gsi = gsi_for_stmt (swtch);
1026 location_t loc = gimple_location (swtch);
1028 gcc_assert (info->default_values[num]);
1030 name = copy_ssa_name (PHI_RESULT (phi));
1031 info->target_inbound_names[num] = name;
1033 cst = constructor_contains_same_values_p (info->constructors[num]);
1034 if (cst)
1035 load = gimple_build_assign (name, cst);
1036 else
1038 tree array_type, ctor, decl, value_type, fetch, default_type;
1040 default_type = TREE_TYPE (info->default_values[num]);
1041 value_type = array_value_type (swtch, default_type, num, info);
1042 array_type = build_array_type (value_type, arr_index_type);
1043 if (default_type != value_type)
1045 unsigned int i;
1046 constructor_elt *elt;
1048 FOR_EACH_VEC_SAFE_ELT (info->constructors[num], i, elt)
1049 elt->value = fold_convert (value_type, elt->value);
1051 ctor = build_constructor (array_type, info->constructors[num]);
1052 TREE_CONSTANT (ctor) = true;
1053 TREE_STATIC (ctor) = true;
1055 decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type);
1056 TREE_STATIC (decl) = 1;
1057 DECL_INITIAL (decl) = ctor;
1059 DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
1060 DECL_ARTIFICIAL (decl) = 1;
1061 DECL_IGNORED_P (decl) = 1;
1062 TREE_CONSTANT (decl) = 1;
1063 TREE_READONLY (decl) = 1;
1064 DECL_IGNORED_P (decl) = 1;
1065 varpool_node::finalize_decl (decl);
1067 fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
1068 NULL_TREE);
1069 if (default_type != value_type)
1071 fetch = fold_convert (default_type, fetch);
1072 fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE,
1073 true, GSI_SAME_STMT);
1075 load = gimple_build_assign (name, fetch);
1078 gsi_insert_before (&gsi, load, GSI_SAME_STMT);
1079 update_stmt (load);
1080 info->arr_ref_last = load;
1083 /* Builds and initializes static arrays initialized with values gathered from
1084 the SWTCH switch statement. Also creates statements that load values from
1085 them. */
1087 static void
1088 build_arrays (gswitch *swtch, struct switch_conv_info *info)
1090 tree arr_index_type;
1091 tree tidx, sub, utype;
1092 gimple *stmt;
1093 gimple_stmt_iterator gsi;
1094 gphi_iterator gpi;
1095 int i;
1096 location_t loc = gimple_location (swtch);
1098 gsi = gsi_for_stmt (swtch);
1100 /* Make sure we do not generate arithmetics in a subrange. */
1101 utype = TREE_TYPE (info->index_expr);
1102 if (TREE_TYPE (utype))
1103 utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1);
1104 else
1105 utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
1107 arr_index_type = build_index_type (info->range_size);
1108 tidx = make_ssa_name (utype);
1109 sub = fold_build2_loc (loc, MINUS_EXPR, utype,
1110 fold_convert_loc (loc, utype, info->index_expr),
1111 fold_convert_loc (loc, utype, info->range_min));
1112 sub = force_gimple_operand_gsi (&gsi, sub,
1113 false, NULL, true, GSI_SAME_STMT);
1114 stmt = gimple_build_assign (tidx, sub);
1116 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1117 update_stmt (stmt);
1118 info->arr_ref_first = stmt;
1120 for (gpi = gsi_start_phis (info->final_bb), i = 0;
1121 !gsi_end_p (gpi); gsi_next (&gpi), i++)
1122 build_one_array (swtch, i, arr_index_type, gpi.phi (), tidx, info);
1125 /* Generates and appropriately inserts loads of default values at the position
1126 given by BSI. Returns the last inserted statement. */
1128 static gassign *
1129 gen_def_assigns (gimple_stmt_iterator *gsi, struct switch_conv_info *info)
1131 int i;
1132 gassign *assign = NULL;
1134 for (i = 0; i < info->phi_count; i++)
1136 tree name = copy_ssa_name (info->target_inbound_names[i]);
1137 info->target_outbound_names[i] = name;
1138 assign = gimple_build_assign (name, info->default_values[i]);
1139 gsi_insert_before (gsi, assign, GSI_SAME_STMT);
1140 update_stmt (assign);
1142 return assign;
1145 /* Deletes the unused bbs and edges that now contain the switch statement and
1146 its empty branch bbs. BBD is the now dead BB containing the original switch
1147 statement, FINAL is the last BB of the converted switch statement (in terms
1148 of succession). */
1150 static void
1151 prune_bbs (basic_block bbd, basic_block final)
1153 edge_iterator ei;
1154 edge e;
1156 for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
1158 basic_block bb;
1159 bb = e->dest;
1160 remove_edge (e);
1161 if (bb != final)
1162 delete_basic_block (bb);
1164 delete_basic_block (bbd);
1167 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
1168 from the basic block loading values from an array and E2F from the basic
1169 block loading default values. BBF is the last switch basic block (see the
1170 bbf description in the comment below). */
1172 static void
1173 fix_phi_nodes (edge e1f, edge e2f, basic_block bbf,
1174 struct switch_conv_info *info)
1176 gphi_iterator gsi;
1177 int i;
1179 for (gsi = gsi_start_phis (bbf), i = 0;
1180 !gsi_end_p (gsi); gsi_next (&gsi), i++)
1182 gphi *phi = gsi.phi ();
1183 add_phi_arg (phi, info->target_inbound_names[i], e1f, UNKNOWN_LOCATION);
1184 add_phi_arg (phi, info->target_outbound_names[i], e2f, UNKNOWN_LOCATION);
1188 /* Creates a check whether the switch expression value actually falls into the
1189 range given by all the cases. If it does not, the temporaries are loaded
1190 with default values instead. SWTCH is the switch statement being converted.
1192 bb0 is the bb with the switch statement, however, we'll end it with a
1193 condition instead.
1195 bb1 is the bb to be used when the range check went ok. It is derived from
1196 the switch BB
1198 bb2 is the bb taken when the expression evaluated outside of the range
1199 covered by the created arrays. It is populated by loads of default
1200 values.
1202 bbF is a fall through for both bb1 and bb2 and contains exactly what
1203 originally followed the switch statement.
1205 bbD contains the switch statement (in the end). It is unreachable but we
1206 still need to strip off its edges.
1209 static void
1210 gen_inbound_check (gswitch *swtch, struct switch_conv_info *info)
1212 tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION);
1213 tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
1214 tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION);
1215 glabel *label1, *label2, *label3;
1216 tree utype, tidx;
1217 tree bound;
1219 gcond *cond_stmt;
1221 gassign *last_assign;
1222 gimple_stmt_iterator gsi;
1223 basic_block bb0, bb1, bb2, bbf, bbd;
1224 edge e01, e02, e21, e1d, e1f, e2f;
1225 location_t loc = gimple_location (swtch);
1227 gcc_assert (info->default_values);
1229 bb0 = gimple_bb (swtch);
1231 tidx = gimple_assign_lhs (info->arr_ref_first);
1232 utype = TREE_TYPE (tidx);
1234 /* (end of) block 0 */
1235 gsi = gsi_for_stmt (info->arr_ref_first);
1236 gsi_next (&gsi);
1238 bound = fold_convert_loc (loc, utype, info->range_size);
1239 cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
1240 gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1241 update_stmt (cond_stmt);
1243 /* block 2 */
1244 label2 = gimple_build_label (label_decl2);
1245 gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
1246 last_assign = gen_def_assigns (&gsi, info);
1248 /* block 1 */
1249 label1 = gimple_build_label (label_decl1);
1250 gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
1252 /* block F */
1253 gsi = gsi_start_bb (info->final_bb);
1254 label3 = gimple_build_label (label_decl3);
1255 gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
1257 /* cfg fix */
1258 e02 = split_block (bb0, cond_stmt);
1259 bb2 = e02->dest;
1261 e21 = split_block (bb2, last_assign);
1262 bb1 = e21->dest;
1263 remove_edge (e21);
1265 e1d = split_block (bb1, info->arr_ref_last);
1266 bbd = e1d->dest;
1267 remove_edge (e1d);
1269 /* flags and profiles of the edge for in-range values */
1270 e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
1271 e01->probability = REG_BR_PROB_BASE - info->default_prob;
1272 e01->count = info->other_count;
1274 /* flags and profiles of the edge taking care of out-of-range values */
1275 e02->flags &= ~EDGE_FALLTHRU;
1276 e02->flags |= EDGE_FALSE_VALUE;
1277 e02->probability = info->default_prob;
1278 e02->count = info->default_count;
1280 bbf = info->final_bb;
1282 e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
1283 e1f->probability = REG_BR_PROB_BASE;
1284 e1f->count = info->other_count;
1286 e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
1287 e2f->probability = REG_BR_PROB_BASE;
1288 e2f->count = info->default_count;
1290 /* frequencies of the new BBs */
1291 bb1->frequency = EDGE_FREQUENCY (e01);
1292 bb2->frequency = EDGE_FREQUENCY (e02);
1293 bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f);
1295 /* Tidy blocks that have become unreachable. */
1296 prune_bbs (bbd, info->final_bb);
1298 /* Fixup the PHI nodes in bbF. */
1299 fix_phi_nodes (e1f, e2f, bbf, info);
1301 /* Fix the dominator tree, if it is available. */
1302 if (dom_info_available_p (CDI_DOMINATORS))
1304 vec<basic_block> bbs_to_fix_dom;
1306 set_immediate_dominator (CDI_DOMINATORS, bb1, bb0);
1307 set_immediate_dominator (CDI_DOMINATORS, bb2, bb0);
1308 if (! get_immediate_dominator (CDI_DOMINATORS, bbf))
1309 /* If bbD was the immediate dominator ... */
1310 set_immediate_dominator (CDI_DOMINATORS, bbf, bb0);
1312 bbs_to_fix_dom.create (4);
1313 bbs_to_fix_dom.quick_push (bb0);
1314 bbs_to_fix_dom.quick_push (bb1);
1315 bbs_to_fix_dom.quick_push (bb2);
1316 bbs_to_fix_dom.quick_push (bbf);
1318 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
1319 bbs_to_fix_dom.release ();
1323 /* The following function is invoked on every switch statement (the current one
1324 is given in SWTCH) and runs the individual phases of switch conversion on it
1325 one after another until one fails or the conversion is completed.
1326 Returns NULL on success, or a pointer to a string with the reason why the
1327 conversion failed. */
1329 static const char *
1330 process_switch (gswitch *swtch)
1332 struct switch_conv_info info;
1334 /* Group case labels so that we get the right results from the heuristics
1335 that decide on the code generation approach for this switch. */
1336 group_case_labels_stmt (swtch);
1338 /* If this switch is now a degenerate case with only a default label,
1339 there is nothing left for us to do. */
1340 if (gimple_switch_num_labels (swtch) < 2)
1341 return "switch is a degenerate case";
1343 collect_switch_conv_info (swtch, &info);
1345 /* No error markers should reach here (they should be filtered out
1346 during gimplification). */
1347 gcc_checking_assert (TREE_TYPE (info.index_expr) != error_mark_node);
1349 /* A switch on a constant should have been optimized in tree-cfg-cleanup. */
1350 gcc_checking_assert (! TREE_CONSTANT (info.index_expr));
1352 if (info.uniq <= MAX_CASE_BIT_TESTS)
1354 if (expand_switch_using_bit_tests_p (info.range_size,
1355 info.uniq, info.count,
1356 optimize_bb_for_speed_p
1357 (gimple_bb (swtch))))
1359 if (dump_file)
1360 fputs (" expanding as bit test is preferable\n", dump_file);
1361 emit_case_bit_tests (swtch, info.index_expr, info.range_min,
1362 info.range_size, info.range_max);
1363 loops_state_set (LOOPS_NEED_FIXUP);
1364 return NULL;
1367 if (info.uniq <= 2)
1368 /* This will be expanded as a decision tree in stmt.c:expand_case. */
1369 return " expanding as jumps is preferable";
1372 /* If there is no common successor, we cannot do the transformation. */
1373 if (! info.final_bb)
1374 return "no common successor to all case label target blocks found";
1376 /* Check the case label values are within reasonable range: */
1377 if (!check_range (&info))
1379 gcc_assert (info.reason);
1380 return info.reason;
1383 /* For all the cases, see whether they are empty, the assignments they
1384 represent constant and so on... */
1385 if (! check_all_empty_except_final (&info))
1387 gcc_assert (info.reason);
1388 return info.reason;
1390 if (!check_final_bb (&info))
1392 gcc_assert (info.reason);
1393 return info.reason;
1396 /* At this point all checks have passed and we can proceed with the
1397 transformation. */
1399 create_temp_arrays (&info);
1400 gather_default_values (gimple_switch_default_label (swtch), &info);
1401 build_constructors (swtch, &info);
1403 build_arrays (swtch, &info); /* Build the static arrays and assignments. */
1404 gen_inbound_check (swtch, &info); /* Build the bounds check. */
1406 /* Cleanup: */
1407 free_temp_arrays (&info);
1408 return NULL;
1411 /* The main function of the pass scans statements for switches and invokes
1412 process_switch on them. */
1414 namespace {
1416 const pass_data pass_data_convert_switch =
1418 GIMPLE_PASS, /* type */
1419 "switchconv", /* name */
1420 OPTGROUP_NONE, /* optinfo_flags */
1421 TV_TREE_SWITCH_CONVERSION, /* tv_id */
1422 ( PROP_cfg | PROP_ssa ), /* properties_required */
1423 0, /* properties_provided */
1424 0, /* properties_destroyed */
1425 0, /* todo_flags_start */
1426 TODO_update_ssa, /* todo_flags_finish */
1429 class pass_convert_switch : public gimple_opt_pass
1431 public:
1432 pass_convert_switch (gcc::context *ctxt)
1433 : gimple_opt_pass (pass_data_convert_switch, ctxt)
1436 /* opt_pass methods: */
1437 virtual bool gate (function *) { return flag_tree_switch_conversion != 0; }
1438 virtual unsigned int execute (function *);
1440 }; // class pass_convert_switch
1442 unsigned int
1443 pass_convert_switch::execute (function *fun)
1445 basic_block bb;
1447 FOR_EACH_BB_FN (bb, fun)
1449 const char *failure_reason;
1450 gimple *stmt = last_stmt (bb);
1451 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
1453 if (dump_file)
1455 expanded_location loc = expand_location (gimple_location (stmt));
1457 fprintf (dump_file, "beginning to process the following "
1458 "SWITCH statement (%s:%d) : ------- \n",
1459 loc.file, loc.line);
1460 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1461 putc ('\n', dump_file);
1464 failure_reason = process_switch (as_a <gswitch *> (stmt));
1465 if (! failure_reason)
1467 if (dump_file)
1469 fputs ("Switch converted\n", dump_file);
1470 fputs ("--------------------------------\n", dump_file);
1473 /* Make no effort to update the post-dominator tree. It is actually not
1474 that hard for the transformations we have performed, but it is not
1475 supported by iterate_fix_dominators. */
1476 free_dominance_info (CDI_POST_DOMINATORS);
1478 else
1480 if (dump_file)
1482 fputs ("Bailing out - ", dump_file);
1483 fputs (failure_reason, dump_file);
1484 fputs ("\n--------------------------------\n", dump_file);
1490 return 0;
1493 } // anon namespace
1495 gimple_opt_pass *
1496 make_pass_convert_switch (gcc::context *ctxt)
1498 return new pass_convert_switch (ctxt);