1 /* Lower GIMPLE_SWITCH expressions to something more efficient than
3 Copyright (C) 2006, 2008, 2009, 2010, 2011, 2012
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by the
10 Free Software Foundation; either version 3, or (at your option) any
13 GCC is distributed in the hope that it will be useful, but WITHOUT
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 /* This file handles the lowering of GIMPLE_SWITCH to an indexed
24 load, or a series of bit-test-and-branch expressions. */
28 #include "coretypes.h"
34 #include "basic-block.h"
35 #include "tree-flow.h"
36 #include "tree-flow-inline.h"
37 #include "tree-ssa-operands.h"
38 #include "tree-pass.h"
39 #include "gimple-pretty-print.h"
40 #include "tree-dump.h"
42 #include "langhooks.h"
44 /* Need to include expr.h and optabs.h for lshift_cheap_p. */
48 /* Maximum number of case bit tests.
49 FIXME: This should be derived from PARAM_CASE_VALUES_THRESHOLD and
50 targetm.case_values_threshold(), or be its own param. */
51 #define MAX_CASE_BIT_TESTS 3
53 /* Split the basic block at the statement pointed to by GSIP, and insert
54 a branch to the target basic block of E_TRUE conditional on tree
57 It is assumed that there is already an edge from the to-be-split
58 basic block to E_TRUE->dest block. This edge is removed, and the
59 profile information on the edge is re-used for the new conditional
62 The CFG is updated. The dominator tree will not be valid after
63 this transformation, but the immediate dominators are updated if
64 UPDATE_DOMINATORS is true.
66 Returns the newly created basic block. */
69 hoist_edge_and_branch_if_true (gimple_stmt_iterator
*gsip
,
70 tree cond
, edge e_true
,
71 bool update_dominators
)
76 basic_block new_bb
, split_bb
= gsi_bb (*gsip
);
77 bool dominated_e_true
= false;
79 gcc_assert (e_true
->src
== split_bb
);
82 && get_immediate_dominator (CDI_DOMINATORS
, e_true
->dest
) == split_bb
)
83 dominated_e_true
= true;
85 tmp
= force_gimple_operand_gsi (gsip
, cond
, /*simple=*/true, NULL
,
86 /*before=*/true, GSI_SAME_STMT
);
87 cond_stmt
= gimple_build_cond_from_tree (tmp
, NULL_TREE
, NULL_TREE
);
88 gsi_insert_before (gsip
, cond_stmt
, GSI_SAME_STMT
);
90 e_false
= split_block (split_bb
, cond_stmt
);
91 new_bb
= e_false
->dest
;
92 redirect_edge_pred (e_true
, split_bb
);
94 e_true
->flags
&= ~EDGE_FALLTHRU
;
95 e_true
->flags
|= EDGE_TRUE_VALUE
;
97 e_false
->flags
&= ~EDGE_FALLTHRU
;
98 e_false
->flags
|= EDGE_FALSE_VALUE
;
99 e_false
->probability
= REG_BR_PROB_BASE
- e_true
->probability
;
100 e_false
->count
= split_bb
->count
- e_true
->count
;
101 new_bb
->count
= e_false
->count
;
103 if (update_dominators
)
105 if (dominated_e_true
)
106 set_immediate_dominator (CDI_DOMINATORS
, e_true
->dest
, split_bb
);
107 set_immediate_dominator (CDI_DOMINATORS
, e_false
->dest
, split_bb
);
114 /* Determine whether "1 << x" is relatively cheap in word_mode. */
115 /* FIXME: This is the function that we need rtl.h and optabs.h for.
116 This function (and similar RTL-related cost code in e.g. IVOPTS) should
117 be moved to some kind of interface file for GIMPLE/RTL interactions. */
119 lshift_cheap_p (void)
121 /* FIXME: This should be made target dependent via this "this_target"
122 mechanism, similar to e.g. can_copy_init_p in gcse.c. */
123 static bool init
[2] = {false, false};
124 static bool cheap
[2] = {true, true};
127 /* If the targer has no lshift in word_mode, the operation will most
128 probably not be cheap. ??? Does GCC even work for such targets? */
129 if (optab_handler (ashl_optab
, word_mode
) == CODE_FOR_nothing
)
132 speed_p
= optimize_insn_for_speed_p ();
136 rtx reg
= gen_raw_REG (word_mode
, 10000);
137 int cost
= set_src_cost (gen_rtx_ASHIFT (word_mode
, const1_rtx
, reg
),
139 cheap
[speed_p
] = cost
< COSTS_N_INSNS (MAX_CASE_BIT_TESTS
);
140 init
[speed_p
] = true;
143 return cheap
[speed_p
];
146 /* Return true if a switch should be expanded as a bit test.
147 RANGE is the difference between highest and lowest case.
148 UNIQ is number of unique case node targets, not counting the default case.
149 COUNT is the number of comparisons needed, not counting the default case. */
152 expand_switch_using_bit_tests_p (tree range
,
156 return (((uniq
== 1 && count
>= 3)
157 || (uniq
== 2 && count
>= 5)
158 || (uniq
== 3 && count
>= 6))
160 && compare_tree_int (range
, GET_MODE_BITSIZE (word_mode
)) < 0
161 && compare_tree_int (range
, 0) > 0);
164 /* Implement switch statements with bit tests
166 A GIMPLE switch statement can be expanded to a short sequence of bit-wise
167 comparisons. "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)"
168 where CST and MINVAL are integer constants. This is better than a series
169 of compare-and-banch insns in some cases, e.g. we can implement:
171 if ((x==4) || (x==6) || (x==9) || (x==11))
173 as a single bit test:
175 if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11)))
177 This transformation is only applied if the number of case targets is small,
178 if CST constains at least 3 bits, and "x << 1" is cheap. The bit tests are
179 performed in "word_mode".
181 The following example shows the code the transformation generates:
187 case '0': case '1': case '2': case '3': case '4':
188 case '5': case '6': case '7': case '8': case '9':
189 case 'A': case 'B': case 'C': case 'D': case 'E':
201 if (tmp1 > (70 - 48)) goto L2;
203 tmp3 = 0b11111100000001111111111;
204 if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2;
211 TODO: There are still some improvements to this transformation that could
214 * A narrower mode than word_mode could be used if that is cheaper, e.g.
215 for x86_64 where a narrower-mode shift may result in smaller code.
217 * The compounded constant could be shifted rather than the one. The
218 test would be either on the sign bit or on the least significant bit,
219 depending on the direction of the shift. On some machines, the test
220 for the branch would be free if the bit to test is already set by the
223 This transformation was contributed by Roger Sayle, see this e-mail:
224 http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html
227 /* A case_bit_test represents a set of case nodes that may be
228 selected from using a bit-wise comparison. HI and LO hold
229 the integer to be tested against, TARGET_EDGE contains the
230 edge to the basic block to jump to upon success and BITS
231 counts the number of case nodes handled by this test,
232 typically the number of bits set in HI:LO. The LABEL field
233 is used to quickly identify all cases in this set without
234 looking at label_to_block for every case label. */
245 /* Comparison function for qsort to order bit tests by decreasing
246 probability of execution. Our best guess comes from a measured
247 profile. If the profile counts are equal, break even on the
248 number of case nodes, i.e. the node with the most cases gets
251 TODO: Actually this currently runs before a profile is available.
252 Therefore the case-as-bit-tests transformation should be done
253 later in the pass pipeline, or something along the lines of
254 "Efficient and effective branch reordering using profile data"
255 (Yang et. al., 2002) should be implemented (although, how good
256 is a paper is called "Efficient and effective ..." when the
257 latter is implied by the former, but oh well...). */
260 case_bit_test_cmp (const void *p1
, const void *p2
)
262 const struct case_bit_test
*const d1
= (const struct case_bit_test
*) p1
;
263 const struct case_bit_test
*const d2
= (const struct case_bit_test
*) p2
;
265 if (d2
->target_edge
->count
!= d1
->target_edge
->count
)
266 return d2
->target_edge
->count
- d1
->target_edge
->count
;
267 if (d2
->bits
!= d1
->bits
)
268 return d2
->bits
- d1
->bits
;
270 /* Stabilize the sort. */
271 return LABEL_DECL_UID (d2
->label
) - LABEL_DECL_UID (d1
->label
);
274 /* Expand a switch statement by a short sequence of bit-wise
275 comparisons. "switch(x)" is effectively converted into
276 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
279 INDEX_EXPR is the value being switched on.
281 MINVAL is the lowest case value of in the case nodes,
282 and RANGE is highest value minus MINVAL. MINVAL and RANGE
283 are not guaranteed to be of the same type as INDEX_EXPR
284 (the gimplifier doesn't change the type of case label values,
285 and MINVAL and RANGE are derived from those values).
287 There *MUST* be MAX_CASE_BIT_TESTS or less unique case
291 emit_case_bit_tests (gimple swtch
, tree index_expr
,
292 tree minval
, tree range
)
294 struct case_bit_test test
[MAX_CASE_BIT_TESTS
];
295 unsigned int i
, j
, k
;
298 basic_block switch_bb
= gimple_bb (swtch
);
299 basic_block default_bb
, new_default_bb
, new_bb
;
301 bool update_dom
= dom_info_available_p (CDI_DOMINATORS
);
303 VEC (basic_block
, heap
) *bbs_to_fix_dom
= NULL
;
305 tree index_type
= TREE_TYPE (index_expr
);
306 tree unsigned_index_type
= unsigned_type_for (index_type
);
307 unsigned int branch_num
= gimple_switch_num_labels (swtch
);
309 gimple_stmt_iterator gsi
;
313 tree word_type_node
= lang_hooks
.types
.type_for_mode (word_mode
, 1);
314 tree word_mode_zero
= fold_convert (word_type_node
, integer_zero_node
);
315 tree word_mode_one
= fold_convert (word_type_node
, integer_one_node
);
317 memset (&test
, 0, sizeof (test
));
319 /* Get the edge for the default case. */
320 tmp
= gimple_switch_label (swtch
, 0);
321 default_bb
= label_to_block (CASE_LABEL (tmp
));
322 default_edge
= find_edge (switch_bb
, default_bb
);
324 /* Go through all case labels, and collect the case labels, profile
325 counts, and other information we need to build the branch tests. */
327 for (i
= 1; i
< branch_num
; i
++)
330 tree cs
= gimple_switch_label (swtch
, i
);
331 tree label
= CASE_LABEL (cs
);
332 for (k
= 0; k
< count
; k
++)
333 if (label
== test
[k
].label
)
338 edge e
= find_edge (switch_bb
, label_to_block (label
));
340 gcc_checking_assert (count
< MAX_CASE_BIT_TESTS
);
343 test
[k
].target_edge
= e
;
344 test
[k
].label
= label
;
351 lo
= tree_low_cst (int_const_binop (MINUS_EXPR
,
352 CASE_LOW (cs
), minval
),
354 if (CASE_HIGH (cs
) == NULL_TREE
)
357 hi
= tree_low_cst (int_const_binop (MINUS_EXPR
,
358 CASE_HIGH (cs
), minval
),
361 for (j
= lo
; j
<= hi
; j
++)
362 if (j
>= HOST_BITS_PER_WIDE_INT
)
363 test
[k
].hi
|= (HOST_WIDE_INT
) 1 << (j
- HOST_BITS_PER_INT
);
365 test
[k
].lo
|= (HOST_WIDE_INT
) 1 << j
;
368 qsort (test
, count
, sizeof(*test
), case_bit_test_cmp
);
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
= VEC_alloc (basic_block
, heap
, 10);
378 VEC_quick_push (basic_block
, bbs_to_fix_dom
, switch_bb
);
379 VEC_quick_push (basic_block
, bbs_to_fix_dom
, default_bb
);
380 VEC_quick_push (basic_block
, bbs_to_fix_dom
, 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_build2 (MINUS_EXPR
, index_type
, index_expr
,
389 fold_convert (index_type
, minval
));
390 idx
= fold_convert (unsigned_index_type
, idx
);
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 VEC_quick_push (basic_block
, bbs_to_fix_dom
, 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
, heap
) *dom_bbs
;
414 dom_bbs
= get_dominated_by (CDI_DOMINATORS
, new_bb
);
415 FOR_EACH_VEC_ELT (basic_block
, 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 VEC_safe_push (basic_block
, heap
, bbs_to_fix_dom
, dom_son
);
423 VEC_free (basic_block
, heap
, dom_bbs
);
426 /* csui = (1 << (word_mode) idx) */
427 tmp
= create_tmp_var (word_type_node
, "csui");
428 add_referenced_var (tmp
);
429 csui
= make_ssa_name (tmp
, NULL
);
430 tmp
= fold_build2 (LSHIFT_EXPR
, word_type_node
, word_mode_one
,
431 fold_convert (word_type_node
, idx
));
432 tmp
= force_gimple_operand_gsi (&gsi
, tmp
,
433 /*simple=*/false, NULL_TREE
,
434 /*before=*/true, GSI_SAME_STMT
);
435 shift_stmt
= gimple_build_assign (csui
, tmp
);
436 SSA_NAME_DEF_STMT (csui
) = shift_stmt
;
437 gsi_insert_before (&gsi
, shift_stmt
, GSI_SAME_STMT
);
438 update_stmt (shift_stmt
);
440 /* for each unique set of cases:
441 if (const & csui) goto target */
442 for (k
= 0; k
< count
; k
++)
444 tmp
= build_int_cst_wide (word_type_node
, test
[k
].lo
, test
[k
].hi
);
445 tmp
= fold_build2 (BIT_AND_EXPR
, word_type_node
, csui
, tmp
);
446 tmp
= force_gimple_operand_gsi (&gsi
, tmp
,
447 /*simple=*/true, NULL_TREE
,
448 /*before=*/true, GSI_SAME_STMT
);
449 tmp
= fold_build2 (NE_EXPR
, boolean_type_node
, tmp
, word_mode_zero
);
450 new_bb
= hoist_edge_and_branch_if_true (&gsi
, tmp
, test
[k
].target_edge
,
453 VEC_safe_push (basic_block
, heap
, bbs_to_fix_dom
, new_bb
);
454 gcc_assert (gimple_bb (swtch
) == new_bb
);
455 gsi
= gsi_last_bb (new_bb
);
458 /* We should have removed all edges now. */
459 gcc_assert (EDGE_COUNT (gsi_bb (gsi
)->succs
) == 0);
461 /* If nothing matched, go to the default label. */
462 make_edge (gsi_bb (gsi
), new_default_bb
, EDGE_FALLTHRU
);
464 /* The GIMPLE_SWITCH is now redundant. */
465 gsi_remove (&gsi
, true);
469 /* Fix up the dominator tree. */
470 iterate_fix_dominators (CDI_DOMINATORS
, bbs_to_fix_dom
, true);
471 VEC_free (basic_block
, heap
, bbs_to_fix_dom
);
476 Switch initialization conversion
478 The following pass changes simple initializations of scalars in a switch
479 statement into initializations from a static array. Obviously, the values
480 must be constant and known at compile time and a default branch must be
481 provided. For example, the following code:
505 a_5 = PHI <a_1, a_2, a_3, a_4>
506 b_5 = PHI <b_1, b_2, b_3, b_4>
511 static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
512 static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
515 if (((unsigned) argc) - 1 < 11)
517 a_6 = CSWTCH02[argc - 1];
518 b_6 = CSWTCH01[argc - 1];
528 There are further constraints. Specifically, the range of values across all
529 case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
530 eight) times the number of the actual switch branches.
532 This transformation was contributed by Martin Jambor, see this e-mail:
533 http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */
535 /* The main structure of the pass. */
536 struct switch_conv_info
538 /* The expression used to decide the switch branch. */
541 /* The following integer constants store the minimum and maximum value
542 covered by the case labels. */
546 /* The difference between the above two numbers. Stored here because it
547 is used in all the conversion heuristics, as well as for some of the
548 transformation, and it is expensive to re-compute it all the time. */
551 /* Basic block that contains the actual GIMPLE_SWITCH. */
552 basic_block switch_bb
;
554 /* Basic block that is the target of the default case. */
555 basic_block default_bb
;
557 /* The single successor block of all branches out of the GIMPLE_SWITCH,
558 if such a block exists. Otherwise NULL. */
559 basic_block final_bb
;
561 /* The probability of the default edge in the replaced switch. */
564 /* The count of the default edge in the replaced switch. */
565 gcov_type default_count
;
567 /* Combined count of all other (non-default) edges in the replaced switch. */
568 gcov_type other_count
;
570 /* Number of phi nodes in the final bb (that we'll be replacing). */
573 /* Array of default values, in the same order as phi nodes. */
574 tree
*default_values
;
576 /* Constructors of new static arrays. */
577 VEC (constructor_elt
, gc
) **constructors
;
579 /* Array of ssa names that are initialized with a value from a new static
581 tree
*target_inbound_names
;
583 /* Array of ssa names that are initialized with the default value if the
584 switch expression is out of range. */
585 tree
*target_outbound_names
;
587 /* The first load statement that loads a temporary from a new static array.
589 gimple arr_ref_first
;
591 /* The last load statement that loads a temporary from a new static array. */
594 /* String reason why the case wasn't a good candidate that is written to the
595 dump file, if there is one. */
598 /* Parameters for expand_switch_using_bit_tests. Should be computed
599 the same way as in expand_case. */
604 /* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */
607 collect_switch_conv_info (gimple swtch
, struct switch_conv_info
*info
)
609 unsigned int branch_num
= gimple_switch_num_labels (swtch
);
610 tree min_case
, max_case
;
611 unsigned int count
, i
;
615 memset (info
, 0, sizeof (*info
));
617 /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
618 is a default label which is the first in the vector. */
619 gcc_assert (CASE_LOW (gimple_switch_label (swtch
, 0)) == NULL_TREE
);
621 /* Collect the bits we can deduce from the CFG. */
622 info
->index_expr
= gimple_switch_index (swtch
);
623 info
->switch_bb
= gimple_bb (swtch
);
625 label_to_block (CASE_LABEL (gimple_switch_label (swtch
, 0)));
626 e_default
= find_edge (info
->switch_bb
, info
->default_bb
);
627 info
->default_prob
= e_default
->probability
;
628 info
->default_count
= e_default
->count
;
629 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
631 info
->other_count
+= e
->count
;
633 /* See if there is one common successor block for all branch
634 targets. If it exists, record it in FINAL_BB. */
635 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
637 if (! single_pred_p (e
->dest
))
639 info
->final_bb
= e
->dest
;
644 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
646 if (e
->dest
== info
->final_bb
)
649 if (single_pred_p (e
->dest
)
650 && single_succ_p (e
->dest
)
651 && single_succ (e
->dest
) == info
->final_bb
)
654 info
->final_bb
= NULL
;
658 /* Get upper and lower bounds of case values, and the covered range. */
659 min_case
= gimple_switch_label (swtch
, 1);
660 max_case
= gimple_switch_label (swtch
, branch_num
- 1);
662 info
->range_min
= CASE_LOW (min_case
);
663 if (CASE_HIGH (max_case
) != NULL_TREE
)
664 info
->range_max
= CASE_HIGH (max_case
);
666 info
->range_max
= CASE_LOW (max_case
);
669 int_const_binop (MINUS_EXPR
, info
->range_max
, info
->range_min
);
671 /* Get a count of the number of case labels. Single-valued case labels
672 simply count as one, but a case range counts double, since it may
673 require two compares if it gets lowered as a branching tree. */
675 for (i
= 1; i
< branch_num
; i
++)
677 tree elt
= gimple_switch_label (swtch
, i
);
680 && ! tree_int_cst_equal (CASE_LOW (elt
), CASE_HIGH (elt
)))
685 /* Get the number of unique non-default targets out of the GIMPLE_SWITCH
686 block. Assume a CFG cleanup would have already removed degenerate
687 switch statements, this allows us to just use EDGE_COUNT. */
688 info
->uniq
= EDGE_COUNT (gimple_bb (swtch
)->succs
) - 1;
691 /* Checks whether the range given by individual case statements of the SWTCH
692 switch statement isn't too big and whether the number of branches actually
693 satisfies the size of the new array. */
696 check_range (struct switch_conv_info
*info
)
698 gcc_assert (info
->range_size
);
699 if (!host_integerp (info
->range_size
, 1))
701 info
->reason
= "index range way too large or otherwise unusable";
705 if ((unsigned HOST_WIDE_INT
) tree_low_cst (info
->range_size
, 1)
706 > ((unsigned) info
->count
* SWITCH_CONVERSION_BRANCH_RATIO
))
708 info
->reason
= "the maximum range-branch ratio exceeded";
715 /* Checks whether all but the FINAL_BB basic blocks are empty. */
718 check_all_empty_except_final (struct switch_conv_info
*info
)
723 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
725 if (e
->dest
== info
->final_bb
)
728 if (!empty_block_p (e
->dest
))
730 info
->reason
= "bad case - a non-final BB not empty";
738 /* This function checks whether all required values in phi nodes in final_bb
739 are constants. Required values are those that correspond to a basic block
740 which is a part of the examined switch statement. It returns true if the
741 phi nodes are OK, otherwise false. */
744 check_final_bb (struct switch_conv_info
*info
)
746 gimple_stmt_iterator gsi
;
749 for (gsi
= gsi_start_phis (info
->final_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
751 gimple phi
= gsi_stmt (gsi
);
756 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
758 basic_block bb
= gimple_phi_arg_edge (phi
, i
)->src
;
760 if (bb
== info
->switch_bb
761 || (single_pred_p (bb
) && single_pred (bb
) == info
->switch_bb
))
765 val
= gimple_phi_arg_def (phi
, i
);
766 if (!is_gimple_ip_invariant (val
))
768 info
->reason
= "non-invariant value from a case";
769 return false; /* Non-invariant argument. */
771 reloc
= initializer_constant_valid_p (val
, TREE_TYPE (val
));
772 if ((flag_pic
&& reloc
!= null_pointer_node
)
773 || (!flag_pic
&& reloc
== NULL_TREE
))
777 = "value from a case would need runtime relocations";
780 = "value from a case is not a valid initializer";
790 /* The following function allocates default_values, target_{in,out}_names and
791 constructors arrays. The last one is also populated with pointers to
792 vectors that will become constructors of new arrays. */
795 create_temp_arrays (struct switch_conv_info
*info
)
799 info
->default_values
= XCNEWVEC (tree
, info
->phi_count
* 3);
800 info
->constructors
= XCNEWVEC (VEC (constructor_elt
, gc
) *, info
->phi_count
);
801 info
->target_inbound_names
= info
->default_values
+ info
->phi_count
;
802 info
->target_outbound_names
= info
->target_inbound_names
+ info
->phi_count
;
803 for (i
= 0; i
< info
->phi_count
; i
++)
804 info
->constructors
[i
]
805 = VEC_alloc (constructor_elt
, gc
, tree_low_cst (info
->range_size
, 1) + 1);
808 /* Free the arrays created by create_temp_arrays(). The vectors that are
809 created by that function are not freed here, however, because they have
810 already become constructors and must be preserved. */
813 free_temp_arrays (struct switch_conv_info
*info
)
815 XDELETEVEC (info
->constructors
);
816 XDELETEVEC (info
->default_values
);
819 /* Populate the array of default values in the order of phi nodes.
820 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch. */
823 gather_default_values (tree default_case
, struct switch_conv_info
*info
)
825 gimple_stmt_iterator gsi
;
826 basic_block bb
= label_to_block (CASE_LABEL (default_case
));
830 gcc_assert (CASE_LOW (default_case
) == NULL_TREE
);
832 if (bb
== info
->final_bb
)
833 e
= find_edge (info
->switch_bb
, bb
);
835 e
= single_succ_edge (bb
);
837 for (gsi
= gsi_start_phis (info
->final_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
839 gimple phi
= gsi_stmt (gsi
);
840 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
842 info
->default_values
[i
++] = val
;
846 /* The following function populates the vectors in the constructors array with
847 future contents of the static arrays. The vectors are populated in the
848 order of phi nodes. SWTCH is the switch statement being converted. */
851 build_constructors (gimple swtch
, struct switch_conv_info
*info
)
853 unsigned i
, branch_num
= gimple_switch_num_labels (swtch
);
854 tree pos
= info
->range_min
;
856 for (i
= 1; i
< branch_num
; i
++)
858 tree cs
= gimple_switch_label (swtch
, i
);
859 basic_block bb
= label_to_block (CASE_LABEL (cs
));
862 gimple_stmt_iterator gsi
;
865 if (bb
== info
->final_bb
)
866 e
= find_edge (info
->switch_bb
, bb
);
868 e
= single_succ_edge (bb
);
871 while (tree_int_cst_lt (pos
, CASE_LOW (cs
)))
874 for (k
= 0; k
< info
->phi_count
; k
++)
876 constructor_elt
*elt
;
878 elt
= VEC_quick_push (constructor_elt
,
879 info
->constructors
[k
], NULL
);
880 elt
->index
= int_const_binop (MINUS_EXPR
, pos
,
882 elt
->value
= info
->default_values
[k
];
885 pos
= int_const_binop (PLUS_EXPR
, pos
, integer_one_node
);
887 gcc_assert (tree_int_cst_equal (pos
, CASE_LOW (cs
)));
891 high
= CASE_HIGH (cs
);
893 high
= CASE_LOW (cs
);
894 for (gsi
= gsi_start_phis (info
->final_bb
);
895 !gsi_end_p (gsi
); gsi_next (&gsi
))
897 gimple phi
= gsi_stmt (gsi
);
898 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
899 tree low
= CASE_LOW (cs
);
904 constructor_elt
*elt
;
906 elt
= VEC_quick_push (constructor_elt
,
907 info
->constructors
[j
], NULL
);
908 elt
->index
= int_const_binop (MINUS_EXPR
, pos
, info
->range_min
);
911 pos
= int_const_binop (PLUS_EXPR
, pos
, integer_one_node
);
912 } while (!tree_int_cst_lt (high
, pos
)
913 && tree_int_cst_lt (low
, pos
));
919 /* If all values in the constructor vector are the same, return the value.
920 Otherwise return NULL_TREE. Not supposed to be called for empty
924 constructor_contains_same_values_p (VEC (constructor_elt
, gc
) *vec
)
927 tree prev
= NULL_TREE
;
928 constructor_elt
*elt
;
930 FOR_EACH_VEC_ELT (constructor_elt
, vec
, i
, elt
)
934 else if (!operand_equal_p (elt
->value
, prev
, OEP_ONLY_CONST
))
940 /* Return type which should be used for array elements, either TYPE,
941 or for integral type some smaller integral type that can still hold
942 all the constants. */
945 array_value_type (gimple swtch
, tree type
, int num
,
946 struct switch_conv_info
*info
)
948 unsigned int i
, len
= VEC_length (constructor_elt
, info
->constructors
[num
]);
949 constructor_elt
*elt
;
950 enum machine_mode mode
;
954 if (!INTEGRAL_TYPE_P (type
))
957 mode
= GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type
)));
958 if (GET_MODE_SIZE (TYPE_MODE (type
)) <= GET_MODE_SIZE (mode
))
961 if (len
< (optimize_bb_for_size_p (gimple_bb (swtch
)) ? 2 : 32))
964 FOR_EACH_VEC_ELT (constructor_elt
, info
->constructors
[num
], i
, elt
)
968 if (TREE_CODE (elt
->value
) != INTEGER_CST
)
971 cst
= TREE_INT_CST (elt
->value
);
974 unsigned int prec
= GET_MODE_BITSIZE (mode
);
975 if (prec
> HOST_BITS_PER_WIDE_INT
)
979 && double_int_equal_p (cst
, double_int_zext (cst
, prec
)))
982 && double_int_equal_p (cst
, double_int_sext (cst
, prec
)))
988 && double_int_equal_p (cst
, double_int_sext (cst
, prec
)))
997 mode
= GET_MODE_WIDER_MODE (mode
);
999 || GET_MODE_SIZE (mode
) >= GET_MODE_SIZE (TYPE_MODE (type
)))
1005 sign
= TYPE_UNSIGNED (type
) ? 1 : -1;
1006 smaller_type
= lang_hooks
.types
.type_for_mode (mode
, sign
>= 0);
1007 if (GET_MODE_SIZE (TYPE_MODE (type
))
1008 <= GET_MODE_SIZE (TYPE_MODE (smaller_type
)))
1011 return smaller_type
;
1014 /* Create an appropriate array type and declaration and assemble a static array
1015 variable. Also create a load statement that initializes the variable in
1016 question with a value from the static array. SWTCH is the switch statement
1017 being converted, NUM is the index to arrays of constructors, default values
1018 and target SSA names for this particular array. ARR_INDEX_TYPE is the type
1019 of the index of the new array, PHI is the phi node of the final BB that
1020 corresponds to the value that will be loaded from the created array. TIDX
1021 is an ssa name of a temporary variable holding the index for loads from the
1025 build_one_array (gimple swtch
, int num
, tree arr_index_type
, gimple phi
,
1026 tree tidx
, struct switch_conv_info
*info
)
1030 gimple_stmt_iterator gsi
= gsi_for_stmt (swtch
);
1031 location_t loc
= gimple_location (swtch
);
1033 gcc_assert (info
->default_values
[num
]);
1035 name
= make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi
)), NULL
);
1036 info
->target_inbound_names
[num
] = name
;
1038 cst
= constructor_contains_same_values_p (info
->constructors
[num
]);
1040 load
= gimple_build_assign (name
, cst
);
1043 tree array_type
, ctor
, decl
, value_type
, fetch
, default_type
;
1045 default_type
= TREE_TYPE (info
->default_values
[num
]);
1046 value_type
= array_value_type (swtch
, default_type
, num
, info
);
1047 array_type
= build_array_type (value_type
, arr_index_type
);
1048 if (default_type
!= value_type
)
1051 constructor_elt
*elt
;
1053 FOR_EACH_VEC_ELT (constructor_elt
, info
->constructors
[num
], i
, elt
)
1054 elt
->value
= fold_convert (value_type
, elt
->value
);
1056 ctor
= build_constructor (array_type
, info
->constructors
[num
]);
1057 TREE_CONSTANT (ctor
) = true;
1058 TREE_STATIC (ctor
) = true;
1060 decl
= build_decl (loc
, VAR_DECL
, NULL_TREE
, array_type
);
1061 TREE_STATIC (decl
) = 1;
1062 DECL_INITIAL (decl
) = ctor
;
1064 DECL_NAME (decl
) = create_tmp_var_name ("CSWTCH");
1065 DECL_ARTIFICIAL (decl
) = 1;
1066 TREE_CONSTANT (decl
) = 1;
1067 TREE_READONLY (decl
) = 1;
1068 varpool_finalize_decl (decl
);
1070 fetch
= build4 (ARRAY_REF
, value_type
, decl
, tidx
, NULL_TREE
,
1072 if (default_type
!= value_type
)
1074 fetch
= fold_convert (default_type
, fetch
);
1075 fetch
= force_gimple_operand_gsi (&gsi
, fetch
, true, NULL_TREE
,
1076 true, GSI_SAME_STMT
);
1078 load
= gimple_build_assign (name
, fetch
);
1081 SSA_NAME_DEF_STMT (name
) = load
;
1082 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
1084 info
->arr_ref_last
= load
;
1087 /* Builds and initializes static arrays initialized with values gathered from
1088 the SWTCH switch statement. Also creates statements that load values from
1092 build_arrays (gimple swtch
, struct switch_conv_info
*info
)
1094 tree arr_index_type
;
1095 tree tidx
, sub
, tmp
, utype
;
1097 gimple_stmt_iterator gsi
;
1099 location_t loc
= gimple_location (swtch
);
1101 gsi
= gsi_for_stmt (swtch
);
1103 /* Make sure we do not generate arithmetics in a subrange. */
1104 utype
= TREE_TYPE (info
->index_expr
);
1105 if (TREE_TYPE (utype
))
1106 utype
= lang_hooks
.types
.type_for_mode (TYPE_MODE (TREE_TYPE (utype
)), 1);
1108 utype
= lang_hooks
.types
.type_for_mode (TYPE_MODE (utype
), 1);
1110 arr_index_type
= build_index_type (info
->range_size
);
1111 tmp
= create_tmp_var (utype
, "csui");
1112 add_referenced_var (tmp
);
1113 tidx
= make_ssa_name (tmp
, NULL
);
1114 sub
= fold_build2_loc (loc
, MINUS_EXPR
, utype
,
1115 fold_convert_loc (loc
, utype
, info
->index_expr
),
1116 fold_convert_loc (loc
, utype
, info
->range_min
));
1117 sub
= force_gimple_operand_gsi (&gsi
, sub
,
1118 false, NULL
, true, GSI_SAME_STMT
);
1119 stmt
= gimple_build_assign (tidx
, sub
);
1120 SSA_NAME_DEF_STMT (tidx
) = stmt
;
1122 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1124 info
->arr_ref_first
= stmt
;
1126 for (gsi
= gsi_start_phis (info
->final_bb
), i
= 0;
1127 !gsi_end_p (gsi
); gsi_next (&gsi
), i
++)
1128 build_one_array (swtch
, i
, arr_index_type
, gsi_stmt (gsi
), tidx
, info
);
1131 /* Generates and appropriately inserts loads of default values at the position
1132 given by BSI. Returns the last inserted statement. */
1135 gen_def_assigns (gimple_stmt_iterator
*gsi
, struct switch_conv_info
*info
)
1138 gimple assign
= NULL
;
1140 for (i
= 0; i
< info
->phi_count
; i
++)
1143 = make_ssa_name (SSA_NAME_VAR (info
->target_inbound_names
[i
]), NULL
);
1145 info
->target_outbound_names
[i
] = name
;
1146 assign
= gimple_build_assign (name
, info
->default_values
[i
]);
1147 SSA_NAME_DEF_STMT (name
) = assign
;
1148 gsi_insert_before (gsi
, assign
, GSI_SAME_STMT
);
1149 update_stmt (assign
);
1154 /* Deletes the unused bbs and edges that now contain the switch statement and
1155 its empty branch bbs. BBD is the now dead BB containing the original switch
1156 statement, FINAL is the last BB of the converted switch statement (in terms
1160 prune_bbs (basic_block bbd
, basic_block final
)
1165 for (ei
= ei_start (bbd
->succs
); (e
= ei_safe_edge (ei
)); )
1171 delete_basic_block (bb
);
1173 delete_basic_block (bbd
);
1176 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
1177 from the basic block loading values from an array and E2F from the basic
1178 block loading default values. BBF is the last switch basic block (see the
1179 bbf description in the comment below). */
1182 fix_phi_nodes (edge e1f
, edge e2f
, basic_block bbf
,
1183 struct switch_conv_info
*info
)
1185 gimple_stmt_iterator gsi
;
1188 for (gsi
= gsi_start_phis (bbf
), i
= 0;
1189 !gsi_end_p (gsi
); gsi_next (&gsi
), i
++)
1191 gimple phi
= gsi_stmt (gsi
);
1192 add_phi_arg (phi
, info
->target_inbound_names
[i
], e1f
, UNKNOWN_LOCATION
);
1193 add_phi_arg (phi
, info
->target_outbound_names
[i
], e2f
, UNKNOWN_LOCATION
);
1197 /* Creates a check whether the switch expression value actually falls into the
1198 range given by all the cases. If it does not, the temporaries are loaded
1199 with default values instead. SWTCH is the switch statement being converted.
1201 bb0 is the bb with the switch statement, however, we'll end it with a
1204 bb1 is the bb to be used when the range check went ok. It is derived from
1207 bb2 is the bb taken when the expression evaluated outside of the range
1208 covered by the created arrays. It is populated by loads of default
1211 bbF is a fall through for both bb1 and bb2 and contains exactly what
1212 originally followed the switch statement.
1214 bbD contains the switch statement (in the end). It is unreachable but we
1215 still need to strip off its edges.
1219 gen_inbound_check (gimple swtch
, struct switch_conv_info
*info
)
1221 tree label_decl1
= create_artificial_label (UNKNOWN_LOCATION
);
1222 tree label_decl2
= create_artificial_label (UNKNOWN_LOCATION
);
1223 tree label_decl3
= create_artificial_label (UNKNOWN_LOCATION
);
1224 gimple label1
, label2
, label3
;
1231 gimple_stmt_iterator gsi
;
1232 basic_block bb0
, bb1
, bb2
, bbf
, bbd
;
1233 edge e01
, e02
, e21
, e1d
, e1f
, e2f
;
1234 location_t loc
= gimple_location (swtch
);
1236 gcc_assert (info
->default_values
);
1238 bb0
= gimple_bb (swtch
);
1240 tidx
= gimple_assign_lhs (info
->arr_ref_first
);
1241 utype
= TREE_TYPE (tidx
);
1243 /* (end of) block 0 */
1244 gsi
= gsi_for_stmt (info
->arr_ref_first
);
1247 bound
= fold_convert_loc (loc
, utype
, info
->range_size
);
1248 cond_stmt
= gimple_build_cond (LE_EXPR
, tidx
, bound
, NULL_TREE
, NULL_TREE
);
1249 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1250 update_stmt (cond_stmt
);
1253 label2
= gimple_build_label (label_decl2
);
1254 gsi_insert_before (&gsi
, label2
, GSI_SAME_STMT
);
1255 last_assign
= gen_def_assigns (&gsi
, info
);
1258 label1
= gimple_build_label (label_decl1
);
1259 gsi_insert_before (&gsi
, label1
, GSI_SAME_STMT
);
1262 gsi
= gsi_start_bb (info
->final_bb
);
1263 label3
= gimple_build_label (label_decl3
);
1264 gsi_insert_before (&gsi
, label3
, GSI_SAME_STMT
);
1267 e02
= split_block (bb0
, cond_stmt
);
1270 e21
= split_block (bb2
, last_assign
);
1274 e1d
= split_block (bb1
, info
->arr_ref_last
);
1278 /* flags and profiles of the edge for in-range values */
1279 e01
= make_edge (bb0
, bb1
, EDGE_TRUE_VALUE
);
1280 e01
->probability
= REG_BR_PROB_BASE
- info
->default_prob
;
1281 e01
->count
= info
->other_count
;
1283 /* flags and profiles of the edge taking care of out-of-range values */
1284 e02
->flags
&= ~EDGE_FALLTHRU
;
1285 e02
->flags
|= EDGE_FALSE_VALUE
;
1286 e02
->probability
= info
->default_prob
;
1287 e02
->count
= info
->default_count
;
1289 bbf
= info
->final_bb
;
1291 e1f
= make_edge (bb1
, bbf
, EDGE_FALLTHRU
);
1292 e1f
->probability
= REG_BR_PROB_BASE
;
1293 e1f
->count
= info
->other_count
;
1295 e2f
= make_edge (bb2
, bbf
, EDGE_FALLTHRU
);
1296 e2f
->probability
= REG_BR_PROB_BASE
;
1297 e2f
->count
= info
->default_count
;
1299 /* frequencies of the new BBs */
1300 bb1
->frequency
= EDGE_FREQUENCY (e01
);
1301 bb2
->frequency
= EDGE_FREQUENCY (e02
);
1302 bbf
->frequency
= EDGE_FREQUENCY (e1f
) + EDGE_FREQUENCY (e2f
);
1304 /* Tidy blocks that have become unreachable. */
1305 prune_bbs (bbd
, info
->final_bb
);
1307 /* Fixup the PHI nodes in bbF. */
1308 fix_phi_nodes (e1f
, e2f
, bbf
, info
);
1310 /* Fix the dominator tree, if it is available. */
1311 if (dom_info_available_p (CDI_DOMINATORS
))
1313 VEC (basic_block
, heap
) *bbs_to_fix_dom
;
1315 set_immediate_dominator (CDI_DOMINATORS
, bb1
, bb0
);
1316 set_immediate_dominator (CDI_DOMINATORS
, bb2
, bb0
);
1317 if (! get_immediate_dominator (CDI_DOMINATORS
, bbf
))
1318 /* If bbD was the immediate dominator ... */
1319 set_immediate_dominator (CDI_DOMINATORS
, bbf
, bb0
);
1321 bbs_to_fix_dom
= VEC_alloc (basic_block
, heap
, 4);
1322 VEC_quick_push (basic_block
, bbs_to_fix_dom
, bb0
);
1323 VEC_quick_push (basic_block
, bbs_to_fix_dom
, bb1
);
1324 VEC_quick_push (basic_block
, bbs_to_fix_dom
, bb2
);
1325 VEC_quick_push (basic_block
, bbs_to_fix_dom
, bbf
);
1327 iterate_fix_dominators (CDI_DOMINATORS
, bbs_to_fix_dom
, true);
1328 VEC_free (basic_block
, heap
, bbs_to_fix_dom
);
1332 /* The following function is invoked on every switch statement (the current one
1333 is given in SWTCH) and runs the individual phases of switch conversion on it
1334 one after another until one fails or the conversion is completed.
1335 Returns NULL on success, or a pointer to a string with the reason why the
1336 conversion failed. */
1339 process_switch (gimple swtch
)
1341 struct switch_conv_info info
;
1343 /* Degenerate case with only a default label should never happen. */
1344 gcc_checking_assert (gimple_switch_num_labels (swtch
) > 1);
1346 collect_switch_conv_info (swtch
, &info
);
1348 /* No error markers should reach here (they should be filtered out
1349 during gimplification). */
1350 gcc_checking_assert (TREE_TYPE (info
.index_expr
) != error_mark_node
);
1352 /* A switch on a constant should have been optimized in tree-cfg-cleanup. */
1353 gcc_checking_assert (! TREE_CONSTANT (info
.index_expr
));
1355 if (info
.uniq
<= MAX_CASE_BIT_TESTS
)
1357 if (expand_switch_using_bit_tests_p (info
.range_size
,
1358 info
.uniq
, info
.count
))
1361 fputs (" expanding as bit test is preferable\n", dump_file
);
1362 emit_case_bit_tests (swtch
, info
.index_expr
,
1363 info
.range_min
, info
.range_size
);
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
);
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
);
1390 if (!check_final_bb (&info
))
1392 gcc_assert (info
.reason
);
1396 /* At this point all checks have passed and we can proceed with the
1399 create_temp_arrays (&info
);
1400 gather_default_values (gimple_switch_label (swtch
, 0), &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. */
1407 free_temp_arrays (&info
);
1411 /* The main function of the pass scans statements for switches and invokes
1412 process_switch on them. */
1415 do_switchconv (void)
1421 const char *failure_reason
;
1422 gimple stmt
= last_stmt (bb
);
1423 if (stmt
&& gimple_code (stmt
) == GIMPLE_SWITCH
)
1427 expanded_location loc
= expand_location (gimple_location (stmt
));
1429 fprintf (dump_file
, "beginning to process the following "
1430 "SWITCH statement (%s:%d) : ------- \n",
1431 loc
.file
, loc
.line
);
1432 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1433 putc ('\n', dump_file
);
1436 failure_reason
= process_switch (stmt
);
1437 if (! failure_reason
)
1441 fputs ("Switch converted\n", dump_file
);
1442 fputs ("--------------------------------\n", dump_file
);
1445 /* Make no effort to update the post-dominator tree. It is actually not
1446 that hard for the transformations we have performed, but it is not
1447 supported by iterate_fix_dominators. */
1448 free_dominance_info (CDI_POST_DOMINATORS
);
1454 fputs ("Bailing out - ", dump_file
);
1455 fputs (failure_reason
, dump_file
);
1456 fputs ("\n--------------------------------\n", dump_file
);
1465 /* The pass gate. */
1468 switchconv_gate (void)
1470 return flag_tree_switch_conversion
!= 0;
1473 struct gimple_opt_pass pass_convert_switch
=
1477 "switchconv", /* name */
1478 switchconv_gate
, /* gate */
1479 do_switchconv
, /* execute */
1482 0, /* static_pass_number */
1483 TV_TREE_SWITCH_CONVERSION
, /* tv_id */
1484 PROP_cfg
| PROP_ssa
, /* properties_required */
1485 0, /* properties_provided */
1486 0, /* properties_destroyed */
1487 0, /* todo_flags_start */
1489 | TODO_ggc_collect
| TODO_verify_ssa
1491 | TODO_verify_flow
/* todo_flags_finish */