Line data Source code
1 : /* If-elseif-else to switch conversion pass
2 : Copyright (C) 2020-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
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)
9 : any later version.
10 :
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.
15 :
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/>. */
19 :
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
29 : first one. */
30 :
31 : #include "config.h"
32 : #include "system.h"
33 : #include "coretypes.h"
34 : #include "backend.h"
35 : #include "rtl.h"
36 : #include "tree.h"
37 : #include "gimple.h"
38 : #include "tree-pass.h"
39 : #include "ssa.h"
40 : #include "gimple-pretty-print.h"
41 : #include "fold-const.h"
42 : #include "gimple-iterator.h"
43 : #include "tree-cfg.h"
44 : #include "tree-dfa.h"
45 : #include "tree-cfgcleanup.h"
46 : #include "alias.h"
47 : #include "tree-ssa-loop.h"
48 : #include "diagnostic.h"
49 : #include "cfghooks.h"
50 : #include "tree-into-ssa.h"
51 : #include "cfganal.h"
52 : #include "dbgcnt.h"
53 : #include "target.h"
54 : #include "alloc-pool.h"
55 : #include "tree-switch-conversion.h"
56 : #include "tree-ssa-reassoc.h"
57 : #include "tree-ssa.h"
58 :
59 : using namespace tree_switch_conversion;
60 :
61 : struct condition_info
62 : {
63 : typedef auto_vec<std::pair<gphi *, tree>> mapping_vec;
64 :
65 3823700 : condition_info (gcond *cond, bool has_side_effect): m_cond (cond),
66 3823700 : m_bb (gimple_bb (cond)), m_forwarder_bb (NULL), m_ranges (),
67 3823700 : m_true_edge (NULL), m_false_edge (NULL),
68 3823700 : m_true_edge_phi_mapping (), m_false_edge_phi_mapping (),
69 3823700 : m_has_side_effect (has_side_effect)
70 : {
71 3823700 : m_ranges.create (0);
72 : }
73 :
74 : /* Recond PHI mapping for an original edge E and save these into
75 : vector VEC. */
76 : void record_phi_mapping (edge e, mapping_vec *vec);
77 :
78 : gcond *m_cond;
79 : basic_block m_bb;
80 : basic_block m_forwarder_bb;
81 : auto_vec<range_entry> m_ranges;
82 : edge m_true_edge;
83 : edge m_false_edge;
84 : mapping_vec m_true_edge_phi_mapping;
85 : mapping_vec m_false_edge_phi_mapping;
86 : bool m_has_side_effect;
87 : };
88 :
89 : /* Recond PHI mapping for an original edge E and save these into vector VEC. */
90 :
91 : void
92 3698198 : condition_info::record_phi_mapping (edge e, mapping_vec *vec)
93 : {
94 4803582 : for (gphi_iterator gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);
95 1105384 : gsi_next (&gsi))
96 : {
97 1105384 : gphi *phi = gsi.phi ();
98 1105384 : tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
99 1105384 : vec->safe_push (std::make_pair (phi, arg));
100 : }
101 3698198 : }
102 :
103 : /* Master structure for one if to switch conversion candidate. */
104 :
105 : struct if_chain
106 : {
107 : /* Default constructor. */
108 1805948 : if_chain (): m_entries ()
109 : {
110 3611896 : m_entries.create (2);
111 : }
112 :
113 : /* Default destructor. */
114 1805948 : ~if_chain ()
115 : {
116 1629 : m_entries.release ();
117 1805948 : }
118 :
119 : /* Verify that all case ranges do not overlap. */
120 : bool check_non_overlapping_cases ();
121 :
122 : /* Return true when the switch can be expanded with a jump table or
123 : a bit test (at least partially). */
124 : bool is_beneficial ();
125 :
126 : /* If chain entries. */
127 : vec<condition_info *> m_entries;
128 : };
129 :
130 : /* Compare two case ranges by minimum value. */
131 :
132 : static int
133 268287 : range_cmp (const void *a, const void *b)
134 : {
135 268287 : const range_entry *re1 = *(const range_entry * const *) a;
136 268287 : const range_entry *re2 = *(const range_entry * const *) b;
137 :
138 268287 : return tree_int_cst_compare (re1->low, re2->low);
139 : }
140 :
141 : /* Verify that all case ranges do not overlap. */
142 :
143 : bool
144 36711 : if_chain::check_non_overlapping_cases ()
145 : {
146 36711 : auto_vec<range_entry *> all_ranges;
147 116573 : for (unsigned i = 0; i < m_entries.length (); i++)
148 163289 : for (unsigned j = 0; j < m_entries[i]->m_ranges.length (); j++)
149 83427 : all_ranges.safe_push (&m_entries[i]->m_ranges[j]);
150 :
151 36711 : all_ranges.qsort (range_cmp);
152 :
153 147408 : for (unsigned i = 0; i < all_ranges.length () - 1; i++)
154 : {
155 46147 : range_entry *left = all_ranges[i];
156 46147 : range_entry *right = all_ranges[i + 1];
157 46147 : if (tree_int_cst_le (left->low, right->low)
158 46147 : && tree_int_cst_le (right->low, left->high))
159 : return false;
160 : }
161 :
162 : return true;
163 36711 : }
164 :
165 : /* Compare clusters by minimum value. */
166 :
167 : static int
168 235986 : cluster_cmp (const void *a, const void *b)
169 : {
170 235986 : simple_cluster *sc1 = *(simple_cluster * const *) a;
171 235986 : simple_cluster *sc2 = *(simple_cluster * const *) b;
172 :
173 235986 : return tree_int_cst_compare (sc1->get_low (), sc2->get_high ());
174 : }
175 :
176 : /* Dump constructed CLUSTERS with prefix MESSAGE. */
177 :
178 : static void
179 29186 : dump_clusters (vec<cluster *> *clusters, const char *message)
180 : {
181 29186 : if (dump_file)
182 : {
183 24 : fprintf (dump_file, ";; %s: ", message);
184 95 : for (unsigned i = 0; i < clusters->length (); i++)
185 71 : (*clusters)[i]->dump (dump_file, dump_flags & TDF_DETAILS);
186 24 : fprintf (dump_file, "\n");
187 : }
188 29186 : }
189 :
190 : /* Return true when the switch can be expanded with a jump table or
191 : a bit test (at least partially). */
192 :
193 : bool
194 27557 : if_chain::is_beneficial ()
195 : {
196 27557 : profile_probability prob = profile_probability::uninitialized ();
197 :
198 27557 : auto_vec<cluster *> clusters;
199 27557 : clusters.create (m_entries.length ());
200 :
201 88543 : for (unsigned i = 0; i < m_entries.length (); i++)
202 : {
203 60986 : condition_info *info = m_entries[i];
204 125536 : for (unsigned j = 0; j < info->m_ranges.length (); j++)
205 : {
206 64550 : range_entry *range = &info->m_ranges[j];
207 64550 : basic_block bb = info->m_true_edge->dest;
208 64550 : bool has_forwarder = !info->m_true_edge_phi_mapping.is_empty ();
209 64550 : clusters.safe_push (new simple_cluster (range->low, range->high,
210 : NULL_TREE, bb, prob,
211 64550 : has_forwarder));
212 : }
213 : }
214 :
215 : /* Sort clusters and merge them. */
216 27557 : auto_vec<cluster *> filtered_clusters;
217 27557 : filtered_clusters.create (16);
218 27557 : clusters.qsort (cluster_cmp);
219 27557 : simple_cluster *left = static_cast<simple_cluster *> (clusters[0]);
220 27557 : filtered_clusters.safe_push (left);
221 :
222 64550 : for (unsigned i = 1; i < clusters.length (); i++)
223 : {
224 36993 : simple_cluster *right = static_cast<simple_cluster *> (clusters[i]);
225 36993 : tree type = TREE_TYPE (left->get_low ());
226 36993 : if (!left->m_has_forward_bb
227 25431 : && !right->m_has_forward_bb
228 24115 : && left->m_case_bb == right->m_case_bb)
229 : {
230 15000 : if (wi::eq_p (wi::to_wide (right->get_low ()) - wi::to_wide
231 22500 : (left->get_high ()), wi::one (TYPE_PRECISION (type))))
232 : {
233 1347 : left->set_high (right->get_high ());
234 1347 : delete right;
235 1347 : continue;
236 : }
237 : }
238 :
239 35646 : left = static_cast<simple_cluster *> (clusters[i]);
240 35646 : filtered_clusters.safe_push (left);
241 : }
242 :
243 27557 : dump_clusters (&filtered_clusters, "Canonical GIMPLE case clusters");
244 :
245 27557 : vec<cluster *> output
246 27557 : = jump_table_cluster::find_jump_tables (filtered_clusters);
247 55114 : bool r = output.length () < filtered_clusters.length ();
248 27557 : if (r)
249 : {
250 655 : dump_clusters (&output, "JT can be built");
251 655 : release_clusters (output);
252 655 : return true;
253 : }
254 : else
255 26902 : output.release ();
256 :
257 26902 : output = bit_test_cluster::find_bit_tests (filtered_clusters, 2);
258 53804 : r = output.length () < filtered_clusters.length ();
259 26902 : if (r)
260 974 : dump_clusters (&output, "BT can be built");
261 :
262 26902 : release_clusters (output);
263 26902 : return r;
264 27557 : }
265 :
266 : /* Build case label with MIN and MAX values of a given basic block DEST. */
267 :
268 : static tree
269 11046 : build_case_label (tree index_type, tree min, tree max, basic_block dest)
270 : {
271 11046 : if (min != NULL_TREE && index_type != TREE_TYPE (min))
272 210 : min = fold_convert (index_type, min);
273 11046 : if (max != NULL_TREE && index_type != TREE_TYPE (max))
274 210 : max = fold_convert (index_type, max);
275 :
276 11046 : tree label = gimple_block_label (dest);
277 21226 : return build_case_label (min, min == max ? NULL_TREE : max, label);
278 : }
279 :
280 : /* Compare two integer constants. */
281 :
282 : static int
283 106798 : label_cmp (const void *a, const void *b)
284 : {
285 106798 : const_tree l1 = *(const const_tree *) a;
286 106798 : const_tree l2 = *(const const_tree *) b;
287 :
288 106798 : return tree_int_cst_compare (CASE_LOW (l1), CASE_LOW (l2));
289 : }
290 :
291 : /* Convert a given if CHAIN into a switch GIMPLE statement. */
292 :
293 : static void
294 1629 : convert_if_conditions_to_switch (if_chain *chain)
295 : {
296 1629 : if (!dbg_cnt (if_to_switch))
297 0 : return;
298 :
299 1629 : auto_vec<tree> labels;
300 1629 : unsigned entries = chain->m_entries.length ();
301 1629 : condition_info *first_cond = chain->m_entries[0];
302 1629 : condition_info *last_cond = chain->m_entries[entries - 1];
303 :
304 1629 : edge default_edge = last_cond->m_false_edge;
305 1629 : basic_block default_bb = default_edge->dest;
306 :
307 1629 : gimple_stmt_iterator gsi = gsi_for_stmt (first_cond->m_cond);
308 1629 : tree index_type = TREE_TYPE (first_cond->m_ranges[0].exp);
309 8167 : for (unsigned i = 0; i < entries; i++)
310 : {
311 6538 : condition_info *info = chain->m_entries[i];
312 6538 : basic_block case_bb = info->m_true_edge->dest;
313 :
314 : /* Create a forwarder block if needed. */
315 6538 : if (!info->m_true_edge_phi_mapping.is_empty ())
316 : {
317 1081 : info->m_forwarder_bb = split_edge (info->m_true_edge);
318 1081 : case_bb = info->m_forwarder_bb;
319 : }
320 :
321 15955 : for (unsigned j = 0; j < info->m_ranges.length (); j++)
322 9417 : labels.safe_push (build_case_label (index_type,
323 9417 : info->m_ranges[j].low,
324 9417 : info->m_ranges[j].high,
325 : case_bb));
326 6538 : default_bb = info->m_false_edge->dest;
327 :
328 6538 : if (i == 0)
329 : {
330 1629 : remove_edge (first_cond->m_true_edge);
331 1629 : remove_edge (first_cond->m_false_edge);
332 : }
333 : else
334 4909 : delete_basic_block (info->m_bb);
335 :
336 6538 : make_edge (first_cond->m_bb, case_bb, 0);
337 : }
338 :
339 1629 : labels.qsort (label_cmp);
340 :
341 1629 : edge e = find_edge (first_cond->m_bb, default_bb);
342 1629 : if (e == NULL)
343 1629 : e = make_edge (first_cond->m_bb, default_bb, 0);
344 1629 : gswitch *s
345 1629 : = gimple_build_switch (first_cond->m_ranges[0].exp,
346 : build_case_label (index_type, NULL_TREE,
347 : NULL_TREE, default_bb),
348 : labels);
349 :
350 1629 : gsi_remove (&gsi, true);
351 1629 : gsi_insert_before (&gsi, s, GSI_NEW_STMT);
352 :
353 1629 : if (dump_file)
354 : {
355 10 : fprintf (dump_file, "Expanded into a new gimple STMT: ");
356 10 : print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
357 10 : putc ('\n', dump_file);
358 : }
359 :
360 : /* Fill up missing PHI node arguments. */
361 16334 : for (unsigned i = 0; i < chain->m_entries.length (); ++i)
362 : {
363 6538 : condition_info *info = chain->m_entries[i];
364 8163 : for (unsigned j = 0; j < info->m_true_edge_phi_mapping.length (); ++j)
365 : {
366 1625 : std::pair<gphi *, tree> item = info->m_true_edge_phi_mapping[j];
367 1625 : add_phi_arg (item.first, item.second,
368 1625 : single_succ_edge (info->m_forwarder_bb),
369 : UNKNOWN_LOCATION);
370 : }
371 : }
372 :
373 : /* Fill up missing PHI nodes for the default BB. */
374 2236 : for (unsigned j = 0; j < last_cond->m_false_edge_phi_mapping.length (); ++j)
375 : {
376 607 : std::pair<gphi *, tree> item = last_cond->m_false_edge_phi_mapping[j];
377 607 : add_phi_arg (item.first, item.second, e, UNKNOWN_LOCATION);
378 : }
379 1629 : }
380 :
381 : /* Identify an index variable used in BB in a GIMPLE condition.
382 : Save information about the condition into CONDITIONS_IN_BBS. */
383 :
384 : static void
385 11024837 : find_conditions (basic_block bb,
386 : hash_map<basic_block, condition_info *> *conditions_in_bbs)
387 : {
388 11024837 : gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
389 11024837 : if (gsi_end_p (gsi))
390 9050236 : return;
391 :
392 12873936 : gcond *cond = dyn_cast<gcond *> (gsi_stmt (gsi));
393 3823700 : if (cond == NULL)
394 : return;
395 :
396 3823700 : tree lhs = gimple_cond_lhs (cond);
397 3823700 : tree rhs = gimple_cond_rhs (cond);
398 3823700 : tree_code code = gimple_cond_code (cond);
399 :
400 3823700 : condition_info *info = new condition_info (cond, !no_side_effect_bb (bb));
401 :
402 3823700 : gassign *def;
403 3823700 : if (code == NE_EXPR
404 1878781 : && TREE_CODE (lhs) == SSA_NAME
405 1878513 : && (def = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (lhs))) != NULL
406 4820369 : && integer_zerop (rhs))
407 : {
408 577214 : enum tree_code rhs_code = gimple_assign_rhs_code (def);
409 577214 : if (rhs_code == BIT_IOR_EXPR)
410 : {
411 28617 : info->m_ranges.safe_grow (2, true);
412 28617 : init_range_entry (&info->m_ranges[0], gimple_assign_rhs1 (def), NULL);
413 57234 : init_range_entry (&info->m_ranges[1], gimple_assign_rhs2 (def), NULL);
414 : }
415 : }
416 : else
417 : {
418 3246486 : info->m_ranges.safe_grow (1, true);
419 3246486 : init_range_entry (&info->m_ranges[0], NULL_TREE, cond);
420 : }
421 :
422 : /* All identified ranges must have equal expression and IN_P flag. */
423 3823700 : if (!info->m_ranges.is_empty ())
424 : {
425 3275103 : edge true_edge, false_edge;
426 3275103 : tree expr = info->m_ranges[0].exp;
427 3275103 : bool in_p = info->m_ranges[0].in_p;
428 :
429 3275103 : extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
430 3275103 : info->m_true_edge = in_p ? true_edge : false_edge;
431 3275103 : info->m_false_edge = in_p ? false_edge : true_edge;
432 :
433 10324052 : for (unsigned i = 0; i < info->m_ranges.length (); ++i)
434 3297342 : if (info->m_ranges[i].exp == NULL_TREE
435 2285867 : || !INTEGRAL_TYPE_P (TREE_TYPE (info->m_ranges[i].exp))
436 2087803 : || info->m_ranges[i].low == NULL_TREE
437 1953189 : || info->m_ranges[i].high == NULL_TREE
438 5184639 : || (TYPE_PRECISION (TREE_TYPE (info->m_ranges[i].low))
439 1887297 : != TYPE_PRECISION (TREE_TYPE (info->m_ranges[i].high))))
440 1426004 : goto exit;
441 :
442 1870485 : for (unsigned i = 1; i < info->m_ranges.length (); ++i)
443 21386 : if (info->m_ranges[i].exp != expr
444 21386 : || info->m_ranges[i].in_p != in_p)
445 15585 : goto exit;
446 :
447 1849099 : info->record_phi_mapping (info->m_true_edge,
448 : &info->m_true_edge_phi_mapping);
449 1849099 : info->record_phi_mapping (info->m_false_edge,
450 : &info->m_false_edge_phi_mapping);
451 1849099 : conditions_in_bbs->put (bb, info);
452 1849099 : return;
453 : }
454 :
455 1974601 : exit:
456 1974601 : delete info;
457 : }
458 :
459 : namespace {
460 :
461 : const pass_data pass_data_if_to_switch =
462 : {
463 : GIMPLE_PASS, /* type */
464 : "iftoswitch", /* name */
465 : OPTGROUP_NONE, /* optinfo_flags */
466 : TV_TREE_IF_TO_SWITCH, /* tv_id */
467 : ( PROP_cfg | PROP_ssa ), /* properties_required */
468 : 0, /* properties_provided */
469 : 0, /* properties_destroyed */
470 : 0, /* todo_flags_start */
471 : TODO_update_ssa /* todo_flags_finish */
472 : };
473 :
474 : class pass_if_to_switch : public gimple_opt_pass
475 : {
476 : public:
477 285722 : pass_if_to_switch (gcc::context *ctxt)
478 571444 : : gimple_opt_pass (pass_data_if_to_switch, ctxt)
479 : {}
480 :
481 : /* opt_pass methods: */
482 2412428 : bool gate (function *) final override
483 : {
484 2412428 : return (jump_table_cluster::is_enabled ()
485 2412428 : || bit_test_cluster::is_enabled ());
486 : }
487 :
488 : unsigned int execute (function *) final override;
489 :
490 : }; // class pass_if_to_switch
491 :
492 : unsigned int
493 2412337 : pass_if_to_switch::execute (function *fun)
494 : {
495 2412337 : auto_vec<if_chain *> all_candidates;
496 2412337 : hash_map<basic_block, condition_info *> conditions_in_bbs;
497 :
498 2412337 : mark_ssa_maybe_undefs ();
499 :
500 2412337 : basic_block bb;
501 13437174 : FOR_EACH_BB_FN (bb, fun)
502 11024837 : find_conditions (bb, &conditions_in_bbs);
503 :
504 2412337 : if (conditions_in_bbs.is_empty ())
505 : return 0;
506 :
507 488884 : int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun));
508 488884 : unsigned n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, false);
509 :
510 488884 : auto_bitmap seen_bbs;
511 7810389 : for (int i = n - 1; i >= 0; --i)
512 : {
513 7321505 : basic_block bb = BASIC_BLOCK_FOR_FN (fun, rpo[i]);
514 7321505 : if (bitmap_bit_p (seen_bbs, bb->index))
515 43151 : continue;
516 :
517 7278354 : bitmap_set_bit (seen_bbs, bb->index);
518 7278354 : condition_info **slot = conditions_in_bbs.get (bb);
519 7278354 : if (slot)
520 : {
521 1805948 : condition_info *info = *slot;
522 1805948 : if_chain *chain = new if_chain ();
523 1805948 : chain->m_entries.safe_push (info);
524 : /* Try to find a chain starting in this BB. */
525 1892250 : while (true)
526 : {
527 1849099 : if (!single_pred_p (gimple_bb (info->m_cond)))
528 : break;
529 1235227 : edge e = single_pred_edge (gimple_bb (info->m_cond));
530 1235227 : condition_info **info2 = conditions_in_bbs.get (e->src);
531 1235227 : if (!info2 || info->m_ranges[0].exp != (*info2)->m_ranges[0].exp)
532 : break;
533 :
534 : /* It is important that the blocks are linked through FALSE_EDGE.
535 : For an expression of index != VALUE, true and false edges
536 : are flipped. */
537 55869 : if ((*info2)->m_false_edge != e)
538 : break;
539 :
540 : /* Only the first BB in a chain can have a side effect. */
541 49923 : if (info->m_has_side_effect)
542 : break;
543 :
544 43151 : chain->m_entries.safe_push (*info2);
545 43151 : bitmap_set_bit (seen_bbs, e->src->index);
546 43151 : info = *info2;
547 43151 : }
548 :
549 1805948 : chain->m_entries.reverse ();
550 1805948 : if (chain->m_entries.length () >= 2
551 36711 : && chain->check_non_overlapping_cases ()
552 1833505 : && chain->is_beneficial ())
553 : {
554 1629 : gcond *cond = chain->m_entries[0]->m_cond;
555 1629 : if (dump_enabled_p ())
556 10 : dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, cond,
557 : "Condition chain with %d BBs "
558 : "transformed into a switch statement.\n",
559 : chain->m_entries.length ());
560 1629 : all_candidates.safe_push (chain);
561 : }
562 : else
563 1804319 : delete chain;
564 : }
565 : }
566 :
567 490513 : for (unsigned i = 0; i < all_candidates.length (); i++)
568 : {
569 1629 : convert_if_conditions_to_switch (all_candidates[i]);
570 3258 : delete all_candidates[i];
571 : }
572 :
573 488884 : free (rpo);
574 :
575 2337983 : for (hash_map<basic_block, condition_info *>::iterator it
576 4675966 : = conditions_in_bbs.begin (); it != conditions_in_bbs.end (); ++it)
577 1849099 : delete (*it).second;
578 :
579 490404 : if (!all_candidates.is_empty ())
580 : {
581 1520 : free_dominance_info (CDI_DOMINATORS);
582 1520 : return TODO_cleanup_cfg;
583 : }
584 :
585 : return 0;
586 2901221 : }
587 :
588 : } // anon namespace
589 :
590 : gimple_opt_pass *
591 285722 : make_pass_if_to_switch (gcc::context *ctxt)
592 : {
593 285722 : return new pass_if_to_switch (ctxt);
594 : }
|
