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

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