1 /* Lower GIMPLE_SWITCH expressions to something more efficient than
3 Copyright (C) 2006-2013 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"
33 #include "basic-block.h"
35 #include "tree-pass.h"
36 #include "gimple-pretty-print.h"
39 /* ??? For lang_hooks.types.type_for_mode, but is there a word_mode
40 type in the GIMPLE type system that is language-independent? */
41 #include "langhooks.h"
43 /* Need to include expr.h and optabs.h for lshift_cheap_p. */
47 /* Maximum number of case bit tests.
48 FIXME: This should be derived from PARAM_CASE_VALUES_THRESHOLD and
49 targetm.case_values_threshold(), or be its own param. */
50 #define MAX_CASE_BIT_TESTS 3
52 /* Split the basic block at the statement pointed to by GSIP, and insert
53 a branch to the target basic block of E_TRUE conditional on tree
56 It is assumed that there is already an edge from the to-be-split
57 basic block to E_TRUE->dest block. This edge is removed, and the
58 profile information on the edge is re-used for the new conditional
61 The CFG is updated. The dominator tree will not be valid after
62 this transformation, but the immediate dominators are updated if
63 UPDATE_DOMINATORS is true.
65 Returns the newly created basic block. */
68 hoist_edge_and_branch_if_true (gimple_stmt_iterator
*gsip
,
69 tree cond
, edge e_true
,
70 bool update_dominators
)
75 basic_block new_bb
, split_bb
= gsi_bb (*gsip
);
76 bool dominated_e_true
= false;
78 gcc_assert (e_true
->src
== split_bb
);
81 && get_immediate_dominator (CDI_DOMINATORS
, e_true
->dest
) == split_bb
)
82 dominated_e_true
= true;
84 tmp
= force_gimple_operand_gsi (gsip
, cond
, /*simple=*/true, NULL
,
85 /*before=*/true, GSI_SAME_STMT
);
86 cond_stmt
= gimple_build_cond_from_tree (tmp
, NULL_TREE
, NULL_TREE
);
87 gsi_insert_before (gsip
, cond_stmt
, GSI_SAME_STMT
);
89 e_false
= split_block (split_bb
, cond_stmt
);
90 new_bb
= e_false
->dest
;
91 redirect_edge_pred (e_true
, split_bb
);
93 e_true
->flags
&= ~EDGE_FALLTHRU
;
94 e_true
->flags
|= EDGE_TRUE_VALUE
;
96 e_false
->flags
&= ~EDGE_FALLTHRU
;
97 e_false
->flags
|= EDGE_FALSE_VALUE
;
98 e_false
->probability
= REG_BR_PROB_BASE
- e_true
->probability
;
99 e_false
->count
= split_bb
->count
- e_true
->count
;
100 new_bb
->count
= e_false
->count
;
102 if (update_dominators
)
104 if (dominated_e_true
)
105 set_immediate_dominator (CDI_DOMINATORS
, e_true
->dest
, split_bb
);
106 set_immediate_dominator (CDI_DOMINATORS
, e_false
->dest
, split_bb
);
113 /* Determine whether "1 << x" is relatively cheap in word_mode. */
114 /* FIXME: This is the function that we need rtl.h and optabs.h for.
115 This function (and similar RTL-related cost code in e.g. IVOPTS) should
116 be moved to some kind of interface file for GIMPLE/RTL interactions. */
118 lshift_cheap_p (void)
120 /* FIXME: This should be made target dependent via this "this_target"
121 mechanism, similar to e.g. can_copy_init_p in gcse.c. */
122 static bool init
[2] = {false, false};
123 static bool cheap
[2] = {true, true};
126 /* If the targer has no lshift in word_mode, the operation will most
127 probably not be cheap. ??? Does GCC even work for such targets? */
128 if (optab_handler (ashl_optab
, word_mode
) == CODE_FOR_nothing
)
131 speed_p
= optimize_insn_for_speed_p ();
135 rtx reg
= gen_raw_REG (word_mode
, 10000);
136 int cost
= set_src_cost (gen_rtx_ASHIFT (word_mode
, const1_rtx
, reg
),
138 cheap
[speed_p
] = cost
< COSTS_N_INSNS (MAX_CASE_BIT_TESTS
);
139 init
[speed_p
] = true;
142 return cheap
[speed_p
];
145 /* Return true if a switch should be expanded as a bit test.
146 RANGE is the difference between highest and lowest case.
147 UNIQ is number of unique case node targets, not counting the default case.
148 COUNT is the number of comparisons needed, not counting the default case. */
151 expand_switch_using_bit_tests_p (tree range
,
155 return (((uniq
== 1 && count
>= 3)
156 || (uniq
== 2 && count
>= 5)
157 || (uniq
== 3 && count
>= 6))
159 && compare_tree_int (range
, GET_MODE_BITSIZE (word_mode
)) < 0
160 && compare_tree_int (range
, 0) > 0);
163 /* Implement switch statements with bit tests
165 A GIMPLE switch statement can be expanded to a short sequence of bit-wise
166 comparisons. "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)"
167 where CST and MINVAL are integer constants. This is better than a series
168 of compare-and-banch insns in some cases, e.g. we can implement:
170 if ((x==4) || (x==6) || (x==9) || (x==11))
172 as a single bit test:
174 if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11)))
176 This transformation is only applied if the number of case targets is small,
177 if CST constains at least 3 bits, and "1 << x" is cheap. The bit tests are
178 performed in "word_mode".
180 The following example shows the code the transformation generates:
186 case '0': case '1': case '2': case '3': case '4':
187 case '5': case '6': case '7': case '8': case '9':
188 case 'A': case 'B': case 'C': case 'D': case 'E':
200 if (tmp1 > (70 - 48)) goto L2;
202 tmp3 = 0b11111100000001111111111;
203 if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2;
210 TODO: There are still some improvements to this transformation that could
213 * A narrower mode than word_mode could be used if that is cheaper, e.g.
214 for x86_64 where a narrower-mode shift may result in smaller code.
216 * The compounded constant could be shifted rather than the one. The
217 test would be either on the sign bit or on the least significant bit,
218 depending on the direction of the shift. On some machines, the test
219 for the branch would be free if the bit to test is already set by the
222 This transformation was contributed by Roger Sayle, see this e-mail:
223 http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html
226 /* A case_bit_test represents a set of case nodes that may be
227 selected from using a bit-wise comparison. HI and LO hold
228 the integer to be tested against, TARGET_EDGE contains the
229 edge to the basic block to jump to upon success and BITS
230 counts the number of case nodes handled by this test,
231 typically the number of bits set in HI:LO. The LABEL field
232 is used to quickly identify all cases in this set without
233 looking at label_to_block for every case label. */
244 /* Comparison function for qsort to order bit tests by decreasing
245 probability of execution. Our best guess comes from a measured
246 profile. If the profile counts are equal, break even on the
247 number of case nodes, i.e. the node with the most cases gets
250 TODO: Actually this currently runs before a profile is available.
251 Therefore the case-as-bit-tests transformation should be done
252 later in the pass pipeline, or something along the lines of
253 "Efficient and effective branch reordering using profile data"
254 (Yang et. al., 2002) should be implemented (although, how good
255 is a paper is called "Efficient and effective ..." when the
256 latter is implied by the former, but oh well...). */
259 case_bit_test_cmp (const void *p1
, const void *p2
)
261 const struct case_bit_test
*const d1
= (const struct case_bit_test
*) p1
;
262 const struct case_bit_test
*const d2
= (const struct case_bit_test
*) p2
;
264 if (d2
->target_edge
->count
!= d1
->target_edge
->count
)
265 return d2
->target_edge
->count
- d1
->target_edge
->count
;
266 if (d2
->bits
!= d1
->bits
)
267 return d2
->bits
- d1
->bits
;
269 /* Stabilize the sort. */
270 return LABEL_DECL_UID (d2
->label
) - LABEL_DECL_UID (d1
->label
);
273 /* Expand a switch statement by a short sequence of bit-wise
274 comparisons. "switch(x)" is effectively converted into
275 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
278 INDEX_EXPR is the value being switched on.
280 MINVAL is the lowest case value of in the case nodes,
281 and RANGE is highest value minus MINVAL. MINVAL and RANGE
282 are not guaranteed to be of the same type as INDEX_EXPR
283 (the gimplifier doesn't change the type of case label values,
284 and MINVAL and RANGE are derived from those values).
286 There *MUST* be MAX_CASE_BIT_TESTS or less unique case
290 emit_case_bit_tests (gimple swtch
, tree index_expr
,
291 tree minval
, tree range
)
293 struct case_bit_test test
[MAX_CASE_BIT_TESTS
];
294 unsigned int i
, j
, k
;
297 basic_block switch_bb
= gimple_bb (swtch
);
298 basic_block default_bb
, new_default_bb
, new_bb
;
300 bool update_dom
= dom_info_available_p (CDI_DOMINATORS
);
302 vec
<basic_block
> bbs_to_fix_dom
= vNULL
;
304 tree index_type
= TREE_TYPE (index_expr
);
305 tree unsigned_index_type
= unsigned_type_for (index_type
);
306 unsigned int branch_num
= gimple_switch_num_labels (swtch
);
308 gimple_stmt_iterator gsi
;
312 tree word_type_node
= lang_hooks
.types
.type_for_mode (word_mode
, 1);
313 tree word_mode_zero
= fold_convert (word_type_node
, integer_zero_node
);
314 tree word_mode_one
= fold_convert (word_type_node
, integer_one_node
);
316 memset (&test
, 0, sizeof (test
));
318 /* Get the edge for the default case. */
319 tmp
= gimple_switch_default_label (swtch
);
320 default_bb
= label_to_block (CASE_LABEL (tmp
));
321 default_edge
= find_edge (switch_bb
, default_bb
);
323 /* Go through all case labels, and collect the case labels, profile
324 counts, and other information we need to build the branch tests. */
326 for (i
= 1; i
< branch_num
; i
++)
329 tree cs
= gimple_switch_label (swtch
, i
);
330 tree label
= CASE_LABEL (cs
);
331 edge e
= find_edge (switch_bb
, label_to_block (label
));
332 for (k
= 0; k
< count
; k
++)
333 if (e
== test
[k
].target_edge
)
338 gcc_checking_assert (count
< MAX_CASE_BIT_TESTS
);
341 test
[k
].target_edge
= e
;
342 test
[k
].label
= label
;
349 lo
= tree_low_cst (int_const_binop (MINUS_EXPR
,
350 CASE_LOW (cs
), minval
),
352 if (CASE_HIGH (cs
) == NULL_TREE
)
355 hi
= tree_low_cst (int_const_binop (MINUS_EXPR
,
356 CASE_HIGH (cs
), minval
),
359 for (j
= lo
; j
<= hi
; j
++)
360 if (j
>= HOST_BITS_PER_WIDE_INT
)
361 test
[k
].hi
|= (HOST_WIDE_INT
) 1 << (j
- HOST_BITS_PER_INT
);
363 test
[k
].lo
|= (HOST_WIDE_INT
) 1 << j
;
366 qsort (test
, count
, sizeof (*test
), case_bit_test_cmp
);
368 /* We generate two jumps to the default case label.
369 Split the default edge, so that we don't have to do any PHI node
371 new_default_bb
= split_edge (default_edge
);
375 bbs_to_fix_dom
.create (10);
376 bbs_to_fix_dom
.quick_push (switch_bb
);
377 bbs_to_fix_dom
.quick_push (default_bb
);
378 bbs_to_fix_dom
.quick_push (new_default_bb
);
381 /* Now build the test-and-branch code. */
383 gsi
= gsi_last_bb (switch_bb
);
385 /* idx = (unsigned)x - minval. */
386 idx
= fold_convert (unsigned_index_type
, index_expr
);
387 idx
= fold_build2 (MINUS_EXPR
, unsigned_index_type
, idx
,
388 fold_convert (unsigned_index_type
, minval
));
389 idx
= force_gimple_operand_gsi (&gsi
, idx
,
390 /*simple=*/true, NULL_TREE
,
391 /*before=*/true, GSI_SAME_STMT
);
393 /* if (idx > range) goto default */
394 range
= force_gimple_operand_gsi (&gsi
,
395 fold_convert (unsigned_index_type
, range
),
396 /*simple=*/true, NULL_TREE
,
397 /*before=*/true, GSI_SAME_STMT
);
398 tmp
= fold_build2 (GT_EXPR
, boolean_type_node
, idx
, range
);
399 new_bb
= hoist_edge_and_branch_if_true (&gsi
, tmp
, default_edge
, update_dom
);
401 bbs_to_fix_dom
.quick_push (new_bb
);
402 gcc_assert (gimple_bb (swtch
) == new_bb
);
403 gsi
= gsi_last_bb (new_bb
);
405 /* Any blocks dominated by the GIMPLE_SWITCH, but that are not successors
406 of NEW_BB, are still immediately dominated by SWITCH_BB. Make it so. */
409 vec
<basic_block
> dom_bbs
;
412 dom_bbs
= get_dominated_by (CDI_DOMINATORS
, new_bb
);
413 FOR_EACH_VEC_ELT (dom_bbs
, i
, dom_son
)
415 edge e
= find_edge (new_bb
, dom_son
);
416 if (e
&& single_pred_p (e
->dest
))
418 set_immediate_dominator (CDI_DOMINATORS
, dom_son
, switch_bb
);
419 bbs_to_fix_dom
.safe_push (dom_son
);
424 /* csui = (1 << (word_mode) idx) */
425 csui
= make_ssa_name (word_type_node
, NULL
);
426 tmp
= fold_build2 (LSHIFT_EXPR
, word_type_node
, word_mode_one
,
427 fold_convert (word_type_node
, idx
));
428 tmp
= force_gimple_operand_gsi (&gsi
, tmp
,
429 /*simple=*/false, NULL_TREE
,
430 /*before=*/true, GSI_SAME_STMT
);
431 shift_stmt
= gimple_build_assign (csui
, tmp
);
432 gsi_insert_before (&gsi
, shift_stmt
, GSI_SAME_STMT
);
433 update_stmt (shift_stmt
);
435 /* for each unique set of cases:
436 if (const & csui) goto target */
437 for (k
= 0; k
< count
; k
++)
439 tmp
= build_int_cst_wide (word_type_node
, test
[k
].lo
, test
[k
].hi
);
440 tmp
= fold_build2 (BIT_AND_EXPR
, word_type_node
, csui
, tmp
);
441 tmp
= force_gimple_operand_gsi (&gsi
, tmp
,
442 /*simple=*/true, NULL_TREE
,
443 /*before=*/true, GSI_SAME_STMT
);
444 tmp
= fold_build2 (NE_EXPR
, boolean_type_node
, tmp
, word_mode_zero
);
445 new_bb
= hoist_edge_and_branch_if_true (&gsi
, tmp
, test
[k
].target_edge
,
448 bbs_to_fix_dom
.safe_push (new_bb
);
449 gcc_assert (gimple_bb (swtch
) == new_bb
);
450 gsi
= gsi_last_bb (new_bb
);
453 /* We should have removed all edges now. */
454 gcc_assert (EDGE_COUNT (gsi_bb (gsi
)->succs
) == 0);
456 /* If nothing matched, go to the default label. */
457 make_edge (gsi_bb (gsi
), new_default_bb
, EDGE_FALLTHRU
);
459 /* The GIMPLE_SWITCH is now redundant. */
460 gsi_remove (&gsi
, true);
464 /* Fix up the dominator tree. */
465 iterate_fix_dominators (CDI_DOMINATORS
, bbs_to_fix_dom
, true);
466 bbs_to_fix_dom
.release ();
471 Switch initialization conversion
473 The following pass changes simple initializations of scalars in a switch
474 statement into initializations from a static array. Obviously, the values
475 must be constant and known at compile time and a default branch must be
476 provided. For example, the following code:
500 a_5 = PHI <a_1, a_2, a_3, a_4>
501 b_5 = PHI <b_1, b_2, b_3, b_4>
506 static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
507 static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
510 if (((unsigned) argc) - 1 < 11)
512 a_6 = CSWTCH02[argc - 1];
513 b_6 = CSWTCH01[argc - 1];
523 There are further constraints. Specifically, the range of values across all
524 case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
525 eight) times the number of the actual switch branches.
527 This transformation was contributed by Martin Jambor, see this e-mail:
528 http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */
530 /* The main structure of the pass. */
531 struct switch_conv_info
533 /* The expression used to decide the switch branch. */
536 /* The following integer constants store the minimum and maximum value
537 covered by the case labels. */
541 /* The difference between the above two numbers. Stored here because it
542 is used in all the conversion heuristics, as well as for some of the
543 transformation, and it is expensive to re-compute it all the time. */
546 /* Basic block that contains the actual GIMPLE_SWITCH. */
547 basic_block switch_bb
;
549 /* Basic block that is the target of the default case. */
550 basic_block default_bb
;
552 /* The single successor block of all branches out of the GIMPLE_SWITCH,
553 if such a block exists. Otherwise NULL. */
554 basic_block final_bb
;
556 /* The probability of the default edge in the replaced switch. */
559 /* The count of the default edge in the replaced switch. */
560 gcov_type default_count
;
562 /* Combined count of all other (non-default) edges in the replaced switch. */
563 gcov_type other_count
;
565 /* Number of phi nodes in the final bb (that we'll be replacing). */
568 /* Array of default values, in the same order as phi nodes. */
569 tree
*default_values
;
571 /* Constructors of new static arrays. */
572 vec
<constructor_elt
, va_gc
> **constructors
;
574 /* Array of ssa names that are initialized with a value from a new static
576 tree
*target_inbound_names
;
578 /* Array of ssa names that are initialized with the default value if the
579 switch expression is out of range. */
580 tree
*target_outbound_names
;
582 /* The first load statement that loads a temporary from a new static array.
584 gimple arr_ref_first
;
586 /* The last load statement that loads a temporary from a new static array. */
589 /* String reason why the case wasn't a good candidate that is written to the
590 dump file, if there is one. */
593 /* Parameters for expand_switch_using_bit_tests. Should be computed
594 the same way as in expand_case. */
599 /* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */
602 collect_switch_conv_info (gimple swtch
, struct switch_conv_info
*info
)
604 unsigned int branch_num
= gimple_switch_num_labels (swtch
);
605 tree min_case
, max_case
;
606 unsigned int count
, i
;
610 memset (info
, 0, sizeof (*info
));
612 /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
613 is a default label which is the first in the vector.
614 Collect the bits we can deduce from the CFG. */
615 info
->index_expr
= gimple_switch_index (swtch
);
616 info
->switch_bb
= gimple_bb (swtch
);
618 label_to_block (CASE_LABEL (gimple_switch_default_label (swtch
)));
619 e_default
= find_edge (info
->switch_bb
, info
->default_bb
);
620 info
->default_prob
= e_default
->probability
;
621 info
->default_count
= e_default
->count
;
622 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
624 info
->other_count
+= e
->count
;
626 /* See if there is one common successor block for all branch
627 targets. If it exists, record it in FINAL_BB. */
628 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
630 if (! single_pred_p (e
->dest
))
632 info
->final_bb
= e
->dest
;
637 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
639 if (e
->dest
== info
->final_bb
)
642 if (single_pred_p (e
->dest
)
643 && single_succ_p (e
->dest
)
644 && single_succ (e
->dest
) == info
->final_bb
)
647 info
->final_bb
= NULL
;
651 /* Get upper and lower bounds of case values, and the covered range. */
652 min_case
= gimple_switch_label (swtch
, 1);
653 max_case
= gimple_switch_label (swtch
, branch_num
- 1);
655 info
->range_min
= CASE_LOW (min_case
);
656 if (CASE_HIGH (max_case
) != NULL_TREE
)
657 info
->range_max
= CASE_HIGH (max_case
);
659 info
->range_max
= CASE_LOW (max_case
);
662 int_const_binop (MINUS_EXPR
, info
->range_max
, info
->range_min
);
664 /* Get a count of the number of case labels. Single-valued case labels
665 simply count as one, but a case range counts double, since it may
666 require two compares if it gets lowered as a branching tree. */
668 for (i
= 1; i
< branch_num
; i
++)
670 tree elt
= gimple_switch_label (swtch
, i
);
673 && ! tree_int_cst_equal (CASE_LOW (elt
), CASE_HIGH (elt
)))
678 /* Get the number of unique non-default targets out of the GIMPLE_SWITCH
679 block. Assume a CFG cleanup would have already removed degenerate
680 switch statements, this allows us to just use EDGE_COUNT. */
681 info
->uniq
= EDGE_COUNT (gimple_bb (swtch
)->succs
) - 1;
684 /* Checks whether the range given by individual case statements of the SWTCH
685 switch statement isn't too big and whether the number of branches actually
686 satisfies the size of the new array. */
689 check_range (struct switch_conv_info
*info
)
691 gcc_assert (info
->range_size
);
692 if (!host_integerp (info
->range_size
, 1))
694 info
->reason
= "index range way too large or otherwise unusable";
698 if ((unsigned HOST_WIDE_INT
) tree_low_cst (info
->range_size
, 1)
699 > ((unsigned) info
->count
* SWITCH_CONVERSION_BRANCH_RATIO
))
701 info
->reason
= "the maximum range-branch ratio exceeded";
708 /* Checks whether all but the FINAL_BB basic blocks are empty. */
711 check_all_empty_except_final (struct switch_conv_info
*info
)
716 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
718 if (e
->dest
== info
->final_bb
)
721 if (!empty_block_p (e
->dest
))
723 info
->reason
= "bad case - a non-final BB not empty";
731 /* This function checks whether all required values in phi nodes in final_bb
732 are constants. Required values are those that correspond to a basic block
733 which is a part of the examined switch statement. It returns true if the
734 phi nodes are OK, otherwise false. */
737 check_final_bb (struct switch_conv_info
*info
)
739 gimple_stmt_iterator gsi
;
742 for (gsi
= gsi_start_phis (info
->final_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
744 gimple phi
= gsi_stmt (gsi
);
749 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
751 basic_block bb
= gimple_phi_arg_edge (phi
, i
)->src
;
753 if (bb
== info
->switch_bb
754 || (single_pred_p (bb
) && single_pred (bb
) == info
->switch_bb
))
758 val
= gimple_phi_arg_def (phi
, i
);
759 if (!is_gimple_ip_invariant (val
))
761 info
->reason
= "non-invariant value from a case";
762 return false; /* Non-invariant argument. */
764 reloc
= initializer_constant_valid_p (val
, TREE_TYPE (val
));
765 if ((flag_pic
&& reloc
!= null_pointer_node
)
766 || (!flag_pic
&& reloc
== NULL_TREE
))
770 = "value from a case would need runtime relocations";
773 = "value from a case is not a valid initializer";
783 /* The following function allocates default_values, target_{in,out}_names and
784 constructors arrays. The last one is also populated with pointers to
785 vectors that will become constructors of new arrays. */
788 create_temp_arrays (struct switch_conv_info
*info
)
792 info
->default_values
= XCNEWVEC (tree
, info
->phi_count
* 3);
793 /* ??? Macros do not support multi argument templates in their
794 argument list. We create a typedef to work around that problem. */
795 typedef vec
<constructor_elt
, va_gc
> *vec_constructor_elt_gc
;
796 info
->constructors
= XCNEWVEC (vec_constructor_elt_gc
, info
->phi_count
);
797 info
->target_inbound_names
= info
->default_values
+ info
->phi_count
;
798 info
->target_outbound_names
= info
->target_inbound_names
+ info
->phi_count
;
799 for (i
= 0; i
< info
->phi_count
; i
++)
800 vec_alloc (info
->constructors
[i
], 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
++)
873 elt
.index
= int_const_binop (MINUS_EXPR
, pos
, info
->range_min
);
875 = unshare_expr_without_location (info
->default_values
[k
]);
876 info
->constructors
[k
]->quick_push (elt
);
879 pos
= int_const_binop (PLUS_EXPR
, pos
, integer_one_node
);
881 gcc_assert (tree_int_cst_equal (pos
, CASE_LOW (cs
)));
885 high
= CASE_HIGH (cs
);
887 high
= CASE_LOW (cs
);
888 for (gsi
= gsi_start_phis (info
->final_bb
);
889 !gsi_end_p (gsi
); gsi_next (&gsi
))
891 gimple phi
= gsi_stmt (gsi
);
892 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
893 tree low
= CASE_LOW (cs
);
900 elt
.index
= int_const_binop (MINUS_EXPR
, pos
, info
->range_min
);
901 elt
.value
= unshare_expr_without_location (val
);
902 info
->constructors
[j
]->quick_push (elt
);
904 pos
= int_const_binop (PLUS_EXPR
, pos
, integer_one_node
);
905 } while (!tree_int_cst_lt (high
, pos
)
906 && tree_int_cst_lt (low
, pos
));
912 /* If all values in the constructor vector are the same, return the value.
913 Otherwise return NULL_TREE. Not supposed to be called for empty
917 constructor_contains_same_values_p (vec
<constructor_elt
, va_gc
> *vec
)
920 tree prev
= NULL_TREE
;
921 constructor_elt
*elt
;
923 FOR_EACH_VEC_SAFE_ELT (vec
, i
, elt
)
927 else if (!operand_equal_p (elt
->value
, prev
, OEP_ONLY_CONST
))
933 /* Return type which should be used for array elements, either TYPE,
934 or for integral type some smaller integral type that can still hold
935 all the constants. */
938 array_value_type (gimple swtch
, tree type
, int num
,
939 struct switch_conv_info
*info
)
941 unsigned int i
, len
= vec_safe_length (info
->constructors
[num
]);
942 constructor_elt
*elt
;
943 enum machine_mode mode
;
947 if (!INTEGRAL_TYPE_P (type
))
950 mode
= GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type
)));
951 if (GET_MODE_SIZE (TYPE_MODE (type
)) <= GET_MODE_SIZE (mode
))
954 if (len
< (optimize_bb_for_size_p (gimple_bb (swtch
)) ? 2 : 32))
957 FOR_EACH_VEC_SAFE_ELT (info
->constructors
[num
], i
, elt
)
961 if (TREE_CODE (elt
->value
) != INTEGER_CST
)
964 cst
= TREE_INT_CST (elt
->value
);
967 unsigned int prec
= GET_MODE_BITSIZE (mode
);
968 if (prec
> HOST_BITS_PER_WIDE_INT
)
971 if (sign
>= 0 && cst
== cst
.zext (prec
))
973 if (sign
== 0 && cst
== cst
.sext (prec
))
978 if (sign
<= 0 && cst
== cst
.sext (prec
))
987 mode
= GET_MODE_WIDER_MODE (mode
);
989 || GET_MODE_SIZE (mode
) >= GET_MODE_SIZE (TYPE_MODE (type
)))
995 sign
= TYPE_UNSIGNED (type
) ? 1 : -1;
996 smaller_type
= lang_hooks
.types
.type_for_mode (mode
, sign
>= 0);
997 if (GET_MODE_SIZE (TYPE_MODE (type
))
998 <= GET_MODE_SIZE (TYPE_MODE (smaller_type
)))
1001 return smaller_type
;
1004 /* Create an appropriate array type and declaration and assemble a static array
1005 variable. Also create a load statement that initializes the variable in
1006 question with a value from the static array. SWTCH is the switch statement
1007 being converted, NUM is the index to arrays of constructors, default values
1008 and target SSA names for this particular array. ARR_INDEX_TYPE is the type
1009 of the index of the new array, PHI is the phi node of the final BB that
1010 corresponds to the value that will be loaded from the created array. TIDX
1011 is an ssa name of a temporary variable holding the index for loads from the
1015 build_one_array (gimple swtch
, int num
, tree arr_index_type
, gimple phi
,
1016 tree tidx
, struct switch_conv_info
*info
)
1020 gimple_stmt_iterator gsi
= gsi_for_stmt (swtch
);
1021 location_t loc
= gimple_location (swtch
);
1023 gcc_assert (info
->default_values
[num
]);
1025 name
= copy_ssa_name (PHI_RESULT (phi
), NULL
);
1026 info
->target_inbound_names
[num
] = name
;
1028 cst
= constructor_contains_same_values_p (info
->constructors
[num
]);
1030 load
= gimple_build_assign (name
, cst
);
1033 tree array_type
, ctor
, decl
, value_type
, fetch
, default_type
;
1035 default_type
= TREE_TYPE (info
->default_values
[num
]);
1036 value_type
= array_value_type (swtch
, default_type
, num
, info
);
1037 array_type
= build_array_type (value_type
, arr_index_type
);
1038 if (default_type
!= value_type
)
1041 constructor_elt
*elt
;
1043 FOR_EACH_VEC_SAFE_ELT (info
->constructors
[num
], i
, elt
)
1044 elt
->value
= fold_convert (value_type
, elt
->value
);
1046 ctor
= build_constructor (array_type
, info
->constructors
[num
]);
1047 TREE_CONSTANT (ctor
) = true;
1048 TREE_STATIC (ctor
) = true;
1050 decl
= build_decl (loc
, VAR_DECL
, NULL_TREE
, array_type
);
1051 TREE_STATIC (decl
) = 1;
1052 DECL_INITIAL (decl
) = ctor
;
1054 DECL_NAME (decl
) = create_tmp_var_name ("CSWTCH");
1055 DECL_ARTIFICIAL (decl
) = 1;
1056 TREE_CONSTANT (decl
) = 1;
1057 TREE_READONLY (decl
) = 1;
1058 varpool_finalize_decl (decl
);
1060 fetch
= build4 (ARRAY_REF
, value_type
, decl
, tidx
, NULL_TREE
,
1062 if (default_type
!= value_type
)
1064 fetch
= fold_convert (default_type
, fetch
);
1065 fetch
= force_gimple_operand_gsi (&gsi
, fetch
, true, NULL_TREE
,
1066 true, GSI_SAME_STMT
);
1068 load
= gimple_build_assign (name
, fetch
);
1071 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
1073 info
->arr_ref_last
= load
;
1076 /* Builds and initializes static arrays initialized with values gathered from
1077 the SWTCH switch statement. Also creates statements that load values from
1081 build_arrays (gimple swtch
, struct switch_conv_info
*info
)
1083 tree arr_index_type
;
1084 tree tidx
, sub
, utype
;
1086 gimple_stmt_iterator gsi
;
1088 location_t loc
= gimple_location (swtch
);
1090 gsi
= gsi_for_stmt (swtch
);
1092 /* Make sure we do not generate arithmetics in a subrange. */
1093 utype
= TREE_TYPE (info
->index_expr
);
1094 if (TREE_TYPE (utype
))
1095 utype
= lang_hooks
.types
.type_for_mode (TYPE_MODE (TREE_TYPE (utype
)), 1);
1097 utype
= lang_hooks
.types
.type_for_mode (TYPE_MODE (utype
), 1);
1099 arr_index_type
= build_index_type (info
->range_size
);
1100 tidx
= make_ssa_name (utype
, NULL
);
1101 sub
= fold_build2_loc (loc
, MINUS_EXPR
, utype
,
1102 fold_convert_loc (loc
, utype
, info
->index_expr
),
1103 fold_convert_loc (loc
, utype
, info
->range_min
));
1104 sub
= force_gimple_operand_gsi (&gsi
, sub
,
1105 false, NULL
, true, GSI_SAME_STMT
);
1106 stmt
= gimple_build_assign (tidx
, sub
);
1108 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1110 info
->arr_ref_first
= stmt
;
1112 for (gsi
= gsi_start_phis (info
->final_bb
), i
= 0;
1113 !gsi_end_p (gsi
); gsi_next (&gsi
), i
++)
1114 build_one_array (swtch
, i
, arr_index_type
, gsi_stmt (gsi
), tidx
, info
);
1117 /* Generates and appropriately inserts loads of default values at the position
1118 given by BSI. Returns the last inserted statement. */
1121 gen_def_assigns (gimple_stmt_iterator
*gsi
, struct switch_conv_info
*info
)
1124 gimple assign
= NULL
;
1126 for (i
= 0; i
< info
->phi_count
; i
++)
1128 tree name
= copy_ssa_name (info
->target_inbound_names
[i
], NULL
);
1129 info
->target_outbound_names
[i
] = name
;
1130 assign
= gimple_build_assign (name
, info
->default_values
[i
]);
1131 gsi_insert_before (gsi
, assign
, GSI_SAME_STMT
);
1132 update_stmt (assign
);
1137 /* Deletes the unused bbs and edges that now contain the switch statement and
1138 its empty branch bbs. BBD is the now dead BB containing the original switch
1139 statement, FINAL is the last BB of the converted switch statement (in terms
1143 prune_bbs (basic_block bbd
, basic_block final
)
1148 for (ei
= ei_start (bbd
->succs
); (e
= ei_safe_edge (ei
)); )
1154 delete_basic_block (bb
);
1156 delete_basic_block (bbd
);
1159 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
1160 from the basic block loading values from an array and E2F from the basic
1161 block loading default values. BBF is the last switch basic block (see the
1162 bbf description in the comment below). */
1165 fix_phi_nodes (edge e1f
, edge e2f
, basic_block bbf
,
1166 struct switch_conv_info
*info
)
1168 gimple_stmt_iterator gsi
;
1171 for (gsi
= gsi_start_phis (bbf
), i
= 0;
1172 !gsi_end_p (gsi
); gsi_next (&gsi
), i
++)
1174 gimple phi
= gsi_stmt (gsi
);
1175 add_phi_arg (phi
, info
->target_inbound_names
[i
], e1f
, UNKNOWN_LOCATION
);
1176 add_phi_arg (phi
, info
->target_outbound_names
[i
], e2f
, UNKNOWN_LOCATION
);
1180 /* Creates a check whether the switch expression value actually falls into the
1181 range given by all the cases. If it does not, the temporaries are loaded
1182 with default values instead. SWTCH is the switch statement being converted.
1184 bb0 is the bb with the switch statement, however, we'll end it with a
1187 bb1 is the bb to be used when the range check went ok. It is derived from
1190 bb2 is the bb taken when the expression evaluated outside of the range
1191 covered by the created arrays. It is populated by loads of default
1194 bbF is a fall through for both bb1 and bb2 and contains exactly what
1195 originally followed the switch statement.
1197 bbD contains the switch statement (in the end). It is unreachable but we
1198 still need to strip off its edges.
1202 gen_inbound_check (gimple swtch
, struct switch_conv_info
*info
)
1204 tree label_decl1
= create_artificial_label (UNKNOWN_LOCATION
);
1205 tree label_decl2
= create_artificial_label (UNKNOWN_LOCATION
);
1206 tree label_decl3
= create_artificial_label (UNKNOWN_LOCATION
);
1207 gimple label1
, label2
, label3
;
1214 gimple_stmt_iterator gsi
;
1215 basic_block bb0
, bb1
, bb2
, bbf
, bbd
;
1216 edge e01
, e02
, e21
, e1d
, e1f
, e2f
;
1217 location_t loc
= gimple_location (swtch
);
1219 gcc_assert (info
->default_values
);
1221 bb0
= gimple_bb (swtch
);
1223 tidx
= gimple_assign_lhs (info
->arr_ref_first
);
1224 utype
= TREE_TYPE (tidx
);
1226 /* (end of) block 0 */
1227 gsi
= gsi_for_stmt (info
->arr_ref_first
);
1230 bound
= fold_convert_loc (loc
, utype
, info
->range_size
);
1231 cond_stmt
= gimple_build_cond (LE_EXPR
, tidx
, bound
, NULL_TREE
, NULL_TREE
);
1232 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1233 update_stmt (cond_stmt
);
1236 label2
= gimple_build_label (label_decl2
);
1237 gsi_insert_before (&gsi
, label2
, GSI_SAME_STMT
);
1238 last_assign
= gen_def_assigns (&gsi
, info
);
1241 label1
= gimple_build_label (label_decl1
);
1242 gsi_insert_before (&gsi
, label1
, GSI_SAME_STMT
);
1245 gsi
= gsi_start_bb (info
->final_bb
);
1246 label3
= gimple_build_label (label_decl3
);
1247 gsi_insert_before (&gsi
, label3
, GSI_SAME_STMT
);
1250 e02
= split_block (bb0
, cond_stmt
);
1253 e21
= split_block (bb2
, last_assign
);
1257 e1d
= split_block (bb1
, info
->arr_ref_last
);
1261 /* flags and profiles of the edge for in-range values */
1262 e01
= make_edge (bb0
, bb1
, EDGE_TRUE_VALUE
);
1263 e01
->probability
= REG_BR_PROB_BASE
- info
->default_prob
;
1264 e01
->count
= info
->other_count
;
1266 /* flags and profiles of the edge taking care of out-of-range values */
1267 e02
->flags
&= ~EDGE_FALLTHRU
;
1268 e02
->flags
|= EDGE_FALSE_VALUE
;
1269 e02
->probability
= info
->default_prob
;
1270 e02
->count
= info
->default_count
;
1272 bbf
= info
->final_bb
;
1274 e1f
= make_edge (bb1
, bbf
, EDGE_FALLTHRU
);
1275 e1f
->probability
= REG_BR_PROB_BASE
;
1276 e1f
->count
= info
->other_count
;
1278 e2f
= make_edge (bb2
, bbf
, EDGE_FALLTHRU
);
1279 e2f
->probability
= REG_BR_PROB_BASE
;
1280 e2f
->count
= info
->default_count
;
1282 /* frequencies of the new BBs */
1283 bb1
->frequency
= EDGE_FREQUENCY (e01
);
1284 bb2
->frequency
= EDGE_FREQUENCY (e02
);
1285 bbf
->frequency
= EDGE_FREQUENCY (e1f
) + EDGE_FREQUENCY (e2f
);
1287 /* Tidy blocks that have become unreachable. */
1288 prune_bbs (bbd
, info
->final_bb
);
1290 /* Fixup the PHI nodes in bbF. */
1291 fix_phi_nodes (e1f
, e2f
, bbf
, info
);
1293 /* Fix the dominator tree, if it is available. */
1294 if (dom_info_available_p (CDI_DOMINATORS
))
1296 vec
<basic_block
> bbs_to_fix_dom
;
1298 set_immediate_dominator (CDI_DOMINATORS
, bb1
, bb0
);
1299 set_immediate_dominator (CDI_DOMINATORS
, bb2
, bb0
);
1300 if (! get_immediate_dominator (CDI_DOMINATORS
, bbf
))
1301 /* If bbD was the immediate dominator ... */
1302 set_immediate_dominator (CDI_DOMINATORS
, bbf
, bb0
);
1304 bbs_to_fix_dom
.create (4);
1305 bbs_to_fix_dom
.quick_push (bb0
);
1306 bbs_to_fix_dom
.quick_push (bb1
);
1307 bbs_to_fix_dom
.quick_push (bb2
);
1308 bbs_to_fix_dom
.quick_push (bbf
);
1310 iterate_fix_dominators (CDI_DOMINATORS
, bbs_to_fix_dom
, true);
1311 bbs_to_fix_dom
.release ();
1315 /* The following function is invoked on every switch statement (the current one
1316 is given in SWTCH) and runs the individual phases of switch conversion on it
1317 one after another until one fails or the conversion is completed.
1318 Returns NULL on success, or a pointer to a string with the reason why the
1319 conversion failed. */
1322 process_switch (gimple swtch
)
1324 struct switch_conv_info info
;
1326 /* Group case labels so that we get the right results from the heuristics
1327 that decide on the code generation approach for this switch. */
1328 group_case_labels_stmt (swtch
);
1330 /* If this switch is now a degenerate case with only a default label,
1331 there is nothing left for us to do. */
1332 if (gimple_switch_num_labels (swtch
) < 2)
1333 return "switch is a degenerate case";
1335 collect_switch_conv_info (swtch
, &info
);
1337 /* No error markers should reach here (they should be filtered out
1338 during gimplification). */
1339 gcc_checking_assert (TREE_TYPE (info
.index_expr
) != error_mark_node
);
1341 /* A switch on a constant should have been optimized in tree-cfg-cleanup. */
1342 gcc_checking_assert (! TREE_CONSTANT (info
.index_expr
));
1344 if (info
.uniq
<= MAX_CASE_BIT_TESTS
)
1346 if (expand_switch_using_bit_tests_p (info
.range_size
,
1347 info
.uniq
, info
.count
))
1350 fputs (" expanding as bit test is preferable\n", dump_file
);
1351 emit_case_bit_tests (swtch
, info
.index_expr
,
1352 info
.range_min
, info
.range_size
);
1354 loops_state_set (LOOPS_NEED_FIXUP
);
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;
1466 const pass_data pass_data_convert_switch
=
1468 GIMPLE_PASS
, /* type */
1469 "switchconv", /* name */
1470 OPTGROUP_NONE
, /* optinfo_flags */
1471 true, /* has_gate */
1472 true, /* has_execute */
1473 TV_TREE_SWITCH_CONVERSION
, /* tv_id */
1474 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1475 0, /* properties_provided */
1476 0, /* properties_destroyed */
1477 0, /* todo_flags_start */
1478 ( TODO_update_ssa
| TODO_verify_ssa
1480 | TODO_verify_flow
), /* todo_flags_finish */
1483 class pass_convert_switch
: public gimple_opt_pass
1486 pass_convert_switch (gcc::context
*ctxt
)
1487 : gimple_opt_pass (pass_data_convert_switch
, ctxt
)
1490 /* opt_pass methods: */
1491 bool gate () { return switchconv_gate (); }
1492 unsigned int execute () { return do_switchconv (); }
1494 }; // class pass_convert_switch
1499 make_pass_convert_switch (gcc::context
*ctxt
)
1501 return new pass_convert_switch (ctxt
);