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 basic_block next
= NULL
;
584 if (single_succ_p (header
))
585 next
= single_succ (header
);
588 cond
= 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 (struct 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 (struct 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 (struct 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 (struct 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
))
826 fprintf (dump_file
, " Moving guard %i->%i (prob %i) to bb %i, "
827 "new preheader is %i\n",
828 guard
->src
->index
, guard
->dest
->index
, guard
->probability
,
829 e
->src
->index
, e
->dest
->index
);
831 gcc_assert (loop_preheader_edge (loop
)->src
== e
->dest
);
835 e
->flags
= EDGE_TRUE_VALUE
;
836 flags
|= EDGE_FALSE_VALUE
;
841 e
->flags
= EDGE_FALSE_VALUE
;
842 flags
|= EDGE_TRUE_VALUE
;
845 new_edge
= make_edge (pre_header
, exit
->dest
, flags
);
847 /* Determine the probability that we skip the loop. Assume that loop has
848 same average number of iterations regardless outcome of guard. */
849 new_edge
->probability
= guard
->probability
;
850 int skip_count
= guard
->src
->count
851 ? RDIV (guard
->count
* pre_header
->count
, guard
->src
->count
)
852 : apply_probability (guard
->count
, new_edge
->probability
);
854 if (skip_count
> e
->count
)
856 fprintf (dump_file
, " Capping count; expect profile inconsistency\n");
857 skip_count
= e
->count
;
859 new_edge
->count
= skip_count
;
860 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
861 fprintf (dump_file
, " Estimated probability of skipping loop is %i\n",
862 new_edge
->probability
);
864 /* Update profile after the transform:
866 First decrease count of path from newly hoisted loop guard
868 e
->count
-= skip_count
;
869 e
->probability
= REG_BR_PROB_BASE
- new_edge
->probability
;
870 e
->dest
->count
= e
->count
;
871 e
->dest
->frequency
= EDGE_FREQUENCY (e
);
873 /* ... now update profile to represent that original guard will be optimized
875 guard
->probability
= 0;
877 not_guard
->probability
= REG_BR_PROB_BASE
;
878 /* This count is wrong (frequency of not_guard does not change),
879 but will be scaled later. */
880 not_guard
->count
= guard
->src
->count
;
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 scale_bbs_frequencies_int (&bb
, 1, e
->probability
, REG_BR_PROB_BASE
);
900 set_immediate_dominator (CDI_DOMINATORS
, exit
->dest
, pre_header
);
901 /* Add NEW_ADGE argument for all phi in post-header block. */
903 for (gphi_iterator gsi
= gsi_start_phis (bb
);
904 !gsi_end_p (gsi
); gsi_next (&gsi
))
906 gphi
*phi
= gsi
.phi ();
908 if (virtual_operand_p (gimple_phi_result (phi
)))
910 arg
= get_vop_from_header (loop
);
911 if (arg
== NULL_TREE
)
912 /* Use exit edge argument. */
913 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
914 add_phi_arg (phi
, arg
, new_edge
, UNKNOWN_LOCATION
);
918 /* Use exit edge argument. */
919 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
920 add_phi_arg (phi
, arg
, new_edge
, UNKNOWN_LOCATION
);
924 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
925 fprintf (dump_file
, "\n guard hoisted.\n");
930 /* Return true if phi argument for exit edge can be used
931 for edge around loop. */
934 check_exit_phi (struct loop
*loop
)
936 edge exit
= single_exit (loop
);
937 basic_block pre_header
= loop_preheader_edge (loop
)->src
;
939 for (gphi_iterator gsi
= gsi_start_phis (exit
->dest
);
940 !gsi_end_p (gsi
); gsi_next (&gsi
))
942 gphi
*phi
= gsi
.phi ();
946 if (virtual_operand_p (gimple_phi_result (phi
)))
948 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
949 if (TREE_CODE (arg
) != SSA_NAME
)
951 def
= SSA_NAME_DEF_STMT (arg
);
954 def_bb
= gimple_bb (def
);
957 if (!dominated_by_p (CDI_DOMINATORS
, pre_header
, def_bb
))
958 /* Definition inside loop! */
960 /* Check loop closed phi invariant. */
961 if (!flow_bb_inside_loop_p (def_bb
->loop_father
, pre_header
))
967 /* Loop unswitching pass. */
971 const pass_data pass_data_tree_unswitch
=
973 GIMPLE_PASS
, /* type */
974 "unswitch", /* name */
975 OPTGROUP_LOOP
, /* optinfo_flags */
976 TV_TREE_LOOP_UNSWITCH
, /* tv_id */
977 PROP_cfg
, /* properties_required */
978 0, /* properties_provided */
979 0, /* properties_destroyed */
980 0, /* todo_flags_start */
981 0, /* todo_flags_finish */
984 class pass_tree_unswitch
: public gimple_opt_pass
987 pass_tree_unswitch (gcc::context
*ctxt
)
988 : gimple_opt_pass (pass_data_tree_unswitch
, ctxt
)
991 /* opt_pass methods: */
992 virtual bool gate (function
*) { return flag_unswitch_loops
!= 0; }
993 virtual unsigned int execute (function
*);
995 }; // class pass_tree_unswitch
998 pass_tree_unswitch::execute (function
*fun
)
1000 if (number_of_loops (fun
) <= 1)
1003 return tree_ssa_unswitch_loops ();
1009 make_pass_tree_unswitch (gcc::context
*ctxt
)
1011 return new pass_tree_unswitch (ctxt
);