1 /* Loop unswitching.
2 Copyright (C) 2004-2016 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
9 later version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
19
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "tree.h"
25 #include "gimple.h"
26 #include "tree-pass.h"
27 #include "ssa.h"
28 #include "fold-const.h"
29 #include "gimplify.h"
30 #include "tree-cfg.h"
31 #include "tree-ssa.h"
32 #include "tree-ssa-loop-niter.h"
33 #include "tree-ssa-loop.h"
34 #include "tree-into-ssa.h"
35 #include "cfgloop.h"
36 #include "params.h"
37 #include "tree-inline.h"
38 #include "gimple-iterator.h"
39 #include "cfghooks.h"
40
41 /* This file implements the loop unswitching, i.e. transformation of loops like
42
43 while (A)
44 {
45 if (inv)
46 B;
47
48 X;
49
50 if (!inv)
51 C;
52 }
53
54 where inv is the loop invariant, into
55
56 if (inv)
57 {
58 while (A)
59 {
60 B;
61 X;
62 }
63 }
64 else
65 {
66 while (A)
67 {
68 X;
69 C;
70 }
71 }
72
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. */
76
77 static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree);
78 static bool tree_unswitch_single_loop (struct loop *, int);
79 static tree tree_may_unswitch_on (basic_block, struct loop *);
80 static bool tree_unswitch_outer_loop (struct loop *);
81 static edge find_loop_guard (struct loop *);
82 static bool empty_bb_without_guard_p (struct loop *, basic_block);
83 static bool used_outside_loop_p (struct loop *, tree);
84 static void hoist_guard (struct loop *, edge);
85 static bool check_exit_phi (struct loop *);
86 static tree get_vop_from_header (struct loop *);
87
88 /* Main entry point. Perform loop unswitching on all suitable loops. */
89
90 unsigned int
tree_ssa_unswitch_loops(void)91 tree_ssa_unswitch_loops (void)
92 {
93 struct loop *loop;
94 bool changed = false;
95
96 /* Go through all loops starting from innermost. */
97 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
98 {
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);
104 }
105
106 if (changed)
107 return TODO_cleanup_cfg;
108 return 0;
109 }
110
111 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
112 basic blocks (for what it means see comments below). */
113
114 static tree
tree_may_unswitch_on(basic_block bb,struct loop * loop)115 tree_may_unswitch_on (basic_block bb, struct loop *loop)
116 {
117 gimple *last, *def;
118 gcond *stmt;
119 tree cond, use;
120 basic_block def_bb;
121 ssa_op_iter iter;
122
123 /* BB must end in a simple conditional jump. */
124 last = last_stmt (bb);
125 if (!last || gimple_code (last) != GIMPLE_COND)
126 return NULL_TREE;
127 stmt = as_a <gcond *> (last);
128
129 /* To keep the things simple, we do not directly remove the conditions,
130 but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite
131 loop where we would unswitch again on such a condition. */
132 if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt))
133 return NULL_TREE;
134
135 /* Condition must be invariant. */
136 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
137 {
138 /* Unswitching on undefined values would introduce undefined
139 behavior that the original program might never exercise. */
140 if (ssa_undefined_value_p (use, true))
141 return NULL_TREE;
142 def = SSA_NAME_DEF_STMT (use);
143 def_bb = gimple_bb (def);
144 if (def_bb
145 && flow_bb_inside_loop_p (loop, def_bb))
146 return NULL_TREE;
147 }
148
149 cond = build2 (gimple_cond_code (stmt), boolean_type_node,
150 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
151
152 return cond;
153 }
154
155 /* Simplifies COND using checks in front of the entry of the LOOP. Just very
156 simplish (sufficient to prevent us from duplicating loop in unswitching
157 unnecessarily). */
158
159 static tree
simplify_using_entry_checks(struct loop * loop,tree cond)160 simplify_using_entry_checks (struct loop *loop, tree cond)
161 {
162 edge e = loop_preheader_edge (loop);
163 gimple *stmt;
164
165 while (1)
166 {
167 stmt = last_stmt (e->src);
168 if (stmt
169 && gimple_code (stmt) == GIMPLE_COND
170 && gimple_cond_code (stmt) == TREE_CODE (cond)
171 && operand_equal_p (gimple_cond_lhs (stmt),
172 TREE_OPERAND (cond, 0), 0)
173 && operand_equal_p (gimple_cond_rhs (stmt),
174 TREE_OPERAND (cond, 1), 0))
175 return (e->flags & EDGE_TRUE_VALUE
176 ? boolean_true_node
177 : boolean_false_node);
178
179 if (!single_pred_p (e->src))
180 return cond;
181
182 e = single_pred_edge (e->src);
183 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
184 return cond;
185 }
186 }
187
188 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow
189 it to grow too much, it is too easy to create example on that the code would
190 grow exponentially. */
191
192 static bool
tree_unswitch_single_loop(struct loop * loop,int num)193 tree_unswitch_single_loop (struct loop *loop, int num)
194 {
195 basic_block *bbs;
196 struct loop *nloop;
197 unsigned i, found;
198 tree cond = NULL_TREE;
199 gimple *stmt;
200 bool changed = false;
201 HOST_WIDE_INT iterations;
202
203 /* Perform initial tests if unswitch is eligible. */
204 if (num == 0)
205 {
206 /* Do not unswitch in cold regions. */
207 if (optimize_loop_for_size_p (loop))
208 {
209 if (dump_file && (dump_flags & TDF_DETAILS))
210 fprintf (dump_file, ";; Not unswitching cold loops\n");
211 return false;
212 }
213
214 /* The loop should not be too large, to limit code growth. */
215 if (tree_num_loop_insns (loop, &eni_size_weights)
216 > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
217 {
218 if (dump_file && (dump_flags & TDF_DETAILS))
219 fprintf (dump_file, ";; Not unswitching, loop too big\n");
220 return false;
221 }
222
223 /* If the loop is not expected to iterate, there is no need
224 for unswitching. */
225 iterations = estimated_loop_iterations_int (loop);
226 if (iterations >= 0 && iterations <= 1)
227 {
228 if (dump_file && (dump_flags & TDF_DETAILS))
229 fprintf (dump_file, ";; Not unswitching, loop is not expected"
230 " to iterate\n");
231 return false;
232 }
233 }
234
235 i = 0;
236 bbs = get_loop_body (loop);
237 found = loop->num_nodes;
238
239 while (1)
240 {
241 /* Find a bb to unswitch on. */
242 for (; i < loop->num_nodes; i++)
243 if ((cond = tree_may_unswitch_on (bbs[i], loop)))
244 break;
245
246 if (i == loop->num_nodes)
247 {
248 if (dump_file
249 && num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)
250 && (dump_flags & TDF_DETAILS))
251 fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
252
253 if (found == loop->num_nodes)
254 {
255 free (bbs);
256 return changed;
257 }
258 break;
259 }
260
261 cond = simplify_using_entry_checks (loop, cond);
262 stmt = last_stmt (bbs[i]);
263 if (integer_nonzerop (cond))
264 {
265 /* Remove false path. */
266 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
267 boolean_true_node);
268 changed = true;
269 }
270 else if (integer_zerop (cond))
271 {
272 /* Remove true path. */
273 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
274 boolean_false_node);
275 changed = true;
276 }
277 /* Do not unswitch too much. */
278 else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
279 {
280 i++;
281 continue;
282 }
283 /* In nested tree_unswitch_single_loop first optimize all conditions
284 using entry checks, then discover still reachable blocks in the
285 loop and find the condition only among those still reachable bbs. */
286 else if (num != 0)
287 {
288 if (found == loop->num_nodes)
289 found = i;
290 i++;
291 continue;
292 }
293 else
294 {
295 found = i;
296 break;
297 }
298
299 update_stmt (stmt);
300 i++;
301 }
302
303 if (num != 0)
304 {
305 basic_block *tos, *worklist;
306
307 /* When called recursively, first do a quick discovery
308 of reachable bbs after the above changes and only
309 consider conditions in still reachable bbs. */
310 tos = worklist = XNEWVEC (basic_block, loop->num_nodes);
311
312 for (i = 0; i < loop->num_nodes; i++)
313 bbs[i]->flags &= ~BB_REACHABLE;
314
315 /* Start with marking header. */
316 *tos++ = bbs[0];
317 bbs[0]->flags |= BB_REACHABLE;
318
319 /* Iterate: find everything reachable from what we've already seen
320 within the same innermost loop. Don't look through false edges
321 if condition is always true or true edges if condition is
322 always false. */
323 while (tos != worklist)
324 {
325 basic_block b = *--tos;
326 edge e;
327 edge_iterator ei;
328 int flags = 0;
329
330 if (EDGE_COUNT (b->succs) == 2)
331 {
332 gimple *stmt = last_stmt (b);
333 if (stmt
334 && gimple_code (stmt) == GIMPLE_COND)
335 {
336 gcond *cond_stmt = as_a <gcond *> (stmt);
337 if (gimple_cond_true_p (cond_stmt))
338 flags = EDGE_FALSE_VALUE;
339 else if (gimple_cond_false_p (cond_stmt))
340 flags = EDGE_TRUE_VALUE;
341 }
342 }
343
344 FOR_EACH_EDGE (e, ei, b->succs)
345 {
346 basic_block dest = e->dest;
347
348 if (dest->loop_father == loop
349 && !(dest->flags & BB_REACHABLE)
350 && !(e->flags & flags))
351 {
352 *tos++ = dest;
353 dest->flags |= BB_REACHABLE;
354 }
355 }
356 }
357
358 free (worklist);
359
360 /* Find a bb to unswitch on. */
361 for (; found < loop->num_nodes; found++)
362 if ((bbs[found]->flags & BB_REACHABLE)
363 && (cond = tree_may_unswitch_on (bbs[found], loop)))
364 break;
365
366 if (found == loop->num_nodes)
367 {
368 free (bbs);
369 return changed;
370 }
371 }
372
373 if (dump_file && (dump_flags & TDF_DETAILS))
374 fprintf (dump_file, ";; Unswitching loop\n");
375
376 initialize_original_copy_tables ();
377 /* Unswitch the loop on this condition. */
378 nloop = tree_unswitch_loop (loop, bbs[found], cond);
379 if (!nloop)
380 {
381 free_original_copy_tables ();
382 free (bbs);
383 return changed;
384 }
385
386 /* Update the SSA form after unswitching. */
387 update_ssa (TODO_update_ssa);
388 free_original_copy_tables ();
389
390 /* Invoke itself on modified loops. */
391 tree_unswitch_single_loop (nloop, num + 1);
392 tree_unswitch_single_loop (loop, num + 1);
393 free (bbs);
394 return true;
395 }
396
397 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
398 unswitching of innermost loops. COND is the condition determining which
399 loop is entered -- the new loop is entered if COND is true. Returns NULL
400 if impossible, new loop otherwise. */
401
402 static struct loop *
tree_unswitch_loop(struct loop * loop,basic_block unswitch_on,tree cond)403 tree_unswitch_loop (struct loop *loop,
404 basic_block unswitch_on, tree cond)
405 {
406 unsigned prob_true;
407 edge edge_true, edge_false;
408
409 /* Some sanity checking. */
410 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
411 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
412 gcc_assert (loop->inner == NULL);
413
414 extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
415 prob_true = edge_true->probability;
416 return loop_version (loop, unshare_expr (cond),
417 NULL, prob_true, prob_true,
418 REG_BR_PROB_BASE - prob_true, false);
419 }
420
421 /* Unswitch outer loops by hoisting invariant guard on
422 inner loop without code duplication. */
423 static bool
tree_unswitch_outer_loop(struct loop * loop)424 tree_unswitch_outer_loop (struct loop *loop)
425 {
426 edge exit, guard;
427 HOST_WIDE_INT iterations;
428
429 gcc_assert (loop->inner);
430 if (loop->inner->next)
431 return false;
432 /* Accept loops with single exit only which is not from inner loop. */
433 exit = single_exit (loop);
434 if (!exit || exit->src->loop_father != loop)
435 return false;
436 /* Check that phi argument of exit edge is not defined inside loop. */
437 if (!check_exit_phi (loop))
438 return false;
439 /* If the loop is not expected to iterate, there is no need
440 for unswitching. */
441 iterations = estimated_loop_iterations_int (loop);
442 if (iterations >= 0 && iterations <= 1)
443 {
444 if (dump_file && (dump_flags & TDF_DETAILS))
445 fprintf (dump_file, ";; Not unswitching, loop is not expected"
446 " to iterate\n");
447 return false;
448 }
449
450 guard = find_loop_guard (loop);
451 if (guard)
452 {
453 hoist_guard (loop, guard);
454 update_ssa (TODO_update_ssa);
455 return true;
456 }
457 return false;
458 }
459
460 /* Checks if the body of the LOOP is within an invariant guard. If this
461 is the case, returns the edge that jumps over the real body of the loop,
462 otherwise returns NULL. */
463
464 static edge
find_loop_guard(struct loop * loop)465 find_loop_guard (struct loop *loop)
466 {
467 basic_block header = loop->header;
468 edge guard_edge, te, fe;
469 basic_block *body = NULL;
470 unsigned i;
471 tree use;
472 ssa_op_iter iter;
473
474 /* We check for the following situation:
475
476 while (1)
477 {
478 [header]]
479 loop_phi_nodes;
480 something1;
481 if (cond1)
482 body;
483 nvar = phi(orig, bvar) ... for all variables changed in body;
484 [guard_end]
485 something2;
486 if (cond2)
487 break;
488 something3;
489 }
490
491 where:
492
493 1) cond1 is loop invariant
494 2) If cond1 is false, then the loop is essentially empty; i.e.,
495 a) nothing in something1, something2 and something3 has side
496 effects
497 b) anything defined in something1, something2 and something3
498 is not used outside of the loop. */
499
500 while (single_succ_p (header))
501 header = single_succ (header);
502 if (!last_stmt (header)
503 || gimple_code (last_stmt (header)) != GIMPLE_COND)
504 return NULL;
505
506 extract_true_false_edges_from_block (header, &te, &fe);
507 if (!flow_bb_inside_loop_p (loop, te->dest)
508 || !flow_bb_inside_loop_p (loop, fe->dest))
509 return NULL;
510
511 if (just_once_each_iteration_p (loop, te->dest)
512 || (single_succ_p (te->dest)
513 && just_once_each_iteration_p (loop, single_succ (te->dest))))
514 {
515 if (just_once_each_iteration_p (loop, fe->dest))
516 return NULL;
517 guard_edge = te;
518 }
519 else if (just_once_each_iteration_p (loop, fe->dest)
520 || (single_succ_p (fe->dest)
521 && just_once_each_iteration_p (loop, single_succ (fe->dest))))
522 guard_edge = fe;
523 else
524 return NULL;
525
526 /* Guard edge must skip inner loop. */
527 if (!dominated_by_p (CDI_DOMINATORS, loop->inner->header,
528 guard_edge == fe ? te->dest : fe->dest))
529 {
530 if (dump_file && (dump_flags & TDF_DETAILS))
531 fprintf (dump_file, "Guard edge %d --> %d is not around the loop!\n",
532 guard_edge->src->index, guard_edge->dest->index);
533 return NULL;
534 }
535 if (guard_edge->dest == loop->latch)
536 {
537 if (dump_file && (dump_flags & TDF_DETAILS))
538 fprintf (dump_file, "Guard edge destination is loop latch.\n");
539 return NULL;
540 }
541
542 if (dump_file && (dump_flags & TDF_DETAILS))
543 fprintf (dump_file,
544 "Considering guard %d -> %d in loop %d\n",
545 guard_edge->src->index, guard_edge->dest->index, loop->num);
546 /* Check if condition operands do not have definitions inside loop since
547 any bb copying is not performed. */
548 FOR_EACH_SSA_TREE_OPERAND (use, last_stmt (header), iter, SSA_OP_USE)
549 {
550 gimple *def = SSA_NAME_DEF_STMT (use);
551 basic_block def_bb = gimple_bb (def);
552 if (def_bb
553 && flow_bb_inside_loop_p (loop, def_bb))
554 {
555 if (dump_file && (dump_flags & TDF_DETAILS))
556 fprintf (dump_file, " guard operands have definitions"
557 " inside loop\n");
558 return NULL;
559 }
560 }
561
562 body = get_loop_body (loop);
563 for (i = 0; i < loop->num_nodes; i++)
564 {
565 basic_block bb = body[i];
566 if (bb->loop_father != loop)
567 continue;
568 if (bb->flags & BB_IRREDUCIBLE_LOOP)
569 {
570 if (dump_file && (dump_flags & TDF_DETAILS))
571 fprintf (dump_file, "Block %d is marked as irreducible in loop\n",
572 bb->index);
573 guard_edge = NULL;
574 goto end;
575 }
576 if (!empty_bb_without_guard_p (loop, bb))
577 {
578 if (dump_file && (dump_flags & TDF_DETAILS))
579 fprintf (dump_file, " block %d has side effects\n", bb->index);
580 guard_edge = NULL;
581 goto end;
582 }
583 }
584
585 if (dump_file && (dump_flags & TDF_DETAILS))
586 fprintf (dump_file, " suitable to hoist\n");
587 end:
588 if (body)
589 free (body);
590 return guard_edge;
591 }
592
593 /* Returns true if
594 1) no statement in BB has side effects
595 2) assuming that edge GUARD is always taken, all definitions in BB
596 are noy used outside of the loop.
597 KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
598 PROCESSED is a set of ssa names for that we already tested whether they
599 are invariant or not. */
600
601 static bool
empty_bb_without_guard_p(struct loop * loop,basic_block bb)602 empty_bb_without_guard_p (struct loop *loop, basic_block bb)
603 {
604 basic_block exit_bb = single_exit (loop)->src;
605 bool may_be_used_outside = (bb == exit_bb
606 || !dominated_by_p (CDI_DOMINATORS, bb, exit_bb));
607 tree name;
608 ssa_op_iter op_iter;
609
610 /* Phi nodes do not have side effects, but their results might be used
611 outside of the loop. */
612 if (may_be_used_outside)
613 {
614 for (gphi_iterator gsi = gsi_start_phis (bb);
615 !gsi_end_p (gsi); gsi_next (&gsi))
616 {
617 gphi *phi = gsi.phi ();
618 name = PHI_RESULT (phi);
619 if (virtual_operand_p (name))
620 continue;
621
622 if (used_outside_loop_p (loop, name))
623 return false;
624 }
625 }
626
627 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
628 !gsi_end_p (gsi); gsi_next (&gsi))
629 {
630 gimple *stmt = gsi_stmt (gsi);
631 if (gimple_has_side_effects (stmt))
632 return false;
633
634 if (gimple_vdef(stmt))
635 return false;
636
637 FOR_EACH_SSA_TREE_OPERAND (name, stmt, op_iter, SSA_OP_DEF)
638 {
639 if (may_be_used_outside
640 && used_outside_loop_p (loop, name))
641 return false;
642 }
643 }
644 return true;
645 }
646
647 /* Return true if NAME is used outside of LOOP. */
648
649 static bool
used_outside_loop_p(struct loop * loop,tree name)650 used_outside_loop_p (struct loop *loop, tree name)
651 {
652 imm_use_iterator it;
653 use_operand_p use;
654
655 FOR_EACH_IMM_USE_FAST (use, it, name)
656 {
657 gimple *stmt = USE_STMT (use);
658 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
659 return true;
660 }
661
662 return false;
663 }
664
665 /* Return argument for loop preheader edge in header virtual phi if any. */
666
667 static tree
get_vop_from_header(struct loop * loop)668 get_vop_from_header (struct loop *loop)
669 {
670 for (gphi_iterator gsi = gsi_start_phis (loop->header);
671 !gsi_end_p (gsi); gsi_next (&gsi))
672 {
673 gphi *phi = gsi.phi ();
674 if (!virtual_operand_p (gimple_phi_result (phi)))
675 continue;
676 return PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
677 }
678 return NULL_TREE;
679 }
680
681 /* Move the check of GUARD outside of LOOP. */
682
683 static void
hoist_guard(struct loop * loop,edge guard)684 hoist_guard (struct loop *loop, edge guard)
685 {
686 edge exit = single_exit (loop);
687 edge preh = loop_preheader_edge (loop);
688 basic_block pre_header = preh->src;
689 basic_block bb;
690 edge te, fe, e, new_edge;
691 gimple *stmt;
692 basic_block guard_bb = guard->src;
693 gimple_stmt_iterator gsi;
694 int flags = 0;
695 bool fix_dom_of_exit;
696 gcond *cond_stmt, *new_cond_stmt;
697
698 bb = get_immediate_dominator (CDI_DOMINATORS, exit->dest);
699 fix_dom_of_exit = flow_bb_inside_loop_p (loop, bb);
700 gsi = gsi_last_bb (guard_bb);
701 stmt = gsi_stmt (gsi);
702 gcc_assert (gimple_code (stmt) == GIMPLE_COND);
703 cond_stmt = as_a <gcond *> (stmt);
704 extract_true_false_edges_from_block (guard_bb, &te, &fe);
705 /* Insert guard to PRE_HEADER. */
706 if (!empty_block_p (pre_header))
707 gsi = gsi_last_bb (pre_header);
708 else
709 gsi = gsi_start_bb (pre_header);
710 /* Create copy of COND_STMT. */
711 new_cond_stmt = gimple_build_cond (gimple_cond_code (cond_stmt),
712 gimple_cond_lhs (cond_stmt),
713 gimple_cond_rhs (cond_stmt),
714 NULL_TREE, NULL_TREE);
715 gsi_insert_after (&gsi, new_cond_stmt, GSI_NEW_STMT);
716 /* Convert COND_STMT to true/false conditional. */
717 if (guard == te)
718 gimple_cond_make_false (cond_stmt);
719 else
720 gimple_cond_make_true (cond_stmt);
721 update_stmt (cond_stmt);
722 /* Create new loop pre-header. */
723 e = split_block (pre_header, last_stmt (pre_header));
724 gcc_assert (loop_preheader_edge (loop)->src == e->dest);
725 if (guard == fe)
726 {
727 e->flags = EDGE_TRUE_VALUE;
728 flags |= EDGE_FALSE_VALUE;
729 }
730 else
731 {
732 e->flags = EDGE_FALSE_VALUE;
733 flags |= EDGE_TRUE_VALUE;
734 }
735 new_edge = make_edge (pre_header, exit->dest, flags);
736 if (fix_dom_of_exit)
737 set_immediate_dominator (CDI_DOMINATORS, exit->dest, pre_header);
738 /* Add NEW_ADGE argument for all phi in post-header block. */
739 bb = exit->dest;
740 for (gphi_iterator gsi = gsi_start_phis (bb);
741 !gsi_end_p (gsi); gsi_next (&gsi))
742 {
743 gphi *phi = gsi.phi ();
744 tree arg;
745 if (virtual_operand_p (gimple_phi_result (phi)))
746 {
747 arg = get_vop_from_header (loop);
748 if (arg == NULL_TREE)
749 /* Use exit edge argument. */
750 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
751 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
752 }
753 else
754 {
755 /* Use exit edge argument. */
756 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
757 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
758 }
759 }
760
761 mark_virtual_operands_for_renaming (cfun);
762 update_ssa (TODO_update_ssa);
763 if (dump_file && (dump_flags & TDF_DETAILS))
764 fprintf (dump_file, " guard hoisted.\n");
765 }
766
767 /* Return true if phi argument for exit edge can be used
768 for edge around loop. */
769
770 static bool
check_exit_phi(struct loop * loop)771 check_exit_phi (struct loop *loop)
772 {
773 edge exit = single_exit (loop);
774 basic_block pre_header = loop_preheader_edge (loop)->src;
775
776 for (gphi_iterator gsi = gsi_start_phis (exit->dest);
777 !gsi_end_p (gsi); gsi_next (&gsi))
778 {
779 gphi *phi = gsi.phi ();
780 tree arg;
781 gimple *def;
782 basic_block def_bb;
783 if (virtual_operand_p (gimple_phi_result (phi)))
784 continue;
785 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
786 if (TREE_CODE (arg) != SSA_NAME)
787 continue;
788 def = SSA_NAME_DEF_STMT (arg);
789 if (!def)
790 continue;
791 def_bb = gimple_bb (def);
792 if (!def_bb)
793 continue;
794 if (!dominated_by_p (CDI_DOMINATORS, pre_header, def_bb))
795 /* Definition inside loop! */
796 return false;
797 /* Check loop closed phi invariant. */
798 if (!flow_bb_inside_loop_p (def_bb->loop_father, pre_header))
799 return false;
800 }
801 return true;
802 }
803
804 /* Loop unswitching pass. */
805
806 namespace {
807
808 const pass_data pass_data_tree_unswitch =
809 {
810 GIMPLE_PASS, /* type */
811 "unswitch", /* name */
812 OPTGROUP_LOOP, /* optinfo_flags */
813 TV_TREE_LOOP_UNSWITCH, /* tv_id */
814 PROP_cfg, /* properties_required */
815 0, /* properties_provided */
816 0, /* properties_destroyed */
817 0, /* todo_flags_start */
818 0, /* todo_flags_finish */
819 };
820
821 class pass_tree_unswitch : public gimple_opt_pass
822 {
823 public:
pass_tree_unswitch(gcc::context * ctxt)824 pass_tree_unswitch (gcc::context *ctxt)
825 : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
826 {}
827
828 /* opt_pass methods: */
gate(function *)829 virtual bool gate (function *) { return flag_unswitch_loops != 0; }
830 virtual unsigned int execute (function *);
831
832 }; // class pass_tree_unswitch
833
834 unsigned int
execute(function * fun)835 pass_tree_unswitch::execute (function *fun)
836 {
837 if (number_of_loops (fun) <= 1)
838 return 0;
839
840 return tree_ssa_unswitch_loops ();
841 }
842
843 } // anon namespace
844
845 gimple_opt_pass *
make_pass_tree_unswitch(gcc::context * ctxt)846 make_pass_tree_unswitch (gcc::context *ctxt)
847 {
848 return new pass_tree_unswitch (ctxt);
849 }
850
851
852