1 | /* Loop unswitching. |
2 | Copyright (C) 2004-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 it |
7 | under the terms of the GNU General Public License as published by the |
8 | Free Software Foundation; either version 3, or (at your option) any |
9 | later version. |
10 | |
11 | GCC is distributed in the hope that it will be useful, but WITHOUT |
12 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
13 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
14 | 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 | #include "config.h" |
21 | #include "system.h" |
22 | #include "coretypes.h" |
23 | #include "backend.h" |
24 | #include "tree.h" |
25 | #include "gimple.h" |
26 | #include "tree-pass.h" |
27 | #include "ssa.h" |
28 | #include "fold-const.h" |
29 | #include "gimplify.h" |
30 | #include "tree-cfg.h" |
31 | #include "tree-ssa.h" |
32 | #include "tree-ssa-loop-niter.h" |
33 | #include "tree-ssa-loop.h" |
34 | #include "tree-into-ssa.h" |
35 | #include "cfgloop.h" |
36 | #include "tree-inline.h" |
37 | #include "gimple-iterator.h" |
38 | #include "cfghooks.h" |
39 | #include "tree-ssa-loop-manip.h" |
40 | #include "tree-vectorizer.h" |
41 | #include "tree-pretty-print.h" |
42 | #include "gimple-range.h" |
43 | #include "dbgcnt.h" |
44 | #include "cfganal.h" |
45 | |
46 | /* This file implements the loop unswitching, i.e. transformation of loops like |
47 | |
48 | while (A) |
49 | { |
50 | if (inv) |
51 | B; |
52 | |
53 | X; |
54 | |
55 | if (!inv) |
56 | C; |
57 | } |
58 | |
59 | where inv is the loop invariant, into |
60 | |
61 | if (inv) |
62 | { |
63 | while (A) |
64 | { |
65 | B; |
66 | X; |
67 | } |
68 | } |
69 | else |
70 | { |
71 | while (A) |
72 | { |
73 | X; |
74 | C; |
75 | } |
76 | } |
77 | |
78 | Inv is considered invariant iff the values it compares are both invariant; |
79 | tree-ssa-loop-im.cc ensures that all the suitable conditions are in this |
80 | shape. */ |
81 | |
82 | /* Loop unswitching algorithm for innermost loops works in the following steps: |
83 | |
84 | 1) Number of instructions is estimated for each BB that belongs to a loop. |
85 | 2) Unswitching candidates are found for gcond and gswitch statements |
86 | (note that an unswitching predicate for a gswitch actually corresponds |
87 | to a non-default edge so it can contain multiple cases). |
88 | 3) The so called unswitch predicates are stored in a cache where the |
89 | gimple_uid of the last stmt in a basic-block is an index to the cache. |
90 | 4) We consider one by one the unswitching candidates and calculate BBs that |
91 | will be reachable in the unswitch version. |
92 | 5) A selected predicate is chosen and we simplify the CFG (dead edges) in |
93 | both versions of the loop. We utilize both Ranger for condition |
94 | simplification and also symbol equivalence. The folded if conditions |
95 | are replaced with true/false values, while for gswitch we mark the |
96 | corresponding edges with a pass-defined unreachable flag. |
97 | 6) Every time we unswitch a loop, we save unswitch_predicate to a vector |
98 | together with information if true or false edge was taken. Doing that |
99 | we have a so called PREDICATE_PATH that is utilized for simplification |
100 | of the cloned loop. |
101 | 7) The process is repeated until we reach a growth threshold or all |
102 | unswitching opportunities are taken. */ |
103 | |
104 | /* A tuple that holds a GENERIC condition and value range for an unswitching |
105 | predicate. */ |
106 | |
107 | struct unswitch_predicate |
108 | { |
109 | /* CTOR for a switch edge predicate. */ |
110 | unswitch_predicate (tree cond, tree lhs_, int edge_index_, edge e, |
111 | const int_range_max& edge_range) |
112 | : condition (cond), lhs (lhs_), |
113 | true_range (edge_range), edge_index (edge_index_), switch_p (true) |
114 | { |
115 | gcc_assert (!(e->flags & (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE)) |
116 | && irange::supports_p (TREE_TYPE (lhs))); |
117 | false_range = true_range; |
118 | if (!false_range.varying_p () |
119 | && !false_range.undefined_p ()) |
120 | false_range.invert (); |
121 | count = e->count (); |
122 | num = predicates->length (); |
123 | predicates->safe_push (obj: this); |
124 | } |
125 | |
126 | /* CTOR for a GIMPLE condition statement. */ |
127 | unswitch_predicate (gcond *stmt) |
128 | : switch_p (false) |
129 | { |
130 | basic_block bb = gimple_bb (g: stmt); |
131 | if (EDGE_SUCC (bb, 0)->flags & EDGE_TRUE_VALUE) |
132 | edge_index = 0; |
133 | else |
134 | edge_index = 1; |
135 | lhs = gimple_cond_lhs (gs: stmt); |
136 | tree rhs = gimple_cond_rhs (gs: stmt); |
137 | enum tree_code code = gimple_cond_code (gs: stmt); |
138 | condition = build2 (code, boolean_type_node, lhs, rhs); |
139 | count = EDGE_SUCC (bb, 0)->count ().max (EDGE_SUCC (bb, 1)->count ()); |
140 | if (irange::supports_p (TREE_TYPE (lhs))) |
141 | { |
142 | auto range_op = range_op_handler (code); |
143 | int_range<2> rhs_range (TREE_TYPE (rhs)); |
144 | if (CONSTANT_CLASS_P (rhs)) |
145 | { |
146 | wide_int w = wi::to_wide (t: rhs); |
147 | rhs_range.set (TREE_TYPE (rhs), w, w); |
148 | } |
149 | if (!range_op.op1_range (r&: true_range, TREE_TYPE (lhs), |
150 | lhs: range_true (), op2: rhs_range) |
151 | || !range_op.op1_range (r&: false_range, TREE_TYPE (lhs), |
152 | lhs: range_false (), op2: rhs_range)) |
153 | { |
154 | true_range.set_varying (TREE_TYPE (lhs)); |
155 | false_range.set_varying (TREE_TYPE (lhs)); |
156 | } |
157 | } |
158 | num = predicates->length (); |
159 | predicates->safe_push (obj: this); |
160 | } |
161 | |
162 | /* Copy ranges for purpose of usage in predicate path. */ |
163 | |
164 | inline void |
165 | copy_merged_ranges () |
166 | { |
167 | merged_true_range = true_range; |
168 | merged_false_range = false_range; |
169 | } |
170 | |
171 | /* GENERIC unswitching expression testing LHS against CONSTANT. */ |
172 | tree condition; |
173 | |
174 | /* LHS of the expression. */ |
175 | tree lhs; |
176 | |
177 | /* Initial ranges (when the expression is true/false) for the expression. */ |
178 | int_range_max true_range = {}, false_range = {}; |
179 | |
180 | /* Modified range that is part of a predicate path. */ |
181 | int_range_max merged_true_range = {}, merged_false_range = {}; |
182 | |
183 | /* Index of the edge the predicate belongs to in the successor vector. */ |
184 | int edge_index; |
185 | |
186 | /* The profile count of this predicate. */ |
187 | profile_count count; |
188 | |
189 | /* Whether the predicate was created from a switch statement. */ |
190 | bool switch_p; |
191 | |
192 | /* The number of the predicate in the predicates vector below. */ |
193 | unsigned num; |
194 | |
195 | /* Vector of all used predicates, used for assigning a unique id that |
196 | can be used for bitmap operations. */ |
197 | static vec<unswitch_predicate *> *predicates; |
198 | }; |
199 | |
200 | vec<unswitch_predicate *> *unswitch_predicate::predicates; |
201 | |
202 | /* Ranger instance used in the pass. */ |
203 | static gimple_ranger *ranger = NULL; |
204 | |
205 | /* Cache storage for unswitch_predicate belonging to a basic block. */ |
206 | static vec<vec<unswitch_predicate *>> *bb_predicates; |
207 | |
208 | /* The type represents a predicate path leading to a basic block. */ |
209 | typedef vec<std::pair<unswitch_predicate *, bool>> predicate_vector; |
210 | |
211 | static class loop *tree_unswitch_loop (class loop *, edge, tree); |
212 | static bool tree_unswitch_single_loop (class loop *, dump_user_location_t, |
213 | predicate_vector &predicate_path, |
214 | unsigned loop_size, unsigned &budget, |
215 | int ignored_edge_flag, bitmap, |
216 | unswitch_predicate * = NULL, |
217 | basic_block = NULL); |
218 | static void |
219 | find_unswitching_predicates_for_bb (basic_block bb, class loop *loop, |
220 | class loop *&outer_loop, |
221 | vec<unswitch_predicate *> &candidates, |
222 | unswitch_predicate *&hottest, |
223 | basic_block &hottest_bb); |
224 | static bool tree_unswitch_outer_loop (class loop *); |
225 | static edge find_loop_guard (class loop *, vec<gimple *>&); |
226 | static bool empty_bb_without_guard_p (class loop *, basic_block, |
227 | vec<gimple *>&); |
228 | static bool used_outside_loop_p (class loop *, tree, vec<gimple *>&); |
229 | static void hoist_guard (class loop *, edge); |
230 | static bool check_exit_phi (class loop *); |
231 | static tree get_vop_from_header (class loop *); |
232 | static void clean_up_after_unswitching (int); |
233 | |
234 | /* Return vector of predicates that belong to a basic block. */ |
235 | |
236 | static vec<unswitch_predicate *> & |
237 | get_predicates_for_bb (basic_block bb) |
238 | { |
239 | gimple *last = last_nondebug_stmt (bb); |
240 | return (*bb_predicates)[last == NULL ? 0 : gimple_uid (g: last)]; |
241 | } |
242 | |
243 | /* Save predicates that belong to a basic block. */ |
244 | |
245 | static void |
246 | set_predicates_for_bb (basic_block bb, vec<unswitch_predicate *> predicates) |
247 | { |
248 | gimple_set_uid (g: last_nondebug_stmt (bb), uid: bb_predicates->length ()); |
249 | bb_predicates->safe_push (obj: predicates); |
250 | } |
251 | |
252 | /* Initialize LOOP information reused during the unswitching pass. |
253 | Return total number of instructions in the loop. Adjusts LOOP to |
254 | the outermost loop all candidates are invariant in. */ |
255 | |
256 | static unsigned |
257 | init_loop_unswitch_info (class loop *&loop, unswitch_predicate *&hottest, |
258 | basic_block &hottest_bb) |
259 | { |
260 | unsigned total_insns = 0; |
261 | |
262 | basic_block *bbs = get_loop_body (loop); |
263 | |
264 | /* Unswitch only nests with no sibling loops. */ |
265 | class loop *outer_loop = loop; |
266 | unsigned max_depth = param_max_unswitch_depth; |
267 | while (loop_outer (loop: outer_loop)->num != 0 |
268 | && !loop_outer (loop: outer_loop)->inner->next |
269 | && --max_depth != 0) |
270 | outer_loop = loop_outer (loop: outer_loop); |
271 | hottest = NULL; |
272 | hottest_bb = NULL; |
273 | /* Find all unswitching candidates in the innermost loop. */ |
274 | for (unsigned i = 0; i != loop->num_nodes; i++) |
275 | { |
276 | /* Find a bb to unswitch on. */ |
277 | vec<unswitch_predicate *> candidates; |
278 | candidates.create (nelems: 1); |
279 | find_unswitching_predicates_for_bb (bb: bbs[i], loop, outer_loop, candidates, |
280 | hottest, hottest_bb); |
281 | if (!candidates.is_empty ()) |
282 | set_predicates_for_bb (bb: bbs[i], predicates: candidates); |
283 | else |
284 | { |
285 | candidates.release (); |
286 | gimple *last = last_nondebug_stmt (bbs[i]); |
287 | if (last != NULL) |
288 | gimple_set_uid (g: last, uid: 0); |
289 | } |
290 | } |
291 | |
292 | if (outer_loop != loop) |
293 | { |
294 | free (ptr: bbs); |
295 | bbs = get_loop_body (outer_loop); |
296 | } |
297 | |
298 | /* Calculate instruction count. */ |
299 | for (unsigned i = 0; i < outer_loop->num_nodes; i++) |
300 | { |
301 | unsigned insns = 0; |
302 | for (gimple_stmt_iterator gsi = gsi_start_bb (bb: bbs[i]); !gsi_end_p (i: gsi); |
303 | gsi_next (i: &gsi)) |
304 | insns += estimate_num_insns (gsi_stmt (i: gsi), &eni_size_weights); |
305 | /* No predicates to unswitch on in the outer loops. */ |
306 | if (!flow_bb_inside_loop_p (loop, bbs[i])) |
307 | { |
308 | gimple *last = last_nondebug_stmt (bbs[i]); |
309 | if (last != NULL) |
310 | gimple_set_uid (g: last, uid: 0); |
311 | } |
312 | |
313 | bbs[i]->aux = (void *)(uintptr_t)insns; |
314 | total_insns += insns; |
315 | } |
316 | |
317 | free (ptr: bbs); |
318 | |
319 | loop = outer_loop; |
320 | return total_insns; |
321 | } |
322 | |
323 | /* Main entry point. Perform loop unswitching on all suitable loops. */ |
324 | |
325 | unsigned int |
326 | tree_ssa_unswitch_loops (function *fun) |
327 | { |
328 | bool changed_unswitch = false; |
329 | bool changed_hoist = false; |
330 | auto_edge_flag ignored_edge_flag (fun); |
331 | |
332 | ranger = enable_ranger (m: fun); |
333 | |
334 | /* Go through all loops starting from innermost, hoisting guards. */ |
335 | for (auto loop : loops_list (fun, LI_FROM_INNERMOST)) |
336 | { |
337 | if (loop->inner) |
338 | changed_hoist |= tree_unswitch_outer_loop (loop); |
339 | } |
340 | |
341 | /* Go through innermost loops, unswitching on invariant predicates |
342 | within those. */ |
343 | for (auto loop : loops_list (fun, LI_ONLY_INNERMOST)) |
344 | { |
345 | /* Perform initial tests if unswitch is eligible. */ |
346 | dump_user_location_t loc = find_loop_location (loop); |
347 | |
348 | /* Do not unswitch in cold regions. */ |
349 | if (optimize_loop_for_size_p (loop)) |
350 | { |
351 | if (dump_enabled_p ()) |
352 | dump_printf_loc (MSG_NOTE, loc, |
353 | "Not unswitching cold loops\n" ); |
354 | continue; |
355 | } |
356 | |
357 | /* If the loop is not expected to iterate, there is no need |
358 | for unswitching. */ |
359 | HOST_WIDE_INT iterations = estimated_loop_iterations_int (loop); |
360 | if (iterations < 0) |
361 | iterations = likely_max_loop_iterations_int (loop); |
362 | if (iterations >= 0 && iterations <= 1) |
363 | { |
364 | if (dump_enabled_p ()) |
365 | dump_printf_loc (MSG_NOTE, loc, |
366 | "Not unswitching, loop is not expected" |
367 | " to iterate\n" ); |
368 | continue; |
369 | } |
370 | |
371 | bb_predicates = new vec<vec<unswitch_predicate *>> (); |
372 | bb_predicates->safe_push (obj: vec<unswitch_predicate *> ()); |
373 | unswitch_predicate::predicates = new vec<unswitch_predicate *> (); |
374 | |
375 | /* Unswitch loop. */ |
376 | unswitch_predicate *hottest; |
377 | basic_block hottest_bb; |
378 | unsigned int loop_size = init_loop_unswitch_info (loop, hottest, |
379 | hottest_bb); |
380 | unsigned int budget = loop_size + param_max_unswitch_insns; |
381 | |
382 | predicate_vector predicate_path; |
383 | predicate_path.create (nelems: 8); |
384 | auto_bitmap handled; |
385 | changed_unswitch |= tree_unswitch_single_loop (loop, loc, predicate_path, |
386 | loop_size, budget, |
387 | ignored_edge_flag, handled, |
388 | hottest, hottest_bb); |
389 | predicate_path.release (); |
390 | |
391 | for (auto predlist : bb_predicates) |
392 | predlist.release (); |
393 | bb_predicates->release (); |
394 | delete bb_predicates; |
395 | bb_predicates = NULL; |
396 | |
397 | for (auto pred : unswitch_predicate::predicates) |
398 | delete pred; |
399 | unswitch_predicate::predicates->release (); |
400 | delete unswitch_predicate::predicates; |
401 | unswitch_predicate::predicates = NULL; |
402 | } |
403 | |
404 | disable_ranger (fun); |
405 | clear_aux_for_blocks (); |
406 | |
407 | if (changed_unswitch) |
408 | clean_up_after_unswitching (ignored_edge_flag); |
409 | |
410 | if (changed_unswitch || changed_hoist) |
411 | return TODO_cleanup_cfg; |
412 | |
413 | return 0; |
414 | } |
415 | |
416 | /* Return TRUE if an SSA_NAME maybe undefined and is therefore |
417 | unsuitable for unswitching. STMT is the statement we are |
418 | considering for unswitching and LOOP is the loop it appears in. */ |
419 | |
420 | static bool |
421 | is_maybe_undefined (const tree name, gimple *stmt, class loop *loop) |
422 | { |
423 | /* The loop header is the only block we can trivially determine that |
424 | will always be executed. If the comparison is in the loop |
425 | header, we know it's OK to unswitch on it. */ |
426 | if (gimple_bb (g: stmt) == loop->header) |
427 | return false; |
428 | |
429 | auto_bitmap visited_ssa; |
430 | auto_vec<tree> worklist; |
431 | worklist.safe_push (obj: name); |
432 | bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (name)); |
433 | while (!worklist.is_empty ()) |
434 | { |
435 | tree t = worklist.pop (); |
436 | |
437 | /* If it's obviously undefined, avoid further computations. */ |
438 | if (ssa_undefined_value_p (t, true)) |
439 | return true; |
440 | |
441 | if (ssa_defined_default_def_p (t)) |
442 | continue; |
443 | |
444 | gimple *def = SSA_NAME_DEF_STMT (t); |
445 | |
446 | /* Check that all the PHI args are fully defined. */ |
447 | if (gphi *phi = dyn_cast <gphi *> (p: def)) |
448 | { |
449 | for (unsigned i = 0; i < gimple_phi_num_args (gs: phi); ++i) |
450 | { |
451 | tree t = gimple_phi_arg_def (gs: phi, index: i); |
452 | /* If an SSA has already been seen, it may be a loop, |
453 | but we can continue and ignore this use. Otherwise, |
454 | add the SSA_NAME to the queue and visit it later. */ |
455 | if (TREE_CODE (t) == SSA_NAME |
456 | && bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t))) |
457 | worklist.safe_push (obj: t); |
458 | } |
459 | continue; |
460 | } |
461 | |
462 | /* Uses in stmts always executed when the region header executes |
463 | are fine. */ |
464 | if (dominated_by_p (CDI_DOMINATORS, loop->header, gimple_bb (g: def))) |
465 | continue; |
466 | |
467 | /* Handle calls and memory loads conservatively. */ |
468 | if (!is_gimple_assign (gs: def) |
469 | || (gimple_assign_single_p (gs: def) |
470 | && gimple_vuse (g: def))) |
471 | return true; |
472 | |
473 | /* Check that any SSA names used to define NAME are also fully |
474 | defined. */ |
475 | use_operand_p use_p; |
476 | ssa_op_iter iter; |
477 | FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE) |
478 | { |
479 | tree t = USE_FROM_PTR (use_p); |
480 | /* If an SSA has already been seen, it may be a loop, |
481 | but we can continue and ignore this use. Otherwise, |
482 | add the SSA_NAME to the queue and visit it later. */ |
483 | if (bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t))) |
484 | worklist.safe_push (obj: t); |
485 | } |
486 | } |
487 | return false; |
488 | } |
489 | |
490 | /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its |
491 | basic blocks (for what it means see comments below). |
492 | All candidates all filled to the provided vector CANDIDATES. |
493 | OUTER_LOOP is updated to the innermost loop all found candidates are |
494 | invariant in. */ |
495 | |
496 | static void |
497 | find_unswitching_predicates_for_bb (basic_block bb, class loop *loop, |
498 | class loop *&outer_loop, |
499 | vec<unswitch_predicate *> &candidates, |
500 | unswitch_predicate *&hottest, |
501 | basic_block &hottest_bb) |
502 | { |
503 | gimple *last, *def; |
504 | tree use; |
505 | basic_block def_bb; |
506 | ssa_op_iter iter; |
507 | |
508 | /* BB must end in a simple conditional jump. */ |
509 | last = *gsi_last_bb (bb); |
510 | if (!last) |
511 | return; |
512 | |
513 | if (gcond *stmt = safe_dyn_cast <gcond *> (p: last)) |
514 | { |
515 | /* To keep the things simple, we do not directly remove the conditions, |
516 | but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite |
517 | loop where we would unswitch again on such a condition. */ |
518 | if (gimple_cond_true_p (gs: stmt) || gimple_cond_false_p (gs: stmt)) |
519 | return; |
520 | |
521 | /* At least the LHS needs to be symbolic. */ |
522 | if (TREE_CODE (gimple_cond_lhs (stmt)) != SSA_NAME) |
523 | return; |
524 | |
525 | /* Condition must be invariant. */ |
526 | FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) |
527 | { |
528 | def = SSA_NAME_DEF_STMT (use); |
529 | def_bb = gimple_bb (g: def); |
530 | if (def_bb |
531 | && flow_bb_inside_loop_p (loop, def_bb)) |
532 | return; |
533 | /* Unswitching on undefined values would introduce undefined |
534 | behavior that the original program might never exercise. */ |
535 | if (is_maybe_undefined (name: use, stmt, loop)) |
536 | return; |
537 | } |
538 | /* Narrow OUTER_LOOP. */ |
539 | if (outer_loop != loop) |
540 | FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) |
541 | { |
542 | def = SSA_NAME_DEF_STMT (use); |
543 | def_bb = gimple_bb (g: def); |
544 | while (outer_loop != loop |
545 | && ((def_bb && flow_bb_inside_loop_p (outer_loop, def_bb)) |
546 | || is_maybe_undefined (name: use, stmt, loop: outer_loop))) |
547 | outer_loop = superloop_at_depth (loop, |
548 | loop_depth (loop: outer_loop) + 1); |
549 | } |
550 | |
551 | unswitch_predicate *predicate = new unswitch_predicate (stmt); |
552 | candidates.safe_push (obj: predicate); |
553 | /* If we unswitch on this predicate we isolate both paths, so |
554 | pick the highest count for updating of the hottest predicate |
555 | to unswitch on first. */ |
556 | if (!hottest || predicate->count > hottest->count) |
557 | { |
558 | hottest = predicate; |
559 | hottest_bb = bb; |
560 | } |
561 | } |
562 | else if (gswitch *stmt = safe_dyn_cast <gswitch *> (p: last)) |
563 | { |
564 | unsigned nlabels = gimple_switch_num_labels (gs: stmt); |
565 | tree idx = gimple_switch_index (gs: stmt); |
566 | tree idx_type = TREE_TYPE (idx); |
567 | if (!gimple_range_ssa_p (exp: idx) || nlabels < 1) |
568 | return; |
569 | /* Index must be invariant. */ |
570 | def = SSA_NAME_DEF_STMT (idx); |
571 | def_bb = gimple_bb (g: def); |
572 | if (def_bb |
573 | && flow_bb_inside_loop_p (loop, def_bb)) |
574 | return; |
575 | /* Unswitching on undefined values would introduce undefined |
576 | behavior that the original program might never exercise. */ |
577 | if (is_maybe_undefined (name: idx, stmt, loop)) |
578 | return; |
579 | /* Narrow OUTER_LOOP. */ |
580 | while (outer_loop != loop |
581 | && ((def_bb && flow_bb_inside_loop_p (outer_loop, def_bb)) |
582 | || is_maybe_undefined (name: idx, stmt, loop: outer_loop))) |
583 | outer_loop = superloop_at_depth (loop, |
584 | loop_depth (loop: outer_loop) + 1); |
585 | |
586 | /* Build compound expression for all outgoing edges of the switch. */ |
587 | auto_vec<tree, 16> preds; |
588 | auto_vec<int_range_max> edge_range; |
589 | preds.safe_grow_cleared (EDGE_COUNT (gimple_bb (stmt)->succs), exact: true); |
590 | edge_range.safe_grow_cleared (EDGE_COUNT (gimple_bb (stmt)->succs), exact: true); |
591 | edge e; |
592 | edge_iterator ei; |
593 | unsigned edge_index = 0; |
594 | FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs) |
595 | e->aux = (void *)(uintptr_t)edge_index++; |
596 | for (unsigned i = 1; i < gimple_switch_num_labels (gs: stmt); ++i) |
597 | { |
598 | tree lab = gimple_switch_label (gs: stmt, index: i); |
599 | tree cmp; |
600 | int_range<2> lab_range; |
601 | tree low = fold_convert (idx_type, CASE_LOW (lab)); |
602 | if (CASE_HIGH (lab) != NULL_TREE) |
603 | { |
604 | tree high = fold_convert (idx_type, CASE_HIGH (lab)); |
605 | tree cmp1 = fold_build2 (GE_EXPR, boolean_type_node, idx, low); |
606 | tree cmp2 = fold_build2 (LE_EXPR, boolean_type_node, idx, high); |
607 | cmp = fold_build2 (BIT_AND_EXPR, boolean_type_node, cmp1, cmp2); |
608 | lab_range.set (type: idx_type, wi::to_wide (t: low), wi::to_wide (t: high)); |
609 | } |
610 | else |
611 | { |
612 | cmp = fold_build2 (EQ_EXPR, boolean_type_node, idx, low); |
613 | wide_int w = wi::to_wide (t: low); |
614 | lab_range.set (type: idx_type, w, w); |
615 | } |
616 | |
617 | /* Combine the expression with the existing one. */ |
618 | basic_block dest = label_to_block (cfun, CASE_LABEL (lab)); |
619 | e = find_edge (gimple_bb (g: stmt), dest); |
620 | tree &expr = preds[(uintptr_t)e->aux]; |
621 | if (expr == NULL_TREE) |
622 | expr = cmp; |
623 | else |
624 | expr = fold_build2 (BIT_IOR_EXPR, boolean_type_node, expr, cmp); |
625 | edge_range[(uintptr_t)e->aux].union_ (lab_range); |
626 | } |
627 | |
628 | /* Now register the predicates. */ |
629 | for (edge_index = 0; edge_index < preds.length (); ++edge_index) |
630 | { |
631 | edge e = EDGE_SUCC (gimple_bb (stmt), edge_index); |
632 | e->aux = NULL; |
633 | if (preds[edge_index] != NULL_TREE) |
634 | { |
635 | unswitch_predicate *predicate |
636 | = new unswitch_predicate (preds[edge_index], idx, |
637 | edge_index, e, |
638 | edge_range[edge_index]); |
639 | candidates.safe_push (obj: predicate); |
640 | if (!hottest || predicate->count > hottest->count) |
641 | { |
642 | hottest = predicate; |
643 | hottest_bb = bb; |
644 | } |
645 | } |
646 | } |
647 | } |
648 | } |
649 | |
650 | /* Merge ranges for the last item of PREDICATE_PATH with a predicate |
651 | that shared the same LHS. */ |
652 | |
653 | static void |
654 | merge_last (predicate_vector &predicate_path) |
655 | { |
656 | unswitch_predicate *last_predicate = predicate_path.last ().first; |
657 | |
658 | for (int i = predicate_path.length () - 2; i >= 0; i--) |
659 | { |
660 | unswitch_predicate *predicate = predicate_path[i].first; |
661 | bool true_edge = predicate_path[i].second; |
662 | |
663 | if (operand_equal_p (predicate->lhs, last_predicate->lhs, flags: 0)) |
664 | { |
665 | irange &other = (true_edge ? predicate->merged_true_range |
666 | : predicate->merged_false_range); |
667 | last_predicate->merged_true_range.intersect (other); |
668 | last_predicate->merged_false_range.intersect (other); |
669 | return; |
670 | } |
671 | } |
672 | } |
673 | |
674 | /* Add PREDICATE to PREDICATE_PATH on TRUE_EDGE. */ |
675 | |
676 | static void |
677 | add_predicate_to_path (predicate_vector &predicate_path, |
678 | unswitch_predicate *predicate, bool true_edge) |
679 | { |
680 | predicate->copy_merged_ranges (); |
681 | predicate_path.safe_push (obj: std::make_pair (x&: predicate, y&: true_edge)); |
682 | merge_last (predicate_path); |
683 | } |
684 | |
685 | static bool |
686 | find_range_for_lhs (predicate_vector &predicate_path, tree lhs, |
687 | int_range_max &range) |
688 | { |
689 | for (int i = predicate_path.length () - 1; i >= 0; i--) |
690 | { |
691 | unswitch_predicate *predicate = predicate_path[i].first; |
692 | bool true_edge = predicate_path[i].second; |
693 | |
694 | if (operand_equal_p (predicate->lhs, lhs, flags: 0)) |
695 | { |
696 | range = (true_edge ? predicate->merged_true_range |
697 | : predicate->merged_false_range); |
698 | return !range.undefined_p (); |
699 | } |
700 | } |
701 | |
702 | return false; |
703 | } |
704 | |
705 | /* Simplifies STMT using the predicate we unswitched on which is the last |
706 | in PREDICATE_PATH. For switch statements add newly unreachable edges |
707 | to IGNORED_EDGES (but do not set IGNORED_EDGE_FLAG on them). */ |
708 | |
709 | static tree |
710 | evaluate_control_stmt_using_entry_checks (gimple *stmt, |
711 | predicate_vector &predicate_path, |
712 | int ignored_edge_flag, |
713 | hash_set<edge> *ignored_edges) |
714 | { |
715 | unswitch_predicate *last_predicate = predicate_path.last ().first; |
716 | bool true_edge = predicate_path.last ().second; |
717 | |
718 | if (gcond *cond = dyn_cast<gcond *> (p: stmt)) |
719 | { |
720 | tree lhs = gimple_cond_lhs (gs: cond); |
721 | if (!operand_equal_p (lhs, last_predicate->lhs)) |
722 | return NULL_TREE; |
723 | /* Try a symbolic match which works for floating point and fully |
724 | symbolic conditions. */ |
725 | if (gimple_cond_code (gs: cond) == TREE_CODE (last_predicate->condition) |
726 | && operand_equal_p (gimple_cond_rhs (gs: cond), |
727 | TREE_OPERAND (last_predicate->condition, 1))) |
728 | return true_edge ? boolean_true_node : boolean_false_node; |
729 | /* Else try ranger if it supports LHS. */ |
730 | else if (irange::supports_p (TREE_TYPE (lhs))) |
731 | { |
732 | int_range<2> r; |
733 | int_range_max path_range; |
734 | |
735 | if (find_range_for_lhs (predicate_path, lhs, range&: path_range) |
736 | && fold_range (r, s: cond, r1&: path_range) |
737 | && r.singleton_p ()) |
738 | return r.zero_p () ? boolean_false_node : boolean_true_node; |
739 | } |
740 | } |
741 | else if (gswitch *swtch = dyn_cast<gswitch *> (p: stmt)) |
742 | { |
743 | unsigned nlabels = gimple_switch_num_labels (gs: swtch); |
744 | |
745 | tree idx = gimple_switch_index (gs: swtch); |
746 | |
747 | /* Already folded switch. */ |
748 | if (TREE_CONSTANT (idx)) |
749 | return NULL_TREE; |
750 | |
751 | int_range_max path_range; |
752 | if (!find_range_for_lhs (predicate_path, lhs: idx, range&: path_range)) |
753 | return NULL_TREE; |
754 | |
755 | tree result = NULL_TREE; |
756 | edge single_edge = NULL; |
757 | for (unsigned i = 0; i < nlabels; ++i) |
758 | { |
759 | tree lab = gimple_switch_label (gs: swtch, index: i); |
760 | basic_block dest = label_to_block (cfun, CASE_LABEL (lab)); |
761 | edge e = find_edge (gimple_bb (g: stmt), dest); |
762 | if (e->flags & ignored_edge_flag) |
763 | continue; |
764 | |
765 | int_range_max r; |
766 | if (!ranger->gori ().outgoing_edge_range_p (r, e, name: idx, |
767 | q&: *get_global_range_query ())) |
768 | continue; |
769 | r.intersect (path_range); |
770 | if (r.undefined_p ()) |
771 | ignored_edges->add (k: e); |
772 | else |
773 | { |
774 | if (!single_edge) |
775 | { |
776 | single_edge = e; |
777 | result = CASE_LOW (lab); |
778 | } |
779 | else if (single_edge != e) |
780 | result = NULL; |
781 | } |
782 | } |
783 | |
784 | /* Only one edge from the switch is alive. */ |
785 | if (single_edge && result) |
786 | return result; |
787 | } |
788 | |
789 | return NULL_TREE; |
790 | } |
791 | |
792 | /* Simplify LOOP based on PREDICATE_PATH where dead edges are properly |
793 | marked. */ |
794 | |
795 | static bool |
796 | simplify_loop_version (class loop *loop, predicate_vector &predicate_path, |
797 | int ignored_edge_flag, bitmap handled) |
798 | { |
799 | bool changed = false; |
800 | basic_block *bbs = get_loop_body (loop); |
801 | |
802 | hash_set<edge> ignored_edges; |
803 | for (unsigned i = 0; i != loop->num_nodes; i++) |
804 | { |
805 | vec<unswitch_predicate *> &predicates = get_predicates_for_bb (bb: bbs[i]); |
806 | if (predicates.is_empty ()) |
807 | continue; |
808 | |
809 | gimple *stmt = *gsi_last_bb (bb: bbs[i]); |
810 | tree folded = evaluate_control_stmt_using_entry_checks (stmt, |
811 | predicate_path, |
812 | ignored_edge_flag, |
813 | ignored_edges: &ignored_edges); |
814 | |
815 | if (gcond *cond = dyn_cast<gcond *> (p: stmt)) |
816 | { |
817 | if (folded) |
818 | { |
819 | /* Remove path. */ |
820 | if (integer_nonzerop (folded)) |
821 | gimple_cond_set_condition_from_tree (cond, boolean_true_node); |
822 | else |
823 | gimple_cond_set_condition_from_tree (cond, boolean_false_node); |
824 | |
825 | gcc_assert (predicates.length () == 1); |
826 | bitmap_set_bit (handled, predicates[0]->num); |
827 | |
828 | update_stmt (s: cond); |
829 | changed = true; |
830 | } |
831 | } |
832 | else if (gswitch *swtch = dyn_cast<gswitch *> (p: stmt)) |
833 | { |
834 | edge e; |
835 | edge_iterator ei; |
836 | FOR_EACH_EDGE (e, ei, bbs[i]->succs) |
837 | if (ignored_edges.contains (k: e)) |
838 | e->flags |= ignored_edge_flag; |
839 | |
840 | for (unsigned j = 0; j < predicates.length (); j++) |
841 | { |
842 | edge e = EDGE_SUCC (bbs[i], predicates[j]->edge_index); |
843 | if (ignored_edges.contains (k: e)) |
844 | bitmap_set_bit (handled, predicates[j]->num); |
845 | } |
846 | |
847 | if (folded) |
848 | { |
849 | gimple_switch_set_index (gs: swtch, index: folded); |
850 | update_stmt (s: swtch); |
851 | changed = true; |
852 | } |
853 | } |
854 | } |
855 | |
856 | free (ptr: bbs); |
857 | return changed; |
858 | } |
859 | |
860 | /* Evaluate reachable blocks in LOOP and call VISIT on them, aborting the |
861 | DFS walk if VISIT returns true. When PREDICATE_PATH is specified then |
862 | take into account that when computing reachability, otherwise just |
863 | look at the simplified state and IGNORED_EDGE_FLAG. */ |
864 | |
865 | template <typename VisitOp> |
866 | static void |
867 | evaluate_bbs (class loop *loop, predicate_vector *predicate_path, |
868 | int ignored_edge_flag, VisitOp visit) |
869 | { |
870 | auto_bb_flag reachable_flag (cfun); |
871 | auto_vec<basic_block, 10> worklist (loop->num_nodes); |
872 | auto_vec<basic_block, 10> reachable (loop->num_nodes); |
873 | hash_set<edge> ignored_edges; |
874 | |
875 | loop->header->flags |= reachable_flag; |
876 | worklist.quick_push (obj: loop->header); |
877 | reachable.safe_push (obj: loop->header); |
878 | |
879 | while (!worklist.is_empty ()) |
880 | { |
881 | edge e; |
882 | edge_iterator ei; |
883 | int flags = ignored_edge_flag; |
884 | basic_block bb = worklist.pop (); |
885 | |
886 | if (visit (bb)) |
887 | break; |
888 | |
889 | gimple *last = *gsi_last_bb (bb); |
890 | if (gcond *cond = safe_dyn_cast <gcond *> (p: last)) |
891 | { |
892 | if (gimple_cond_true_p (gs: cond)) |
893 | flags = EDGE_FALSE_VALUE; |
894 | else if (gimple_cond_false_p (gs: cond)) |
895 | flags = EDGE_TRUE_VALUE; |
896 | else if (predicate_path) |
897 | { |
898 | tree res; |
899 | if (!get_predicates_for_bb (bb).is_empty () |
900 | && (res = evaluate_control_stmt_using_entry_checks |
901 | (stmt: cond, predicate_path&: *predicate_path, ignored_edge_flag, |
902 | ignored_edges: &ignored_edges))) |
903 | flags = (integer_nonzerop (res) |
904 | ? EDGE_FALSE_VALUE : EDGE_TRUE_VALUE); |
905 | } |
906 | } |
907 | else if (gswitch *swtch = safe_dyn_cast<gswitch *> (p: last)) |
908 | if (predicate_path |
909 | && !get_predicates_for_bb (bb).is_empty ()) |
910 | evaluate_control_stmt_using_entry_checks (stmt: swtch, predicate_path&: *predicate_path, |
911 | ignored_edge_flag, |
912 | ignored_edges: &ignored_edges); |
913 | |
914 | /* Note that for the moment we do not account reachable conditions |
915 | which are simplified to take a known edge as zero size nor |
916 | are we accounting for the required addition of the versioning |
917 | condition. Those should cancel out conservatively. */ |
918 | |
919 | FOR_EACH_EDGE (e, ei, bb->succs) |
920 | { |
921 | basic_block dest = e->dest; |
922 | |
923 | if (flow_bb_inside_loop_p (loop, dest) |
924 | && !(dest->flags & reachable_flag) |
925 | && !(e->flags & flags) |
926 | && !ignored_edges.contains (k: e)) |
927 | { |
928 | dest->flags |= reachable_flag; |
929 | worklist.safe_push (obj: dest); |
930 | reachable.safe_push (obj: dest); |
931 | } |
932 | } |
933 | } |
934 | |
935 | /* Clear the flag from basic blocks. */ |
936 | while (!reachable.is_empty ()) |
937 | reachable.pop ()->flags &= ~reachable_flag; |
938 | } |
939 | |
940 | /* Evaluate how many instruction will we have if we unswitch LOOP (with BBS) |
941 | based on PREDICATE predicate (using PREDICATE_PATH). Store the |
942 | result in TRUE_SIZE and FALSE_SIZE. */ |
943 | |
944 | static void |
945 | evaluate_loop_insns_for_predicate (class loop *loop, |
946 | predicate_vector &predicate_path, |
947 | unswitch_predicate *predicate, |
948 | int ignored_edge_flag, |
949 | unsigned *true_size, unsigned *false_size) |
950 | { |
951 | unsigned size = 0; |
952 | auto sum_size = [&](basic_block bb) -> bool |
953 | { size += (uintptr_t)bb->aux; return false; }; |
954 | |
955 | add_predicate_to_path (predicate_path, predicate, true_edge: true); |
956 | evaluate_bbs (loop, predicate_path: &predicate_path, ignored_edge_flag, visit: sum_size); |
957 | predicate_path.pop (); |
958 | unsigned true_loop_cost = size; |
959 | |
960 | size = 0; |
961 | add_predicate_to_path (predicate_path, predicate, true_edge: false); |
962 | evaluate_bbs (loop, predicate_path: &predicate_path, ignored_edge_flag, visit: sum_size); |
963 | predicate_path.pop (); |
964 | unsigned false_loop_cost = size; |
965 | |
966 | *true_size = true_loop_cost; |
967 | *false_size = false_loop_cost; |
968 | } |
969 | |
970 | /* Unswitch single LOOP. PREDICATE_PATH contains so far used predicates |
971 | for unswitching. BUDGET is number of instruction for which we can increase |
972 | the loop and is updated when unswitching occurs. If HOTTEST is not |
973 | NULL then pick this candidate as the one to unswitch on. */ |
974 | |
975 | static bool |
976 | tree_unswitch_single_loop (class loop *loop, dump_user_location_t loc, |
977 | predicate_vector &predicate_path, |
978 | unsigned loop_size, unsigned &budget, |
979 | int ignored_edge_flag, bitmap handled, |
980 | unswitch_predicate *hottest, basic_block hottest_bb) |
981 | { |
982 | class loop *nloop; |
983 | bool changed = false; |
984 | unswitch_predicate *predicate = NULL; |
985 | basic_block predicate_bb = NULL; |
986 | unsigned true_size = 0, false_size = 0; |
987 | |
988 | auto check_predicates = [&](basic_block bb) -> bool |
989 | { |
990 | for (auto pred : get_predicates_for_bb (bb)) |
991 | { |
992 | if (bitmap_bit_p (handled, pred->num)) |
993 | continue; |
994 | |
995 | evaluate_loop_insns_for_predicate (loop, predicate_path, |
996 | predicate: pred, ignored_edge_flag, |
997 | true_size: &true_size, false_size: &false_size); |
998 | |
999 | /* We'll get LOOP replaced with a simplified version according |
1000 | to PRED estimated to TRUE_SIZE and a copy simplified |
1001 | according to the inverted PRED estimated to FALSE_SIZE. */ |
1002 | if (true_size + false_size < budget + loop_size) |
1003 | { |
1004 | predicate = pred; |
1005 | predicate_bb = bb; |
1006 | |
1007 | /* There are cases where true_size and false_size add up to |
1008 | less than the original loop_size. We do not want to |
1009 | grow the remaining budget because of that. */ |
1010 | if (true_size + false_size > loop_size) |
1011 | budget -= (true_size + false_size - loop_size); |
1012 | |
1013 | /* FIXME: right now we select first candidate, but we can |
1014 | choose the cheapest or hottest one. */ |
1015 | return true; |
1016 | } |
1017 | else if (dump_enabled_p ()) |
1018 | dump_printf_loc (MSG_NOTE, loc, |
1019 | "not unswitching condition, cost too big " |
1020 | "(%u insns copied to %u and %u)\n" , loop_size, |
1021 | true_size, false_size); |
1022 | } |
1023 | return false; |
1024 | }; |
1025 | |
1026 | if (hottest) |
1027 | { |
1028 | predicate = hottest; |
1029 | predicate_bb = hottest_bb; |
1030 | } |
1031 | else |
1032 | /* Check predicates of reachable blocks. */ |
1033 | evaluate_bbs (loop, NULL, ignored_edge_flag, visit: check_predicates); |
1034 | |
1035 | if (predicate != NULL) |
1036 | { |
1037 | if (!dbg_cnt (index: loop_unswitch)) |
1038 | goto exit; |
1039 | |
1040 | if (dump_enabled_p ()) |
1041 | { |
1042 | dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc, |
1043 | "unswitching %sloop %d on %qs with condition: %T\n" , |
1044 | loop->inner ? "outer " : "" , |
1045 | loop->num, predicate->switch_p ? "switch" : "if" , |
1046 | predicate->condition); |
1047 | dump_printf_loc (MSG_NOTE, loc, |
1048 | "optimized sizes estimated to %u (true) " |
1049 | "and %u (false) from original size %u\n" , |
1050 | true_size, false_size, loop_size); |
1051 | } |
1052 | |
1053 | bitmap_set_bit (handled, predicate->num); |
1054 | initialize_original_copy_tables (); |
1055 | /* Unswitch the loop on this condition. */ |
1056 | nloop = tree_unswitch_loop (loop, EDGE_SUCC (predicate_bb, |
1057 | predicate->edge_index), |
1058 | predicate->condition); |
1059 | if (!nloop) |
1060 | { |
1061 | free_original_copy_tables (); |
1062 | goto exit; |
1063 | } |
1064 | |
1065 | /* Copy BB costs. */ |
1066 | basic_block *bbs2 = get_loop_body (nloop); |
1067 | for (unsigned i = 0; i < nloop->num_nodes; i++) |
1068 | bbs2[i]->aux = get_bb_original (bbs2[i])->aux; |
1069 | free (ptr: bbs2); |
1070 | |
1071 | free_original_copy_tables (); |
1072 | |
1073 | /* Update the SSA form after unswitching. */ |
1074 | update_ssa (TODO_update_ssa_no_phi); |
1075 | |
1076 | /* Invoke itself on modified loops. */ |
1077 | bitmap handled_copy = BITMAP_ALLOC (NULL); |
1078 | bitmap_copy (handled_copy, handled); |
1079 | add_predicate_to_path (predicate_path, predicate, true_edge: false); |
1080 | changed |= simplify_loop_version (loop: nloop, predicate_path, |
1081 | ignored_edge_flag, handled: handled_copy); |
1082 | tree_unswitch_single_loop (loop: nloop, loc, predicate_path, |
1083 | loop_size: false_size, budget, |
1084 | ignored_edge_flag, handled: handled_copy); |
1085 | predicate_path.pop (); |
1086 | BITMAP_FREE (handled_copy); |
1087 | |
1088 | /* FIXME: After unwinding above we have to reset all ->handled |
1089 | flags as otherwise we fail to realize unswitching opportunities |
1090 | in the below recursion. See gcc.dg/loop-unswitch-16.c */ |
1091 | add_predicate_to_path (predicate_path, predicate, true_edge: true); |
1092 | changed |= simplify_loop_version (loop, predicate_path, |
1093 | ignored_edge_flag, handled); |
1094 | tree_unswitch_single_loop (loop, loc, predicate_path, |
1095 | loop_size: true_size, budget, |
1096 | ignored_edge_flag, handled); |
1097 | predicate_path.pop (); |
1098 | changed = true; |
1099 | } |
1100 | |
1101 | exit: |
1102 | return changed; |
1103 | } |
1104 | |
1105 | /* Unswitch a LOOP w.r. to given EDGE_TRUE. We only support unswitching of |
1106 | innermost loops. COND is the condition determining which loop is entered; |
1107 | the new loop is entered if COND is true. Returns NULL if impossible, new |
1108 | loop otherwise. */ |
1109 | |
1110 | static class loop * |
1111 | tree_unswitch_loop (class loop *loop, edge edge_true, tree cond) |
1112 | { |
1113 | /* Some sanity checking. */ |
1114 | gcc_assert (flow_bb_inside_loop_p (loop, edge_true->src)); |
1115 | gcc_assert (EDGE_COUNT (edge_true->src->succs) >= 2); |
1116 | |
1117 | profile_probability prob_true = edge_true->probability; |
1118 | return loop_version (loop, unshare_expr (cond), |
1119 | NULL, prob_true, |
1120 | prob_true.invert (), |
1121 | prob_true, prob_true.invert (), |
1122 | false); |
1123 | } |
1124 | |
1125 | /* Unswitch outer loops by hoisting invariant guard on |
1126 | inner loop without code duplication. */ |
1127 | static bool |
1128 | tree_unswitch_outer_loop (class loop *loop) |
1129 | { |
1130 | edge exit, guard; |
1131 | HOST_WIDE_INT iterations; |
1132 | |
1133 | gcc_assert (loop->inner); |
1134 | if (loop->inner->next) |
1135 | return false; |
1136 | /* Accept loops with single exit only which is not from inner loop. */ |
1137 | exit = single_exit (loop); |
1138 | if (!exit || exit->src->loop_father != loop) |
1139 | return false; |
1140 | /* Check that phi argument of exit edge is not defined inside loop. */ |
1141 | if (!check_exit_phi (loop)) |
1142 | return false; |
1143 | /* If the loop is not expected to iterate, there is no need |
1144 | for unswitching. */ |
1145 | iterations = estimated_loop_iterations_int (loop); |
1146 | if (iterations < 0) |
1147 | iterations = likely_max_loop_iterations_int (loop); |
1148 | if (iterations >= 0 && iterations <= 1) |
1149 | { |
1150 | if (dump_enabled_p ()) |
1151 | dump_printf_loc (MSG_MISSED_OPTIMIZATION, find_loop_location (loop), |
1152 | "Not unswitching, loop is not expected" |
1153 | " to iterate\n" ); |
1154 | return false; |
1155 | } |
1156 | |
1157 | bool changed = false; |
1158 | auto_vec<gimple *> dbg_to_reset; |
1159 | while ((guard = find_loop_guard (loop, dbg_to_reset))) |
1160 | { |
1161 | hoist_guard (loop, guard); |
1162 | for (gimple *debug_stmt : dbg_to_reset) |
1163 | { |
1164 | gimple_debug_bind_reset_value (dbg: debug_stmt); |
1165 | update_stmt (s: debug_stmt); |
1166 | } |
1167 | dbg_to_reset.truncate (size: 0); |
1168 | changed = true; |
1169 | } |
1170 | return changed; |
1171 | } |
1172 | |
1173 | /* Checks if the body of the LOOP is within an invariant guard. If this |
1174 | is the case, returns the edge that jumps over the real body of the loop, |
1175 | otherwise returns NULL. */ |
1176 | |
1177 | static edge |
1178 | find_loop_guard (class loop *loop, vec<gimple *> &dbg_to_reset) |
1179 | { |
1180 | basic_block = loop->header; |
1181 | edge guard_edge, te, fe; |
1182 | basic_block *body = NULL; |
1183 | unsigned i; |
1184 | tree use; |
1185 | ssa_op_iter iter; |
1186 | |
1187 | /* We check for the following situation: |
1188 | |
1189 | while (1) |
1190 | { |
1191 | [header]] |
1192 | loop_phi_nodes; |
1193 | something1; |
1194 | if (cond1) |
1195 | body; |
1196 | nvar = phi(orig, bvar) ... for all variables changed in body; |
1197 | [guard_end] |
1198 | something2; |
1199 | if (cond2) |
1200 | break; |
1201 | something3; |
1202 | } |
1203 | |
1204 | where: |
1205 | |
1206 | 1) cond1 is loop invariant |
1207 | 2) If cond1 is false, then the loop is essentially empty; i.e., |
1208 | a) nothing in something1, something2 and something3 has side |
1209 | effects |
1210 | b) anything defined in something1, something2 and something3 |
1211 | is not used outside of the loop. */ |
1212 | |
1213 | gcond *cond; |
1214 | do |
1215 | { |
1216 | basic_block next = NULL; |
1217 | if (single_succ_p (bb: header)) |
1218 | next = single_succ (bb: header); |
1219 | else |
1220 | { |
1221 | cond = safe_dyn_cast <gcond *> (p: *gsi_last_bb (bb: header)); |
1222 | if (! cond) |
1223 | return NULL; |
1224 | extract_true_false_edges_from_block (header, &te, &fe); |
1225 | /* Make sure to skip earlier hoisted guards that are left |
1226 | in place as if (true). */ |
1227 | if (gimple_cond_true_p (gs: cond)) |
1228 | next = te->dest; |
1229 | else if (gimple_cond_false_p (gs: cond)) |
1230 | next = fe->dest; |
1231 | else |
1232 | break; |
1233 | } |
1234 | /* Never traverse a backedge. */ |
1235 | if (header->loop_father->header == next) |
1236 | return NULL; |
1237 | header = next; |
1238 | } |
1239 | while (1); |
1240 | if (!flow_bb_inside_loop_p (loop, te->dest) |
1241 | || !flow_bb_inside_loop_p (loop, fe->dest)) |
1242 | return NULL; |
1243 | |
1244 | if (just_once_each_iteration_p (loop, te->dest) |
1245 | || (single_succ_p (bb: te->dest) |
1246 | && just_once_each_iteration_p (loop, single_succ (bb: te->dest)))) |
1247 | { |
1248 | if (just_once_each_iteration_p (loop, fe->dest)) |
1249 | return NULL; |
1250 | guard_edge = te; |
1251 | } |
1252 | else if (just_once_each_iteration_p (loop, fe->dest) |
1253 | || (single_succ_p (bb: fe->dest) |
1254 | && just_once_each_iteration_p (loop, single_succ (bb: fe->dest)))) |
1255 | guard_edge = fe; |
1256 | else |
1257 | return NULL; |
1258 | |
1259 | dump_user_location_t loc = find_loop_location (loop); |
1260 | |
1261 | /* Guard edge must skip inner loop. */ |
1262 | if (!dominated_by_p (CDI_DOMINATORS, loop->inner->header, |
1263 | guard_edge == fe ? te->dest : fe->dest)) |
1264 | { |
1265 | if (dump_enabled_p ()) |
1266 | dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc, |
1267 | "Guard edge %d --> %d is not around the loop!\n" , |
1268 | guard_edge->src->index, guard_edge->dest->index); |
1269 | return NULL; |
1270 | } |
1271 | if (guard_edge->dest == loop->latch) |
1272 | { |
1273 | if (dump_enabled_p ()) |
1274 | dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc, |
1275 | "Guard edge destination is loop latch.\n" ); |
1276 | return NULL; |
1277 | } |
1278 | |
1279 | if (dump_enabled_p ()) |
1280 | dump_printf_loc (MSG_NOTE, loc, |
1281 | "Considering guard %d -> %d in loop %d\n" , |
1282 | guard_edge->src->index, guard_edge->dest->index, |
1283 | loop->num); |
1284 | /* Check if condition operands do not have definitions inside loop since |
1285 | any bb copying is not performed. */ |
1286 | FOR_EACH_SSA_TREE_OPERAND (use, cond, iter, SSA_OP_USE) |
1287 | { |
1288 | gimple *def = SSA_NAME_DEF_STMT (use); |
1289 | basic_block def_bb = gimple_bb (g: def); |
1290 | if (def_bb |
1291 | && flow_bb_inside_loop_p (loop, def_bb)) |
1292 | { |
1293 | if (dump_enabled_p ()) |
1294 | dump_printf_loc (MSG_NOTE, loc, "guard operands have definitions" |
1295 | " inside loop\n" ); |
1296 | return NULL; |
1297 | } |
1298 | } |
1299 | |
1300 | body = get_loop_body (loop); |
1301 | for (i = 0; i < loop->num_nodes; i++) |
1302 | { |
1303 | basic_block bb = body[i]; |
1304 | if (bb->loop_father != loop) |
1305 | continue; |
1306 | if (bb->flags & BB_IRREDUCIBLE_LOOP) |
1307 | { |
1308 | if (dump_enabled_p ()) |
1309 | dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc, |
1310 | "Block %d is marked as irreducible in loop\n" , |
1311 | bb->index); |
1312 | guard_edge = NULL; |
1313 | goto end; |
1314 | } |
1315 | if (!empty_bb_without_guard_p (loop, bb, dbg_to_reset)) |
1316 | { |
1317 | if (dump_enabled_p ()) |
1318 | dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc, |
1319 | "Block %d has side effects\n" , bb->index); |
1320 | guard_edge = NULL; |
1321 | goto end; |
1322 | } |
1323 | } |
1324 | |
1325 | if (dump_enabled_p ()) |
1326 | dump_printf_loc (MSG_NOTE, loc, |
1327 | "suitable to hoist\n" ); |
1328 | end: |
1329 | if (body) |
1330 | free (ptr: body); |
1331 | return guard_edge; |
1332 | } |
1333 | |
1334 | /* Returns true if |
1335 | 1) no statement in BB has side effects |
1336 | 2) assuming that edge GUARD is always taken, all definitions in BB |
1337 | are noy used outside of the loop. |
1338 | KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and |
1339 | PROCESSED is a set of ssa names for that we already tested whether they |
1340 | are invariant or not. Uses in debug stmts outside of the loop are |
1341 | pushed to DBG_TO_RESET. */ |
1342 | |
1343 | static bool |
1344 | empty_bb_without_guard_p (class loop *loop, basic_block bb, |
1345 | vec<gimple *> &dbg_to_reset) |
1346 | { |
1347 | basic_block exit_bb = single_exit (loop)->src; |
1348 | bool may_be_used_outside = (bb == exit_bb |
1349 | || !dominated_by_p (CDI_DOMINATORS, bb, exit_bb)); |
1350 | tree name; |
1351 | ssa_op_iter op_iter; |
1352 | |
1353 | /* Phi nodes do not have side effects, but their results might be used |
1354 | outside of the loop. */ |
1355 | if (may_be_used_outside) |
1356 | { |
1357 | for (gphi_iterator gsi = gsi_start_phis (bb); |
1358 | !gsi_end_p (i: gsi); gsi_next (i: &gsi)) |
1359 | { |
1360 | gphi *phi = gsi.phi (); |
1361 | name = PHI_RESULT (phi); |
1362 | if (virtual_operand_p (op: name)) |
1363 | continue; |
1364 | |
1365 | if (used_outside_loop_p (loop, name, dbg_to_reset)) |
1366 | return false; |
1367 | } |
1368 | } |
1369 | |
1370 | for (gimple_stmt_iterator gsi = gsi_start_bb (bb); |
1371 | !gsi_end_p (i: gsi); gsi_next (i: &gsi)) |
1372 | { |
1373 | gimple *stmt = gsi_stmt (i: gsi); |
1374 | if (is_gimple_debug (gs: stmt)) |
1375 | continue; |
1376 | |
1377 | if (gimple_has_side_effects (stmt)) |
1378 | return false; |
1379 | |
1380 | if (gimple_vdef(g: stmt)) |
1381 | return false; |
1382 | |
1383 | FOR_EACH_SSA_TREE_OPERAND (name, stmt, op_iter, SSA_OP_DEF) |
1384 | { |
1385 | if (may_be_used_outside |
1386 | && used_outside_loop_p (loop, name, dbg_to_reset)) |
1387 | return false; |
1388 | } |
1389 | } |
1390 | return true; |
1391 | } |
1392 | |
1393 | /* Return true if NAME is used outside of LOOP. Pushes debug stmts that |
1394 | have such uses to DBG_TO_RESET but do not consider such uses. */ |
1395 | |
1396 | static bool |
1397 | used_outside_loop_p (class loop *loop, tree name, vec<gimple *> &dbg_to_reset) |
1398 | { |
1399 | imm_use_iterator it; |
1400 | use_operand_p use; |
1401 | |
1402 | FOR_EACH_IMM_USE_FAST (use, it, name) |
1403 | { |
1404 | gimple *stmt = USE_STMT (use); |
1405 | if (!flow_bb_inside_loop_p (loop, gimple_bb (g: stmt))) |
1406 | { |
1407 | if (!is_gimple_debug (gs: stmt)) |
1408 | return true; |
1409 | dbg_to_reset.safe_push (obj: stmt); |
1410 | } |
1411 | } |
1412 | |
1413 | return false; |
1414 | } |
1415 | |
1416 | /* Return argument for loop preheader edge in header virtual phi if any. */ |
1417 | |
1418 | static tree |
1419 | (class loop *loop) |
1420 | { |
1421 | for (gphi_iterator gsi = gsi_start_phis (loop->header); |
1422 | !gsi_end_p (i: gsi); gsi_next (i: &gsi)) |
1423 | { |
1424 | gphi *phi = gsi.phi (); |
1425 | if (!virtual_operand_p (op: gimple_phi_result (gs: phi))) |
1426 | continue; |
1427 | return PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); |
1428 | } |
1429 | return NULL_TREE; |
1430 | } |
1431 | |
1432 | /* Move the check of GUARD outside of LOOP. */ |
1433 | |
1434 | static void |
1435 | hoist_guard (class loop *loop, edge guard) |
1436 | { |
1437 | edge exit = single_exit (loop); |
1438 | edge preh = loop_preheader_edge (loop); |
1439 | basic_block = preh->src; |
1440 | basic_block bb; |
1441 | edge te, fe, e, new_edge; |
1442 | gimple *stmt; |
1443 | basic_block guard_bb = guard->src; |
1444 | edge not_guard; |
1445 | gimple_stmt_iterator gsi; |
1446 | int flags = 0; |
1447 | bool fix_dom_of_exit; |
1448 | gcond *cond_stmt, *new_cond_stmt; |
1449 | |
1450 | bb = get_immediate_dominator (CDI_DOMINATORS, exit->dest); |
1451 | fix_dom_of_exit = flow_bb_inside_loop_p (loop, bb); |
1452 | gsi = gsi_last_bb (bb: guard_bb); |
1453 | stmt = gsi_stmt (i: gsi); |
1454 | gcc_assert (gimple_code (stmt) == GIMPLE_COND); |
1455 | cond_stmt = as_a <gcond *> (p: stmt); |
1456 | extract_true_false_edges_from_block (guard_bb, &te, &fe); |
1457 | /* Insert guard to PRE_HEADER. */ |
1458 | gsi = gsi_last_bb (bb: pre_header); |
1459 | /* Create copy of COND_STMT. */ |
1460 | new_cond_stmt = gimple_build_cond (gimple_cond_code (gs: cond_stmt), |
1461 | gimple_cond_lhs (gs: cond_stmt), |
1462 | gimple_cond_rhs (gs: cond_stmt), |
1463 | NULL_TREE, NULL_TREE); |
1464 | gsi_insert_after (&gsi, new_cond_stmt, GSI_NEW_STMT); |
1465 | /* Convert COND_STMT to true/false conditional. */ |
1466 | if (guard == te) |
1467 | gimple_cond_make_false (gs: cond_stmt); |
1468 | else |
1469 | gimple_cond_make_true (gs: cond_stmt); |
1470 | update_stmt (s: cond_stmt); |
1471 | /* Create new loop pre-header. */ |
1472 | e = split_block (pre_header, last_nondebug_stmt (pre_header)); |
1473 | |
1474 | dump_user_location_t loc = find_loop_location (loop); |
1475 | |
1476 | if (dump_enabled_p ()) |
1477 | { |
1478 | char buffer[64]; |
1479 | guard->probability.dump (buffer); |
1480 | |
1481 | dump_printf_loc (MSG_NOTE, loc, |
1482 | "Moving guard %i->%i (prob %s) to bb %i, " |
1483 | "new preheader is %i\n" , |
1484 | guard->src->index, guard->dest->index, |
1485 | buffer, e->src->index, e->dest->index); |
1486 | } |
1487 | |
1488 | gcc_assert (loop_preheader_edge (loop)->src == e->dest); |
1489 | |
1490 | if (guard == fe) |
1491 | { |
1492 | e->flags = EDGE_TRUE_VALUE; |
1493 | flags |= EDGE_FALSE_VALUE; |
1494 | not_guard = te; |
1495 | } |
1496 | else |
1497 | { |
1498 | e->flags = EDGE_FALSE_VALUE; |
1499 | flags |= EDGE_TRUE_VALUE; |
1500 | not_guard = fe; |
1501 | } |
1502 | new_edge = make_edge (pre_header, exit->dest, flags); |
1503 | |
1504 | /* Determine the probability that we skip the loop. Assume that loop has |
1505 | same average number of iterations regardless outcome of guard. */ |
1506 | new_edge->probability = guard->probability; |
1507 | profile_count skip_count = guard->src->count.nonzero_p () |
1508 | ? guard->count ().apply_scale (num: pre_header->count, |
1509 | den: guard->src->count) |
1510 | : guard->count ().apply_probability (prob: new_edge->probability); |
1511 | |
1512 | if (skip_count > e->count ()) |
1513 | { |
1514 | fprintf (stream: dump_file, format: " Capping count; expect profile inconsistency\n" ); |
1515 | skip_count = e->count (); |
1516 | } |
1517 | if (dump_enabled_p ()) |
1518 | { |
1519 | char buffer[64]; |
1520 | new_edge->probability.dump (buffer); |
1521 | |
1522 | dump_printf_loc (MSG_NOTE, loc, |
1523 | "Estimated probability of skipping loop is %s\n" , |
1524 | buffer); |
1525 | } |
1526 | |
1527 | /* Update profile after the transform: |
1528 | |
1529 | First decrease count of path from newly hoisted loop guard |
1530 | to loop header... */ |
1531 | e->probability = new_edge->probability.invert (); |
1532 | e->dest->count = e->count (); |
1533 | |
1534 | /* ... now update profile to represent that original guard will be optimized |
1535 | away ... */ |
1536 | guard->probability = profile_probability::never (); |
1537 | not_guard->probability = profile_probability::always (); |
1538 | |
1539 | /* ... finally scale everything in the loop except for guarded basic blocks |
1540 | where profile does not change. */ |
1541 | basic_block *body = get_loop_body (loop); |
1542 | |
1543 | for (unsigned int i = 0; i < loop->num_nodes; i++) |
1544 | { |
1545 | basic_block bb = body[i]; |
1546 | if (!dominated_by_p (CDI_DOMINATORS, bb, not_guard->dest)) |
1547 | { |
1548 | if (dump_enabled_p ()) |
1549 | dump_printf_loc (MSG_NOTE, loc, |
1550 | "Scaling nonguarded BBs in loop: %i\n" , |
1551 | bb->index); |
1552 | if (e->probability.initialized_p ()) |
1553 | scale_bbs_frequencies (&bb, 1, e->probability); |
1554 | } |
1555 | } |
1556 | |
1557 | if (fix_dom_of_exit) |
1558 | set_immediate_dominator (CDI_DOMINATORS, exit->dest, pre_header); |
1559 | /* Add NEW_ADGE argument for all phi in post-header block. */ |
1560 | bb = exit->dest; |
1561 | for (gphi_iterator gsi = gsi_start_phis (bb); |
1562 | !gsi_end_p (i: gsi); gsi_next (i: &gsi)) |
1563 | { |
1564 | gphi *phi = gsi.phi (); |
1565 | tree arg; |
1566 | if (virtual_operand_p (op: gimple_phi_result (gs: phi))) |
1567 | { |
1568 | arg = get_vop_from_header (loop); |
1569 | if (arg == NULL_TREE) |
1570 | /* Use exit edge argument. */ |
1571 | arg = PHI_ARG_DEF_FROM_EDGE (phi, exit); |
1572 | add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION); |
1573 | } |
1574 | else |
1575 | { |
1576 | /* Use exit edge argument. */ |
1577 | arg = PHI_ARG_DEF_FROM_EDGE (phi, exit); |
1578 | add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION); |
1579 | } |
1580 | } |
1581 | |
1582 | if (dump_enabled_p ()) |
1583 | dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc, |
1584 | "Guard hoisted\n" ); |
1585 | |
1586 | free (ptr: body); |
1587 | } |
1588 | |
1589 | /* Return true if phi argument for exit edge can be used |
1590 | for edge around loop. */ |
1591 | |
1592 | static bool |
1593 | check_exit_phi (class loop *loop) |
1594 | { |
1595 | edge exit = single_exit (loop); |
1596 | basic_block = loop_preheader_edge (loop)->src; |
1597 | |
1598 | for (gphi_iterator gsi = gsi_start_phis (exit->dest); |
1599 | !gsi_end_p (i: gsi); gsi_next (i: &gsi)) |
1600 | { |
1601 | gphi *phi = gsi.phi (); |
1602 | tree arg; |
1603 | gimple *def; |
1604 | basic_block def_bb; |
1605 | if (virtual_operand_p (op: gimple_phi_result (gs: phi))) |
1606 | continue; |
1607 | arg = PHI_ARG_DEF_FROM_EDGE (phi, exit); |
1608 | if (TREE_CODE (arg) != SSA_NAME) |
1609 | continue; |
1610 | def = SSA_NAME_DEF_STMT (arg); |
1611 | if (!def) |
1612 | continue; |
1613 | def_bb = gimple_bb (g: def); |
1614 | if (!def_bb) |
1615 | continue; |
1616 | if (!dominated_by_p (CDI_DOMINATORS, pre_header, def_bb)) |
1617 | /* Definition inside loop! */ |
1618 | return false; |
1619 | /* Check loop closed phi invariant. */ |
1620 | if (!flow_bb_inside_loop_p (def_bb->loop_father, pre_header)) |
1621 | return false; |
1622 | } |
1623 | return true; |
1624 | } |
1625 | |
1626 | /* Remove all dead cases from switches that are unswitched. */ |
1627 | |
1628 | static void |
1629 | clean_up_after_unswitching (int ignored_edge_flag) |
1630 | { |
1631 | basic_block bb; |
1632 | edge e; |
1633 | edge_iterator ei; |
1634 | bool removed_edge = false; |
1635 | |
1636 | FOR_EACH_BB_FN (bb, cfun) |
1637 | { |
1638 | gswitch *stmt= safe_dyn_cast <gswitch *> (p: *gsi_last_bb (bb)); |
1639 | if (stmt && !CONSTANT_CLASS_P (gimple_switch_index (stmt))) |
1640 | { |
1641 | unsigned nlabels = gimple_switch_num_labels (gs: stmt); |
1642 | unsigned index = 1; |
1643 | tree lab = gimple_switch_default_label (gs: stmt); |
1644 | edge default_e = find_edge (gimple_bb (g: stmt), |
1645 | label_to_block (cfun, CASE_LABEL (lab))); |
1646 | for (unsigned i = 1; i < nlabels; ++i) |
1647 | { |
1648 | tree lab = gimple_switch_label (gs: stmt, index: i); |
1649 | basic_block dest = label_to_block (cfun, CASE_LABEL (lab)); |
1650 | edge e = find_edge (gimple_bb (g: stmt), dest); |
1651 | if (e == NULL) |
1652 | ; /* The edge is already removed. */ |
1653 | else if (e->flags & ignored_edge_flag) |
1654 | { |
1655 | /* We may not remove the default label so we also have |
1656 | to preserve its edge. But we can remove the |
1657 | non-default CASE sharing the edge. */ |
1658 | if (e != default_e) |
1659 | { |
1660 | remove_edge (e); |
1661 | removed_edge = true; |
1662 | } |
1663 | } |
1664 | else |
1665 | { |
1666 | gimple_switch_set_label (gs: stmt, index, label: lab); |
1667 | ++index; |
1668 | } |
1669 | } |
1670 | |
1671 | if (index != nlabels) |
1672 | gimple_switch_set_num_labels (g: stmt, nlabels: index); |
1673 | } |
1674 | |
1675 | /* Clean up the ignored_edge_flag from edges. */ |
1676 | FOR_EACH_EDGE (e, ei, bb->succs) |
1677 | e->flags &= ~ignored_edge_flag; |
1678 | } |
1679 | |
1680 | /* If we removed an edge we possibly have to recompute dominators. */ |
1681 | if (removed_edge) |
1682 | free_dominance_info (CDI_DOMINATORS); |
1683 | } |
1684 | |
1685 | /* Loop unswitching pass. */ |
1686 | |
1687 | namespace { |
1688 | |
1689 | const pass_data pass_data_tree_unswitch = |
1690 | { |
1691 | .type: GIMPLE_PASS, /* type */ |
1692 | .name: "unswitch" , /* name */ |
1693 | .optinfo_flags: OPTGROUP_LOOP, /* optinfo_flags */ |
1694 | .tv_id: TV_TREE_LOOP_UNSWITCH, /* tv_id */ |
1695 | PROP_cfg, /* properties_required */ |
1696 | .properties_provided: 0, /* properties_provided */ |
1697 | .properties_destroyed: 0, /* properties_destroyed */ |
1698 | .todo_flags_start: 0, /* todo_flags_start */ |
1699 | .todo_flags_finish: 0, /* todo_flags_finish */ |
1700 | }; |
1701 | |
1702 | class pass_tree_unswitch : public gimple_opt_pass |
1703 | { |
1704 | public: |
1705 | pass_tree_unswitch (gcc::context *ctxt) |
1706 | : gimple_opt_pass (pass_data_tree_unswitch, ctxt) |
1707 | {} |
1708 | |
1709 | /* opt_pass methods: */ |
1710 | bool gate (function *) final override { return flag_unswitch_loops != 0; } |
1711 | unsigned int execute (function *) final override; |
1712 | |
1713 | }; // class pass_tree_unswitch |
1714 | |
1715 | unsigned int |
1716 | pass_tree_unswitch::execute (function *fun) |
1717 | { |
1718 | if (number_of_loops (fn: fun) <= 1) |
1719 | return 0; |
1720 | |
1721 | return tree_ssa_unswitch_loops (fun); |
1722 | } |
1723 | |
1724 | } // anon namespace |
1725 | |
1726 | gimple_opt_pass * |
1727 | make_pass_tree_unswitch (gcc::context *ctxt) |
1728 | { |
1729 | return new pass_tree_unswitch (ctxt); |
1730 | } |
1731 | |
1732 | |
1733 | |