Branch data Line data Source code
1 : : /* If-elseif-else to switch conversion pass
2 : : Copyright (C) 2020-2024 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 : 3544966 : condition_info (gcond *cond, bool has_side_effect): m_cond (cond),
66 : 3544966 : m_bb (gimple_bb (cond)), m_forwarder_bb (NULL), m_ranges (),
67 : 3544966 : m_true_edge (NULL), m_false_edge (NULL),
68 : 3544966 : m_true_edge_phi_mapping (), m_false_edge_phi_mapping (),
69 : 3544966 : m_has_side_effect (has_side_effect)
70 : : {
71 : 3544966 : 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 : 3427304 : condition_info::record_phi_mapping (edge e, mapping_vec *vec)
93 : : {
94 : 4447306 : for (gphi_iterator gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);
95 : 1020002 : gsi_next (&gsi))
96 : : {
97 : 1020002 : gphi *phi = gsi.phi ();
98 : 1020002 : tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
99 : 1020002 : vec->safe_push (std::make_pair (phi, arg));
100 : : }
101 : 3427304 : }
102 : :
103 : : /* Master structure for one if to switch conversion candidate. */
104 : :
105 : : struct if_chain
106 : : {
107 : : /* Default constructor. */
108 : 1681680 : if_chain (): m_entries ()
109 : : {
110 : 3363360 : m_entries.create (2);
111 : : }
112 : :
113 : : /* Default destructor. */
114 : 1681680 : ~if_chain ()
115 : : {
116 : 1419 : m_entries.release ();
117 : 1681680 : }
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 : 223087 : range_cmp (const void *a, const void *b)
134 : : {
135 : 223087 : const range_entry *re1 = *(const range_entry * const *) a;
136 : 223087 : const range_entry *re2 = *(const range_entry * const *) b;
137 : :
138 : 223087 : return tree_int_cst_compare (re1->low, re2->low);
139 : : }
140 : :
141 : : /* Verify that all case ranges do not overlap. */
142 : :
143 : : bool
144 : 26104 : if_chain::check_non_overlapping_cases ()
145 : : {
146 : 26104 : auto_vec<range_entry *> all_ranges;
147 : 84180 : for (unsigned i = 0; i < m_entries.length (); i++)
148 : 119570 : for (unsigned j = 0; j < m_entries[i]->m_ranges.length (); j++)
149 : 61494 : all_ranges.safe_push (&m_entries[i]->m_ranges[j]);
150 : :
151 : 26104 : all_ranges.qsort (range_cmp);
152 : :
153 : 115838 : for (unsigned i = 0; i < all_ranges.length () - 1; i++)
154 : : {
155 : 34806 : range_entry *left = all_ranges[i];
156 : 34806 : range_entry *right = all_ranges[i + 1];
157 : 34806 : if (tree_int_cst_le (left->low, right->low)
158 : 34806 : && tree_int_cst_le (right->low, left->high))
159 : : return false;
160 : : }
161 : :
162 : : return true;
163 : 26104 : }
164 : :
165 : : /* Compare clusters by minimum value. */
166 : :
167 : : static int
168 : 209184 : cluster_cmp (const void *a, const void *b)
169 : : {
170 : 209184 : simple_cluster *sc1 = *(simple_cluster * const *) a;
171 : 209184 : simple_cluster *sc2 = *(simple_cluster * const *) b;
172 : :
173 : 209184 : 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 : 24532 : dump_clusters (vec<cluster *> *clusters, const char *message)
180 : : {
181 : 24532 : 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 : 24532 : }
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 : 23113 : if_chain::is_beneficial ()
195 : : {
196 : 23113 : profile_probability prob = profile_probability::uninitialized ();
197 : :
198 : 23113 : auto_vec<cluster *> clusters;
199 : 23113 : clusters.create (m_entries.length ());
200 : :
201 : 74624 : for (unsigned i = 0; i < m_entries.length (); i++)
202 : : {
203 : 51511 : condition_info *info = m_entries[i];
204 : 106439 : for (unsigned j = 0; j < info->m_ranges.length (); j++)
205 : : {
206 : 54928 : range_entry *range = &info->m_ranges[j];
207 : 54928 : basic_block bb = info->m_true_edge->dest;
208 : 54928 : bool has_forwarder = !info->m_true_edge_phi_mapping.is_empty ();
209 : 54928 : clusters.safe_push (new simple_cluster (range->low, range->high,
210 : : NULL_TREE, bb, prob,
211 : 54928 : has_forwarder));
212 : : }
213 : : }
214 : :
215 : : /* Sort clusters and merge them. */
216 : 23113 : auto_vec<cluster *> filtered_clusters;
217 : 23113 : filtered_clusters.create (16);
218 : 23113 : clusters.qsort (cluster_cmp);
219 : 23113 : simple_cluster *left = static_cast<simple_cluster *> (clusters[0]);
220 : 23113 : filtered_clusters.safe_push (left);
221 : :
222 : 54928 : for (unsigned i = 1; i < clusters.length (); i++)
223 : : {
224 : 31815 : simple_cluster *right = static_cast<simple_cluster *> (clusters[i]);
225 : 31815 : tree type = TREE_TYPE (left->get_low ());
226 : 31815 : if (!left->m_has_forward_bb
227 : 23727 : && !right->m_has_forward_bb
228 : 22216 : && left->m_case_bb == right->m_case_bb)
229 : : {
230 : 12798 : if (wi::eq_p (wi::to_wide (right->get_low ()) - wi::to_wide
231 : 19197 : (left->get_high ()), wi::one (TYPE_PRECISION (type))))
232 : : {
233 : 1189 : left->set_high (right->get_high ());
234 : 1189 : delete right;
235 : 1189 : continue;
236 : : }
237 : : }
238 : :
239 : 30626 : left = static_cast<simple_cluster *> (clusters[i]);
240 : 30626 : filtered_clusters.safe_push (left);
241 : : }
242 : :
243 : 23113 : dump_clusters (&filtered_clusters, "Canonical GIMPLE case clusters");
244 : :
245 : 23113 : vec<cluster *> output
246 : 23113 : = jump_table_cluster::find_jump_tables (filtered_clusters);
247 : 46226 : bool r = output.length () < filtered_clusters.length ();
248 : 23113 : if (r)
249 : : {
250 : 618 : dump_clusters (&output, "JT can be built");
251 : 618 : release_clusters (output);
252 : 618 : return true;
253 : : }
254 : : else
255 : 22495 : output.release ();
256 : :
257 : 22495 : output = bit_test_cluster::find_bit_tests (filtered_clusters, 2);
258 : 44990 : r = output.length () < filtered_clusters.length ();
259 : 22495 : if (r)
260 : 801 : dump_clusters (&output, "BT can be built");
261 : :
262 : 22495 : release_clusters (output);
263 : 22495 : return r;
264 : 23113 : }
265 : :
266 : : /* Build case label with MIN and MAX values of a given basic block DEST. */
267 : :
268 : : static tree
269 : 9889 : build_case_label (tree index_type, tree min, tree max, basic_block dest)
270 : : {
271 : 9889 : if (min != NULL_TREE && index_type != TREE_TYPE (min))
272 : 166 : min = fold_convert (index_type, min);
273 : 9889 : if (max != NULL_TREE && index_type != TREE_TYPE (max))
274 : 166 : max = fold_convert (index_type, max);
275 : :
276 : 9889 : tree label = gimple_block_label (dest);
277 : 18923 : return build_case_label (min, min == max ? NULL_TREE : max, label);
278 : : }
279 : :
280 : : /* Compare two integer constants. */
281 : :
282 : : static int
283 : 98629 : label_cmp (const void *a, const void *b)
284 : : {
285 : 98629 : const_tree l1 = *(const const_tree *) a;
286 : 98629 : const_tree l2 = *(const const_tree *) b;
287 : :
288 : 98629 : 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 : 1419 : convert_if_conditions_to_switch (if_chain *chain)
295 : : {
296 : 1419 : if (!dbg_cnt (if_to_switch))
297 : 0 : return;
298 : :
299 : 1419 : auto_vec<tree> labels;
300 : 1419 : unsigned entries = chain->m_entries.length ();
301 : 1419 : condition_info *first_cond = chain->m_entries[0];
302 : 1419 : condition_info *last_cond = chain->m_entries[entries - 1];
303 : :
304 : 1419 : edge default_edge = last_cond->m_false_edge;
305 : 1419 : basic_block default_bb = default_edge->dest;
306 : :
307 : 1419 : gimple_stmt_iterator gsi = gsi_for_stmt (first_cond->m_cond);
308 : 1419 : tree index_type = TREE_TYPE (first_cond->m_ranges[0].exp);
309 : 7229 : for (unsigned i = 0; i < entries; i++)
310 : : {
311 : 5810 : condition_info *info = chain->m_entries[i];
312 : 5810 : basic_block case_bb = info->m_true_edge->dest;
313 : :
314 : : /* Create a forwarder block if needed. */
315 : 5810 : if (!info->m_true_edge_phi_mapping.is_empty ())
316 : : {
317 : 869 : info->m_forwarder_bb = split_edge (info->m_true_edge);
318 : 869 : case_bb = info->m_forwarder_bb;
319 : : }
320 : :
321 : 14280 : for (unsigned j = 0; j < info->m_ranges.length (); j++)
322 : 8470 : labels.safe_push (build_case_label (index_type,
323 : 8470 : info->m_ranges[j].low,
324 : 8470 : info->m_ranges[j].high,
325 : : case_bb));
326 : 5810 : default_bb = info->m_false_edge->dest;
327 : :
328 : 5810 : if (i == 0)
329 : : {
330 : 1419 : remove_edge (first_cond->m_true_edge);
331 : 1419 : remove_edge (first_cond->m_false_edge);
332 : : }
333 : : else
334 : 4391 : delete_basic_block (info->m_bb);
335 : :
336 : 5810 : make_edge (first_cond->m_bb, case_bb, 0);
337 : : }
338 : :
339 : 1419 : labels.qsort (label_cmp);
340 : :
341 : 1419 : edge e = find_edge (first_cond->m_bb, default_bb);
342 : 1419 : if (e == NULL)
343 : 1419 : e = make_edge (first_cond->m_bb, default_bb, 0);
344 : 1419 : gswitch *s
345 : 1419 : = 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 : 1419 : gsi_remove (&gsi, true);
351 : 1419 : gsi_insert_before (&gsi, s, GSI_NEW_STMT);
352 : :
353 : 1419 : 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 : 14458 : for (unsigned i = 0; i < chain->m_entries.length (); ++i)
362 : : {
363 : 5810 : condition_info *info = chain->m_entries[i];
364 : 6959 : for (unsigned j = 0; j < info->m_true_edge_phi_mapping.length (); ++j)
365 : : {
366 : 1149 : std::pair<gphi *, tree> item = info->m_true_edge_phi_mapping[j];
367 : 1149 : add_phi_arg (item.first, item.second,
368 : 1149 : single_succ_edge (info->m_forwarder_bb),
369 : : UNKNOWN_LOCATION);
370 : : }
371 : : }
372 : :
373 : : /* Fill up missing PHI nodes for the default BB. */
374 : 1712 : for (unsigned j = 0; j < last_cond->m_false_edge_phi_mapping.length (); ++j)
375 : : {
376 : 293 : std::pair<gphi *, tree> item = last_cond->m_false_edge_phi_mapping[j];
377 : 293 : add_phi_arg (item.first, item.second, e, UNKNOWN_LOCATION);
378 : : }
379 : 1419 : }
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 : 11647805 : find_conditions (basic_block bb,
386 : : hash_map<basic_block, condition_info *> *conditions_in_bbs)
387 : : {
388 : 11647805 : gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
389 : 11647805 : if (gsi_end_p (gsi))
390 : 9816491 : return;
391 : :
392 : 13361457 : gcond *cond = dyn_cast<gcond *> (gsi_stmt (gsi));
393 : 3544966 : if (cond == NULL)
394 : : return;
395 : :
396 : 3544966 : tree lhs = gimple_cond_lhs (cond);
397 : 3544966 : tree rhs = gimple_cond_rhs (cond);
398 : 3544966 : tree_code code = gimple_cond_code (cond);
399 : :
400 : 3544966 : condition_info *info = new condition_info (cond, !no_side_effect_bb (bb));
401 : :
402 : 3544966 : gassign *def;
403 : 3544966 : if (code == NE_EXPR
404 : 1791203 : && TREE_CODE (lhs) == SSA_NAME
405 : 1784736 : && (def = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (lhs))) != NULL
406 : 4497274 : && integer_zerop (rhs))
407 : : {
408 : 543864 : enum tree_code rhs_code = gimple_assign_rhs_code (def);
409 : 543864 : if (rhs_code == BIT_IOR_EXPR)
410 : : {
411 : 29577 : info->m_ranges.safe_grow (2, true);
412 : 29577 : init_range_entry (&info->m_ranges[0], gimple_assign_rhs1 (def), NULL);
413 : 59154 : init_range_entry (&info->m_ranges[1], gimple_assign_rhs2 (def), NULL);
414 : : }
415 : : }
416 : : else
417 : : {
418 : 3001102 : info->m_ranges.safe_grow (1, true);
419 : 3001102 : 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 : 3544966 : if (!info->m_ranges.is_empty ())
424 : : {
425 : 3030679 : edge true_edge, false_edge;
426 : 3030679 : tree expr = info->m_ranges[0].exp;
427 : 3030679 : bool in_p = info->m_ranges[0].in_p;
428 : :
429 : 3030679 : extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
430 : 3030679 : info->m_true_edge = in_p ? true_edge : false_edge;
431 : 3030679 : info->m_false_edge = in_p ? false_edge : true_edge;
432 : :
433 : 9566854 : for (unsigned i = 0; i < info->m_ranges.length (); ++i)
434 : 3053822 : if (info->m_ranges[i].exp == NULL_TREE
435 : 2127912 : || !INTEGRAL_TYPE_P (TREE_TYPE (info->m_ranges[i].exp))
436 : 1939098 : || info->m_ranges[i].low == NULL_TREE
437 : 1809841 : || info->m_ranges[i].high == NULL_TREE
438 : 4807000 : || (TYPE_PRECISION (TREE_TYPE (info->m_ranges[i].low))
439 : 1753178 : != TYPE_PRECISION (TREE_TYPE (info->m_ranges[i].high))))
440 : 1317027 : goto exit;
441 : :
442 : 1735893 : for (unsigned i = 1; i < info->m_ranges.length (); ++i)
443 : 22241 : if (info->m_ranges[i].exp != expr
444 : 22241 : || info->m_ranges[i].in_p != in_p)
445 : 15953 : goto exit;
446 : :
447 : 1713652 : info->record_phi_mapping (info->m_true_edge,
448 : : &info->m_true_edge_phi_mapping);
449 : 1713652 : info->record_phi_mapping (info->m_false_edge,
450 : : &info->m_false_edge_phi_mapping);
451 : 1713652 : conditions_in_bbs->put (bb, info);
452 : 1713652 : return;
453 : : }
454 : :
455 : 1831314 : exit:
456 : 1831314 : 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 : 280114 : pass_if_to_switch (gcc::context *ctxt)
478 : 560228 : : gimple_opt_pass (pass_data_if_to_switch, ctxt)
479 : : {}
480 : :
481 : : /* opt_pass methods: */
482 : 2238990 : bool gate (function *) final override
483 : : {
484 : 2238990 : return (jump_table_cluster::is_enabled ()
485 : 2238990 : || 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 : 2236011 : pass_if_to_switch::execute (function *fun)
494 : : {
495 : 2236011 : auto_vec<if_chain *> all_candidates;
496 : 2236011 : hash_map<basic_block, condition_info *> conditions_in_bbs;
497 : :
498 : 2236011 : mark_ssa_maybe_undefs ();
499 : :
500 : 2236011 : basic_block bb;
501 : 13883816 : FOR_EACH_BB_FN (bb, fun)
502 : 11647805 : find_conditions (bb, &conditions_in_bbs);
503 : :
504 : 2236011 : if (conditions_in_bbs.is_empty ())
505 : : return 0;
506 : :
507 : 440180 : int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun));
508 : 440180 : unsigned n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, false);
509 : :
510 : 440180 : auto_bitmap seen_bbs;
511 : 8328670 : for (int i = n - 1; i >= 0; --i)
512 : : {
513 : 7888490 : basic_block bb = BASIC_BLOCK_FOR_FN (fun, rpo[i]);
514 : 7888490 : if (bitmap_bit_p (seen_bbs, bb->index))
515 : 31972 : continue;
516 : :
517 : 7856518 : bitmap_set_bit (seen_bbs, bb->index);
518 : 7856518 : condition_info **slot = conditions_in_bbs.get (bb);
519 : 7856518 : if (slot)
520 : : {
521 : 1681680 : condition_info *info = *slot;
522 : 1681680 : if_chain *chain = new if_chain ();
523 : 1681680 : chain->m_entries.safe_push (info);
524 : : /* Try to find a chain starting in this BB. */
525 : 1745624 : while (true)
526 : : {
527 : 1713652 : if (!single_pred_p (gimple_bb (info->m_cond)))
528 : : break;
529 : 1183527 : edge e = single_pred_edge (gimple_bb (info->m_cond));
530 : 1183527 : condition_info **info2 = conditions_in_bbs.get (e->src);
531 : 1183527 : 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 : 40228 : if ((*info2)->m_false_edge != e)
538 : : break;
539 : :
540 : : /* Only the first BB in a chain can have a side effect. */
541 : 35814 : if (info->m_has_side_effect)
542 : : break;
543 : :
544 : 31972 : chain->m_entries.safe_push (*info2);
545 : 31972 : bitmap_set_bit (seen_bbs, e->src->index);
546 : 31972 : info = *info2;
547 : 31972 : }
548 : :
549 : 1681680 : chain->m_entries.reverse ();
550 : 1681680 : if (chain->m_entries.length () >= 2
551 : 26104 : && chain->check_non_overlapping_cases ()
552 : 1704793 : && chain->is_beneficial ())
553 : : {
554 : 1419 : gcond *cond = chain->m_entries[0]->m_cond;
555 : 1419 : 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 : 1419 : all_candidates.safe_push (chain);
561 : : }
562 : : else
563 : 1680261 : delete chain;
564 : : }
565 : : }
566 : :
567 : 441599 : for (unsigned i = 0; i < all_candidates.length (); i++)
568 : : {
569 : 1419 : convert_if_conditions_to_switch (all_candidates[i]);
570 : 2838 : delete all_candidates[i];
571 : : }
572 : :
573 : 440180 : free (rpo);
574 : :
575 : 2153832 : for (hash_map<basic_block, condition_info *>::iterator it
576 : 4307664 : = conditions_in_bbs.begin (); it != conditions_in_bbs.end (); ++it)
577 : 1713652 : delete (*it).second;
578 : :
579 : 441500 : if (!all_candidates.is_empty ())
580 : : {
581 : 1320 : free_dominance_info (CDI_DOMINATORS);
582 : 1320 : return TODO_cleanup_cfg;
583 : : }
584 : :
585 : : return 0;
586 : 2676191 : }
587 : :
588 : : } // anon namespace
589 : :
590 : : gimple_opt_pass *
591 : 280114 : make_pass_if_to_switch (gcc::context *ctxt)
592 : : {
593 : 280114 : return new pass_if_to_switch (ctxt);
594 : : }
|
