1 /* Loop unswitching.
2 Copyright (C) 2004-2022 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
42 /* This file implements the loop unswitching, i.e. transformation of loops like
43
44 while (A)
45 {
46 if (inv)
47 B;
48
49 X;
50
51 if (!inv)
52 C;
53 }
54
55 where inv is the loop invariant, into
56
57 if (inv)
58 {
59 while (A)
60 {
61 B;
62 X;
63 }
64 }
65 else
66 {
67 while (A)
68 {
69 X;
70 C;
71 }
72 }
73
74 Inv is considered invariant iff the values it compares are both invariant;
75 tree-ssa-loop-im.cc ensures that all the suitable conditions are in this
76 shape. */
77
78 static class loop *tree_unswitch_loop (class loop *, basic_block, tree);
79 static bool tree_unswitch_single_loop (class loop *, int);
80 static tree tree_may_unswitch_on (basic_block, class loop *);
81 static bool tree_unswitch_outer_loop (class loop *);
82 static edge find_loop_guard (class loop *, vec<gimple *>&);
83 static bool empty_bb_without_guard_p (class loop *, basic_block,
84 vec<gimple *>&);
85 static bool used_outside_loop_p (class loop *, tree, vec<gimple *>&);
86 static void hoist_guard (class loop *, edge);
87 static bool check_exit_phi (class loop *);
88 static tree get_vop_from_header (class loop *);
89
90 /* Main entry point. Perform loop unswitching on all suitable loops. */
91
92 unsigned int
tree_ssa_unswitch_loops(void)93 tree_ssa_unswitch_loops (void)
94 {
95 bool changed = false;
96
97 /* Go through all loops starting from innermost. */
98 for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
99 {
100 if (!loop->inner)
101 /* Unswitch innermost loop. */
102 changed |= tree_unswitch_single_loop (loop, 0);
103 else
104 changed |= tree_unswitch_outer_loop (loop);
105 }
106
107 if (changed)
108 return TODO_cleanup_cfg;
109 return 0;
110 }
111
112 /* Return TRUE if an SSA_NAME maybe undefined and is therefore
113 unsuitable for unswitching. STMT is the statement we are
114 considering for unswitching and LOOP is the loop it appears in. */
115
116 static bool
is_maybe_undefined(const tree name,gimple * stmt,class loop * loop)117 is_maybe_undefined (const tree name, gimple *stmt, class loop *loop)
118 {
119 /* The loop header is the only block we can trivially determine that
120 will always be executed. If the comparison is in the loop
121 header, we know it's OK to unswitch on it. */
122 if (gimple_bb (stmt) == loop->header)
123 return false;
124
125 auto_bitmap visited_ssa;
126 auto_vec<tree> worklist;
127 worklist.safe_push (name);
128 bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (name));
129 while (!worklist.is_empty ())
130 {
131 tree t = worklist.pop ();
132
133 /* If it's obviously undefined, avoid further computations. */
134 if (ssa_undefined_value_p (t, true))
135 return true;
136
137 if (ssa_defined_default_def_p (t))
138 continue;
139
140 gimple *def = SSA_NAME_DEF_STMT (t);
141
142 /* Check that all the PHI args are fully defined. */
143 if (gphi *phi = dyn_cast <gphi *> (def))
144 {
145 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
146 {
147 tree t = gimple_phi_arg_def (phi, i);
148 /* If an SSA has already been seen, it may be a loop,
149 but we can continue and ignore this use. Otherwise,
150 add the SSA_NAME to the queue and visit it later. */
151 if (TREE_CODE (t) == SSA_NAME
152 && bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t)))
153 worklist.safe_push (t);
154 }
155 continue;
156 }
157
158 /* Uses in stmts always executed when the region header executes
159 are fine. */
160 if (dominated_by_p (CDI_DOMINATORS, loop->header, gimple_bb (def)))
161 continue;
162
163 /* Handle calls and memory loads conservatively. */
164 if (!is_gimple_assign (def)
165 || (gimple_assign_single_p (def)
166 && gimple_vuse (def)))
167 return true;
168
169 /* Check that any SSA names used to define NAME are also fully
170 defined. */
171 use_operand_p use_p;
172 ssa_op_iter iter;
173 FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE)
174 {
175 tree t = USE_FROM_PTR (use_p);
176 /* If an SSA has already been seen, it may be a loop,
177 but we can continue and ignore this use. Otherwise,
178 add the SSA_NAME to the queue and visit it later. */
179 if (bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t)))
180 worklist.safe_push (t);
181 }
182 }
183 return false;
184 }
185
186 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
187 basic blocks (for what it means see comments below). */
188
189 static tree
tree_may_unswitch_on(basic_block bb,class loop * loop)190 tree_may_unswitch_on (basic_block bb, class loop *loop)
191 {
192 gimple *last, *def;
193 gcond *stmt;
194 tree cond, use;
195 basic_block def_bb;
196 ssa_op_iter iter;
197
198 /* BB must end in a simple conditional jump. */
199 last = last_stmt (bb);
200 if (!last || gimple_code (last) != GIMPLE_COND)
201 return NULL_TREE;
202 stmt = as_a <gcond *> (last);
203
204 /* To keep the things simple, we do not directly remove the conditions,
205 but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite
206 loop where we would unswitch again on such a condition. */
207 if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt))
208 return NULL_TREE;
209
210 /* Condition must be invariant. */
211 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
212 {
213 def = SSA_NAME_DEF_STMT (use);
214 def_bb = gimple_bb (def);
215 if (def_bb
216 && flow_bb_inside_loop_p (loop, def_bb))
217 return NULL_TREE;
218 /* Unswitching on undefined values would introduce undefined
219 behavior that the original program might never exercise. */
220 if (is_maybe_undefined (use, stmt, loop))
221 return NULL_TREE;
222 }
223
224 cond = build2 (gimple_cond_code (stmt), boolean_type_node,
225 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
226
227 return cond;
228 }
229
230 /* Simplifies COND using checks in front of the entry of the LOOP. Just very
231 simplish (sufficient to prevent us from duplicating loop in unswitching
232 unnecessarily). */
233
234 static tree
simplify_using_entry_checks(class loop * loop,tree cond)235 simplify_using_entry_checks (class loop *loop, tree cond)
236 {
237 edge e = loop_preheader_edge (loop);
238 gimple *stmt;
239
240 while (1)
241 {
242 stmt = last_stmt (e->src);
243 if (stmt
244 && gimple_code (stmt) == GIMPLE_COND
245 && gimple_cond_code (stmt) == TREE_CODE (cond)
246 && operand_equal_p (gimple_cond_lhs (stmt),
247 TREE_OPERAND (cond, 0), 0)
248 && operand_equal_p (gimple_cond_rhs (stmt),
249 TREE_OPERAND (cond, 1), 0))
250 return (e->flags & EDGE_TRUE_VALUE
251 ? boolean_true_node
252 : boolean_false_node);
253
254 if (!single_pred_p (e->src))
255 return cond;
256
257 e = single_pred_edge (e->src);
258 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
259 return cond;
260 }
261 }
262
263 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow
264 it to grow too much, it is too easy to create example on that the code would
265 grow exponentially. */
266
267 static bool
tree_unswitch_single_loop(class loop * loop,int num)268 tree_unswitch_single_loop (class loop *loop, int num)
269 {
270 basic_block *bbs;
271 class loop *nloop;
272 unsigned i, found;
273 tree cond = NULL_TREE;
274 gimple *stmt;
275 bool changed = false;
276 HOST_WIDE_INT iterations;
277
278 dump_user_location_t loc = find_loop_location (loop);
279
280 /* Perform initial tests if unswitch is eligible. */
281 if (num == 0)
282 {
283 /* Do not unswitch in cold regions. */
284 if (optimize_loop_for_size_p (loop))
285 {
286 if (dump_enabled_p ())
287 dump_printf_loc (MSG_NOTE, loc,
288 "Not unswitching cold loops\n");
289 return false;
290 }
291
292 /* The loop should not be too large, to limit code growth. */
293 if (tree_num_loop_insns (loop, &eni_size_weights)
294 > (unsigned) param_max_unswitch_insns)
295 {
296 if (dump_enabled_p ())
297 dump_printf_loc (MSG_NOTE, loc,
298 "Not unswitching, loop too big\n");
299 return false;
300 }
301
302 /* If the loop is not expected to iterate, there is no need
303 for unswitching. */
304 iterations = estimated_loop_iterations_int (loop);
305 if (iterations < 0)
306 iterations = likely_max_loop_iterations_int (loop);
307 if (iterations >= 0 && iterations <= 1)
308 {
309 if (dump_enabled_p ())
310 dump_printf_loc (MSG_NOTE, loc,
311 "Not unswitching, loop is not expected"
312 " to iterate\n");
313 return false;
314 }
315 }
316
317 i = 0;
318 bbs = get_loop_body (loop);
319 found = loop->num_nodes;
320
321 while (1)
322 {
323 /* Find a bb to unswitch on. */
324 for (; i < loop->num_nodes; i++)
325 if ((cond = tree_may_unswitch_on (bbs[i], loop)))
326 break;
327
328 if (i == loop->num_nodes)
329 {
330 if (dump_enabled_p ()
331 && num > param_max_unswitch_level)
332 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
333 "Not unswitching anymore, hit max level\n");
334
335 if (found == loop->num_nodes)
336 {
337 free (bbs);
338 return changed;
339 }
340 break;
341 }
342
343 cond = simplify_using_entry_checks (loop, cond);
344 stmt = last_stmt (bbs[i]);
345 if (integer_nonzerop (cond))
346 {
347 /* Remove false path. */
348 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
349 boolean_true_node);
350 changed = true;
351 }
352 else if (integer_zerop (cond))
353 {
354 /* Remove true path. */
355 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
356 boolean_false_node);
357 changed = true;
358 }
359 /* Do not unswitch too much. */
360 else if (num > param_max_unswitch_level)
361 {
362 i++;
363 continue;
364 }
365 /* In nested tree_unswitch_single_loop first optimize all conditions
366 using entry checks, then discover still reachable blocks in the
367 loop and find the condition only among those still reachable bbs. */
368 else if (num != 0)
369 {
370 if (found == loop->num_nodes)
371 found = i;
372 i++;
373 continue;
374 }
375 else
376 {
377 found = i;
378 break;
379 }
380
381 update_stmt (stmt);
382 i++;
383 }
384
385 if (num != 0)
386 {
387 basic_block *tos, *worklist;
388
389 /* When called recursively, first do a quick discovery
390 of reachable bbs after the above changes and only
391 consider conditions in still reachable bbs. */
392 tos = worklist = XNEWVEC (basic_block, loop->num_nodes);
393
394 for (i = 0; i < loop->num_nodes; i++)
395 bbs[i]->flags &= ~BB_REACHABLE;
396
397 /* Start with marking header. */
398 *tos++ = bbs[0];
399 bbs[0]->flags |= BB_REACHABLE;
400
401 /* Iterate: find everything reachable from what we've already seen
402 within the same innermost loop. Don't look through false edges
403 if condition is always true or true edges if condition is
404 always false. */
405 while (tos != worklist)
406 {
407 basic_block b = *--tos;
408 edge e;
409 edge_iterator ei;
410 int flags = 0;
411
412 if (EDGE_COUNT (b->succs) == 2)
413 {
414 gimple *stmt = last_stmt (b);
415 if (stmt
416 && gimple_code (stmt) == GIMPLE_COND)
417 {
418 gcond *cond_stmt = as_a <gcond *> (stmt);
419 if (gimple_cond_true_p (cond_stmt))
420 flags = EDGE_FALSE_VALUE;
421 else if (gimple_cond_false_p (cond_stmt))
422 flags = EDGE_TRUE_VALUE;
423 }
424 }
425
426 FOR_EACH_EDGE (e, ei, b->succs)
427 {
428 basic_block dest = e->dest;
429
430 if (dest->loop_father == loop
431 && !(dest->flags & BB_REACHABLE)
432 && !(e->flags & flags))
433 {
434 *tos++ = dest;
435 dest->flags |= BB_REACHABLE;
436 }
437 }
438 }
439
440 free (worklist);
441
442 /* Find a bb to unswitch on. */
443 for (; found < loop->num_nodes; found++)
444 if ((bbs[found]->flags & BB_REACHABLE)
445 && (cond = tree_may_unswitch_on (bbs[found], loop)))
446 break;
447
448 if (found == loop->num_nodes)
449 {
450 free (bbs);
451 return changed;
452 }
453 }
454
455 if (dump_enabled_p ())
456 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
457 "Unswitching loop on condition: %G\n",
458 last_stmt (bbs[found]));
459
460 initialize_original_copy_tables ();
461 /* Unswitch the loop on this condition. */
462 nloop = tree_unswitch_loop (loop, bbs[found], cond);
463 if (!nloop)
464 {
465 free_original_copy_tables ();
466 free (bbs);
467 return changed;
468 }
469
470 /* Update the SSA form after unswitching. */
471 update_ssa (TODO_update_ssa);
472 free_original_copy_tables ();
473
474 /* Invoke itself on modified loops. */
475 tree_unswitch_single_loop (nloop, num + 1);
476 tree_unswitch_single_loop (loop, num + 1);
477 free (bbs);
478 return true;
479 }
480
481 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
482 unswitching of innermost loops. COND is the condition determining which
483 loop is entered -- the new loop is entered if COND is true. Returns NULL
484 if impossible, new loop otherwise. */
485
486 static class loop *
tree_unswitch_loop(class loop * loop,basic_block unswitch_on,tree cond)487 tree_unswitch_loop (class loop *loop,
488 basic_block unswitch_on, tree cond)
489 {
490 profile_probability prob_true;
491 edge edge_true, edge_false;
492
493 /* Some sanity checking. */
494 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
495 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
496 gcc_assert (loop->inner == NULL);
497
498 extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
499 prob_true = edge_true->probability;
500 return loop_version (loop, unshare_expr (cond),
501 NULL, prob_true,
502 prob_true.invert (),
503 prob_true, prob_true.invert (),
504 false);
505 }
506
507 /* Unswitch outer loops by hoisting invariant guard on
508 inner loop without code duplication. */
509 static bool
tree_unswitch_outer_loop(class loop * loop)510 tree_unswitch_outer_loop (class loop *loop)
511 {
512 edge exit, guard;
513 HOST_WIDE_INT iterations;
514
515 gcc_assert (loop->inner);
516 if (loop->inner->next)
517 return false;
518 /* Accept loops with single exit only which is not from inner loop. */
519 exit = single_exit (loop);
520 if (!exit || exit->src->loop_father != loop)
521 return false;
522 /* Check that phi argument of exit edge is not defined inside loop. */
523 if (!check_exit_phi (loop))
524 return false;
525 /* If the loop is not expected to iterate, there is no need
526 for unswitching. */
527 iterations = estimated_loop_iterations_int (loop);
528 if (iterations < 0)
529 iterations = likely_max_loop_iterations_int (loop);
530 if (iterations >= 0 && iterations <= 1)
531 {
532 if (dump_enabled_p ())
533 dump_printf_loc (MSG_MISSED_OPTIMIZATION, find_loop_location (loop),
534 "Not unswitching, loop is not expected"
535 " to iterate\n");
536 return false;
537 }
538
539 bool changed = false;
540 auto_vec<gimple *> dbg_to_reset;
541 while ((guard = find_loop_guard (loop, dbg_to_reset)))
542 {
543 if (! changed)
544 rewrite_virtuals_into_loop_closed_ssa (loop);
545 hoist_guard (loop, guard);
546 for (gimple *debug_stmt : dbg_to_reset)
547 {
548 gimple_debug_bind_reset_value (debug_stmt);
549 update_stmt (debug_stmt);
550 }
551 dbg_to_reset.truncate (0);
552 changed = true;
553 }
554 return changed;
555 }
556
557 /* Checks if the body of the LOOP is within an invariant guard. If this
558 is the case, returns the edge that jumps over the real body of the loop,
559 otherwise returns NULL. */
560
561 static edge
find_loop_guard(class loop * loop,vec<gimple * > & dbg_to_reset)562 find_loop_guard (class loop *loop, vec<gimple *> &dbg_to_reset)
563 {
564 basic_block header = loop->header;
565 edge guard_edge, te, fe;
566 basic_block *body = NULL;
567 unsigned i;
568 tree use;
569 ssa_op_iter iter;
570
571 /* We check for the following situation:
572
573 while (1)
574 {
575 [header]]
576 loop_phi_nodes;
577 something1;
578 if (cond1)
579 body;
580 nvar = phi(orig, bvar) ... for all variables changed in body;
581 [guard_end]
582 something2;
583 if (cond2)
584 break;
585 something3;
586 }
587
588 where:
589
590 1) cond1 is loop invariant
591 2) If cond1 is false, then the loop is essentially empty; i.e.,
592 a) nothing in something1, something2 and something3 has side
593 effects
594 b) anything defined in something1, something2 and something3
595 is not used outside of the loop. */
596
597 gcond *cond;
598 do
599 {
600 basic_block next = NULL;
601 if (single_succ_p (header))
602 next = single_succ (header);
603 else
604 {
605 cond = safe_dyn_cast <gcond *> (last_stmt (header));
606 if (! cond)
607 return NULL;
608 extract_true_false_edges_from_block (header, &te, &fe);
609 /* Make sure to skip earlier hoisted guards that are left
610 in place as if (true). */
611 if (gimple_cond_true_p (cond))
612 next = te->dest;
613 else if (gimple_cond_false_p (cond))
614 next = fe->dest;
615 else
616 break;
617 }
618 /* Never traverse a backedge. */
619 if (header->loop_father->header == next)
620 return NULL;
621 header = next;
622 }
623 while (1);
624 if (!flow_bb_inside_loop_p (loop, te->dest)
625 || !flow_bb_inside_loop_p (loop, fe->dest))
626 return NULL;
627
628 if (just_once_each_iteration_p (loop, te->dest)
629 || (single_succ_p (te->dest)
630 && just_once_each_iteration_p (loop, single_succ (te->dest))))
631 {
632 if (just_once_each_iteration_p (loop, fe->dest))
633 return NULL;
634 guard_edge = te;
635 }
636 else if (just_once_each_iteration_p (loop, fe->dest)
637 || (single_succ_p (fe->dest)
638 && just_once_each_iteration_p (loop, single_succ (fe->dest))))
639 guard_edge = fe;
640 else
641 return NULL;
642
643 dump_user_location_t loc = find_loop_location (loop);
644
645 /* Guard edge must skip inner loop. */
646 if (!dominated_by_p (CDI_DOMINATORS, loop->inner->header,
647 guard_edge == fe ? te->dest : fe->dest))
648 {
649 if (dump_enabled_p ())
650 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
651 "Guard edge %d --> %d is not around the loop!\n",
652 guard_edge->src->index, guard_edge->dest->index);
653 return NULL;
654 }
655 if (guard_edge->dest == loop->latch)
656 {
657 if (dump_enabled_p ())
658 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
659 "Guard edge destination is loop latch.\n");
660 return NULL;
661 }
662
663 if (dump_enabled_p ())
664 dump_printf_loc (MSG_NOTE, loc,
665 "Considering guard %d -> %d in loop %d\n",
666 guard_edge->src->index, guard_edge->dest->index,
667 loop->num);
668 /* Check if condition operands do not have definitions inside loop since
669 any bb copying is not performed. */
670 FOR_EACH_SSA_TREE_OPERAND (use, cond, iter, SSA_OP_USE)
671 {
672 gimple *def = SSA_NAME_DEF_STMT (use);
673 basic_block def_bb = gimple_bb (def);
674 if (def_bb
675 && flow_bb_inside_loop_p (loop, def_bb))
676 {
677 if (dump_enabled_p ())
678 dump_printf_loc (MSG_NOTE, loc, "guard operands have definitions"
679 " inside loop\n");
680 return NULL;
681 }
682 }
683
684 body = get_loop_body (loop);
685 for (i = 0; i < loop->num_nodes; i++)
686 {
687 basic_block bb = body[i];
688 if (bb->loop_father != loop)
689 continue;
690 if (bb->flags & BB_IRREDUCIBLE_LOOP)
691 {
692 if (dump_enabled_p ())
693 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
694 "Block %d is marked as irreducible in loop\n",
695 bb->index);
696 guard_edge = NULL;
697 goto end;
698 }
699 if (!empty_bb_without_guard_p (loop, bb, dbg_to_reset))
700 {
701 if (dump_enabled_p ())
702 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
703 "Block %d has side effects\n", bb->index);
704 guard_edge = NULL;
705 goto end;
706 }
707 }
708
709 if (dump_enabled_p ())
710 dump_printf_loc (MSG_NOTE, loc,
711 "suitable to hoist\n");
712 end:
713 if (body)
714 free (body);
715 return guard_edge;
716 }
717
718 /* Returns true if
719 1) no statement in BB has side effects
720 2) assuming that edge GUARD is always taken, all definitions in BB
721 are noy used outside of the loop.
722 KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
723 PROCESSED is a set of ssa names for that we already tested whether they
724 are invariant or not. Uses in debug stmts outside of the loop are
725 pushed to DBG_TO_RESET. */
726
727 static bool
empty_bb_without_guard_p(class loop * loop,basic_block bb,vec<gimple * > & dbg_to_reset)728 empty_bb_without_guard_p (class loop *loop, basic_block bb,
729 vec<gimple *> &dbg_to_reset)
730 {
731 basic_block exit_bb = single_exit (loop)->src;
732 bool may_be_used_outside = (bb == exit_bb
733 || !dominated_by_p (CDI_DOMINATORS, bb, exit_bb));
734 tree name;
735 ssa_op_iter op_iter;
736
737 /* Phi nodes do not have side effects, but their results might be used
738 outside of the loop. */
739 if (may_be_used_outside)
740 {
741 for (gphi_iterator gsi = gsi_start_phis (bb);
742 !gsi_end_p (gsi); gsi_next (&gsi))
743 {
744 gphi *phi = gsi.phi ();
745 name = PHI_RESULT (phi);
746 if (virtual_operand_p (name))
747 continue;
748
749 if (used_outside_loop_p (loop, name, dbg_to_reset))
750 return false;
751 }
752 }
753
754 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
755 !gsi_end_p (gsi); gsi_next (&gsi))
756 {
757 gimple *stmt = gsi_stmt (gsi);
758 if (is_gimple_debug (stmt))
759 continue;
760
761 if (gimple_has_side_effects (stmt))
762 return false;
763
764 if (gimple_vdef(stmt))
765 return false;
766
767 FOR_EACH_SSA_TREE_OPERAND (name, stmt, op_iter, SSA_OP_DEF)
768 {
769 if (may_be_used_outside
770 && used_outside_loop_p (loop, name, dbg_to_reset))
771 return false;
772 }
773 }
774 return true;
775 }
776
777 /* Return true if NAME is used outside of LOOP. Pushes debug stmts that
778 have such uses to DBG_TO_RESET but do not consider such uses. */
779
780 static bool
used_outside_loop_p(class loop * loop,tree name,vec<gimple * > & dbg_to_reset)781 used_outside_loop_p (class loop *loop, tree name, vec<gimple *> &dbg_to_reset)
782 {
783 imm_use_iterator it;
784 use_operand_p use;
785
786 FOR_EACH_IMM_USE_FAST (use, it, name)
787 {
788 gimple *stmt = USE_STMT (use);
789 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
790 {
791 if (!is_gimple_debug (stmt))
792 return true;
793 dbg_to_reset.safe_push (stmt);
794 }
795 }
796
797 return false;
798 }
799
800 /* Return argument for loop preheader edge in header virtual phi if any. */
801
802 static tree
get_vop_from_header(class loop * loop)803 get_vop_from_header (class loop *loop)
804 {
805 for (gphi_iterator gsi = gsi_start_phis (loop->header);
806 !gsi_end_p (gsi); gsi_next (&gsi))
807 {
808 gphi *phi = gsi.phi ();
809 if (!virtual_operand_p (gimple_phi_result (phi)))
810 continue;
811 return PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
812 }
813 return NULL_TREE;
814 }
815
816 /* Move the check of GUARD outside of LOOP. */
817
818 static void
hoist_guard(class loop * loop,edge guard)819 hoist_guard (class loop *loop, edge guard)
820 {
821 edge exit = single_exit (loop);
822 edge preh = loop_preheader_edge (loop);
823 basic_block pre_header = preh->src;
824 basic_block bb;
825 edge te, fe, e, new_edge;
826 gimple *stmt;
827 basic_block guard_bb = guard->src;
828 edge not_guard;
829 gimple_stmt_iterator gsi;
830 int flags = 0;
831 bool fix_dom_of_exit;
832 gcond *cond_stmt, *new_cond_stmt;
833
834 bb = get_immediate_dominator (CDI_DOMINATORS, exit->dest);
835 fix_dom_of_exit = flow_bb_inside_loop_p (loop, bb);
836 gsi = gsi_last_bb (guard_bb);
837 stmt = gsi_stmt (gsi);
838 gcc_assert (gimple_code (stmt) == GIMPLE_COND);
839 cond_stmt = as_a <gcond *> (stmt);
840 extract_true_false_edges_from_block (guard_bb, &te, &fe);
841 /* Insert guard to PRE_HEADER. */
842 gsi = gsi_last_bb (pre_header);
843 /* Create copy of COND_STMT. */
844 new_cond_stmt = gimple_build_cond (gimple_cond_code (cond_stmt),
845 gimple_cond_lhs (cond_stmt),
846 gimple_cond_rhs (cond_stmt),
847 NULL_TREE, NULL_TREE);
848 gsi_insert_after (&gsi, new_cond_stmt, GSI_NEW_STMT);
849 /* Convert COND_STMT to true/false conditional. */
850 if (guard == te)
851 gimple_cond_make_false (cond_stmt);
852 else
853 gimple_cond_make_true (cond_stmt);
854 update_stmt (cond_stmt);
855 /* Create new loop pre-header. */
856 e = split_block (pre_header, last_stmt (pre_header));
857
858 dump_user_location_t loc = find_loop_location (loop);
859
860 if (dump_enabled_p ())
861 {
862 char buffer[64];
863 guard->probability.dump (buffer);
864
865 dump_printf_loc (MSG_NOTE, loc,
866 "Moving guard %i->%i (prob %s) to bb %i, "
867 "new preheader is %i\n",
868 guard->src->index, guard->dest->index,
869 buffer, e->src->index, e->dest->index);
870 }
871
872 gcc_assert (loop_preheader_edge (loop)->src == e->dest);
873
874 if (guard == fe)
875 {
876 e->flags = EDGE_TRUE_VALUE;
877 flags |= EDGE_FALSE_VALUE;
878 not_guard = te;
879 }
880 else
881 {
882 e->flags = EDGE_FALSE_VALUE;
883 flags |= EDGE_TRUE_VALUE;
884 not_guard = fe;
885 }
886 new_edge = make_edge (pre_header, exit->dest, flags);
887
888 /* Determine the probability that we skip the loop. Assume that loop has
889 same average number of iterations regardless outcome of guard. */
890 new_edge->probability = guard->probability;
891 profile_count skip_count = guard->src->count.nonzero_p ()
892 ? guard->count ().apply_scale (pre_header->count,
893 guard->src->count)
894 : guard->count ().apply_probability (new_edge->probability);
895
896 if (skip_count > e->count ())
897 {
898 fprintf (dump_file, " Capping count; expect profile inconsistency\n");
899 skip_count = e->count ();
900 }
901 if (dump_enabled_p ())
902 {
903 char buffer[64];
904 new_edge->probability.dump (buffer);
905
906 dump_printf_loc (MSG_NOTE, loc,
907 "Estimated probability of skipping loop is %s\n",
908 buffer);
909 }
910
911 /* Update profile after the transform:
912
913 First decrease count of path from newly hoisted loop guard
914 to loop header... */
915 e->probability = new_edge->probability.invert ();
916 e->dest->count = e->count ();
917
918 /* ... now update profile to represent that original guard will be optimized
919 away ... */
920 guard->probability = profile_probability::never ();
921 not_guard->probability = profile_probability::always ();
922
923 /* ... finally scale everything in the loop except for guarded basic blocks
924 where profile does not change. */
925 basic_block *body = get_loop_body (loop);
926
927 for (unsigned int i = 0; i < loop->num_nodes; i++)
928 {
929 basic_block bb = body[i];
930 if (!dominated_by_p (CDI_DOMINATORS, bb, not_guard->dest))
931 {
932 if (dump_enabled_p ())
933 dump_printf_loc (MSG_NOTE, loc,
934 "Scaling nonguarded BBs in loop: %i\n",
935 bb->index);
936 if (e->probability.initialized_p ())
937 scale_bbs_frequencies (&bb, 1, e->probability);
938 }
939 }
940
941 if (fix_dom_of_exit)
942 set_immediate_dominator (CDI_DOMINATORS, exit->dest, pre_header);
943 /* Add NEW_ADGE argument for all phi in post-header block. */
944 bb = exit->dest;
945 for (gphi_iterator gsi = gsi_start_phis (bb);
946 !gsi_end_p (gsi); gsi_next (&gsi))
947 {
948 gphi *phi = gsi.phi ();
949 tree arg;
950 if (virtual_operand_p (gimple_phi_result (phi)))
951 {
952 arg = get_vop_from_header (loop);
953 if (arg == NULL_TREE)
954 /* Use exit edge argument. */
955 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
956 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
957 }
958 else
959 {
960 /* Use exit edge argument. */
961 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
962 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
963 }
964 }
965
966 if (dump_enabled_p ())
967 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
968 "Guard hoisted\n");
969
970 free (body);
971 }
972
973 /* Return true if phi argument for exit edge can be used
974 for edge around loop. */
975
976 static bool
check_exit_phi(class loop * loop)977 check_exit_phi (class loop *loop)
978 {
979 edge exit = single_exit (loop);
980 basic_block pre_header = loop_preheader_edge (loop)->src;
981
982 for (gphi_iterator gsi = gsi_start_phis (exit->dest);
983 !gsi_end_p (gsi); gsi_next (&gsi))
984 {
985 gphi *phi = gsi.phi ();
986 tree arg;
987 gimple *def;
988 basic_block def_bb;
989 if (virtual_operand_p (gimple_phi_result (phi)))
990 continue;
991 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
992 if (TREE_CODE (arg) != SSA_NAME)
993 continue;
994 def = SSA_NAME_DEF_STMT (arg);
995 if (!def)
996 continue;
997 def_bb = gimple_bb (def);
998 if (!def_bb)
999 continue;
1000 if (!dominated_by_p (CDI_DOMINATORS, pre_header, def_bb))
1001 /* Definition inside loop! */
1002 return false;
1003 /* Check loop closed phi invariant. */
1004 if (!flow_bb_inside_loop_p (def_bb->loop_father, pre_header))
1005 return false;
1006 }
1007 return true;
1008 }
1009
1010 /* Loop unswitching pass. */
1011
1012 namespace {
1013
1014 const pass_data pass_data_tree_unswitch =
1015 {
1016 GIMPLE_PASS, /* type */
1017 "unswitch", /* name */
1018 OPTGROUP_LOOP, /* optinfo_flags */
1019 TV_TREE_LOOP_UNSWITCH, /* tv_id */
1020 PROP_cfg, /* properties_required */
1021 0, /* properties_provided */
1022 0, /* properties_destroyed */
1023 0, /* todo_flags_start */
1024 0, /* todo_flags_finish */
1025 };
1026
1027 class pass_tree_unswitch : public gimple_opt_pass
1028 {
1029 public:
pass_tree_unswitch(gcc::context * ctxt)1030 pass_tree_unswitch (gcc::context *ctxt)
1031 : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
1032 {}
1033
1034 /* opt_pass methods: */
gate(function *)1035 virtual bool gate (function *) { return flag_unswitch_loops != 0; }
1036 virtual unsigned int execute (function *);
1037
1038 }; // class pass_tree_unswitch
1039
1040 unsigned int
execute(function * fun)1041 pass_tree_unswitch::execute (function *fun)
1042 {
1043 if (number_of_loops (fun) <= 1)
1044 return 0;
1045
1046 return tree_ssa_unswitch_loops ();
1047 }
1048
1049 } // anon namespace
1050
1051 gimple_opt_pass *
make_pass_tree_unswitch(gcc::context * ctxt)1052 make_pass_tree_unswitch (gcc::context *ctxt)
1053 {
1054 return new pass_tree_unswitch (ctxt);
1055 }
1056
1057
1058