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 must
28 be constant and known at compile time and a default branch must be
29 provided. For example, the following code:
52 a_5 = PHI <a_1, a_2, a_3, a_4>
53 b_5 = PHI <b_1, b_2, b_3, b_4>
58 static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
59 static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
62 if (((unsigned) argc) - 1 < 11)
64 a_6 = CSWTCH02[argc - 1];
65 b_6 = CSWTCH01[argc - 1];
75 There are further constraints. Specifically, the range of values across all
76 case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
77 eight) times the number of the actual switch branches. */
81 #include "coretypes.h"
87 #include "basic-block.h"
88 #include "tree-flow.h"
89 #include "tree-flow-inline.h"
90 #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. (It is subsequently used
103 as the index to the created array.) */
106 /* The following integer constants store the minimum value covered by the
110 /* The difference between the above two numbers, i.e. The size of the array
111 that would have to be created by the transformation. */
114 /* Basic block that contains the actual SWITCH_EXPR. */
115 basic_block switch_bb
;
117 /* All branches of the switch statement must have a single successor stored in
118 the following variable. */
119 basic_block final_bb
;
121 /* Number of phi nodes in the final bb (that we'll be replacing). */
124 /* Array of default values, in the same order as phi nodes. */
125 tree
*default_values
;
127 /* Constructors of new static arrays. */
128 VEC (constructor_elt
, gc
) **constructors
;
130 /* Array of ssa names that are initialized with a value from a new static
132 tree
*target_inbound_names
;
134 /* Array of ssa names that are initialized with the default value if the
135 switch expression is out of range. */
136 tree
*target_outbound_names
;
138 /* The probability of the default edge in the replaced switch. */
141 /* The count of the default edge in the replaced switch. */
142 gcov_type default_count
;
144 /* Combined count of all other (non-default) edges in the replaced switch. */
145 gcov_type other_count
;
147 /* The first load statement that loads a temporary from a new static array.
149 gimple arr_ref_first
;
151 /* The last load statement that loads a temporary from a new static array. */
154 /* String reason why the case wasn't a good candidate that is written to the
155 dump file, if there is one. */
158 /* Parameters for expand_switch_using_bit_tests. Should be computed
159 the same way as in expand_case. */
160 unsigned int bit_test_uniq
;
161 unsigned int bit_test_count
;
162 basic_block bit_test_bb
[2];
165 /* Global pass info. */
166 static struct switch_conv_info info
;
169 /* Checks whether the range given by individual case statements of the SWTCH
170 switch statement isn't too big and whether the number of branches actually
171 satisfies the size of the new array. */
174 check_range (gimple swtch
)
176 tree min_case
, max_case
;
177 unsigned int branch_num
= gimple_switch_num_labels (swtch
);
180 /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
181 is a default label which is the first in the vector. */
183 min_case
= gimple_switch_label (swtch
, 1);
184 info
.range_min
= CASE_LOW (min_case
);
186 gcc_assert (branch_num
> 1);
187 gcc_assert (CASE_LOW (gimple_switch_label (swtch
, 0)) == NULL_TREE
);
188 max_case
= gimple_switch_label (swtch
, branch_num
- 1);
189 if (CASE_HIGH (max_case
) != NULL_TREE
)
190 range_max
= CASE_HIGH (max_case
);
192 range_max
= CASE_LOW (max_case
);
194 gcc_assert (info
.range_min
);
195 gcc_assert (range_max
);
197 info
.range_size
= int_const_binop (MINUS_EXPR
, range_max
, info
.range_min
);
199 gcc_assert (info
.range_size
);
200 if (!host_integerp (info
.range_size
, 1))
202 info
.reason
= "index range way too large or otherwise unusable.\n";
206 if ((unsigned HOST_WIDE_INT
) tree_low_cst (info
.range_size
, 1)
207 > ((unsigned) branch_num
* SWITCH_CONVERSION_BRANCH_RATIO
))
209 info
.reason
= "the maximum range-branch ratio exceeded.\n";
216 /* Checks the given CS switch case whether it is suitable for conversion
217 (whether all but the default basic blocks are empty and so on). If it is,
218 adds the case to the branch list along with values for the defined variables
219 and returns true. Otherwise returns false. */
222 check_process_case (tree cs
)
225 basic_block label_bb
, following_bb
;
228 ldecl
= CASE_LABEL (cs
);
229 label_bb
= label_to_block (ldecl
);
231 e
= find_edge (info
.switch_bb
, label_bb
);
234 if (CASE_LOW (cs
) == NULL_TREE
)
236 /* Default branch. */
237 info
.default_prob
= e
->probability
;
238 info
.default_count
= e
->count
;
243 info
.other_count
+= e
->count
;
244 for (i
= 0; i
< 2; i
++)
245 if (info
.bit_test_bb
[i
] == label_bb
)
247 else if (info
.bit_test_bb
[i
] == NULL
)
249 info
.bit_test_bb
[i
] = label_bb
;
250 info
.bit_test_uniq
++;
254 info
.bit_test_uniq
= 3;
255 if (CASE_HIGH (cs
) != NULL_TREE
256 && ! tree_int_cst_equal (CASE_LOW (cs
), CASE_HIGH (cs
)))
257 info
.bit_test_count
+= 2;
259 info
.bit_test_count
++;
264 info
.reason
= " Bad case - cs BB label is NULL\n";
268 if (!single_pred_p (label_bb
))
270 if (info
.final_bb
&& info
.final_bb
!= label_bb
)
272 info
.reason
= " Bad case - a non-final BB has two predecessors\n";
273 return false; /* sth complex going on in this branch */
276 following_bb
= label_bb
;
280 if (!empty_block_p (label_bb
))
282 info
.reason
= " Bad case - a non-final BB not empty\n";
286 if (!single_succ_p (label_bb
))
289 = " Bad case - a non-final BB without a single successor\n";
292 following_bb
= single_succ (label_bb
);
296 info
.final_bb
= following_bb
;
297 else if (info
.final_bb
!= following_bb
)
299 info
.reason
= " Bad case - different final BB\n";
300 return false; /* the only successor is not common for all the branches */
306 /* This function checks whether all required values in phi nodes in final_bb
307 are constants. Required values are those that correspond to a basic block
308 which is a part of the examined switch statement. It returns true if the
309 phi nodes are OK, otherwise false. */
312 check_final_bb (void)
314 gimple_stmt_iterator gsi
;
317 for (gsi
= gsi_start_phis (info
.final_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
319 gimple phi
= gsi_stmt (gsi
);
324 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
326 basic_block bb
= gimple_phi_arg_edge (phi
, i
)->src
;
328 if (bb
== info
.switch_bb
329 || (single_pred_p (bb
) && single_pred (bb
) == info
.switch_bb
))
333 val
= gimple_phi_arg_def (phi
, i
);
334 if (!is_gimple_ip_invariant (val
))
336 info
.reason
= " Non-invariant value from a case\n";
337 return false; /* Non-invariant argument. */
339 reloc
= initializer_constant_valid_p (val
, TREE_TYPE (val
));
340 if ((flag_pic
&& reloc
!= null_pointer_node
)
341 || (!flag_pic
&& reloc
== NULL_TREE
))
345 = " Value from a case would need runtime relocations\n";
348 = " Value from a case is not a valid initializer\n";
358 /* The following function allocates default_values, target_{in,out}_names and
359 constructors arrays. The last one is also populated with pointers to
360 vectors that will become constructors of new arrays. */
363 create_temp_arrays (void)
367 info
.default_values
= XCNEWVEC (tree
, info
.phi_count
* 3);
368 info
.constructors
= XCNEWVEC (VEC (constructor_elt
, gc
) *, info
.phi_count
);
369 info
.target_inbound_names
= info
.default_values
+ info
.phi_count
;
370 info
.target_outbound_names
= info
.target_inbound_names
+ info
.phi_count
;
371 for (i
= 0; i
< info
.phi_count
; i
++)
373 = VEC_alloc (constructor_elt
, gc
, tree_low_cst (info
.range_size
, 1) + 1);
376 /* Free the arrays created by create_temp_arrays(). The vectors that are
377 created by that function are not freed here, however, because they have
378 already become constructors and must be preserved. */
381 free_temp_arrays (void)
383 XDELETEVEC (info
.constructors
);
384 XDELETEVEC (info
.default_values
);
387 /* Populate the array of default values in the order of phi nodes.
388 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch. */
391 gather_default_values (tree default_case
)
393 gimple_stmt_iterator gsi
;
394 basic_block bb
= label_to_block (CASE_LABEL (default_case
));
398 gcc_assert (CASE_LOW (default_case
) == NULL_TREE
);
400 if (bb
== info
.final_bb
)
401 e
= find_edge (info
.switch_bb
, bb
);
403 e
= single_succ_edge (bb
);
405 for (gsi
= gsi_start_phis (info
.final_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
407 gimple phi
= gsi_stmt (gsi
);
408 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
410 info
.default_values
[i
++] = val
;
414 /* The following function populates the vectors in the constructors array with
415 future contents of the static arrays. The vectors are populated in the
416 order of phi nodes. SWTCH is the switch statement being converted. */
419 build_constructors (gimple swtch
)
421 unsigned i
, branch_num
= gimple_switch_num_labels (swtch
);
422 tree pos
= info
.range_min
;
424 for (i
= 1; i
< branch_num
; i
++)
426 tree cs
= gimple_switch_label (swtch
, i
);
427 basic_block bb
= label_to_block (CASE_LABEL (cs
));
430 gimple_stmt_iterator gsi
;
433 if (bb
== info
.final_bb
)
434 e
= find_edge (info
.switch_bb
, bb
);
436 e
= single_succ_edge (bb
);
439 while (tree_int_cst_lt (pos
, CASE_LOW (cs
)))
442 for (k
= 0; k
< info
.phi_count
; k
++)
444 constructor_elt
*elt
;
446 elt
= VEC_quick_push (constructor_elt
,
447 info
.constructors
[k
], NULL
);
448 elt
->index
= int_const_binop (MINUS_EXPR
, pos
,
450 elt
->value
= info
.default_values
[k
];
453 pos
= int_const_binop (PLUS_EXPR
, pos
, integer_one_node
);
455 gcc_assert (tree_int_cst_equal (pos
, CASE_LOW (cs
)));
459 high
= CASE_HIGH (cs
);
461 high
= CASE_LOW (cs
);
462 for (gsi
= gsi_start_phis (info
.final_bb
);
463 !gsi_end_p (gsi
); gsi_next (&gsi
))
465 gimple phi
= gsi_stmt (gsi
);
466 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
467 tree low
= CASE_LOW (cs
);
472 constructor_elt
*elt
;
474 elt
= VEC_quick_push (constructor_elt
,
475 info
.constructors
[j
], NULL
);
476 elt
->index
= int_const_binop (MINUS_EXPR
, pos
, info
.range_min
);
479 pos
= int_const_binop (PLUS_EXPR
, pos
, integer_one_node
);
480 } while (!tree_int_cst_lt (high
, pos
)
481 && tree_int_cst_lt (low
, pos
));
487 /* If all values in the constructor vector are the same, return the value.
488 Otherwise return NULL_TREE. Not supposed to be called for empty
492 constructor_contains_same_values_p (VEC (constructor_elt
, gc
) *vec
)
495 tree prev
= NULL_TREE
;
496 constructor_elt
*elt
;
498 FOR_EACH_VEC_ELT (constructor_elt
, vec
, i
, elt
)
502 else if (!operand_equal_p (elt
->value
, prev
, OEP_ONLY_CONST
))
508 /* Return type which should be used for array elements, either TYPE,
509 or for integral type some smaller integral type that can still hold
510 all the constants. */
513 array_value_type (gimple swtch
, tree type
, int num
)
515 unsigned int i
, len
= VEC_length (constructor_elt
, info
.constructors
[num
]);
516 constructor_elt
*elt
;
517 enum machine_mode mode
;
521 if (!INTEGRAL_TYPE_P (type
))
524 mode
= GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type
)));
525 if (GET_MODE_SIZE (TYPE_MODE (type
)) <= GET_MODE_SIZE (mode
))
528 if (len
< (optimize_bb_for_size_p (gimple_bb (swtch
)) ? 2 : 32))
531 FOR_EACH_VEC_ELT (constructor_elt
, info
.constructors
[num
], i
, elt
)
535 if (TREE_CODE (elt
->value
) != INTEGER_CST
)
538 cst
= TREE_INT_CST (elt
->value
);
541 unsigned int prec
= GET_MODE_BITSIZE (mode
);
542 if (prec
> HOST_BITS_PER_WIDE_INT
)
546 && double_int_equal_p (cst
, double_int_zext (cst
, prec
)))
549 && double_int_equal_p (cst
, double_int_sext (cst
, prec
)))
555 && double_int_equal_p (cst
, double_int_sext (cst
, prec
)))
564 mode
= GET_MODE_WIDER_MODE (mode
);
566 || GET_MODE_SIZE (mode
) >= GET_MODE_SIZE (TYPE_MODE (type
)))
572 sign
= TYPE_UNSIGNED (type
) ? 1 : -1;
573 smaller_type
= lang_hooks
.types
.type_for_mode (mode
, sign
>= 0);
574 if (GET_MODE_SIZE (TYPE_MODE (type
))
575 <= GET_MODE_SIZE (TYPE_MODE (smaller_type
)))
581 /* Create an appropriate array type and declaration and assemble a static array
582 variable. Also create a load statement that initializes the variable in
583 question with a value from the static array. SWTCH is the switch statement
584 being converted, NUM is the index to arrays of constructors, default values
585 and target SSA names for this particular array. ARR_INDEX_TYPE is the type
586 of the index of the new array, PHI is the phi node of the final BB that
587 corresponds to the value that will be loaded from the created array. TIDX
588 is an ssa name of a temporary variable holding the index for loads from the
592 build_one_array (gimple swtch
, int num
, tree arr_index_type
, gimple phi
,
597 gimple_stmt_iterator gsi
= gsi_for_stmt (swtch
);
598 location_t loc
= gimple_location (swtch
);
600 gcc_assert (info
.default_values
[num
]);
602 name
= make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi
)), NULL
);
603 info
.target_inbound_names
[num
] = name
;
605 cst
= constructor_contains_same_values_p (info
.constructors
[num
]);
607 load
= gimple_build_assign (name
, cst
);
610 tree array_type
, ctor
, decl
, value_type
, fetch
, default_type
;
612 default_type
= TREE_TYPE (info
.default_values
[num
]);
613 value_type
= array_value_type (swtch
, default_type
, num
);
614 array_type
= build_array_type (value_type
, arr_index_type
);
615 if (default_type
!= value_type
)
618 constructor_elt
*elt
;
620 FOR_EACH_VEC_ELT (constructor_elt
, info
.constructors
[num
], i
, elt
)
621 elt
->value
= fold_convert (value_type
, elt
->value
);
623 ctor
= build_constructor (array_type
, info
.constructors
[num
]);
624 TREE_CONSTANT (ctor
) = true;
625 TREE_STATIC (ctor
) = true;
627 decl
= build_decl (loc
, VAR_DECL
, NULL_TREE
, array_type
);
628 TREE_STATIC (decl
) = 1;
629 DECL_INITIAL (decl
) = ctor
;
631 DECL_NAME (decl
) = create_tmp_var_name ("CSWTCH");
632 DECL_ARTIFICIAL (decl
) = 1;
633 TREE_CONSTANT (decl
) = 1;
634 TREE_READONLY (decl
) = 1;
635 add_referenced_var (decl
);
636 varpool_mark_needed_node (varpool_node (decl
));
637 varpool_finalize_decl (decl
);
639 fetch
= build4 (ARRAY_REF
, value_type
, decl
, tidx
, NULL_TREE
,
641 if (default_type
!= value_type
)
643 fetch
= fold_convert (default_type
, fetch
);
644 fetch
= force_gimple_operand_gsi (&gsi
, fetch
, true, NULL_TREE
,
645 true, GSI_SAME_STMT
);
647 load
= gimple_build_assign (name
, fetch
);
650 SSA_NAME_DEF_STMT (name
) = load
;
651 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
653 info
.arr_ref_last
= load
;
656 /* Builds and initializes static arrays initialized with values gathered from
657 the SWTCH switch statement. Also creates statements that load values from
661 build_arrays (gimple swtch
)
664 tree tidx
, sub
, tmp
, utype
;
666 gimple_stmt_iterator gsi
;
668 location_t loc
= gimple_location (swtch
);
670 gsi
= gsi_for_stmt (swtch
);
672 /* Make sure we do not generate arithmetics in a subrange. */
673 utype
= TREE_TYPE (info
.index_expr
);
674 if (TREE_TYPE (utype
))
675 utype
= lang_hooks
.types
.type_for_mode (TYPE_MODE (TREE_TYPE (utype
)), 1);
677 utype
= lang_hooks
.types
.type_for_mode (TYPE_MODE (utype
), 1);
679 arr_index_type
= build_index_type (info
.range_size
);
680 tmp
= create_tmp_var (utype
, "csui");
681 add_referenced_var (tmp
);
682 tidx
= make_ssa_name (tmp
, NULL
);
683 sub
= fold_build2_loc (loc
, MINUS_EXPR
, utype
,
684 fold_convert_loc (loc
, utype
, info
.index_expr
),
685 fold_convert_loc (loc
, utype
, info
.range_min
));
686 sub
= force_gimple_operand_gsi (&gsi
, sub
,
687 false, NULL
, true, GSI_SAME_STMT
);
688 stmt
= gimple_build_assign (tidx
, sub
);
689 SSA_NAME_DEF_STMT (tidx
) = stmt
;
691 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
693 info
.arr_ref_first
= stmt
;
695 for (gsi
= gsi_start_phis (info
.final_bb
), i
= 0;
696 !gsi_end_p (gsi
); gsi_next (&gsi
), i
++)
697 build_one_array (swtch
, i
, arr_index_type
, gsi_stmt (gsi
), tidx
);
700 /* Generates and appropriately inserts loads of default values at the position
701 given by BSI. Returns the last inserted statement. */
704 gen_def_assigns (gimple_stmt_iterator
*gsi
)
707 gimple assign
= NULL
;
709 for (i
= 0; i
< info
.phi_count
; i
++)
712 = make_ssa_name (SSA_NAME_VAR (info
.target_inbound_names
[i
]), NULL
);
714 info
.target_outbound_names
[i
] = name
;
715 assign
= gimple_build_assign (name
, info
.default_values
[i
]);
716 SSA_NAME_DEF_STMT (name
) = assign
;
717 gsi_insert_before (gsi
, assign
, GSI_SAME_STMT
);
718 update_stmt (assign
);
723 /* Deletes the unused bbs and edges that now contain the switch statement and
724 its empty branch bbs. BBD is the now dead BB containing the original switch
725 statement, FINAL is the last BB of the converted switch statement (in terms
729 prune_bbs (basic_block bbd
, basic_block final
)
734 for (ei
= ei_start (bbd
->succs
); (e
= ei_safe_edge (ei
)); )
740 delete_basic_block (bb
);
742 delete_basic_block (bbd
);
745 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
746 from the basic block loading values from an array and E2F from the basic
747 block loading default values. BBF is the last switch basic block (see the
748 bbf description in the comment below). */
751 fix_phi_nodes (edge e1f
, edge e2f
, basic_block bbf
)
753 gimple_stmt_iterator gsi
;
756 for (gsi
= gsi_start_phis (bbf
), i
= 0;
757 !gsi_end_p (gsi
); gsi_next (&gsi
), i
++)
759 gimple phi
= gsi_stmt (gsi
);
760 add_phi_arg (phi
, info
.target_inbound_names
[i
], e1f
, UNKNOWN_LOCATION
);
761 add_phi_arg (phi
, info
.target_outbound_names
[i
], e2f
, UNKNOWN_LOCATION
);
766 /* Creates a check whether the switch expression value actually falls into the
767 range given by all the cases. If it does not, the temporaries are loaded
768 with default values instead. SWTCH is the switch statement being converted.
770 bb0 is the bb with the switch statement, however, we'll end it with a
773 bb1 is the bb to be used when the range check went ok. It is derived from
776 bb2 is the bb taken when the expression evaluated outside of the range
777 covered by the created arrays. It is populated by loads of default
780 bbF is a fall through for both bb1 and bb2 and contains exactly what
781 originally followed the switch statement.
783 bbD contains the switch statement (in the end). It is unreachable but we
784 still need to strip off its edges.
788 gen_inbound_check (gimple swtch
)
790 tree label_decl1
= create_artificial_label (UNKNOWN_LOCATION
);
791 tree label_decl2
= create_artificial_label (UNKNOWN_LOCATION
);
792 tree label_decl3
= create_artificial_label (UNKNOWN_LOCATION
);
793 gimple label1
, label2
, label3
;
800 gimple_stmt_iterator gsi
;
801 basic_block bb0
, bb1
, bb2
, bbf
, bbd
;
802 edge e01
, e02
, e21
, e1d
, e1f
, e2f
;
803 location_t loc
= gimple_location (swtch
);
805 gcc_assert (info
.default_values
);
806 bb0
= gimple_bb (swtch
);
808 tidx
= gimple_assign_lhs (info
.arr_ref_first
);
809 utype
= TREE_TYPE (tidx
);
811 /* (end of) block 0 */
812 gsi
= gsi_for_stmt (info
.arr_ref_first
);
815 bound
= fold_convert_loc (loc
, utype
, info
.range_size
);
816 cond_stmt
= gimple_build_cond (LE_EXPR
, tidx
, bound
, NULL_TREE
, NULL_TREE
);
817 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
818 update_stmt (cond_stmt
);
821 label2
= gimple_build_label (label_decl2
);
822 gsi_insert_before (&gsi
, label2
, GSI_SAME_STMT
);
823 last_assign
= gen_def_assigns (&gsi
);
826 label1
= gimple_build_label (label_decl1
);
827 gsi_insert_before (&gsi
, label1
, GSI_SAME_STMT
);
830 gsi
= gsi_start_bb (info
.final_bb
);
831 label3
= gimple_build_label (label_decl3
);
832 gsi_insert_before (&gsi
, label3
, GSI_SAME_STMT
);
835 e02
= split_block (bb0
, cond_stmt
);
838 e21
= split_block (bb2
, last_assign
);
842 e1d
= split_block (bb1
, info
.arr_ref_last
);
846 /* flags and profiles of the edge for in-range values */
847 e01
= make_edge (bb0
, bb1
, EDGE_TRUE_VALUE
);
848 e01
->probability
= REG_BR_PROB_BASE
- info
.default_prob
;
849 e01
->count
= info
.other_count
;
851 /* flags and profiles of the edge taking care of out-of-range values */
852 e02
->flags
&= ~EDGE_FALLTHRU
;
853 e02
->flags
|= EDGE_FALSE_VALUE
;
854 e02
->probability
= info
.default_prob
;
855 e02
->count
= info
.default_count
;
859 e1f
= make_edge (bb1
, bbf
, EDGE_FALLTHRU
);
860 e1f
->probability
= REG_BR_PROB_BASE
;
861 e1f
->count
= info
.other_count
;
863 e2f
= make_edge (bb2
, bbf
, EDGE_FALLTHRU
);
864 e2f
->probability
= REG_BR_PROB_BASE
;
865 e2f
->count
= info
.default_count
;
867 /* frequencies of the new BBs */
868 bb1
->frequency
= EDGE_FREQUENCY (e01
);
869 bb2
->frequency
= EDGE_FREQUENCY (e02
);
870 bbf
->frequency
= EDGE_FREQUENCY (e1f
) + EDGE_FREQUENCY (e2f
);
872 prune_bbs (bbd
, info
.final_bb
); /* To keep calc_dfs_tree() in dominance.c
875 fix_phi_nodes (e1f
, e2f
, bbf
);
877 free_dominance_info (CDI_DOMINATORS
);
878 free_dominance_info (CDI_POST_DOMINATORS
);
881 /* The following function is invoked on every switch statement (the current one
882 is given in SWTCH) and runs the individual phases of switch conversion on it
883 one after another until one fails or the conversion is completed. */
886 process_switch (gimple swtch
)
888 unsigned int i
, branch_num
= gimple_switch_num_labels (swtch
);
891 /* Operand 2 is either NULL_TREE or a vector of cases (stmt.c). */
894 info
.reason
= "switch has no labels\n";
898 info
.final_bb
= NULL
;
899 info
.switch_bb
= gimple_bb (swtch
);
900 info
.index_expr
= gimple_switch_index (swtch
);
901 index_type
= TREE_TYPE (info
.index_expr
);
902 info
.arr_ref_first
= NULL
;
903 info
.arr_ref_last
= NULL
;
904 info
.default_prob
= 0;
905 info
.default_count
= 0;
906 info
.other_count
= 0;
907 info
.bit_test_uniq
= 0;
908 info
.bit_test_count
= 0;
909 info
.bit_test_bb
[0] = NULL
;
910 info
.bit_test_bb
[1] = NULL
;
912 /* An ERROR_MARK occurs for various reasons including invalid data type.
913 (comment from stmt.c) */
914 if (index_type
== error_mark_node
)
916 info
.reason
= "index error.\n";
920 /* Check the case label values are within reasonable range: */
921 if (!check_range (swtch
))
924 /* For all the cases, see whether they are empty, the assignments they
925 represent constant and so on... */
926 for (i
= 0; i
< branch_num
; i
++)
927 if (!check_process_case (gimple_switch_label (swtch
, i
)))
930 fprintf (dump_file
, "Processing of case %i failed\n", i
);
934 if (info
.bit_test_uniq
<= 2)
936 rtl_profile_for_bb (gimple_bb (swtch
));
937 if (expand_switch_using_bit_tests_p (gimple_switch_index (swtch
),
938 info
.range_size
, info
.bit_test_uniq
,
939 info
.bit_test_count
))
941 info
.reason
= " Expanding as bit test is preferable\n";
946 if (!check_final_bb ())
949 /* At this point all checks have passed and we can proceed with the
952 create_temp_arrays ();
953 gather_default_values (gimple_switch_label (swtch
, 0));
954 build_constructors (swtch
);
956 build_arrays (swtch
); /* Build the static arrays and assignments. */
957 gen_inbound_check (swtch
); /* Build the bounds check. */
964 /* The main function of the pass scans statements for switches and invokes
965 process_switch on them. */
974 gimple stmt
= last_stmt (bb
);
975 if (stmt
&& gimple_code (stmt
) == GIMPLE_SWITCH
)
979 expanded_location loc
= expand_location (gimple_location (stmt
));
981 fprintf (dump_file
, "beginning to process the following "
982 "SWITCH statement (%s:%d) : ------- \n",
984 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
985 putc ('\n', dump_file
);
989 if (process_switch (stmt
))
993 fputs ("Switch converted\n", dump_file
);
994 fputs ("--------------------------------\n", dump_file
);
1001 gcc_assert (info
.reason
);
1002 fputs ("Bailing out - ", dump_file
);
1003 fputs (info
.reason
, dump_file
);
1004 fputs ("--------------------------------\n", dump_file
);
1013 /* The pass gate. */
1016 switchconv_gate (void)
1018 return flag_tree_switch_conversion
!= 0;
1021 struct gimple_opt_pass pass_convert_switch
=
1025 "switchconv", /* name */
1026 switchconv_gate
, /* gate */
1027 do_switchconv
, /* execute */
1030 0, /* static_pass_number */
1031 TV_TREE_SWITCH_CONVERSION
, /* tv_id */
1032 PROP_cfg
| PROP_ssa
, /* properties_required */
1033 0, /* properties_provided */
1034 0, /* properties_destroyed */
1035 0, /* todo_flags_start */
1037 | TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */