1 /* Lower GIMPLE_SWITCH expressions to something more efficient than
3 Copyright (C) 2006-2024 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
22 /* This file handles the lowering of GIMPLE_SWITCH to an indexed
23 load, or a series of bit-test-and-branch expressions. */
27 #include "coretypes.h"
29 #include "insn-codes.h"
34 #include "tree-pass.h"
36 #include "optabs-tree.h"
38 #include "gimple-pretty-print.h"
39 #include "fold-const.h"
41 #include "stor-layout.h"
44 #include "gimple-iterator.h"
45 #include "gimplify-me.h"
46 #include "gimple-fold.h"
49 #include "alloc-pool.h"
51 #include "tree-into-ssa.h"
52 #include "omp-general.h"
53 #include "gimple-range.h"
54 #include "tree-cfgcleanup.h"
56 /* ??? For lang_hooks.types.type_for_mode, but is there a word_mode
57 type in the GIMPLE type system that is language-independent? */
58 #include "langhooks.h"
60 #include "tree-switch-conversion.h"
62 using namespace tree_switch_conversion
;
66 switch_conversion::switch_conversion (): m_final_bb (NULL
),
67 m_constructors (NULL
), m_default_values (NULL
),
68 m_arr_ref_first (NULL
), m_arr_ref_last (NULL
),
69 m_reason (NULL
), m_default_case_nonstandard (false), m_cfg_altered (false)
73 /* Collection information about SWTCH statement. */
76 switch_conversion::collect (gswitch
*swtch
)
78 unsigned int branch_num
= gimple_switch_num_labels (swtch
);
79 tree min_case
, max_case
;
81 edge e
, e_default
, e_first
;
86 /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
87 is a default label which is the first in the vector.
88 Collect the bits we can deduce from the CFG. */
89 m_index_expr
= gimple_switch_index (swtch
);
90 m_switch_bb
= gimple_bb (swtch
);
91 e_default
= gimple_switch_default_edge (cfun
, swtch
);
92 m_default_bb
= e_default
->dest
;
93 m_default_prob
= e_default
->probability
;
95 /* Get upper and lower bounds of case values, and the covered range. */
96 min_case
= gimple_switch_label (swtch
, 1);
97 max_case
= gimple_switch_label (swtch
, branch_num
- 1);
99 m_range_min
= CASE_LOW (min_case
);
100 if (CASE_HIGH (max_case
) != NULL_TREE
)
101 m_range_max
= CASE_HIGH (max_case
);
103 m_range_max
= CASE_LOW (max_case
);
105 m_contiguous_range
= true;
106 tree last
= CASE_HIGH (min_case
) ? CASE_HIGH (min_case
) : m_range_min
;
107 for (i
= 2; i
< branch_num
; i
++)
109 tree elt
= gimple_switch_label (swtch
, i
);
110 if (wi::to_wide (last
) + 1 != wi::to_wide (CASE_LOW (elt
)))
112 m_contiguous_range
= false;
115 last
= CASE_HIGH (elt
) ? CASE_HIGH (elt
) : CASE_LOW (elt
);
118 if (m_contiguous_range
)
119 e_first
= gimple_switch_edge (cfun
, swtch
, 1);
123 /* See if there is one common successor block for all branch
124 targets. If it exists, record it in FINAL_BB.
125 Start with the destination of the first non-default case
126 if the range is contiguous and default case otherwise as
127 guess or its destination in case it is a forwarder block. */
128 if (! single_pred_p (e_first
->dest
))
129 m_final_bb
= e_first
->dest
;
130 else if (single_succ_p (e_first
->dest
)
131 && ! single_pred_p (single_succ (e_first
->dest
)))
132 m_final_bb
= single_succ (e_first
->dest
);
133 /* Require that all switch destinations are either that common
134 FINAL_BB or a forwarder to it, except for the default
135 case if contiguous range. */
136 auto_vec
<edge
, 10> fw_edges
;
139 FOR_EACH_EDGE (e
, ei
, m_switch_bb
->succs
)
141 edge phi_e
= nullptr;
142 if (e
->dest
== m_final_bb
)
144 else if (single_pred_p (e
->dest
)
145 && single_succ_p (e
->dest
)
146 && single_succ (e
->dest
) == m_final_bb
)
147 phi_e
= single_succ_edge (e
->dest
);
152 else if (phi_e
== e
|| empty_block_p (e
->dest
))
154 /* For empty blocks consider forwarders with equal
155 PHI arguments in m_final_bb as unique. */
157 for (i
= 0; i
< fw_edges
.length (); ++i
)
158 if (phi_alternatives_equal (m_final_bb
, fw_edges
[i
], phi_e
))
160 if (i
== fw_edges
.length ())
162 /* But limit the above possibly quadratic search. */
163 if (fw_edges
.length () < 10)
164 fw_edges
.quick_push (phi_e
);
173 if (e
== e_default
&& m_contiguous_range
)
175 m_default_case_nonstandard
= true;
183 /* When there's not a single common successor block conservatively
184 approximate the number of unique non-default targets. */
186 m_uniq
= EDGE_COUNT (gimple_bb (swtch
)->succs
) - 1;
189 = int_const_binop (MINUS_EXPR
, m_range_max
, m_range_min
);
191 /* Get a count of the number of case labels. Single-valued case labels
192 simply count as one, but a case range counts double, since it may
193 require two compares if it gets lowered as a branching tree. */
195 for (i
= 1; i
< branch_num
; i
++)
197 tree elt
= gimple_switch_label (swtch
, i
);
200 && ! tree_int_cst_equal (CASE_LOW (elt
), CASE_HIGH (elt
)))
205 /* Checks whether the range given by individual case statements of the switch
206 switch statement isn't too big and whether the number of branches actually
207 satisfies the size of the new array. */
210 switch_conversion::check_range ()
212 gcc_assert (m_range_size
);
213 if (!tree_fits_uhwi_p (m_range_size
))
215 m_reason
= "index range way too large or otherwise unusable";
219 if (tree_to_uhwi (m_range_size
)
220 > ((unsigned) m_count
* param_switch_conversion_branch_ratio
))
222 m_reason
= "the maximum range-branch ratio exceeded";
229 /* Checks whether all but the final BB basic blocks are empty. */
232 switch_conversion::check_all_empty_except_final ()
234 edge e
, e_default
= find_edge (m_switch_bb
, m_default_bb
);
237 FOR_EACH_EDGE (e
, ei
, m_switch_bb
->succs
)
239 if (e
->dest
== m_final_bb
)
242 if (!empty_block_p (e
->dest
))
244 if (m_contiguous_range
&& e
== e_default
)
246 m_default_case_nonstandard
= true;
250 m_reason
= "bad case - a non-final BB not empty";
258 /* This function checks whether all required values in phi nodes in final_bb
259 are constants. Required values are those that correspond to a basic block
260 which is a part of the examined switch statement. It returns true if the
261 phi nodes are OK, otherwise false. */
264 switch_conversion::check_final_bb ()
269 for (gsi
= gsi_start_phis (m_final_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
271 gphi
*phi
= gsi
.phi ();
274 if (virtual_operand_p (gimple_phi_result (phi
)))
279 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
281 basic_block bb
= gimple_phi_arg_edge (phi
, i
)->src
;
283 if (bb
== m_switch_bb
284 || (single_pred_p (bb
)
285 && single_pred (bb
) == m_switch_bb
286 && (!m_default_case_nonstandard
287 || empty_block_p (bb
))))
290 const char *reason
= NULL
;
292 val
= gimple_phi_arg_def (phi
, i
);
293 if (!is_gimple_ip_invariant (val
))
294 reason
= "non-invariant value from a case";
297 reloc
= initializer_constant_valid_p (val
, TREE_TYPE (val
));
298 if ((flag_pic
&& reloc
!= null_pointer_node
)
299 || (!flag_pic
&& reloc
== NULL_TREE
))
303 = "value from a case would need runtime relocations";
306 = "value from a case is not a valid initializer";
311 /* For contiguous range, we can allow non-constant
312 or one that needs relocation, as long as it is
313 only reachable from the default case. */
314 if (bb
== m_switch_bb
)
316 if (!m_contiguous_range
|| bb
!= m_default_bb
)
322 unsigned int branch_num
= gimple_switch_num_labels (m_switch
);
323 for (unsigned int i
= 1; i
< branch_num
; i
++)
325 if (gimple_switch_label_bb (cfun
, m_switch
, i
) == bb
)
331 m_default_case_nonstandard
= true;
340 /* The following function allocates default_values, target_{in,out}_names and
341 constructors arrays. The last one is also populated with pointers to
342 vectors that will become constructors of new arrays. */
345 switch_conversion::create_temp_arrays ()
349 m_default_values
= XCNEWVEC (tree
, m_phi_count
* 3);
350 /* ??? Macros do not support multi argument templates in their
351 argument list. We create a typedef to work around that problem. */
352 typedef vec
<constructor_elt
, va_gc
> *vec_constructor_elt_gc
;
353 m_constructors
= XCNEWVEC (vec_constructor_elt_gc
, m_phi_count
);
354 m_target_inbound_names
= m_default_values
+ m_phi_count
;
355 m_target_outbound_names
= m_target_inbound_names
+ m_phi_count
;
356 for (i
= 0; i
< m_phi_count
; i
++)
357 vec_alloc (m_constructors
[i
], tree_to_uhwi (m_range_size
) + 1);
360 /* Populate the array of default values in the order of phi nodes.
361 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch
362 if the range is non-contiguous or the default case has standard
363 structure, otherwise it is the first non-default case instead. */
366 switch_conversion::gather_default_values (tree default_case
)
369 basic_block bb
= label_to_block (cfun
, CASE_LABEL (default_case
));
373 gcc_assert (CASE_LOW (default_case
) == NULL_TREE
374 || m_default_case_nonstandard
);
376 if (bb
== m_final_bb
)
377 e
= find_edge (m_switch_bb
, bb
);
379 e
= single_succ_edge (bb
);
381 for (gsi
= gsi_start_phis (m_final_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
383 gphi
*phi
= gsi
.phi ();
384 if (virtual_operand_p (gimple_phi_result (phi
)))
386 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
388 m_default_values
[i
++] = val
;
392 /* The following function populates the vectors in the constructors array with
393 future contents of the static arrays. The vectors are populated in the
394 order of phi nodes. */
397 switch_conversion::build_constructors ()
399 unsigned i
, branch_num
= gimple_switch_num_labels (m_switch
);
400 tree pos
= m_range_min
;
401 tree pos_one
= build_int_cst (TREE_TYPE (pos
), 1);
403 for (i
= 1; i
< branch_num
; i
++)
405 tree cs
= gimple_switch_label (m_switch
, i
);
406 basic_block bb
= label_to_block (cfun
, CASE_LABEL (cs
));
412 if (bb
== m_final_bb
)
413 e
= find_edge (m_switch_bb
, bb
);
415 e
= single_succ_edge (bb
);
418 while (tree_int_cst_lt (pos
, CASE_LOW (cs
)))
421 for (k
= 0; k
< m_phi_count
; k
++)
425 elt
.index
= int_const_binop (MINUS_EXPR
, pos
, m_range_min
);
426 if (TYPE_PRECISION (TREE_TYPE (elt
.index
))
427 > TYPE_PRECISION (sizetype
))
428 elt
.index
= fold_convert (sizetype
, elt
.index
);
430 = unshare_expr_without_location (m_default_values
[k
]);
431 m_constructors
[k
]->quick_push (elt
);
434 pos
= int_const_binop (PLUS_EXPR
, pos
, pos_one
);
436 gcc_assert (tree_int_cst_equal (pos
, CASE_LOW (cs
)));
440 high
= CASE_HIGH (cs
);
442 high
= CASE_LOW (cs
);
443 for (gsi
= gsi_start_phis (m_final_bb
);
444 !gsi_end_p (gsi
); gsi_next (&gsi
))
446 gphi
*phi
= gsi
.phi ();
447 if (virtual_operand_p (gimple_phi_result (phi
)))
449 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
450 tree low
= CASE_LOW (cs
);
457 elt
.index
= int_const_binop (MINUS_EXPR
, pos
, m_range_min
);
458 if (TYPE_PRECISION (TREE_TYPE (elt
.index
))
459 > TYPE_PRECISION (sizetype
))
460 elt
.index
= fold_convert (sizetype
, elt
.index
);
461 elt
.value
= unshare_expr_without_location (val
);
462 m_constructors
[j
]->quick_push (elt
);
464 pos
= int_const_binop (PLUS_EXPR
, pos
, pos_one
);
465 } while (!tree_int_cst_lt (high
, pos
)
466 && tree_int_cst_lt (low
, pos
));
472 /* If all values in the constructor vector are products of a linear function
473 a * x + b, then return true. When true, COEFF_A and COEFF_B and
474 coefficients of the linear function. Note that equal values are special
475 case of a linear function with a and b equal to zero. */
478 switch_conversion::contains_linear_function_p (vec
<constructor_elt
, va_gc
> *vec
,
483 constructor_elt
*elt
;
485 gcc_assert (vec
->length () >= 2);
487 /* Let's try to find any linear function a * x + y that can apply to
488 given values. 'a' can be calculated as follows:
490 a = (y2 - y1) / (x2 - x1) where x2 - x1 = 1 (consecutive case indices)
499 tree elt0
= (*vec
)[0].value
;
500 tree elt1
= (*vec
)[1].value
;
502 if (TREE_CODE (elt0
) != INTEGER_CST
|| TREE_CODE (elt1
) != INTEGER_CST
)
506 = wide_int::from (wi::to_wide (m_range_min
),
507 TYPE_PRECISION (TREE_TYPE (elt0
)),
508 TYPE_SIGN (TREE_TYPE (m_range_min
)));
509 wide_int y1
= wi::to_wide (elt0
);
510 wide_int y2
= wi::to_wide (elt1
);
511 wide_int a
= y2
- y1
;
512 wide_int b
= y2
- a
* (range_min
+ 1);
514 /* Verify that all values fulfill the linear function. */
515 FOR_EACH_VEC_SAFE_ELT (vec
, i
, elt
)
517 if (TREE_CODE (elt
->value
) != INTEGER_CST
)
520 wide_int value
= wi::to_wide (elt
->value
);
521 if (a
* range_min
+ b
!= value
)
533 /* Return type which should be used for array elements, either TYPE's
534 main variant or, for integral types, some smaller integral type
535 that can still hold all the constants. */
538 switch_conversion::array_value_type (tree type
, int num
)
540 unsigned int i
, len
= vec_safe_length (m_constructors
[num
]);
541 constructor_elt
*elt
;
545 /* Types with alignments greater than their size can reach here, e.g. out of
546 SRA. We couldn't use these as an array component type so get back to the
547 main variant first, which, for our purposes, is fine for other types as
550 type
= TYPE_MAIN_VARIANT (type
);
552 if (!INTEGRAL_TYPE_P (type
)
553 || (TREE_CODE (type
) == BITINT_TYPE
554 && (TYPE_PRECISION (type
) > MAX_FIXED_MODE_SIZE
555 || TYPE_MODE (type
) == BLKmode
)))
558 scalar_int_mode type_mode
= SCALAR_INT_TYPE_MODE (type
);
559 scalar_int_mode mode
= get_narrowest_mode (type_mode
);
560 if (GET_MODE_SIZE (type_mode
) <= GET_MODE_SIZE (mode
))
563 if (len
< (optimize_bb_for_size_p (gimple_bb (m_switch
)) ? 2 : 32))
566 FOR_EACH_VEC_SAFE_ELT (m_constructors
[num
], i
, elt
)
570 if (TREE_CODE (elt
->value
) != INTEGER_CST
)
573 cst
= wi::to_wide (elt
->value
);
576 unsigned int prec
= GET_MODE_BITSIZE (mode
);
577 if (prec
> HOST_BITS_PER_WIDE_INT
)
580 if (sign
>= 0 && cst
== wi::zext (cst
, prec
))
582 if (sign
== 0 && cst
== wi::sext (cst
, prec
))
587 if (sign
<= 0 && cst
== wi::sext (cst
, prec
))
596 if (!GET_MODE_WIDER_MODE (mode
).exists (&mode
)
597 || GET_MODE_SIZE (mode
) >= GET_MODE_SIZE (type_mode
))
603 sign
= TYPE_UNSIGNED (type
) ? 1 : -1;
604 smaller_type
= lang_hooks
.types
.type_for_mode (mode
, sign
>= 0);
605 if (GET_MODE_SIZE (type_mode
)
606 <= GET_MODE_SIZE (SCALAR_INT_TYPE_MODE (smaller_type
)))
612 /* Create an appropriate array type and declaration and assemble a static
613 array variable. Also create a load statement that initializes
614 the variable in question with a value from the static array. SWTCH is
615 the switch statement being converted, NUM is the index to
616 arrays of constructors, default values and target SSA names
617 for this particular array. ARR_INDEX_TYPE is the type of the index
618 of the new array, PHI is the phi node of the final BB that corresponds
619 to the value that will be loaded from the created array. TIDX
620 is an ssa name of a temporary variable holding the index for loads from the
624 switch_conversion::build_one_array (int num
, tree arr_index_type
,
625 gphi
*phi
, tree tidx
)
629 gimple_stmt_iterator gsi
= gsi_for_stmt (m_switch
);
630 location_t loc
= gimple_location (m_switch
);
632 gcc_assert (m_default_values
[num
]);
634 name
= copy_ssa_name (PHI_RESULT (phi
));
635 m_target_inbound_names
[num
] = name
;
637 vec
<constructor_elt
, va_gc
> *constructor
= m_constructors
[num
];
638 wide_int coeff_a
, coeff_b
;
639 bool linear_p
= contains_linear_function_p (constructor
, &coeff_a
, &coeff_b
);
642 && (type
= range_check_type (TREE_TYPE ((*constructor
)[0].value
))))
644 if (dump_file
&& coeff_a
.to_uhwi () > 0)
645 fprintf (dump_file
, "Linear transformation with A = %" PRId64
646 " and B = %" PRId64
"\n", coeff_a
.to_shwi (),
649 /* We must use type of constructor values. */
650 gimple_seq seq
= NULL
;
651 tree tmp
= gimple_convert (&seq
, type
, m_index_expr
);
652 tree tmp2
= gimple_build (&seq
, MULT_EXPR
, type
,
653 wide_int_to_tree (type
, coeff_a
), tmp
);
654 tree tmp3
= gimple_build (&seq
, PLUS_EXPR
, type
, tmp2
,
655 wide_int_to_tree (type
, coeff_b
));
656 tree tmp4
= gimple_convert (&seq
, TREE_TYPE (name
), tmp3
);
657 gsi_insert_seq_before (&gsi
, seq
, GSI_SAME_STMT
);
658 load
= gimple_build_assign (name
, tmp4
);
662 tree array_type
, ctor
, decl
, value_type
, fetch
, default_type
;
664 default_type
= TREE_TYPE (m_default_values
[num
]);
665 value_type
= array_value_type (default_type
, num
);
666 array_type
= build_array_type (value_type
, arr_index_type
);
667 if (default_type
!= value_type
)
670 constructor_elt
*elt
;
672 FOR_EACH_VEC_SAFE_ELT (constructor
, i
, elt
)
673 elt
->value
= fold_convert (value_type
, elt
->value
);
675 ctor
= build_constructor (array_type
, constructor
);
676 TREE_CONSTANT (ctor
) = true;
677 TREE_STATIC (ctor
) = true;
679 decl
= build_decl (loc
, VAR_DECL
, NULL_TREE
, array_type
);
680 TREE_STATIC (decl
) = 1;
681 DECL_INITIAL (decl
) = ctor
;
683 DECL_NAME (decl
) = create_tmp_var_name ("CSWTCH");
684 DECL_ARTIFICIAL (decl
) = 1;
685 DECL_IGNORED_P (decl
) = 1;
686 TREE_CONSTANT (decl
) = 1;
687 TREE_READONLY (decl
) = 1;
688 DECL_IGNORED_P (decl
) = 1;
689 if (offloading_function_p (cfun
->decl
))
690 DECL_ATTRIBUTES (decl
)
691 = tree_cons (get_identifier ("omp declare target"), NULL_TREE
,
693 varpool_node::finalize_decl (decl
);
695 fetch
= build4 (ARRAY_REF
, value_type
, decl
, tidx
, NULL_TREE
,
697 if (default_type
!= value_type
)
699 fetch
= fold_convert (default_type
, fetch
);
700 fetch
= force_gimple_operand_gsi (&gsi
, fetch
, true, NULL_TREE
,
701 true, GSI_SAME_STMT
);
703 load
= gimple_build_assign (name
, fetch
);
706 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
708 m_arr_ref_last
= load
;
711 /* Builds and initializes static arrays initialized with values gathered from
712 the switch statement. Also creates statements that load values from
716 switch_conversion::build_arrays ()
719 tree tidx
, sub
, utype
, tidxtype
;
721 gimple_stmt_iterator gsi
;
724 location_t loc
= gimple_location (m_switch
);
726 gsi
= gsi_for_stmt (m_switch
);
728 /* Make sure we do not generate arithmetics in a subrange. */
729 utype
= TREE_TYPE (m_index_expr
);
730 if (TREE_TYPE (utype
))
731 utype
= lang_hooks
.types
.type_for_mode (TYPE_MODE (TREE_TYPE (utype
)), 1);
732 else if (TREE_CODE (utype
) == BITINT_TYPE
733 && (TYPE_PRECISION (utype
) > MAX_FIXED_MODE_SIZE
734 || TYPE_MODE (utype
) == BLKmode
))
735 utype
= unsigned_type_for (utype
);
737 utype
= lang_hooks
.types
.type_for_mode (TYPE_MODE (utype
), 1);
738 if (TYPE_PRECISION (utype
) > TYPE_PRECISION (sizetype
))
743 arr_index_type
= build_index_type (m_range_size
);
744 tidx
= make_ssa_name (tidxtype
);
745 sub
= fold_build2_loc (loc
, MINUS_EXPR
, utype
,
746 fold_convert_loc (loc
, utype
, m_index_expr
),
747 fold_convert_loc (loc
, utype
, m_range_min
));
748 sub
= fold_convert (tidxtype
, sub
);
749 sub
= force_gimple_operand_gsi (&gsi
, sub
,
750 false, NULL
, true, GSI_SAME_STMT
);
751 stmt
= gimple_build_assign (tidx
, sub
);
753 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
755 m_arr_ref_first
= stmt
;
757 for (gpi
= gsi_start_phis (m_final_bb
), i
= 0;
758 !gsi_end_p (gpi
); gsi_next (&gpi
))
760 gphi
*phi
= gpi
.phi ();
761 if (!virtual_operand_p (gimple_phi_result (phi
)))
762 build_one_array (i
++, arr_index_type
, phi
, tidx
);
767 FOR_EACH_EDGE (e
, ei
, m_switch_bb
->succs
)
769 if (e
->dest
== m_final_bb
)
771 if (!m_default_case_nonstandard
772 || e
->dest
!= m_default_bb
)
774 e
= single_succ_edge (e
->dest
);
778 gcc_assert (e
&& e
->dest
== m_final_bb
);
779 m_target_vop
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
784 /* Generates and appropriately inserts loads of default values at the position
785 given by GSI. Returns the last inserted statement. */
788 switch_conversion::gen_def_assigns (gimple_stmt_iterator
*gsi
)
791 gassign
*assign
= NULL
;
793 for (i
= 0; i
< m_phi_count
; i
++)
795 tree name
= copy_ssa_name (m_target_inbound_names
[i
]);
796 m_target_outbound_names
[i
] = name
;
797 assign
= gimple_build_assign (name
, m_default_values
[i
]);
798 gsi_insert_before (gsi
, assign
, GSI_SAME_STMT
);
799 update_stmt (assign
);
804 /* Deletes the unused bbs and edges that now contain the switch statement and
805 its empty branch bbs. BBD is the now dead BB containing
806 the original switch statement, FINAL is the last BB of the converted
807 switch statement (in terms of succession). */
810 switch_conversion::prune_bbs (basic_block bbd
, basic_block final
,
811 basic_block default_bb
)
816 for (ei
= ei_start (bbd
->succs
); (e
= ei_safe_edge (ei
)); )
821 if (bb
!= final
&& bb
!= default_bb
)
822 delete_basic_block (bb
);
824 delete_basic_block (bbd
);
827 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
828 from the basic block loading values from an array and E2F from the basic
829 block loading default values. BBF is the last switch basic block (see the
830 bbf description in the comment below). */
833 switch_conversion::fix_phi_nodes (edge e1f
, edge e2f
, basic_block bbf
)
838 for (gsi
= gsi_start_phis (bbf
), i
= 0;
839 !gsi_end_p (gsi
); gsi_next (&gsi
))
841 gphi
*phi
= gsi
.phi ();
842 tree inbound
, outbound
;
843 if (virtual_operand_p (gimple_phi_result (phi
)))
844 inbound
= outbound
= m_target_vop
;
847 inbound
= m_target_inbound_names
[i
];
848 outbound
= m_target_outbound_names
[i
++];
850 add_phi_arg (phi
, inbound
, e1f
, UNKNOWN_LOCATION
);
851 if (!m_default_case_nonstandard
)
852 add_phi_arg (phi
, outbound
, e2f
, UNKNOWN_LOCATION
);
856 /* Creates a check whether the switch expression value actually falls into the
857 range given by all the cases. If it does not, the temporaries are loaded
858 with default values instead. */
861 switch_conversion::gen_inbound_check ()
863 tree label_decl1
= create_artificial_label (UNKNOWN_LOCATION
);
864 tree label_decl2
= create_artificial_label (UNKNOWN_LOCATION
);
865 tree label_decl3
= create_artificial_label (UNKNOWN_LOCATION
);
866 glabel
*label1
, *label2
, *label3
;
872 gassign
*last_assign
= NULL
;
873 gimple_stmt_iterator gsi
;
874 basic_block bb0
, bb1
, bb2
, bbf
, bbd
;
875 edge e01
= NULL
, e02
, e21
, e1d
, e1f
, e2f
;
876 location_t loc
= gimple_location (m_switch
);
878 gcc_assert (m_default_values
);
880 bb0
= gimple_bb (m_switch
);
882 tidx
= gimple_assign_lhs (m_arr_ref_first
);
883 utype
= TREE_TYPE (tidx
);
885 /* (end of) block 0 */
886 gsi
= gsi_for_stmt (m_arr_ref_first
);
889 bound
= fold_convert_loc (loc
, utype
, m_range_size
);
890 cond_stmt
= gimple_build_cond (LE_EXPR
, tidx
, bound
, NULL_TREE
, NULL_TREE
);
891 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
892 update_stmt (cond_stmt
);
895 if (!m_default_case_nonstandard
)
897 label2
= gimple_build_label (label_decl2
);
898 gsi_insert_before (&gsi
, label2
, GSI_SAME_STMT
);
899 last_assign
= gen_def_assigns (&gsi
);
903 label1
= gimple_build_label (label_decl1
);
904 gsi_insert_before (&gsi
, label1
, GSI_SAME_STMT
);
907 gsi
= gsi_start_bb (m_final_bb
);
908 label3
= gimple_build_label (label_decl3
);
909 gsi_insert_before (&gsi
, label3
, GSI_SAME_STMT
);
912 e02
= split_block (bb0
, cond_stmt
);
915 if (m_default_case_nonstandard
)
920 e01
->flags
= EDGE_TRUE_VALUE
;
921 e02
= make_edge (bb0
, bb2
, EDGE_FALSE_VALUE
);
922 edge e_default
= find_edge (bb1
, bb2
);
923 for (gphi_iterator gsi
= gsi_start_phis (bb2
);
924 !gsi_end_p (gsi
); gsi_next (&gsi
))
926 gphi
*phi
= gsi
.phi ();
927 tree arg
= PHI_ARG_DEF_FROM_EDGE (phi
, e_default
);
928 add_phi_arg (phi
, arg
, e02
,
929 gimple_phi_arg_location_from_edge (phi
, e_default
));
931 /* Partially fix the dominator tree, if it is available. */
932 if (dom_info_available_p (CDI_DOMINATORS
))
933 redirect_immediate_dominators (CDI_DOMINATORS
, bb1
, bb0
);
937 e21
= split_block (bb2
, last_assign
);
942 e1d
= split_block (bb1
, m_arr_ref_last
);
946 /* Flags and profiles of the edge for in-range values. */
947 if (!m_default_case_nonstandard
)
948 e01
= make_edge (bb0
, bb1
, EDGE_TRUE_VALUE
);
949 e01
->probability
= m_default_prob
.invert ();
951 /* Flags and profiles of the edge taking care of out-of-range values. */
952 e02
->flags
&= ~EDGE_FALLTHRU
;
953 e02
->flags
|= EDGE_FALSE_VALUE
;
954 e02
->probability
= m_default_prob
;
958 e1f
= make_edge (bb1
, bbf
, EDGE_FALLTHRU
);
959 e1f
->probability
= profile_probability::always ();
961 if (m_default_case_nonstandard
)
965 e2f
= make_edge (bb2
, bbf
, EDGE_FALLTHRU
);
966 e2f
->probability
= profile_probability::always ();
969 /* frequencies of the new BBs */
970 bb1
->count
= e01
->count ();
971 bb2
->count
= e02
->count ();
972 if (!m_default_case_nonstandard
)
973 bbf
->count
= e1f
->count () + e2f
->count ();
975 /* Tidy blocks that have become unreachable. */
976 prune_bbs (bbd
, m_final_bb
,
977 m_default_case_nonstandard
? m_default_bb
: NULL
);
979 /* Fixup the PHI nodes in bbF. */
980 fix_phi_nodes (e1f
, e2f
, bbf
);
982 /* Fix the dominator tree, if it is available. */
983 if (dom_info_available_p (CDI_DOMINATORS
))
985 vec
<basic_block
> bbs_to_fix_dom
;
987 set_immediate_dominator (CDI_DOMINATORS
, bb1
, bb0
);
988 if (!m_default_case_nonstandard
)
989 set_immediate_dominator (CDI_DOMINATORS
, bb2
, bb0
);
990 if (! get_immediate_dominator (CDI_DOMINATORS
, bbf
))
991 /* If bbD was the immediate dominator ... */
992 set_immediate_dominator (CDI_DOMINATORS
, bbf
, bb0
);
994 bbs_to_fix_dom
.create (3 + (bb2
!= bbf
));
995 bbs_to_fix_dom
.quick_push (bb0
);
996 bbs_to_fix_dom
.quick_push (bb1
);
998 bbs_to_fix_dom
.quick_push (bb2
);
999 bbs_to_fix_dom
.quick_push (bbf
);
1001 iterate_fix_dominators (CDI_DOMINATORS
, bbs_to_fix_dom
, true);
1002 bbs_to_fix_dom
.release ();
1006 /* The following function is invoked on every switch statement (the current
1007 one is given in SWTCH) and runs the individual phases of switch
1008 conversion on it one after another until one fails or the conversion
1009 is completed. On success, NULL is in m_reason, otherwise points
1010 to a string with the reason why the conversion failed. */
1013 switch_conversion::expand (gswitch
*swtch
)
1015 /* Group case labels so that we get the right results from the heuristics
1016 that decide on the code generation approach for this switch. */
1017 m_cfg_altered
|= group_case_labels_stmt (swtch
);
1019 /* If this switch is now a degenerate case with only a default label,
1020 there is nothing left for us to do. */
1021 if (gimple_switch_num_labels (swtch
) < 2)
1023 m_reason
= "switch is a degenerate case";
1029 /* No error markers should reach here (they should be filtered out
1030 during gimplification). */
1031 gcc_checking_assert (TREE_TYPE (m_index_expr
) != error_mark_node
);
1033 /* Prefer bit test if possible. */
1034 if (tree_fits_uhwi_p (m_range_size
)
1035 && bit_test_cluster::can_be_handled (tree_to_uhwi (m_range_size
), m_uniq
)
1036 && bit_test_cluster::is_beneficial (m_count
, m_uniq
))
1038 m_reason
= "expanding as bit test is preferable";
1044 /* This will be expanded as a decision tree . */
1045 m_reason
= "expanding as jumps is preferable";
1049 /* If there is no common successor, we cannot do the transformation. */
1052 m_reason
= "no common successor to all case label target blocks found";
1056 /* Check the case label values are within reasonable range: */
1057 if (!check_range ())
1059 gcc_assert (m_reason
);
1063 /* For all the cases, see whether they are empty, the assignments they
1064 represent constant and so on... */
1065 if (!check_all_empty_except_final ())
1067 gcc_assert (m_reason
);
1070 if (!check_final_bb ())
1072 gcc_assert (m_reason
);
1076 /* At this point all checks have passed and we can proceed with the
1079 create_temp_arrays ();
1080 gather_default_values (m_default_case_nonstandard
1081 ? gimple_switch_label (swtch
, 1)
1082 : gimple_switch_default_label (swtch
));
1083 build_constructors ();
1085 build_arrays (); /* Build the static arrays and assignments. */
1086 gen_inbound_check (); /* Build the bounds check. */
1088 m_cfg_altered
= true;
1093 switch_conversion::~switch_conversion ()
1095 XDELETEVEC (m_constructors
);
1096 XDELETEVEC (m_default_values
);
1101 group_cluster::group_cluster (vec
<cluster
*> &clusters
,
1102 unsigned start
, unsigned end
)
1104 gcc_checking_assert (end
- start
+ 1 >= 1);
1105 m_prob
= profile_probability::never ();
1106 m_cases
.create (end
- start
+ 1);
1107 for (unsigned i
= start
; i
<= end
; i
++)
1109 m_cases
.quick_push (static_cast<simple_cluster
*> (clusters
[i
]));
1110 m_prob
+= clusters
[i
]->m_prob
;
1112 m_subtree_prob
= m_prob
;
1117 group_cluster::~group_cluster ()
1119 for (unsigned i
= 0; i
< m_cases
.length (); i
++)
1125 /* Dump content of a cluster. */
1128 group_cluster::dump (FILE *f
, bool details
)
1130 unsigned total_values
= 0;
1131 for (unsigned i
= 0; i
< m_cases
.length (); i
++)
1132 total_values
+= m_cases
[i
]->get_range (m_cases
[i
]->get_low (),
1133 m_cases
[i
]->get_high ());
1135 unsigned comparison_count
= 0;
1136 for (unsigned i
= 0; i
< m_cases
.length (); i
++)
1138 simple_cluster
*sc
= static_cast<simple_cluster
*> (m_cases
[i
]);
1139 comparison_count
+= sc
->get_comparison_count ();
1142 unsigned HOST_WIDE_INT range
= get_range (get_low (), get_high ());
1143 fprintf (f
, "%s", get_type () == JUMP_TABLE
? "JT" : "BT");
1146 fprintf (f
, "(values:%d comparisons:%d range:" HOST_WIDE_INT_PRINT_DEC
1147 " density: %.2f%%)", total_values
, comparison_count
, range
,
1148 100.0f
* comparison_count
/ range
);
1151 PRINT_CASE (f
, get_low ());
1153 PRINT_CASE (f
, get_high ());
1157 /* Emit GIMPLE code to handle the cluster. */
1160 jump_table_cluster::emit (tree index_expr
, tree
,
1161 tree default_label_expr
, basic_block default_bb
,
1164 tree low
= get_low ();
1165 unsigned HOST_WIDE_INT range
= get_range (low
, get_high ());
1166 unsigned HOST_WIDE_INT nondefault_range
= 0;
1167 bool bitint
= false;
1168 gimple_stmt_iterator gsi
= gsi_start_bb (m_case_bb
);
1170 /* For large/huge _BitInt, subtract low from index_expr, cast to unsigned
1171 DImode type (get_range doesn't support ranges larger than 64-bits)
1172 and subtract low from all case values as well. */
1173 if (TREE_CODE (TREE_TYPE (index_expr
)) == BITINT_TYPE
1174 && TYPE_PRECISION (TREE_TYPE (index_expr
)) > GET_MODE_PRECISION (DImode
))
1177 tree this_low
= low
, type
;
1179 gimple_seq seq
= NULL
;
1180 if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (index_expr
)))
1182 type
= unsigned_type_for (TREE_TYPE (index_expr
));
1183 index_expr
= gimple_convert (&seq
, type
, index_expr
);
1184 this_low
= fold_convert (type
, this_low
);
1186 this_low
= const_unop (NEGATE_EXPR
, TREE_TYPE (this_low
), this_low
);
1187 index_expr
= gimple_build (&seq
, PLUS_EXPR
, TREE_TYPE (index_expr
),
1188 index_expr
, this_low
);
1189 type
= build_nonstandard_integer_type (GET_MODE_PRECISION (DImode
), 1);
1190 g
= gimple_build_cond (GT_EXPR
, index_expr
,
1191 fold_convert (TREE_TYPE (index_expr
),
1192 TYPE_MAX_VALUE (type
)),
1193 NULL_TREE
, NULL_TREE
);
1194 gimple_seq_add_stmt (&seq
, g
);
1195 gimple_seq_set_location (seq
, loc
);
1196 gsi_insert_seq_after (&gsi
, seq
, GSI_NEW_STMT
);
1197 edge e1
= split_block (m_case_bb
, g
);
1198 e1
->flags
= EDGE_FALSE_VALUE
;
1199 e1
->probability
= profile_probability::likely ();
1200 edge e2
= make_edge (e1
->src
, default_bb
, EDGE_TRUE_VALUE
);
1201 e2
->probability
= e1
->probability
.invert ();
1202 gsi
= gsi_start_bb (e1
->dest
);
1204 index_expr
= gimple_convert (&seq
, type
, index_expr
);
1205 gimple_seq_set_location (seq
, loc
);
1206 gsi_insert_seq_after (&gsi
, seq
, GSI_NEW_STMT
);
1209 /* For jump table we just emit a new gswitch statement that will
1210 be latter lowered to jump table. */
1211 auto_vec
<tree
> labels
;
1212 labels
.create (m_cases
.length ());
1214 basic_block case_bb
= gsi_bb (gsi
);
1215 make_edge (case_bb
, default_bb
, 0);
1216 for (unsigned i
= 0; i
< m_cases
.length (); i
++)
1218 tree lab
= unshare_expr (m_cases
[i
]->m_case_label_expr
);
1222 = fold_convert (TREE_TYPE (index_expr
),
1223 const_binop (MINUS_EXPR
,
1224 TREE_TYPE (CASE_LOW (lab
)),
1225 CASE_LOW (lab
), low
));
1226 if (CASE_HIGH (lab
))
1228 = fold_convert (TREE_TYPE (index_expr
),
1229 const_binop (MINUS_EXPR
,
1230 TREE_TYPE (CASE_HIGH (lab
)),
1231 CASE_HIGH (lab
), low
));
1233 labels
.quick_push (lab
);
1234 make_edge (case_bb
, m_cases
[i
]->m_case_bb
, 0);
1237 gswitch
*s
= gimple_build_switch (index_expr
,
1238 unshare_expr (default_label_expr
), labels
);
1239 gimple_set_location (s
, loc
);
1240 gsi_insert_after (&gsi
, s
, GSI_NEW_STMT
);
1242 /* Set up even probabilities for all cases. */
1243 for (unsigned i
= 0; i
< m_cases
.length (); i
++)
1245 simple_cluster
*sc
= static_cast<simple_cluster
*> (m_cases
[i
]);
1246 edge case_edge
= find_edge (case_bb
, sc
->m_case_bb
);
1247 unsigned HOST_WIDE_INT case_range
1248 = sc
->get_range (sc
->get_low (), sc
->get_high ());
1249 nondefault_range
+= case_range
;
1251 /* case_edge->aux is number of values in a jump-table that are covered
1252 by the case_edge. */
1253 case_edge
->aux
= (void *) ((intptr_t) (case_edge
->aux
) + case_range
);
1256 edge default_edge
= gimple_switch_default_edge (cfun
, s
);
1257 default_edge
->probability
= profile_probability::never ();
1259 for (unsigned i
= 0; i
< m_cases
.length (); i
++)
1261 simple_cluster
*sc
= static_cast<simple_cluster
*> (m_cases
[i
]);
1262 edge case_edge
= find_edge (case_bb
, sc
->m_case_bb
);
1263 case_edge
->probability
1264 = profile_probability::always ().apply_scale ((intptr_t)case_edge
->aux
,
1268 /* Number of non-default values is probability of default edge. */
1269 default_edge
->probability
1270 += profile_probability::always ().apply_scale (nondefault_range
,
1273 switch_decision_tree::reset_out_edges_aux (s
);
1276 /* Find jump tables of given CLUSTERS, where all members of the vector
1277 are of type simple_cluster. New clusters are returned. */
1280 jump_table_cluster::find_jump_tables (vec
<cluster
*> &clusters
)
1283 return clusters
.copy ();
1285 unsigned l
= clusters
.length ();
1286 auto_vec
<min_cluster_item
> min
;
1287 min
.reserve (l
+ 1);
1289 min
.quick_push (min_cluster_item (0, 0, 0));
1291 unsigned HOST_WIDE_INT max_ratio
1292 = (optimize_insn_for_size_p ()
1293 ? param_jump_table_max_growth_ratio_for_size
1294 : param_jump_table_max_growth_ratio_for_speed
);
1296 for (unsigned i
= 1; i
<= l
; i
++)
1298 /* Set minimal # of clusters with i-th item to infinite. */
1299 min
.quick_push (min_cluster_item (INT_MAX
, INT_MAX
, INT_MAX
));
1301 /* Pre-calculate number of comparisons for the clusters. */
1302 HOST_WIDE_INT comparison_count
= 0;
1303 for (unsigned k
= 0; k
<= i
- 1; k
++)
1305 simple_cluster
*sc
= static_cast<simple_cluster
*> (clusters
[k
]);
1306 comparison_count
+= sc
->get_comparison_count ();
1309 for (unsigned j
= 0; j
< i
; j
++)
1311 unsigned HOST_WIDE_INT s
= min
[j
].m_non_jt_cases
;
1312 if (i
- j
< case_values_threshold ())
1315 /* Prefer clusters with smaller number of numbers covered. */
1316 if ((min
[j
].m_count
+ 1 < min
[i
].m_count
1317 || (min
[j
].m_count
+ 1 == min
[i
].m_count
1318 && s
< min
[i
].m_non_jt_cases
))
1319 && can_be_handled (clusters
, j
, i
- 1, max_ratio
,
1321 min
[i
] = min_cluster_item (min
[j
].m_count
+ 1, j
, s
);
1323 simple_cluster
*sc
= static_cast<simple_cluster
*> (clusters
[j
]);
1324 comparison_count
-= sc
->get_comparison_count ();
1327 gcc_checking_assert (comparison_count
== 0);
1328 gcc_checking_assert (min
[i
].m_count
!= INT_MAX
);
1332 if (min
[l
].m_count
== l
)
1333 return clusters
.copy ();
1335 vec
<cluster
*> output
;
1338 /* Find and build the clusters. */
1339 for (unsigned int end
= l
;;)
1341 int start
= min
[end
].m_start
;
1343 /* Do not allow clusters with small number of cases. */
1344 if (is_beneficial (clusters
, start
, end
- 1))
1345 output
.safe_push (new jump_table_cluster (clusters
, start
, end
- 1));
1347 for (int i
= end
- 1; i
>= start
; i
--)
1348 output
.safe_push (clusters
[i
]);
1360 /* Return true when cluster starting at START and ending at END (inclusive)
1361 can build a jump-table. */
1364 jump_table_cluster::can_be_handled (const vec
<cluster
*> &clusters
,
1365 unsigned start
, unsigned end
,
1366 unsigned HOST_WIDE_INT max_ratio
,
1367 unsigned HOST_WIDE_INT comparison_count
)
1369 /* If the switch is relatively small such that the cost of one
1370 indirect jump on the target are higher than the cost of a
1371 decision tree, go with the decision tree.
1373 If range of values is much bigger than number of values,
1374 or if it is too large to represent in a HOST_WIDE_INT,
1375 make a sequence of conditional branches instead of a dispatch.
1377 The definition of "much bigger" depends on whether we are
1378 optimizing for size or for speed.
1380 For algorithm correctness, jump table for a single case must return
1381 true. We bail out in is_beneficial if it's called just for
1386 unsigned HOST_WIDE_INT range
= get_range (clusters
[start
]->get_low (),
1387 clusters
[end
]->get_high ());
1388 /* Check overflow. */
1392 if (range
> HOST_WIDE_INT_M1U
/ 100)
1395 unsigned HOST_WIDE_INT lhs
= 100 * range
;
1399 return lhs
<= max_ratio
* comparison_count
;
1402 /* Return true if cluster starting at START and ending at END (inclusive)
1403 is profitable transformation. */
1406 jump_table_cluster::is_beneficial (const vec
<cluster
*> &,
1407 unsigned start
, unsigned end
)
1409 /* Single case bail out. */
1413 return end
- start
+ 1 >= case_values_threshold ();
1416 /* Find bit tests of given CLUSTERS, where all members of the vector
1417 are of type simple_cluster. New clusters are returned. */
1420 bit_test_cluster::find_bit_tests (vec
<cluster
*> &clusters
)
1423 return clusters
.copy ();
1425 unsigned l
= clusters
.length ();
1426 auto_vec
<min_cluster_item
> min
;
1427 min
.reserve (l
+ 1);
1429 min
.quick_push (min_cluster_item (0, 0, 0));
1431 for (unsigned i
= 1; i
<= l
; i
++)
1433 /* Set minimal # of clusters with i-th item to infinite. */
1434 min
.quick_push (min_cluster_item (INT_MAX
, INT_MAX
, INT_MAX
));
1436 for (unsigned j
= 0; j
< i
; j
++)
1438 if (min
[j
].m_count
+ 1 < min
[i
].m_count
1439 && can_be_handled (clusters
, j
, i
- 1))
1440 min
[i
] = min_cluster_item (min
[j
].m_count
+ 1, j
, INT_MAX
);
1443 gcc_checking_assert (min
[i
].m_count
!= INT_MAX
);
1447 if (min
[l
].m_count
== l
)
1448 return clusters
.copy ();
1450 vec
<cluster
*> output
;
1453 /* Find and build the clusters. */
1454 for (unsigned end
= l
;;)
1456 int start
= min
[end
].m_start
;
1458 if (is_beneficial (clusters
, start
, end
- 1))
1460 bool entire
= start
== 0 && end
== clusters
.length ();
1461 output
.safe_push (new bit_test_cluster (clusters
, start
, end
- 1,
1465 for (int i
= end
- 1; i
>= start
; i
--)
1466 output
.safe_push (clusters
[i
]);
1478 /* Return true when RANGE of case values with UNIQ labels
1479 can build a bit test. */
1482 bit_test_cluster::can_be_handled (unsigned HOST_WIDE_INT range
,
1485 /* Check overflow. */
1489 if (range
>= GET_MODE_BITSIZE (word_mode
))
1492 return uniq
<= m_max_case_bit_tests
;
1495 /* Return true when cluster starting at START and ending at END (inclusive)
1496 can build a bit test. */
1499 bit_test_cluster::can_be_handled (const vec
<cluster
*> &clusters
,
1500 unsigned start
, unsigned end
)
1502 auto_vec
<int, m_max_case_bit_tests
> dest_bbs
;
1503 /* For algorithm correctness, bit test for a single case must return
1504 true. We bail out in is_beneficial if it's called just for
1509 unsigned HOST_WIDE_INT range
= get_range (clusters
[start
]->get_low (),
1510 clusters
[end
]->get_high ());
1512 /* Make a guess first. */
1513 if (!can_be_handled (range
, m_max_case_bit_tests
))
1516 for (unsigned i
= start
; i
<= end
; i
++)
1518 simple_cluster
*sc
= static_cast<simple_cluster
*> (clusters
[i
]);
1519 /* m_max_case_bit_tests is very small integer, thus the operation
1521 if (!dest_bbs
.contains (sc
->m_case_bb
->index
))
1523 if (dest_bbs
.length () >= m_max_case_bit_tests
)
1525 dest_bbs
.quick_push (sc
->m_case_bb
->index
);
1532 /* Return true when COUNT of cases of UNIQ labels is beneficial for bit test
1536 bit_test_cluster::is_beneficial (unsigned count
, unsigned uniq
)
1538 return (((uniq
== 1 && count
>= 3)
1539 || (uniq
== 2 && count
>= 5)
1540 || (uniq
== 3 && count
>= 6)));
1543 /* Return true if cluster starting at START and ending at END (inclusive)
1544 is profitable transformation. */
1547 bit_test_cluster::is_beneficial (const vec
<cluster
*> &clusters
,
1548 unsigned start
, unsigned end
)
1550 /* Single case bail out. */
1554 auto_bitmap dest_bbs
;
1556 for (unsigned i
= start
; i
<= end
; i
++)
1558 simple_cluster
*sc
= static_cast<simple_cluster
*> (clusters
[i
]);
1559 bitmap_set_bit (dest_bbs
, sc
->m_case_bb
->index
);
1562 unsigned uniq
= bitmap_count_bits (dest_bbs
);
1563 unsigned count
= end
- start
+ 1;
1564 return is_beneficial (count
, uniq
);
1567 /* Comparison function for qsort to order bit tests by decreasing
1568 probability of execution. */
1571 case_bit_test::cmp (const void *p1
, const void *p2
)
1573 const case_bit_test
*const d1
= (const case_bit_test
*) p1
;
1574 const case_bit_test
*const d2
= (const case_bit_test
*) p2
;
1576 if (d2
->bits
!= d1
->bits
)
1577 return d2
->bits
- d1
->bits
;
1579 /* Stabilize the sort. */
1580 return (LABEL_DECL_UID (CASE_LABEL (d2
->label
))
1581 - LABEL_DECL_UID (CASE_LABEL (d1
->label
)));
1584 /* Expand a switch statement by a short sequence of bit-wise
1585 comparisons. "switch(x)" is effectively converted into
1586 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
1589 INDEX_EXPR is the value being switched on.
1591 MINVAL is the lowest case value of in the case nodes,
1592 and RANGE is highest value minus MINVAL. MINVAL and RANGE
1593 are not guaranteed to be of the same type as INDEX_EXPR
1594 (the gimplifier doesn't change the type of case label values,
1595 and MINVAL and RANGE are derived from those values).
1596 MAXVAL is MINVAL + RANGE.
1598 There *MUST* be max_case_bit_tests or less unique case
1602 bit_test_cluster::emit (tree index_expr
, tree index_type
,
1603 tree
, basic_block default_bb
, location_t loc
)
1605 case_bit_test test
[m_max_case_bit_tests
] = { {} };
1606 unsigned int i
, j
, k
;
1609 tree unsigned_index_type
= range_check_type (index_type
);
1611 gimple_stmt_iterator gsi
;
1612 gassign
*shift_stmt
;
1614 tree idx
, tmp
, csui
;
1615 tree word_type_node
= lang_hooks
.types
.type_for_mode (word_mode
, 1);
1616 tree word_mode_zero
= fold_convert (word_type_node
, integer_zero_node
);
1617 tree word_mode_one
= fold_convert (word_type_node
, integer_one_node
);
1618 int prec
= TYPE_PRECISION (word_type_node
);
1619 wide_int wone
= wi::one (prec
);
1621 tree minval
= get_low ();
1622 tree maxval
= get_high ();
1624 /* Go through all case labels, and collect the case labels, profile
1625 counts, and other information we need to build the branch tests. */
1627 for (i
= 0; i
< m_cases
.length (); i
++)
1629 unsigned int lo
, hi
;
1630 simple_cluster
*n
= static_cast<simple_cluster
*> (m_cases
[i
]);
1631 for (k
= 0; k
< count
; k
++)
1632 if (n
->m_case_bb
== test
[k
].target_bb
)
1637 gcc_checking_assert (count
< m_max_case_bit_tests
);
1638 test
[k
].mask
= wi::zero (prec
);
1639 test
[k
].target_bb
= n
->m_case_bb
;
1640 test
[k
].label
= n
->m_case_label_expr
;
1642 test
[k
].prob
= profile_probability::never ();
1646 test
[k
].bits
+= n
->get_range (n
->get_low (), n
->get_high ());
1647 test
[k
].prob
+= n
->m_prob
;
1649 lo
= tree_to_uhwi (int_const_binop (MINUS_EXPR
, n
->get_low (), minval
));
1650 if (n
->get_high () == NULL_TREE
)
1653 hi
= tree_to_uhwi (int_const_binop (MINUS_EXPR
, n
->get_high (),
1656 for (j
= lo
; j
<= hi
; j
++)
1657 test
[k
].mask
|= wi::lshift (wone
, j
);
1660 qsort (test
, count
, sizeof (*test
), case_bit_test::cmp
);
1662 /* If every possible relative value of the index expression is a valid shift
1663 amount, then we can merge the entry test in the bit test. */
1664 bool entry_test_needed
;
1666 if (TREE_CODE (index_expr
) == SSA_NAME
1667 && get_range_query (cfun
)->range_of_expr (r
, index_expr
)
1668 && !r
.undefined_p ()
1670 && wi::leu_p (r
.upper_bound () - r
.lower_bound (), prec
- 1))
1672 wide_int min
= r
.lower_bound ();
1673 wide_int max
= r
.upper_bound ();
1674 tree index_type
= TREE_TYPE (index_expr
);
1675 minval
= fold_convert (index_type
, minval
);
1676 wide_int iminval
= wi::to_wide (minval
);
1677 if (wi::lt_p (min
, iminval
, TYPE_SIGN (index_type
)))
1679 minval
= wide_int_to_tree (index_type
, min
);
1680 for (i
= 0; i
< count
; i
++)
1681 test
[i
].mask
= wi::lshift (test
[i
].mask
, iminval
- min
);
1683 else if (wi::gt_p (min
, iminval
, TYPE_SIGN (index_type
)))
1685 minval
= wide_int_to_tree (index_type
, min
);
1686 for (i
= 0; i
< count
; i
++)
1687 test
[i
].mask
= wi::lrshift (test
[i
].mask
, min
- iminval
);
1689 maxval
= wide_int_to_tree (index_type
, max
);
1690 entry_test_needed
= false;
1693 entry_test_needed
= true;
1695 /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of
1696 the minval subtractions, but it might make the mask constants more
1697 expensive. So, compare the costs. */
1698 if (compare_tree_int (minval
, 0) > 0 && compare_tree_int (maxval
, prec
) < 0)
1701 HOST_WIDE_INT m
= tree_to_uhwi (minval
);
1702 rtx reg
= gen_raw_REG (word_mode
, 10000);
1703 bool speed_p
= optimize_insn_for_speed_p ();
1704 cost_diff
= set_src_cost (gen_rtx_PLUS (word_mode
, reg
,
1706 word_mode
, speed_p
);
1707 for (i
= 0; i
< count
; i
++)
1709 rtx r
= immed_wide_int_const (test
[i
].mask
, word_mode
);
1710 cost_diff
+= set_src_cost (gen_rtx_AND (word_mode
, reg
, r
),
1711 word_mode
, speed_p
);
1712 r
= immed_wide_int_const (wi::lshift (test
[i
].mask
, m
), word_mode
);
1713 cost_diff
-= set_src_cost (gen_rtx_AND (word_mode
, reg
, r
),
1714 word_mode
, speed_p
);
1718 for (i
= 0; i
< count
; i
++)
1719 test
[i
].mask
= wi::lshift (test
[i
].mask
, m
);
1720 minval
= build_zero_cst (TREE_TYPE (minval
));
1724 /* Now build the test-and-branch code. */
1726 gsi
= gsi_last_bb (m_case_bb
);
1728 /* idx = (unsigned)x - minval. */
1729 idx
= fold_convert_loc (loc
, unsigned_index_type
, index_expr
);
1730 idx
= fold_build2_loc (loc
, MINUS_EXPR
, unsigned_index_type
, idx
,
1731 fold_convert_loc (loc
, unsigned_index_type
, minval
));
1732 idx
= force_gimple_operand_gsi (&gsi
, idx
,
1733 /*simple=*/true, NULL_TREE
,
1734 /*before=*/true, GSI_SAME_STMT
);
1736 profile_probability subtree_prob
= m_subtree_prob
;
1737 profile_probability default_prob
= m_default_prob
;
1738 if (!default_prob
.initialized_p ())
1739 default_prob
= m_subtree_prob
.invert ();
1741 if (m_handles_entire_switch
&& entry_test_needed
)
1743 tree range
= int_const_binop (MINUS_EXPR
, maxval
, minval
);
1744 /* if (idx > range) goto default */
1746 = force_gimple_operand_gsi (&gsi
,
1747 fold_convert (unsigned_index_type
, range
),
1748 /*simple=*/true, NULL_TREE
,
1749 /*before=*/true, GSI_SAME_STMT
);
1750 tmp
= fold_build2 (GT_EXPR
, boolean_type_node
, idx
, range
);
1751 default_prob
= default_prob
/ 2;
1753 = hoist_edge_and_branch_if_true (&gsi
, tmp
, default_bb
,
1755 gsi
= gsi_last_bb (new_bb
);
1758 tmp
= fold_build2_loc (loc
, LSHIFT_EXPR
, word_type_node
, word_mode_one
,
1759 fold_convert_loc (loc
, word_type_node
, idx
));
1761 /* csui = (1 << (word_mode) idx) */
1764 csui
= make_ssa_name (word_type_node
);
1765 tmp
= force_gimple_operand_gsi (&gsi
, tmp
,
1766 /*simple=*/false, NULL_TREE
,
1767 /*before=*/true, GSI_SAME_STMT
);
1768 shift_stmt
= gimple_build_assign (csui
, tmp
);
1769 gsi_insert_before (&gsi
, shift_stmt
, GSI_SAME_STMT
);
1770 update_stmt (shift_stmt
);
1775 /* for each unique set of cases:
1776 if (const & csui) goto target */
1777 for (k
= 0; k
< count
; k
++)
1779 profile_probability prob
= test
[k
].prob
/ (subtree_prob
+ default_prob
);
1780 subtree_prob
-= test
[k
].prob
;
1781 tmp
= wide_int_to_tree (word_type_node
, test
[k
].mask
);
1782 tmp
= fold_build2_loc (loc
, BIT_AND_EXPR
, word_type_node
, csui
, tmp
);
1783 tmp
= fold_build2_loc (loc
, NE_EXPR
, boolean_type_node
,
1784 tmp
, word_mode_zero
);
1785 tmp
= force_gimple_operand_gsi (&gsi
, tmp
,
1786 /*simple=*/true, NULL_TREE
,
1787 /*before=*/true, GSI_SAME_STMT
);
1789 = hoist_edge_and_branch_if_true (&gsi
, tmp
, test
[k
].target_bb
,
1791 gsi
= gsi_last_bb (new_bb
);
1794 /* We should have removed all edges now. */
1795 gcc_assert (EDGE_COUNT (gsi_bb (gsi
)->succs
) == 0);
1797 /* If nothing matched, go to the default label. */
1798 edge e
= make_edge (gsi_bb (gsi
), default_bb
, EDGE_FALLTHRU
);
1799 e
->probability
= profile_probability::always ();
1802 /* Split the basic block at the statement pointed to by GSIP, and insert
1803 a branch to the target basic block of E_TRUE conditional on tree
1806 It is assumed that there is already an edge from the to-be-split
1807 basic block to E_TRUE->dest block. This edge is removed, and the
1808 profile information on the edge is re-used for the new conditional
1811 The CFG is updated. The dominator tree will not be valid after
1812 this transformation, but the immediate dominators are updated if
1813 UPDATE_DOMINATORS is true.
1815 Returns the newly created basic block. */
1818 bit_test_cluster::hoist_edge_and_branch_if_true (gimple_stmt_iterator
*gsip
,
1819 tree cond
, basic_block case_bb
,
1820 profile_probability prob
,
1826 basic_block new_bb
, split_bb
= gsi_bb (*gsip
);
1828 edge e_true
= make_edge (split_bb
, case_bb
, EDGE_TRUE_VALUE
);
1829 e_true
->probability
= prob
;
1830 gcc_assert (e_true
->src
== split_bb
);
1832 tmp
= force_gimple_operand_gsi (gsip
, cond
, /*simple=*/true, NULL
,
1833 /*before=*/true, GSI_SAME_STMT
);
1834 cond_stmt
= gimple_build_cond_from_tree (tmp
, NULL_TREE
, NULL_TREE
);
1835 gimple_set_location (cond_stmt
, loc
);
1836 gsi_insert_before (gsip
, cond_stmt
, GSI_SAME_STMT
);
1838 e_false
= split_block (split_bb
, cond_stmt
);
1839 new_bb
= e_false
->dest
;
1840 redirect_edge_pred (e_true
, split_bb
);
1842 e_false
->flags
&= ~EDGE_FALLTHRU
;
1843 e_false
->flags
|= EDGE_FALSE_VALUE
;
1844 e_false
->probability
= e_true
->probability
.invert ();
1845 new_bb
->count
= e_false
->count ();
1850 /* Compute the number of case labels that correspond to each outgoing edge of
1851 switch statement. Record this information in the aux field of the edge. */
1854 switch_decision_tree::compute_cases_per_edge ()
1856 reset_out_edges_aux (m_switch
);
1857 int ncases
= gimple_switch_num_labels (m_switch
);
1858 for (int i
= ncases
- 1; i
>= 1; --i
)
1860 edge case_edge
= gimple_switch_edge (cfun
, m_switch
, i
);
1861 case_edge
->aux
= (void *) ((intptr_t) (case_edge
->aux
) + 1);
1865 /* Analyze switch statement and return true when the statement is expanded
1866 as decision tree. */
1869 switch_decision_tree::analyze_switch_statement ()
1871 unsigned l
= gimple_switch_num_labels (m_switch
);
1872 basic_block bb
= gimple_bb (m_switch
);
1873 auto_vec
<cluster
*> clusters
;
1874 clusters
.create (l
- 1);
1876 basic_block default_bb
= gimple_switch_default_bb (cfun
, m_switch
);
1877 m_case_bbs
.reserve (l
);
1878 m_case_bbs
.quick_push (default_bb
);
1880 compute_cases_per_edge ();
1882 for (unsigned i
= 1; i
< l
; i
++)
1884 tree elt
= gimple_switch_label (m_switch
, i
);
1885 tree lab
= CASE_LABEL (elt
);
1886 basic_block case_bb
= label_to_block (cfun
, lab
);
1887 edge case_edge
= find_edge (bb
, case_bb
);
1888 tree low
= CASE_LOW (elt
);
1889 tree high
= CASE_HIGH (elt
);
1891 profile_probability p
1892 = case_edge
->probability
/ ((intptr_t) (case_edge
->aux
));
1893 clusters
.quick_push (new simple_cluster (low
, high
, elt
, case_edge
->dest
,
1895 m_case_bbs
.quick_push (case_edge
->dest
);
1898 reset_out_edges_aux (m_switch
);
1900 /* Find bit-test clusters. */
1901 vec
<cluster
*> output
= bit_test_cluster::find_bit_tests (clusters
);
1903 /* Find jump table clusters. */
1904 vec
<cluster
*> output2
;
1905 auto_vec
<cluster
*> tmp
;
1909 for (unsigned i
= 0; i
< output
.length (); i
++)
1911 cluster
*c
= output
[i
];
1912 if (c
->get_type () != SIMPLE_CASE
)
1914 if (!tmp
.is_empty ())
1916 vec
<cluster
*> n
= jump_table_cluster::find_jump_tables (tmp
);
1917 output2
.safe_splice (n
);
1921 output2
.safe_push (c
);
1927 /* We still can have a temporary vector to test. */
1928 if (!tmp
.is_empty ())
1930 vec
<cluster
*> n
= jump_table_cluster::find_jump_tables (tmp
);
1931 output2
.safe_splice (n
);
1937 fprintf (dump_file
, ";; GIMPLE switch case clusters: ");
1938 for (unsigned i
= 0; i
< output2
.length (); i
++)
1939 output2
[i
]->dump (dump_file
, dump_flags
& TDF_DETAILS
);
1940 fprintf (dump_file
, "\n");
1945 bool expanded
= try_switch_expansion (output2
);
1946 release_clusters (output2
);
1950 /* Attempt to expand CLUSTERS as a decision tree. Return true when
1954 switch_decision_tree::try_switch_expansion (vec
<cluster
*> &clusters
)
1956 tree index_expr
= gimple_switch_index (m_switch
);
1957 tree index_type
= TREE_TYPE (index_expr
);
1958 basic_block bb
= gimple_bb (m_switch
);
1960 if (gimple_switch_num_labels (m_switch
) == 1
1961 || range_check_type (index_type
) == NULL_TREE
)
1964 /* Find the default case target label. */
1965 edge default_edge
= gimple_switch_default_edge (cfun
, m_switch
);
1966 m_default_bb
= default_edge
->dest
;
1968 /* Do the insertion of a case label into m_case_list. The labels are
1969 fed to us in descending order from the sorted vector of case labels used
1970 in the tree part of the middle end. So the list we construct is
1971 sorted in ascending order. */
1973 for (int i
= clusters
.length () - 1; i
>= 0; i
--)
1975 case_tree_node
*r
= m_case_list
;
1976 m_case_list
= m_case_node_pool
.allocate ();
1977 m_case_list
->m_right
= r
;
1978 m_case_list
->m_c
= clusters
[i
];
1981 record_phi_operand_mapping ();
1983 /* Split basic block that contains the gswitch statement. */
1984 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1986 if (gsi_end_p (gsi
))
1987 e
= split_block_after_labels (bb
);
1991 e
= split_block (bb
, gsi_stmt (gsi
));
1993 bb
= split_edge (e
);
1995 /* Create new basic blocks for non-case clusters where specific expansion
1997 for (unsigned i
= 0; i
< clusters
.length (); i
++)
1998 if (clusters
[i
]->get_type () != SIMPLE_CASE
)
2000 clusters
[i
]->m_case_bb
= create_empty_bb (bb
);
2001 clusters
[i
]->m_case_bb
->count
= bb
->count
;
2002 clusters
[i
]->m_case_bb
->loop_father
= bb
->loop_father
;
2005 /* Do not do an extra work for a single cluster. */
2006 if (clusters
.length () == 1
2007 && clusters
[0]->get_type () != SIMPLE_CASE
)
2009 cluster
*c
= clusters
[0];
2010 c
->emit (index_expr
, index_type
,
2011 gimple_switch_default_label (m_switch
), m_default_bb
,
2012 gimple_location (m_switch
));
2013 redirect_edge_succ (single_succ_edge (bb
), c
->m_case_bb
);
2017 emit (bb
, index_expr
, default_edge
->probability
, index_type
);
2019 /* Emit cluster-specific switch handling. */
2020 for (unsigned i
= 0; i
< clusters
.length (); i
++)
2021 if (clusters
[i
]->get_type () != SIMPLE_CASE
)
2023 edge e
= single_pred_edge (clusters
[i
]->m_case_bb
);
2024 e
->dest
->count
= e
->src
->count
.apply_probability (e
->probability
);
2025 clusters
[i
]->emit (index_expr
, index_type
,
2026 gimple_switch_default_label (m_switch
),
2027 m_default_bb
, gimple_location (m_switch
));
2031 fix_phi_operands_for_edges ();
2036 /* Before switch transformation, record all SSA_NAMEs defined in switch BB
2037 and used in a label basic block. */
2040 switch_decision_tree::record_phi_operand_mapping ()
2042 basic_block switch_bb
= gimple_bb (m_switch
);
2043 /* Record all PHI nodes that have to be fixed after conversion. */
2044 for (unsigned i
= 0; i
< m_case_bbs
.length (); i
++)
2047 basic_block bb
= m_case_bbs
[i
];
2048 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2050 gphi
*phi
= gsi
.phi ();
2052 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2054 basic_block phi_src_bb
= gimple_phi_arg_edge (phi
, i
)->src
;
2055 if (phi_src_bb
== switch_bb
)
2057 tree def
= gimple_phi_arg_def (phi
, i
);
2058 tree result
= gimple_phi_result (phi
);
2059 m_phi_mapping
.put (result
, def
);
2067 /* Append new operands to PHI statements that were introduced due to
2068 addition of new edges to case labels. */
2071 switch_decision_tree::fix_phi_operands_for_edges ()
2075 for (unsigned i
= 0; i
< m_case_bbs
.length (); i
++)
2077 basic_block bb
= m_case_bbs
[i
];
2078 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2080 gphi
*phi
= gsi
.phi ();
2081 for (unsigned j
= 0; j
< gimple_phi_num_args (phi
); j
++)
2083 tree def
= gimple_phi_arg_def (phi
, j
);
2084 if (def
== NULL_TREE
)
2086 edge e
= gimple_phi_arg_edge (phi
, j
);
2088 = m_phi_mapping
.get (gimple_phi_result (phi
));
2089 gcc_assert (definition
);
2090 add_phi_arg (phi
, *definition
, e
, UNKNOWN_LOCATION
);
2097 /* Generate a decision tree, switching on INDEX_EXPR and jumping to
2098 one of the labels in CASE_LIST or to the DEFAULT_LABEL.
2100 We generate a binary decision tree to select the appropriate target
2104 switch_decision_tree::emit (basic_block bb
, tree index_expr
,
2105 profile_probability default_prob
, tree index_type
)
2107 balance_case_nodes (&m_case_list
, NULL
);
2110 dump_function_to_file (current_function_decl
, dump_file
, dump_flags
);
2111 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2113 int indent_step
= ceil_log2 (TYPE_PRECISION (index_type
)) + 2;
2114 fprintf (dump_file
, ";; Expanding GIMPLE switch as decision tree:\n");
2115 gcc_assert (m_case_list
!= NULL
);
2116 dump_case_nodes (dump_file
, m_case_list
, indent_step
, 0);
2119 bb
= emit_case_nodes (bb
, index_expr
, m_case_list
, default_prob
, index_type
,
2120 gimple_location (m_switch
));
2123 emit_jump (bb
, m_default_bb
);
2125 /* Remove all edges and do just an edge that will reach default_bb. */
2126 bb
= gimple_bb (m_switch
);
2127 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2128 gsi_remove (&gsi
, true);
2130 delete_basic_block (bb
);
2133 /* Take an ordered list of case nodes
2134 and transform them into a near optimal binary tree,
2135 on the assumption that any target code selection value is as
2136 likely as any other.
2138 The transformation is performed by splitting the ordered
2139 list into two equal sections plus a pivot. The parts are
2140 then attached to the pivot as left and right branches. Each
2141 branch is then transformed recursively. */
2144 switch_decision_tree::balance_case_nodes (case_tree_node
**head
,
2145 case_tree_node
*parent
)
2153 case_tree_node
**npp
;
2154 case_tree_node
*left
;
2155 profile_probability prob
= profile_probability::never ();
2157 /* Count the number of entries on branch. */
2162 prob
+= np
->m_c
->m_prob
;
2168 /* Split this list if it is long enough for that to help. */
2171 profile_probability pivot_prob
= prob
/ 2;
2173 /* Find the place in the list that bisects the list's total cost
2177 /* Skip nodes while their probability does not reach
2179 prob
-= (*npp
)->m_c
->m_prob
;
2180 if ((prob
.initialized_p () && prob
< pivot_prob
)
2181 || ! (*npp
)->m_right
)
2183 npp
= &(*npp
)->m_right
;
2189 np
->m_parent
= parent
;
2190 np
->m_left
= left
== np
? NULL
: left
;
2192 /* Optimize each of the two split parts. */
2193 balance_case_nodes (&np
->m_left
, np
);
2194 balance_case_nodes (&np
->m_right
, np
);
2195 np
->m_c
->m_subtree_prob
= np
->m_c
->m_prob
;
2197 np
->m_c
->m_subtree_prob
+= np
->m_left
->m_c
->m_subtree_prob
;
2199 np
->m_c
->m_subtree_prob
+= np
->m_right
->m_c
->m_subtree_prob
;
2203 /* Else leave this branch as one level,
2204 but fill in `parent' fields. */
2206 np
->m_parent
= parent
;
2207 np
->m_c
->m_subtree_prob
= np
->m_c
->m_prob
;
2208 for (; np
->m_right
; np
= np
->m_right
)
2210 np
->m_right
->m_parent
= np
;
2211 (*head
)->m_c
->m_subtree_prob
+= np
->m_right
->m_c
->m_subtree_prob
;
2217 /* Dump ROOT, a list or tree of case nodes, to file. */
2220 switch_decision_tree::dump_case_nodes (FILE *f
, case_tree_node
*root
,
2221 int indent_step
, int indent_level
)
2227 dump_case_nodes (f
, root
->m_left
, indent_step
, indent_level
);
2230 fprintf (f
, "%*s", indent_step
* indent_level
, "");
2231 root
->m_c
->dump (f
);
2232 root
->m_c
->m_prob
.dump (f
);
2233 fputs (" subtree: ", f
);
2234 root
->m_c
->m_subtree_prob
.dump (f
);
2237 dump_case_nodes (f
, root
->m_right
, indent_step
, indent_level
);
2241 /* Add an unconditional jump to CASE_BB that happens in basic block BB. */
2244 switch_decision_tree::emit_jump (basic_block bb
, basic_block case_bb
)
2246 edge e
= single_succ_edge (bb
);
2247 redirect_edge_succ (e
, case_bb
);
2250 /* Generate code to compare OP0 with OP1 so that the condition codes are
2251 set and to jump to LABEL_BB if the condition is true.
2252 COMPARISON is the GIMPLE comparison (EQ, NE, GT, etc.).
2253 PROB is the probability of jumping to LABEL_BB. */
2256 switch_decision_tree::emit_cmp_and_jump_insns (basic_block bb
, tree op0
,
2257 tree op1
, tree_code comparison
,
2258 basic_block label_bb
,
2259 profile_probability prob
,
2262 // TODO: it's once called with lhs != index.
2263 op1
= fold_convert (TREE_TYPE (op0
), op1
);
2265 gcond
*cond
= gimple_build_cond (comparison
, op0
, op1
, NULL_TREE
, NULL_TREE
);
2266 gimple_set_location (cond
, loc
);
2267 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2268 gsi_insert_after (&gsi
, cond
, GSI_NEW_STMT
);
2270 gcc_assert (single_succ_p (bb
));
2272 /* Make a new basic block where false branch will take place. */
2273 edge false_edge
= split_block (bb
, cond
);
2274 false_edge
->flags
= EDGE_FALSE_VALUE
;
2275 false_edge
->probability
= prob
.invert ();
2276 false_edge
->dest
->count
= bb
->count
.apply_probability (prob
.invert ());
2278 edge true_edge
= make_edge (bb
, label_bb
, EDGE_TRUE_VALUE
);
2279 true_edge
->probability
= prob
;
2281 return false_edge
->dest
;
2284 /* Generate code to jump to LABEL if OP0 and OP1 are equal.
2285 PROB is the probability of jumping to LABEL_BB.
2286 BB is a basic block where the new condition will be placed. */
2289 switch_decision_tree::do_jump_if_equal (basic_block bb
, tree op0
, tree op1
,
2290 basic_block label_bb
,
2291 profile_probability prob
,
2294 op1
= fold_convert (TREE_TYPE (op0
), op1
);
2296 gcond
*cond
= gimple_build_cond (EQ_EXPR
, op0
, op1
, NULL_TREE
, NULL_TREE
);
2297 gimple_set_location (cond
, loc
);
2298 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2299 gsi_insert_before (&gsi
, cond
, GSI_SAME_STMT
);
2301 gcc_assert (single_succ_p (bb
));
2303 /* Make a new basic block where false branch will take place. */
2304 edge false_edge
= split_block (bb
, cond
);
2305 false_edge
->flags
= EDGE_FALSE_VALUE
;
2306 false_edge
->probability
= prob
.invert ();
2307 false_edge
->dest
->count
= bb
->count
.apply_probability (prob
.invert ());
2309 edge true_edge
= make_edge (bb
, label_bb
, EDGE_TRUE_VALUE
);
2310 true_edge
->probability
= prob
;
2312 return false_edge
->dest
;
2315 /* Emit step-by-step code to select a case for the value of INDEX.
2316 The thus generated decision tree follows the form of the
2317 case-node binary tree NODE, whose nodes represent test conditions.
2318 DEFAULT_PROB is probability of cases leading to default BB.
2319 INDEX_TYPE is the type of the index of the switch. */
2322 switch_decision_tree::emit_case_nodes (basic_block bb
, tree index
,
2323 case_tree_node
*node
,
2324 profile_probability default_prob
,
2325 tree index_type
, location_t loc
)
2327 profile_probability p
;
2329 /* If node is null, we are done. */
2333 /* Single value case. */
2334 if (node
->m_c
->is_single_value_p ())
2336 /* Node is single valued. First see if the index expression matches
2337 this node and then check our children, if any. */
2338 p
= node
->m_c
->m_prob
/ (node
->m_c
->m_subtree_prob
+ default_prob
);
2339 bb
= do_jump_if_equal (bb
, index
, node
->m_c
->get_low (),
2340 node
->m_c
->m_case_bb
, p
, loc
);
2341 /* Since this case is taken at this point, reduce its weight from
2343 node
->m_c
->m_subtree_prob
-= node
->m_c
->m_prob
;
2345 if (node
->m_left
!= NULL
&& node
->m_right
!= NULL
)
2347 /* 1) the node has both children
2349 If both children are single-valued cases with no
2350 children, finish up all the work. This way, we can save
2351 one ordered comparison. */
2353 if (!node
->m_left
->has_child ()
2354 && node
->m_left
->m_c
->is_single_value_p ()
2355 && !node
->m_right
->has_child ()
2356 && node
->m_right
->m_c
->is_single_value_p ())
2358 p
= (node
->m_right
->m_c
->m_prob
2359 / (node
->m_c
->m_subtree_prob
+ default_prob
));
2360 bb
= do_jump_if_equal (bb
, index
, node
->m_right
->m_c
->get_low (),
2361 node
->m_right
->m_c
->m_case_bb
, p
, loc
);
2362 node
->m_c
->m_subtree_prob
-= node
->m_right
->m_c
->m_prob
;
2364 p
= (node
->m_left
->m_c
->m_prob
2365 / (node
->m_c
->m_subtree_prob
+ default_prob
));
2366 bb
= do_jump_if_equal (bb
, index
, node
->m_left
->m_c
->get_low (),
2367 node
->m_left
->m_c
->m_case_bb
, p
, loc
);
2371 /* Branch to a label where we will handle it later. */
2372 basic_block test_bb
= split_edge (single_succ_edge (bb
));
2373 redirect_edge_succ (single_pred_edge (test_bb
),
2374 single_succ_edge (bb
)->dest
);
2376 p
= ((node
->m_right
->m_c
->m_subtree_prob
+ default_prob
/ 2)
2377 / (node
->m_c
->m_subtree_prob
+ default_prob
));
2378 test_bb
->count
= bb
->count
.apply_probability (p
);
2379 bb
= emit_cmp_and_jump_insns (bb
, index
, node
->m_c
->get_high (),
2380 GT_EXPR
, test_bb
, p
, loc
);
2383 /* Handle the left-hand subtree. */
2384 bb
= emit_case_nodes (bb
, index
, node
->m_left
,
2385 default_prob
, index_type
, loc
);
2387 /* If the left-hand subtree fell through,
2388 don't let it fall into the right-hand subtree. */
2389 if (bb
&& m_default_bb
)
2390 emit_jump (bb
, m_default_bb
);
2392 bb
= emit_case_nodes (test_bb
, index
, node
->m_right
,
2393 default_prob
, index_type
, loc
);
2396 else if (node
->m_left
== NULL
&& node
->m_right
!= NULL
)
2398 /* 2) the node has only right child. */
2400 /* Here we have a right child but no left so we issue a conditional
2401 branch to default and process the right child.
2403 Omit the conditional branch to default if the right child
2404 does not have any children and is single valued; it would
2405 cost too much space to save so little time. */
2407 if (node
->m_right
->has_child ()
2408 || !node
->m_right
->m_c
->is_single_value_p ())
2410 p
= ((default_prob
/ 2)
2411 / (node
->m_c
->m_subtree_prob
+ default_prob
));
2412 bb
= emit_cmp_and_jump_insns (bb
, index
, node
->m_c
->get_low (),
2413 LT_EXPR
, m_default_bb
, p
, loc
);
2416 bb
= emit_case_nodes (bb
, index
, node
->m_right
, default_prob
,
2421 /* We cannot process node->right normally
2422 since we haven't ruled out the numbers less than
2423 this node's value. So handle node->right explicitly. */
2424 p
= (node
->m_right
->m_c
->m_subtree_prob
2425 / (node
->m_c
->m_subtree_prob
+ default_prob
));
2426 bb
= do_jump_if_equal (bb
, index
, node
->m_right
->m_c
->get_low (),
2427 node
->m_right
->m_c
->m_case_bb
, p
, loc
);
2430 else if (node
->m_left
!= NULL
&& node
->m_right
== NULL
)
2432 /* 3) just one subtree, on the left. Similar case as previous. */
2434 if (node
->m_left
->has_child ()
2435 || !node
->m_left
->m_c
->is_single_value_p ())
2437 p
= ((default_prob
/ 2)
2438 / (node
->m_c
->m_subtree_prob
+ default_prob
));
2439 bb
= emit_cmp_and_jump_insns (bb
, index
, node
->m_c
->get_high (),
2440 GT_EXPR
, m_default_bb
, p
, loc
);
2443 bb
= emit_case_nodes (bb
, index
, node
->m_left
, default_prob
,
2448 /* We cannot process node->left normally
2449 since we haven't ruled out the numbers less than
2450 this node's value. So handle node->left explicitly. */
2451 p
= (node
->m_left
->m_c
->m_subtree_prob
2452 / (node
->m_c
->m_subtree_prob
+ default_prob
));
2453 bb
= do_jump_if_equal (bb
, index
, node
->m_left
->m_c
->get_low (),
2454 node
->m_left
->m_c
->m_case_bb
, p
, loc
);
2460 /* Node is a range. These cases are very similar to those for a single
2461 value, except that we do not start by testing whether this node
2462 is the one to branch to. */
2463 if (node
->has_child () || node
->m_c
->get_type () != SIMPLE_CASE
)
2465 bool is_bt
= node
->m_c
->get_type () == BIT_TEST
;
2466 int parts
= is_bt
? 3 : 2;
2468 /* Branch to a label where we will handle it later. */
2469 basic_block test_bb
= split_edge (single_succ_edge (bb
));
2470 redirect_edge_succ (single_pred_edge (test_bb
),
2471 single_succ_edge (bb
)->dest
);
2473 profile_probability right_prob
= profile_probability::never ();
2475 right_prob
= node
->m_right
->m_c
->m_subtree_prob
;
2476 p
= ((right_prob
+ default_prob
/ parts
)
2477 / (node
->m_c
->m_subtree_prob
+ default_prob
));
2478 test_bb
->count
= bb
->count
.apply_probability (p
);
2480 bb
= emit_cmp_and_jump_insns (bb
, index
, node
->m_c
->get_high (),
2481 GT_EXPR
, test_bb
, p
, loc
);
2483 default_prob
/= parts
;
2484 node
->m_c
->m_subtree_prob
-= right_prob
;
2486 node
->m_c
->m_default_prob
= default_prob
;
2488 /* Value belongs to this node or to the left-hand subtree. */
2489 p
= node
->m_c
->m_prob
/ (node
->m_c
->m_subtree_prob
+ default_prob
);
2490 bb
= emit_cmp_and_jump_insns (bb
, index
, node
->m_c
->get_low (),
2491 GE_EXPR
, node
->m_c
->m_case_bb
, p
, loc
);
2493 /* Handle the left-hand subtree. */
2494 bb
= emit_case_nodes (bb
, index
, node
->m_left
, default_prob
,
2497 /* If the left-hand subtree fell through,
2498 don't let it fall into the right-hand subtree. */
2499 if (bb
&& m_default_bb
)
2500 emit_jump (bb
, m_default_bb
);
2502 bb
= emit_case_nodes (test_bb
, index
, node
->m_right
, default_prob
,
2507 /* Node has no children so we check low and high bounds to remove
2508 redundant tests. Only one of the bounds can exist,
2509 since otherwise this node is bounded--a case tested already. */
2511 generate_range_test (bb
, index
, node
->m_c
->get_low (),
2512 node
->m_c
->get_high (), &lhs
, &rhs
);
2513 p
= default_prob
/ (node
->m_c
->m_subtree_prob
+ default_prob
);
2515 bb
= emit_cmp_and_jump_insns (bb
, lhs
, rhs
, GT_EXPR
,
2516 m_default_bb
, p
, loc
);
2518 emit_jump (bb
, node
->m_c
->m_case_bb
);
2526 /* The main function of the pass scans statements for switches and invokes
2527 process_switch on them. */
2531 const pass_data pass_data_convert_switch
=
2533 GIMPLE_PASS
, /* type */
2534 "switchconv", /* name */
2535 OPTGROUP_NONE
, /* optinfo_flags */
2536 TV_TREE_SWITCH_CONVERSION
, /* tv_id */
2537 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2538 0, /* properties_provided */
2539 0, /* properties_destroyed */
2540 0, /* todo_flags_start */
2541 TODO_update_ssa
, /* todo_flags_finish */
2544 class pass_convert_switch
: public gimple_opt_pass
2547 pass_convert_switch (gcc::context
*ctxt
)
2548 : gimple_opt_pass (pass_data_convert_switch
, ctxt
)
2551 /* opt_pass methods: */
2552 bool gate (function
*) final override
2554 return flag_tree_switch_conversion
!= 0;
2556 unsigned int execute (function
*) final override
;
2558 }; // class pass_convert_switch
2561 pass_convert_switch::execute (function
*fun
)
2564 bool cfg_altered
= false;
2566 FOR_EACH_BB_FN (bb
, fun
)
2568 if (gswitch
*stmt
= safe_dyn_cast
<gswitch
*> (*gsi_last_bb (bb
)))
2572 expanded_location loc
= expand_location (gimple_location (stmt
));
2574 fprintf (dump_file
, "beginning to process the following "
2575 "SWITCH statement (%s:%d) : ------- \n",
2576 loc
.file
, loc
.line
);
2577 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2578 putc ('\n', dump_file
);
2581 switch_conversion sconv
;
2582 sconv
.expand (stmt
);
2583 cfg_altered
|= sconv
.m_cfg_altered
;
2584 if (!sconv
.m_reason
)
2588 fputs ("Switch converted\n", dump_file
);
2589 fputs ("--------------------------------\n", dump_file
);
2592 /* Make no effort to update the post-dominator tree.
2593 It is actually not that hard for the transformations
2594 we have performed, but it is not supported
2595 by iterate_fix_dominators. */
2596 free_dominance_info (CDI_POST_DOMINATORS
);
2602 fputs ("Bailing out - ", dump_file
);
2603 fputs (sconv
.m_reason
, dump_file
);
2604 fputs ("\n--------------------------------\n", dump_file
);
2610 return cfg_altered
? TODO_cleanup_cfg
: 0;;
2616 make_pass_convert_switch (gcc::context
*ctxt
)
2618 return new pass_convert_switch (ctxt
);
2621 /* The main function of the pass scans statements for switches and invokes
2622 process_switch on them. */
2626 template <bool O0
> class pass_lower_switch
: public gimple_opt_pass
2629 pass_lower_switch (gcc::context
*ctxt
) : gimple_opt_pass (data
, ctxt
) {}
2631 static const pass_data data
;
2633 clone () final override
2635 return new pass_lower_switch
<O0
> (m_ctxt
);
2639 gate (function
*) final override
2641 return !O0
|| !optimize
;
2644 unsigned int execute (function
*fun
) final override
;
2645 }; // class pass_lower_switch
2648 const pass_data pass_lower_switch
<O0
>::data
= {
2649 GIMPLE_PASS
, /* type */
2650 O0
? "switchlower_O0" : "switchlower", /* name */
2651 OPTGROUP_NONE
, /* optinfo_flags */
2652 TV_TREE_SWITCH_LOWERING
, /* tv_id */
2653 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2654 0, /* properties_provided */
2655 0, /* properties_destroyed */
2656 0, /* todo_flags_start */
2657 TODO_update_ssa
| TODO_cleanup_cfg
, /* todo_flags_finish */
2662 pass_lower_switch
<O0
>::execute (function
*fun
)
2665 bool expanded
= false;
2667 auto_vec
<gimple
*> switch_statements
;
2668 switch_statements
.create (1);
2670 FOR_EACH_BB_FN (bb
, fun
)
2672 if (gswitch
*swtch
= safe_dyn_cast
<gswitch
*> (*gsi_last_bb (bb
)))
2675 group_case_labels_stmt (swtch
);
2676 switch_statements
.safe_push (swtch
);
2680 for (unsigned i
= 0; i
< switch_statements
.length (); i
++)
2682 gimple
*stmt
= switch_statements
[i
];
2685 expanded_location loc
= expand_location (gimple_location (stmt
));
2687 fprintf (dump_file
, "beginning to process the following "
2688 "SWITCH statement (%s:%d) : ------- \n",
2689 loc
.file
, loc
.line
);
2690 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2691 putc ('\n', dump_file
);
2694 gswitch
*swtch
= dyn_cast
<gswitch
*> (stmt
);
2697 switch_decision_tree
dt (swtch
);
2698 expanded
|= dt
.analyze_switch_statement ();
2704 free_dominance_info (CDI_DOMINATORS
);
2705 free_dominance_info (CDI_POST_DOMINATORS
);
2706 mark_virtual_operands_for_renaming (cfun
);
2715 make_pass_lower_switch_O0 (gcc::context
*ctxt
)
2717 return new pass_lower_switch
<true> (ctxt
);
2720 make_pass_lower_switch (gcc::context
*ctxt
)
2722 return new pass_lower_switch
<false> (ctxt
);