1 /* Switch Conversion converts variable initializations based on switch
2 statements to initializations from a static array.
3 Copyright (C) 2006, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
4 Contributed by Martin Jambor <jamborm@suse.cz>
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
24 Switch initialization conversion
26 The following pass changes simple initializations of scalars in a switch
27 statement into initializations from a static array. Obviously, the values
28 must be constant and known at compile time and a default branch must be
29 provided. For example, the following code:
53 a_5 = PHI <a_1, a_2, a_3, a_4>
54 b_5 = PHI <b_1, b_2, b_3, b_4>
59 static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
60 static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
63 if (((unsigned) argc) - 1 < 11)
65 a_6 = CSWTCH02[argc - 1];
66 b_6 = CSWTCH01[argc - 1];
76 There are further constraints. Specifically, the range of values across all
77 case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
78 eight) times the number of the actual switch branches. */
82 #include "coretypes.h"
88 #include "basic-block.h"
89 #include "tree-flow.h"
90 #include "tree-flow-inline.h"
91 #include "tree-ssa-operands.h"
93 #include "tree-pass.h"
94 #include "gimple-pretty-print.h"
95 #include "tree-dump.h"
97 #include "langhooks.h"
99 /* The main structure of the pass. */
100 struct switch_conv_info
102 /* The expression used to decide the switch branch. */
105 /* The following integer constants store the minimum and maximum value
106 covered by the case labels. */
110 /* The difference between the above two numbers. Stored here because it
111 is used in all the conversion heuristics, as well as for some of the
112 transformation, and it is expensive to re-compute it all the time. */
115 /* Basic block that contains the actual GIMPLE_SWITCH. */
116 basic_block switch_bb
;
118 /* Basic block that is the target of the default case. */
119 basic_block default_bb
;
121 /* The single successor block of all branches out of the GIMPLE_SWITCH,
122 if such a block exists. Otherwise NULL. */
123 basic_block final_bb
;
125 /* The probability of the default edge in the replaced switch. */
128 /* The count of the default edge in the replaced switch. */
129 gcov_type default_count
;
131 /* Combined count of all other (non-default) edges in the replaced switch. */
132 gcov_type other_count
;
134 /* Number of phi nodes in the final bb (that we'll be replacing). */
137 /* Array of default values, in the same order as phi nodes. */
138 tree
*default_values
;
140 /* Constructors of new static arrays. */
141 VEC (constructor_elt
, gc
) **constructors
;
143 /* Array of ssa names that are initialized with a value from a new static
145 tree
*target_inbound_names
;
147 /* Array of ssa names that are initialized with the default value if the
148 switch expression is out of range. */
149 tree
*target_outbound_names
;
151 /* The first load statement that loads a temporary from a new static array.
153 gimple arr_ref_first
;
155 /* The last load statement that loads a temporary from a new static array. */
158 /* String reason why the case wasn't a good candidate that is written to the
159 dump file, if there is one. */
162 /* Parameters for expand_switch_using_bit_tests. Should be computed
163 the same way as in expand_case. */
168 /* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */
171 collect_switch_conv_info (gimple swtch
, struct switch_conv_info
*info
)
173 unsigned int branch_num
= gimple_switch_num_labels (swtch
);
174 tree min_case
, max_case
;
175 unsigned int count
, i
;
179 memset (info
, 0, sizeof (*info
));
181 /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
182 is a default label which is the first in the vector. */
183 gcc_assert (CASE_LOW (gimple_switch_label (swtch
, 0)) == NULL_TREE
);
185 /* Collect the bits we can deduce from the CFG. */
186 info
->index_expr
= gimple_switch_index (swtch
);
187 info
->switch_bb
= gimple_bb (swtch
);
189 label_to_block (CASE_LABEL (gimple_switch_label (swtch
, 0)));
190 e_default
= find_edge (info
->switch_bb
, info
->default_bb
);
191 info
->default_prob
= e_default
->probability
;
192 info
->default_count
= e_default
->count
;
193 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
195 info
->other_count
+= e
->count
;
197 /* See if there is one common successor block for all branch
198 targets. If it exists, record it in FINAL_BB. */
199 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
201 if (! single_pred_p (e
->dest
))
203 info
->final_bb
= e
->dest
;
208 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
210 if (e
->dest
== info
->final_bb
)
213 if (single_pred_p (e
->dest
)
214 && single_succ_p (e
->dest
)
215 && single_succ (e
->dest
) == info
->final_bb
)
218 info
->final_bb
= NULL
;
222 /* Get upper and lower bounds of case values, and the covered range. */
223 min_case
= gimple_switch_label (swtch
, 1);
224 max_case
= gimple_switch_label (swtch
, branch_num
- 1);
226 info
->range_min
= CASE_LOW (min_case
);
227 if (CASE_HIGH (max_case
) != NULL_TREE
)
228 info
->range_max
= CASE_HIGH (max_case
);
230 info
->range_max
= CASE_LOW (max_case
);
233 int_const_binop (MINUS_EXPR
, info
->range_max
, info
->range_min
);
235 /* Get a count of the number of case labels. Single-valued case labels
236 simply count as one, but a case range counts double, since it may
237 require two compares if it gets lowered as a branching tree. */
239 for (i
= 1; i
< branch_num
; i
++)
241 tree elt
= gimple_switch_label (swtch
, i
);
244 && ! tree_int_cst_equal (CASE_LOW (elt
), CASE_HIGH (elt
)))
249 /* Get the number of unique non-default targets out of the GIMPLE_SWITCH
250 block. Assume a CFG cleanup would have already removed degenerate
251 switch statements, this allows us to just use EDGE_COUNT. */
252 info
->uniq
= EDGE_COUNT (gimple_bb (swtch
)->succs
) - 1;
255 /* Checks whether the range given by individual case statements of the SWTCH
256 switch statement isn't too big and whether the number of branches actually
257 satisfies the size of the new array. */
260 check_range (struct switch_conv_info
*info
)
262 gcc_assert (info
->range_size
);
263 if (!host_integerp (info
->range_size
, 1))
265 info
->reason
= "index range way too large or otherwise unusable";
269 if ((unsigned HOST_WIDE_INT
) tree_low_cst (info
->range_size
, 1)
270 > ((unsigned) info
->count
* SWITCH_CONVERSION_BRANCH_RATIO
))
272 info
->reason
= "the maximum range-branch ratio exceeded";
279 /* Checks whether all but the FINAL_BB basic blocks are empty. */
282 check_all_empty_except_final (struct switch_conv_info
*info
)
287 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
289 if (e
->dest
== info
->final_bb
)
292 if (!empty_block_p (e
->dest
))
294 info
->reason
= "bad case - a non-final BB not empty";
302 /* This function checks whether all required values in phi nodes in final_bb
303 are constants. Required values are those that correspond to a basic block
304 which is a part of the examined switch statement. It returns true if the
305 phi nodes are OK, otherwise false. */
308 check_final_bb (struct switch_conv_info
*info
)
310 gimple_stmt_iterator gsi
;
313 for (gsi
= gsi_start_phis (info
->final_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
315 gimple phi
= gsi_stmt (gsi
);
320 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
322 basic_block bb
= gimple_phi_arg_edge (phi
, i
)->src
;
324 if (bb
== info
->switch_bb
325 || (single_pred_p (bb
) && single_pred (bb
) == info
->switch_bb
))
329 val
= gimple_phi_arg_def (phi
, i
);
330 if (!is_gimple_ip_invariant (val
))
332 info
->reason
= "non-invariant value from a case";
333 return false; /* Non-invariant argument. */
335 reloc
= initializer_constant_valid_p (val
, TREE_TYPE (val
));
336 if ((flag_pic
&& reloc
!= null_pointer_node
)
337 || (!flag_pic
&& reloc
== NULL_TREE
))
341 = "value from a case would need runtime relocations";
344 = "value from a case is not a valid initializer";
354 /* The following function allocates default_values, target_{in,out}_names and
355 constructors arrays. The last one is also populated with pointers to
356 vectors that will become constructors of new arrays. */
359 create_temp_arrays (struct switch_conv_info
*info
)
363 info
->default_values
= XCNEWVEC (tree
, info
->phi_count
* 3);
364 info
->constructors
= XCNEWVEC (VEC (constructor_elt
, gc
) *, info
->phi_count
);
365 info
->target_inbound_names
= info
->default_values
+ info
->phi_count
;
366 info
->target_outbound_names
= info
->target_inbound_names
+ info
->phi_count
;
367 for (i
= 0; i
< info
->phi_count
; i
++)
368 info
->constructors
[i
]
369 = VEC_alloc (constructor_elt
, gc
, tree_low_cst (info
->range_size
, 1) + 1);
372 /* Free the arrays created by create_temp_arrays(). The vectors that are
373 created by that function are not freed here, however, because they have
374 already become constructors and must be preserved. */
377 free_temp_arrays (struct switch_conv_info
*info
)
379 XDELETEVEC (info
->constructors
);
380 XDELETEVEC (info
->default_values
);
383 /* Populate the array of default values in the order of phi nodes.
384 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch. */
387 gather_default_values (tree default_case
, struct switch_conv_info
*info
)
389 gimple_stmt_iterator gsi
;
390 basic_block bb
= label_to_block (CASE_LABEL (default_case
));
394 gcc_assert (CASE_LOW (default_case
) == NULL_TREE
);
396 if (bb
== info
->final_bb
)
397 e
= find_edge (info
->switch_bb
, bb
);
399 e
= single_succ_edge (bb
);
401 for (gsi
= gsi_start_phis (info
->final_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
403 gimple phi
= gsi_stmt (gsi
);
404 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
406 info
->default_values
[i
++] = val
;
410 /* The following function populates the vectors in the constructors array with
411 future contents of the static arrays. The vectors are populated in the
412 order of phi nodes. SWTCH is the switch statement being converted. */
415 build_constructors (gimple swtch
, struct switch_conv_info
*info
)
417 unsigned i
, branch_num
= gimple_switch_num_labels (swtch
);
418 tree pos
= info
->range_min
;
420 for (i
= 1; i
< branch_num
; i
++)
422 tree cs
= gimple_switch_label (swtch
, i
);
423 basic_block bb
= label_to_block (CASE_LABEL (cs
));
426 gimple_stmt_iterator gsi
;
429 if (bb
== info
->final_bb
)
430 e
= find_edge (info
->switch_bb
, bb
);
432 e
= single_succ_edge (bb
);
435 while (tree_int_cst_lt (pos
, CASE_LOW (cs
)))
438 for (k
= 0; k
< info
->phi_count
; k
++)
440 constructor_elt
*elt
;
442 elt
= VEC_quick_push (constructor_elt
,
443 info
->constructors
[k
], NULL
);
444 elt
->index
= int_const_binop (MINUS_EXPR
, pos
,
446 elt
->value
= info
->default_values
[k
];
449 pos
= int_const_binop (PLUS_EXPR
, pos
, integer_one_node
);
451 gcc_assert (tree_int_cst_equal (pos
, CASE_LOW (cs
)));
455 high
= CASE_HIGH (cs
);
457 high
= CASE_LOW (cs
);
458 for (gsi
= gsi_start_phis (info
->final_bb
);
459 !gsi_end_p (gsi
); gsi_next (&gsi
))
461 gimple phi
= gsi_stmt (gsi
);
462 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
463 tree low
= CASE_LOW (cs
);
468 constructor_elt
*elt
;
470 elt
= VEC_quick_push (constructor_elt
,
471 info
->constructors
[j
], NULL
);
472 elt
->index
= int_const_binop (MINUS_EXPR
, pos
, info
->range_min
);
475 pos
= int_const_binop (PLUS_EXPR
, pos
, integer_one_node
);
476 } while (!tree_int_cst_lt (high
, pos
)
477 && tree_int_cst_lt (low
, pos
));
483 /* If all values in the constructor vector are the same, return the value.
484 Otherwise return NULL_TREE. Not supposed to be called for empty
488 constructor_contains_same_values_p (VEC (constructor_elt
, gc
) *vec
)
491 tree prev
= NULL_TREE
;
492 constructor_elt
*elt
;
494 FOR_EACH_VEC_ELT (constructor_elt
, vec
, i
, elt
)
498 else if (!operand_equal_p (elt
->value
, prev
, OEP_ONLY_CONST
))
504 /* Return type which should be used for array elements, either TYPE,
505 or for integral type some smaller integral type that can still hold
506 all the constants. */
509 array_value_type (gimple swtch
, tree type
, int num
,
510 struct switch_conv_info
*info
)
512 unsigned int i
, len
= VEC_length (constructor_elt
, info
->constructors
[num
]);
513 constructor_elt
*elt
;
514 enum machine_mode mode
;
518 if (!INTEGRAL_TYPE_P (type
))
521 mode
= GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type
)));
522 if (GET_MODE_SIZE (TYPE_MODE (type
)) <= GET_MODE_SIZE (mode
))
525 if (len
< (optimize_bb_for_size_p (gimple_bb (swtch
)) ? 2 : 32))
528 FOR_EACH_VEC_ELT (constructor_elt
, info
->constructors
[num
], i
, elt
)
532 if (TREE_CODE (elt
->value
) != INTEGER_CST
)
535 cst
= TREE_INT_CST (elt
->value
);
538 unsigned int prec
= GET_MODE_BITSIZE (mode
);
539 if (prec
> HOST_BITS_PER_WIDE_INT
)
543 && double_int_equal_p (cst
, double_int_zext (cst
, prec
)))
546 && double_int_equal_p (cst
, double_int_sext (cst
, prec
)))
552 && double_int_equal_p (cst
, double_int_sext (cst
, prec
)))
561 mode
= GET_MODE_WIDER_MODE (mode
);
563 || GET_MODE_SIZE (mode
) >= GET_MODE_SIZE (TYPE_MODE (type
)))
569 sign
= TYPE_UNSIGNED (type
) ? 1 : -1;
570 smaller_type
= lang_hooks
.types
.type_for_mode (mode
, sign
>= 0);
571 if (GET_MODE_SIZE (TYPE_MODE (type
))
572 <= GET_MODE_SIZE (TYPE_MODE (smaller_type
)))
578 /* Create an appropriate array type and declaration and assemble a static array
579 variable. Also create a load statement that initializes the variable in
580 question with a value from the static array. SWTCH is the switch statement
581 being converted, NUM is the index to arrays of constructors, default values
582 and target SSA names for this particular array. ARR_INDEX_TYPE is the type
583 of the index of the new array, PHI is the phi node of the final BB that
584 corresponds to the value that will be loaded from the created array. TIDX
585 is an ssa name of a temporary variable holding the index for loads from the
589 build_one_array (gimple swtch
, int num
, tree arr_index_type
, gimple phi
,
590 tree tidx
, struct switch_conv_info
*info
)
594 gimple_stmt_iterator gsi
= gsi_for_stmt (swtch
);
595 location_t loc
= gimple_location (swtch
);
597 gcc_assert (info
->default_values
[num
]);
599 name
= make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi
)), NULL
);
600 info
->target_inbound_names
[num
] = name
;
602 cst
= constructor_contains_same_values_p (info
->constructors
[num
]);
604 load
= gimple_build_assign (name
, cst
);
607 tree array_type
, ctor
, decl
, value_type
, fetch
, default_type
;
609 default_type
= TREE_TYPE (info
->default_values
[num
]);
610 value_type
= array_value_type (swtch
, default_type
, num
, info
);
611 array_type
= build_array_type (value_type
, arr_index_type
);
612 if (default_type
!= value_type
)
615 constructor_elt
*elt
;
617 FOR_EACH_VEC_ELT (constructor_elt
, info
->constructors
[num
], i
, elt
)
618 elt
->value
= fold_convert (value_type
, elt
->value
);
620 ctor
= build_constructor (array_type
, info
->constructors
[num
]);
621 TREE_CONSTANT (ctor
) = true;
622 TREE_STATIC (ctor
) = true;
624 decl
= build_decl (loc
, VAR_DECL
, NULL_TREE
, array_type
);
625 TREE_STATIC (decl
) = 1;
626 DECL_INITIAL (decl
) = ctor
;
628 DECL_NAME (decl
) = create_tmp_var_name ("CSWTCH");
629 DECL_ARTIFICIAL (decl
) = 1;
630 TREE_CONSTANT (decl
) = 1;
631 TREE_READONLY (decl
) = 1;
632 varpool_finalize_decl (decl
);
634 fetch
= build4 (ARRAY_REF
, value_type
, decl
, tidx
, NULL_TREE
,
636 if (default_type
!= value_type
)
638 fetch
= fold_convert (default_type
, fetch
);
639 fetch
= force_gimple_operand_gsi (&gsi
, fetch
, true, NULL_TREE
,
640 true, GSI_SAME_STMT
);
642 load
= gimple_build_assign (name
, fetch
);
645 SSA_NAME_DEF_STMT (name
) = load
;
646 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
648 info
->arr_ref_last
= load
;
651 /* Builds and initializes static arrays initialized with values gathered from
652 the SWTCH switch statement. Also creates statements that load values from
656 build_arrays (gimple swtch
, struct switch_conv_info
*info
)
659 tree tidx
, sub
, tmp
, utype
;
661 gimple_stmt_iterator gsi
;
663 location_t loc
= gimple_location (swtch
);
665 gsi
= gsi_for_stmt (swtch
);
667 /* Make sure we do not generate arithmetics in a subrange. */
668 utype
= TREE_TYPE (info
->index_expr
);
669 if (TREE_TYPE (utype
))
670 utype
= lang_hooks
.types
.type_for_mode (TYPE_MODE (TREE_TYPE (utype
)), 1);
672 utype
= lang_hooks
.types
.type_for_mode (TYPE_MODE (utype
), 1);
674 arr_index_type
= build_index_type (info
->range_size
);
675 tmp
= create_tmp_var (utype
, "csui");
676 add_referenced_var (tmp
);
677 tidx
= make_ssa_name (tmp
, NULL
);
678 sub
= fold_build2_loc (loc
, MINUS_EXPR
, utype
,
679 fold_convert_loc (loc
, utype
, info
->index_expr
),
680 fold_convert_loc (loc
, utype
, info
->range_min
));
681 sub
= force_gimple_operand_gsi (&gsi
, sub
,
682 false, NULL
, true, GSI_SAME_STMT
);
683 stmt
= gimple_build_assign (tidx
, sub
);
684 SSA_NAME_DEF_STMT (tidx
) = stmt
;
686 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
688 info
->arr_ref_first
= stmt
;
690 for (gsi
= gsi_start_phis (info
->final_bb
), i
= 0;
691 !gsi_end_p (gsi
); gsi_next (&gsi
), i
++)
692 build_one_array (swtch
, i
, arr_index_type
, gsi_stmt (gsi
), tidx
, info
);
695 /* Generates and appropriately inserts loads of default values at the position
696 given by BSI. Returns the last inserted statement. */
699 gen_def_assigns (gimple_stmt_iterator
*gsi
, struct switch_conv_info
*info
)
702 gimple assign
= NULL
;
704 for (i
= 0; i
< info
->phi_count
; i
++)
707 = make_ssa_name (SSA_NAME_VAR (info
->target_inbound_names
[i
]), NULL
);
709 info
->target_outbound_names
[i
] = name
;
710 assign
= gimple_build_assign (name
, info
->default_values
[i
]);
711 SSA_NAME_DEF_STMT (name
) = assign
;
712 gsi_insert_before (gsi
, assign
, GSI_SAME_STMT
);
713 update_stmt (assign
);
718 /* Deletes the unused bbs and edges that now contain the switch statement and
719 its empty branch bbs. BBD is the now dead BB containing the original switch
720 statement, FINAL is the last BB of the converted switch statement (in terms
724 prune_bbs (basic_block bbd
, basic_block final
)
729 for (ei
= ei_start (bbd
->succs
); (e
= ei_safe_edge (ei
)); )
735 delete_basic_block (bb
);
737 delete_basic_block (bbd
);
740 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
741 from the basic block loading values from an array and E2F from the basic
742 block loading default values. BBF is the last switch basic block (see the
743 bbf description in the comment below). */
746 fix_phi_nodes (edge e1f
, edge e2f
, basic_block bbf
,
747 struct switch_conv_info
*info
)
749 gimple_stmt_iterator gsi
;
752 for (gsi
= gsi_start_phis (bbf
), i
= 0;
753 !gsi_end_p (gsi
); gsi_next (&gsi
), i
++)
755 gimple phi
= gsi_stmt (gsi
);
756 add_phi_arg (phi
, info
->target_inbound_names
[i
], e1f
, UNKNOWN_LOCATION
);
757 add_phi_arg (phi
, info
->target_outbound_names
[i
], e2f
, UNKNOWN_LOCATION
);
761 /* Creates a check whether the switch expression value actually falls into the
762 range given by all the cases. If it does not, the temporaries are loaded
763 with default values instead. SWTCH is the switch statement being converted.
765 bb0 is the bb with the switch statement, however, we'll end it with a
768 bb1 is the bb to be used when the range check went ok. It is derived from
771 bb2 is the bb taken when the expression evaluated outside of the range
772 covered by the created arrays. It is populated by loads of default
775 bbF is a fall through for both bb1 and bb2 and contains exactly what
776 originally followed the switch statement.
778 bbD contains the switch statement (in the end). It is unreachable but we
779 still need to strip off its edges.
783 gen_inbound_check (gimple swtch
, struct switch_conv_info
*info
)
785 tree label_decl1
= create_artificial_label (UNKNOWN_LOCATION
);
786 tree label_decl2
= create_artificial_label (UNKNOWN_LOCATION
);
787 tree label_decl3
= create_artificial_label (UNKNOWN_LOCATION
);
788 gimple label1
, label2
, label3
;
795 gimple_stmt_iterator gsi
;
796 basic_block bb0
, bb1
, bb2
, bbf
, bbd
;
797 edge e01
, e02
, e21
, e1d
, e1f
, e2f
;
798 location_t loc
= gimple_location (swtch
);
800 gcc_assert (info
->default_values
);
802 /* Make no effort to update the post-dominator tree. It is actually not
803 that hard for the transformations we have performed, but it is not
804 supported by iterate_fix_dominators.
805 Freeing post-dominance info is dome early to avoid pointless work in
806 create_basic_block, which is called when we split SWITCH_BB. */
807 free_dominance_info (CDI_POST_DOMINATORS
);
809 bb0
= gimple_bb (swtch
);
811 tidx
= gimple_assign_lhs (info
->arr_ref_first
);
812 utype
= TREE_TYPE (tidx
);
814 /* (end of) block 0 */
815 gsi
= gsi_for_stmt (info
->arr_ref_first
);
818 bound
= fold_convert_loc (loc
, utype
, info
->range_size
);
819 cond_stmt
= gimple_build_cond (LE_EXPR
, tidx
, bound
, NULL_TREE
, NULL_TREE
);
820 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
821 update_stmt (cond_stmt
);
824 label2
= gimple_build_label (label_decl2
);
825 gsi_insert_before (&gsi
, label2
, GSI_SAME_STMT
);
826 last_assign
= gen_def_assigns (&gsi
, info
);
829 label1
= gimple_build_label (label_decl1
);
830 gsi_insert_before (&gsi
, label1
, GSI_SAME_STMT
);
833 gsi
= gsi_start_bb (info
->final_bb
);
834 label3
= gimple_build_label (label_decl3
);
835 gsi_insert_before (&gsi
, label3
, GSI_SAME_STMT
);
838 e02
= split_block (bb0
, cond_stmt
);
841 e21
= split_block (bb2
, last_assign
);
845 e1d
= split_block (bb1
, info
->arr_ref_last
);
849 /* flags and profiles of the edge for in-range values */
850 e01
= make_edge (bb0
, bb1
, EDGE_TRUE_VALUE
);
851 e01
->probability
= REG_BR_PROB_BASE
- info
->default_prob
;
852 e01
->count
= info
->other_count
;
854 /* flags and profiles of the edge taking care of out-of-range values */
855 e02
->flags
&= ~EDGE_FALLTHRU
;
856 e02
->flags
|= EDGE_FALSE_VALUE
;
857 e02
->probability
= info
->default_prob
;
858 e02
->count
= info
->default_count
;
860 bbf
= info
->final_bb
;
862 e1f
= make_edge (bb1
, bbf
, EDGE_FALLTHRU
);
863 e1f
->probability
= REG_BR_PROB_BASE
;
864 e1f
->count
= info
->other_count
;
866 e2f
= make_edge (bb2
, bbf
, EDGE_FALLTHRU
);
867 e2f
->probability
= REG_BR_PROB_BASE
;
868 e2f
->count
= info
->default_count
;
870 /* frequencies of the new BBs */
871 bb1
->frequency
= EDGE_FREQUENCY (e01
);
872 bb2
->frequency
= EDGE_FREQUENCY (e02
);
873 bbf
->frequency
= EDGE_FREQUENCY (e1f
) + EDGE_FREQUENCY (e2f
);
875 /* Tidy blocks that have become unreachable. */
876 prune_bbs (bbd
, info
->final_bb
);
878 /* Fixup the PHI nodes in bbF. */
879 fix_phi_nodes (e1f
, e2f
, bbf
, info
);
881 /* Fix the dominator tree, if it is available. */
882 if (dom_info_available_p (CDI_DOMINATORS
))
884 VEC (basic_block
, heap
) *bbs_to_fix_dom
;
886 set_immediate_dominator (CDI_DOMINATORS
, bb1
, bb0
);
887 set_immediate_dominator (CDI_DOMINATORS
, bb2
, bb0
);
888 if (! get_immediate_dominator(CDI_DOMINATORS
, bbf
))
889 /* If bbD was the immediate dominator ... */
890 set_immediate_dominator (CDI_DOMINATORS
, bbf
, bb0
);
892 bbs_to_fix_dom
= VEC_alloc (basic_block
, heap
, 4);
893 VEC_quick_push (basic_block
, bbs_to_fix_dom
, bb0
);
894 VEC_quick_push (basic_block
, bbs_to_fix_dom
, bb1
);
895 VEC_quick_push (basic_block
, bbs_to_fix_dom
, bb2
);
896 VEC_quick_push (basic_block
, bbs_to_fix_dom
, bbf
);
898 iterate_fix_dominators (CDI_DOMINATORS
, bbs_to_fix_dom
, true);
899 VEC_free (basic_block
, heap
, bbs_to_fix_dom
);
903 /* The following function is invoked on every switch statement (the current one
904 is given in SWTCH) and runs the individual phases of switch conversion on it
905 one after another until one fails or the conversion is completed.
906 Returns NULL on success, or a pointer to a string with the reason why the
907 conversion failed. */
910 process_switch (gimple swtch
)
912 struct switch_conv_info info
;
914 /* Degenerate case with only a default label should never happen. */
915 gcc_checking_assert (gimple_switch_num_labels (swtch
) > 1);
917 collect_switch_conv_info (swtch
, &info
);
919 /* No error markers should reach here (they should be filtered out
920 during gimplification). */
921 gcc_checking_assert (TREE_TYPE (info
.index_expr
) != error_mark_node
);
923 /* If there is no common successor, we cannot do the transformation. */
925 return "no common successor to all case label target blocks found";
929 if (expand_switch_using_bit_tests_p (info
.index_expr
, info
.range_size
,
930 info
.uniq
, info
.count
))
931 return "expanding as bit test is preferable";
934 /* Check the case label values are within reasonable range: */
935 if (!check_range (&info
))
937 gcc_assert (info
.reason
);
941 /* For all the cases, see whether they are empty, the assignments they
942 represent constant and so on... */
943 if (! check_all_empty_except_final (&info
))
945 gcc_assert (info
.reason
);
948 if (!check_final_bb (&info
))
950 gcc_assert (info
.reason
);
954 /* At this point all checks have passed and we can proceed with the
957 create_temp_arrays (&info
);
958 gather_default_values (gimple_switch_label (swtch
, 0), &info
);
959 build_constructors (swtch
, &info
);
961 build_arrays (swtch
, &info
); /* Build the static arrays and assignments. */
962 gen_inbound_check (swtch
, &info
); /* Build the bounds check. */
965 free_temp_arrays (&info
);
969 /* The main function of the pass scans statements for switches and invokes
970 process_switch on them. */
979 const char *failure_reason
;
980 gimple stmt
= last_stmt (bb
);
981 if (stmt
&& gimple_code (stmt
) == GIMPLE_SWITCH
)
985 expanded_location loc
= expand_location (gimple_location (stmt
));
987 fprintf (dump_file
, "beginning to process the following "
988 "SWITCH statement (%s:%d) : ------- \n",
990 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
991 putc ('\n', dump_file
);
994 failure_reason
= process_switch (stmt
);
995 if (! failure_reason
)
999 fputs ("Switch converted\n", dump_file
);
1000 fputs ("--------------------------------\n", dump_file
);
1007 fputs ("Bailing out - ", dump_file
);
1008 fputs (failure_reason
, dump_file
);
1009 fputs ("\n--------------------------------\n", dump_file
);
1018 /* The pass gate. */
1021 switchconv_gate (void)
1023 return flag_tree_switch_conversion
!= 0;
1026 struct gimple_opt_pass pass_convert_switch
=
1030 "switchconv", /* name */
1031 switchconv_gate
, /* gate */
1032 do_switchconv
, /* execute */
1035 0, /* static_pass_number */
1036 TV_TREE_SWITCH_CONVERSION
, /* tv_id */
1037 PROP_cfg
| PROP_ssa
, /* properties_required */
1038 0, /* properties_provided */
1039 0, /* properties_destroyed */
1040 0, /* todo_flags_start */
1042 | TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */