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:
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 /* Checks whether the range given by individual case statements of the SWTCH
166 switch statement isn't too big and whether the number of branches actually
167 satisfies the size of the new array. */
170 check_range (gimple swtch
, struct switch_conv_info
*info
)
172 tree min_case
, max_case
;
173 unsigned int branch_num
= gimple_switch_num_labels (swtch
);
176 /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
177 is a default label which is the first in the vector. */
179 min_case
= gimple_switch_label (swtch
, 1);
180 info
->range_min
= CASE_LOW (min_case
);
182 gcc_assert (branch_num
> 1);
183 gcc_assert (CASE_LOW (gimple_switch_label (swtch
, 0)) == NULL_TREE
);
184 max_case
= gimple_switch_label (swtch
, branch_num
- 1);
185 if (CASE_HIGH (max_case
) != NULL_TREE
)
186 range_max
= CASE_HIGH (max_case
);
188 range_max
= CASE_LOW (max_case
);
190 gcc_assert (info
->range_min
);
191 gcc_assert (range_max
);
193 info
->range_size
= int_const_binop (MINUS_EXPR
, range_max
, info
->range_min
);
195 gcc_assert (info
->range_size
);
196 if (!host_integerp (info
->range_size
, 1))
198 info
->reason
= "index range way too large or otherwise unusable";
202 if ((unsigned HOST_WIDE_INT
) tree_low_cst (info
->range_size
, 1)
203 > ((unsigned) branch_num
* SWITCH_CONVERSION_BRANCH_RATIO
))
205 info
->reason
= "the maximum range-branch ratio exceeded";
212 /* Checks the given CS switch case whether it is suitable for conversion
213 (whether all but the default basic blocks are empty and so on). If it is,
214 adds the case to the branch list along with values for the defined variables
215 and returns true. Otherwise returns false. */
218 check_process_case (tree cs
, struct switch_conv_info
*info
)
221 basic_block label_bb
, following_bb
;
224 ldecl
= CASE_LABEL (cs
);
225 label_bb
= label_to_block (ldecl
);
227 e
= find_edge (info
->switch_bb
, label_bb
);
230 if (CASE_LOW (cs
) == NULL_TREE
)
232 /* Default branch. */
233 info
->default_prob
= e
->probability
;
234 info
->default_count
= e
->count
;
239 info
->other_count
+= e
->count
;
240 for (i
= 0; i
< 2; i
++)
241 if (info
->bit_test_bb
[i
] == label_bb
)
243 else if (info
->bit_test_bb
[i
] == NULL
)
245 info
->bit_test_bb
[i
] = label_bb
;
246 info
->bit_test_uniq
++;
250 info
->bit_test_uniq
= 3;
251 if (CASE_HIGH (cs
) != NULL_TREE
252 && ! tree_int_cst_equal (CASE_LOW (cs
), CASE_HIGH (cs
)))
253 info
->bit_test_count
+= 2;
255 info
->bit_test_count
++;
260 info
->reason
= "bad case - cs BB label is NULL";
264 if (!single_pred_p (label_bb
))
266 if (info
->final_bb
&& info
->final_bb
!= label_bb
)
268 info
->reason
= "bad case - a non-final BB has two predecessors";
269 return false; /* sth complex going on in this branch */
272 following_bb
= label_bb
;
276 if (!empty_block_p (label_bb
))
278 info
->reason
= "bad case - a non-final BB not empty";
282 e
= single_succ_edge (label_bb
);
283 following_bb
= single_succ (label_bb
);
287 info
->final_bb
= following_bb
;
288 else if (info
->final_bb
!= following_bb
)
290 info
->reason
= "bad case - different final BB";
291 return false; /* the only successor is not common for all the branches */
297 /* This function checks whether all required values in phi nodes in final_bb
298 are constants. Required values are those that correspond to a basic block
299 which is a part of the examined switch statement. It returns true if the
300 phi nodes are OK, otherwise false. */
303 check_final_bb (struct switch_conv_info
*info
)
305 gimple_stmt_iterator gsi
;
308 for (gsi
= gsi_start_phis (info
->final_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
310 gimple phi
= gsi_stmt (gsi
);
315 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
317 basic_block bb
= gimple_phi_arg_edge (phi
, i
)->src
;
319 if (bb
== info
->switch_bb
320 || (single_pred_p (bb
) && single_pred (bb
) == info
->switch_bb
))
324 val
= gimple_phi_arg_def (phi
, i
);
325 if (!is_gimple_ip_invariant (val
))
327 info
->reason
= "non-invariant value from a case";
328 return false; /* Non-invariant argument. */
330 reloc
= initializer_constant_valid_p (val
, TREE_TYPE (val
));
331 if ((flag_pic
&& reloc
!= null_pointer_node
)
332 || (!flag_pic
&& reloc
== NULL_TREE
))
336 = "value from a case would need runtime relocations";
339 = "value from a case is not a valid initializer";
349 /* The following function allocates default_values, target_{in,out}_names and
350 constructors arrays. The last one is also populated with pointers to
351 vectors that will become constructors of new arrays. */
354 create_temp_arrays (struct switch_conv_info
*info
)
358 info
->default_values
= XCNEWVEC (tree
, info
->phi_count
* 3);
359 info
->constructors
= XCNEWVEC (VEC (constructor_elt
, gc
) *, info
->phi_count
);
360 info
->target_inbound_names
= info
->default_values
+ info
->phi_count
;
361 info
->target_outbound_names
= info
->target_inbound_names
+ info
->phi_count
;
362 for (i
= 0; i
< info
->phi_count
; i
++)
363 info
->constructors
[i
]
364 = VEC_alloc (constructor_elt
, gc
, tree_low_cst (info
->range_size
, 1) + 1);
367 /* Free the arrays created by create_temp_arrays(). The vectors that are
368 created by that function are not freed here, however, because they have
369 already become constructors and must be preserved. */
372 free_temp_arrays (struct switch_conv_info
*info
)
374 XDELETEVEC (info
->constructors
);
375 XDELETEVEC (info
->default_values
);
378 /* Populate the array of default values in the order of phi nodes.
379 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch. */
382 gather_default_values (tree default_case
, struct switch_conv_info
*info
)
384 gimple_stmt_iterator gsi
;
385 basic_block bb
= label_to_block (CASE_LABEL (default_case
));
389 gcc_assert (CASE_LOW (default_case
) == NULL_TREE
);
391 if (bb
== info
->final_bb
)
392 e
= find_edge (info
->switch_bb
, bb
);
394 e
= single_succ_edge (bb
);
396 for (gsi
= gsi_start_phis (info
->final_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
398 gimple phi
= gsi_stmt (gsi
);
399 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
401 info
->default_values
[i
++] = val
;
405 /* The following function populates the vectors in the constructors array with
406 future contents of the static arrays. The vectors are populated in the
407 order of phi nodes. SWTCH is the switch statement being converted. */
410 build_constructors (gimple swtch
, struct switch_conv_info
*info
)
412 unsigned i
, branch_num
= gimple_switch_num_labels (swtch
);
413 tree pos
= info
->range_min
;
415 for (i
= 1; i
< branch_num
; i
++)
417 tree cs
= gimple_switch_label (swtch
, i
);
418 basic_block bb
= label_to_block (CASE_LABEL (cs
));
421 gimple_stmt_iterator gsi
;
424 if (bb
== info
->final_bb
)
425 e
= find_edge (info
->switch_bb
, bb
);
427 e
= single_succ_edge (bb
);
430 while (tree_int_cst_lt (pos
, CASE_LOW (cs
)))
433 for (k
= 0; k
< info
->phi_count
; k
++)
435 constructor_elt
*elt
;
437 elt
= VEC_quick_push (constructor_elt
,
438 info
->constructors
[k
], NULL
);
439 elt
->index
= int_const_binop (MINUS_EXPR
, pos
,
441 elt
->value
= info
->default_values
[k
];
444 pos
= int_const_binop (PLUS_EXPR
, pos
, integer_one_node
);
446 gcc_assert (tree_int_cst_equal (pos
, CASE_LOW (cs
)));
450 high
= CASE_HIGH (cs
);
452 high
= CASE_LOW (cs
);
453 for (gsi
= gsi_start_phis (info
->final_bb
);
454 !gsi_end_p (gsi
); gsi_next (&gsi
))
456 gimple phi
= gsi_stmt (gsi
);
457 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
458 tree low
= CASE_LOW (cs
);
463 constructor_elt
*elt
;
465 elt
= VEC_quick_push (constructor_elt
,
466 info
->constructors
[j
], NULL
);
467 elt
->index
= int_const_binop (MINUS_EXPR
, pos
, info
->range_min
);
470 pos
= int_const_binop (PLUS_EXPR
, pos
, integer_one_node
);
471 } while (!tree_int_cst_lt (high
, pos
)
472 && tree_int_cst_lt (low
, pos
));
478 /* If all values in the constructor vector are the same, return the value.
479 Otherwise return NULL_TREE. Not supposed to be called for empty
483 constructor_contains_same_values_p (VEC (constructor_elt
, gc
) *vec
)
486 tree prev
= NULL_TREE
;
487 constructor_elt
*elt
;
489 FOR_EACH_VEC_ELT (constructor_elt
, vec
, i
, elt
)
493 else if (!operand_equal_p (elt
->value
, prev
, OEP_ONLY_CONST
))
499 /* Return type which should be used for array elements, either TYPE,
500 or for integral type some smaller integral type that can still hold
501 all the constants. */
504 array_value_type (gimple swtch
, tree type
, int num
,
505 struct switch_conv_info
*info
)
507 unsigned int i
, len
= VEC_length (constructor_elt
, info
->constructors
[num
]);
508 constructor_elt
*elt
;
509 enum machine_mode mode
;
513 if (!INTEGRAL_TYPE_P (type
))
516 mode
= GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type
)));
517 if (GET_MODE_SIZE (TYPE_MODE (type
)) <= GET_MODE_SIZE (mode
))
520 if (len
< (optimize_bb_for_size_p (gimple_bb (swtch
)) ? 2 : 32))
523 FOR_EACH_VEC_ELT (constructor_elt
, info
->constructors
[num
], i
, elt
)
527 if (TREE_CODE (elt
->value
) != INTEGER_CST
)
530 cst
= TREE_INT_CST (elt
->value
);
533 unsigned int prec
= GET_MODE_BITSIZE (mode
);
534 if (prec
> HOST_BITS_PER_WIDE_INT
)
538 && double_int_equal_p (cst
, double_int_zext (cst
, prec
)))
541 && double_int_equal_p (cst
, double_int_sext (cst
, prec
)))
547 && double_int_equal_p (cst
, double_int_sext (cst
, prec
)))
556 mode
= GET_MODE_WIDER_MODE (mode
);
558 || GET_MODE_SIZE (mode
) >= GET_MODE_SIZE (TYPE_MODE (type
)))
564 sign
= TYPE_UNSIGNED (type
) ? 1 : -1;
565 smaller_type
= lang_hooks
.types
.type_for_mode (mode
, sign
>= 0);
566 if (GET_MODE_SIZE (TYPE_MODE (type
))
567 <= GET_MODE_SIZE (TYPE_MODE (smaller_type
)))
573 /* Create an appropriate array type and declaration and assemble a static array
574 variable. Also create a load statement that initializes the variable in
575 question with a value from the static array. SWTCH is the switch statement
576 being converted, NUM is the index to arrays of constructors, default values
577 and target SSA names for this particular array. ARR_INDEX_TYPE is the type
578 of the index of the new array, PHI is the phi node of the final BB that
579 corresponds to the value that will be loaded from the created array. TIDX
580 is an ssa name of a temporary variable holding the index for loads from the
584 build_one_array (gimple swtch
, int num
, tree arr_index_type
, gimple phi
,
585 tree tidx
, struct switch_conv_info
*info
)
589 gimple_stmt_iterator gsi
= gsi_for_stmt (swtch
);
590 location_t loc
= gimple_location (swtch
);
592 gcc_assert (info
->default_values
[num
]);
594 name
= make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi
)), NULL
);
595 info
->target_inbound_names
[num
] = name
;
597 cst
= constructor_contains_same_values_p (info
->constructors
[num
]);
599 load
= gimple_build_assign (name
, cst
);
602 tree array_type
, ctor
, decl
, value_type
, fetch
, default_type
;
604 default_type
= TREE_TYPE (info
->default_values
[num
]);
605 value_type
= array_value_type (swtch
, default_type
, num
, info
);
606 array_type
= build_array_type (value_type
, arr_index_type
);
607 if (default_type
!= value_type
)
610 constructor_elt
*elt
;
612 FOR_EACH_VEC_ELT (constructor_elt
, info
->constructors
[num
], i
, elt
)
613 elt
->value
= fold_convert (value_type
, elt
->value
);
615 ctor
= build_constructor (array_type
, info
->constructors
[num
]);
616 TREE_CONSTANT (ctor
) = true;
617 TREE_STATIC (ctor
) = true;
619 decl
= build_decl (loc
, VAR_DECL
, NULL_TREE
, array_type
);
620 TREE_STATIC (decl
) = 1;
621 DECL_INITIAL (decl
) = ctor
;
623 DECL_NAME (decl
) = create_tmp_var_name ("CSWTCH");
624 DECL_ARTIFICIAL (decl
) = 1;
625 TREE_CONSTANT (decl
) = 1;
626 TREE_READONLY (decl
) = 1;
627 add_referenced_var (decl
);
628 varpool_finalize_decl (decl
);
630 fetch
= build4 (ARRAY_REF
, value_type
, decl
, tidx
, NULL_TREE
,
632 if (default_type
!= value_type
)
634 fetch
= fold_convert (default_type
, fetch
);
635 fetch
= force_gimple_operand_gsi (&gsi
, fetch
, true, NULL_TREE
,
636 true, GSI_SAME_STMT
);
638 load
= gimple_build_assign (name
, fetch
);
641 SSA_NAME_DEF_STMT (name
) = load
;
642 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
644 info
->arr_ref_last
= load
;
647 /* Builds and initializes static arrays initialized with values gathered from
648 the SWTCH switch statement. Also creates statements that load values from
652 build_arrays (gimple swtch
, struct switch_conv_info
*info
)
655 tree tidx
, sub
, tmp
, utype
;
657 gimple_stmt_iterator gsi
;
659 location_t loc
= gimple_location (swtch
);
661 gsi
= gsi_for_stmt (swtch
);
663 /* Make sure we do not generate arithmetics in a subrange. */
664 utype
= TREE_TYPE (info
->index_expr
);
665 if (TREE_TYPE (utype
))
666 utype
= lang_hooks
.types
.type_for_mode (TYPE_MODE (TREE_TYPE (utype
)), 1);
668 utype
= lang_hooks
.types
.type_for_mode (TYPE_MODE (utype
), 1);
670 arr_index_type
= build_index_type (info
->range_size
);
671 tmp
= create_tmp_var (utype
, "csui");
672 add_referenced_var (tmp
);
673 tidx
= make_ssa_name (tmp
, NULL
);
674 sub
= fold_build2_loc (loc
, MINUS_EXPR
, utype
,
675 fold_convert_loc (loc
, utype
, info
->index_expr
),
676 fold_convert_loc (loc
, utype
, info
->range_min
));
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
, info
);
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
, struct switch_conv_info
*info
)
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
,
743 struct switch_conv_info
*info
)
745 gimple_stmt_iterator gsi
;
748 for (gsi
= gsi_start_phis (bbf
), i
= 0;
749 !gsi_end_p (gsi
); gsi_next (&gsi
), i
++)
751 gimple phi
= gsi_stmt (gsi
);
752 add_phi_arg (phi
, info
->target_inbound_names
[i
], e1f
, UNKNOWN_LOCATION
);
753 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
, struct switch_conv_info
*info
)
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
;
791 gimple_stmt_iterator gsi
;
792 basic_block bb0
, bb1
, bb2
, bbf
, bbd
;
793 edge e01
, e02
, e21
, e1d
, e1f
, e2f
;
794 location_t loc
= gimple_location (swtch
);
796 gcc_assert (info
->default_values
);
797 bb0
= gimple_bb (swtch
);
799 tidx
= gimple_assign_lhs (info
->arr_ref_first
);
800 utype
= TREE_TYPE (tidx
);
802 /* (end of) block 0 */
803 gsi
= gsi_for_stmt (info
->arr_ref_first
);
806 bound
= fold_convert_loc (loc
, utype
, info
->range_size
);
807 cond_stmt
= gimple_build_cond (LE_EXPR
, tidx
, bound
, NULL_TREE
, NULL_TREE
);
808 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
809 update_stmt (cond_stmt
);
812 label2
= gimple_build_label (label_decl2
);
813 gsi_insert_before (&gsi
, label2
, GSI_SAME_STMT
);
814 last_assign
= gen_def_assigns (&gsi
, info
);
817 label1
= gimple_build_label (label_decl1
);
818 gsi_insert_before (&gsi
, label1
, GSI_SAME_STMT
);
821 gsi
= gsi_start_bb (info
->final_bb
);
822 label3
= gimple_build_label (label_decl3
);
823 gsi_insert_before (&gsi
, label3
, GSI_SAME_STMT
);
826 e02
= split_block (bb0
, cond_stmt
);
829 e21
= split_block (bb2
, last_assign
);
833 e1d
= split_block (bb1
, info
->arr_ref_last
);
837 /* flags and profiles of the edge for in-range values */
838 e01
= make_edge (bb0
, bb1
, EDGE_TRUE_VALUE
);
839 e01
->probability
= REG_BR_PROB_BASE
- info
->default_prob
;
840 e01
->count
= info
->other_count
;
842 /* flags and profiles of the edge taking care of out-of-range values */
843 e02
->flags
&= ~EDGE_FALLTHRU
;
844 e02
->flags
|= EDGE_FALSE_VALUE
;
845 e02
->probability
= info
->default_prob
;
846 e02
->count
= info
->default_count
;
848 bbf
= info
->final_bb
;
850 e1f
= make_edge (bb1
, bbf
, EDGE_FALLTHRU
);
851 e1f
->probability
= REG_BR_PROB_BASE
;
852 e1f
->count
= info
->other_count
;
854 e2f
= make_edge (bb2
, bbf
, EDGE_FALLTHRU
);
855 e2f
->probability
= REG_BR_PROB_BASE
;
856 e2f
->count
= info
->default_count
;
858 /* frequencies of the new BBs */
859 bb1
->frequency
= EDGE_FREQUENCY (e01
);
860 bb2
->frequency
= EDGE_FREQUENCY (e02
);
861 bbf
->frequency
= EDGE_FREQUENCY (e1f
) + EDGE_FREQUENCY (e2f
);
863 prune_bbs (bbd
, info
->final_bb
); /* To keep calc_dfs_tree() in dominance.c
866 fix_phi_nodes (e1f
, e2f
, bbf
, info
);
868 free_dominance_info (CDI_DOMINATORS
);
869 free_dominance_info (CDI_POST_DOMINATORS
);
872 /* The following function is invoked on every switch statement (the current one
873 is given in SWTCH) and runs the individual phases of switch conversion on it
874 one after another until one fails or the conversion is completed.
875 Returns NULL on success, or a pointer to a string with the reason why the
876 conversion failed. */
879 process_switch (gimple swtch
)
881 unsigned int i
, branch_num
= gimple_switch_num_labels (swtch
);
883 struct switch_conv_info info
;
885 /* Operand 2 is either NULL_TREE or a vector of cases (stmt.c). */
887 return "switch has no labels";
890 info
.final_bb
= NULL
;
891 info
.switch_bb
= gimple_bb (swtch
);
892 info
.index_expr
= gimple_switch_index (swtch
);
893 info
.arr_ref_first
= NULL
;
894 info
.arr_ref_last
= NULL
;
895 info
.default_prob
= 0;
896 info
.default_count
= 0;
897 info
.other_count
= 0;
898 info
.bit_test_uniq
= 0;
899 info
.bit_test_count
= 0;
900 info
.bit_test_bb
[0] = NULL
;
901 info
.bit_test_bb
[1] = NULL
;
903 /* An ERROR_MARK occurs for various reasons including invalid data type.
904 (comment from stmt.c) */
905 index_type
= TREE_TYPE (info
.index_expr
);
906 if (index_type
== error_mark_node
)
907 return "index error\n";
909 /* Check the case label values are within reasonable range: */
910 if (!check_range (swtch
, &info
))
912 gcc_assert (info
.reason
);
916 /* For all the cases, see whether they are empty, the assignments they
917 represent constant and so on... */
918 for (i
= 0; i
< branch_num
; i
++)
919 if (!check_process_case (gimple_switch_label (swtch
, i
), &info
))
921 gcc_assert (info
.reason
);
923 fprintf (dump_file
, "processing of case %i failed\n\t", i
);
927 if (info
.bit_test_uniq
<= 2)
929 rtl_profile_for_bb (gimple_bb (swtch
));
930 if (expand_switch_using_bit_tests_p (gimple_switch_index (swtch
),
931 info
.range_size
, info
.bit_test_uniq
,
932 info
.bit_test_count
))
934 return "expanding as bit test is preferable";
938 if (!check_final_bb (&info
))
940 gcc_assert (info
.reason
);
944 /* At this point all checks have passed and we can proceed with the
947 create_temp_arrays (&info
);
948 gather_default_values (gimple_switch_label (swtch
, 0), &info
);
949 build_constructors (swtch
, &info
);
951 build_arrays (swtch
, &info
); /* Build the static arrays and assignments. */
952 gen_inbound_check (swtch
, &info
); /* Build the bounds check. */
955 free_temp_arrays (&info
);
959 /* The main function of the pass scans statements for switches and invokes
960 process_switch on them. */
969 const char *failure_reason
;
970 gimple stmt
= last_stmt (bb
);
971 if (stmt
&& gimple_code (stmt
) == GIMPLE_SWITCH
)
975 expanded_location loc
= expand_location (gimple_location (stmt
));
977 fprintf (dump_file
, "beginning to process the following "
978 "SWITCH statement (%s:%d) : ------- \n",
980 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
981 putc ('\n', dump_file
);
984 failure_reason
= process_switch (stmt
);
985 if (! failure_reason
)
989 fputs ("Switch converted\n", dump_file
);
990 fputs ("--------------------------------\n", dump_file
);
997 fputs ("Bailing out - ", dump_file
);
998 fputs (failure_reason
, dump_file
);
999 fputs ("\n--------------------------------\n", dump_file
);
1008 /* The pass gate. */
1011 switchconv_gate (void)
1013 return flag_tree_switch_conversion
!= 0;
1016 struct gimple_opt_pass pass_convert_switch
=
1020 "switchconv", /* name */
1021 switchconv_gate
, /* gate */
1022 do_switchconv
, /* execute */
1025 0, /* static_pass_number */
1026 TV_TREE_SWITCH_CONVERSION
, /* tv_id */
1027 PROP_cfg
| PROP_ssa
, /* properties_required */
1028 0, /* properties_provided */
1029 0, /* properties_destroyed */
1030 0, /* todo_flags_start */
1032 | TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */