]>
Commit | Line | Data |
---|---|---|
03eb0929 | 1 | /* If-elseif-else to switch conversion pass |
a945c346 | 2 | Copyright (C) 2020-2024 Free Software Foundation, Inc. |
03eb0929 ML |
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" | |
113475d0 | 57 | #include "tree-ssa.h" |
03eb0929 ML |
58 | |
59 | using namespace tree_switch_conversion; | |
60 | ||
61 | struct condition_info | |
62 | { | |
fa4586d8 | 63 | typedef auto_vec<std::pair<gphi *, tree>> mapping_vec; |
03eb0929 | 64 | |
618bac5b ML |
65 | condition_info (gcond *cond, bool has_side_effect): m_cond (cond), |
66 | m_bb (gimple_bb (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) | |
03eb0929 ML |
70 | { |
71 | 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; | |
fa4586d8 | 81 | auto_vec<range_entry> m_ranges; |
03eb0929 ML |
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; | |
618bac5b | 86 | bool m_has_side_effect; |
03eb0929 ML |
87 | }; |
88 | ||
89 | /* Recond PHI mapping for an original edge E and save these into vector VEC. */ | |
90 | ||
91 | void | |
92 | condition_info::record_phi_mapping (edge e, mapping_vec *vec) | |
93 | { | |
94 | for (gphi_iterator gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); | |
95 | gsi_next (&gsi)) | |
96 | { | |
97 | gphi *phi = gsi.phi (); | |
7875e8dc ML |
98 | tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e); |
99 | vec->safe_push (std::make_pair (phi, arg)); | |
03eb0929 ML |
100 | } |
101 | } | |
102 | ||
103 | /* Master structure for one if to switch conversion candidate. */ | |
104 | ||
105 | struct if_chain | |
106 | { | |
107 | /* Default constructor. */ | |
108 | if_chain (): m_entries () | |
109 | { | |
110 | m_entries.create (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 | ||
132 | static int | |
133 | range_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 (re1->low, re2->low); | |
139 | } | |
140 | ||
141 | /* Verify that all case ranges do not overlap. */ | |
142 | ||
143 | bool | |
144 | if_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 (&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 (left->low, right->low) | |
158 | && tree_int_cst_le (right->low, left->high)) | |
159 | return false; | |
160 | } | |
161 | ||
162 | return true; | |
163 | } | |
164 | ||
165 | /* Compare clusters by minimum value. */ | |
166 | ||
167 | static int | |
168 | cluster_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 (sc1->get_low (), sc2->get_high ()); | |
174 | } | |
175 | ||
176 | /* Dump constructed CLUSTERS with prefix MESSAGE. */ | |
177 | ||
178 | static void | |
179 | dump_clusters (vec<cluster *> *clusters, const char *message) | |
180 | { | |
181 | if (dump_file) | |
182 | { | |
183 | fprintf (dump_file, ";; %s: ", message); | |
184 | for (unsigned i = 0; i < clusters->length (); i++) | |
185 | (*clusters)[i]->dump (dump_file, dump_flags & TDF_DETAILS); | |
186 | fprintf (dump_file, "\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 | ||
193 | bool | |
194 | if_chain::is_beneficial () | |
195 | { | |
196 | profile_probability prob = profile_probability::uninitialized (); | |
197 | ||
198 | auto_vec<cluster *> clusters; | |
199 | clusters.create (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 (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 (16); | |
218 | clusters.qsort (cluster_cmp); | |
219 | simple_cluster *left = static_cast<simple_cluster *> (clusters[0]); | |
220 | filtered_clusters.safe_push (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 (wi::to_wide (right->get_low ()) - wi::to_wide | |
231 | (left->get_high ()), wi::one (TYPE_PRECISION (type)))) | |
232 | { | |
233 | left->set_high (right->get_high ()); | |
57d1b68d | 234 | delete right; |
03eb0929 ML |
235 | continue; |
236 | } | |
237 | } | |
238 | ||
239 | left = static_cast<simple_cluster *> (clusters[i]); | |
240 | filtered_clusters.safe_push (left); | |
241 | } | |
242 | ||
243 | dump_clusters (&filtered_clusters, "Canonical GIMPLE case clusters"); | |
244 | ||
245 | vec<cluster *> output | |
246 | = jump_table_cluster::find_jump_tables (filtered_clusters); | |
247 | bool r = output.length () < filtered_clusters.length (); | |
248 | if (r) | |
57d1b68d ML |
249 | { |
250 | dump_clusters (&output, "JT can be built"); | |
251 | release_clusters (output); | |
252 | return true; | |
253 | } | |
254 | else | |
255 | output.release (); | |
03eb0929 ML |
256 | |
257 | output = bit_test_cluster::find_bit_tests (filtered_clusters); | |
258 | r = output.length () < filtered_clusters.length (); | |
259 | if (r) | |
260 | dump_clusters (&output, "BT can be built"); | |
fa4586d8 | 261 | |
57d1b68d | 262 | release_clusters (output); |
03eb0929 ML |
263 | return r; |
264 | } | |
265 | ||
266 | /* Build case label with MIN and MAX values of a given basic block DEST. */ | |
267 | ||
268 | static tree | |
269 | build_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 | ||
282 | static int | |
283 | label_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 | ||
293 | static void | |
294 | convert_if_conditions_to_switch (if_chain *chain) | |
295 | { | |
296 | if (!dbg_cnt (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 (build_case_label (index_type, | |
323 | info->m_ranges[j].low, | |
324 | info->m_ranges[j].high, | |
325 | 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, 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 (dump_file, "Expanded into a new gimple STMT: "); | |
356 | print_gimple_stmt (dump_file, s, 0, TDF_SLIM); | |
357 | putc ('\n', 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 (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 | ||
384 | static void | |
385 | find_conditions (basic_block bb, | |
fa4586d8 | 386 | hash_map<basic_block, condition_info *> *conditions_in_bbs) |
03eb0929 ML |
387 | { |
388 | gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb); | |
389 | if (gsi_end_p (gsi)) | |
390 | return; | |
391 | ||
392 | gcond *cond = dyn_cast<gcond *> (gsi_stmt (gsi)); | |
393 | if (cond == NULL) | |
394 | return; | |
395 | ||
03eb0929 ML |
396 | tree lhs = gimple_cond_lhs (cond); |
397 | tree rhs = gimple_cond_rhs (cond); | |
398 | tree_code code = gimple_cond_code (cond); | |
399 | ||
618bac5b | 400 | condition_info *info = new condition_info (cond, !no_side_effect_bb (bb)); |
03eb0929 ML |
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 (def); | |
409 | if (rhs_code == BIT_IOR_EXPR) | |
410 | { | |
fa4586d8 ML |
411 | info->m_ranges.safe_grow (2, true); |
412 | init_range_entry (&info->m_ranges[0], gimple_assign_rhs1 (def), NULL); | |
413 | init_range_entry (&info->m_ranges[1], gimple_assign_rhs2 (def), NULL); | |
03eb0929 ML |
414 | } |
415 | } | |
416 | else | |
417 | { | |
fa4586d8 ML |
418 | info->m_ranges.safe_grow (1, true); |
419 | init_range_entry (&info->m_ranges[0], NULL_TREE, cond); | |
03eb0929 ML |
420 | } |
421 | ||
422 | /* All identified ranges must have equal expression and IN_P flag. */ | |
fa4586d8 | 423 | if (!info->m_ranges.is_empty ()) |
03eb0929 ML |
424 | { |
425 | edge true_edge, false_edge; | |
fa4586d8 ML |
426 | tree expr = info->m_ranges[0].exp; |
427 | bool in_p = info->m_ranges[0].in_p; | |
03eb0929 ML |
428 | |
429 | extract_true_false_edges_from_block (bb, &true_edge, &false_edge); | |
fa4586d8 ML |
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 (info->m_true_edge, | |
448 | &info->m_true_edge_phi_mapping); | |
449 | info->record_phi_mapping (info->m_false_edge, | |
450 | &info->m_false_edge_phi_mapping); | |
03eb0929 | 451 | conditions_in_bbs->put (bb, info); |
5da5d8a0 | 452 | return; |
03eb0929 ML |
453 | } |
454 | ||
fa4586d8 ML |
455 | exit: |
456 | delete info; | |
03eb0929 ML |
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 */ | |
7875e8dc | 471 | TODO_update_ssa /* todo_flags_finish */ |
03eb0929 ML |
472 | }; |
473 | ||
474 | class pass_if_to_switch : public gimple_opt_pass | |
475 | { | |
476 | public: | |
477 | pass_if_to_switch (gcc::context *ctxt) | |
478 | : gimple_opt_pass (pass_data_if_to_switch, ctxt) | |
479 | {} | |
480 | ||
481 | /* opt_pass methods: */ | |
725793af | 482 | bool gate (function *) final override |
03eb0929 ML |
483 | { |
484 | return (jump_table_cluster::is_enabled () | |
485 | || bit_test_cluster::is_enabled ()); | |
486 | } | |
487 | ||
725793af | 488 | unsigned int execute (function *) final override; |
03eb0929 ML |
489 | |
490 | }; // class pass_if_to_switch | |
491 | ||
492 | unsigned int | |
493 | pass_if_to_switch::execute (function *fun) | |
494 | { | |
495 | auto_vec<if_chain *> all_candidates; | |
fa4586d8 | 496 | hash_map<basic_block, condition_info *> conditions_in_bbs; |
03eb0929 | 497 | |
113475d0 AP |
498 | mark_ssa_maybe_undefs (); |
499 | ||
03eb0929 ML |
500 | basic_block bb; |
501 | FOR_EACH_BB_FN (bb, fun) | |
502 | find_conditions (bb, &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); | |
fa4586d8 ML |
518 | condition_info **slot = conditions_in_bbs.get (bb); |
519 | if (slot) | |
03eb0929 | 520 | { |
fa4586d8 | 521 | condition_info *info = *slot; |
03eb0929 ML |
522 | if_chain *chain = new if_chain (); |
523 | chain->m_entries.safe_push (info); | |
524 | /* Try to find a chain starting in this BB. */ | |
525 | while (true) | |
526 | { | |
527 | if (!single_pred_p (gimple_bb (info->m_cond))) | |
528 | break; | |
529 | edge e = single_pred_edge (gimple_bb (info->m_cond)); | |
fa4586d8 ML |
530 | condition_info **info2 = conditions_in_bbs.get (e->src); |
531 | if (!info2 || info->m_ranges[0].exp != (*info2)->m_ranges[0].exp) | |
03eb0929 ML |
532 | break; |
533 | ||
f7251a2c ML |
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. */ | |
fa4586d8 | 537 | if ((*info2)->m_false_edge != e) |
f7251a2c ML |
538 | break; |
539 | ||
618bac5b ML |
540 | /* Only the first BB in a chain can have a side effect. */ |
541 | if (info->m_has_side_effect) | |
542 | break; | |
543 | ||
fa4586d8 | 544 | chain->m_entries.safe_push (*info2); |
03eb0929 | 545 | bitmap_set_bit (seen_bbs, e->src->index); |
fa4586d8 | 546 | info = *info2; |
03eb0929 ML |
547 | } |
548 | ||
549 | chain->m_entries.reverse (); | |
c961e949 | 550 | if (chain->m_entries.length () >= 2 |
03eb0929 ML |
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 (chain); | |
561 | } | |
fa4586d8 ML |
562 | else |
563 | delete chain; | |
03eb0929 ML |
564 | } |
565 | } | |
566 | ||
567 | for (unsigned i = 0; i < all_candidates.length (); i++) | |
568 | { | |
569 | convert_if_conditions_to_switch (all_candidates[i]); | |
570 | delete all_candidates[i]; | |
571 | } | |
572 | ||
573 | free (rpo); | |
574 | ||
fa4586d8 ML |
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 | ||
03eb0929 ML |
579 | if (!all_candidates.is_empty ()) |
580 | { | |
581 | free_dominance_info (CDI_DOMINATORS); | |
7875e8dc | 582 | return TODO_cleanup_cfg; |
03eb0929 ML |
583 | } |
584 | ||
585 | return 0; | |
586 | } | |
587 | ||
588 | } // anon namespace | |
589 | ||
590 | gimple_opt_pass * | |
591 | make_pass_if_to_switch (gcc::context *ctxt) | |
592 | { | |
593 | return new pass_if_to_switch (ctxt); | |
594 | } |