mklog: add subject line skeleton
[official-gcc.git] / gcc / tree-ssa-loop-unswitch.c
blob04d4553f13eefbf0505e35eb49b30240afc425fd
1 /* Loop unswitching.
2 Copyright (C) 2004-2021 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
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"
41 /* This file implements the loop unswitching, i.e. transformation of loops like
43 while (A)
45 if (inv)
50 if (!inv)
54 where inv is the loop invariant, into
56 if (inv)
58 while (A)
64 else
66 while (A)
73 Inv is considered invariant iff the values it compares are both invariant;
74 tree-ssa-loop-im.c ensures that all the suitable conditions are in this
75 shape. */
77 static class loop *tree_unswitch_loop (class loop *, basic_block, tree);
78 static bool tree_unswitch_single_loop (class loop *, int);
79 static tree tree_may_unswitch_on (basic_block, class loop *);
80 static bool tree_unswitch_outer_loop (class loop *);
81 static edge find_loop_guard (class loop *);
82 static bool empty_bb_without_guard_p (class loop *, basic_block);
83 static bool used_outside_loop_p (class loop *, tree);
84 static void hoist_guard (class loop *, edge);
85 static bool check_exit_phi (class loop *);
86 static tree get_vop_from_header (class loop *);
88 /* Main entry point. Perform loop unswitching on all suitable loops. */
90 unsigned int
91 tree_ssa_unswitch_loops (void)
93 class loop *loop;
94 bool changed = false;
96 /* Go through all loops starting from innermost. */
97 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
99 if (!loop->inner)
100 /* Unswitch innermost loop. */
101 changed |= tree_unswitch_single_loop (loop, 0);
102 else
103 changed |= tree_unswitch_outer_loop (loop);
106 if (changed)
107 return TODO_cleanup_cfg;
108 return 0;
111 /* Return TRUE if an SSA_NAME maybe undefined and is therefore
112 unsuitable for unswitching. STMT is the statement we are
113 considering for unswitching and LOOP is the loop it appears in. */
115 static bool
116 is_maybe_undefined (const tree name, gimple *stmt, class loop *loop)
118 /* The loop header is the only block we can trivially determine that
119 will always be executed. If the comparison is in the loop
120 header, we know it's OK to unswitch on it. */
121 if (gimple_bb (stmt) == loop->header)
122 return false;
124 auto_bitmap visited_ssa;
125 auto_vec<tree> worklist;
126 worklist.safe_push (name);
127 bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (name));
128 while (!worklist.is_empty ())
130 tree t = worklist.pop ();
132 /* If it's obviously undefined, avoid further computations. */
133 if (ssa_undefined_value_p (t, true))
134 return true;
136 if (ssa_defined_default_def_p (t))
137 continue;
139 gimple *def = SSA_NAME_DEF_STMT (t);
141 /* Check that all the PHI args are fully defined. */
142 if (gphi *phi = dyn_cast <gphi *> (def))
144 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
146 tree t = gimple_phi_arg_def (phi, i);
147 /* If an SSA has already been seen, it may be a loop,
148 but we can continue and ignore this use. Otherwise,
149 add the SSA_NAME to the queue and visit it later. */
150 if (TREE_CODE (t) == SSA_NAME
151 && bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t)))
152 worklist.safe_push (t);
154 continue;
157 /* Uses in stmts always executed when the region header executes
158 are fine. */
159 if (dominated_by_p (CDI_DOMINATORS, loop->header, gimple_bb (def)))
160 continue;
162 /* Handle calls and memory loads conservatively. */
163 if (!is_gimple_assign (def)
164 || (gimple_assign_single_p (def)
165 && gimple_vuse (def)))
166 return true;
168 /* Check that any SSA names used to define NAME are also fully
169 defined. */
170 use_operand_p use_p;
171 ssa_op_iter iter;
172 FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE)
174 tree t = USE_FROM_PTR (use_p);
175 /* If an SSA has already been seen, it may be a loop,
176 but we can continue and ignore this use. Otherwise,
177 add the SSA_NAME to the queue and visit it later. */
178 if (bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t)))
179 worklist.safe_push (t);
182 return false;
185 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
186 basic blocks (for what it means see comments below). */
188 static tree
189 tree_may_unswitch_on (basic_block bb, class loop *loop)
191 gimple *last, *def;
192 gcond *stmt;
193 tree cond, use;
194 basic_block def_bb;
195 ssa_op_iter iter;
197 /* BB must end in a simple conditional jump. */
198 last = last_stmt (bb);
199 if (!last || gimple_code (last) != GIMPLE_COND)
200 return NULL_TREE;
201 stmt = as_a <gcond *> (last);
203 /* To keep the things simple, we do not directly remove the conditions,
204 but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite
205 loop where we would unswitch again on such a condition. */
206 if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt))
207 return NULL_TREE;
209 /* Condition must be invariant. */
210 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
212 def = SSA_NAME_DEF_STMT (use);
213 def_bb = gimple_bb (def);
214 if (def_bb
215 && flow_bb_inside_loop_p (loop, def_bb))
216 return NULL_TREE;
217 /* Unswitching on undefined values would introduce undefined
218 behavior that the original program might never exercise. */
219 if (is_maybe_undefined (use, stmt, loop))
220 return NULL_TREE;
223 cond = build2 (gimple_cond_code (stmt), boolean_type_node,
224 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
226 return cond;
229 /* Simplifies COND using checks in front of the entry of the LOOP. Just very
230 simplish (sufficient to prevent us from duplicating loop in unswitching
231 unnecessarily). */
233 static tree
234 simplify_using_entry_checks (class loop *loop, tree cond)
236 edge e = loop_preheader_edge (loop);
237 gimple *stmt;
239 while (1)
241 stmt = last_stmt (e->src);
242 if (stmt
243 && gimple_code (stmt) == GIMPLE_COND
244 && gimple_cond_code (stmt) == TREE_CODE (cond)
245 && operand_equal_p (gimple_cond_lhs (stmt),
246 TREE_OPERAND (cond, 0), 0)
247 && operand_equal_p (gimple_cond_rhs (stmt),
248 TREE_OPERAND (cond, 1), 0))
249 return (e->flags & EDGE_TRUE_VALUE
250 ? boolean_true_node
251 : boolean_false_node);
253 if (!single_pred_p (e->src))
254 return cond;
256 e = single_pred_edge (e->src);
257 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
258 return cond;
262 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow
263 it to grow too much, it is too easy to create example on that the code would
264 grow exponentially. */
266 static bool
267 tree_unswitch_single_loop (class loop *loop, int num)
269 basic_block *bbs;
270 class loop *nloop;
271 unsigned i, found;
272 tree cond = NULL_TREE;
273 gimple *stmt;
274 bool changed = false;
275 HOST_WIDE_INT iterations;
277 /* Perform initial tests if unswitch is eligible. */
278 if (num == 0)
280 /* Do not unswitch in cold regions. */
281 if (optimize_loop_for_size_p (loop))
283 if (dump_file && (dump_flags & TDF_DETAILS))
284 fprintf (dump_file, ";; Not unswitching cold loops\n");
285 return false;
288 /* The loop should not be too large, to limit code growth. */
289 if (tree_num_loop_insns (loop, &eni_size_weights)
290 > (unsigned) param_max_unswitch_insns)
292 if (dump_file && (dump_flags & TDF_DETAILS))
293 fprintf (dump_file, ";; Not unswitching, loop too big\n");
294 return false;
297 /* If the loop is not expected to iterate, there is no need
298 for unswitching. */
299 iterations = estimated_loop_iterations_int (loop);
300 if (iterations < 0)
301 iterations = likely_max_loop_iterations_int (loop);
302 if (iterations >= 0 && iterations <= 1)
304 if (dump_file && (dump_flags & TDF_DETAILS))
305 fprintf (dump_file, ";; Not unswitching, loop is not expected"
306 " to iterate\n");
307 return false;
311 i = 0;
312 bbs = get_loop_body (loop);
313 found = loop->num_nodes;
315 while (1)
317 /* Find a bb to unswitch on. */
318 for (; i < loop->num_nodes; i++)
319 if ((cond = tree_may_unswitch_on (bbs[i], loop)))
320 break;
322 if (i == loop->num_nodes)
324 if (dump_file
325 && num > param_max_unswitch_level
326 && (dump_flags & TDF_DETAILS))
327 fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
329 if (found == loop->num_nodes)
331 free (bbs);
332 return changed;
334 break;
337 cond = simplify_using_entry_checks (loop, cond);
338 stmt = last_stmt (bbs[i]);
339 if (integer_nonzerop (cond))
341 /* Remove false path. */
342 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
343 boolean_true_node);
344 changed = true;
346 else if (integer_zerop (cond))
348 /* Remove true path. */
349 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
350 boolean_false_node);
351 changed = true;
353 /* Do not unswitch too much. */
354 else if (num > param_max_unswitch_level)
356 i++;
357 continue;
359 /* In nested tree_unswitch_single_loop first optimize all conditions
360 using entry checks, then discover still reachable blocks in the
361 loop and find the condition only among those still reachable bbs. */
362 else if (num != 0)
364 if (found == loop->num_nodes)
365 found = i;
366 i++;
367 continue;
369 else
371 found = i;
372 break;
375 update_stmt (stmt);
376 i++;
379 if (num != 0)
381 basic_block *tos, *worklist;
383 /* When called recursively, first do a quick discovery
384 of reachable bbs after the above changes and only
385 consider conditions in still reachable bbs. */
386 tos = worklist = XNEWVEC (basic_block, loop->num_nodes);
388 for (i = 0; i < loop->num_nodes; i++)
389 bbs[i]->flags &= ~BB_REACHABLE;
391 /* Start with marking header. */
392 *tos++ = bbs[0];
393 bbs[0]->flags |= BB_REACHABLE;
395 /* Iterate: find everything reachable from what we've already seen
396 within the same innermost loop. Don't look through false edges
397 if condition is always true or true edges if condition is
398 always false. */
399 while (tos != worklist)
401 basic_block b = *--tos;
402 edge e;
403 edge_iterator ei;
404 int flags = 0;
406 if (EDGE_COUNT (b->succs) == 2)
408 gimple *stmt = last_stmt (b);
409 if (stmt
410 && gimple_code (stmt) == GIMPLE_COND)
412 gcond *cond_stmt = as_a <gcond *> (stmt);
413 if (gimple_cond_true_p (cond_stmt))
414 flags = EDGE_FALSE_VALUE;
415 else if (gimple_cond_false_p (cond_stmt))
416 flags = EDGE_TRUE_VALUE;
420 FOR_EACH_EDGE (e, ei, b->succs)
422 basic_block dest = e->dest;
424 if (dest->loop_father == loop
425 && !(dest->flags & BB_REACHABLE)
426 && !(e->flags & flags))
428 *tos++ = dest;
429 dest->flags |= BB_REACHABLE;
434 free (worklist);
436 /* Find a bb to unswitch on. */
437 for (; found < loop->num_nodes; found++)
438 if ((bbs[found]->flags & BB_REACHABLE)
439 && (cond = tree_may_unswitch_on (bbs[found], loop)))
440 break;
442 if (found == loop->num_nodes)
444 free (bbs);
445 return changed;
449 if (dump_file && (dump_flags & TDF_DETAILS))
450 fprintf (dump_file, ";; Unswitching loop\n");
452 initialize_original_copy_tables ();
453 /* Unswitch the loop on this condition. */
454 nloop = tree_unswitch_loop (loop, bbs[found], cond);
455 if (!nloop)
457 free_original_copy_tables ();
458 free (bbs);
459 return changed;
462 /* Update the SSA form after unswitching. */
463 update_ssa (TODO_update_ssa);
464 free_original_copy_tables ();
466 /* Invoke itself on modified loops. */
467 tree_unswitch_single_loop (nloop, num + 1);
468 tree_unswitch_single_loop (loop, num + 1);
469 free (bbs);
470 return true;
473 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
474 unswitching of innermost loops. COND is the condition determining which
475 loop is entered -- the new loop is entered if COND is true. Returns NULL
476 if impossible, new loop otherwise. */
478 static class loop *
479 tree_unswitch_loop (class loop *loop,
480 basic_block unswitch_on, tree cond)
482 profile_probability prob_true;
483 edge edge_true, edge_false;
485 /* Some sanity checking. */
486 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
487 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
488 gcc_assert (loop->inner == NULL);
490 extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
491 prob_true = edge_true->probability;
492 return loop_version (loop, unshare_expr (cond),
493 NULL, prob_true,
494 prob_true.invert (),
495 prob_true, prob_true.invert (),
496 false);
499 /* Unswitch outer loops by hoisting invariant guard on
500 inner loop without code duplication. */
501 static bool
502 tree_unswitch_outer_loop (class loop *loop)
504 edge exit, guard;
505 HOST_WIDE_INT iterations;
507 gcc_assert (loop->inner);
508 if (loop->inner->next)
509 return false;
510 /* Accept loops with single exit only which is not from inner loop. */
511 exit = single_exit (loop);
512 if (!exit || exit->src->loop_father != loop)
513 return false;
514 /* Check that phi argument of exit edge is not defined inside loop. */
515 if (!check_exit_phi (loop))
516 return false;
517 /* If the loop is not expected to iterate, there is no need
518 for unswitching. */
519 iterations = estimated_loop_iterations_int (loop);
520 if (iterations < 0)
521 iterations = likely_max_loop_iterations_int (loop);
522 if (iterations >= 0 && iterations <= 1)
524 if (dump_file && (dump_flags & TDF_DETAILS))
525 fprintf (dump_file, ";; Not unswitching, loop is not expected"
526 " to iterate\n");
527 return false;
530 bool changed = false;
531 while ((guard = find_loop_guard (loop)))
533 if (! changed)
534 rewrite_virtuals_into_loop_closed_ssa (loop);
535 hoist_guard (loop, guard);
536 changed = true;
538 return changed;
541 /* Checks if the body of the LOOP is within an invariant guard. If this
542 is the case, returns the edge that jumps over the real body of the loop,
543 otherwise returns NULL. */
545 static edge
546 find_loop_guard (class loop *loop)
548 basic_block header = loop->header;
549 edge guard_edge, te, fe;
550 basic_block *body = NULL;
551 unsigned i;
552 tree use;
553 ssa_op_iter iter;
555 /* We check for the following situation:
557 while (1)
559 [header]]
560 loop_phi_nodes;
561 something1;
562 if (cond1)
563 body;
564 nvar = phi(orig, bvar) ... for all variables changed in body;
565 [guard_end]
566 something2;
567 if (cond2)
568 break;
569 something3;
572 where:
574 1) cond1 is loop invariant
575 2) If cond1 is false, then the loop is essentially empty; i.e.,
576 a) nothing in something1, something2 and something3 has side
577 effects
578 b) anything defined in something1, something2 and something3
579 is not used outside of the loop. */
581 gcond *cond;
584 basic_block next = NULL;
585 if (single_succ_p (header))
586 next = single_succ (header);
587 else
589 cond = safe_dyn_cast <gcond *> (last_stmt (header));
590 if (! cond)
591 return NULL;
592 extract_true_false_edges_from_block (header, &te, &fe);
593 /* Make sure to skip earlier hoisted guards that are left
594 in place as if (true). */
595 if (gimple_cond_true_p (cond))
596 next = te->dest;
597 else if (gimple_cond_false_p (cond))
598 next = fe->dest;
599 else
600 break;
602 /* Never traverse a backedge. */
603 if (header->loop_father->header == next)
604 return NULL;
605 header = next;
607 while (1);
608 if (!flow_bb_inside_loop_p (loop, te->dest)
609 || !flow_bb_inside_loop_p (loop, fe->dest))
610 return NULL;
612 if (just_once_each_iteration_p (loop, te->dest)
613 || (single_succ_p (te->dest)
614 && just_once_each_iteration_p (loop, single_succ (te->dest))))
616 if (just_once_each_iteration_p (loop, fe->dest))
617 return NULL;
618 guard_edge = te;
620 else if (just_once_each_iteration_p (loop, fe->dest)
621 || (single_succ_p (fe->dest)
622 && just_once_each_iteration_p (loop, single_succ (fe->dest))))
623 guard_edge = fe;
624 else
625 return NULL;
627 /* Guard edge must skip inner loop. */
628 if (!dominated_by_p (CDI_DOMINATORS, loop->inner->header,
629 guard_edge == fe ? te->dest : fe->dest))
631 if (dump_file && (dump_flags & TDF_DETAILS))
632 fprintf (dump_file, "Guard edge %d --> %d is not around the loop!\n",
633 guard_edge->src->index, guard_edge->dest->index);
634 return NULL;
636 if (guard_edge->dest == loop->latch)
638 if (dump_file && (dump_flags & TDF_DETAILS))
639 fprintf (dump_file, "Guard edge destination is loop latch.\n");
640 return NULL;
643 if (dump_file && (dump_flags & TDF_DETAILS))
644 fprintf (dump_file,
645 "Considering guard %d -> %d in loop %d\n",
646 guard_edge->src->index, guard_edge->dest->index, loop->num);
647 /* Check if condition operands do not have definitions inside loop since
648 any bb copying is not performed. */
649 FOR_EACH_SSA_TREE_OPERAND (use, cond, iter, SSA_OP_USE)
651 gimple *def = SSA_NAME_DEF_STMT (use);
652 basic_block def_bb = gimple_bb (def);
653 if (def_bb
654 && flow_bb_inside_loop_p (loop, def_bb))
656 if (dump_file && (dump_flags & TDF_DETAILS))
657 fprintf (dump_file, " guard operands have definitions"
658 " inside loop\n");
659 return NULL;
663 body = get_loop_body (loop);
664 for (i = 0; i < loop->num_nodes; i++)
666 basic_block bb = body[i];
667 if (bb->loop_father != loop)
668 continue;
669 if (bb->flags & BB_IRREDUCIBLE_LOOP)
671 if (dump_file && (dump_flags & TDF_DETAILS))
672 fprintf (dump_file, "Block %d is marked as irreducible in loop\n",
673 bb->index);
674 guard_edge = NULL;
675 goto end;
677 if (!empty_bb_without_guard_p (loop, bb))
679 if (dump_file && (dump_flags & TDF_DETAILS))
680 fprintf (dump_file, " block %d has side effects\n", bb->index);
681 guard_edge = NULL;
682 goto end;
686 if (dump_file && (dump_flags & TDF_DETAILS))
687 fprintf (dump_file, " suitable to hoist\n");
688 end:
689 if (body)
690 free (body);
691 return guard_edge;
694 /* Returns true if
695 1) no statement in BB has side effects
696 2) assuming that edge GUARD is always taken, all definitions in BB
697 are noy used outside of the loop.
698 KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
699 PROCESSED is a set of ssa names for that we already tested whether they
700 are invariant or not. */
702 static bool
703 empty_bb_without_guard_p (class loop *loop, basic_block bb)
705 basic_block exit_bb = single_exit (loop)->src;
706 bool may_be_used_outside = (bb == exit_bb
707 || !dominated_by_p (CDI_DOMINATORS, bb, exit_bb));
708 tree name;
709 ssa_op_iter op_iter;
711 /* Phi nodes do not have side effects, but their results might be used
712 outside of the loop. */
713 if (may_be_used_outside)
715 for (gphi_iterator gsi = gsi_start_phis (bb);
716 !gsi_end_p (gsi); gsi_next (&gsi))
718 gphi *phi = gsi.phi ();
719 name = PHI_RESULT (phi);
720 if (virtual_operand_p (name))
721 continue;
723 if (used_outside_loop_p (loop, name))
724 return false;
728 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
729 !gsi_end_p (gsi); gsi_next (&gsi))
731 gimple *stmt = gsi_stmt (gsi);
732 if (gimple_has_side_effects (stmt))
733 return false;
735 if (gimple_vdef(stmt))
736 return false;
738 FOR_EACH_SSA_TREE_OPERAND (name, stmt, op_iter, SSA_OP_DEF)
740 if (may_be_used_outside
741 && used_outside_loop_p (loop, name))
742 return false;
745 return true;
748 /* Return true if NAME is used outside of LOOP. */
750 static bool
751 used_outside_loop_p (class loop *loop, tree name)
753 imm_use_iterator it;
754 use_operand_p use;
756 FOR_EACH_IMM_USE_FAST (use, it, name)
758 gimple *stmt = USE_STMT (use);
759 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
760 return true;
763 return false;
766 /* Return argument for loop preheader edge in header virtual phi if any. */
768 static tree
769 get_vop_from_header (class loop *loop)
771 for (gphi_iterator gsi = gsi_start_phis (loop->header);
772 !gsi_end_p (gsi); gsi_next (&gsi))
774 gphi *phi = gsi.phi ();
775 if (!virtual_operand_p (gimple_phi_result (phi)))
776 continue;
777 return PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
779 return NULL_TREE;
782 /* Move the check of GUARD outside of LOOP. */
784 static void
785 hoist_guard (class loop *loop, edge guard)
787 edge exit = single_exit (loop);
788 edge preh = loop_preheader_edge (loop);
789 basic_block pre_header = preh->src;
790 basic_block bb;
791 edge te, fe, e, new_edge;
792 gimple *stmt;
793 basic_block guard_bb = guard->src;
794 edge not_guard;
795 gimple_stmt_iterator gsi;
796 int flags = 0;
797 bool fix_dom_of_exit;
798 gcond *cond_stmt, *new_cond_stmt;
800 bb = get_immediate_dominator (CDI_DOMINATORS, exit->dest);
801 fix_dom_of_exit = flow_bb_inside_loop_p (loop, bb);
802 gsi = gsi_last_bb (guard_bb);
803 stmt = gsi_stmt (gsi);
804 gcc_assert (gimple_code (stmt) == GIMPLE_COND);
805 cond_stmt = as_a <gcond *> (stmt);
806 extract_true_false_edges_from_block (guard_bb, &te, &fe);
807 /* Insert guard to PRE_HEADER. */
808 if (!empty_block_p (pre_header))
809 gsi = gsi_last_bb (pre_header);
810 else
811 gsi = gsi_start_bb (pre_header);
812 /* Create copy of COND_STMT. */
813 new_cond_stmt = gimple_build_cond (gimple_cond_code (cond_stmt),
814 gimple_cond_lhs (cond_stmt),
815 gimple_cond_rhs (cond_stmt),
816 NULL_TREE, NULL_TREE);
817 gsi_insert_after (&gsi, new_cond_stmt, GSI_NEW_STMT);
818 /* Convert COND_STMT to true/false conditional. */
819 if (guard == te)
820 gimple_cond_make_false (cond_stmt);
821 else
822 gimple_cond_make_true (cond_stmt);
823 update_stmt (cond_stmt);
824 /* Create new loop pre-header. */
825 e = split_block (pre_header, last_stmt (pre_header));
826 if (dump_file && (dump_flags & TDF_DETAILS))
828 fprintf (dump_file, " Moving guard %i->%i (prob ",
829 guard->src->index, guard->dest->index);
830 guard->probability.dump (dump_file);
831 fprintf (dump_file, ") to bb %i, new preheader is %i\n",
832 e->src->index, e->dest->index);
835 gcc_assert (loop_preheader_edge (loop)->src == e->dest);
837 if (guard == fe)
839 e->flags = EDGE_TRUE_VALUE;
840 flags |= EDGE_FALSE_VALUE;
841 not_guard = te;
843 else
845 e->flags = EDGE_FALSE_VALUE;
846 flags |= EDGE_TRUE_VALUE;
847 not_guard = fe;
849 new_edge = make_edge (pre_header, exit->dest, flags);
851 /* Determine the probability that we skip the loop. Assume that loop has
852 same average number of iterations regardless outcome of guard. */
853 new_edge->probability = guard->probability;
854 profile_count skip_count = guard->src->count.nonzero_p ()
855 ? guard->count ().apply_scale (pre_header->count,
856 guard->src->count)
857 : guard->count ().apply_probability (new_edge->probability);
859 if (skip_count > e->count ())
861 fprintf (dump_file, " Capping count; expect profile inconsistency\n");
862 skip_count = e->count ();
864 if (dump_file && (dump_flags & TDF_DETAILS))
866 fprintf (dump_file, " Estimated probability of skipping loop is ");
867 new_edge->probability.dump (dump_file);
868 fprintf (dump_file, "\n");
871 /* Update profile after the transform:
873 First decrease count of path from newly hoisted loop guard
874 to loop header... */
875 e->probability = new_edge->probability.invert ();
876 e->dest->count = e->count ();
878 /* ... now update profile to represent that original guard will be optimized
879 away ... */
880 guard->probability = profile_probability::never ();
881 not_guard->probability = profile_probability::always ();
883 /* ... finally scale everything in the loop except for guarded basic blocks
884 where profile does not change. */
885 basic_block *body = get_loop_body (loop);
887 if (dump_file && (dump_flags & TDF_DETAILS))
888 fprintf (dump_file, " Scaling nonguarded BBs in loop:");
889 for (unsigned int i = 0; i < loop->num_nodes; i++)
891 basic_block bb = body[i];
892 if (!dominated_by_p (CDI_DOMINATORS, bb, not_guard->dest))
894 if (dump_file && (dump_flags & TDF_DETAILS))
895 fprintf (dump_file, " %i", bb->index);
896 if (e->probability.initialized_p ())
897 scale_bbs_frequencies (&bb, 1, e->probability);
901 if (fix_dom_of_exit)
902 set_immediate_dominator (CDI_DOMINATORS, exit->dest, pre_header);
903 /* Add NEW_ADGE argument for all phi in post-header block. */
904 bb = exit->dest;
905 for (gphi_iterator gsi = gsi_start_phis (bb);
906 !gsi_end_p (gsi); gsi_next (&gsi))
908 gphi *phi = gsi.phi ();
909 tree arg;
910 if (virtual_operand_p (gimple_phi_result (phi)))
912 arg = get_vop_from_header (loop);
913 if (arg == NULL_TREE)
914 /* Use exit edge argument. */
915 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
916 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
918 else
920 /* Use exit edge argument. */
921 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
922 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
926 if (dump_file && (dump_flags & TDF_DETAILS))
927 fprintf (dump_file, "\n guard hoisted.\n");
929 free (body);
932 /* Return true if phi argument for exit edge can be used
933 for edge around loop. */
935 static bool
936 check_exit_phi (class loop *loop)
938 edge exit = single_exit (loop);
939 basic_block pre_header = loop_preheader_edge (loop)->src;
941 for (gphi_iterator gsi = gsi_start_phis (exit->dest);
942 !gsi_end_p (gsi); gsi_next (&gsi))
944 gphi *phi = gsi.phi ();
945 tree arg;
946 gimple *def;
947 basic_block def_bb;
948 if (virtual_operand_p (gimple_phi_result (phi)))
949 continue;
950 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
951 if (TREE_CODE (arg) != SSA_NAME)
952 continue;
953 def = SSA_NAME_DEF_STMT (arg);
954 if (!def)
955 continue;
956 def_bb = gimple_bb (def);
957 if (!def_bb)
958 continue;
959 if (!dominated_by_p (CDI_DOMINATORS, pre_header, def_bb))
960 /* Definition inside loop! */
961 return false;
962 /* Check loop closed phi invariant. */
963 if (!flow_bb_inside_loop_p (def_bb->loop_father, pre_header))
964 return false;
966 return true;
969 /* Loop unswitching pass. */
971 namespace {
973 const pass_data pass_data_tree_unswitch =
975 GIMPLE_PASS, /* type */
976 "unswitch", /* name */
977 OPTGROUP_LOOP, /* optinfo_flags */
978 TV_TREE_LOOP_UNSWITCH, /* tv_id */
979 PROP_cfg, /* properties_required */
980 0, /* properties_provided */
981 0, /* properties_destroyed */
982 0, /* todo_flags_start */
983 0, /* todo_flags_finish */
986 class pass_tree_unswitch : public gimple_opt_pass
988 public:
989 pass_tree_unswitch (gcc::context *ctxt)
990 : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
993 /* opt_pass methods: */
994 virtual bool gate (function *) { return flag_unswitch_loops != 0; }
995 virtual unsigned int execute (function *);
997 }; // class pass_tree_unswitch
999 unsigned int
1000 pass_tree_unswitch::execute (function *fun)
1002 if (number_of_loops (fun) <= 1)
1003 return 0;
1005 return tree_ssa_unswitch_loops ();
1008 } // anon namespace
1010 gimple_opt_pass *
1011 make_pass_tree_unswitch (gcc::context *ctxt)
1013 return new pass_tree_unswitch (ctxt);