2 Copyright (C) 2004-2021 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"
36 #include "tree-inline.h"
37 #include "gimple-iterator.h"
39 #include "tree-ssa-loop-manip.h"
41 /* This file implements the loop unswitching, i.e. transformation of loops like
54 where inv is the loop invariant, into
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
77 static class loop
*tree_unswitch_loop (class loop
*, basic_block
, tree
);
78 static bool tree_unswitch_single_loop (class loop
*, int);
79 static tree
tree_may_unswitch_on (basic_block
, class loop
*);
80 static bool tree_unswitch_outer_loop (class loop
*);
81 static edge
find_loop_guard (class loop
*);
82 static bool empty_bb_without_guard_p (class loop
*, basic_block
);
83 static bool used_outside_loop_p (class loop
*, tree
);
84 static void hoist_guard (class loop
*, edge
);
85 static bool check_exit_phi (class loop
*);
86 static tree
get_vop_from_header (class loop
*);
88 /* Main entry point. Perform loop unswitching on all suitable loops. */
91 tree_ssa_unswitch_loops (void)
95 /* Go through all loops starting from innermost. */
96 for (auto loop
: loops_list (cfun
, LI_FROM_INNERMOST
))
99 /* Unswitch innermost loop. */
100 changed
|= tree_unswitch_single_loop (loop
, 0);
102 changed
|= tree_unswitch_outer_loop (loop
);
106 return TODO_cleanup_cfg
;
110 /* Return TRUE if an SSA_NAME maybe undefined and is therefore
111 unsuitable for unswitching. STMT is the statement we are
112 considering for unswitching and LOOP is the loop it appears in. */
115 is_maybe_undefined (const tree name
, gimple
*stmt
, class loop
*loop
)
117 /* The loop header is the only block we can trivially determine that
118 will always be executed. If the comparison is in the loop
119 header, we know it's OK to unswitch on it. */
120 if (gimple_bb (stmt
) == loop
->header
)
123 auto_bitmap visited_ssa
;
124 auto_vec
<tree
> worklist
;
125 worklist
.safe_push (name
);
126 bitmap_set_bit (visited_ssa
, SSA_NAME_VERSION (name
));
127 while (!worklist
.is_empty ())
129 tree t
= worklist
.pop ();
131 /* If it's obviously undefined, avoid further computations. */
132 if (ssa_undefined_value_p (t
, true))
135 if (ssa_defined_default_def_p (t
))
138 gimple
*def
= SSA_NAME_DEF_STMT (t
);
140 /* Check that all the PHI args are fully defined. */
141 if (gphi
*phi
= dyn_cast
<gphi
*> (def
))
143 for (unsigned i
= 0; i
< gimple_phi_num_args (phi
); ++i
)
145 tree t
= gimple_phi_arg_def (phi
, i
);
146 /* If an SSA has already been seen, it may be a loop,
147 but we can continue and ignore this use. Otherwise,
148 add the SSA_NAME to the queue and visit it later. */
149 if (TREE_CODE (t
) == SSA_NAME
150 && bitmap_set_bit (visited_ssa
, SSA_NAME_VERSION (t
)))
151 worklist
.safe_push (t
);
156 /* Uses in stmts always executed when the region header executes
158 if (dominated_by_p (CDI_DOMINATORS
, loop
->header
, gimple_bb (def
)))
161 /* Handle calls and memory loads conservatively. */
162 if (!is_gimple_assign (def
)
163 || (gimple_assign_single_p (def
)
164 && gimple_vuse (def
)))
167 /* Check that any SSA names used to define NAME are also fully
171 FOR_EACH_SSA_USE_OPERAND (use_p
, def
, iter
, SSA_OP_USE
)
173 tree t
= USE_FROM_PTR (use_p
);
174 /* If an SSA has already been seen, it may be a loop,
175 but we can continue and ignore this use. Otherwise,
176 add the SSA_NAME to the queue and visit it later. */
177 if (bitmap_set_bit (visited_ssa
, SSA_NAME_VERSION (t
)))
178 worklist
.safe_push (t
);
184 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
185 basic blocks (for what it means see comments below). */
188 tree_may_unswitch_on (basic_block bb
, class loop
*loop
)
196 /* BB must end in a simple conditional jump. */
197 last
= last_stmt (bb
);
198 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
200 stmt
= as_a
<gcond
*> (last
);
202 /* To keep the things simple, we do not directly remove the conditions,
203 but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite
204 loop where we would unswitch again on such a condition. */
205 if (gimple_cond_true_p (stmt
) || gimple_cond_false_p (stmt
))
208 /* Condition must be invariant. */
209 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
211 def
= SSA_NAME_DEF_STMT (use
);
212 def_bb
= gimple_bb (def
);
214 && flow_bb_inside_loop_p (loop
, def_bb
))
216 /* Unswitching on undefined values would introduce undefined
217 behavior that the original program might never exercise. */
218 if (is_maybe_undefined (use
, stmt
, loop
))
222 cond
= build2 (gimple_cond_code (stmt
), boolean_type_node
,
223 gimple_cond_lhs (stmt
), gimple_cond_rhs (stmt
));
228 /* Simplifies COND using checks in front of the entry of the LOOP. Just very
229 simplish (sufficient to prevent us from duplicating loop in unswitching
233 simplify_using_entry_checks (class loop
*loop
, tree cond
)
235 edge e
= loop_preheader_edge (loop
);
240 stmt
= last_stmt (e
->src
);
242 && gimple_code (stmt
) == GIMPLE_COND
243 && gimple_cond_code (stmt
) == TREE_CODE (cond
)
244 && operand_equal_p (gimple_cond_lhs (stmt
),
245 TREE_OPERAND (cond
, 0), 0)
246 && operand_equal_p (gimple_cond_rhs (stmt
),
247 TREE_OPERAND (cond
, 1), 0))
248 return (e
->flags
& EDGE_TRUE_VALUE
250 : boolean_false_node
);
252 if (!single_pred_p (e
->src
))
255 e
= single_pred_edge (e
->src
);
256 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
261 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow
262 it to grow too much, it is too easy to create example on that the code would
263 grow exponentially. */
266 tree_unswitch_single_loop (class loop
*loop
, int num
)
271 tree cond
= NULL_TREE
;
273 bool changed
= false;
274 HOST_WIDE_INT iterations
;
276 /* Perform initial tests if unswitch is eligible. */
279 /* Do not unswitch in cold regions. */
280 if (optimize_loop_for_size_p (loop
))
282 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
283 fprintf (dump_file
, ";; Not unswitching cold loops\n");
287 /* The loop should not be too large, to limit code growth. */
288 if (tree_num_loop_insns (loop
, &eni_size_weights
)
289 > (unsigned) param_max_unswitch_insns
)
291 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
292 fprintf (dump_file
, ";; Not unswitching, loop too big\n");
296 /* If the loop is not expected to iterate, there is no need
298 iterations
= estimated_loop_iterations_int (loop
);
300 iterations
= likely_max_loop_iterations_int (loop
);
301 if (iterations
>= 0 && iterations
<= 1)
303 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
304 fprintf (dump_file
, ";; Not unswitching, loop is not expected"
311 bbs
= get_loop_body (loop
);
312 found
= loop
->num_nodes
;
316 /* Find a bb to unswitch on. */
317 for (; i
< loop
->num_nodes
; i
++)
318 if ((cond
= tree_may_unswitch_on (bbs
[i
], loop
)))
321 if (i
== loop
->num_nodes
)
324 && num
> param_max_unswitch_level
325 && (dump_flags
& TDF_DETAILS
))
326 fprintf (dump_file
, ";; Not unswitching anymore, hit max level\n");
328 if (found
== loop
->num_nodes
)
336 cond
= simplify_using_entry_checks (loop
, cond
);
337 stmt
= last_stmt (bbs
[i
]);
338 if (integer_nonzerop (cond
))
340 /* Remove false path. */
341 gimple_cond_set_condition_from_tree (as_a
<gcond
*> (stmt
),
345 else if (integer_zerop (cond
))
347 /* Remove true path. */
348 gimple_cond_set_condition_from_tree (as_a
<gcond
*> (stmt
),
352 /* Do not unswitch too much. */
353 else if (num
> param_max_unswitch_level
)
358 /* In nested tree_unswitch_single_loop first optimize all conditions
359 using entry checks, then discover still reachable blocks in the
360 loop and find the condition only among those still reachable bbs. */
363 if (found
== loop
->num_nodes
)
380 basic_block
*tos
, *worklist
;
382 /* When called recursively, first do a quick discovery
383 of reachable bbs after the above changes and only
384 consider conditions in still reachable bbs. */
385 tos
= worklist
= XNEWVEC (basic_block
, loop
->num_nodes
);
387 for (i
= 0; i
< loop
->num_nodes
; i
++)
388 bbs
[i
]->flags
&= ~BB_REACHABLE
;
390 /* Start with marking header. */
392 bbs
[0]->flags
|= BB_REACHABLE
;
394 /* Iterate: find everything reachable from what we've already seen
395 within the same innermost loop. Don't look through false edges
396 if condition is always true or true edges if condition is
398 while (tos
!= worklist
)
400 basic_block b
= *--tos
;
405 if (EDGE_COUNT (b
->succs
) == 2)
407 gimple
*stmt
= last_stmt (b
);
409 && gimple_code (stmt
) == GIMPLE_COND
)
411 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
412 if (gimple_cond_true_p (cond_stmt
))
413 flags
= EDGE_FALSE_VALUE
;
414 else if (gimple_cond_false_p (cond_stmt
))
415 flags
= EDGE_TRUE_VALUE
;
419 FOR_EACH_EDGE (e
, ei
, b
->succs
)
421 basic_block dest
= e
->dest
;
423 if (dest
->loop_father
== loop
424 && !(dest
->flags
& BB_REACHABLE
)
425 && !(e
->flags
& flags
))
428 dest
->flags
|= BB_REACHABLE
;
435 /* Find a bb to unswitch on. */
436 for (; found
< loop
->num_nodes
; found
++)
437 if ((bbs
[found
]->flags
& BB_REACHABLE
)
438 && (cond
= tree_may_unswitch_on (bbs
[found
], loop
)))
441 if (found
== loop
->num_nodes
)
448 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
449 fprintf (dump_file
, ";; Unswitching loop\n");
451 initialize_original_copy_tables ();
452 /* Unswitch the loop on this condition. */
453 nloop
= tree_unswitch_loop (loop
, bbs
[found
], cond
);
456 free_original_copy_tables ();
461 /* Update the SSA form after unswitching. */
462 update_ssa (TODO_update_ssa
);
463 free_original_copy_tables ();
465 /* Invoke itself on modified loops. */
466 tree_unswitch_single_loop (nloop
, num
+ 1);
467 tree_unswitch_single_loop (loop
, num
+ 1);
472 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
473 unswitching of innermost loops. COND is the condition determining which
474 loop is entered -- the new loop is entered if COND is true. Returns NULL
475 if impossible, new loop otherwise. */
478 tree_unswitch_loop (class loop
*loop
,
479 basic_block unswitch_on
, tree cond
)
481 profile_probability prob_true
;
482 edge edge_true
, edge_false
;
484 /* Some sanity checking. */
485 gcc_assert (flow_bb_inside_loop_p (loop
, unswitch_on
));
486 gcc_assert (EDGE_COUNT (unswitch_on
->succs
) == 2);
487 gcc_assert (loop
->inner
== NULL
);
489 extract_true_false_edges_from_block (unswitch_on
, &edge_true
, &edge_false
);
490 prob_true
= edge_true
->probability
;
491 return loop_version (loop
, unshare_expr (cond
),
494 prob_true
, prob_true
.invert (),
498 /* Unswitch outer loops by hoisting invariant guard on
499 inner loop without code duplication. */
501 tree_unswitch_outer_loop (class 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 (class 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 basic_block next
= NULL
;
584 if (single_succ_p (header
))
585 next
= single_succ (header
);
588 cond
= safe_dyn_cast
<gcond
*> (last_stmt (header
));
591 extract_true_false_edges_from_block (header
, &te
, &fe
);
592 /* Make sure to skip earlier hoisted guards that are left
593 in place as if (true). */
594 if (gimple_cond_true_p (cond
))
596 else if (gimple_cond_false_p (cond
))
601 /* Never traverse a backedge. */
602 if (header
->loop_father
->header
== next
)
607 if (!flow_bb_inside_loop_p (loop
, te
->dest
)
608 || !flow_bb_inside_loop_p (loop
, fe
->dest
))
611 if (just_once_each_iteration_p (loop
, te
->dest
)
612 || (single_succ_p (te
->dest
)
613 && just_once_each_iteration_p (loop
, single_succ (te
->dest
))))
615 if (just_once_each_iteration_p (loop
, fe
->dest
))
619 else if (just_once_each_iteration_p (loop
, fe
->dest
)
620 || (single_succ_p (fe
->dest
)
621 && just_once_each_iteration_p (loop
, single_succ (fe
->dest
))))
626 /* Guard edge must skip inner loop. */
627 if (!dominated_by_p (CDI_DOMINATORS
, loop
->inner
->header
,
628 guard_edge
== fe
? te
->dest
: fe
->dest
))
630 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
631 fprintf (dump_file
, "Guard edge %d --> %d is not around the loop!\n",
632 guard_edge
->src
->index
, guard_edge
->dest
->index
);
635 if (guard_edge
->dest
== loop
->latch
)
637 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
638 fprintf (dump_file
, "Guard edge destination is loop latch.\n");
642 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
644 "Considering guard %d -> %d in loop %d\n",
645 guard_edge
->src
->index
, guard_edge
->dest
->index
, loop
->num
);
646 /* Check if condition operands do not have definitions inside loop since
647 any bb copying is not performed. */
648 FOR_EACH_SSA_TREE_OPERAND (use
, cond
, iter
, SSA_OP_USE
)
650 gimple
*def
= SSA_NAME_DEF_STMT (use
);
651 basic_block def_bb
= gimple_bb (def
);
653 && flow_bb_inside_loop_p (loop
, def_bb
))
655 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
656 fprintf (dump_file
, " guard operands have definitions"
662 body
= get_loop_body (loop
);
663 for (i
= 0; i
< loop
->num_nodes
; i
++)
665 basic_block bb
= body
[i
];
666 if (bb
->loop_father
!= loop
)
668 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
670 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
671 fprintf (dump_file
, "Block %d is marked as irreducible in loop\n",
676 if (!empty_bb_without_guard_p (loop
, bb
))
678 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
679 fprintf (dump_file
, " block %d has side effects\n", bb
->index
);
685 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
686 fprintf (dump_file
, " suitable to hoist\n");
694 1) no statement in BB has side effects
695 2) assuming that edge GUARD is always taken, all definitions in BB
696 are noy used outside of the loop.
697 KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
698 PROCESSED is a set of ssa names for that we already tested whether they
699 are invariant or not. */
702 empty_bb_without_guard_p (class loop
*loop
, basic_block bb
)
704 basic_block exit_bb
= single_exit (loop
)->src
;
705 bool may_be_used_outside
= (bb
== exit_bb
706 || !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
));
710 /* Phi nodes do not have side effects, but their results might be used
711 outside of the loop. */
712 if (may_be_used_outside
)
714 for (gphi_iterator gsi
= gsi_start_phis (bb
);
715 !gsi_end_p (gsi
); gsi_next (&gsi
))
717 gphi
*phi
= gsi
.phi ();
718 name
= PHI_RESULT (phi
);
719 if (virtual_operand_p (name
))
722 if (used_outside_loop_p (loop
, name
))
727 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
728 !gsi_end_p (gsi
); gsi_next (&gsi
))
730 gimple
*stmt
= gsi_stmt (gsi
);
731 if (gimple_has_side_effects (stmt
))
734 if (gimple_vdef(stmt
))
737 FOR_EACH_SSA_TREE_OPERAND (name
, stmt
, op_iter
, SSA_OP_DEF
)
739 if (may_be_used_outside
740 && used_outside_loop_p (loop
, name
))
747 /* Return true if NAME is used outside of LOOP. */
750 used_outside_loop_p (class loop
*loop
, tree name
)
755 FOR_EACH_IMM_USE_FAST (use
, it
, name
)
757 gimple
*stmt
= USE_STMT (use
);
758 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
765 /* Return argument for loop preheader edge in header virtual phi if any. */
768 get_vop_from_header (class loop
*loop
)
770 for (gphi_iterator gsi
= gsi_start_phis (loop
->header
);
771 !gsi_end_p (gsi
); gsi_next (&gsi
))
773 gphi
*phi
= gsi
.phi ();
774 if (!virtual_operand_p (gimple_phi_result (phi
)))
776 return PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
781 /* Move the check of GUARD outside of LOOP. */
784 hoist_guard (class loop
*loop
, edge guard
)
786 edge exit
= single_exit (loop
);
787 edge preh
= loop_preheader_edge (loop
);
788 basic_block pre_header
= preh
->src
;
790 edge te
, fe
, e
, new_edge
;
792 basic_block guard_bb
= guard
->src
;
794 gimple_stmt_iterator gsi
;
796 bool fix_dom_of_exit
;
797 gcond
*cond_stmt
, *new_cond_stmt
;
799 bb
= get_immediate_dominator (CDI_DOMINATORS
, exit
->dest
);
800 fix_dom_of_exit
= flow_bb_inside_loop_p (loop
, bb
);
801 gsi
= gsi_last_bb (guard_bb
);
802 stmt
= gsi_stmt (gsi
);
803 gcc_assert (gimple_code (stmt
) == GIMPLE_COND
);
804 cond_stmt
= as_a
<gcond
*> (stmt
);
805 extract_true_false_edges_from_block (guard_bb
, &te
, &fe
);
806 /* Insert guard to PRE_HEADER. */
807 if (!empty_block_p (pre_header
))
808 gsi
= gsi_last_bb (pre_header
);
810 gsi
= gsi_start_bb (pre_header
);
811 /* Create copy of COND_STMT. */
812 new_cond_stmt
= gimple_build_cond (gimple_cond_code (cond_stmt
),
813 gimple_cond_lhs (cond_stmt
),
814 gimple_cond_rhs (cond_stmt
),
815 NULL_TREE
, NULL_TREE
);
816 gsi_insert_after (&gsi
, new_cond_stmt
, GSI_NEW_STMT
);
817 /* Convert COND_STMT to true/false conditional. */
819 gimple_cond_make_false (cond_stmt
);
821 gimple_cond_make_true (cond_stmt
);
822 update_stmt (cond_stmt
);
823 /* Create new loop pre-header. */
824 e
= split_block (pre_header
, last_stmt (pre_header
));
825 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
827 fprintf (dump_file
, " Moving guard %i->%i (prob ",
828 guard
->src
->index
, guard
->dest
->index
);
829 guard
->probability
.dump (dump_file
);
830 fprintf (dump_file
, ") to bb %i, new preheader is %i\n",
831 e
->src
->index
, e
->dest
->index
);
834 gcc_assert (loop_preheader_edge (loop
)->src
== e
->dest
);
838 e
->flags
= EDGE_TRUE_VALUE
;
839 flags
|= EDGE_FALSE_VALUE
;
844 e
->flags
= EDGE_FALSE_VALUE
;
845 flags
|= EDGE_TRUE_VALUE
;
848 new_edge
= make_edge (pre_header
, exit
->dest
, flags
);
850 /* Determine the probability that we skip the loop. Assume that loop has
851 same average number of iterations regardless outcome of guard. */
852 new_edge
->probability
= guard
->probability
;
853 profile_count skip_count
= guard
->src
->count
.nonzero_p ()
854 ? guard
->count ().apply_scale (pre_header
->count
,
856 : guard
->count ().apply_probability (new_edge
->probability
);
858 if (skip_count
> e
->count ())
860 fprintf (dump_file
, " Capping count; expect profile inconsistency\n");
861 skip_count
= e
->count ();
863 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
865 fprintf (dump_file
, " Estimated probability of skipping loop is ");
866 new_edge
->probability
.dump (dump_file
);
867 fprintf (dump_file
, "\n");
870 /* Update profile after the transform:
872 First decrease count of path from newly hoisted loop guard
874 e
->probability
= new_edge
->probability
.invert ();
875 e
->dest
->count
= e
->count ();
877 /* ... now update profile to represent that original guard will be optimized
879 guard
->probability
= profile_probability::never ();
880 not_guard
->probability
= profile_probability::always ();
882 /* ... finally scale everything in the loop except for guarded basic blocks
883 where profile does not change. */
884 basic_block
*body
= get_loop_body (loop
);
886 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
887 fprintf (dump_file
, " Scaling nonguarded BBs in loop:");
888 for (unsigned int i
= 0; i
< loop
->num_nodes
; i
++)
890 basic_block bb
= body
[i
];
891 if (!dominated_by_p (CDI_DOMINATORS
, bb
, not_guard
->dest
))
893 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
894 fprintf (dump_file
, " %i", bb
->index
);
895 if (e
->probability
.initialized_p ())
896 scale_bbs_frequencies (&bb
, 1, e
->probability
);
901 set_immediate_dominator (CDI_DOMINATORS
, exit
->dest
, pre_header
);
902 /* Add NEW_ADGE argument for all phi in post-header block. */
904 for (gphi_iterator gsi
= gsi_start_phis (bb
);
905 !gsi_end_p (gsi
); gsi_next (&gsi
))
907 gphi
*phi
= gsi
.phi ();
909 if (virtual_operand_p (gimple_phi_result (phi
)))
911 arg
= get_vop_from_header (loop
);
912 if (arg
== NULL_TREE
)
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 /* Use exit edge argument. */
920 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
921 add_phi_arg (phi
, arg
, new_edge
, UNKNOWN_LOCATION
);
925 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
926 fprintf (dump_file
, "\n guard hoisted.\n");
931 /* Return true if phi argument for exit edge can be used
932 for edge around loop. */
935 check_exit_phi (class loop
*loop
)
937 edge exit
= single_exit (loop
);
938 basic_block pre_header
= loop_preheader_edge (loop
)->src
;
940 for (gphi_iterator gsi
= gsi_start_phis (exit
->dest
);
941 !gsi_end_p (gsi
); gsi_next (&gsi
))
943 gphi
*phi
= gsi
.phi ();
947 if (virtual_operand_p (gimple_phi_result (phi
)))
949 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
950 if (TREE_CODE (arg
) != SSA_NAME
)
952 def
= SSA_NAME_DEF_STMT (arg
);
955 def_bb
= gimple_bb (def
);
958 if (!dominated_by_p (CDI_DOMINATORS
, pre_header
, def_bb
))
959 /* Definition inside loop! */
961 /* Check loop closed phi invariant. */
962 if (!flow_bb_inside_loop_p (def_bb
->loop_father
, pre_header
))
968 /* Loop unswitching pass. */
972 const pass_data pass_data_tree_unswitch
=
974 GIMPLE_PASS
, /* type */
975 "unswitch", /* name */
976 OPTGROUP_LOOP
, /* optinfo_flags */
977 TV_TREE_LOOP_UNSWITCH
, /* tv_id */
978 PROP_cfg
, /* properties_required */
979 0, /* properties_provided */
980 0, /* properties_destroyed */
981 0, /* todo_flags_start */
982 0, /* todo_flags_finish */
985 class pass_tree_unswitch
: public gimple_opt_pass
988 pass_tree_unswitch (gcc::context
*ctxt
)
989 : gimple_opt_pass (pass_data_tree_unswitch
, ctxt
)
992 /* opt_pass methods: */
993 virtual bool gate (function
*) { return flag_unswitch_loops
!= 0; }
994 virtual unsigned int execute (function
*);
996 }; // class pass_tree_unswitch
999 pass_tree_unswitch::execute (function
*fun
)
1001 if (number_of_loops (fun
) <= 1)
1004 return tree_ssa_unswitch_loops ();
1010 make_pass_tree_unswitch (gcc::context
*ctxt
)
1012 return new pass_tree_unswitch (ctxt
);