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"
94 #include "tree-pass.h"
95 #include "gimple-pretty-print.h"
96 #include "tree-dump.h"
98 #include "langhooks.h"
100 /* The main structure of the pass. */
101 struct switch_conv_info
103 /* The expression used to decide the switch branch. */
106 /* The following integer constants store the minimum and maximum value
107 covered by the case labels. */
111 /* The difference between the above two numbers. Stored here because it
112 is used in all the conversion heuristics, as well as for some of the
113 transformation, and it is expensive to re-compute it all the time. */
116 /* Basic block that contains the actual GIMPLE_SWITCH. */
117 basic_block switch_bb
;
119 /* Basic block that is the target of the default case. */
120 basic_block default_bb
;
122 /* The single successor block of all branches out of the GIMPLE_SWITCH,
123 if such a block exists. Otherwise NULL. */
124 basic_block final_bb
;
126 /* The probability of the default edge in the replaced switch. */
129 /* The count of the default edge in the replaced switch. */
130 gcov_type default_count
;
132 /* Combined count of all other (non-default) edges in the replaced switch. */
133 gcov_type other_count
;
135 /* Number of phi nodes in the final bb (that we'll be replacing). */
138 /* Array of default values, in the same order as phi nodes. */
139 tree
*default_values
;
141 /* Constructors of new static arrays. */
142 VEC (constructor_elt
, gc
) **constructors
;
144 /* Array of ssa names that are initialized with a value from a new static
146 tree
*target_inbound_names
;
148 /* Array of ssa names that are initialized with the default value if the
149 switch expression is out of range. */
150 tree
*target_outbound_names
;
152 /* The first load statement that loads a temporary from a new static array.
154 gimple arr_ref_first
;
156 /* The last load statement that loads a temporary from a new static array. */
159 /* String reason why the case wasn't a good candidate that is written to the
160 dump file, if there is one. */
163 /* Parameters for expand_switch_using_bit_tests. Should be computed
164 the same way as in expand_case. */
169 /* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */
172 collect_switch_conv_info (gimple swtch
, struct switch_conv_info
*info
)
174 unsigned int branch_num
= gimple_switch_num_labels (swtch
);
175 tree min_case
, max_case
;
176 unsigned int count
, i
;
180 memset (info
, 0, sizeof (*info
));
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. */
184 gcc_assert (CASE_LOW (gimple_switch_label (swtch
, 0)) == NULL_TREE
);
186 /* Collect the bits we can deduce from the CFG. */
187 info
->index_expr
= gimple_switch_index (swtch
);
188 info
->switch_bb
= gimple_bb (swtch
);
190 label_to_block (CASE_LABEL (gimple_switch_label (swtch
, 0)));
191 e_default
= find_edge (info
->switch_bb
, info
->default_bb
);
192 info
->default_prob
= e_default
->probability
;
193 info
->default_count
= e_default
->count
;
194 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
196 info
->other_count
+= e
->count
;
198 /* See if there is one common successor block for all branch
199 targets. If it exists, record it in FINAL_BB. */
200 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
202 if (! single_pred_p (e
->dest
))
204 info
->final_bb
= e
->dest
;
209 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
211 if (e
->dest
== info
->final_bb
)
214 if (single_pred_p (e
->dest
)
215 && single_succ_p (e
->dest
)
216 && single_succ (e
->dest
) == info
->final_bb
)
219 info
->final_bb
= NULL
;
223 /* Get upper and lower bounds of case values, and the covered range. */
224 min_case
= gimple_switch_label (swtch
, 1);
225 max_case
= gimple_switch_label (swtch
, branch_num
- 1);
227 info
->range_min
= CASE_LOW (min_case
);
228 if (CASE_HIGH (max_case
) != NULL_TREE
)
229 info
->range_max
= CASE_HIGH (max_case
);
231 info
->range_max
= CASE_LOW (max_case
);
234 int_const_binop (MINUS_EXPR
, info
->range_max
, info
->range_min
);
236 /* Get a count of the number of case labels. Single-valued case labels
237 simply count as one, but a case range counts double, since it may
238 require two compares if it gets lowered as a branching tree. */
240 for (i
= 1; i
< branch_num
; i
++)
242 tree elt
= gimple_switch_label (swtch
, i
);
245 && ! tree_int_cst_equal (CASE_LOW (elt
), CASE_HIGH (elt
)))
250 /* Get the number of unique non-default targets out of the GIMPLE_SWITCH
251 block. Assume a CFG cleanup would have already removed degenerate
252 switch statements, this allows us to just use EDGE_COUNT. */
253 info
->uniq
= EDGE_COUNT (gimple_bb (swtch
)->succs
) - 1;
256 /* Checks whether the range given by individual case statements of the SWTCH
257 switch statement isn't too big and whether the number of branches actually
258 satisfies the size of the new array. */
261 check_range (struct switch_conv_info
*info
)
263 gcc_assert (info
->range_size
);
264 if (!host_integerp (info
->range_size
, 1))
266 info
->reason
= "index range way too large or otherwise unusable";
270 if ((unsigned HOST_WIDE_INT
) tree_low_cst (info
->range_size
, 1)
271 > ((unsigned) info
->count
* SWITCH_CONVERSION_BRANCH_RATIO
))
273 info
->reason
= "the maximum range-branch ratio exceeded";
280 /* Checks whether all but the FINAL_BB basic blocks are empty. */
283 check_all_empty_except_final (struct switch_conv_info
*info
)
288 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
290 if (e
->dest
== info
->final_bb
)
293 if (!empty_block_p (e
->dest
))
295 info
->reason
= "bad case - a non-final BB not empty";
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 (struct switch_conv_info
*info
)
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";
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";
345 = "value from a case is not a valid initializer";
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 (struct switch_conv_info
*info
)
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
++)
369 info
->constructors
[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 (struct switch_conv_info
*info
)
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
, struct switch_conv_info
*info
)
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
, struct switch_conv_info
*info
)
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
);
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
);
476 pos
= int_const_binop (PLUS_EXPR
, pos
, integer_one_node
);
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
,
511 struct switch_conv_info
*info
)
513 unsigned int i
, len
= VEC_length (constructor_elt
, info
->constructors
[num
]);
514 constructor_elt
*elt
;
515 enum machine_mode mode
;
519 if (!INTEGRAL_TYPE_P (type
))
522 mode
= GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type
)));
523 if (GET_MODE_SIZE (TYPE_MODE (type
)) <= GET_MODE_SIZE (mode
))
526 if (len
< (optimize_bb_for_size_p (gimple_bb (swtch
)) ? 2 : 32))
529 FOR_EACH_VEC_ELT (constructor_elt
, info
->constructors
[num
], i
, elt
)
533 if (TREE_CODE (elt
->value
) != INTEGER_CST
)
536 cst
= TREE_INT_CST (elt
->value
);
539 unsigned int prec
= GET_MODE_BITSIZE (mode
);
540 if (prec
> HOST_BITS_PER_WIDE_INT
)
544 && double_int_equal_p (cst
, double_int_zext (cst
, prec
)))
547 && double_int_equal_p (cst
, double_int_sext (cst
, prec
)))
553 && double_int_equal_p (cst
, double_int_sext (cst
, prec
)))
562 mode
= GET_MODE_WIDER_MODE (mode
);
564 || GET_MODE_SIZE (mode
) >= GET_MODE_SIZE (TYPE_MODE (type
)))
570 sign
= TYPE_UNSIGNED (type
) ? 1 : -1;
571 smaller_type
= lang_hooks
.types
.type_for_mode (mode
, sign
>= 0);
572 if (GET_MODE_SIZE (TYPE_MODE (type
))
573 <= GET_MODE_SIZE (TYPE_MODE (smaller_type
)))
579 /* Create an appropriate array type and declaration and assemble a static array
580 variable. Also create a load statement that initializes the variable in
581 question with a value from the static array. SWTCH is the switch statement
582 being converted, NUM is the index to arrays of constructors, default values
583 and target SSA names for this particular array. ARR_INDEX_TYPE is the type
584 of the index of the new array, PHI is the phi node of the final BB that
585 corresponds to the value that will be loaded from the created array. TIDX
586 is an ssa name of a temporary variable holding the index for loads from the
590 build_one_array (gimple swtch
, int num
, tree arr_index_type
, gimple phi
,
591 tree tidx
, struct switch_conv_info
*info
)
595 gimple_stmt_iterator gsi
= gsi_for_stmt (swtch
);
596 location_t loc
= gimple_location (swtch
);
598 gcc_assert (info
->default_values
[num
]);
600 name
= make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi
)), NULL
);
601 info
->target_inbound_names
[num
] = name
;
603 cst
= constructor_contains_same_values_p (info
->constructors
[num
]);
605 load
= gimple_build_assign (name
, cst
);
608 tree array_type
, ctor
, decl
, value_type
, fetch
, default_type
;
610 default_type
= TREE_TYPE (info
->default_values
[num
]);
611 value_type
= array_value_type (swtch
, default_type
, num
, info
);
612 array_type
= build_array_type (value_type
, arr_index_type
);
613 if (default_type
!= value_type
)
616 constructor_elt
*elt
;
618 FOR_EACH_VEC_ELT (constructor_elt
, info
->constructors
[num
], i
, elt
)
619 elt
->value
= fold_convert (value_type
, elt
->value
);
621 ctor
= build_constructor (array_type
, info
->constructors
[num
]);
622 TREE_CONSTANT (ctor
) = true;
623 TREE_STATIC (ctor
) = true;
625 decl
= build_decl (loc
, VAR_DECL
, NULL_TREE
, array_type
);
626 TREE_STATIC (decl
) = 1;
627 DECL_INITIAL (decl
) = ctor
;
629 DECL_NAME (decl
) = create_tmp_var_name ("CSWTCH");
630 DECL_ARTIFICIAL (decl
) = 1;
631 TREE_CONSTANT (decl
) = 1;
632 TREE_READONLY (decl
) = 1;
633 add_referenced_var (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
, struct switch_conv_info
*info
)
661 tree tidx
, sub
, tmp
, utype
;
663 gimple_stmt_iterator gsi
;
665 location_t loc
= gimple_location (swtch
);
667 gsi
= gsi_for_stmt (swtch
);
669 /* Make sure we do not generate arithmetics in a subrange. */
670 utype
= TREE_TYPE (info
->index_expr
);
671 if (TREE_TYPE (utype
))
672 utype
= lang_hooks
.types
.type_for_mode (TYPE_MODE (TREE_TYPE (utype
)), 1);
674 utype
= lang_hooks
.types
.type_for_mode (TYPE_MODE (utype
), 1);
676 arr_index_type
= build_index_type (info
->range_size
);
677 tmp
= create_tmp_var (utype
, "csui");
678 add_referenced_var (tmp
);
679 tidx
= make_ssa_name (tmp
, NULL
);
680 sub
= fold_build2_loc (loc
, MINUS_EXPR
, utype
,
681 fold_convert_loc (loc
, utype
, info
->index_expr
),
682 fold_convert_loc (loc
, utype
, info
->range_min
));
683 sub
= force_gimple_operand_gsi (&gsi
, sub
,
684 false, NULL
, true, GSI_SAME_STMT
);
685 stmt
= gimple_build_assign (tidx
, sub
);
686 SSA_NAME_DEF_STMT (tidx
) = stmt
;
688 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
690 info
->arr_ref_first
= stmt
;
692 for (gsi
= gsi_start_phis (info
->final_bb
), i
= 0;
693 !gsi_end_p (gsi
); gsi_next (&gsi
), i
++)
694 build_one_array (swtch
, i
, arr_index_type
, gsi_stmt (gsi
), tidx
, info
);
697 /* Generates and appropriately inserts loads of default values at the position
698 given by BSI. Returns the last inserted statement. */
701 gen_def_assigns (gimple_stmt_iterator
*gsi
, struct switch_conv_info
*info
)
704 gimple assign
= NULL
;
706 for (i
= 0; i
< info
->phi_count
; i
++)
709 = make_ssa_name (SSA_NAME_VAR (info
->target_inbound_names
[i
]), NULL
);
711 info
->target_outbound_names
[i
] = name
;
712 assign
= gimple_build_assign (name
, info
->default_values
[i
]);
713 SSA_NAME_DEF_STMT (name
) = assign
;
714 gsi_insert_before (gsi
, assign
, GSI_SAME_STMT
);
715 update_stmt (assign
);
720 /* Deletes the unused bbs and edges that now contain the switch statement and
721 its empty branch bbs. BBD is the now dead BB containing the original switch
722 statement, FINAL is the last BB of the converted switch statement (in terms
726 prune_bbs (basic_block bbd
, basic_block final
)
731 for (ei
= ei_start (bbd
->succs
); (e
= ei_safe_edge (ei
)); )
737 delete_basic_block (bb
);
739 delete_basic_block (bbd
);
742 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
743 from the basic block loading values from an array and E2F from the basic
744 block loading default values. BBF is the last switch basic block (see the
745 bbf description in the comment below). */
748 fix_phi_nodes (edge e1f
, edge e2f
, basic_block bbf
,
749 struct switch_conv_info
*info
)
751 gimple_stmt_iterator gsi
;
754 for (gsi
= gsi_start_phis (bbf
), i
= 0;
755 !gsi_end_p (gsi
); gsi_next (&gsi
), i
++)
757 gimple phi
= gsi_stmt (gsi
);
758 add_phi_arg (phi
, info
->target_inbound_names
[i
], e1f
, UNKNOWN_LOCATION
);
759 add_phi_arg (phi
, info
->target_outbound_names
[i
], e2f
, UNKNOWN_LOCATION
);
763 /* Creates a check whether the switch expression value actually falls into the
764 range given by all the cases. If it does not, the temporaries are loaded
765 with default values instead. SWTCH is the switch statement being converted.
767 bb0 is the bb with the switch statement, however, we'll end it with a
770 bb1 is the bb to be used when the range check went ok. It is derived from
773 bb2 is the bb taken when the expression evaluated outside of the range
774 covered by the created arrays. It is populated by loads of default
777 bbF is a fall through for both bb1 and bb2 and contains exactly what
778 originally followed the switch statement.
780 bbD contains the switch statement (in the end). It is unreachable but we
781 still need to strip off its edges.
785 gen_inbound_check (gimple swtch
, struct switch_conv_info
*info
)
787 tree label_decl1
= create_artificial_label (UNKNOWN_LOCATION
);
788 tree label_decl2
= create_artificial_label (UNKNOWN_LOCATION
);
789 tree label_decl3
= create_artificial_label (UNKNOWN_LOCATION
);
790 gimple label1
, label2
, label3
;
797 gimple_stmt_iterator gsi
;
798 basic_block bb0
, bb1
, bb2
, bbf
, bbd
;
799 edge e01
, e02
, e21
, e1d
, e1f
, e2f
;
800 location_t loc
= gimple_location (swtch
);
802 gcc_assert (info
->default_values
);
804 /* Make no effort to update the post-dominator tree. It is actually not
805 that hard for the transformations we have performed, but it is not
806 supported by iterate_fix_dominators.
807 Freeing post-dominance info is dome early to avoid pointless work in
808 create_basic_block, which is called when we split SWITCH_BB. */
809 free_dominance_info (CDI_POST_DOMINATORS
);
811 bb0
= gimple_bb (swtch
);
813 tidx
= gimple_assign_lhs (info
->arr_ref_first
);
814 utype
= TREE_TYPE (tidx
);
816 /* (end of) block 0 */
817 gsi
= gsi_for_stmt (info
->arr_ref_first
);
820 bound
= fold_convert_loc (loc
, utype
, info
->range_size
);
821 cond_stmt
= gimple_build_cond (LE_EXPR
, tidx
, bound
, NULL_TREE
, NULL_TREE
);
822 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
823 update_stmt (cond_stmt
);
826 label2
= gimple_build_label (label_decl2
);
827 gsi_insert_before (&gsi
, label2
, GSI_SAME_STMT
);
828 last_assign
= gen_def_assigns (&gsi
, info
);
831 label1
= gimple_build_label (label_decl1
);
832 gsi_insert_before (&gsi
, label1
, GSI_SAME_STMT
);
835 gsi
= gsi_start_bb (info
->final_bb
);
836 label3
= gimple_build_label (label_decl3
);
837 gsi_insert_before (&gsi
, label3
, GSI_SAME_STMT
);
840 e02
= split_block (bb0
, cond_stmt
);
843 e21
= split_block (bb2
, last_assign
);
847 e1d
= split_block (bb1
, info
->arr_ref_last
);
851 /* flags and profiles of the edge for in-range values */
852 e01
= make_edge (bb0
, bb1
, EDGE_TRUE_VALUE
);
853 e01
->probability
= REG_BR_PROB_BASE
- info
->default_prob
;
854 e01
->count
= info
->other_count
;
856 /* flags and profiles of the edge taking care of out-of-range values */
857 e02
->flags
&= ~EDGE_FALLTHRU
;
858 e02
->flags
|= EDGE_FALSE_VALUE
;
859 e02
->probability
= info
->default_prob
;
860 e02
->count
= info
->default_count
;
862 bbf
= info
->final_bb
;
864 e1f
= make_edge (bb1
, bbf
, EDGE_FALLTHRU
);
865 e1f
->probability
= REG_BR_PROB_BASE
;
866 e1f
->count
= info
->other_count
;
868 e2f
= make_edge (bb2
, bbf
, EDGE_FALLTHRU
);
869 e2f
->probability
= REG_BR_PROB_BASE
;
870 e2f
->count
= info
->default_count
;
872 /* frequencies of the new BBs */
873 bb1
->frequency
= EDGE_FREQUENCY (e01
);
874 bb2
->frequency
= EDGE_FREQUENCY (e02
);
875 bbf
->frequency
= EDGE_FREQUENCY (e1f
) + EDGE_FREQUENCY (e2f
);
877 /* Tidy blocks that have become unreachable. */
878 prune_bbs (bbd
, info
->final_bb
);
880 /* Fixup the PHI nodes in bbF. */
881 fix_phi_nodes (e1f
, e2f
, bbf
, info
);
883 /* Fix the dominator tree, if it is available. */
884 if (dom_info_available_p (CDI_DOMINATORS
))
886 VEC (basic_block
, heap
) *bbs_to_fix_dom
;
888 set_immediate_dominator (CDI_DOMINATORS
, bb1
, bb0
);
889 set_immediate_dominator (CDI_DOMINATORS
, bb2
, bb0
);
890 if (! get_immediate_dominator(CDI_DOMINATORS
, bbf
))
891 /* If bbD was the immediate dominator ... */
892 set_immediate_dominator (CDI_DOMINATORS
, bbf
, bb0
);
894 bbs_to_fix_dom
= VEC_alloc (basic_block
, heap
, 4);
895 VEC_quick_push (basic_block
, bbs_to_fix_dom
, bb0
);
896 VEC_quick_push (basic_block
, bbs_to_fix_dom
, bb1
);
897 VEC_quick_push (basic_block
, bbs_to_fix_dom
, bb2
);
898 VEC_quick_push (basic_block
, bbs_to_fix_dom
, bbf
);
900 iterate_fix_dominators (CDI_DOMINATORS
, bbs_to_fix_dom
, true);
901 VEC_free (basic_block
, heap
, bbs_to_fix_dom
);
905 /* The following function is invoked on every switch statement (the current one
906 is given in SWTCH) and runs the individual phases of switch conversion on it
907 one after another until one fails or the conversion is completed.
908 Returns NULL on success, or a pointer to a string with the reason why the
909 conversion failed. */
912 process_switch (gimple swtch
)
914 struct switch_conv_info info
;
916 /* Degenerate case with only a default label should never happen. */
917 gcc_checking_assert (gimple_switch_num_labels (swtch
) > 1);
919 collect_switch_conv_info (swtch
, &info
);
921 /* No error markers should reach here (they should be filtered out
922 during gimplification). */
923 gcc_checking_assert (TREE_TYPE (info
.index_expr
) != error_mark_node
);
925 /* If there is no common successor, we cannot do the transformation. */
927 return "no common successor to all case label target blocks found";
931 if (expand_switch_using_bit_tests_p (info
.index_expr
, info
.range_size
,
932 info
.uniq
, info
.count
))
933 return "expanding as bit test is preferable";
936 /* Check the case label values are within reasonable range: */
937 if (!check_range (&info
))
939 gcc_assert (info
.reason
);
943 /* For all the cases, see whether they are empty, the assignments they
944 represent constant and so on... */
945 if (! check_all_empty_except_final (&info
))
947 gcc_assert (info
.reason
);
950 if (!check_final_bb (&info
))
952 gcc_assert (info
.reason
);
956 /* At this point all checks have passed and we can proceed with the
959 create_temp_arrays (&info
);
960 gather_default_values (gimple_switch_label (swtch
, 0), &info
);
961 build_constructors (swtch
, &info
);
963 build_arrays (swtch
, &info
); /* Build the static arrays and assignments. */
964 gen_inbound_check (swtch
, &info
); /* Build the bounds check. */
967 free_temp_arrays (&info
);
971 /* The main function of the pass scans statements for switches and invokes
972 process_switch on them. */
981 const char *failure_reason
;
982 gimple stmt
= last_stmt (bb
);
983 if (stmt
&& gimple_code (stmt
) == GIMPLE_SWITCH
)
987 expanded_location loc
= expand_location (gimple_location (stmt
));
989 fprintf (dump_file
, "beginning to process the following "
990 "SWITCH statement (%s:%d) : ------- \n",
992 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
993 putc ('\n', dump_file
);
996 failure_reason
= process_switch (stmt
);
997 if (! failure_reason
)
1001 fputs ("Switch converted\n", dump_file
);
1002 fputs ("--------------------------------\n", dump_file
);
1009 fputs ("Bailing out - ", dump_file
);
1010 fputs (failure_reason
, dump_file
);
1011 fputs ("\n--------------------------------\n", dump_file
);
1020 /* The pass gate. */
1023 switchconv_gate (void)
1025 return flag_tree_switch_conversion
!= 0;
1028 struct gimple_opt_pass pass_convert_switch
=
1032 "switchconv", /* name */
1033 switchconv_gate
, /* gate */
1034 do_switchconv
, /* execute */
1037 0, /* static_pass_number */
1038 TV_TREE_SWITCH_CONVERSION
, /* tv_id */
1039 PROP_cfg
| PROP_ssa
, /* properties_required */
1040 0, /* properties_provided */
1041 0, /* properties_destroyed */
1042 0, /* todo_flags_start */
1044 | TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */