1/* Loop unswitching.
2 Copyright (C) 2004-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it
7under the terms of the GNU General Public License as published by the
8Free Software Foundation; either version 3, or (at your option) any
9later version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT
12ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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 "params.h"
37#include "tree-inline.h"
38#include "gimple-iterator.h"
39#include "cfghooks.h"
40#include "tree-ssa-loop-manip.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.c ensures that all the suitable conditions are in this
76 shape. */
77
78static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree);
79static bool tree_unswitch_single_loop (struct loop *, int);
80static tree tree_may_unswitch_on (basic_block, struct loop *);
81static bool tree_unswitch_outer_loop (struct loop *);
82static edge find_loop_guard (struct loop *);
83static bool empty_bb_without_guard_p (struct loop *, basic_block);
84static bool used_outside_loop_p (struct loop *, tree);
85static void hoist_guard (struct loop *, edge);
86static bool check_exit_phi (struct loop *);
87static tree get_vop_from_header (struct loop *);
88
89/* Main entry point. Perform loop unswitching on all suitable loops. */
90
91unsigned int
92tree_ssa_unswitch_loops (void)
93{
94 struct loop *loop;
95 bool changed = false;
96
97 /* Go through all loops starting from innermost. */
98 FOR_EACH_LOOP (loop, 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
116static bool
117is_maybe_undefined (const tree name, gimple *stmt, struct 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
189static tree
190tree_may_unswitch_on (basic_block bb, struct 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
234static tree
235simplify_using_entry_checks (struct 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
267static bool
268tree_unswitch_single_loop (struct loop *loop, int num)
269{
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;
277
278 /* Perform initial tests if unswitch is eligible. */
279 if (num == 0)
280 {
281 /* Do not unswitch in cold regions. */
282 if (optimize_loop_for_size_p (loop))
283 {
284 if (dump_file && (dump_flags & TDF_DETAILS))
285 fprintf (dump_file, ";; Not unswitching cold loops\n");
286 return false;
287 }
288
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))
292 {
293 if (dump_file && (dump_flags & TDF_DETAILS))
294 fprintf (dump_file, ";; Not unswitching, loop too big\n");
295 return false;
296 }
297
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)
304 {
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;
309 }
310 }
311
312 i = 0;
313 bbs = get_loop_body (loop);
314 found = loop->num_nodes;
315
316 while (1)
317 {
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;
322
323 if (i == loop->num_nodes)
324 {
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");
329
330 if (found == loop->num_nodes)
331 {
332 free (bbs);
333 return changed;
334 }
335 break;
336 }
337
338 cond = simplify_using_entry_checks (loop, cond);
339 stmt = last_stmt (bbs[i]);
340 if (integer_nonzerop (cond))
341 {
342 /* Remove false path. */
343 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
344 boolean_true_node);
345 changed = true;
346 }
347 else if (integer_zerop (cond))
348 {
349 /* Remove true path. */
350 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
351 boolean_false_node);
352 changed = true;
353 }
354 /* Do not unswitch too much. */
355 else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
356 {
357 i++;
358 continue;
359 }
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)
364 {
365 if (found == loop->num_nodes)
366 found = i;
367 i++;
368 continue;
369 }
370 else
371 {
372 found = i;
373 break;
374 }
375
376 update_stmt (stmt);
377 i++;
378 }
379
380 if (num != 0)
381 {
382 basic_block *tos, *worklist;
383
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);
388
389 for (i = 0; i < loop->num_nodes; i++)
390 bbs[i]->flags &= ~BB_REACHABLE;
391
392 /* Start with marking header. */
393 *tos++ = bbs[0];
394 bbs[0]->flags |= BB_REACHABLE;
395
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)
401 {
402 basic_block b = *--tos;
403 edge e;
404 edge_iterator ei;
405 int flags = 0;
406
407 if (EDGE_COUNT (b->succs) == 2)
408 {
409 gimple *stmt = last_stmt (b);
410 if (stmt
411 && gimple_code (stmt) == GIMPLE_COND)
412 {
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;
418 }
419 }
420
421 FOR_EACH_EDGE (e, ei, b->succs)
422 {
423 basic_block dest = e->dest;
424
425 if (dest->loop_father == loop
426 && !(dest->flags & BB_REACHABLE)
427 && !(e->flags & flags))
428 {
429 *tos++ = dest;
430 dest->flags |= BB_REACHABLE;
431 }
432 }
433 }
434
435 free (worklist);
436
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;
442
443 if (found == loop->num_nodes)
444 {
445 free (bbs);
446 return changed;
447 }
448 }
449
450 if (dump_file && (dump_flags & TDF_DETAILS))
451 fprintf (dump_file, ";; Unswitching loop\n");
452
453 initialize_original_copy_tables ();
454 /* Unswitch the loop on this condition. */
455 nloop = tree_unswitch_loop (loop, bbs[found], cond);
456 if (!nloop)
457 {
458 free_original_copy_tables ();
459 free (bbs);
460 return changed;
461 }
462
463 /* Update the SSA form after unswitching. */
464 update_ssa (TODO_update_ssa);
465 free_original_copy_tables ();
466
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;
472}
473
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. */
478
479static struct loop *
480tree_unswitch_loop (struct loop *loop,
481 basic_block unswitch_on, tree cond)
482{
483 profile_probability prob_true;
484 edge edge_true, edge_false;
485
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);
490
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);
498}
499
500/* Unswitch outer loops by hoisting invariant guard on
501 inner loop without code duplication. */
502static bool
503tree_unswitch_outer_loop (struct loop *loop)
504{
505 edge exit, guard;
506 HOST_WIDE_INT iterations;
507
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)
524 {
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;
529 }
530
531 bool changed = false;
532 while ((guard = find_loop_guard (loop)))
533 {
534 if (! changed)
535 rewrite_virtuals_into_loop_closed_ssa (loop);
536 hoist_guard (loop, guard);
537 changed = true;
538 }
539 return changed;
540}
541
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. */
545
546static edge
547find_loop_guard (struct loop *loop)
548{
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;
555
556 /* We check for the following situation:
557
558 while (1)
559 {
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;
571 }
572
573 where:
574
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. */
581
582 gcond *cond;
583 do
584 {
585 basic_block next = NULL;
586 if (single_succ_p (header))
587 next = single_succ (header);
588 else
589 {
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;
602 }
603 /* Never traverse a backedge. */
604 if (header->loop_father->header == next)
605 return NULL;
606 header = next;
607 }
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;
612
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))))
616 {
617 if (just_once_each_iteration_p (loop, fe->dest))
618 return NULL;
619 guard_edge = te;
620 }
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;
627
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))
631 {
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;
636 }
637 if (guard_edge->dest == loop->latch)
638 {
639 if (dump_file && (dump_flags & TDF_DETAILS))
640 fprintf (dump_file, "Guard edge destination is loop latch.\n");
641 return NULL;
642 }
643
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)
651 {
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))
656 {
657 if (dump_file && (dump_flags & TDF_DETAILS))
658 fprintf (dump_file, " guard operands have definitions"
659 " inside loop\n");
660 return NULL;
661 }
662 }
663
664 body = get_loop_body (loop);
665 for (i = 0; i < loop->num_nodes; i++)
666 {
667 basic_block bb = body[i];
668 if (bb->loop_father != loop)
669 continue;
670 if (bb->flags & BB_IRREDUCIBLE_LOOP)
671 {
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;
677 }
678 if (!empty_bb_without_guard_p (loop, bb))
679 {
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;
684 }
685 }
686
687 if (dump_file && (dump_flags & TDF_DETAILS))
688 fprintf (dump_file, " suitable to hoist\n");
689end:
690 if (body)
691 free (body);
692 return guard_edge;
693}
694
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. */
702
703static bool
704empty_bb_without_guard_p (struct loop *loop, basic_block bb)
705{
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;
711
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)
715 {
716 for (gphi_iterator gsi = gsi_start_phis (bb);
717 !gsi_end_p (gsi); gsi_next (&gsi))
718 {
719 gphi *phi = gsi.phi ();
720 name = PHI_RESULT (phi);
721 if (virtual_operand_p (name))
722 continue;
723
724 if (used_outside_loop_p (loop, name))
725 return false;
726 }
727 }
728
729 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
730 !gsi_end_p (gsi); gsi_next (&gsi))
731 {
732 gimple *stmt = gsi_stmt (gsi);
733 if (gimple_has_side_effects (stmt))
734 return false;
735
736 if (gimple_vdef(stmt))
737 return false;
738
739 FOR_EACH_SSA_TREE_OPERAND (name, stmt, op_iter, SSA_OP_DEF)
740 {
741 if (may_be_used_outside
742 && used_outside_loop_p (loop, name))
743 return false;
744 }
745 }
746 return true;
747}
748
749/* Return true if NAME is used outside of LOOP. */
750
751static bool
752used_outside_loop_p (struct loop *loop, tree name)
753{
754 imm_use_iterator it;
755 use_operand_p use;
756
757 FOR_EACH_IMM_USE_FAST (use, it, name)
758 {
759 gimple *stmt = USE_STMT (use);
760 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
761 return true;
762 }
763
764 return false;
765}
766
767/* Return argument for loop preheader edge in header virtual phi if any. */
768
769static tree
770get_vop_from_header (struct loop *loop)
771{
772 for (gphi_iterator gsi = gsi_start_phis (loop->header);
773 !gsi_end_p (gsi); gsi_next (&gsi))
774 {
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));
779 }
780 return NULL_TREE;
781}
782
783/* Move the check of GUARD outside of LOOP. */
784
785static void
786hoist_guard (struct loop *loop, edge guard)
787{
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;
800
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))
828 {
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);
834 }
835
836 gcc_assert (loop_preheader_edge (loop)->src == e->dest);
837
838 if (guard == fe)
839 {
840 e->flags = EDGE_TRUE_VALUE;
841 flags |= EDGE_FALSE_VALUE;
842 not_guard = te;
843 }
844 else
845 {
846 e->flags = EDGE_FALSE_VALUE;
847 flags |= EDGE_TRUE_VALUE;
848 not_guard = fe;
849 }
850 new_edge = make_edge (pre_header, exit->dest, flags);
851
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);
859
860 if (skip_count > e->count ())
861 {
862 fprintf (dump_file, " Capping count; expect profile inconsistency\n");
863 skip_count = e->count ();
864 }
865 if (dump_file && (dump_flags & TDF_DETAILS))
866 {
867 fprintf (dump_file, " Estimated probability of skipping loop is ");
868 new_edge->probability.dump (dump_file);
869 fprintf (dump_file, "\n");
870 }
871
872 /* Update profile after the transform:
873
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 ();
878
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 ();
883
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);
887
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++)
891 {
892 basic_block bb = body[i];
893 if (!dominated_by_p (CDI_DOMINATORS, bb, not_guard->dest))
894 {
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);
899 }
900 }
901
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))
908 {
909 gphi *phi = gsi.phi ();
910 tree arg;
911 if (virtual_operand_p (gimple_phi_result (phi)))
912 {
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);
918 }
919 else
920 {
921 /* Use exit edge argument. */
922 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
923 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
924 }
925 }
926
927 if (dump_file && (dump_flags & TDF_DETAILS))
928 fprintf (dump_file, "\n guard hoisted.\n");
929
930 free (body);
931}
932
933/* Return true if phi argument for exit edge can be used
934 for edge around loop. */
935
936static bool
937check_exit_phi (struct loop *loop)
938{
939 edge exit = single_exit (loop);
940 basic_block pre_header = loop_preheader_edge (loop)->src;
941
942 for (gphi_iterator gsi = gsi_start_phis (exit->dest);
943 !gsi_end_p (gsi); gsi_next (&gsi))
944 {
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;
966 }
967 return true;
968}
969
970/* Loop unswitching pass. */
971
972namespace {
973
974const pass_data pass_data_tree_unswitch =
975{
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 */
985};
986
987class pass_tree_unswitch : public gimple_opt_pass
988{
989public:
990 pass_tree_unswitch (gcc::context *ctxt)
991 : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
992 {}
993
994 /* opt_pass methods: */
995 virtual bool gate (function *) { return flag_unswitch_loops != 0; }
996 virtual unsigned int execute (function *);
997
998}; // class pass_tree_unswitch
999
1000unsigned int
1001pass_tree_unswitch::execute (function *fun)
1002{
1003 if (number_of_loops (fun) <= 1)
1004 return 0;
1005
1006 return tree_ssa_unswitch_loops ();
1007}
1008
1009} // anon namespace
1010
1011gimple_opt_pass *
1012make_pass_tree_unswitch (gcc::context *ctxt)
1013{
1014 return new pass_tree_unswitch (ctxt);
1015}
1016
1017
1018