1 /* Switch Conversion converts variable initializations based on switch
2 statements to initializations from a static array.
3 Copyright (C) 2006, 2008, 2009, 2010 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"
89 #include "basic-block.h"
90 #include "tree-flow.h"
91 #include "tree-flow-inline.h"
92 #include "tree-ssa-operands.h"
95 #include "tree-pass.h"
96 #include "gimple-pretty-print.h"
97 #include "tree-dump.h"
99 #include "langhooks.h"
101 /* The main structure of the pass. */
102 struct switch_conv_info
104 /* The expression used to decide the switch branch. (It is subsequently used
105 as the index to the created array.) */
108 /* The following integer constants store the minimum value covered by the
112 /* The difference between the above two numbers, i.e. The size of the array
113 that would have to be created by the transformation. */
116 /* Basic block that contains the actual SWITCH_EXPR. */
117 basic_block switch_bb
;
119 /* All branches of the switch statement must have a single successor stored in
120 the following variable. */
121 basic_block final_bb
;
123 /* Number of phi nodes in the final bb (that we'll be replacing). */
126 /* Array of default values, in the same order as phi nodes. */
127 tree
*default_values
;
129 /* Constructors of new static arrays. */
130 VEC (constructor_elt
, gc
) **constructors
;
132 /* Array of ssa names that are initialized with a value from a new static
134 tree
*target_inbound_names
;
136 /* Array of ssa names that are initialized with the default value if the
137 switch expression is out of range. */
138 tree
*target_outbound_names
;
140 /* The probability of the default edge in the replaced switch. */
143 /* The count of the default edge in the replaced switch. */
144 gcov_type default_count
;
146 /* Combined count of all other (non-default) edges in the replaced switch. */
147 gcov_type other_count
;
149 /* The first load statement that loads a temporary from a new static array.
151 gimple arr_ref_first
;
153 /* The last load statement that loads a temporary from a new static array. */
156 /* String reason why the case wasn't a good candidate that is written to the
157 dump file, if there is one. */
160 /* Parameters for expand_switch_using_bit_tests. Should be computed
161 the same way as in expand_case. */
162 unsigned int bit_test_uniq
;
163 unsigned int bit_test_count
;
164 basic_block bit_test_bb
[2];
167 /* Global pass info. */
168 static struct switch_conv_info info
;
171 /* Checks whether the range given by individual case statements of the SWTCH
172 switch statement isn't too big and whether the number of branches actually
173 satisfies the size of the new array. */
176 check_range (gimple swtch
)
178 tree min_case
, max_case
;
179 unsigned int branch_num
= gimple_switch_num_labels (swtch
);
182 /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
183 is a default label which is the first in the vector. */
185 min_case
= gimple_switch_label (swtch
, 1);
186 info
.range_min
= CASE_LOW (min_case
);
188 gcc_assert (branch_num
> 1);
189 gcc_assert (CASE_LOW (gimple_switch_label (swtch
, 0)) == NULL_TREE
);
190 max_case
= gimple_switch_label (swtch
, branch_num
- 1);
191 if (CASE_HIGH (max_case
) != NULL_TREE
)
192 range_max
= CASE_HIGH (max_case
);
194 range_max
= CASE_LOW (max_case
);
196 gcc_assert (info
.range_min
);
197 gcc_assert (range_max
);
199 info
.range_size
= int_const_binop (MINUS_EXPR
, range_max
, info
.range_min
, 0);
201 gcc_assert (info
.range_size
);
202 if (!host_integerp (info
.range_size
, 1))
204 info
.reason
= "index range way too large or otherwise unusable.\n";
208 if ((unsigned HOST_WIDE_INT
) tree_low_cst (info
.range_size
, 1)
209 > ((unsigned) branch_num
* SWITCH_CONVERSION_BRANCH_RATIO
))
211 info
.reason
= "the maximum range-branch ratio exceeded.\n";
218 /* Checks the given CS switch case whether it is suitable for conversion
219 (whether all but the default basic blocks are empty and so on). If it is,
220 adds the case to the branch list along with values for the defined variables
221 and returns true. Otherwise returns false. */
224 check_process_case (tree cs
)
227 basic_block label_bb
, following_bb
;
230 ldecl
= CASE_LABEL (cs
);
231 label_bb
= label_to_block (ldecl
);
233 e
= find_edge (info
.switch_bb
, label_bb
);
236 if (CASE_LOW (cs
) == NULL_TREE
)
238 /* Default branch. */
239 info
.default_prob
= e
->probability
;
240 info
.default_count
= e
->count
;
245 info
.other_count
+= e
->count
;
246 for (i
= 0; i
< 2; i
++)
247 if (info
.bit_test_bb
[i
] == label_bb
)
249 else if (info
.bit_test_bb
[i
] == NULL
)
251 info
.bit_test_bb
[i
] = label_bb
;
252 info
.bit_test_uniq
++;
256 info
.bit_test_uniq
= 3;
257 if (CASE_HIGH (cs
) != NULL_TREE
258 && ! tree_int_cst_equal (CASE_LOW (cs
), CASE_HIGH (cs
)))
259 info
.bit_test_count
+= 2;
261 info
.bit_test_count
++;
266 info
.reason
= " Bad case - cs BB label is NULL\n";
270 if (!single_pred_p (label_bb
))
272 if (info
.final_bb
&& info
.final_bb
!= label_bb
)
274 info
.reason
= " Bad case - a non-final BB has two predecessors\n";
275 return false; /* sth complex going on in this branch */
278 following_bb
= label_bb
;
282 if (!empty_block_p (label_bb
))
284 info
.reason
= " Bad case - a non-final BB not empty\n";
288 e
= single_succ_edge (label_bb
);
289 following_bb
= single_succ (label_bb
);
293 info
.final_bb
= following_bb
;
294 else if (info
.final_bb
!= following_bb
)
296 info
.reason
= " Bad case - different final BB\n";
297 return false; /* the only successor is not common for all the branches */
303 /* This function checks whether all required values in phi nodes in final_bb
304 are constants. Required values are those that correspond to a basic block
305 which is a part of the examined switch statement. It returns true if the
306 phi nodes are OK, otherwise false. */
309 check_final_bb (void)
311 gimple_stmt_iterator gsi
;
314 for (gsi
= gsi_start_phis (info
.final_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
316 gimple phi
= gsi_stmt (gsi
);
321 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
323 basic_block bb
= gimple_phi_arg_edge (phi
, i
)->src
;
325 if (bb
== info
.switch_bb
326 || (single_pred_p (bb
) && single_pred (bb
) == info
.switch_bb
))
330 val
= gimple_phi_arg_def (phi
, i
);
331 if (!is_gimple_ip_invariant (val
))
333 info
.reason
= " Non-invariant value from a case\n";
334 return false; /* Non-invariant argument. */
336 reloc
= initializer_constant_valid_p (val
, TREE_TYPE (val
));
337 if ((flag_pic
&& reloc
!= null_pointer_node
)
338 || (!flag_pic
&& reloc
== NULL_TREE
))
342 = " Value from a case would need runtime relocations\n";
345 = " Value from a case is not a valid initializer\n";
355 /* The following function allocates default_values, target_{in,out}_names and
356 constructors arrays. The last one is also populated with pointers to
357 vectors that will become constructors of new arrays. */
360 create_temp_arrays (void)
364 info
.default_values
= XCNEWVEC (tree
, info
.phi_count
* 3);
365 info
.constructors
= XCNEWVEC (VEC (constructor_elt
, gc
) *, info
.phi_count
);
366 info
.target_inbound_names
= info
.default_values
+ info
.phi_count
;
367 info
.target_outbound_names
= info
.target_inbound_names
+ info
.phi_count
;
368 for (i
= 0; i
< info
.phi_count
; i
++)
370 = VEC_alloc (constructor_elt
, gc
, tree_low_cst (info
.range_size
, 1) + 1);
373 /* Free the arrays created by create_temp_arrays(). The vectors that are
374 created by that function are not freed here, however, because they have
375 already become constructors and must be preserved. */
378 free_temp_arrays (void)
380 XDELETEVEC (info
.constructors
);
381 XDELETEVEC (info
.default_values
);
384 /* Populate the array of default values in the order of phi nodes.
385 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch. */
388 gather_default_values (tree default_case
)
390 gimple_stmt_iterator gsi
;
391 basic_block bb
= label_to_block (CASE_LABEL (default_case
));
395 gcc_assert (CASE_LOW (default_case
) == NULL_TREE
);
397 if (bb
== info
.final_bb
)
398 e
= find_edge (info
.switch_bb
, bb
);
400 e
= single_succ_edge (bb
);
402 for (gsi
= gsi_start_phis (info
.final_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
404 gimple phi
= gsi_stmt (gsi
);
405 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
407 info
.default_values
[i
++] = val
;
411 /* The following function populates the vectors in the constructors array with
412 future contents of the static arrays. The vectors are populated in the
413 order of phi nodes. SWTCH is the switch statement being converted. */
416 build_constructors (gimple swtch
)
418 unsigned i
, branch_num
= gimple_switch_num_labels (swtch
);
419 tree pos
= info
.range_min
;
421 for (i
= 1; i
< branch_num
; i
++)
423 tree cs
= gimple_switch_label (swtch
, i
);
424 basic_block bb
= label_to_block (CASE_LABEL (cs
));
427 gimple_stmt_iterator gsi
;
430 if (bb
== info
.final_bb
)
431 e
= find_edge (info
.switch_bb
, bb
);
433 e
= single_succ_edge (bb
);
436 while (tree_int_cst_lt (pos
, CASE_LOW (cs
)))
439 for (k
= 0; k
< info
.phi_count
; k
++)
441 constructor_elt
*elt
;
443 elt
= VEC_quick_push (constructor_elt
,
444 info
.constructors
[k
], NULL
);
445 elt
->index
= int_const_binop (MINUS_EXPR
, pos
,
447 elt
->value
= info
.default_values
[k
];
450 pos
= int_const_binop (PLUS_EXPR
, pos
, integer_one_node
, 0);
452 gcc_assert (tree_int_cst_equal (pos
, CASE_LOW (cs
)));
456 high
= CASE_HIGH (cs
);
458 high
= CASE_LOW (cs
);
459 for (gsi
= gsi_start_phis (info
.final_bb
);
460 !gsi_end_p (gsi
); gsi_next (&gsi
))
462 gimple phi
= gsi_stmt (gsi
);
463 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
464 tree low
= CASE_LOW (cs
);
469 constructor_elt
*elt
;
471 elt
= VEC_quick_push (constructor_elt
,
472 info
.constructors
[j
], NULL
);
473 elt
->index
= int_const_binop (MINUS_EXPR
, pos
, info
.range_min
, 0);
476 pos
= int_const_binop (PLUS_EXPR
, pos
, integer_one_node
, 0);
477 } while (!tree_int_cst_lt (high
, pos
)
478 && tree_int_cst_lt (low
, pos
));
484 /* If all values in the constructor vector are the same, return the value.
485 Otherwise return NULL_TREE. Not supposed to be called for empty
489 constructor_contains_same_values_p (VEC (constructor_elt
, gc
) *vec
)
492 tree prev
= NULL_TREE
;
493 constructor_elt
*elt
;
495 FOR_EACH_VEC_ELT (constructor_elt
, vec
, i
, elt
)
499 else if (!operand_equal_p (elt
->value
, prev
, OEP_ONLY_CONST
))
505 /* Return type which should be used for array elements, either TYPE,
506 or for integral type some smaller integral type that can still hold
507 all the constants. */
510 array_value_type (gimple swtch
, tree type
, int num
)
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
,
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
);
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 add_referenced_var (decl
);
633 varpool_mark_needed_node (varpool_node (decl
));
634 varpool_finalize_decl (decl
);
636 fetch
= build4 (ARRAY_REF
, value_type
, decl
, tidx
, NULL_TREE
,
638 if (default_type
!= value_type
)
640 fetch
= fold_convert (default_type
, fetch
);
641 fetch
= force_gimple_operand_gsi (&gsi
, fetch
, true, NULL_TREE
,
642 true, GSI_SAME_STMT
);
644 load
= gimple_build_assign (name
, fetch
);
647 SSA_NAME_DEF_STMT (name
) = load
;
648 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
650 info
.arr_ref_last
= load
;
653 /* Builds and initializes static arrays initialized with values gathered from
654 the SWTCH switch statement. Also creates statements that load values from
658 build_arrays (gimple swtch
)
663 gimple_stmt_iterator gsi
;
665 location_t loc
= gimple_location (swtch
);
667 gsi
= gsi_for_stmt (swtch
);
669 arr_index_type
= build_index_type (info
.range_size
);
670 tmp
= create_tmp_var (TREE_TYPE (info
.index_expr
), "csti");
671 add_referenced_var (tmp
);
672 tidx
= make_ssa_name (tmp
, NULL
);
673 sub
= fold_build2_loc (loc
, MINUS_EXPR
,
674 TREE_TYPE (info
.index_expr
), info
.index_expr
,
675 fold_convert_loc (loc
, TREE_TYPE (info
.index_expr
),
677 sub
= force_gimple_operand_gsi (&gsi
, sub
,
678 false, NULL
, true, GSI_SAME_STMT
);
679 stmt
= gimple_build_assign (tidx
, sub
);
680 SSA_NAME_DEF_STMT (tidx
) = stmt
;
682 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
684 info
.arr_ref_first
= stmt
;
686 for (gsi
= gsi_start_phis (info
.final_bb
), i
= 0;
687 !gsi_end_p (gsi
); gsi_next (&gsi
), i
++)
688 build_one_array (swtch
, i
, arr_index_type
, gsi_stmt (gsi
), tidx
);
691 /* Generates and appropriately inserts loads of default values at the position
692 given by BSI. Returns the last inserted statement. */
695 gen_def_assigns (gimple_stmt_iterator
*gsi
)
698 gimple assign
= NULL
;
700 for (i
= 0; i
< info
.phi_count
; i
++)
703 = make_ssa_name (SSA_NAME_VAR (info
.target_inbound_names
[i
]), NULL
);
705 info
.target_outbound_names
[i
] = name
;
706 assign
= gimple_build_assign (name
, info
.default_values
[i
]);
707 SSA_NAME_DEF_STMT (name
) = assign
;
708 gsi_insert_before (gsi
, assign
, GSI_SAME_STMT
);
709 update_stmt (assign
);
714 /* Deletes the unused bbs and edges that now contain the switch statement and
715 its empty branch bbs. BBD is the now dead BB containing the original switch
716 statement, FINAL is the last BB of the converted switch statement (in terms
720 prune_bbs (basic_block bbd
, basic_block final
)
725 for (ei
= ei_start (bbd
->succs
); (e
= ei_safe_edge (ei
)); )
731 delete_basic_block (bb
);
733 delete_basic_block (bbd
);
736 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
737 from the basic block loading values from an array and E2F from the basic
738 block loading default values. BBF is the last switch basic block (see the
739 bbf description in the comment below). */
742 fix_phi_nodes (edge e1f
, edge e2f
, basic_block bbf
)
744 gimple_stmt_iterator gsi
;
747 for (gsi
= gsi_start_phis (bbf
), i
= 0;
748 !gsi_end_p (gsi
); gsi_next (&gsi
), i
++)
750 gimple phi
= gsi_stmt (gsi
);
751 add_phi_arg (phi
, info
.target_inbound_names
[i
], e1f
, UNKNOWN_LOCATION
);
752 add_phi_arg (phi
, info
.target_outbound_names
[i
], e2f
, UNKNOWN_LOCATION
);
757 /* Creates a check whether the switch expression value actually falls into the
758 range given by all the cases. If it does not, the temporaries are loaded
759 with default values instead. SWTCH is the switch statement being converted.
761 bb0 is the bb with the switch statement, however, we'll end it with a
764 bb1 is the bb to be used when the range check went ok. It is derived from
767 bb2 is the bb taken when the expression evaluated outside of the range
768 covered by the created arrays. It is populated by loads of default
771 bbF is a fall through for both bb1 and bb2 and contains exactly what
772 originally followed the switch statement.
774 bbD contains the switch statement (in the end). It is unreachable but we
775 still need to strip off its edges.
779 gen_inbound_check (gimple swtch
)
781 tree label_decl1
= create_artificial_label (UNKNOWN_LOCATION
);
782 tree label_decl2
= create_artificial_label (UNKNOWN_LOCATION
);
783 tree label_decl3
= create_artificial_label (UNKNOWN_LOCATION
);
784 gimple label1
, label2
, label3
;
787 tree tmp_u_1
, tmp_u_2
, tmp_u_var
;
789 gimple cast_assign
, minus_assign
;
796 gimple_stmt_iterator gsi
;
797 basic_block bb0
, bb1
, bb2
, bbf
, bbd
;
798 edge e01
, e02
, e21
, e1d
, e1f
, e2f
;
799 location_t loc
= gimple_location (swtch
);
801 gcc_assert (info
.default_values
);
802 bb0
= gimple_bb (swtch
);
804 /* Make sure we do not generate arithmetics in a subrange. */
805 if (TREE_TYPE (TREE_TYPE (info
.index_expr
)))
806 utype
= lang_hooks
.types
.type_for_mode
807 (TYPE_MODE (TREE_TYPE (TREE_TYPE (info
.index_expr
))), 1);
809 utype
= lang_hooks
.types
.type_for_mode
810 (TYPE_MODE (TREE_TYPE (info
.index_expr
)), 1);
812 /* (end of) block 0 */
813 gsi
= gsi_for_stmt (info
.arr_ref_first
);
814 tmp_u_var
= create_tmp_var (utype
, "csui");
815 add_referenced_var (tmp_u_var
);
816 tmp_u_1
= make_ssa_name (tmp_u_var
, NULL
);
818 cast
= fold_convert_loc (loc
, utype
, info
.index_expr
);
819 cast_assign
= gimple_build_assign (tmp_u_1
, cast
);
820 SSA_NAME_DEF_STMT (tmp_u_1
) = cast_assign
;
821 gsi_insert_before (&gsi
, cast_assign
, GSI_SAME_STMT
);
822 update_stmt (cast_assign
);
824 ulb
= fold_convert_loc (loc
, utype
, info
.range_min
);
825 minus
= fold_build2_loc (loc
, MINUS_EXPR
, utype
, tmp_u_1
, ulb
);
826 minus
= force_gimple_operand_gsi (&gsi
, minus
, false, NULL
, true,
828 tmp_u_2
= make_ssa_name (tmp_u_var
, NULL
);
829 minus_assign
= gimple_build_assign (tmp_u_2
, minus
);
830 SSA_NAME_DEF_STMT (tmp_u_2
) = minus_assign
;
831 gsi_insert_before (&gsi
, minus_assign
, GSI_SAME_STMT
);
832 update_stmt (minus_assign
);
834 bound
= fold_convert_loc (loc
, utype
, info
.range_size
);
835 cond_stmt
= gimple_build_cond (LE_EXPR
, tmp_u_2
, bound
, NULL_TREE
, NULL_TREE
);
836 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
837 update_stmt (cond_stmt
);
840 gsi
= gsi_for_stmt (info
.arr_ref_first
);
841 label2
= gimple_build_label (label_decl2
);
842 gsi_insert_before (&gsi
, label2
, GSI_SAME_STMT
);
843 last_assign
= gen_def_assigns (&gsi
);
846 gsi
= gsi_for_stmt (info
.arr_ref_first
);
847 label1
= gimple_build_label (label_decl1
);
848 gsi_insert_before (&gsi
, label1
, GSI_SAME_STMT
);
851 gsi
= gsi_start_bb (info
.final_bb
);
852 label3
= gimple_build_label (label_decl3
);
853 gsi_insert_before (&gsi
, label3
, GSI_SAME_STMT
);
856 e02
= split_block (bb0
, cond_stmt
);
859 e21
= split_block (bb2
, last_assign
);
863 e1d
= split_block (bb1
, info
.arr_ref_last
);
867 /* flags and profiles of the edge for in-range values */
868 e01
= make_edge (bb0
, bb1
, EDGE_TRUE_VALUE
);
869 e01
->probability
= REG_BR_PROB_BASE
- info
.default_prob
;
870 e01
->count
= info
.other_count
;
872 /* flags and profiles of the edge taking care of out-of-range values */
873 e02
->flags
&= ~EDGE_FALLTHRU
;
874 e02
->flags
|= EDGE_FALSE_VALUE
;
875 e02
->probability
= info
.default_prob
;
876 e02
->count
= info
.default_count
;
880 e1f
= make_edge (bb1
, bbf
, EDGE_FALLTHRU
);
881 e1f
->probability
= REG_BR_PROB_BASE
;
882 e1f
->count
= info
.other_count
;
884 e2f
= make_edge (bb2
, bbf
, EDGE_FALLTHRU
);
885 e2f
->probability
= REG_BR_PROB_BASE
;
886 e2f
->count
= info
.default_count
;
888 /* frequencies of the new BBs */
889 bb1
->frequency
= EDGE_FREQUENCY (e01
);
890 bb2
->frequency
= EDGE_FREQUENCY (e02
);
891 bbf
->frequency
= EDGE_FREQUENCY (e1f
) + EDGE_FREQUENCY (e2f
);
893 prune_bbs (bbd
, info
.final_bb
); /* To keep calc_dfs_tree() in dominance.c
896 fix_phi_nodes (e1f
, e2f
, bbf
);
898 free_dominance_info (CDI_DOMINATORS
);
899 free_dominance_info (CDI_POST_DOMINATORS
);
902 /* The following function is invoked on every switch statement (the current one
903 is given in SWTCH) and runs the individual phases of switch conversion on it
904 one after another until one fails or the conversion is completed. */
907 process_switch (gimple swtch
)
909 unsigned int i
, branch_num
= gimple_switch_num_labels (swtch
);
912 /* Operand 2 is either NULL_TREE or a vector of cases (stmt.c). */
915 info
.reason
= "switch has no labels\n";
919 info
.final_bb
= NULL
;
920 info
.switch_bb
= gimple_bb (swtch
);
921 info
.index_expr
= gimple_switch_index (swtch
);
922 index_type
= TREE_TYPE (info
.index_expr
);
923 info
.arr_ref_first
= NULL
;
924 info
.arr_ref_last
= NULL
;
925 info
.default_prob
= 0;
926 info
.default_count
= 0;
927 info
.other_count
= 0;
928 info
.bit_test_uniq
= 0;
929 info
.bit_test_count
= 0;
930 info
.bit_test_bb
[0] = NULL
;
931 info
.bit_test_bb
[1] = NULL
;
933 /* An ERROR_MARK occurs for various reasons including invalid data type.
934 (comment from stmt.c) */
935 if (index_type
== error_mark_node
)
937 info
.reason
= "index error.\n";
941 /* Check the case label values are within reasonable range: */
942 if (!check_range (swtch
))
945 /* For all the cases, see whether they are empty, the assignments they
946 represent constant and so on... */
947 for (i
= 0; i
< branch_num
; i
++)
948 if (!check_process_case (gimple_switch_label (swtch
, i
)))
951 fprintf (dump_file
, "Processing of case %i failed\n", i
);
955 if (info
.bit_test_uniq
<= 2)
957 rtl_profile_for_bb (gimple_bb (swtch
));
958 if (expand_switch_using_bit_tests_p (gimple_switch_index (swtch
),
959 info
.range_size
, info
.bit_test_uniq
,
960 info
.bit_test_count
))
962 info
.reason
= " Expanding as bit test is preferable\n";
967 if (!check_final_bb ())
970 /* At this point all checks have passed and we can proceed with the
973 create_temp_arrays ();
974 gather_default_values (gimple_switch_label (swtch
, 0));
975 build_constructors (swtch
);
977 build_arrays (swtch
); /* Build the static arrays and assignments. */
978 gen_inbound_check (swtch
); /* Build the bounds check. */
985 /* The main function of the pass scans statements for switches and invokes
986 process_switch on them. */
995 gimple stmt
= last_stmt (bb
);
996 if (stmt
&& gimple_code (stmt
) == GIMPLE_SWITCH
)
1000 expanded_location loc
= expand_location (gimple_location (stmt
));
1002 fprintf (dump_file
, "beginning to process the following "
1003 "SWITCH statement (%s:%d) : ------- \n",
1004 loc
.file
, loc
.line
);
1005 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1006 putc ('\n', dump_file
);
1010 if (process_switch (stmt
))
1014 fputs ("Switch converted\n", dump_file
);
1015 fputs ("--------------------------------\n", dump_file
);
1022 gcc_assert (info
.reason
);
1023 fputs ("Bailing out - ", dump_file
);
1024 fputs (info
.reason
, dump_file
);
1025 fputs ("--------------------------------\n", dump_file
);
1034 /* The pass gate. */
1037 switchconv_gate (void)
1039 return flag_tree_switch_conversion
!= 0;
1042 struct gimple_opt_pass pass_convert_switch
=
1046 "switchconv", /* name */
1047 switchconv_gate
, /* gate */
1048 do_switchconv
, /* execute */
1051 0, /* static_pass_number */
1052 TV_TREE_SWITCH_CONVERSION
, /* tv_id */
1053 PROP_cfg
| PROP_ssa
, /* properties_required */
1054 0, /* properties_provided */
1055 0, /* properties_destroyed */
1056 0, /* todo_flags_start */
1057 TODO_update_ssa
| TODO_dump_func
1058 | TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */