1 /* If-elseif-else to switch conversion pass
2 Copyright (C) 2020-2021 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 auto_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 auto_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 tree arg
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
95 vec
->safe_push (std::make_pair (phi
, arg
));
99 /* Master structure for one if to switch conversion candidate. */
103 /* Default constructor. */
104 if_chain (): m_entries ()
106 m_entries
.create (2);
109 /* Default destructor. */
112 m_entries
.release ();
115 /* Verify that all case ranges do not overlap. */
116 bool check_non_overlapping_cases ();
118 /* Return true when the switch can be expanded with a jump table or
119 a bit test (at least partially). */
120 bool is_beneficial ();
122 /* If chain entries. */
123 vec
<condition_info
*> m_entries
;
126 /* Compare two case ranges by minimum value. */
129 range_cmp (const void *a
, const void *b
)
131 const range_entry
*re1
= *(const range_entry
* const *) a
;
132 const range_entry
*re2
= *(const range_entry
* const *) b
;
134 return tree_int_cst_compare (re1
->low
, re2
->low
);
137 /* Verify that all case ranges do not overlap. */
140 if_chain::check_non_overlapping_cases ()
142 auto_vec
<range_entry
*> all_ranges
;
143 for (unsigned i
= 0; i
< m_entries
.length (); i
++)
144 for (unsigned j
= 0; j
< m_entries
[i
]->m_ranges
.length (); j
++)
145 all_ranges
.safe_push (&m_entries
[i
]->m_ranges
[j
]);
147 all_ranges
.qsort (range_cmp
);
149 for (unsigned i
= 0; i
< all_ranges
.length () - 1; i
++)
151 range_entry
*left
= all_ranges
[i
];
152 range_entry
*right
= all_ranges
[i
+ 1];
153 if (tree_int_cst_le (left
->low
, right
->low
)
154 && tree_int_cst_le (right
->low
, left
->high
))
161 /* Compare clusters by minimum value. */
164 cluster_cmp (const void *a
, const void *b
)
166 simple_cluster
*sc1
= *(simple_cluster
* const *) a
;
167 simple_cluster
*sc2
= *(simple_cluster
* const *) b
;
169 return tree_int_cst_compare (sc1
->get_low (), sc2
->get_high ());
172 /* Dump constructed CLUSTERS with prefix MESSAGE. */
175 dump_clusters (vec
<cluster
*> *clusters
, const char *message
)
179 fprintf (dump_file
, ";; %s: ", message
);
180 for (unsigned i
= 0; i
< clusters
->length (); i
++)
181 (*clusters
)[i
]->dump (dump_file
, dump_flags
& TDF_DETAILS
);
182 fprintf (dump_file
, "\n");
186 /* Return true when the switch can be expanded with a jump table or
187 a bit test (at least partially). */
190 if_chain::is_beneficial ()
192 profile_probability prob
= profile_probability::uninitialized ();
194 auto_vec
<cluster
*> clusters
;
195 clusters
.create (m_entries
.length ());
197 for (unsigned i
= 0; i
< m_entries
.length (); i
++)
199 condition_info
*info
= m_entries
[i
];
200 for (unsigned j
= 0; j
< info
->m_ranges
.length (); j
++)
202 range_entry
*range
= &info
->m_ranges
[j
];
203 basic_block bb
= info
->m_true_edge
->dest
;
204 bool has_forwarder
= !info
->m_true_edge_phi_mapping
.is_empty ();
205 clusters
.safe_push (new simple_cluster (range
->low
, range
->high
,
211 /* Sort clusters and merge them. */
212 auto_vec
<cluster
*> filtered_clusters
;
213 filtered_clusters
.create (16);
214 clusters
.qsort (cluster_cmp
);
215 simple_cluster
*left
= static_cast<simple_cluster
*> (clusters
[0]);
216 filtered_clusters
.safe_push (left
);
218 for (unsigned i
= 1; i
< clusters
.length (); i
++)
220 simple_cluster
*right
= static_cast<simple_cluster
*> (clusters
[i
]);
221 tree type
= TREE_TYPE (left
->get_low ());
222 if (!left
->m_has_forward_bb
223 && !right
->m_has_forward_bb
224 && left
->m_case_bb
== right
->m_case_bb
)
226 if (wi::eq_p (wi::to_wide (right
->get_low ()) - wi::to_wide
227 (left
->get_high ()), wi::one (TYPE_PRECISION (type
))))
229 left
->set_high (right
->get_high ());
234 left
= static_cast<simple_cluster
*> (clusters
[i
]);
235 filtered_clusters
.safe_push (left
);
238 dump_clusters (&filtered_clusters
, "Canonical GIMPLE case clusters");
240 vec
<cluster
*> output
241 = jump_table_cluster::find_jump_tables (filtered_clusters
);
242 bool r
= output
.length () < filtered_clusters
.length ();
244 dump_clusters (&output
, "JT can be built");
249 output
= bit_test_cluster::find_bit_tests (filtered_clusters
);
250 r
= output
.length () < filtered_clusters
.length ();
252 dump_clusters (&output
, "BT can be built");
254 for (unsigned i
= 0; i
< output
.length (); i
++)
261 /* Build case label with MIN and MAX values of a given basic block DEST. */
264 build_case_label (tree index_type
, tree min
, tree max
, basic_block dest
)
266 if (min
!= NULL_TREE
&& index_type
!= TREE_TYPE (min
))
267 min
= fold_convert (index_type
, min
);
268 if (max
!= NULL_TREE
&& index_type
!= TREE_TYPE (max
))
269 max
= fold_convert (index_type
, max
);
271 tree label
= gimple_block_label (dest
);
272 return build_case_label (min
, min
== max
? NULL_TREE
: max
, label
);
275 /* Compare two integer constants. */
278 label_cmp (const void *a
, const void *b
)
280 const_tree l1
= *(const const_tree
*) a
;
281 const_tree l2
= *(const const_tree
*) b
;
283 return tree_int_cst_compare (CASE_LOW (l1
), CASE_LOW (l2
));
286 /* Convert a given if CHAIN into a switch GIMPLE statement. */
289 convert_if_conditions_to_switch (if_chain
*chain
)
291 if (!dbg_cnt (if_to_switch
))
294 auto_vec
<tree
> labels
;
295 unsigned entries
= chain
->m_entries
.length ();
296 condition_info
*first_cond
= chain
->m_entries
[0];
297 condition_info
*last_cond
= chain
->m_entries
[entries
- 1];
299 edge default_edge
= last_cond
->m_false_edge
;
300 basic_block default_bb
= default_edge
->dest
;
302 gimple_stmt_iterator gsi
= gsi_for_stmt (first_cond
->m_cond
);
303 tree index_type
= TREE_TYPE (first_cond
->m_ranges
[0].exp
);
304 for (unsigned i
= 0; i
< entries
; i
++)
306 condition_info
*info
= chain
->m_entries
[i
];
307 basic_block case_bb
= info
->m_true_edge
->dest
;
309 /* Create a forwarder block if needed. */
310 if (!info
->m_true_edge_phi_mapping
.is_empty ())
312 info
->m_forwarder_bb
= split_edge (info
->m_true_edge
);
313 case_bb
= info
->m_forwarder_bb
;
316 for (unsigned j
= 0; j
< info
->m_ranges
.length (); j
++)
317 labels
.safe_push (build_case_label (index_type
,
318 info
->m_ranges
[j
].low
,
319 info
->m_ranges
[j
].high
,
321 default_bb
= info
->m_false_edge
->dest
;
325 remove_edge (first_cond
->m_true_edge
);
326 remove_edge (first_cond
->m_false_edge
);
329 delete_basic_block (info
->m_bb
);
331 make_edge (first_cond
->m_bb
, case_bb
, 0);
334 labels
.qsort (label_cmp
);
336 edge e
= find_edge (first_cond
->m_bb
, default_bb
);
338 e
= make_edge (first_cond
->m_bb
, default_bb
, 0);
340 = gimple_build_switch (first_cond
->m_ranges
[0].exp
,
341 build_case_label (index_type
, NULL_TREE
,
342 NULL_TREE
, default_bb
),
345 gsi_remove (&gsi
, true);
346 gsi_insert_before (&gsi
, s
, GSI_NEW_STMT
);
350 fprintf (dump_file
, "Expanded into a new gimple STMT: ");
351 print_gimple_stmt (dump_file
, s
, 0, TDF_SLIM
);
352 putc ('\n', dump_file
);
355 /* Fill up missing PHI node arguments. */
356 for (unsigned i
= 0; i
< chain
->m_entries
.length (); ++i
)
358 condition_info
*info
= chain
->m_entries
[i
];
359 for (unsigned j
= 0; j
< info
->m_true_edge_phi_mapping
.length (); ++j
)
361 std::pair
<gphi
*, tree
> item
= info
->m_true_edge_phi_mapping
[j
];
362 add_phi_arg (item
.first
, item
.second
,
363 single_succ_edge (info
->m_forwarder_bb
),
368 /* Fill up missing PHI nodes for the default BB. */
369 for (unsigned j
= 0; j
< last_cond
->m_false_edge_phi_mapping
.length (); ++j
)
371 std::pair
<gphi
*, tree
> item
= last_cond
->m_false_edge_phi_mapping
[j
];
372 add_phi_arg (item
.first
, item
.second
, e
, UNKNOWN_LOCATION
);
376 /* Identify an index variable used in BB in a GIMPLE condition.
377 Save information about the condition into CONDITIONS_IN_BBS. */
380 find_conditions (basic_block bb
,
381 hash_map
<basic_block
, condition_info
*> *conditions_in_bbs
)
383 gimple_stmt_iterator gsi
= gsi_last_nondebug_bb (bb
);
387 gcond
*cond
= dyn_cast
<gcond
*> (gsi_stmt (gsi
));
391 if (!no_side_effect_bb (bb
))
394 tree lhs
= gimple_cond_lhs (cond
);
395 tree rhs
= gimple_cond_rhs (cond
);
396 tree_code code
= gimple_cond_code (cond
);
398 condition_info
*info
= new condition_info (cond
);
402 && TREE_CODE (lhs
) == SSA_NAME
403 && (def
= dyn_cast
<gassign
*> (SSA_NAME_DEF_STMT (lhs
))) != NULL
404 && integer_zerop (rhs
))
406 enum tree_code rhs_code
= gimple_assign_rhs_code (def
);
407 if (rhs_code
== BIT_IOR_EXPR
)
409 info
->m_ranges
.safe_grow (2, true);
410 init_range_entry (&info
->m_ranges
[0], gimple_assign_rhs1 (def
), NULL
);
411 init_range_entry (&info
->m_ranges
[1], gimple_assign_rhs2 (def
), NULL
);
416 info
->m_ranges
.safe_grow (1, true);
417 init_range_entry (&info
->m_ranges
[0], NULL_TREE
, cond
);
420 /* All identified ranges must have equal expression and IN_P flag. */
421 if (!info
->m_ranges
.is_empty ())
423 edge true_edge
, false_edge
;
424 tree expr
= info
->m_ranges
[0].exp
;
425 bool in_p
= info
->m_ranges
[0].in_p
;
427 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
428 info
->m_true_edge
= in_p
? true_edge
: false_edge
;
429 info
->m_false_edge
= in_p
? false_edge
: true_edge
;
431 for (unsigned i
= 0; i
< info
->m_ranges
.length (); ++i
)
432 if (info
->m_ranges
[i
].exp
== NULL_TREE
433 || !INTEGRAL_TYPE_P (TREE_TYPE (info
->m_ranges
[i
].exp
))
434 || info
->m_ranges
[i
].low
== NULL_TREE
435 || info
->m_ranges
[i
].high
== NULL_TREE
436 || (TYPE_PRECISION (TREE_TYPE (info
->m_ranges
[i
].low
))
437 != TYPE_PRECISION (TREE_TYPE (info
->m_ranges
[i
].high
))))
440 for (unsigned i
= 1; i
< info
->m_ranges
.length (); ++i
)
441 if (info
->m_ranges
[i
].exp
!= expr
442 || info
->m_ranges
[i
].in_p
!= in_p
)
445 info
->record_phi_mapping (info
->m_true_edge
,
446 &info
->m_true_edge_phi_mapping
);
447 info
->record_phi_mapping (info
->m_false_edge
,
448 &info
->m_false_edge_phi_mapping
);
449 conditions_in_bbs
->put (bb
, info
);
459 const pass_data pass_data_if_to_switch
=
461 GIMPLE_PASS
, /* type */
462 "iftoswitch", /* name */
463 OPTGROUP_NONE
, /* optinfo_flags */
464 TV_TREE_IF_TO_SWITCH
, /* tv_id */
465 ( PROP_cfg
| PROP_ssa
), /* properties_required */
466 0, /* properties_provided */
467 0, /* properties_destroyed */
468 0, /* todo_flags_start */
469 TODO_update_ssa
/* todo_flags_finish */
472 class pass_if_to_switch
: public gimple_opt_pass
475 pass_if_to_switch (gcc::context
*ctxt
)
476 : gimple_opt_pass (pass_data_if_to_switch
, ctxt
)
479 /* opt_pass methods: */
480 virtual bool gate (function
*)
482 return (jump_table_cluster::is_enabled ()
483 || bit_test_cluster::is_enabled ());
486 virtual unsigned int execute (function
*);
488 }; // class pass_if_to_switch
491 pass_if_to_switch::execute (function
*fun
)
493 auto_vec
<if_chain
*> all_candidates
;
494 hash_map
<basic_block
, condition_info
*> conditions_in_bbs
;
497 FOR_EACH_BB_FN (bb
, fun
)
498 find_conditions (bb
, &conditions_in_bbs
);
500 if (conditions_in_bbs
.is_empty ())
503 int *rpo
= XNEWVEC (int, n_basic_blocks_for_fn (fun
));
504 unsigned n
= pre_and_rev_post_order_compute_fn (fun
, NULL
, rpo
, false);
506 auto_bitmap seen_bbs
;
507 for (int i
= n
- 1; i
>= 0; --i
)
509 basic_block bb
= BASIC_BLOCK_FOR_FN (fun
, rpo
[i
]);
510 if (bitmap_bit_p (seen_bbs
, bb
->index
))
513 bitmap_set_bit (seen_bbs
, bb
->index
);
514 condition_info
**slot
= conditions_in_bbs
.get (bb
);
517 condition_info
*info
= *slot
;
518 if_chain
*chain
= new if_chain ();
519 chain
->m_entries
.safe_push (info
);
520 /* Try to find a chain starting in this BB. */
523 if (!single_pred_p (gimple_bb (info
->m_cond
)))
525 edge e
= single_pred_edge (gimple_bb (info
->m_cond
));
526 condition_info
**info2
= conditions_in_bbs
.get (e
->src
);
527 if (!info2
|| info
->m_ranges
[0].exp
!= (*info2
)->m_ranges
[0].exp
)
530 /* It is important that the blocks are linked through FALSE_EDGE.
531 For an expression of index != VALUE, true and false edges
533 if ((*info2
)->m_false_edge
!= e
)
536 chain
->m_entries
.safe_push (*info2
);
537 bitmap_set_bit (seen_bbs
, e
->src
->index
);
541 chain
->m_entries
.reverse ();
542 if (chain
->m_entries
.length () >= 2
543 && chain
->check_non_overlapping_cases ()
544 && chain
->is_beneficial ())
546 gcond
*cond
= chain
->m_entries
[0]->m_cond
;
547 if (dump_enabled_p ())
548 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, cond
,
549 "Condition chain with %d BBs "
550 "transformed into a switch statement.\n",
551 chain
->m_entries
.length ());
552 all_candidates
.safe_push (chain
);
559 for (unsigned i
= 0; i
< all_candidates
.length (); i
++)
561 convert_if_conditions_to_switch (all_candidates
[i
]);
562 delete all_candidates
[i
];
567 for (hash_map
<basic_block
, condition_info
*>::iterator it
568 = conditions_in_bbs
.begin (); it
!= conditions_in_bbs
.end (); ++it
)
571 if (!all_candidates
.is_empty ())
573 free_dominance_info (CDI_DOMINATORS
);
574 return TODO_cleanup_cfg
;
583 make_pass_if_to_switch (gcc::context
*ctxt
)
585 return new pass_if_to_switch (ctxt
);