1 /* Lower GIMPLE_SWITCH expressions to something more efficient than
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
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
22 /* This file handles the lowering of GIMPLE_SWITCH to an indexed
23 load, or a series of bit-test-and-branch expressions. */
27 #include "coretypes.h"
29 #include "insn-codes.h"
34 #include "tree-pass.h"
36 #include "optabs-tree.h"
38 #include "gimple-pretty-print.h"
40 #include "fold-const.h"
42 #include "stor-layout.h"
45 #include "gimple-iterator.h"
46 #include "gimplify-me.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
64 It is assumed that there is already an edge from the to-be-split
65 basic block to E_TRUE->dest block. This edge is removed, and the
66 profile information on the edge is re-used for the new conditional
69 The CFG is updated. The dominator tree will not be valid after
70 this transformation, but the immediate dominators are updated if
71 UPDATE_DOMINATORS is true.
73 Returns the newly created basic block. */
76 hoist_edge_and_branch_if_true (gimple_stmt_iterator
*gsip
,
77 tree cond
, edge e_true
,
78 bool update_dominators
)
83 basic_block new_bb
, split_bb
= gsi_bb (*gsip
);
84 bool dominated_e_true
= false;
86 gcc_assert (e_true
->src
== split_bb
);
89 && get_immediate_dominator (CDI_DOMINATORS
, e_true
->dest
) == split_bb
)
90 dominated_e_true
= true;
92 tmp
= force_gimple_operand_gsi (gsip
, cond
, /*simple=*/true, NULL
,
93 /*before=*/true, GSI_SAME_STMT
);
94 cond_stmt
= gimple_build_cond_from_tree (tmp
, NULL_TREE
, NULL_TREE
);
95 gsi_insert_before (gsip
, cond_stmt
, GSI_SAME_STMT
);
97 e_false
= split_block (split_bb
, cond_stmt
);
98 new_bb
= e_false
->dest
;
99 redirect_edge_pred (e_true
, split_bb
);
101 e_true
->flags
&= ~EDGE_FALLTHRU
;
102 e_true
->flags
|= EDGE_TRUE_VALUE
;
104 e_false
->flags
&= ~EDGE_FALLTHRU
;
105 e_false
->flags
|= EDGE_FALSE_VALUE
;
106 e_false
->probability
= REG_BR_PROB_BASE
- e_true
->probability
;
107 e_false
->count
= split_bb
->count
- e_true
->count
;
108 new_bb
->count
= e_false
->count
;
110 if (update_dominators
)
112 if (dominated_e_true
)
113 set_immediate_dominator (CDI_DOMINATORS
, e_true
->dest
, split_bb
);
114 set_immediate_dominator (CDI_DOMINATORS
, e_false
->dest
, split_bb
);
121 /* 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. */
127 expand_switch_using_bit_tests_p (tree range
,
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:
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':
176 if (tmp1 > (70 - 48)) goto L2;
178 tmp3 = 0b11111100000001111111111;
179 if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2;
186 TODO: There are still some improvements to this transformation that could
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
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. */
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
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...). */
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
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
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
;
273 basic_block switch_bb
= gimple_bb (swtch
);
274 basic_block default_bb
, new_default_bb
, new_bb
;
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
;
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. */
304 for (i
= 1; i
< branch_num
; i
++)
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
)
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
;
326 lo
= tree_to_uhwi (int_const_binop (MINUS_EXPR
,
327 CASE_LOW (cs
), minval
));
328 if (CASE_HIGH (cs
) == NULL_TREE
)
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)
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
),
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
),
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
));
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
373 new_default_bb
= split_edge (default_edge
);
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
);
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. */
411 vec
<basic_block
> dom_bbs
;
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
))
420 set_immediate_dominator (CDI_DOMINATORS
, dom_son
, switch_bb
);
421 bbs_to_fix_dom
.safe_push (dom_son
);
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
,
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);
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:
502 a_5 = PHI <a_1, a_2, a_3, a_4>
503 b_5 = PHI <b_1, b_2, b_3, b_4>
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,
512 if (((unsigned) argc) - 1 < 11)
514 a_6 = CSWTCH02[argc - 1];
515 b_6 = CSWTCH01[argc - 1];
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. */
538 /* The following integer constants store the minimum and maximum value
539 covered by the case labels. */
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. */
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. */
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). */
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
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. */
595 /* True if default case is not used for any value between range_min and
596 range_max inclusive. */
597 bool contiguous_range
;
599 /* True if default case does not have the required shape for other case
601 bool default_case_nonstandard
;
603 /* Parameters for expand_switch_using_bit_tests. Should be computed
604 the same way as in expand_case. */
609 /* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */
612 collect_switch_conv_info (gswitch
*swtch
, struct switch_conv_info
*info
)
614 unsigned int branch_num
= gimple_switch_num_labels (swtch
);
615 tree min_case
, max_case
;
616 unsigned int count
, i
;
617 edge e
, e_default
, e_first
;
621 memset (info
, 0, sizeof (*info
));
623 /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
624 is a default label which is the first in the vector.
625 Collect the bits we can deduce from the CFG. */
626 info
->index_expr
= gimple_switch_index (swtch
);
627 info
->switch_bb
= gimple_bb (swtch
);
629 = label_to_block (CASE_LABEL (gimple_switch_default_label (swtch
)));
630 e_default
= find_edge (info
->switch_bb
, info
->default_bb
);
631 info
->default_prob
= e_default
->probability
;
632 info
->default_count
= e_default
->count
;
633 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
635 info
->other_count
+= e
->count
;
637 /* Get upper and lower bounds of case values, and the covered range. */
638 min_case
= gimple_switch_label (swtch
, 1);
639 max_case
= gimple_switch_label (swtch
, branch_num
- 1);
641 info
->range_min
= CASE_LOW (min_case
);
642 if (CASE_HIGH (max_case
) != NULL_TREE
)
643 info
->range_max
= CASE_HIGH (max_case
);
645 info
->range_max
= CASE_LOW (max_case
);
647 info
->contiguous_range
= true;
648 tree last
= CASE_HIGH (min_case
) ? CASE_HIGH (min_case
) : info
->range_min
;
649 for (i
= 2; i
< branch_num
; i
++)
651 tree elt
= gimple_switch_label (swtch
, i
);
653 if (w
+ 1 != CASE_LOW (elt
))
655 info
->contiguous_range
= false;
658 last
= CASE_HIGH (elt
) ? CASE_HIGH (elt
) : CASE_LOW (elt
);
661 if (info
->contiguous_range
)
663 first
= label_to_block (CASE_LABEL (gimple_switch_label (swtch
, 1)));
664 e_first
= find_edge (info
->switch_bb
, first
);
668 first
= info
->default_bb
;
672 /* See if there is one common successor block for all branch
673 targets. If it exists, record it in FINAL_BB.
674 Start with the destination of the first non-default case
675 if the range is contiguous and default case otherwise as
676 guess or its destination in case it is a forwarder block. */
677 if (! single_pred_p (e_first
->dest
))
678 info
->final_bb
= e_first
->dest
;
679 else if (single_succ_p (e_first
->dest
)
680 && ! single_pred_p (single_succ (e_first
->dest
)))
681 info
->final_bb
= single_succ (e_first
->dest
);
682 /* Require that all switch destinations are either that common
683 FINAL_BB or a forwarder to it, except for the default
684 case if contiguous range. */
686 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
688 if (e
->dest
== info
->final_bb
)
691 if (single_pred_p (e
->dest
)
692 && single_succ_p (e
->dest
)
693 && single_succ (e
->dest
) == info
->final_bb
)
696 if (e
== e_default
&& info
->contiguous_range
)
698 info
->default_case_nonstandard
= true;
702 info
->final_bb
= NULL
;
707 = int_const_binop (MINUS_EXPR
, info
->range_max
, info
->range_min
);
709 /* Get a count of the number of case labels. Single-valued case labels
710 simply count as one, but a case range counts double, since it may
711 require two compares if it gets lowered as a branching tree. */
713 for (i
= 1; i
< branch_num
; i
++)
715 tree elt
= gimple_switch_label (swtch
, i
);
718 && ! tree_int_cst_equal (CASE_LOW (elt
), CASE_HIGH (elt
)))
723 /* Get the number of unique non-default targets out of the GIMPLE_SWITCH
724 block. Assume a CFG cleanup would have already removed degenerate
725 switch statements, this allows us to just use EDGE_COUNT. */
726 info
->uniq
= EDGE_COUNT (gimple_bb (swtch
)->succs
) - 1;
729 /* Checks whether the range given by individual case statements of the SWTCH
730 switch statement isn't too big and whether the number of branches actually
731 satisfies the size of the new array. */
734 check_range (struct switch_conv_info
*info
)
736 gcc_assert (info
->range_size
);
737 if (!tree_fits_uhwi_p (info
->range_size
))
739 info
->reason
= "index range way too large or otherwise unusable";
743 if (tree_to_uhwi (info
->range_size
)
744 > ((unsigned) info
->count
* SWITCH_CONVERSION_BRANCH_RATIO
))
746 info
->reason
= "the maximum range-branch ratio exceeded";
753 /* Checks whether all but the FINAL_BB basic blocks are empty. */
756 check_all_empty_except_final (struct switch_conv_info
*info
)
758 edge e
, e_default
= find_edge (info
->switch_bb
, info
->default_bb
);
761 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
763 if (e
->dest
== info
->final_bb
)
766 if (!empty_block_p (e
->dest
))
768 if (info
->contiguous_range
&& e
== e_default
)
770 info
->default_case_nonstandard
= true;
774 info
->reason
= "bad case - a non-final BB not empty";
782 /* This function checks whether all required values in phi nodes in final_bb
783 are constants. Required values are those that correspond to a basic block
784 which is a part of the examined switch statement. It returns true if the
785 phi nodes are OK, otherwise false. */
788 check_final_bb (gswitch
*swtch
, struct switch_conv_info
*info
)
793 for (gsi
= gsi_start_phis (info
->final_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
795 gphi
*phi
= gsi
.phi ();
798 if (virtual_operand_p (gimple_phi_result (phi
)))
803 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
805 basic_block bb
= gimple_phi_arg_edge (phi
, i
)->src
;
807 if (bb
== info
->switch_bb
808 || (single_pred_p (bb
)
809 && single_pred (bb
) == info
->switch_bb
810 && (!info
->default_case_nonstandard
811 || empty_block_p (bb
))))
814 const char *reason
= NULL
;
816 val
= gimple_phi_arg_def (phi
, i
);
817 if (!is_gimple_ip_invariant (val
))
818 reason
= "non-invariant value from a case";
821 reloc
= initializer_constant_valid_p (val
, TREE_TYPE (val
));
822 if ((flag_pic
&& reloc
!= null_pointer_node
)
823 || (!flag_pic
&& reloc
== NULL_TREE
))
827 = "value from a case would need runtime relocations";
830 = "value from a case is not a valid initializer";
835 /* For contiguous range, we can allow non-constant
836 or one that needs relocation, as long as it is
837 only reachable from the default case. */
838 if (bb
== info
->switch_bb
)
840 if (!info
->contiguous_range
|| bb
!= info
->default_bb
)
842 info
->reason
= reason
;
846 unsigned int branch_num
= gimple_switch_num_labels (swtch
);
847 for (unsigned int i
= 1; i
< branch_num
; i
++)
849 tree lab
= CASE_LABEL (gimple_switch_label (swtch
, i
));
850 if (label_to_block (lab
) == bb
)
852 info
->reason
= reason
;
856 info
->default_case_nonstandard
= true;
865 /* The following function allocates default_values, target_{in,out}_names and
866 constructors arrays. The last one is also populated with pointers to
867 vectors that will become constructors of new arrays. */
870 create_temp_arrays (struct switch_conv_info
*info
)
874 info
->default_values
= XCNEWVEC (tree
, info
->phi_count
* 3);
875 /* ??? Macros do not support multi argument templates in their
876 argument list. We create a typedef to work around that problem. */
877 typedef vec
<constructor_elt
, va_gc
> *vec_constructor_elt_gc
;
878 info
->constructors
= XCNEWVEC (vec_constructor_elt_gc
, info
->phi_count
);
879 info
->target_inbound_names
= info
->default_values
+ info
->phi_count
;
880 info
->target_outbound_names
= info
->target_inbound_names
+ info
->phi_count
;
881 for (i
= 0; i
< info
->phi_count
; i
++)
882 vec_alloc (info
->constructors
[i
], tree_to_uhwi (info
->range_size
) + 1);
885 /* Free the arrays created by create_temp_arrays(). The vectors that are
886 created by that function are not freed here, however, because they have
887 already become constructors and must be preserved. */
890 free_temp_arrays (struct switch_conv_info
*info
)
892 XDELETEVEC (info
->constructors
);
893 XDELETEVEC (info
->default_values
);
896 /* Populate the array of default values in the order of phi nodes.
897 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch
898 if the range is non-contiguous or the default case has standard
899 structure, otherwise it is the first non-default case instead. */
902 gather_default_values (tree default_case
, struct switch_conv_info
*info
)
905 basic_block bb
= label_to_block (CASE_LABEL (default_case
));
909 gcc_assert (CASE_LOW (default_case
) == NULL_TREE
910 || info
->default_case_nonstandard
);
912 if (bb
== info
->final_bb
)
913 e
= find_edge (info
->switch_bb
, bb
);
915 e
= single_succ_edge (bb
);
917 for (gsi
= gsi_start_phis (info
->final_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
919 gphi
*phi
= gsi
.phi ();
920 if (virtual_operand_p (gimple_phi_result (phi
)))
922 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
924 info
->default_values
[i
++] = val
;
928 /* The following function populates the vectors in the constructors array with
929 future contents of the static arrays. The vectors are populated in the
930 order of phi nodes. SWTCH is the switch statement being converted. */
933 build_constructors (gswitch
*swtch
, struct switch_conv_info
*info
)
935 unsigned i
, branch_num
= gimple_switch_num_labels (swtch
);
936 tree pos
= info
->range_min
;
937 tree pos_one
= build_int_cst (TREE_TYPE (pos
), 1);
939 for (i
= 1; i
< branch_num
; i
++)
941 tree cs
= gimple_switch_label (swtch
, i
);
942 basic_block bb
= label_to_block (CASE_LABEL (cs
));
948 if (bb
== info
->final_bb
)
949 e
= find_edge (info
->switch_bb
, bb
);
951 e
= single_succ_edge (bb
);
954 while (tree_int_cst_lt (pos
, CASE_LOW (cs
)))
957 gcc_assert (!info
->contiguous_range
);
958 for (k
= 0; k
< info
->phi_count
; k
++)
962 elt
.index
= int_const_binop (MINUS_EXPR
, pos
, info
->range_min
);
964 = unshare_expr_without_location (info
->default_values
[k
]);
965 info
->constructors
[k
]->quick_push (elt
);
968 pos
= int_const_binop (PLUS_EXPR
, pos
, pos_one
);
970 gcc_assert (tree_int_cst_equal (pos
, CASE_LOW (cs
)));
974 high
= CASE_HIGH (cs
);
976 high
= CASE_LOW (cs
);
977 for (gsi
= gsi_start_phis (info
->final_bb
);
978 !gsi_end_p (gsi
); gsi_next (&gsi
))
980 gphi
*phi
= gsi
.phi ();
981 if (virtual_operand_p (gimple_phi_result (phi
)))
983 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
984 tree low
= CASE_LOW (cs
);
991 elt
.index
= int_const_binop (MINUS_EXPR
, pos
, info
->range_min
);
992 elt
.value
= unshare_expr_without_location (val
);
993 info
->constructors
[j
]->quick_push (elt
);
995 pos
= int_const_binop (PLUS_EXPR
, pos
, pos_one
);
996 } while (!tree_int_cst_lt (high
, pos
)
997 && tree_int_cst_lt (low
, pos
));
1003 /* If all values in the constructor vector are the same, return the value.
1004 Otherwise return NULL_TREE. Not supposed to be called for empty
1008 constructor_contains_same_values_p (vec
<constructor_elt
, va_gc
> *vec
)
1011 tree prev
= NULL_TREE
;
1012 constructor_elt
*elt
;
1014 FOR_EACH_VEC_SAFE_ELT (vec
, i
, elt
)
1018 else if (!operand_equal_p (elt
->value
, prev
, OEP_ONLY_CONST
))
1024 /* Return type which should be used for array elements, either TYPE's
1025 main variant or, for integral types, some smaller integral type
1026 that can still hold all the constants. */
1029 array_value_type (gswitch
*swtch
, tree type
, int num
,
1030 struct switch_conv_info
*info
)
1032 unsigned int i
, len
= vec_safe_length (info
->constructors
[num
]);
1033 constructor_elt
*elt
;
1038 /* Types with alignments greater than their size can reach here, e.g. out of
1039 SRA. We couldn't use these as an array component type so get back to the
1040 main variant first, which, for our purposes, is fine for other types as
1043 type
= TYPE_MAIN_VARIANT (type
);
1045 if (!INTEGRAL_TYPE_P (type
))
1048 mode
= GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type
)));
1049 if (GET_MODE_SIZE (TYPE_MODE (type
)) <= GET_MODE_SIZE (mode
))
1052 if (len
< (optimize_bb_for_size_p (gimple_bb (swtch
)) ? 2 : 32))
1055 FOR_EACH_VEC_SAFE_ELT (info
->constructors
[num
], i
, elt
)
1059 if (TREE_CODE (elt
->value
) != INTEGER_CST
)
1065 unsigned int prec
= GET_MODE_BITSIZE (mode
);
1066 if (prec
> HOST_BITS_PER_WIDE_INT
)
1069 if (sign
>= 0 && cst
== wi::zext (cst
, prec
))
1071 if (sign
== 0 && cst
== wi::sext (cst
, prec
))
1076 if (sign
<= 0 && cst
== wi::sext (cst
, prec
))
1085 mode
= GET_MODE_WIDER_MODE (mode
);
1086 if (mode
== VOIDmode
1087 || GET_MODE_SIZE (mode
) >= GET_MODE_SIZE (TYPE_MODE (type
)))
1093 sign
= TYPE_UNSIGNED (type
) ? 1 : -1;
1094 smaller_type
= lang_hooks
.types
.type_for_mode (mode
, sign
>= 0);
1095 if (GET_MODE_SIZE (TYPE_MODE (type
))
1096 <= GET_MODE_SIZE (TYPE_MODE (smaller_type
)))
1099 return smaller_type
;
1102 /* Create an appropriate array type and declaration and assemble a static array
1103 variable. Also create a load statement that initializes the variable in
1104 question with a value from the static array. SWTCH is the switch statement
1105 being converted, NUM is the index to arrays of constructors, default values
1106 and target SSA names for this particular array. ARR_INDEX_TYPE is the type
1107 of the index of the new array, PHI is the phi node of the final BB that
1108 corresponds to the value that will be loaded from the created array. TIDX
1109 is an ssa name of a temporary variable holding the index for loads from the
1113 build_one_array (gswitch
*swtch
, int num
, tree arr_index_type
,
1114 gphi
*phi
, tree tidx
, struct switch_conv_info
*info
)
1118 gimple_stmt_iterator gsi
= gsi_for_stmt (swtch
);
1119 location_t loc
= gimple_location (swtch
);
1121 gcc_assert (info
->default_values
[num
]);
1123 name
= copy_ssa_name (PHI_RESULT (phi
));
1124 info
->target_inbound_names
[num
] = name
;
1126 cst
= constructor_contains_same_values_p (info
->constructors
[num
]);
1128 load
= gimple_build_assign (name
, cst
);
1131 tree array_type
, ctor
, decl
, value_type
, fetch
, default_type
;
1133 default_type
= TREE_TYPE (info
->default_values
[num
]);
1134 value_type
= array_value_type (swtch
, default_type
, num
, info
);
1135 array_type
= build_array_type (value_type
, arr_index_type
);
1136 if (default_type
!= value_type
)
1139 constructor_elt
*elt
;
1141 FOR_EACH_VEC_SAFE_ELT (info
->constructors
[num
], i
, elt
)
1142 elt
->value
= fold_convert (value_type
, elt
->value
);
1144 ctor
= build_constructor (array_type
, info
->constructors
[num
]);
1145 TREE_CONSTANT (ctor
) = true;
1146 TREE_STATIC (ctor
) = true;
1148 decl
= build_decl (loc
, VAR_DECL
, NULL_TREE
, array_type
);
1149 TREE_STATIC (decl
) = 1;
1150 DECL_INITIAL (decl
) = ctor
;
1152 DECL_NAME (decl
) = create_tmp_var_name ("CSWTCH");
1153 DECL_ARTIFICIAL (decl
) = 1;
1154 DECL_IGNORED_P (decl
) = 1;
1155 TREE_CONSTANT (decl
) = 1;
1156 TREE_READONLY (decl
) = 1;
1157 DECL_IGNORED_P (decl
) = 1;
1158 varpool_node::finalize_decl (decl
);
1160 fetch
= build4 (ARRAY_REF
, value_type
, decl
, tidx
, NULL_TREE
,
1162 if (default_type
!= value_type
)
1164 fetch
= fold_convert (default_type
, fetch
);
1165 fetch
= force_gimple_operand_gsi (&gsi
, fetch
, true, NULL_TREE
,
1166 true, GSI_SAME_STMT
);
1168 load
= gimple_build_assign (name
, fetch
);
1171 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
1173 info
->arr_ref_last
= load
;
1176 /* Builds and initializes static arrays initialized with values gathered from
1177 the SWTCH switch statement. Also creates statements that load values from
1181 build_arrays (gswitch
*swtch
, struct switch_conv_info
*info
)
1183 tree arr_index_type
;
1184 tree tidx
, sub
, utype
;
1186 gimple_stmt_iterator gsi
;
1189 location_t loc
= gimple_location (swtch
);
1191 gsi
= gsi_for_stmt (swtch
);
1193 /* Make sure we do not generate arithmetics in a subrange. */
1194 utype
= TREE_TYPE (info
->index_expr
);
1195 if (TREE_TYPE (utype
))
1196 utype
= lang_hooks
.types
.type_for_mode (TYPE_MODE (TREE_TYPE (utype
)), 1);
1198 utype
= lang_hooks
.types
.type_for_mode (TYPE_MODE (utype
), 1);
1200 arr_index_type
= build_index_type (info
->range_size
);
1201 tidx
= make_ssa_name (utype
);
1202 sub
= fold_build2_loc (loc
, MINUS_EXPR
, utype
,
1203 fold_convert_loc (loc
, utype
, info
->index_expr
),
1204 fold_convert_loc (loc
, utype
, info
->range_min
));
1205 sub
= force_gimple_operand_gsi (&gsi
, sub
,
1206 false, NULL
, true, GSI_SAME_STMT
);
1207 stmt
= gimple_build_assign (tidx
, sub
);
1209 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1211 info
->arr_ref_first
= stmt
;
1213 for (gpi
= gsi_start_phis (info
->final_bb
), i
= 0;
1214 !gsi_end_p (gpi
); gsi_next (&gpi
))
1216 gphi
*phi
= gpi
.phi ();
1217 if (!virtual_operand_p (gimple_phi_result (phi
)))
1218 build_one_array (swtch
, i
++, arr_index_type
, phi
, tidx
, info
);
1222 /* Generates and appropriately inserts loads of default values at the position
1223 given by BSI. Returns the last inserted statement. */
1226 gen_def_assigns (gimple_stmt_iterator
*gsi
, struct switch_conv_info
*info
)
1229 gassign
*assign
= NULL
;
1231 for (i
= 0; i
< info
->phi_count
; i
++)
1233 tree name
= copy_ssa_name (info
->target_inbound_names
[i
]);
1234 info
->target_outbound_names
[i
] = name
;
1235 assign
= gimple_build_assign (name
, info
->default_values
[i
]);
1236 gsi_insert_before (gsi
, assign
, GSI_SAME_STMT
);
1237 update_stmt (assign
);
1242 /* Deletes the unused bbs and edges that now contain the switch statement and
1243 its empty branch bbs. BBD is the now dead BB containing the original switch
1244 statement, FINAL is the last BB of the converted switch statement (in terms
1248 prune_bbs (basic_block bbd
, basic_block final
, basic_block default_bb
)
1253 for (ei
= ei_start (bbd
->succs
); (e
= ei_safe_edge (ei
)); )
1258 if (bb
!= final
&& bb
!= default_bb
)
1259 delete_basic_block (bb
);
1261 delete_basic_block (bbd
);
1264 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
1265 from the basic block loading values from an array and E2F from the basic
1266 block loading default values. BBF is the last switch basic block (see the
1267 bbf description in the comment below). */
1270 fix_phi_nodes (edge e1f
, edge e2f
, basic_block bbf
,
1271 struct switch_conv_info
*info
)
1276 for (gsi
= gsi_start_phis (bbf
), i
= 0;
1277 !gsi_end_p (gsi
); gsi_next (&gsi
))
1279 gphi
*phi
= gsi
.phi ();
1280 tree inbound
, outbound
;
1281 if (virtual_operand_p (gimple_phi_result (phi
)))
1282 inbound
= outbound
= gimple_vop (cfun
);
1285 inbound
= info
->target_inbound_names
[i
];
1286 outbound
= info
->target_outbound_names
[i
++];
1288 add_phi_arg (phi
, inbound
, e1f
, UNKNOWN_LOCATION
);
1289 if (!info
->default_case_nonstandard
)
1290 add_phi_arg (phi
, outbound
, e2f
, UNKNOWN_LOCATION
);
1294 /* Creates a check whether the switch expression value actually falls into the
1295 range given by all the cases. If it does not, the temporaries are loaded
1296 with default values instead. SWTCH is the switch statement being converted.
1298 bb0 is the bb with the switch statement, however, we'll end it with a
1301 bb1 is the bb to be used when the range check went ok. It is derived from
1304 bb2 is the bb taken when the expression evaluated outside of the range
1305 covered by the created arrays. It is populated by loads of default
1308 bbF is a fall through for both bb1 and bb2 and contains exactly what
1309 originally followed the switch statement.
1311 bbD contains the switch statement (in the end). It is unreachable but we
1312 still need to strip off its edges.
1316 gen_inbound_check (gswitch
*swtch
, struct switch_conv_info
*info
)
1318 tree label_decl1
= create_artificial_label (UNKNOWN_LOCATION
);
1319 tree label_decl2
= create_artificial_label (UNKNOWN_LOCATION
);
1320 tree label_decl3
= create_artificial_label (UNKNOWN_LOCATION
);
1321 glabel
*label1
, *label2
, *label3
;
1327 gassign
*last_assign
= NULL
;
1328 gimple_stmt_iterator gsi
;
1329 basic_block bb0
, bb1
, bb2
, bbf
, bbd
;
1330 edge e01
= NULL
, e02
, e21
, e1d
, e1f
, e2f
;
1331 location_t loc
= gimple_location (swtch
);
1333 gcc_assert (info
->default_values
);
1335 bb0
= gimple_bb (swtch
);
1337 tidx
= gimple_assign_lhs (info
->arr_ref_first
);
1338 utype
= TREE_TYPE (tidx
);
1340 /* (end of) block 0 */
1341 gsi
= gsi_for_stmt (info
->arr_ref_first
);
1344 bound
= fold_convert_loc (loc
, utype
, info
->range_size
);
1345 cond_stmt
= gimple_build_cond (LE_EXPR
, tidx
, bound
, NULL_TREE
, NULL_TREE
);
1346 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1347 update_stmt (cond_stmt
);
1350 if (!info
->default_case_nonstandard
)
1352 label2
= gimple_build_label (label_decl2
);
1353 gsi_insert_before (&gsi
, label2
, GSI_SAME_STMT
);
1354 last_assign
= gen_def_assigns (&gsi
, info
);
1358 label1
= gimple_build_label (label_decl1
);
1359 gsi_insert_before (&gsi
, label1
, GSI_SAME_STMT
);
1362 gsi
= gsi_start_bb (info
->final_bb
);
1363 label3
= gimple_build_label (label_decl3
);
1364 gsi_insert_before (&gsi
, label3
, GSI_SAME_STMT
);
1367 e02
= split_block (bb0
, cond_stmt
);
1370 if (info
->default_case_nonstandard
)
1373 bb2
= info
->default_bb
;
1375 e01
->flags
= EDGE_TRUE_VALUE
;
1376 e02
= make_edge (bb0
, bb2
, EDGE_FALSE_VALUE
);
1377 edge e_default
= find_edge (bb1
, bb2
);
1378 for (gphi_iterator gsi
= gsi_start_phis (bb2
);
1379 !gsi_end_p (gsi
); gsi_next (&gsi
))
1381 gphi
*phi
= gsi
.phi ();
1382 tree arg
= PHI_ARG_DEF_FROM_EDGE (phi
, e_default
);
1383 add_phi_arg (phi
, arg
, e02
,
1384 gimple_phi_arg_location_from_edge (phi
, e_default
));
1386 /* Partially fix the dominator tree, if it is available. */
1387 if (dom_info_available_p (CDI_DOMINATORS
))
1388 redirect_immediate_dominators (CDI_DOMINATORS
, bb1
, bb0
);
1392 e21
= split_block (bb2
, last_assign
);
1397 e1d
= split_block (bb1
, info
->arr_ref_last
);
1401 /* flags and profiles of the edge for in-range values */
1402 if (!info
->default_case_nonstandard
)
1403 e01
= make_edge (bb0
, bb1
, EDGE_TRUE_VALUE
);
1404 e01
->probability
= REG_BR_PROB_BASE
- info
->default_prob
;
1405 e01
->count
= info
->other_count
;
1407 /* flags and profiles of the edge taking care of out-of-range values */
1408 e02
->flags
&= ~EDGE_FALLTHRU
;
1409 e02
->flags
|= EDGE_FALSE_VALUE
;
1410 e02
->probability
= info
->default_prob
;
1411 e02
->count
= info
->default_count
;
1413 bbf
= info
->final_bb
;
1415 e1f
= make_edge (bb1
, bbf
, EDGE_FALLTHRU
);
1416 e1f
->probability
= REG_BR_PROB_BASE
;
1417 e1f
->count
= info
->other_count
;
1419 if (info
->default_case_nonstandard
)
1423 e2f
= make_edge (bb2
, bbf
, EDGE_FALLTHRU
);
1424 e2f
->probability
= REG_BR_PROB_BASE
;
1425 e2f
->count
= info
->default_count
;
1428 /* frequencies of the new BBs */
1429 bb1
->frequency
= EDGE_FREQUENCY (e01
);
1430 bb2
->frequency
= EDGE_FREQUENCY (e02
);
1431 if (!info
->default_case_nonstandard
)
1432 bbf
->frequency
= EDGE_FREQUENCY (e1f
) + EDGE_FREQUENCY (e2f
);
1434 /* Tidy blocks that have become unreachable. */
1435 prune_bbs (bbd
, info
->final_bb
,
1436 info
->default_case_nonstandard
? info
->default_bb
: NULL
);
1438 /* Fixup the PHI nodes in bbF. */
1439 fix_phi_nodes (e1f
, e2f
, bbf
, info
);
1441 /* Fix the dominator tree, if it is available. */
1442 if (dom_info_available_p (CDI_DOMINATORS
))
1444 vec
<basic_block
> bbs_to_fix_dom
;
1446 set_immediate_dominator (CDI_DOMINATORS
, bb1
, bb0
);
1447 if (!info
->default_case_nonstandard
)
1448 set_immediate_dominator (CDI_DOMINATORS
, bb2
, bb0
);
1449 if (! get_immediate_dominator (CDI_DOMINATORS
, bbf
))
1450 /* If bbD was the immediate dominator ... */
1451 set_immediate_dominator (CDI_DOMINATORS
, bbf
, bb0
);
1453 bbs_to_fix_dom
.create (3 + (bb2
!= bbf
));
1454 bbs_to_fix_dom
.quick_push (bb0
);
1455 bbs_to_fix_dom
.quick_push (bb1
);
1457 bbs_to_fix_dom
.quick_push (bb2
);
1458 bbs_to_fix_dom
.quick_push (bbf
);
1460 iterate_fix_dominators (CDI_DOMINATORS
, bbs_to_fix_dom
, true);
1461 bbs_to_fix_dom
.release ();
1465 /* The following function is invoked on every switch statement (the current one
1466 is given in SWTCH) and runs the individual phases of switch conversion on it
1467 one after another until one fails or the conversion is completed.
1468 Returns NULL on success, or a pointer to a string with the reason why the
1469 conversion failed. */
1472 process_switch (gswitch
*swtch
)
1474 struct switch_conv_info info
;
1476 /* Group case labels so that we get the right results from the heuristics
1477 that decide on the code generation approach for this switch. */
1478 group_case_labels_stmt (swtch
);
1480 /* If this switch is now a degenerate case with only a default label,
1481 there is nothing left for us to do. */
1482 if (gimple_switch_num_labels (swtch
) < 2)
1483 return "switch is a degenerate case";
1485 collect_switch_conv_info (swtch
, &info
);
1487 /* No error markers should reach here (they should be filtered out
1488 during gimplification). */
1489 gcc_checking_assert (TREE_TYPE (info
.index_expr
) != error_mark_node
);
1491 /* A switch on a constant should have been optimized in tree-cfg-cleanup. */
1492 gcc_checking_assert (! TREE_CONSTANT (info
.index_expr
));
1494 if (info
.uniq
<= MAX_CASE_BIT_TESTS
)
1496 if (expand_switch_using_bit_tests_p (info
.range_size
,
1497 info
.uniq
, info
.count
,
1498 optimize_bb_for_speed_p
1499 (gimple_bb (swtch
))))
1502 fputs (" expanding as bit test is preferable\n", dump_file
);
1503 emit_case_bit_tests (swtch
, info
.index_expr
, info
.range_min
,
1504 info
.range_size
, info
.range_max
);
1505 loops_state_set (LOOPS_NEED_FIXUP
);
1510 /* This will be expanded as a decision tree in stmt.c:expand_case. */
1511 return " expanding as jumps is preferable";
1514 /* If there is no common successor, we cannot do the transformation. */
1515 if (! info
.final_bb
)
1516 return "no common successor to all case label target blocks found";
1518 /* Check the case label values are within reasonable range: */
1519 if (!check_range (&info
))
1521 gcc_assert (info
.reason
);
1525 /* For all the cases, see whether they are empty, the assignments they
1526 represent constant and so on... */
1527 if (! check_all_empty_except_final (&info
))
1529 gcc_assert (info
.reason
);
1532 if (!check_final_bb (swtch
, &info
))
1534 gcc_assert (info
.reason
);
1538 /* At this point all checks have passed and we can proceed with the
1541 create_temp_arrays (&info
);
1542 gather_default_values (info
.default_case_nonstandard
1543 ? gimple_switch_label (swtch
, 1)
1544 : gimple_switch_default_label (swtch
), &info
);
1545 build_constructors (swtch
, &info
);
1547 build_arrays (swtch
, &info
); /* Build the static arrays and assignments. */
1548 gen_inbound_check (swtch
, &info
); /* Build the bounds check. */
1551 free_temp_arrays (&info
);
1555 /* The main function of the pass scans statements for switches and invokes
1556 process_switch on them. */
1560 const pass_data pass_data_convert_switch
=
1562 GIMPLE_PASS
, /* type */
1563 "switchconv", /* name */
1564 OPTGROUP_NONE
, /* optinfo_flags */
1565 TV_TREE_SWITCH_CONVERSION
, /* tv_id */
1566 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1567 0, /* properties_provided */
1568 0, /* properties_destroyed */
1569 0, /* todo_flags_start */
1570 TODO_update_ssa
, /* todo_flags_finish */
1573 class pass_convert_switch
: public gimple_opt_pass
1576 pass_convert_switch (gcc::context
*ctxt
)
1577 : gimple_opt_pass (pass_data_convert_switch
, ctxt
)
1580 /* opt_pass methods: */
1581 virtual bool gate (function
*) { return flag_tree_switch_conversion
!= 0; }
1582 virtual unsigned int execute (function
*);
1584 }; // class pass_convert_switch
1587 pass_convert_switch::execute (function
*fun
)
1591 FOR_EACH_BB_FN (bb
, fun
)
1593 const char *failure_reason
;
1594 gimple
*stmt
= last_stmt (bb
);
1595 if (stmt
&& gimple_code (stmt
) == GIMPLE_SWITCH
)
1599 expanded_location loc
= expand_location (gimple_location (stmt
));
1601 fprintf (dump_file
, "beginning to process the following "
1602 "SWITCH statement (%s:%d) : ------- \n",
1603 loc
.file
, loc
.line
);
1604 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1605 putc ('\n', dump_file
);
1608 failure_reason
= process_switch (as_a
<gswitch
*> (stmt
));
1609 if (! failure_reason
)
1613 fputs ("Switch converted\n", dump_file
);
1614 fputs ("--------------------------------\n", dump_file
);
1617 /* Make no effort to update the post-dominator tree. It is actually not
1618 that hard for the transformations we have performed, but it is not
1619 supported by iterate_fix_dominators. */
1620 free_dominance_info (CDI_POST_DOMINATORS
);
1626 fputs ("Bailing out - ", dump_file
);
1627 fputs (failure_reason
, dump_file
);
1628 fputs ("\n--------------------------------\n", dump_file
);
1640 make_pass_convert_switch (gcc::context
*ctxt
)
1642 return new pass_convert_switch (ctxt
);