PR tree-optimization/85699
[official-gcc.git] / gcc / tree-ssa-loop-unswitch.c
blob711c1cd316f9e9f05e1a8ba94104d6bbe37834e1
1 /* Loop unswitching.
2 Copyright (C) 2004-2018 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 "params.h"
37 #include "tree-inline.h"
38 #include "gimple-iterator.h"
39 #include "cfghooks.h"
40 #include "tree-ssa-loop-manip.h"
42 /* This file implements the loop unswitching, i.e. transformation of loops like
44 while (A)
46 if (inv)
51 if (!inv)
55 where inv is the loop invariant, into
57 if (inv)
59 while (A)
65 else
67 while (A)
74 Inv is considered invariant iff the values it compares are both invariant;
75 tree-ssa-loop-im.c ensures that all the suitable conditions are in this
76 shape. */
78 static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree);
79 static bool tree_unswitch_single_loop (struct loop *, int);
80 static tree tree_may_unswitch_on (basic_block, struct loop *);
81 static bool tree_unswitch_outer_loop (struct loop *);
82 static edge find_loop_guard (struct loop *);
83 static bool empty_bb_without_guard_p (struct loop *, basic_block);
84 static bool used_outside_loop_p (struct loop *, tree);
85 static void hoist_guard (struct loop *, edge);
86 static bool check_exit_phi (struct loop *);
87 static tree get_vop_from_header (struct loop *);
89 /* Main entry point. Perform loop unswitching on all suitable loops. */
91 unsigned int
92 tree_ssa_unswitch_loops (void)
94 struct loop *loop;
95 bool changed = false;
97 /* Go through all loops starting from innermost. */
98 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
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);
107 if (changed)
108 return TODO_cleanup_cfg;
109 return 0;
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. */
116 static bool
117 is_maybe_undefined (const tree name, gimple *stmt, struct loop *loop)
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;
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 ())
131 tree t = worklist.pop ();
133 /* If it's obviously undefined, avoid further computations. */
134 if (ssa_undefined_value_p (t, true))
135 return true;
137 if (ssa_defined_default_def_p (t))
138 continue;
140 gimple *def = SSA_NAME_DEF_STMT (t);
142 /* Check that all the PHI args are fully defined. */
143 if (gphi *phi = dyn_cast <gphi *> (def))
145 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
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);
155 continue;
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;
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;
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)
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);
183 return false;
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). */
189 static tree
190 tree_may_unswitch_on (basic_block bb, struct loop *loop)
192 gimple *last, *def;
193 gcond *stmt;
194 tree cond, use;
195 basic_block def_bb;
196 ssa_op_iter iter;
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);
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;
210 /* Condition must be invariant. */
211 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
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;
224 cond = build2 (gimple_cond_code (stmt), boolean_type_node,
225 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
227 return cond;
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). */
234 static tree
235 simplify_using_entry_checks (struct loop *loop, tree cond)
237 edge e = loop_preheader_edge (loop);
238 gimple *stmt;
240 while (1)
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);
254 if (!single_pred_p (e->src))
255 return cond;
257 e = single_pred_edge (e->src);
258 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
259 return cond;
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. */
267 static bool
268 tree_unswitch_single_loop (struct loop *loop, int num)
270 basic_block *bbs;
271 struct loop *nloop;
272 unsigned i, found;
273 tree cond = NULL_TREE;
274 gimple *stmt;
275 bool changed = false;
276 HOST_WIDE_INT iterations;
278 /* Perform initial tests if unswitch is eligible. */
279 if (num == 0)
281 /* Do not unswitch in cold regions. */
282 if (optimize_loop_for_size_p (loop))
284 if (dump_file && (dump_flags & TDF_DETAILS))
285 fprintf (dump_file, ";; Not unswitching cold loops\n");
286 return false;
289 /* The loop should not be too large, to limit code growth. */
290 if (tree_num_loop_insns (loop, &eni_size_weights)
291 > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
293 if (dump_file && (dump_flags & TDF_DETAILS))
294 fprintf (dump_file, ";; Not unswitching, loop too big\n");
295 return false;
298 /* If the loop is not expected to iterate, there is no need
299 for unswitching. */
300 iterations = estimated_loop_iterations_int (loop);
301 if (iterations < 0)
302 iterations = likely_max_loop_iterations_int (loop);
303 if (iterations >= 0 && iterations <= 1)
305 if (dump_file && (dump_flags & TDF_DETAILS))
306 fprintf (dump_file, ";; Not unswitching, loop is not expected"
307 " to iterate\n");
308 return false;
312 i = 0;
313 bbs = get_loop_body (loop);
314 found = loop->num_nodes;
316 while (1)
318 /* Find a bb to unswitch on. */
319 for (; i < loop->num_nodes; i++)
320 if ((cond = tree_may_unswitch_on (bbs[i], loop)))
321 break;
323 if (i == loop->num_nodes)
325 if (dump_file
326 && num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)
327 && (dump_flags & TDF_DETAILS))
328 fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
330 if (found == loop->num_nodes)
332 free (bbs);
333 return changed;
335 break;
338 cond = simplify_using_entry_checks (loop, cond);
339 stmt = last_stmt (bbs[i]);
340 if (integer_nonzerop (cond))
342 /* Remove false path. */
343 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
344 boolean_true_node);
345 changed = true;
347 else if (integer_zerop (cond))
349 /* Remove true path. */
350 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
351 boolean_false_node);
352 changed = true;
354 /* Do not unswitch too much. */
355 else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
357 i++;
358 continue;
360 /* In nested tree_unswitch_single_loop first optimize all conditions
361 using entry checks, then discover still reachable blocks in the
362 loop and find the condition only among those still reachable bbs. */
363 else if (num != 0)
365 if (found == loop->num_nodes)
366 found = i;
367 i++;
368 continue;
370 else
372 found = i;
373 break;
376 update_stmt (stmt);
377 i++;
380 if (num != 0)
382 basic_block *tos, *worklist;
384 /* When called recursively, first do a quick discovery
385 of reachable bbs after the above changes and only
386 consider conditions in still reachable bbs. */
387 tos = worklist = XNEWVEC (basic_block, loop->num_nodes);
389 for (i = 0; i < loop->num_nodes; i++)
390 bbs[i]->flags &= ~BB_REACHABLE;
392 /* Start with marking header. */
393 *tos++ = bbs[0];
394 bbs[0]->flags |= BB_REACHABLE;
396 /* Iterate: find everything reachable from what we've already seen
397 within the same innermost loop. Don't look through false edges
398 if condition is always true or true edges if condition is
399 always false. */
400 while (tos != worklist)
402 basic_block b = *--tos;
403 edge e;
404 edge_iterator ei;
405 int flags = 0;
407 if (EDGE_COUNT (b->succs) == 2)
409 gimple *stmt = last_stmt (b);
410 if (stmt
411 && gimple_code (stmt) == GIMPLE_COND)
413 gcond *cond_stmt = as_a <gcond *> (stmt);
414 if (gimple_cond_true_p (cond_stmt))
415 flags = EDGE_FALSE_VALUE;
416 else if (gimple_cond_false_p (cond_stmt))
417 flags = EDGE_TRUE_VALUE;
421 FOR_EACH_EDGE (e, ei, b->succs)
423 basic_block dest = e->dest;
425 if (dest->loop_father == loop
426 && !(dest->flags & BB_REACHABLE)
427 && !(e->flags & flags))
429 *tos++ = dest;
430 dest->flags |= BB_REACHABLE;
435 free (worklist);
437 /* Find a bb to unswitch on. */
438 for (; found < loop->num_nodes; found++)
439 if ((bbs[found]->flags & BB_REACHABLE)
440 && (cond = tree_may_unswitch_on (bbs[found], loop)))
441 break;
443 if (found == loop->num_nodes)
445 free (bbs);
446 return changed;
450 if (dump_file && (dump_flags & TDF_DETAILS))
451 fprintf (dump_file, ";; Unswitching loop\n");
453 initialize_original_copy_tables ();
454 /* Unswitch the loop on this condition. */
455 nloop = tree_unswitch_loop (loop, bbs[found], cond);
456 if (!nloop)
458 free_original_copy_tables ();
459 free (bbs);
460 return changed;
463 /* Update the SSA form after unswitching. */
464 update_ssa (TODO_update_ssa);
465 free_original_copy_tables ();
467 /* Invoke itself on modified loops. */
468 tree_unswitch_single_loop (nloop, num + 1);
469 tree_unswitch_single_loop (loop, num + 1);
470 free (bbs);
471 return true;
474 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
475 unswitching of innermost loops. COND is the condition determining which
476 loop is entered -- the new loop is entered if COND is true. Returns NULL
477 if impossible, new loop otherwise. */
479 static struct loop *
480 tree_unswitch_loop (struct loop *loop,
481 basic_block unswitch_on, tree cond)
483 profile_probability prob_true;
484 edge edge_true, edge_false;
486 /* Some sanity checking. */
487 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
488 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
489 gcc_assert (loop->inner == NULL);
491 extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
492 prob_true = edge_true->probability;
493 return loop_version (loop, unshare_expr (cond),
494 NULL, prob_true,
495 prob_true.invert (),
496 prob_true, prob_true.invert (),
497 false);
500 /* Unswitch outer loops by hoisting invariant guard on
501 inner loop without code duplication. */
502 static bool
503 tree_unswitch_outer_loop (struct loop *loop)
505 edge exit, guard;
506 HOST_WIDE_INT iterations;
508 gcc_assert (loop->inner);
509 if (loop->inner->next)
510 return false;
511 /* Accept loops with single exit only which is not from inner loop. */
512 exit = single_exit (loop);
513 if (!exit || exit->src->loop_father != loop)
514 return false;
515 /* Check that phi argument of exit edge is not defined inside loop. */
516 if (!check_exit_phi (loop))
517 return false;
518 /* If the loop is not expected to iterate, there is no need
519 for unswitching. */
520 iterations = estimated_loop_iterations_int (loop);
521 if (iterations < 0)
522 iterations = likely_max_loop_iterations_int (loop);
523 if (iterations >= 0 && iterations <= 1)
525 if (dump_file && (dump_flags & TDF_DETAILS))
526 fprintf (dump_file, ";; Not unswitching, loop is not expected"
527 " to iterate\n");
528 return false;
531 bool changed = false;
532 while ((guard = find_loop_guard (loop)))
534 if (! changed)
535 rewrite_virtuals_into_loop_closed_ssa (loop);
536 hoist_guard (loop, guard);
537 changed = true;
539 return changed;
542 /* Checks if the body of the LOOP is within an invariant guard. If this
543 is the case, returns the edge that jumps over the real body of the loop,
544 otherwise returns NULL. */
546 static edge
547 find_loop_guard (struct loop *loop)
549 basic_block header = loop->header;
550 edge guard_edge, te, fe;
551 basic_block *body = NULL;
552 unsigned i;
553 tree use;
554 ssa_op_iter iter;
556 /* We check for the following situation:
558 while (1)
560 [header]]
561 loop_phi_nodes;
562 something1;
563 if (cond1)
564 body;
565 nvar = phi(orig, bvar) ... for all variables changed in body;
566 [guard_end]
567 something2;
568 if (cond2)
569 break;
570 something3;
573 where:
575 1) cond1 is loop invariant
576 2) If cond1 is false, then the loop is essentially empty; i.e.,
577 a) nothing in something1, something2 and something3 has side
578 effects
579 b) anything defined in something1, something2 and something3
580 is not used outside of the loop. */
582 gcond *cond;
585 basic_block next = NULL;
586 if (single_succ_p (header))
587 next = single_succ (header);
588 else
590 cond = dyn_cast <gcond *> (last_stmt (header));
591 if (! cond)
592 return NULL;
593 extract_true_false_edges_from_block (header, &te, &fe);
594 /* Make sure to skip earlier hoisted guards that are left
595 in place as if (true). */
596 if (gimple_cond_true_p (cond))
597 next = te->dest;
598 else if (gimple_cond_false_p (cond))
599 next = fe->dest;
600 else
601 break;
603 /* Never traverse a backedge. */
604 if (header->loop_father->header == next)
605 return NULL;
606 header = next;
608 while (1);
609 if (!flow_bb_inside_loop_p (loop, te->dest)
610 || !flow_bb_inside_loop_p (loop, fe->dest))
611 return NULL;
613 if (just_once_each_iteration_p (loop, te->dest)
614 || (single_succ_p (te->dest)
615 && just_once_each_iteration_p (loop, single_succ (te->dest))))
617 if (just_once_each_iteration_p (loop, fe->dest))
618 return NULL;
619 guard_edge = te;
621 else if (just_once_each_iteration_p (loop, fe->dest)
622 || (single_succ_p (fe->dest)
623 && just_once_each_iteration_p (loop, single_succ (fe->dest))))
624 guard_edge = fe;
625 else
626 return NULL;
628 /* Guard edge must skip inner loop. */
629 if (!dominated_by_p (CDI_DOMINATORS, loop->inner->header,
630 guard_edge == fe ? te->dest : fe->dest))
632 if (dump_file && (dump_flags & TDF_DETAILS))
633 fprintf (dump_file, "Guard edge %d --> %d is not around the loop!\n",
634 guard_edge->src->index, guard_edge->dest->index);
635 return NULL;
637 if (guard_edge->dest == loop->latch)
639 if (dump_file && (dump_flags & TDF_DETAILS))
640 fprintf (dump_file, "Guard edge destination is loop latch.\n");
641 return NULL;
644 if (dump_file && (dump_flags & TDF_DETAILS))
645 fprintf (dump_file,
646 "Considering guard %d -> %d in loop %d\n",
647 guard_edge->src->index, guard_edge->dest->index, loop->num);
648 /* Check if condition operands do not have definitions inside loop since
649 any bb copying is not performed. */
650 FOR_EACH_SSA_TREE_OPERAND (use, cond, iter, SSA_OP_USE)
652 gimple *def = SSA_NAME_DEF_STMT (use);
653 basic_block def_bb = gimple_bb (def);
654 if (def_bb
655 && flow_bb_inside_loop_p (loop, def_bb))
657 if (dump_file && (dump_flags & TDF_DETAILS))
658 fprintf (dump_file, " guard operands have definitions"
659 " inside loop\n");
660 return NULL;
664 body = get_loop_body (loop);
665 for (i = 0; i < loop->num_nodes; i++)
667 basic_block bb = body[i];
668 if (bb->loop_father != loop)
669 continue;
670 if (bb->flags & BB_IRREDUCIBLE_LOOP)
672 if (dump_file && (dump_flags & TDF_DETAILS))
673 fprintf (dump_file, "Block %d is marked as irreducible in loop\n",
674 bb->index);
675 guard_edge = NULL;
676 goto end;
678 if (!empty_bb_without_guard_p (loop, bb))
680 if (dump_file && (dump_flags & TDF_DETAILS))
681 fprintf (dump_file, " block %d has side effects\n", bb->index);
682 guard_edge = NULL;
683 goto end;
687 if (dump_file && (dump_flags & TDF_DETAILS))
688 fprintf (dump_file, " suitable to hoist\n");
689 end:
690 if (body)
691 free (body);
692 return guard_edge;
695 /* Returns true if
696 1) no statement in BB has side effects
697 2) assuming that edge GUARD is always taken, all definitions in BB
698 are noy used outside of the loop.
699 KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
700 PROCESSED is a set of ssa names for that we already tested whether they
701 are invariant or not. */
703 static bool
704 empty_bb_without_guard_p (struct loop *loop, basic_block bb)
706 basic_block exit_bb = single_exit (loop)->src;
707 bool may_be_used_outside = (bb == exit_bb
708 || !dominated_by_p (CDI_DOMINATORS, bb, exit_bb));
709 tree name;
710 ssa_op_iter op_iter;
712 /* Phi nodes do not have side effects, but their results might be used
713 outside of the loop. */
714 if (may_be_used_outside)
716 for (gphi_iterator gsi = gsi_start_phis (bb);
717 !gsi_end_p (gsi); gsi_next (&gsi))
719 gphi *phi = gsi.phi ();
720 name = PHI_RESULT (phi);
721 if (virtual_operand_p (name))
722 continue;
724 if (used_outside_loop_p (loop, name))
725 return false;
729 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
730 !gsi_end_p (gsi); gsi_next (&gsi))
732 gimple *stmt = gsi_stmt (gsi);
733 if (gimple_has_side_effects (stmt))
734 return false;
736 if (gimple_vdef(stmt))
737 return false;
739 FOR_EACH_SSA_TREE_OPERAND (name, stmt, op_iter, SSA_OP_DEF)
741 if (may_be_used_outside
742 && used_outside_loop_p (loop, name))
743 return false;
746 return true;
749 /* Return true if NAME is used outside of LOOP. */
751 static bool
752 used_outside_loop_p (struct loop *loop, tree name)
754 imm_use_iterator it;
755 use_operand_p use;
757 FOR_EACH_IMM_USE_FAST (use, it, name)
759 gimple *stmt = USE_STMT (use);
760 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
761 return true;
764 return false;
767 /* Return argument for loop preheader edge in header virtual phi if any. */
769 static tree
770 get_vop_from_header (struct loop *loop)
772 for (gphi_iterator gsi = gsi_start_phis (loop->header);
773 !gsi_end_p (gsi); gsi_next (&gsi))
775 gphi *phi = gsi.phi ();
776 if (!virtual_operand_p (gimple_phi_result (phi)))
777 continue;
778 return PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
780 return NULL_TREE;
783 /* Move the check of GUARD outside of LOOP. */
785 static void
786 hoist_guard (struct loop *loop, edge guard)
788 edge exit = single_exit (loop);
789 edge preh = loop_preheader_edge (loop);
790 basic_block pre_header = preh->src;
791 basic_block bb;
792 edge te, fe, e, new_edge;
793 gimple *stmt;
794 basic_block guard_bb = guard->src;
795 edge not_guard;
796 gimple_stmt_iterator gsi;
797 int flags = 0;
798 bool fix_dom_of_exit;
799 gcond *cond_stmt, *new_cond_stmt;
801 bb = get_immediate_dominator (CDI_DOMINATORS, exit->dest);
802 fix_dom_of_exit = flow_bb_inside_loop_p (loop, bb);
803 gsi = gsi_last_bb (guard_bb);
804 stmt = gsi_stmt (gsi);
805 gcc_assert (gimple_code (stmt) == GIMPLE_COND);
806 cond_stmt = as_a <gcond *> (stmt);
807 extract_true_false_edges_from_block (guard_bb, &te, &fe);
808 /* Insert guard to PRE_HEADER. */
809 if (!empty_block_p (pre_header))
810 gsi = gsi_last_bb (pre_header);
811 else
812 gsi = gsi_start_bb (pre_header);
813 /* Create copy of COND_STMT. */
814 new_cond_stmt = gimple_build_cond (gimple_cond_code (cond_stmt),
815 gimple_cond_lhs (cond_stmt),
816 gimple_cond_rhs (cond_stmt),
817 NULL_TREE, NULL_TREE);
818 gsi_insert_after (&gsi, new_cond_stmt, GSI_NEW_STMT);
819 /* Convert COND_STMT to true/false conditional. */
820 if (guard == te)
821 gimple_cond_make_false (cond_stmt);
822 else
823 gimple_cond_make_true (cond_stmt);
824 update_stmt (cond_stmt);
825 /* Create new loop pre-header. */
826 e = split_block (pre_header, last_stmt (pre_header));
827 if (dump_file && (dump_flags & TDF_DETAILS))
829 fprintf (dump_file, " Moving guard %i->%i (prob ",
830 guard->src->index, guard->dest->index);
831 guard->probability.dump (dump_file);
832 fprintf (dump_file, ") to bb %i, new preheader is %i\n",
833 e->src->index, e->dest->index);
836 gcc_assert (loop_preheader_edge (loop)->src == e->dest);
838 if (guard == fe)
840 e->flags = EDGE_TRUE_VALUE;
841 flags |= EDGE_FALSE_VALUE;
842 not_guard = te;
844 else
846 e->flags = EDGE_FALSE_VALUE;
847 flags |= EDGE_TRUE_VALUE;
848 not_guard = fe;
850 new_edge = make_edge (pre_header, exit->dest, flags);
852 /* Determine the probability that we skip the loop. Assume that loop has
853 same average number of iterations regardless outcome of guard. */
854 new_edge->probability = guard->probability;
855 profile_count skip_count = guard->src->count.nonzero_p ()
856 ? guard->count ().apply_scale (pre_header->count,
857 guard->src->count)
858 : guard->count ().apply_probability (new_edge->probability);
860 if (skip_count > e->count ())
862 fprintf (dump_file, " Capping count; expect profile inconsistency\n");
863 skip_count = e->count ();
865 if (dump_file && (dump_flags & TDF_DETAILS))
867 fprintf (dump_file, " Estimated probability of skipping loop is ");
868 new_edge->probability.dump (dump_file);
869 fprintf (dump_file, "\n");
872 /* Update profile after the transform:
874 First decrease count of path from newly hoisted loop guard
875 to loop header... */
876 e->probability = new_edge->probability.invert ();
877 e->dest->count = e->count ();
879 /* ... now update profile to represent that original guard will be optimized
880 away ... */
881 guard->probability = profile_probability::never ();
882 not_guard->probability = profile_probability::always ();
884 /* ... finally scale everything in the loop except for guarded basic blocks
885 where profile does not change. */
886 basic_block *body = get_loop_body (loop);
888 if (dump_file && (dump_flags & TDF_DETAILS))
889 fprintf (dump_file, " Scaling nonguarded BBs in loop:");
890 for (unsigned int i = 0; i < loop->num_nodes; i++)
892 basic_block bb = body[i];
893 if (!dominated_by_p (CDI_DOMINATORS, bb, not_guard->dest))
895 if (dump_file && (dump_flags & TDF_DETAILS))
896 fprintf (dump_file, " %i", bb->index);
897 if (e->probability.initialized_p ())
898 scale_bbs_frequencies (&bb, 1, e->probability);
902 if (fix_dom_of_exit)
903 set_immediate_dominator (CDI_DOMINATORS, exit->dest, pre_header);
904 /* Add NEW_ADGE argument for all phi in post-header block. */
905 bb = exit->dest;
906 for (gphi_iterator gsi = gsi_start_phis (bb);
907 !gsi_end_p (gsi); gsi_next (&gsi))
909 gphi *phi = gsi.phi ();
910 tree arg;
911 if (virtual_operand_p (gimple_phi_result (phi)))
913 arg = get_vop_from_header (loop);
914 if (arg == NULL_TREE)
915 /* Use exit edge argument. */
916 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
917 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
919 else
921 /* Use exit edge argument. */
922 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
923 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
927 if (dump_file && (dump_flags & TDF_DETAILS))
928 fprintf (dump_file, "\n guard hoisted.\n");
930 free (body);
933 /* Return true if phi argument for exit edge can be used
934 for edge around loop. */
936 static bool
937 check_exit_phi (struct loop *loop)
939 edge exit = single_exit (loop);
940 basic_block pre_header = loop_preheader_edge (loop)->src;
942 for (gphi_iterator gsi = gsi_start_phis (exit->dest);
943 !gsi_end_p (gsi); gsi_next (&gsi))
945 gphi *phi = gsi.phi ();
946 tree arg;
947 gimple *def;
948 basic_block def_bb;
949 if (virtual_operand_p (gimple_phi_result (phi)))
950 continue;
951 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
952 if (TREE_CODE (arg) != SSA_NAME)
953 continue;
954 def = SSA_NAME_DEF_STMT (arg);
955 if (!def)
956 continue;
957 def_bb = gimple_bb (def);
958 if (!def_bb)
959 continue;
960 if (!dominated_by_p (CDI_DOMINATORS, pre_header, def_bb))
961 /* Definition inside loop! */
962 return false;
963 /* Check loop closed phi invariant. */
964 if (!flow_bb_inside_loop_p (def_bb->loop_father, pre_header))
965 return false;
967 return true;
970 /* Loop unswitching pass. */
972 namespace {
974 const pass_data pass_data_tree_unswitch =
976 GIMPLE_PASS, /* type */
977 "unswitch", /* name */
978 OPTGROUP_LOOP, /* optinfo_flags */
979 TV_TREE_LOOP_UNSWITCH, /* tv_id */
980 PROP_cfg, /* properties_required */
981 0, /* properties_provided */
982 0, /* properties_destroyed */
983 0, /* todo_flags_start */
984 0, /* todo_flags_finish */
987 class pass_tree_unswitch : public gimple_opt_pass
989 public:
990 pass_tree_unswitch (gcc::context *ctxt)
991 : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
994 /* opt_pass methods: */
995 virtual bool gate (function *) { return flag_unswitch_loops != 0; }
996 virtual unsigned int execute (function *);
998 }; // class pass_tree_unswitch
1000 unsigned int
1001 pass_tree_unswitch::execute (function *fun)
1003 if (number_of_loops (fun) <= 1)
1004 return 0;
1006 return tree_ssa_unswitch_loops ();
1009 } // anon namespace
1011 gimple_opt_pass *
1012 make_pass_tree_unswitch (gcc::context *ctxt)
1014 return new pass_tree_unswitch (ctxt);