2 Copyright (C) 2004-2017 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
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
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/>. */
22 #include "coretypes.h"
26 #include "tree-pass.h"
28 #include "fold-const.h"
32 #include "tree-ssa-loop-niter.h"
33 #include "tree-ssa-loop.h"
34 #include "tree-into-ssa.h"
37 #include "tree-inline.h"
38 #include "gimple-iterator.h"
40 #include "tree-ssa-loop-manip.h"
42 /* This file implements the loop unswitching, i.e. transformation of loops like
55 where inv is the loop invariant, into
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
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. */
92 tree_ssa_unswitch_loops (void)
97 /* Go through all loops starting from innermost. */
98 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
101 /* Unswitch innermost loop. */
102 changed
|= tree_unswitch_single_loop (loop
, 0);
104 changed
|= tree_unswitch_outer_loop (loop
);
108 return TODO_cleanup_cfg
;
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. */
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
)
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))
137 if (ssa_defined_default_def_p (t
))
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
);
158 /* Uses in stmts always executed when the region header executes
160 if (dominated_by_p (CDI_DOMINATORS
, loop
->header
, gimple_bb (def
)))
163 /* Handle calls and memory loads conservatively. */
164 if (!is_gimple_assign (def
)
165 || (gimple_assign_single_p (def
)
166 && gimple_vuse (def
)))
169 /* Check that any SSA names used to define NAME are also fully
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
);
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). */
190 tree_may_unswitch_on (basic_block bb
, struct loop
*loop
)
198 /* BB must end in a simple conditional jump. */
199 last
= last_stmt (bb
);
200 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
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
))
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
);
216 && flow_bb_inside_loop_p (loop
, def_bb
))
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
))
224 cond
= build2 (gimple_cond_code (stmt
), boolean_type_node
,
225 gimple_cond_lhs (stmt
), gimple_cond_rhs (stmt
));
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
235 simplify_using_entry_checks (struct loop
*loop
, tree cond
)
237 edge e
= loop_preheader_edge (loop
);
242 stmt
= last_stmt (e
->src
);
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
252 : boolean_false_node
);
254 if (!single_pred_p (e
->src
))
257 e
= single_pred_edge (e
->src
);
258 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
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. */
268 tree_unswitch_single_loop (struct loop
*loop
, int num
)
273 tree cond
= NULL_TREE
;
275 bool changed
= false;
276 HOST_WIDE_INT iterations
;
278 /* Perform initial tests if unswitch is eligible. */
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");
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");
298 /* If the loop is not expected to iterate, there is no need
300 iterations
= estimated_loop_iterations_int (loop
);
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"
313 bbs
= get_loop_body (loop
);
314 found
= loop
->num_nodes
;
318 /* Find a bb to unswitch on. */
319 for (; i
< loop
->num_nodes
; i
++)
320 if ((cond
= tree_may_unswitch_on (bbs
[i
], loop
)))
323 if (i
== loop
->num_nodes
)
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
)
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
),
347 else if (integer_zerop (cond
))
349 /* Remove true path. */
350 gimple_cond_set_condition_from_tree (as_a
<gcond
*> (stmt
),
354 /* Do not unswitch too much. */
355 else if (num
> PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL
))
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. */
365 if (found
== loop
->num_nodes
)
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. */
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
400 while (tos
!= worklist
)
402 basic_block b
= *--tos
;
407 if (EDGE_COUNT (b
->succs
) == 2)
409 gimple
*stmt
= last_stmt (b
);
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
))
430 dest
->flags
|= BB_REACHABLE
;
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
)))
443 if (found
== loop
->num_nodes
)
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
);
458 free_original_copy_tables ();
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);
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. */
480 tree_unswitch_loop (struct loop
*loop
,
481 basic_block unswitch_on
, tree cond
)
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
, REG_BR_PROB_BASE
- prob_true
, prob_true
,
495 REG_BR_PROB_BASE
- prob_true
, false);
498 /* Unswitch outer loops by hoisting invariant guard on
499 inner loop without code duplication. */
501 tree_unswitch_outer_loop (struct loop
*loop
)
504 HOST_WIDE_INT iterations
;
506 gcc_assert (loop
->inner
);
507 if (loop
->inner
->next
)
509 /* Accept loops with single exit only which is not from inner loop. */
510 exit
= single_exit (loop
);
511 if (!exit
|| exit
->src
->loop_father
!= loop
)
513 /* Check that phi argument of exit edge is not defined inside loop. */
514 if (!check_exit_phi (loop
))
516 /* If the loop is not expected to iterate, there is no need
518 iterations
= estimated_loop_iterations_int (loop
);
520 iterations
= likely_max_loop_iterations_int (loop
);
521 if (iterations
>= 0 && iterations
<= 1)
523 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
524 fprintf (dump_file
, ";; Not unswitching, loop is not expected"
529 bool changed
= false;
530 while ((guard
= find_loop_guard (loop
)))
533 rewrite_virtuals_into_loop_closed_ssa (loop
);
534 hoist_guard (loop
, guard
);
540 /* Checks if the body of the LOOP is within an invariant guard. If this
541 is the case, returns the edge that jumps over the real body of the loop,
542 otherwise returns NULL. */
545 find_loop_guard (struct loop
*loop
)
547 basic_block header
= loop
->header
;
548 edge guard_edge
, te
, fe
;
549 basic_block
*body
= NULL
;
554 /* We check for the following situation:
563 nvar = phi(orig, bvar) ... for all variables changed in body;
573 1) cond1 is loop invariant
574 2) If cond1 is false, then the loop is essentially empty; i.e.,
575 a) nothing in something1, something2 and something3 has side
577 b) anything defined in something1, something2 and something3
578 is not used outside of the loop. */
583 if (single_succ_p (header
))
584 header
= single_succ (header
);
587 cond
= dyn_cast
<gcond
*> (last_stmt (header
));
590 extract_true_false_edges_from_block (header
, &te
, &fe
);
591 /* Make sure to skip earlier hoisted guards that are left
592 in place as if (true). */
593 if (gimple_cond_true_p (cond
))
595 else if (gimple_cond_false_p (cond
))
602 if (!flow_bb_inside_loop_p (loop
, te
->dest
)
603 || !flow_bb_inside_loop_p (loop
, fe
->dest
))
606 if (just_once_each_iteration_p (loop
, te
->dest
)
607 || (single_succ_p (te
->dest
)
608 && just_once_each_iteration_p (loop
, single_succ (te
->dest
))))
610 if (just_once_each_iteration_p (loop
, fe
->dest
))
614 else if (just_once_each_iteration_p (loop
, fe
->dest
)
615 || (single_succ_p (fe
->dest
)
616 && just_once_each_iteration_p (loop
, single_succ (fe
->dest
))))
621 /* Guard edge must skip inner loop. */
622 if (!dominated_by_p (CDI_DOMINATORS
, loop
->inner
->header
,
623 guard_edge
== fe
? te
->dest
: fe
->dest
))
625 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
626 fprintf (dump_file
, "Guard edge %d --> %d is not around the loop!\n",
627 guard_edge
->src
->index
, guard_edge
->dest
->index
);
630 if (guard_edge
->dest
== loop
->latch
)
632 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
633 fprintf (dump_file
, "Guard edge destination is loop latch.\n");
637 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
639 "Considering guard %d -> %d in loop %d\n",
640 guard_edge
->src
->index
, guard_edge
->dest
->index
, loop
->num
);
641 /* Check if condition operands do not have definitions inside loop since
642 any bb copying is not performed. */
643 FOR_EACH_SSA_TREE_OPERAND (use
, cond
, iter
, SSA_OP_USE
)
645 gimple
*def
= SSA_NAME_DEF_STMT (use
);
646 basic_block def_bb
= gimple_bb (def
);
648 && flow_bb_inside_loop_p (loop
, def_bb
))
650 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
651 fprintf (dump_file
, " guard operands have definitions"
657 body
= get_loop_body (loop
);
658 for (i
= 0; i
< loop
->num_nodes
; i
++)
660 basic_block bb
= body
[i
];
661 if (bb
->loop_father
!= loop
)
663 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
665 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
666 fprintf (dump_file
, "Block %d is marked as irreducible in loop\n",
671 if (!empty_bb_without_guard_p (loop
, bb
))
673 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
674 fprintf (dump_file
, " block %d has side effects\n", bb
->index
);
680 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
681 fprintf (dump_file
, " suitable to hoist\n");
689 1) no statement in BB has side effects
690 2) assuming that edge GUARD is always taken, all definitions in BB
691 are noy used outside of the loop.
692 KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
693 PROCESSED is a set of ssa names for that we already tested whether they
694 are invariant or not. */
697 empty_bb_without_guard_p (struct loop
*loop
, basic_block bb
)
699 basic_block exit_bb
= single_exit (loop
)->src
;
700 bool may_be_used_outside
= (bb
== exit_bb
701 || !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
));
705 /* Phi nodes do not have side effects, but their results might be used
706 outside of the loop. */
707 if (may_be_used_outside
)
709 for (gphi_iterator gsi
= gsi_start_phis (bb
);
710 !gsi_end_p (gsi
); gsi_next (&gsi
))
712 gphi
*phi
= gsi
.phi ();
713 name
= PHI_RESULT (phi
);
714 if (virtual_operand_p (name
))
717 if (used_outside_loop_p (loop
, name
))
722 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
723 !gsi_end_p (gsi
); gsi_next (&gsi
))
725 gimple
*stmt
= gsi_stmt (gsi
);
726 if (gimple_has_side_effects (stmt
))
729 if (gimple_vdef(stmt
))
732 FOR_EACH_SSA_TREE_OPERAND (name
, stmt
, op_iter
, SSA_OP_DEF
)
734 if (may_be_used_outside
735 && used_outside_loop_p (loop
, name
))
742 /* Return true if NAME is used outside of LOOP. */
745 used_outside_loop_p (struct loop
*loop
, tree name
)
750 FOR_EACH_IMM_USE_FAST (use
, it
, name
)
752 gimple
*stmt
= USE_STMT (use
);
753 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
760 /* Return argument for loop preheader edge in header virtual phi if any. */
763 get_vop_from_header (struct loop
*loop
)
765 for (gphi_iterator gsi
= gsi_start_phis (loop
->header
);
766 !gsi_end_p (gsi
); gsi_next (&gsi
))
768 gphi
*phi
= gsi
.phi ();
769 if (!virtual_operand_p (gimple_phi_result (phi
)))
771 return PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
776 /* Move the check of GUARD outside of LOOP. */
779 hoist_guard (struct loop
*loop
, edge guard
)
781 edge exit
= single_exit (loop
);
782 edge preh
= loop_preheader_edge (loop
);
783 basic_block pre_header
= preh
->src
;
785 edge te
, fe
, e
, new_edge
;
787 basic_block guard_bb
= guard
->src
;
789 gimple_stmt_iterator gsi
;
791 bool fix_dom_of_exit
;
792 gcond
*cond_stmt
, *new_cond_stmt
;
794 bb
= get_immediate_dominator (CDI_DOMINATORS
, exit
->dest
);
795 fix_dom_of_exit
= flow_bb_inside_loop_p (loop
, bb
);
796 gsi
= gsi_last_bb (guard_bb
);
797 stmt
= gsi_stmt (gsi
);
798 gcc_assert (gimple_code (stmt
) == GIMPLE_COND
);
799 cond_stmt
= as_a
<gcond
*> (stmt
);
800 extract_true_false_edges_from_block (guard_bb
, &te
, &fe
);
801 /* Insert guard to PRE_HEADER. */
802 if (!empty_block_p (pre_header
))
803 gsi
= gsi_last_bb (pre_header
);
805 gsi
= gsi_start_bb (pre_header
);
806 /* Create copy of COND_STMT. */
807 new_cond_stmt
= gimple_build_cond (gimple_cond_code (cond_stmt
),
808 gimple_cond_lhs (cond_stmt
),
809 gimple_cond_rhs (cond_stmt
),
810 NULL_TREE
, NULL_TREE
);
811 gsi_insert_after (&gsi
, new_cond_stmt
, GSI_NEW_STMT
);
812 /* Convert COND_STMT to true/false conditional. */
814 gimple_cond_make_false (cond_stmt
);
816 gimple_cond_make_true (cond_stmt
);
817 update_stmt (cond_stmt
);
818 /* Create new loop pre-header. */
819 e
= split_block (pre_header
, last_stmt (pre_header
));
820 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
821 fprintf (dump_file
, " Moving guard %i->%i (prob %i) to bb %i, "
822 "new preheader is %i\n",
823 guard
->src
->index
, guard
->dest
->index
, guard
->probability
,
824 e
->src
->index
, e
->dest
->index
);
826 gcc_assert (loop_preheader_edge (loop
)->src
== e
->dest
);
830 e
->flags
= EDGE_TRUE_VALUE
;
831 flags
|= EDGE_FALSE_VALUE
;
836 e
->flags
= EDGE_FALSE_VALUE
;
837 flags
|= EDGE_TRUE_VALUE
;
840 new_edge
= make_edge (pre_header
, exit
->dest
, flags
);
842 /* Determine the probability that we skip the loop. Assume that loop has
843 same average number of iterations regardless outcome of guard. */
844 new_edge
->probability
= guard
->probability
;
845 int skip_count
= guard
->src
->count
846 ? RDIV (guard
->count
* pre_header
->count
, guard
->src
->count
)
847 : apply_probability (guard
->count
, new_edge
->probability
);
849 if (skip_count
> e
->count
)
851 fprintf (dump_file
, " Capping count; expect profile inconsistency\n");
852 skip_count
= e
->count
;
854 new_edge
->count
= skip_count
;
855 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
856 fprintf (dump_file
, " Estimated probability of skipping loop is %i\n",
857 new_edge
->probability
);
859 /* Update profile after the transform:
861 First decrease count of path from newly hoisted loop guard
863 e
->count
-= skip_count
;
864 e
->probability
= REG_BR_PROB_BASE
- new_edge
->probability
;
865 e
->dest
->count
= e
->count
;
866 e
->dest
->frequency
= EDGE_FREQUENCY (e
);
868 /* ... now update profile to represent that original guard will be optimized
870 guard
->probability
= 0;
872 not_guard
->probability
= REG_BR_PROB_BASE
;
873 /* This count is wrong (frequency of not_guard does not change),
874 but will be scaled later. */
875 not_guard
->count
= guard
->src
->count
;
877 /* ... finally scale everything in the loop except for guarded basic blocks
878 where profile does not change. */
879 basic_block
*body
= get_loop_body (loop
);
881 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
882 fprintf (dump_file
, " Scaling nonguarded BBs in loop:");
883 for (unsigned int i
= 0; i
< loop
->num_nodes
; i
++)
885 basic_block bb
= body
[i
];
886 if (!dominated_by_p (CDI_DOMINATORS
, bb
, not_guard
->dest
))
888 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
889 fprintf (dump_file
, " %i", bb
->index
);
890 scale_bbs_frequencies_int (&bb
, 1, e
->probability
, REG_BR_PROB_BASE
);
895 set_immediate_dominator (CDI_DOMINATORS
, exit
->dest
, pre_header
);
896 /* Add NEW_ADGE argument for all phi in post-header block. */
898 for (gphi_iterator gsi
= gsi_start_phis (bb
);
899 !gsi_end_p (gsi
); gsi_next (&gsi
))
901 gphi
*phi
= gsi
.phi ();
903 if (virtual_operand_p (gimple_phi_result (phi
)))
905 arg
= get_vop_from_header (loop
);
906 if (arg
== NULL_TREE
)
907 /* Use exit edge argument. */
908 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
909 add_phi_arg (phi
, arg
, new_edge
, UNKNOWN_LOCATION
);
913 /* Use exit edge argument. */
914 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
915 add_phi_arg (phi
, arg
, new_edge
, UNKNOWN_LOCATION
);
919 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
920 fprintf (dump_file
, "\n guard hoisted.\n");
925 /* Return true if phi argument for exit edge can be used
926 for edge around loop. */
929 check_exit_phi (struct loop
*loop
)
931 edge exit
= single_exit (loop
);
932 basic_block pre_header
= loop_preheader_edge (loop
)->src
;
934 for (gphi_iterator gsi
= gsi_start_phis (exit
->dest
);
935 !gsi_end_p (gsi
); gsi_next (&gsi
))
937 gphi
*phi
= gsi
.phi ();
941 if (virtual_operand_p (gimple_phi_result (phi
)))
943 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
944 if (TREE_CODE (arg
) != SSA_NAME
)
946 def
= SSA_NAME_DEF_STMT (arg
);
949 def_bb
= gimple_bb (def
);
952 if (!dominated_by_p (CDI_DOMINATORS
, pre_header
, def_bb
))
953 /* Definition inside loop! */
955 /* Check loop closed phi invariant. */
956 if (!flow_bb_inside_loop_p (def_bb
->loop_father
, pre_header
))
962 /* Loop unswitching pass. */
966 const pass_data pass_data_tree_unswitch
=
968 GIMPLE_PASS
, /* type */
969 "unswitch", /* name */
970 OPTGROUP_LOOP
, /* optinfo_flags */
971 TV_TREE_LOOP_UNSWITCH
, /* tv_id */
972 PROP_cfg
, /* properties_required */
973 0, /* properties_provided */
974 0, /* properties_destroyed */
975 0, /* todo_flags_start */
976 0, /* todo_flags_finish */
979 class pass_tree_unswitch
: public gimple_opt_pass
982 pass_tree_unswitch (gcc::context
*ctxt
)
983 : gimple_opt_pass (pass_data_tree_unswitch
, ctxt
)
986 /* opt_pass methods: */
987 virtual bool gate (function
*) { return flag_unswitch_loops
!= 0; }
988 virtual unsigned int execute (function
*);
990 }; // class pass_tree_unswitch
993 pass_tree_unswitch::execute (function
*fun
)
995 if (number_of_loops (fun
) <= 1)
998 return tree_ssa_unswitch_loops ();
1004 make_pass_tree_unswitch (gcc::context
*ctxt
)
1006 return new pass_tree_unswitch (ctxt
);