1 /* If-elseif-else to switch conversion pass
2 Copyright (C) 2020 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* Algorithm of the pass runs in the following steps:
21 a) We walk basic blocks in DOMINATOR order so that we first reach
22 a first condition of a future switch.
23 b) We follow false edges of a if-else-chain and we record chain
24 of GIMPLE conditions. These blocks are only used for comparison
25 of a common SSA_NAME and we do not allow any side effect.
26 c) We remove all basic blocks (except first) of such chain and
27 GIMPLE switch replaces the condition in the first basic block.
28 d) We move all GIMPLE statements in the removed blocks into the
33 #include "coretypes.h"
38 #include "tree-pass.h"
40 #include "gimple-pretty-print.h"
41 #include "fold-const.h"
42 #include "gimple-iterator.h"
45 #include "tree-cfgcleanup.h"
47 #include "tree-ssa-loop.h"
48 #include "diagnostic.h"
50 #include "tree-into-ssa.h"
54 #include "alloc-pool.h"
55 #include "tree-switch-conversion.h"
56 #include "tree-ssa-reassoc.h"
58 using namespace tree_switch_conversion
;
62 typedef vec
<std::pair
<gphi
*, tree
>> mapping_vec
;
64 condition_info (gcond
*cond
): m_cond (cond
), m_bb (gimple_bb (cond
)),
65 m_forwarder_bb (NULL
), m_ranges (), m_true_edge (NULL
), m_false_edge (NULL
),
66 m_true_edge_phi_mapping (), m_false_edge_phi_mapping ()
71 /* Recond PHI mapping for an original edge E and save these into
73 void record_phi_mapping (edge e
, mapping_vec
*vec
);
77 basic_block m_forwarder_bb
;
78 vec
<range_entry
> m_ranges
;
81 mapping_vec m_true_edge_phi_mapping
;
82 mapping_vec m_false_edge_phi_mapping
;
85 /* Recond PHI mapping for an original edge E and save these into vector VEC. */
88 condition_info::record_phi_mapping (edge e
, mapping_vec
*vec
)
90 for (gphi_iterator gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
);
93 gphi
*phi
= gsi
.phi ();
94 if (!virtual_operand_p (gimple_phi_result (phi
)))
96 tree arg
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
97 vec
->safe_push (std::make_pair (phi
, arg
));
102 /* Master structure for one if to switch conversion candidate. */
106 /* Default constructor. */
107 if_chain (): m_entries ()
109 m_entries
.create (2);
112 /* Default destructor. */
115 m_entries
.release ();
118 /* Verify that all case ranges do not overlap. */
119 bool check_non_overlapping_cases ();
121 /* Return true when the switch can be expanded with a jump table or
122 a bit test (at least partially). */
123 bool is_beneficial ();
125 /* If chain entries. */
126 vec
<condition_info
*> m_entries
;
129 /* Compare two case ranges by minimum value. */
132 range_cmp (const void *a
, const void *b
)
134 const range_entry
*re1
= *(const range_entry
* const *) a
;
135 const range_entry
*re2
= *(const range_entry
* const *) b
;
137 return tree_int_cst_compare (re1
->low
, re2
->low
);
140 /* Verify that all case ranges do not overlap. */
143 if_chain::check_non_overlapping_cases ()
145 auto_vec
<range_entry
*> all_ranges
;
146 for (unsigned i
= 0; i
< m_entries
.length (); i
++)
147 for (unsigned j
= 0; j
< m_entries
[i
]->m_ranges
.length (); j
++)
148 all_ranges
.safe_push (&m_entries
[i
]->m_ranges
[j
]);
150 all_ranges
.qsort (range_cmp
);
152 for (unsigned i
= 0; i
< all_ranges
.length () - 1; i
++)
154 range_entry
*left
= all_ranges
[i
];
155 range_entry
*right
= all_ranges
[i
+ 1];
156 if (tree_int_cst_le (left
->low
, right
->low
)
157 && tree_int_cst_le (right
->low
, left
->high
))
164 /* Compare clusters by minimum value. */
167 cluster_cmp (const void *a
, const void *b
)
169 simple_cluster
*sc1
= *(simple_cluster
* const *) a
;
170 simple_cluster
*sc2
= *(simple_cluster
* const *) b
;
172 return tree_int_cst_compare (sc1
->get_low (), sc2
->get_high ());
175 /* Dump constructed CLUSTERS with prefix MESSAGE. */
178 dump_clusters (vec
<cluster
*> *clusters
, const char *message
)
182 fprintf (dump_file
, ";; %s: ", message
);
183 for (unsigned i
= 0; i
< clusters
->length (); i
++)
184 (*clusters
)[i
]->dump (dump_file
, dump_flags
& TDF_DETAILS
);
185 fprintf (dump_file
, "\n");
189 /* Return true when the switch can be expanded with a jump table or
190 a bit test (at least partially). */
193 if_chain::is_beneficial ()
195 profile_probability prob
= profile_probability::uninitialized ();
197 auto_vec
<cluster
*> clusters
;
198 clusters
.create (m_entries
.length ());
200 for (unsigned i
= 0; i
< m_entries
.length (); i
++)
202 condition_info
*info
= m_entries
[i
];
203 for (unsigned j
= 0; j
< info
->m_ranges
.length (); j
++)
205 range_entry
*range
= &info
->m_ranges
[j
];
206 basic_block bb
= info
->m_true_edge
->dest
;
207 bool has_forwarder
= !info
->m_true_edge_phi_mapping
.is_empty ();
208 clusters
.safe_push (new simple_cluster (range
->low
, range
->high
,
214 /* Sort clusters and merge them. */
215 auto_vec
<cluster
*> filtered_clusters
;
216 filtered_clusters
.create (16);
217 clusters
.qsort (cluster_cmp
);
218 simple_cluster
*left
= static_cast<simple_cluster
*> (clusters
[0]);
219 filtered_clusters
.safe_push (left
);
221 for (unsigned i
= 1; i
< clusters
.length (); i
++)
223 simple_cluster
*right
= static_cast<simple_cluster
*> (clusters
[i
]);
224 tree type
= TREE_TYPE (left
->get_low ());
225 if (!left
->m_has_forward_bb
226 && !right
->m_has_forward_bb
227 && left
->m_case_bb
== right
->m_case_bb
)
229 if (wi::eq_p (wi::to_wide (right
->get_low ()) - wi::to_wide
230 (left
->get_high ()), wi::one (TYPE_PRECISION (type
))))
232 left
->set_high (right
->get_high ());
237 left
= static_cast<simple_cluster
*> (clusters
[i
]);
238 filtered_clusters
.safe_push (left
);
241 dump_clusters (&filtered_clusters
, "Canonical GIMPLE case clusters");
243 vec
<cluster
*> output
244 = jump_table_cluster::find_jump_tables (filtered_clusters
);
245 bool r
= output
.length () < filtered_clusters
.length ();
247 dump_clusters (&output
, "JT can be built");
252 output
= bit_test_cluster::find_bit_tests (filtered_clusters
);
253 r
= output
.length () < filtered_clusters
.length ();
255 dump_clusters (&output
, "BT can be built");
260 /* Build case label with MIN and MAX values of a given basic block DEST. */
263 build_case_label (tree index_type
, tree min
, tree max
, basic_block dest
)
265 if (min
!= NULL_TREE
&& index_type
!= TREE_TYPE (min
))
266 min
= fold_convert (index_type
, min
);
267 if (max
!= NULL_TREE
&& index_type
!= TREE_TYPE (max
))
268 max
= fold_convert (index_type
, max
);
270 tree label
= gimple_block_label (dest
);
271 return build_case_label (min
, min
== max
? NULL_TREE
: max
, label
);
274 /* Compare two integer constants. */
277 label_cmp (const void *a
, const void *b
)
279 const_tree l1
= *(const const_tree
*) a
;
280 const_tree l2
= *(const const_tree
*) b
;
282 return tree_int_cst_compare (CASE_LOW (l1
), CASE_LOW (l2
));
285 /* Convert a given if CHAIN into a switch GIMPLE statement. */
288 convert_if_conditions_to_switch (if_chain
*chain
)
290 if (!dbg_cnt (if_to_switch
))
293 auto_vec
<tree
> labels
;
294 unsigned entries
= chain
->m_entries
.length ();
295 condition_info
*first_cond
= chain
->m_entries
[0];
296 condition_info
*last_cond
= chain
->m_entries
[entries
- 1];
298 edge default_edge
= last_cond
->m_false_edge
;
299 basic_block default_bb
= default_edge
->dest
;
301 gimple_stmt_iterator gsi
= gsi_for_stmt (first_cond
->m_cond
);
302 tree index_type
= TREE_TYPE (first_cond
->m_ranges
[0].exp
);
303 for (unsigned i
= 0; i
< entries
; i
++)
305 condition_info
*info
= chain
->m_entries
[i
];
306 basic_block case_bb
= info
->m_true_edge
->dest
;
308 /* Create a forwarder block if needed. */
309 if (!info
->m_true_edge_phi_mapping
.is_empty ())
311 info
->m_forwarder_bb
= split_edge (info
->m_true_edge
);
312 case_bb
= info
->m_forwarder_bb
;
315 for (unsigned j
= 0; j
< info
->m_ranges
.length (); j
++)
316 labels
.safe_push (build_case_label (index_type
,
317 info
->m_ranges
[j
].low
,
318 info
->m_ranges
[j
].high
,
320 default_bb
= info
->m_false_edge
->dest
;
324 remove_edge (first_cond
->m_true_edge
);
325 remove_edge (first_cond
->m_false_edge
);
328 delete_basic_block (info
->m_bb
);
330 make_edge (first_cond
->m_bb
, case_bb
, 0);
333 labels
.qsort (label_cmp
);
335 edge e
= find_edge (first_cond
->m_bb
, default_bb
);
337 e
= make_edge (first_cond
->m_bb
, default_bb
, 0);
339 = gimple_build_switch (first_cond
->m_ranges
[0].exp
,
340 build_case_label (index_type
, NULL_TREE
,
341 NULL_TREE
, default_bb
),
344 gsi_remove (&gsi
, true);
345 gsi_insert_before (&gsi
, s
, GSI_NEW_STMT
);
349 fprintf (dump_file
, "Expanded into a new gimple STMT: ");
350 print_gimple_stmt (dump_file
, s
, 0, TDF_SLIM
);
351 putc ('\n', dump_file
);
354 /* Fill up missing PHI node arguments. */
355 for (unsigned i
= 0; i
< chain
->m_entries
.length (); ++i
)
357 condition_info
*info
= chain
->m_entries
[i
];
358 for (unsigned j
= 0; j
< info
->m_true_edge_phi_mapping
.length (); ++j
)
360 std::pair
<gphi
*, tree
> item
= info
->m_true_edge_phi_mapping
[j
];
361 add_phi_arg (item
.first
, item
.second
,
362 single_succ_edge (info
->m_forwarder_bb
),
367 /* Fill up missing PHI nodes for the default BB. */
368 for (unsigned j
= 0; j
< last_cond
->m_false_edge_phi_mapping
.length (); ++j
)
370 std::pair
<gphi
*, tree
> item
= last_cond
->m_false_edge_phi_mapping
[j
];
371 add_phi_arg (item
.first
, item
.second
, e
, UNKNOWN_LOCATION
);
375 /* Identify an index variable used in BB in a GIMPLE condition.
376 Save information about the condition into CONDITIONS_IN_BBS. */
379 find_conditions (basic_block bb
,
380 hash_map
<basic_block
, condition_info
> *conditions_in_bbs
)
382 gimple_stmt_iterator gsi
= gsi_last_nondebug_bb (bb
);
386 gcond
*cond
= dyn_cast
<gcond
*> (gsi_stmt (gsi
));
390 if (!no_side_effect_bb (bb
))
393 tree lhs
= gimple_cond_lhs (cond
);
394 tree rhs
= gimple_cond_rhs (cond
);
395 tree_code code
= gimple_cond_code (cond
);
397 condition_info
info (cond
);
401 && TREE_CODE (lhs
) == SSA_NAME
402 && (def
= dyn_cast
<gassign
*> (SSA_NAME_DEF_STMT (lhs
))) != NULL
403 && integer_zerop (rhs
))
405 enum tree_code rhs_code
= gimple_assign_rhs_code (def
);
406 if (rhs_code
== BIT_IOR_EXPR
)
408 info
.m_ranges
.safe_grow (2, true);
409 init_range_entry (&info
.m_ranges
[0], gimple_assign_rhs1 (def
), NULL
);
410 init_range_entry (&info
.m_ranges
[1], gimple_assign_rhs2 (def
), NULL
);
415 info
.m_ranges
.safe_grow (1, true);
416 init_range_entry (&info
.m_ranges
[0], NULL_TREE
, cond
);
419 /* All identified ranges must have equal expression and IN_P flag. */
420 if (!info
.m_ranges
.is_empty ())
422 edge true_edge
, false_edge
;
423 tree expr
= info
.m_ranges
[0].exp
;
424 bool in_p
= info
.m_ranges
[0].in_p
;
426 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
427 info
.m_true_edge
= in_p
? true_edge
: false_edge
;
428 info
.m_false_edge
= in_p
? false_edge
: true_edge
;
430 for (unsigned i
= 0; i
< info
.m_ranges
.length (); ++i
)
431 if (info
.m_ranges
[i
].exp
== NULL_TREE
432 || !INTEGRAL_TYPE_P (TREE_TYPE (info
.m_ranges
[i
].exp
))
433 || info
.m_ranges
[i
].low
== NULL_TREE
434 || info
.m_ranges
[i
].high
== NULL_TREE
435 || (TYPE_PRECISION (TREE_TYPE (info
.m_ranges
[i
].low
))
436 != TYPE_PRECISION (TREE_TYPE (info
.m_ranges
[i
].high
))))
439 for (unsigned i
= 1; i
< info
.m_ranges
.length (); ++i
)
440 if (info
.m_ranges
[i
].exp
!= expr
441 || info
.m_ranges
[i
].in_p
!= in_p
)
444 info
.record_phi_mapping (info
.m_true_edge
,
445 &info
.m_true_edge_phi_mapping
);
446 info
.record_phi_mapping (info
.m_false_edge
,
447 &info
.m_false_edge_phi_mapping
);
448 conditions_in_bbs
->put (bb
, info
);
455 const pass_data pass_data_if_to_switch
=
457 GIMPLE_PASS
, /* type */
458 "iftoswitch", /* name */
459 OPTGROUP_NONE
, /* optinfo_flags */
460 TV_TREE_IF_TO_SWITCH
, /* tv_id */
461 ( PROP_cfg
| PROP_ssa
), /* properties_required */
462 0, /* properties_provided */
463 0, /* properties_destroyed */
464 0, /* todo_flags_start */
465 TODO_cleanup_cfg
| TODO_update_ssa
/* todo_flags_finish */
468 class pass_if_to_switch
: public gimple_opt_pass
471 pass_if_to_switch (gcc::context
*ctxt
)
472 : gimple_opt_pass (pass_data_if_to_switch
, ctxt
)
475 /* opt_pass methods: */
476 virtual bool gate (function
*)
478 return (jump_table_cluster::is_enabled ()
479 || bit_test_cluster::is_enabled ());
482 virtual unsigned int execute (function
*);
484 }; // class pass_if_to_switch
487 pass_if_to_switch::execute (function
*fun
)
489 auto_vec
<if_chain
*> all_candidates
;
490 hash_map
<basic_block
, condition_info
> conditions_in_bbs
;
493 FOR_EACH_BB_FN (bb
, fun
)
494 find_conditions (bb
, &conditions_in_bbs
);
496 if (conditions_in_bbs
.is_empty ())
499 int *rpo
= XNEWVEC (int, n_basic_blocks_for_fn (fun
));
500 unsigned n
= pre_and_rev_post_order_compute_fn (fun
, NULL
, rpo
, false);
502 auto_bitmap seen_bbs
;
503 for (int i
= n
- 1; i
>= 0; --i
)
505 basic_block bb
= BASIC_BLOCK_FOR_FN (fun
, rpo
[i
]);
506 if (bitmap_bit_p (seen_bbs
, bb
->index
))
509 bitmap_set_bit (seen_bbs
, bb
->index
);
510 condition_info
*info
= conditions_in_bbs
.get (bb
);
513 if_chain
*chain
= new if_chain ();
514 chain
->m_entries
.safe_push (info
);
515 /* Try to find a chain starting in this BB. */
518 if (!single_pred_p (gimple_bb (info
->m_cond
)))
520 edge e
= single_pred_edge (gimple_bb (info
->m_cond
));
521 condition_info
*info2
= conditions_in_bbs
.get (e
->src
);
522 if (!info2
|| info
->m_ranges
[0].exp
!= info2
->m_ranges
[0].exp
)
525 /* It is important that the blocks are linked through FALSE_EDGE.
526 For an expression of index != VALUE, true and false edges
528 if (info2
->m_false_edge
!= e
)
531 chain
->m_entries
.safe_push (info2
);
532 bitmap_set_bit (seen_bbs
, e
->src
->index
);
536 chain
->m_entries
.reverse ();
537 if (chain
->m_entries
.length () >= 2
538 && chain
->check_non_overlapping_cases ()
539 && chain
->is_beneficial ())
541 gcond
*cond
= chain
->m_entries
[0]->m_cond
;
542 if (dump_enabled_p ())
543 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, cond
,
544 "Condition chain with %d BBs "
545 "transformed into a switch statement.\n",
546 chain
->m_entries
.length ());
547 all_candidates
.safe_push (chain
);
552 for (unsigned i
= 0; i
< all_candidates
.length (); i
++)
554 convert_if_conditions_to_switch (all_candidates
[i
]);
555 delete all_candidates
[i
];
560 if (!all_candidates
.is_empty ())
562 free_dominance_info (CDI_DOMINATORS
);
563 mark_virtual_operands_for_renaming (fun
);
572 make_pass_if_to_switch (gcc::context
*ctxt
)
574 return new pass_if_to_switch (ctxt
);