comparison gcc/tree-ssa-loop-unswitch.c @ 16:04ced10e8804

gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents f6334be47118
children 84e7813d76e9
comparison
equal deleted inserted replaced
15:561a7518be6b 16:04ced10e8804
1 /* Loop unswitching. 1 /* Loop unswitching.
2 Copyright (C) 2004, 2005, 2007, 2008, 2010 Free Software Foundation, Inc. 2 Copyright (C) 2004-2017 Free Software Foundation, Inc.
3 3
4 This file is part of GCC. 4 This file is part of GCC.
5 5
6 GCC is free software; you can redistribute it and/or modify it 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 7 under the terms of the GNU General Public License as published by the
18 <http://www.gnu.org/licenses/>. */ 18 <http://www.gnu.org/licenses/>. */
19 19
20 #include "config.h" 20 #include "config.h"
21 #include "system.h" 21 #include "system.h"
22 #include "coretypes.h" 22 #include "coretypes.h"
23 #include "tm.h" 23 #include "backend.h"
24 #include "tree.h" 24 #include "tree.h"
25 #include "tm_p.h" 25 #include "gimple.h"
26 #include "basic-block.h" 26 #include "tree-pass.h"
27 #include "output.h" 27 #include "ssa.h"
28 #include "tree-flow.h" 28 #include "fold-const.h"
29 #include "tree-dump.h" 29 #include "gimplify.h"
30 #include "timevar.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"
31 #include "cfgloop.h" 35 #include "cfgloop.h"
32 #include "params.h" 36 #include "params.h"
33 #include "tree-pass.h"
34 #include "tree-inline.h" 37 #include "tree-inline.h"
38 #include "gimple-iterator.h"
39 #include "cfghooks.h"
40 #include "tree-ssa-loop-manip.h"
35 41
36 /* This file implements the loop unswitching, i.e. transformation of loops like 42 /* This file implements the loop unswitching, i.e. transformation of loops like
37 43
38 while (A) 44 while (A)
39 { 45 {
70 shape. */ 76 shape. */
71 77
72 static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree); 78 static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree);
73 static bool tree_unswitch_single_loop (struct loop *, int); 79 static bool tree_unswitch_single_loop (struct loop *, int);
74 static tree tree_may_unswitch_on (basic_block, struct loop *); 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 *);
75 88
76 /* Main entry point. Perform loop unswitching on all suitable loops. */ 89 /* Main entry point. Perform loop unswitching on all suitable loops. */
77 90
78 unsigned int 91 unsigned int
79 tree_ssa_unswitch_loops (void) 92 tree_ssa_unswitch_loops (void)
80 { 93 {
81 loop_iterator li;
82 struct loop *loop; 94 struct loop *loop;
83 bool changed = false; 95 bool changed = false;
84 96
85 /* Go through inner loops (only original ones). */ 97 /* Go through all loops starting from innermost. */
86 FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST) 98 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
87 { 99 {
88 if (dump_file && (dump_flags & TDF_DETAILS)) 100 if (!loop->inner)
89 fprintf (dump_file, ";; Considering loop %d\n", loop->num); 101 /* Unswitch innermost loop. */
90 102 changed |= tree_unswitch_single_loop (loop, 0);
91 /* Do not unswitch in cold regions. */ 103 else
92 if (optimize_loop_for_size_p (loop)) 104 changed |= tree_unswitch_outer_loop (loop);
93 {
94 if (dump_file && (dump_flags & TDF_DETAILS))
95 fprintf (dump_file, ";; Not unswitching cold loops\n");
96 continue;
97 }
98
99 /* The loop should not be too large, to limit code growth. */
100 if (tree_num_loop_insns (loop, &eni_size_weights)
101 > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
102 {
103 if (dump_file && (dump_flags & TDF_DETAILS))
104 fprintf (dump_file, ";; Not unswitching, loop too big\n");
105 continue;
106 }
107
108 changed |= tree_unswitch_single_loop (loop, 0);
109 } 105 }
110 106
111 if (changed) 107 if (changed)
112 return TODO_cleanup_cfg; 108 return TODO_cleanup_cfg;
113 return 0; 109 return 0;
114 } 110 }
115 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
117 is_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
116 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its 186 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
117 basic blocks (for what it means see comments below). */ 187 basic blocks (for what it means see comments below). */
118 188
119 static tree 189 static tree
120 tree_may_unswitch_on (basic_block bb, struct loop *loop) 190 tree_may_unswitch_on (basic_block bb, struct loop *loop)
121 { 191 {
122 gimple stmt, def; 192 gimple *last, *def;
193 gcond *stmt;
123 tree cond, use; 194 tree cond, use;
124 basic_block def_bb; 195 basic_block def_bb;
125 ssa_op_iter iter; 196 ssa_op_iter iter;
126 197
127 /* BB must end in a simple conditional jump. */ 198 /* BB must end in a simple conditional jump. */
128 stmt = last_stmt (bb); 199 last = last_stmt (bb);
129 if (!stmt || gimple_code (stmt) != GIMPLE_COND) 200 if (!last || gimple_code (last) != GIMPLE_COND)
130 return NULL_TREE; 201 return NULL_TREE;
202 stmt = as_a <gcond *> (last);
131 203
132 /* To keep the things simple, we do not directly remove the conditions, 204 /* To keep the things simple, we do not directly remove the conditions,
133 but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite 205 but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite
134 loop where we would unswitch again on such a condition. */ 206 loop where we would unswitch again on such a condition. */
135 if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt)) 207 if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt))
141 def = SSA_NAME_DEF_STMT (use); 213 def = SSA_NAME_DEF_STMT (use);
142 def_bb = gimple_bb (def); 214 def_bb = gimple_bb (def);
143 if (def_bb 215 if (def_bb
144 && flow_bb_inside_loop_p (loop, def_bb)) 216 && flow_bb_inside_loop_p (loop, def_bb))
145 return NULL_TREE; 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;
146 } 222 }
147 223
148 cond = build2 (gimple_cond_code (stmt), boolean_type_node, 224 cond = build2 (gimple_cond_code (stmt), boolean_type_node,
149 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); 225 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
150 226
157 233
158 static tree 234 static tree
159 simplify_using_entry_checks (struct loop *loop, tree cond) 235 simplify_using_entry_checks (struct loop *loop, tree cond)
160 { 236 {
161 edge e = loop_preheader_edge (loop); 237 edge e = loop_preheader_edge (loop);
162 gimple stmt; 238 gimple *stmt;
163 239
164 while (1) 240 while (1)
165 { 241 {
166 stmt = last_stmt (e->src); 242 stmt = last_stmt (e->src);
167 if (stmt 243 if (stmt
177 253
178 if (!single_pred_p (e->src)) 254 if (!single_pred_p (e->src))
179 return cond; 255 return cond;
180 256
181 e = single_pred_edge (e->src); 257 e = single_pred_edge (e->src);
182 if (e->src == ENTRY_BLOCK_PTR) 258 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
183 return cond; 259 return cond;
184 } 260 }
185 } 261 }
186 262
187 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow 263 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow
193 { 269 {
194 basic_block *bbs; 270 basic_block *bbs;
195 struct loop *nloop; 271 struct loop *nloop;
196 unsigned i, found; 272 unsigned i, found;
197 tree cond = NULL_TREE; 273 tree cond = NULL_TREE;
198 gimple stmt; 274 gimple *stmt;
199 bool changed = false; 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 }
200 311
201 i = 0; 312 i = 0;
202 bbs = get_loop_body (loop); 313 bbs = get_loop_body (loop);
203 found = loop->num_nodes; 314 found = loop->num_nodes;
204 315
227 cond = simplify_using_entry_checks (loop, cond); 338 cond = simplify_using_entry_checks (loop, cond);
228 stmt = last_stmt (bbs[i]); 339 stmt = last_stmt (bbs[i]);
229 if (integer_nonzerop (cond)) 340 if (integer_nonzerop (cond))
230 { 341 {
231 /* Remove false path. */ 342 /* Remove false path. */
232 gimple_cond_set_condition_from_tree (stmt, boolean_true_node); 343 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
344 boolean_true_node);
233 changed = true; 345 changed = true;
234 } 346 }
235 else if (integer_zerop (cond)) 347 else if (integer_zerop (cond))
236 { 348 {
237 /* Remove true path. */ 349 /* Remove true path. */
238 gimple_cond_set_condition_from_tree (stmt, boolean_false_node); 350 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
351 boolean_false_node);
239 changed = true; 352 changed = true;
240 } 353 }
241 /* Do not unswitch too much. */ 354 /* Do not unswitch too much. */
242 else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)) 355 else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
243 { 356 {
291 edge_iterator ei; 404 edge_iterator ei;
292 int flags = 0; 405 int flags = 0;
293 406
294 if (EDGE_COUNT (b->succs) == 2) 407 if (EDGE_COUNT (b->succs) == 2)
295 { 408 {
296 gimple stmt = last_stmt (b); 409 gimple *stmt = last_stmt (b);
297 if (stmt 410 if (stmt
298 && gimple_code (stmt) == GIMPLE_COND) 411 && gimple_code (stmt) == GIMPLE_COND)
299 { 412 {
300 if (gimple_cond_true_p (stmt)) 413 gcond *cond_stmt = as_a <gcond *> (stmt);
414 if (gimple_cond_true_p (cond_stmt))
301 flags = EDGE_FALSE_VALUE; 415 flags = EDGE_FALSE_VALUE;
302 else if (gimple_cond_false_p (stmt)) 416 else if (gimple_cond_false_p (cond_stmt))
303 flags = EDGE_TRUE_VALUE; 417 flags = EDGE_TRUE_VALUE;
304 } 418 }
305 } 419 }
306 420
307 FOR_EACH_EDGE (e, ei, b->succs) 421 FOR_EACH_EDGE (e, ei, b->succs)
364 478
365 static struct loop * 479 static struct loop *
366 tree_unswitch_loop (struct loop *loop, 480 tree_unswitch_loop (struct loop *loop,
367 basic_block unswitch_on, tree cond) 481 basic_block unswitch_on, tree cond)
368 { 482 {
369 unsigned prob_true; 483 profile_probability prob_true;
370 edge edge_true, edge_false; 484 edge edge_true, edge_false;
371 485
372 /* Some sanity checking. */ 486 /* Some sanity checking. */
373 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on)); 487 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
374 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2); 488 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
375 gcc_assert (loop->inner == NULL); 489 gcc_assert (loop->inner == NULL);
376 490
377 extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false); 491 extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
378 prob_true = edge_true->probability; 492 prob_true = edge_true->probability;
379 return loop_version (loop, unshare_expr (cond), 493 return loop_version (loop, unshare_expr (cond),
380 NULL, prob_true, prob_true, 494 NULL, prob_true,
381 REG_BR_PROB_BASE - prob_true, false); 495 prob_true.invert (),
382 } 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. */
502 static bool
503 tree_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
546 static edge
547 find_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");
689 end:
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
703 static bool
704 empty_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
751 static bool
752 used_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
769 static tree
770 get_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
785 static void
786 hoist_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 > 0
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 e->dest->frequency = EDGE_FREQUENCY (e);
879
880 /* ... now update profile to represent that original guard will be optimized
881 away ... */
882 guard->probability = profile_probability::never ();
883 not_guard->probability = profile_probability::always ();
884
885 /* ... finally scale everything in the loop except for guarded basic blocks
886 where profile does not change. */
887 basic_block *body = get_loop_body (loop);
888
889 if (dump_file && (dump_flags & TDF_DETAILS))
890 fprintf (dump_file, " Scaling nonguarded BBs in loop:");
891 for (unsigned int i = 0; i < loop->num_nodes; i++)
892 {
893 basic_block bb = body[i];
894 if (!dominated_by_p (CDI_DOMINATORS, bb, not_guard->dest))
895 {
896 if (dump_file && (dump_flags & TDF_DETAILS))
897 fprintf (dump_file, " %i", bb->index);
898 if (e->probability.initialized_p ())
899 scale_bbs_frequencies (&bb, 1, e->probability);
900 }
901 }
902
903 if (fix_dom_of_exit)
904 set_immediate_dominator (CDI_DOMINATORS, exit->dest, pre_header);
905 /* Add NEW_ADGE argument for all phi in post-header block. */
906 bb = exit->dest;
907 for (gphi_iterator gsi = gsi_start_phis (bb);
908 !gsi_end_p (gsi); gsi_next (&gsi))
909 {
910 gphi *phi = gsi.phi ();
911 tree arg;
912 if (virtual_operand_p (gimple_phi_result (phi)))
913 {
914 arg = get_vop_from_header (loop);
915 if (arg == NULL_TREE)
916 /* Use exit edge argument. */
917 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
918 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
919 }
920 else
921 {
922 /* Use exit edge argument. */
923 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
924 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
925 }
926 }
927
928 if (dump_file && (dump_flags & TDF_DETAILS))
929 fprintf (dump_file, "\n guard hoisted.\n");
930
931 free (body);
932 }
933
934 /* Return true if phi argument for exit edge can be used
935 for edge around loop. */
936
937 static bool
938 check_exit_phi (struct loop *loop)
939 {
940 edge exit = single_exit (loop);
941 basic_block pre_header = loop_preheader_edge (loop)->src;
942
943 for (gphi_iterator gsi = gsi_start_phis (exit->dest);
944 !gsi_end_p (gsi); gsi_next (&gsi))
945 {
946 gphi *phi = gsi.phi ();
947 tree arg;
948 gimple *def;
949 basic_block def_bb;
950 if (virtual_operand_p (gimple_phi_result (phi)))
951 continue;
952 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
953 if (TREE_CODE (arg) != SSA_NAME)
954 continue;
955 def = SSA_NAME_DEF_STMT (arg);
956 if (!def)
957 continue;
958 def_bb = gimple_bb (def);
959 if (!def_bb)
960 continue;
961 if (!dominated_by_p (CDI_DOMINATORS, pre_header, def_bb))
962 /* Definition inside loop! */
963 return false;
964 /* Check loop closed phi invariant. */
965 if (!flow_bb_inside_loop_p (def_bb->loop_father, pre_header))
966 return false;
967 }
968 return true;
969 }
970
971 /* Loop unswitching pass. */
972
973 namespace {
974
975 const pass_data pass_data_tree_unswitch =
976 {
977 GIMPLE_PASS, /* type */
978 "unswitch", /* name */
979 OPTGROUP_LOOP, /* optinfo_flags */
980 TV_TREE_LOOP_UNSWITCH, /* tv_id */
981 PROP_cfg, /* properties_required */
982 0, /* properties_provided */
983 0, /* properties_destroyed */
984 0, /* todo_flags_start */
985 0, /* todo_flags_finish */
986 };
987
988 class pass_tree_unswitch : public gimple_opt_pass
989 {
990 public:
991 pass_tree_unswitch (gcc::context *ctxt)
992 : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
993 {}
994
995 /* opt_pass methods: */
996 virtual bool gate (function *) { return flag_unswitch_loops != 0; }
997 virtual unsigned int execute (function *);
998
999 }; // class pass_tree_unswitch
1000
1001 unsigned int
1002 pass_tree_unswitch::execute (function *fun)
1003 {
1004 if (number_of_loops (fun) <= 1)
1005 return 0;
1006
1007 return tree_ssa_unswitch_loops ();
1008 }
1009
1010 } // anon namespace
1011
1012 gimple_opt_pass *
1013 make_pass_tree_unswitch (gcc::context *ctxt)
1014 {
1015 return new pass_tree_unswitch (ctxt);
1016 }
1017
1018