1/* If-elseif-else to switch conversion pass
2 Copyright (C) 2020-2024 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify
7it under the terms of the GNU General Public License as published by
8the Free Software Foundation; either version 3, or (at your option)
9any later version.
10
11GCC is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14GNU General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along 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
59using namespace tree_switch_conversion;
60
61struct condition_info
62{
63 typedef auto_vec<std::pair<gphi *, tree>> mapping_vec;
64
65 condition_info (gcond *cond, bool has_side_effect): m_cond (cond),
66 m_bb (gimple_bb (g: cond)), m_forwarder_bb (NULL), m_ranges (),
67 m_true_edge (NULL), m_false_edge (NULL),
68 m_true_edge_phi_mapping (), m_false_edge_phi_mapping (),
69 m_has_side_effect (has_side_effect)
70 {
71 m_ranges.create (nelems: 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
91void
92condition_info::record_phi_mapping (edge e, mapping_vec *vec)
93{
94 for (gphi_iterator gsi = gsi_start_phis (e->dest); !gsi_end_p (i: gsi);
95 gsi_next (i: &gsi))
96 {
97 gphi *phi = gsi.phi ();
98 tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
99 vec->safe_push (obj: std::make_pair (x&: phi, y&: arg));
100 }
101}
102
103/* Master structure for one if to switch conversion candidate. */
104
105struct if_chain
106{
107 /* Default constructor. */
108 if_chain (): m_entries ()
109 {
110 m_entries.create (nelems: 2);
111 }
112
113 /* Default destructor. */
114 ~if_chain ()
115 {
116 m_entries.release ();
117 }
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
132static int
133range_cmp (const void *a, const void *b)
134{
135 const range_entry *re1 = *(const range_entry * const *) a;
136 const range_entry *re2 = *(const range_entry * const *) b;
137
138 return tree_int_cst_compare (t1: re1->low, t2: re2->low);
139}
140
141/* Verify that all case ranges do not overlap. */
142
143bool
144if_chain::check_non_overlapping_cases ()
145{
146 auto_vec<range_entry *> all_ranges;
147 for (unsigned i = 0; i < m_entries.length (); i++)
148 for (unsigned j = 0; j < m_entries[i]->m_ranges.length (); j++)
149 all_ranges.safe_push (obj: &m_entries[i]->m_ranges[j]);
150
151 all_ranges.qsort (range_cmp);
152
153 for (unsigned i = 0; i < all_ranges.length () - 1; i++)
154 {
155 range_entry *left = all_ranges[i];
156 range_entry *right = all_ranges[i + 1];
157 if (tree_int_cst_le (t1: left->low, t2: right->low)
158 && tree_int_cst_le (t1: right->low, t2: left->high))
159 return false;
160 }
161
162 return true;
163}
164
165/* Compare clusters by minimum value. */
166
167static int
168cluster_cmp (const void *a, const void *b)
169{
170 simple_cluster *sc1 = *(simple_cluster * const *) a;
171 simple_cluster *sc2 = *(simple_cluster * const *) b;
172
173 return tree_int_cst_compare (t1: sc1->get_low (), t2: sc2->get_high ());
174}
175
176/* Dump constructed CLUSTERS with prefix MESSAGE. */
177
178static void
179dump_clusters (vec<cluster *> *clusters, const char *message)
180{
181 if (dump_file)
182 {
183 fprintf (stream: dump_file, format: ";; %s: ", message);
184 for (unsigned i = 0; i < clusters->length (); i++)
185 (*clusters)[i]->dump (f: dump_file, details: dump_flags & TDF_DETAILS);
186 fprintf (stream: dump_file, format: "\n");
187 }
188}
189
190/* Return true when the switch can be expanded with a jump table or
191 a bit test (at least partially). */
192
193bool
194if_chain::is_beneficial ()
195{
196 profile_probability prob = profile_probability::uninitialized ();
197
198 auto_vec<cluster *> clusters;
199 clusters.create (nelems: m_entries.length ());
200
201 for (unsigned i = 0; i < m_entries.length (); i++)
202 {
203 condition_info *info = m_entries[i];
204 for (unsigned j = 0; j < info->m_ranges.length (); j++)
205 {
206 range_entry *range = &info->m_ranges[j];
207 basic_block bb = info->m_true_edge->dest;
208 bool has_forwarder = !info->m_true_edge_phi_mapping.is_empty ();
209 clusters.safe_push (obj: new simple_cluster (range->low, range->high,
210 NULL_TREE, bb, prob,
211 has_forwarder));
212 }
213 }
214
215 /* Sort clusters and merge them. */
216 auto_vec<cluster *> filtered_clusters;
217 filtered_clusters.create (nelems: 16);
218 clusters.qsort (cluster_cmp);
219 simple_cluster *left = static_cast<simple_cluster *> (clusters[0]);
220 filtered_clusters.safe_push (obj: left);
221
222 for (unsigned i = 1; i < clusters.length (); i++)
223 {
224 simple_cluster *right = static_cast<simple_cluster *> (clusters[i]);
225 tree type = TREE_TYPE (left->get_low ());
226 if (!left->m_has_forward_bb
227 && !right->m_has_forward_bb
228 && left->m_case_bb == right->m_case_bb)
229 {
230 if (wi::eq_p (x: wi::to_wide (t: right->get_low ()) - wi::to_wide
231 (t: left->get_high ()), y: wi::one (TYPE_PRECISION (type))))
232 {
233 left->set_high (right->get_high ());
234 delete right;
235 continue;
236 }
237 }
238
239 left = static_cast<simple_cluster *> (clusters[i]);
240 filtered_clusters.safe_push (obj: left);
241 }
242
243 dump_clusters (clusters: &filtered_clusters, message: "Canonical GIMPLE case clusters");
244
245 vec<cluster *> output
246 = jump_table_cluster::find_jump_tables (clusters&: filtered_clusters);
247 bool r = output.length () < filtered_clusters.length ();
248 if (r)
249 {
250 dump_clusters (clusters: &output, message: "JT can be built");
251 release_clusters (clusters&: output);
252 return true;
253 }
254 else
255 output.release ();
256
257 output = bit_test_cluster::find_bit_tests (clusters&: filtered_clusters);
258 r = output.length () < filtered_clusters.length ();
259 if (r)
260 dump_clusters (clusters: &output, message: "BT can be built");
261
262 release_clusters (clusters&: output);
263 return r;
264}
265
266/* Build case label with MIN and MAX values of a given basic block DEST. */
267
268static tree
269build_case_label (tree index_type, tree min, tree max, basic_block dest)
270{
271 if (min != NULL_TREE && index_type != TREE_TYPE (min))
272 min = fold_convert (index_type, min);
273 if (max != NULL_TREE && index_type != TREE_TYPE (max))
274 max = fold_convert (index_type, max);
275
276 tree label = gimple_block_label (dest);
277 return build_case_label (min, min == max ? NULL_TREE : max, label);
278}
279
280/* Compare two integer constants. */
281
282static int
283label_cmp (const void *a, const void *b)
284{
285 const_tree l1 = *(const const_tree *) a;
286 const_tree l2 = *(const const_tree *) b;
287
288 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
293static void
294convert_if_conditions_to_switch (if_chain *chain)
295{
296 if (!dbg_cnt (index: if_to_switch))
297 return;
298
299 auto_vec<tree> labels;
300 unsigned entries = chain->m_entries.length ();
301 condition_info *first_cond = chain->m_entries[0];
302 condition_info *last_cond = chain->m_entries[entries - 1];
303
304 edge default_edge = last_cond->m_false_edge;
305 basic_block default_bb = default_edge->dest;
306
307 gimple_stmt_iterator gsi = gsi_for_stmt (first_cond->m_cond);
308 tree index_type = TREE_TYPE (first_cond->m_ranges[0].exp);
309 for (unsigned i = 0; i < entries; i++)
310 {
311 condition_info *info = chain->m_entries[i];
312 basic_block case_bb = info->m_true_edge->dest;
313
314 /* Create a forwarder block if needed. */
315 if (!info->m_true_edge_phi_mapping.is_empty ())
316 {
317 info->m_forwarder_bb = split_edge (info->m_true_edge);
318 case_bb = info->m_forwarder_bb;
319 }
320
321 for (unsigned j = 0; j < info->m_ranges.length (); j++)
322 labels.safe_push (obj: build_case_label (index_type,
323 min: info->m_ranges[j].low,
324 max: info->m_ranges[j].high,
325 dest: case_bb));
326 default_bb = info->m_false_edge->dest;
327
328 if (i == 0)
329 {
330 remove_edge (first_cond->m_true_edge);
331 remove_edge (first_cond->m_false_edge);
332 }
333 else
334 delete_basic_block (info->m_bb);
335
336 make_edge (first_cond->m_bb, case_bb, 0);
337 }
338
339 labels.qsort (label_cmp);
340
341 edge e = find_edge (first_cond->m_bb, default_bb);
342 if (e == NULL)
343 e = make_edge (first_cond->m_bb, default_bb, 0);
344 gswitch *s
345 = gimple_build_switch (first_cond->m_ranges[0].exp,
346 build_case_label (index_type, NULL_TREE,
347 NULL_TREE, dest: default_bb),
348 labels);
349
350 gsi_remove (&gsi, true);
351 gsi_insert_before (&gsi, s, GSI_NEW_STMT);
352
353 if (dump_file)
354 {
355 fprintf (stream: dump_file, format: "Expanded into a new gimple STMT: ");
356 print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
357 putc (c: '\n', stream: dump_file);
358 }
359
360 /* Fill up missing PHI node arguments. */
361 for (unsigned i = 0; i < chain->m_entries.length (); ++i)
362 {
363 condition_info *info = chain->m_entries[i];
364 for (unsigned j = 0; j < info->m_true_edge_phi_mapping.length (); ++j)
365 {
366 std::pair<gphi *, tree> item = info->m_true_edge_phi_mapping[j];
367 add_phi_arg (item.first, item.second,
368 single_succ_edge (bb: info->m_forwarder_bb),
369 UNKNOWN_LOCATION);
370 }
371 }
372
373 /* Fill up missing PHI nodes for the default BB. */
374 for (unsigned j = 0; j < last_cond->m_false_edge_phi_mapping.length (); ++j)
375 {
376 std::pair<gphi *, tree> item = last_cond->m_false_edge_phi_mapping[j];
377 add_phi_arg (item.first, item.second, e, UNKNOWN_LOCATION);
378 }
379}
380
381/* Identify an index variable used in BB in a GIMPLE condition.
382 Save information about the condition into CONDITIONS_IN_BBS. */
383
384static void
385find_conditions (basic_block bb,
386 hash_map<basic_block, condition_info *> *conditions_in_bbs)
387{
388 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
389 if (gsi_end_p (i: gsi))
390 return;
391
392 gcond *cond = dyn_cast<gcond *> (p: gsi_stmt (i: gsi));
393 if (cond == NULL)
394 return;
395
396 tree lhs = gimple_cond_lhs (gs: cond);
397 tree rhs = gimple_cond_rhs (gs: cond);
398 tree_code code = gimple_cond_code (gs: cond);
399
400 condition_info *info = new condition_info (cond, !no_side_effect_bb (bb));
401
402 gassign *def;
403 if (code == NE_EXPR
404 && TREE_CODE (lhs) == SSA_NAME
405 && (def = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (lhs))) != NULL
406 && integer_zerop (rhs))
407 {
408 enum tree_code rhs_code = gimple_assign_rhs_code (gs: def);
409 if (rhs_code == BIT_IOR_EXPR)
410 {
411 info->m_ranges.safe_grow (len: 2, exact: true);
412 init_range_entry (r: &info->m_ranges[0], exp: gimple_assign_rhs1 (gs: def), NULL);
413 init_range_entry (r: &info->m_ranges[1], exp: gimple_assign_rhs2 (gs: def), NULL);
414 }
415 }
416 else
417 {
418 info->m_ranges.safe_grow (len: 1, exact: true);
419 init_range_entry (r: &info->m_ranges[0], NULL_TREE, stmt: cond);
420 }
421
422 /* All identified ranges must have equal expression and IN_P flag. */
423 if (!info->m_ranges.is_empty ())
424 {
425 edge true_edge, false_edge;
426 tree expr = info->m_ranges[0].exp;
427 bool in_p = info->m_ranges[0].in_p;
428
429 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
430 info->m_true_edge = in_p ? true_edge : false_edge;
431 info->m_false_edge = in_p ? false_edge : true_edge;
432
433 for (unsigned i = 0; i < info->m_ranges.length (); ++i)
434 if (info->m_ranges[i].exp == NULL_TREE
435 || !INTEGRAL_TYPE_P (TREE_TYPE (info->m_ranges[i].exp))
436 || info->m_ranges[i].low == NULL_TREE
437 || info->m_ranges[i].high == NULL_TREE
438 || (TYPE_PRECISION (TREE_TYPE (info->m_ranges[i].low))
439 != TYPE_PRECISION (TREE_TYPE (info->m_ranges[i].high))))
440 goto exit;
441
442 for (unsigned i = 1; i < info->m_ranges.length (); ++i)
443 if (info->m_ranges[i].exp != expr
444 || info->m_ranges[i].in_p != in_p)
445 goto exit;
446
447 info->record_phi_mapping (e: info->m_true_edge,
448 vec: &info->m_true_edge_phi_mapping);
449 info->record_phi_mapping (e: info->m_false_edge,
450 vec: &info->m_false_edge_phi_mapping);
451 conditions_in_bbs->put (k: bb, v: info);
452 return;
453 }
454
455exit:
456 delete info;
457}
458
459namespace {
460
461const pass_data pass_data_if_to_switch =
462{
463 .type: GIMPLE_PASS, /* type */
464 .name: "iftoswitch", /* name */
465 .optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
466 .tv_id: TV_TREE_IF_TO_SWITCH, /* tv_id */
467 .properties_required: ( PROP_cfg | PROP_ssa ), /* properties_required */
468 .properties_provided: 0, /* properties_provided */
469 .properties_destroyed: 0, /* properties_destroyed */
470 .todo_flags_start: 0, /* todo_flags_start */
471 TODO_update_ssa /* todo_flags_finish */
472};
473
474class pass_if_to_switch : public gimple_opt_pass
475{
476public:
477 pass_if_to_switch (gcc::context *ctxt)
478 : gimple_opt_pass (pass_data_if_to_switch, ctxt)
479 {}
480
481 /* opt_pass methods: */
482 bool gate (function *) final override
483 {
484 return (jump_table_cluster::is_enabled ()
485 || bit_test_cluster::is_enabled ());
486 }
487
488 unsigned int execute (function *) final override;
489
490}; // class pass_if_to_switch
491
492unsigned int
493pass_if_to_switch::execute (function *fun)
494{
495 auto_vec<if_chain *> all_candidates;
496 hash_map<basic_block, condition_info *> conditions_in_bbs;
497
498 mark_ssa_maybe_undefs ();
499
500 basic_block bb;
501 FOR_EACH_BB_FN (bb, fun)
502 find_conditions (bb, conditions_in_bbs: &conditions_in_bbs);
503
504 if (conditions_in_bbs.is_empty ())
505 return 0;
506
507 int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun));
508 unsigned n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, false);
509
510 auto_bitmap seen_bbs;
511 for (int i = n - 1; i >= 0; --i)
512 {
513 basic_block bb = BASIC_BLOCK_FOR_FN (fun, rpo[i]);
514 if (bitmap_bit_p (seen_bbs, bb->index))
515 continue;
516
517 bitmap_set_bit (seen_bbs, bb->index);
518 condition_info **slot = conditions_in_bbs.get (k: bb);
519 if (slot)
520 {
521 condition_info *info = *slot;
522 if_chain *chain = new if_chain ();
523 chain->m_entries.safe_push (obj: info);
524 /* Try to find a chain starting in this BB. */
525 while (true)
526 {
527 if (!single_pred_p (bb: gimple_bb (g: info->m_cond)))
528 break;
529 edge e = single_pred_edge (bb: gimple_bb (g: info->m_cond));
530 condition_info **info2 = conditions_in_bbs.get (k: e->src);
531 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 if ((*info2)->m_false_edge != e)
538 break;
539
540 /* Only the first BB in a chain can have a side effect. */
541 if (info->m_has_side_effect)
542 break;
543
544 chain->m_entries.safe_push (obj: *info2);
545 bitmap_set_bit (seen_bbs, e->src->index);
546 info = *info2;
547 }
548
549 chain->m_entries.reverse ();
550 if (chain->m_entries.length () >= 2
551 && chain->check_non_overlapping_cases ()
552 && chain->is_beneficial ())
553 {
554 gcond *cond = chain->m_entries[0]->m_cond;
555 if (dump_enabled_p ())
556 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 all_candidates.safe_push (obj: chain);
561 }
562 else
563 delete chain;
564 }
565 }
566
567 for (unsigned i = 0; i < all_candidates.length (); i++)
568 {
569 convert_if_conditions_to_switch (chain: all_candidates[i]);
570 delete all_candidates[i];
571 }
572
573 free (ptr: rpo);
574
575 for (hash_map<basic_block, condition_info *>::iterator it
576 = conditions_in_bbs.begin (); it != conditions_in_bbs.end (); ++it)
577 delete (*it).second;
578
579 if (!all_candidates.is_empty ())
580 {
581 free_dominance_info (CDI_DOMINATORS);
582 return TODO_cleanup_cfg;
583 }
584
585 return 0;
586}
587
588} // anon namespace
589
590gimple_opt_pass *
591make_pass_if_to_switch (gcc::context *ctxt)
592{
593 return new pass_if_to_switch (ctxt);
594}
595

source code of gcc/gimple-if-to-switch.cc