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"
41 /* ??? For lang_hooks.types.type_for_mode, but is there a word_mode
42 type in the GIMPLE type system that is language-independent? */
43 #include "langhooks.h"
45 /* Need to include expr.h and optabs.h for lshift_cheap_p. */
49 /* Maximum number of case bit tests.
50 FIXME: This should be derived from PARAM_CASE_VALUES_THRESHOLD and
51 targetm.case_values_threshold(), or be its own param. */
52 #define MAX_CASE_BIT_TESTS 3
54 /* Split the basic block at the statement pointed to by GSIP, and insert
55 a branch to the target basic block of E_TRUE conditional on tree
58 It is assumed that there is already an edge from the to-be-split
59 basic block to E_TRUE->dest block. This edge is removed, and the
60 profile information on the edge is re-used for the new conditional
63 The CFG is updated. The dominator tree will not be valid after
64 this transformation, but the immediate dominators are updated if
65 UPDATE_DOMINATORS is true.
67 Returns the newly created basic block. */
70 hoist_edge_and_branch_if_true (gimple_stmt_iterator
*gsip
,
71 tree cond
, edge e_true
,
72 bool update_dominators
)
77 basic_block new_bb
, split_bb
= gsi_bb (*gsip
);
78 bool dominated_e_true
= false;
80 gcc_assert (e_true
->src
== split_bb
);
83 && get_immediate_dominator (CDI_DOMINATORS
, e_true
->dest
) == split_bb
)
84 dominated_e_true
= true;
86 tmp
= force_gimple_operand_gsi (gsip
, cond
, /*simple=*/true, NULL
,
87 /*before=*/true, GSI_SAME_STMT
);
88 cond_stmt
= gimple_build_cond_from_tree (tmp
, NULL_TREE
, NULL_TREE
);
89 gsi_insert_before (gsip
, cond_stmt
, GSI_SAME_STMT
);
91 e_false
= split_block (split_bb
, cond_stmt
);
92 new_bb
= e_false
->dest
;
93 redirect_edge_pred (e_true
, split_bb
);
95 e_true
->flags
&= ~EDGE_FALLTHRU
;
96 e_true
->flags
|= EDGE_TRUE_VALUE
;
98 e_false
->flags
&= ~EDGE_FALLTHRU
;
99 e_false
->flags
|= EDGE_FALSE_VALUE
;
100 e_false
->probability
= REG_BR_PROB_BASE
- e_true
->probability
;
101 e_false
->count
= split_bb
->count
- e_true
->count
;
102 new_bb
->count
= e_false
->count
;
104 if (update_dominators
)
106 if (dominated_e_true
)
107 set_immediate_dominator (CDI_DOMINATORS
, e_true
->dest
, split_bb
);
108 set_immediate_dominator (CDI_DOMINATORS
, e_false
->dest
, split_bb
);
115 /* Determine whether "1 << x" is relatively cheap in word_mode. */
116 /* FIXME: This is the function that we need rtl.h and optabs.h for.
117 This function (and similar RTL-related cost code in e.g. IVOPTS) should
118 be moved to some kind of interface file for GIMPLE/RTL interactions. */
120 lshift_cheap_p (void)
122 /* FIXME: This should be made target dependent via this "this_target"
123 mechanism, similar to e.g. can_copy_init_p in gcse.c. */
124 static bool init
[2] = {false, false};
125 static bool cheap
[2] = {true, true};
128 /* If the targer has no lshift in word_mode, the operation will most
129 probably not be cheap. ??? Does GCC even work for such targets? */
130 if (optab_handler (ashl_optab
, word_mode
) == CODE_FOR_nothing
)
133 speed_p
= optimize_insn_for_speed_p ();
137 rtx reg
= gen_raw_REG (word_mode
, 10000);
138 int cost
= set_src_cost (gen_rtx_ASHIFT (word_mode
, const1_rtx
, reg
),
140 cheap
[speed_p
] = cost
< COSTS_N_INSNS (MAX_CASE_BIT_TESTS
);
141 init
[speed_p
] = true;
144 return cheap
[speed_p
];
147 /* Return true if a switch should be expanded as a bit test.
148 RANGE is the difference between highest and lowest case.
149 UNIQ is number of unique case node targets, not counting the default case.
150 COUNT is the number of comparisons needed, not counting the default case. */
153 expand_switch_using_bit_tests_p (tree range
,
157 return (((uniq
== 1 && count
>= 3)
158 || (uniq
== 2 && count
>= 5)
159 || (uniq
== 3 && count
>= 6))
161 && compare_tree_int (range
, GET_MODE_BITSIZE (word_mode
)) < 0
162 && compare_tree_int (range
, 0) > 0);
165 /* Implement switch statements with bit tests
167 A GIMPLE switch statement can be expanded to a short sequence of bit-wise
168 comparisons. "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)"
169 where CST and MINVAL are integer constants. This is better than a series
170 of compare-and-banch insns in some cases, e.g. we can implement:
172 if ((x==4) || (x==6) || (x==9) || (x==11))
174 as a single bit test:
176 if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11)))
178 This transformation is only applied if the number of case targets is small,
179 if CST constains at least 3 bits, and "1 << x" is cheap. The bit tests are
180 performed in "word_mode".
182 The following example shows the code the transformation generates:
188 case '0': case '1': case '2': case '3': case '4':
189 case '5': case '6': case '7': case '8': case '9':
190 case 'A': case 'B': case 'C': case 'D': case 'E':
202 if (tmp1 > (70 - 48)) goto L2;
204 tmp3 = 0b11111100000001111111111;
205 if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2;
212 TODO: There are still some improvements to this transformation that could
215 * A narrower mode than word_mode could be used if that is cheaper, e.g.
216 for x86_64 where a narrower-mode shift may result in smaller code.
218 * The compounded constant could be shifted rather than the one. The
219 test would be either on the sign bit or on the least significant bit,
220 depending on the direction of the shift. On some machines, the test
221 for the branch would be free if the bit to test is already set by the
224 This transformation was contributed by Roger Sayle, see this e-mail:
225 http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html
228 /* A case_bit_test represents a set of case nodes that may be
229 selected from using a bit-wise comparison. HI and LO hold
230 the integer to be tested against, TARGET_EDGE contains the
231 edge to the basic block to jump to upon success and BITS
232 counts the number of case nodes handled by this test,
233 typically the number of bits set in HI:LO. The LABEL field
234 is used to quickly identify all cases in this set without
235 looking at label_to_block for every case label. */
246 /* Comparison function for qsort to order bit tests by decreasing
247 probability of execution. Our best guess comes from a measured
248 profile. If the profile counts are equal, break even on the
249 number of case nodes, i.e. the node with the most cases gets
252 TODO: Actually this currently runs before a profile is available.
253 Therefore the case-as-bit-tests transformation should be done
254 later in the pass pipeline, or something along the lines of
255 "Efficient and effective branch reordering using profile data"
256 (Yang et. al., 2002) should be implemented (although, how good
257 is a paper is called "Efficient and effective ..." when the
258 latter is implied by the former, but oh well...). */
261 case_bit_test_cmp (const void *p1
, const void *p2
)
263 const struct case_bit_test
*const d1
= (const struct case_bit_test
*) p1
;
264 const struct case_bit_test
*const d2
= (const struct case_bit_test
*) p2
;
266 if (d2
->target_edge
->count
!= d1
->target_edge
->count
)
267 return d2
->target_edge
->count
- d1
->target_edge
->count
;
268 if (d2
->bits
!= d1
->bits
)
269 return d2
->bits
- d1
->bits
;
271 /* Stabilize the sort. */
272 return LABEL_DECL_UID (d2
->label
) - LABEL_DECL_UID (d1
->label
);
275 /* Expand a switch statement by a short sequence of bit-wise
276 comparisons. "switch(x)" is effectively converted into
277 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
280 INDEX_EXPR is the value being switched on.
282 MINVAL is the lowest case value of in the case nodes,
283 and RANGE is highest value minus MINVAL. MINVAL and RANGE
284 are not guaranteed to be of the same type as INDEX_EXPR
285 (the gimplifier doesn't change the type of case label values,
286 and MINVAL and RANGE are derived from those values).
288 There *MUST* be MAX_CASE_BIT_TESTS or less unique case
292 emit_case_bit_tests (gimple swtch
, tree index_expr
,
293 tree minval
, tree range
)
295 struct case_bit_test test
[MAX_CASE_BIT_TESTS
];
296 unsigned int i
, j
, k
;
299 basic_block switch_bb
= gimple_bb (swtch
);
300 basic_block default_bb
, new_default_bb
, new_bb
;
302 bool update_dom
= dom_info_available_p (CDI_DOMINATORS
);
304 VEC (basic_block
, heap
) *bbs_to_fix_dom
= NULL
;
306 tree index_type
= TREE_TYPE (index_expr
);
307 tree unsigned_index_type
= unsigned_type_for (index_type
);
308 unsigned int branch_num
= gimple_switch_num_labels (swtch
);
310 gimple_stmt_iterator gsi
;
314 tree word_type_node
= lang_hooks
.types
.type_for_mode (word_mode
, 1);
315 tree word_mode_zero
= fold_convert (word_type_node
, integer_zero_node
);
316 tree word_mode_one
= fold_convert (word_type_node
, integer_one_node
);
318 memset (&test
, 0, sizeof (test
));
320 /* Get the edge for the default case. */
321 tmp
= gimple_switch_default_label (swtch
);
322 default_bb
= label_to_block (CASE_LABEL (tmp
));
323 default_edge
= find_edge (switch_bb
, default_bb
);
325 /* Go through all case labels, and collect the case labels, profile
326 counts, and other information we need to build the branch tests. */
328 for (i
= 1; i
< branch_num
; i
++)
331 tree cs
= gimple_switch_label (swtch
, i
);
332 tree label
= CASE_LABEL (cs
);
333 edge e
= find_edge (switch_bb
, label_to_block (label
));
334 for (k
= 0; k
< count
; k
++)
335 if (e
== test
[k
].target_edge
)
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_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 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 csui
= make_ssa_name (word_type_node
, NULL
);
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
= build_int_cst_wide (word_type_node
, test
[k
].lo
, test
[k
].hi
);
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 VEC_safe_push (basic_block
, heap
, bbs_to_fix_dom
, 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 VEC_free (basic_block
, heap
, bbs_to_fix_dom
);
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
, 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. */
591 /* String reason why the case wasn't a good candidate that is written to the
592 dump file, if there is one. */
595 /* Parameters for expand_switch_using_bit_tests. Should be computed
596 the same way as in expand_case. */
601 /* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */
604 collect_switch_conv_info (gimple 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
;
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
);
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
)
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 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
632 if (! single_pred_p (e
->dest
))
634 info
->final_bb
= e
->dest
;
639 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
641 if (e
->dest
== info
->final_bb
)
644 if (single_pred_p (e
->dest
)
645 && single_succ_p (e
->dest
)
646 && single_succ (e
->dest
) == info
->final_bb
)
649 info
->final_bb
= NULL
;
653 /* Get upper and lower bounds of case values, and the covered range. */
654 min_case
= gimple_switch_label (swtch
, 1);
655 max_case
= gimple_switch_label (swtch
, branch_num
- 1);
657 info
->range_min
= CASE_LOW (min_case
);
658 if (CASE_HIGH (max_case
) != NULL_TREE
)
659 info
->range_max
= CASE_HIGH (max_case
);
661 info
->range_max
= CASE_LOW (max_case
);
664 int_const_binop (MINUS_EXPR
, info
->range_max
, info
->range_min
);
666 /* Get a count of the number of case labels. Single-valued case labels
667 simply count as one, but a case range counts double, since it may
668 require two compares if it gets lowered as a branching tree. */
670 for (i
= 1; i
< branch_num
; i
++)
672 tree elt
= gimple_switch_label (swtch
, i
);
675 && ! tree_int_cst_equal (CASE_LOW (elt
), CASE_HIGH (elt
)))
680 /* Get the number of unique non-default targets out of the GIMPLE_SWITCH
681 block. Assume a CFG cleanup would have already removed degenerate
682 switch statements, this allows us to just use EDGE_COUNT. */
683 info
->uniq
= EDGE_COUNT (gimple_bb (swtch
)->succs
) - 1;
686 /* Checks whether the range given by individual case statements of the SWTCH
687 switch statement isn't too big and whether the number of branches actually
688 satisfies the size of the new array. */
691 check_range (struct switch_conv_info
*info
)
693 gcc_assert (info
->range_size
);
694 if (!host_integerp (info
->range_size
, 1))
696 info
->reason
= "index range way too large or otherwise unusable";
700 if ((unsigned HOST_WIDE_INT
) tree_low_cst (info
->range_size
, 1)
701 > ((unsigned) info
->count
* SWITCH_CONVERSION_BRANCH_RATIO
))
703 info
->reason
= "the maximum range-branch ratio exceeded";
710 /* Checks whether all but the FINAL_BB basic blocks are empty. */
713 check_all_empty_except_final (struct switch_conv_info
*info
)
718 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
720 if (e
->dest
== info
->final_bb
)
723 if (!empty_block_p (e
->dest
))
725 info
->reason
= "bad case - a non-final BB not empty";
733 /* This function checks whether all required values in phi nodes in final_bb
734 are constants. Required values are those that correspond to a basic block
735 which is a part of the examined switch statement. It returns true if the
736 phi nodes are OK, otherwise false. */
739 check_final_bb (struct switch_conv_info
*info
)
741 gimple_stmt_iterator gsi
;
744 for (gsi
= gsi_start_phis (info
->final_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
746 gimple phi
= gsi_stmt (gsi
);
751 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
753 basic_block bb
= gimple_phi_arg_edge (phi
, i
)->src
;
755 if (bb
== info
->switch_bb
756 || (single_pred_p (bb
) && single_pred (bb
) == info
->switch_bb
))
760 val
= gimple_phi_arg_def (phi
, i
);
761 if (!is_gimple_ip_invariant (val
))
763 info
->reason
= "non-invariant value from a case";
764 return false; /* Non-invariant argument. */
766 reloc
= initializer_constant_valid_p (val
, TREE_TYPE (val
));
767 if ((flag_pic
&& reloc
!= null_pointer_node
)
768 || (!flag_pic
&& reloc
== NULL_TREE
))
772 = "value from a case would need runtime relocations";
775 = "value from a case is not a valid initializer";
785 /* The following function allocates default_values, target_{in,out}_names and
786 constructors arrays. The last one is also populated with pointers to
787 vectors that will become constructors of new arrays. */
790 create_temp_arrays (struct switch_conv_info
*info
)
794 info
->default_values
= XCNEWVEC (tree
, info
->phi_count
* 3);
795 info
->constructors
= XCNEWVEC (VEC (constructor_elt
, gc
) *, info
->phi_count
);
796 info
->target_inbound_names
= info
->default_values
+ info
->phi_count
;
797 info
->target_outbound_names
= info
->target_inbound_names
+ info
->phi_count
;
798 for (i
= 0; i
< info
->phi_count
; i
++)
799 info
->constructors
[i
]
800 = VEC_alloc (constructor_elt
, gc
, tree_low_cst (info
->range_size
, 1) + 1);
803 /* Free the arrays created by create_temp_arrays(). The vectors that are
804 created by that function are not freed here, however, because they have
805 already become constructors and must be preserved. */
808 free_temp_arrays (struct switch_conv_info
*info
)
810 XDELETEVEC (info
->constructors
);
811 XDELETEVEC (info
->default_values
);
814 /* Populate the array of default values in the order of phi nodes.
815 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch. */
818 gather_default_values (tree default_case
, struct switch_conv_info
*info
)
820 gimple_stmt_iterator gsi
;
821 basic_block bb
= label_to_block (CASE_LABEL (default_case
));
825 gcc_assert (CASE_LOW (default_case
) == NULL_TREE
);
827 if (bb
== info
->final_bb
)
828 e
= find_edge (info
->switch_bb
, bb
);
830 e
= single_succ_edge (bb
);
832 for (gsi
= gsi_start_phis (info
->final_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
834 gimple phi
= gsi_stmt (gsi
);
835 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
837 info
->default_values
[i
++] = val
;
841 /* The following function populates the vectors in the constructors array with
842 future contents of the static arrays. The vectors are populated in the
843 order of phi nodes. SWTCH is the switch statement being converted. */
846 build_constructors (gimple swtch
, struct switch_conv_info
*info
)
848 unsigned i
, branch_num
= gimple_switch_num_labels (swtch
);
849 tree pos
= info
->range_min
;
851 for (i
= 1; i
< branch_num
; i
++)
853 tree cs
= gimple_switch_label (swtch
, i
);
854 basic_block bb
= label_to_block (CASE_LABEL (cs
));
857 gimple_stmt_iterator gsi
;
860 if (bb
== info
->final_bb
)
861 e
= find_edge (info
->switch_bb
, bb
);
863 e
= single_succ_edge (bb
);
866 while (tree_int_cst_lt (pos
, CASE_LOW (cs
)))
869 for (k
= 0; k
< info
->phi_count
; k
++)
871 constructor_elt
*elt
;
873 elt
= VEC_quick_push (constructor_elt
,
874 info
->constructors
[k
], NULL
);
875 elt
->index
= int_const_binop (MINUS_EXPR
, pos
,
877 elt
->value
= info
->default_values
[k
];
880 pos
= int_const_binop (PLUS_EXPR
, pos
, integer_one_node
);
882 gcc_assert (tree_int_cst_equal (pos
, CASE_LOW (cs
)));
886 high
= CASE_HIGH (cs
);
888 high
= CASE_LOW (cs
);
889 for (gsi
= gsi_start_phis (info
->final_bb
);
890 !gsi_end_p (gsi
); gsi_next (&gsi
))
892 gimple phi
= gsi_stmt (gsi
);
893 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
894 tree low
= CASE_LOW (cs
);
899 constructor_elt
*elt
;
901 elt
= VEC_quick_push (constructor_elt
,
902 info
->constructors
[j
], NULL
);
903 elt
->index
= int_const_binop (MINUS_EXPR
, pos
, info
->range_min
);
906 pos
= int_const_binop (PLUS_EXPR
, pos
, integer_one_node
);
907 } while (!tree_int_cst_lt (high
, pos
)
908 && tree_int_cst_lt (low
, pos
));
914 /* If all values in the constructor vector are the same, return the value.
915 Otherwise return NULL_TREE. Not supposed to be called for empty
919 constructor_contains_same_values_p (VEC (constructor_elt
, gc
) *vec
)
922 tree prev
= NULL_TREE
;
923 constructor_elt
*elt
;
925 FOR_EACH_VEC_ELT (constructor_elt
, vec
, i
, elt
)
929 else if (!operand_equal_p (elt
->value
, prev
, OEP_ONLY_CONST
))
935 /* Return type which should be used for array elements, either TYPE,
936 or for integral type some smaller integral type that can still hold
937 all the constants. */
940 array_value_type (gimple swtch
, tree type
, int num
,
941 struct switch_conv_info
*info
)
943 unsigned int i
, len
= VEC_length (constructor_elt
, info
->constructors
[num
]);
944 constructor_elt
*elt
;
945 enum machine_mode mode
;
949 if (!INTEGRAL_TYPE_P (type
))
952 mode
= GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type
)));
953 if (GET_MODE_SIZE (TYPE_MODE (type
)) <= GET_MODE_SIZE (mode
))
956 if (len
< (optimize_bb_for_size_p (gimple_bb (swtch
)) ? 2 : 32))
959 FOR_EACH_VEC_ELT (constructor_elt
, info
->constructors
[num
], i
, elt
)
963 if (TREE_CODE (elt
->value
) != INTEGER_CST
)
966 cst
= TREE_INT_CST (elt
->value
);
969 unsigned int prec
= GET_MODE_BITSIZE (mode
);
970 if (prec
> HOST_BITS_PER_WIDE_INT
)
973 if (sign
>= 0 && cst
== cst
.zext (prec
))
975 if (sign
== 0 && cst
== cst
.sext (prec
))
980 if (sign
<= 0 && cst
== cst
.sext (prec
))
989 mode
= GET_MODE_WIDER_MODE (mode
);
991 || GET_MODE_SIZE (mode
) >= GET_MODE_SIZE (TYPE_MODE (type
)))
997 sign
= TYPE_UNSIGNED (type
) ? 1 : -1;
998 smaller_type
= lang_hooks
.types
.type_for_mode (mode
, sign
>= 0);
999 if (GET_MODE_SIZE (TYPE_MODE (type
))
1000 <= GET_MODE_SIZE (TYPE_MODE (smaller_type
)))
1003 return smaller_type
;
1006 /* Create an appropriate array type and declaration and assemble a static array
1007 variable. Also create a load statement that initializes the variable in
1008 question with a value from the static array. SWTCH is the switch statement
1009 being converted, NUM is the index to arrays of constructors, default values
1010 and target SSA names for this particular array. ARR_INDEX_TYPE is the type
1011 of the index of the new array, PHI is the phi node of the final BB that
1012 corresponds to the value that will be loaded from the created array. TIDX
1013 is an ssa name of a temporary variable holding the index for loads from the
1017 build_one_array (gimple swtch
, int num
, tree arr_index_type
, gimple phi
,
1018 tree tidx
, struct switch_conv_info
*info
)
1022 gimple_stmt_iterator gsi
= gsi_for_stmt (swtch
);
1023 location_t loc
= gimple_location (swtch
);
1025 gcc_assert (info
->default_values
[num
]);
1027 name
= copy_ssa_name (PHI_RESULT (phi
), NULL
);
1028 info
->target_inbound_names
[num
] = name
;
1030 cst
= constructor_contains_same_values_p (info
->constructors
[num
]);
1032 load
= gimple_build_assign (name
, cst
);
1035 tree array_type
, ctor
, decl
, value_type
, fetch
, default_type
;
1037 default_type
= TREE_TYPE (info
->default_values
[num
]);
1038 value_type
= array_value_type (swtch
, default_type
, num
, info
);
1039 array_type
= build_array_type (value_type
, arr_index_type
);
1040 if (default_type
!= value_type
)
1043 constructor_elt
*elt
;
1045 FOR_EACH_VEC_ELT (constructor_elt
, info
->constructors
[num
], i
, elt
)
1046 elt
->value
= fold_convert (value_type
, elt
->value
);
1048 ctor
= build_constructor (array_type
, info
->constructors
[num
]);
1049 TREE_CONSTANT (ctor
) = true;
1050 TREE_STATIC (ctor
) = true;
1052 decl
= build_decl (loc
, VAR_DECL
, NULL_TREE
, array_type
);
1053 TREE_STATIC (decl
) = 1;
1054 DECL_INITIAL (decl
) = ctor
;
1056 DECL_NAME (decl
) = create_tmp_var_name ("CSWTCH");
1057 DECL_ARTIFICIAL (decl
) = 1;
1058 TREE_CONSTANT (decl
) = 1;
1059 TREE_READONLY (decl
) = 1;
1060 varpool_finalize_decl (decl
);
1062 fetch
= build4 (ARRAY_REF
, value_type
, decl
, tidx
, NULL_TREE
,
1064 if (default_type
!= value_type
)
1066 fetch
= fold_convert (default_type
, fetch
);
1067 fetch
= force_gimple_operand_gsi (&gsi
, fetch
, true, NULL_TREE
,
1068 true, GSI_SAME_STMT
);
1070 load
= gimple_build_assign (name
, fetch
);
1073 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
1075 info
->arr_ref_last
= load
;
1078 /* Builds and initializes static arrays initialized with values gathered from
1079 the SWTCH switch statement. Also creates statements that load values from
1083 build_arrays (gimple swtch
, struct switch_conv_info
*info
)
1085 tree arr_index_type
;
1086 tree tidx
, sub
, utype
;
1088 gimple_stmt_iterator gsi
;
1090 location_t loc
= gimple_location (swtch
);
1092 gsi
= gsi_for_stmt (swtch
);
1094 /* Make sure we do not generate arithmetics in a subrange. */
1095 utype
= TREE_TYPE (info
->index_expr
);
1096 if (TREE_TYPE (utype
))
1097 utype
= lang_hooks
.types
.type_for_mode (TYPE_MODE (TREE_TYPE (utype
)), 1);
1099 utype
= lang_hooks
.types
.type_for_mode (TYPE_MODE (utype
), 1);
1101 arr_index_type
= build_index_type (info
->range_size
);
1102 tidx
= make_ssa_name (utype
, NULL
);
1103 sub
= fold_build2_loc (loc
, MINUS_EXPR
, utype
,
1104 fold_convert_loc (loc
, utype
, info
->index_expr
),
1105 fold_convert_loc (loc
, utype
, info
->range_min
));
1106 sub
= force_gimple_operand_gsi (&gsi
, sub
,
1107 false, NULL
, true, GSI_SAME_STMT
);
1108 stmt
= gimple_build_assign (tidx
, sub
);
1110 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1112 info
->arr_ref_first
= stmt
;
1114 for (gsi
= gsi_start_phis (info
->final_bb
), i
= 0;
1115 !gsi_end_p (gsi
); gsi_next (&gsi
), i
++)
1116 build_one_array (swtch
, i
, arr_index_type
, gsi_stmt (gsi
), tidx
, info
);
1119 /* Generates and appropriately inserts loads of default values at the position
1120 given by BSI. Returns the last inserted statement. */
1123 gen_def_assigns (gimple_stmt_iterator
*gsi
, struct switch_conv_info
*info
)
1126 gimple assign
= NULL
;
1128 for (i
= 0; i
< info
->phi_count
; i
++)
1130 tree name
= copy_ssa_name (info
->target_inbound_names
[i
], NULL
);
1131 info
->target_outbound_names
[i
] = name
;
1132 assign
= gimple_build_assign (name
, info
->default_values
[i
]);
1133 gsi_insert_before (gsi
, assign
, GSI_SAME_STMT
);
1134 update_stmt (assign
);
1139 /* Deletes the unused bbs and edges that now contain the switch statement and
1140 its empty branch bbs. BBD is the now dead BB containing the original switch
1141 statement, FINAL is the last BB of the converted switch statement (in terms
1145 prune_bbs (basic_block bbd
, basic_block final
)
1150 for (ei
= ei_start (bbd
->succs
); (e
= ei_safe_edge (ei
)); )
1156 delete_basic_block (bb
);
1158 delete_basic_block (bbd
);
1161 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
1162 from the basic block loading values from an array and E2F from the basic
1163 block loading default values. BBF is the last switch basic block (see the
1164 bbf description in the comment below). */
1167 fix_phi_nodes (edge e1f
, edge e2f
, basic_block bbf
,
1168 struct switch_conv_info
*info
)
1170 gimple_stmt_iterator gsi
;
1173 for (gsi
= gsi_start_phis (bbf
), i
= 0;
1174 !gsi_end_p (gsi
); gsi_next (&gsi
), i
++)
1176 gimple phi
= gsi_stmt (gsi
);
1177 add_phi_arg (phi
, info
->target_inbound_names
[i
], e1f
, UNKNOWN_LOCATION
);
1178 add_phi_arg (phi
, info
->target_outbound_names
[i
], e2f
, UNKNOWN_LOCATION
);
1182 /* Creates a check whether the switch expression value actually falls into the
1183 range given by all the cases. If it does not, the temporaries are loaded
1184 with default values instead. SWTCH is the switch statement being converted.
1186 bb0 is the bb with the switch statement, however, we'll end it with a
1189 bb1 is the bb to be used when the range check went ok. It is derived from
1192 bb2 is the bb taken when the expression evaluated outside of the range
1193 covered by the created arrays. It is populated by loads of default
1196 bbF is a fall through for both bb1 and bb2 and contains exactly what
1197 originally followed the switch statement.
1199 bbD contains the switch statement (in the end). It is unreachable but we
1200 still need to strip off its edges.
1204 gen_inbound_check (gimple swtch
, struct switch_conv_info
*info
)
1206 tree label_decl1
= create_artificial_label (UNKNOWN_LOCATION
);
1207 tree label_decl2
= create_artificial_label (UNKNOWN_LOCATION
);
1208 tree label_decl3
= create_artificial_label (UNKNOWN_LOCATION
);
1209 gimple label1
, label2
, label3
;
1216 gimple_stmt_iterator gsi
;
1217 basic_block bb0
, bb1
, bb2
, bbf
, bbd
;
1218 edge e01
, e02
, e21
, e1d
, e1f
, e2f
;
1219 location_t loc
= gimple_location (swtch
);
1221 gcc_assert (info
->default_values
);
1223 bb0
= gimple_bb (swtch
);
1225 tidx
= gimple_assign_lhs (info
->arr_ref_first
);
1226 utype
= TREE_TYPE (tidx
);
1228 /* (end of) block 0 */
1229 gsi
= gsi_for_stmt (info
->arr_ref_first
);
1232 bound
= fold_convert_loc (loc
, utype
, info
->range_size
);
1233 cond_stmt
= gimple_build_cond (LE_EXPR
, tidx
, bound
, NULL_TREE
, NULL_TREE
);
1234 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1235 update_stmt (cond_stmt
);
1238 label2
= gimple_build_label (label_decl2
);
1239 gsi_insert_before (&gsi
, label2
, GSI_SAME_STMT
);
1240 last_assign
= gen_def_assigns (&gsi
, info
);
1243 label1
= gimple_build_label (label_decl1
);
1244 gsi_insert_before (&gsi
, label1
, GSI_SAME_STMT
);
1247 gsi
= gsi_start_bb (info
->final_bb
);
1248 label3
= gimple_build_label (label_decl3
);
1249 gsi_insert_before (&gsi
, label3
, GSI_SAME_STMT
);
1252 e02
= split_block (bb0
, cond_stmt
);
1255 e21
= split_block (bb2
, last_assign
);
1259 e1d
= split_block (bb1
, info
->arr_ref_last
);
1263 /* flags and profiles of the edge for in-range values */
1264 e01
= make_edge (bb0
, bb1
, EDGE_TRUE_VALUE
);
1265 e01
->probability
= REG_BR_PROB_BASE
- info
->default_prob
;
1266 e01
->count
= info
->other_count
;
1268 /* flags and profiles of the edge taking care of out-of-range values */
1269 e02
->flags
&= ~EDGE_FALLTHRU
;
1270 e02
->flags
|= EDGE_FALSE_VALUE
;
1271 e02
->probability
= info
->default_prob
;
1272 e02
->count
= info
->default_count
;
1274 bbf
= info
->final_bb
;
1276 e1f
= make_edge (bb1
, bbf
, EDGE_FALLTHRU
);
1277 e1f
->probability
= REG_BR_PROB_BASE
;
1278 e1f
->count
= info
->other_count
;
1280 e2f
= make_edge (bb2
, bbf
, EDGE_FALLTHRU
);
1281 e2f
->probability
= REG_BR_PROB_BASE
;
1282 e2f
->count
= info
->default_count
;
1284 /* frequencies of the new BBs */
1285 bb1
->frequency
= EDGE_FREQUENCY (e01
);
1286 bb2
->frequency
= EDGE_FREQUENCY (e02
);
1287 bbf
->frequency
= EDGE_FREQUENCY (e1f
) + EDGE_FREQUENCY (e2f
);
1289 /* Tidy blocks that have become unreachable. */
1290 prune_bbs (bbd
, info
->final_bb
);
1292 /* Fixup the PHI nodes in bbF. */
1293 fix_phi_nodes (e1f
, e2f
, bbf
, info
);
1295 /* Fix the dominator tree, if it is available. */
1296 if (dom_info_available_p (CDI_DOMINATORS
))
1298 VEC (basic_block
, heap
) *bbs_to_fix_dom
;
1300 set_immediate_dominator (CDI_DOMINATORS
, bb1
, bb0
);
1301 set_immediate_dominator (CDI_DOMINATORS
, bb2
, bb0
);
1302 if (! get_immediate_dominator (CDI_DOMINATORS
, bbf
))
1303 /* If bbD was the immediate dominator ... */
1304 set_immediate_dominator (CDI_DOMINATORS
, bbf
, bb0
);
1306 bbs_to_fix_dom
= VEC_alloc (basic_block
, heap
, 4);
1307 VEC_quick_push (basic_block
, bbs_to_fix_dom
, bb0
);
1308 VEC_quick_push (basic_block
, bbs_to_fix_dom
, bb1
);
1309 VEC_quick_push (basic_block
, bbs_to_fix_dom
, bb2
);
1310 VEC_quick_push (basic_block
, bbs_to_fix_dom
, bbf
);
1312 iterate_fix_dominators (CDI_DOMINATORS
, bbs_to_fix_dom
, true);
1313 VEC_free (basic_block
, heap
, bbs_to_fix_dom
);
1317 /* The following function is invoked on every switch statement (the current one
1318 is given in SWTCH) and runs the individual phases of switch conversion on it
1319 one after another until one fails or the conversion is completed.
1320 Returns NULL on success, or a pointer to a string with the reason why the
1321 conversion failed. */
1324 process_switch (gimple swtch
)
1326 struct switch_conv_info info
;
1328 /* Group case labels so that we get the right results from the heuristics
1329 that decide on the code generation approach for this switch. */
1330 group_case_labels_stmt (swtch
);
1332 /* If this switch is now a degenerate case with only a default label,
1333 there is nothing left for us to do. */
1334 if (gimple_switch_num_labels (swtch
) < 2)
1335 return "switch is a degenerate case";
1337 collect_switch_conv_info (swtch
, &info
);
1339 /* No error markers should reach here (they should be filtered out
1340 during gimplification). */
1341 gcc_checking_assert (TREE_TYPE (info
.index_expr
) != error_mark_node
);
1343 /* A switch on a constant should have been optimized in tree-cfg-cleanup. */
1344 gcc_checking_assert (! TREE_CONSTANT (info
.index_expr
));
1346 if (info
.uniq
<= MAX_CASE_BIT_TESTS
)
1348 if (expand_switch_using_bit_tests_p (info
.range_size
,
1349 info
.uniq
, info
.count
))
1352 fputs (" expanding as bit test is preferable\n", dump_file
);
1353 emit_case_bit_tests (swtch
, info
.index_expr
,
1354 info
.range_min
, info
.range_size
);
1359 /* This will be expanded as a decision tree in stmt.c:expand_case. */
1360 return " expanding as jumps is preferable";
1363 /* If there is no common successor, we cannot do the transformation. */
1364 if (! info
.final_bb
)
1365 return "no common successor to all case label target blocks found";
1367 /* Check the case label values are within reasonable range: */
1368 if (!check_range (&info
))
1370 gcc_assert (info
.reason
);
1374 /* For all the cases, see whether they are empty, the assignments they
1375 represent constant and so on... */
1376 if (! check_all_empty_except_final (&info
))
1378 gcc_assert (info
.reason
);
1381 if (!check_final_bb (&info
))
1383 gcc_assert (info
.reason
);
1387 /* At this point all checks have passed and we can proceed with the
1390 create_temp_arrays (&info
);
1391 gather_default_values (gimple_switch_default_label (swtch
), &info
);
1392 build_constructors (swtch
, &info
);
1394 build_arrays (swtch
, &info
); /* Build the static arrays and assignments. */
1395 gen_inbound_check (swtch
, &info
); /* Build the bounds check. */
1398 free_temp_arrays (&info
);
1402 /* The main function of the pass scans statements for switches and invokes
1403 process_switch on them. */
1406 do_switchconv (void)
1412 const char *failure_reason
;
1413 gimple stmt
= last_stmt (bb
);
1414 if (stmt
&& gimple_code (stmt
) == GIMPLE_SWITCH
)
1418 expanded_location loc
= expand_location (gimple_location (stmt
));
1420 fprintf (dump_file
, "beginning to process the following "
1421 "SWITCH statement (%s:%d) : ------- \n",
1422 loc
.file
, loc
.line
);
1423 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1424 putc ('\n', dump_file
);
1427 failure_reason
= process_switch (stmt
);
1428 if (! failure_reason
)
1432 fputs ("Switch converted\n", dump_file
);
1433 fputs ("--------------------------------\n", dump_file
);
1436 /* Make no effort to update the post-dominator tree. It is actually not
1437 that hard for the transformations we have performed, but it is not
1438 supported by iterate_fix_dominators. */
1439 free_dominance_info (CDI_POST_DOMINATORS
);
1445 fputs ("Bailing out - ", dump_file
);
1446 fputs (failure_reason
, dump_file
);
1447 fputs ("\n--------------------------------\n", dump_file
);
1456 /* The pass gate. */
1459 switchconv_gate (void)
1461 return flag_tree_switch_conversion
!= 0;
1464 struct gimple_opt_pass pass_convert_switch
=
1468 "switchconv", /* name */
1469 switchconv_gate
, /* gate */
1470 do_switchconv
, /* execute */
1473 0, /* static_pass_number */
1474 TV_TREE_SWITCH_CONVERSION
, /* tv_id */
1475 PROP_cfg
| PROP_ssa
, /* properties_required */
1476 0, /* properties_provided */
1477 0, /* properties_destroyed */
1478 0, /* todo_flags_start */
1480 | TODO_ggc_collect
| TODO_verify_ssa
1482 | TODO_verify_flow
/* todo_flags_finish */