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
)
483 profile_probability prob_true
;
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
),
496 prob_true
, prob_true
.invert (),
500 /* Unswitch outer loops by hoisting invariant guard on
501 inner loop without code duplication. */
503 tree_unswitch_outer_loop (struct loop
*loop
)
506 HOST_WIDE_INT iterations
;
508 gcc_assert (loop
->inner
);
509 if (loop
->inner
->next
)
511 /* Accept loops with single exit only which is not from inner loop. */
512 exit
= single_exit (loop
);
513 if (!exit
|| exit
->src
->loop_father
!= loop
)
515 /* Check that phi argument of exit edge is not defined inside loop. */
516 if (!check_exit_phi (loop
))
518 /* If the loop is not expected to iterate, there is no need
520 iterations
= estimated_loop_iterations_int (loop
);
522 iterations
= likely_max_loop_iterations_int (loop
);
523 if (iterations
>= 0 && iterations
<= 1)
525 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
526 fprintf (dump_file
, ";; Not unswitching, loop is not expected"
531 bool changed
= false;
532 while ((guard
= find_loop_guard (loop
)))
535 rewrite_virtuals_into_loop_closed_ssa (loop
);
536 hoist_guard (loop
, guard
);
542 /* Checks if the body of the LOOP is within an invariant guard. If this
543 is the case, returns the edge that jumps over the real body of the loop,
544 otherwise returns NULL. */
547 find_loop_guard (struct loop
*loop
)
549 basic_block header
= loop
->header
;
550 edge guard_edge
, te
, fe
;
551 basic_block
*body
= NULL
;
556 /* We check for the following situation:
565 nvar = phi(orig, bvar) ... for all variables changed in body;
575 1) cond1 is loop invariant
576 2) If cond1 is false, then the loop is essentially empty; i.e.,
577 a) nothing in something1, something2 and something3 has side
579 b) anything defined in something1, something2 and something3
580 is not used outside of the loop. */
585 if (single_succ_p (header
))
586 header
= single_succ (header
);
589 cond
= dyn_cast
<gcond
*> (last_stmt (header
));
592 extract_true_false_edges_from_block (header
, &te
, &fe
);
593 /* Make sure to skip earlier hoisted guards that are left
594 in place as if (true). */
595 if (gimple_cond_true_p (cond
))
597 else if (gimple_cond_false_p (cond
))
604 if (!flow_bb_inside_loop_p (loop
, te
->dest
)
605 || !flow_bb_inside_loop_p (loop
, fe
->dest
))
608 if (just_once_each_iteration_p (loop
, te
->dest
)
609 || (single_succ_p (te
->dest
)
610 && just_once_each_iteration_p (loop
, single_succ (te
->dest
))))
612 if (just_once_each_iteration_p (loop
, fe
->dest
))
616 else if (just_once_each_iteration_p (loop
, fe
->dest
)
617 || (single_succ_p (fe
->dest
)
618 && just_once_each_iteration_p (loop
, single_succ (fe
->dest
))))
623 /* Guard edge must skip inner loop. */
624 if (!dominated_by_p (CDI_DOMINATORS
, loop
->inner
->header
,
625 guard_edge
== fe
? te
->dest
: fe
->dest
))
627 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
628 fprintf (dump_file
, "Guard edge %d --> %d is not around the loop!\n",
629 guard_edge
->src
->index
, guard_edge
->dest
->index
);
632 if (guard_edge
->dest
== loop
->latch
)
634 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
635 fprintf (dump_file
, "Guard edge destination is loop latch.\n");
639 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
641 "Considering guard %d -> %d in loop %d\n",
642 guard_edge
->src
->index
, guard_edge
->dest
->index
, loop
->num
);
643 /* Check if condition operands do not have definitions inside loop since
644 any bb copying is not performed. */
645 FOR_EACH_SSA_TREE_OPERAND (use
, cond
, iter
, SSA_OP_USE
)
647 gimple
*def
= SSA_NAME_DEF_STMT (use
);
648 basic_block def_bb
= gimple_bb (def
);
650 && flow_bb_inside_loop_p (loop
, def_bb
))
652 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
653 fprintf (dump_file
, " guard operands have definitions"
659 body
= get_loop_body (loop
);
660 for (i
= 0; i
< loop
->num_nodes
; i
++)
662 basic_block bb
= body
[i
];
663 if (bb
->loop_father
!= loop
)
665 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
667 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
668 fprintf (dump_file
, "Block %d is marked as irreducible in loop\n",
673 if (!empty_bb_without_guard_p (loop
, bb
))
675 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
676 fprintf (dump_file
, " block %d has side effects\n", bb
->index
);
682 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
683 fprintf (dump_file
, " suitable to hoist\n");
691 1) no statement in BB has side effects
692 2) assuming that edge GUARD is always taken, all definitions in BB
693 are noy used outside of the loop.
694 KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
695 PROCESSED is a set of ssa names for that we already tested whether they
696 are invariant or not. */
699 empty_bb_without_guard_p (struct loop
*loop
, basic_block bb
)
701 basic_block exit_bb
= single_exit (loop
)->src
;
702 bool may_be_used_outside
= (bb
== exit_bb
703 || !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
));
707 /* Phi nodes do not have side effects, but their results might be used
708 outside of the loop. */
709 if (may_be_used_outside
)
711 for (gphi_iterator gsi
= gsi_start_phis (bb
);
712 !gsi_end_p (gsi
); gsi_next (&gsi
))
714 gphi
*phi
= gsi
.phi ();
715 name
= PHI_RESULT (phi
);
716 if (virtual_operand_p (name
))
719 if (used_outside_loop_p (loop
, name
))
724 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
725 !gsi_end_p (gsi
); gsi_next (&gsi
))
727 gimple
*stmt
= gsi_stmt (gsi
);
728 if (gimple_has_side_effects (stmt
))
731 if (gimple_vdef(stmt
))
734 FOR_EACH_SSA_TREE_OPERAND (name
, stmt
, op_iter
, SSA_OP_DEF
)
736 if (may_be_used_outside
737 && used_outside_loop_p (loop
, name
))
744 /* Return true if NAME is used outside of LOOP. */
747 used_outside_loop_p (struct loop
*loop
, tree name
)
752 FOR_EACH_IMM_USE_FAST (use
, it
, name
)
754 gimple
*stmt
= USE_STMT (use
);
755 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
762 /* Return argument for loop preheader edge in header virtual phi if any. */
765 get_vop_from_header (struct loop
*loop
)
767 for (gphi_iterator gsi
= gsi_start_phis (loop
->header
);
768 !gsi_end_p (gsi
); gsi_next (&gsi
))
770 gphi
*phi
= gsi
.phi ();
771 if (!virtual_operand_p (gimple_phi_result (phi
)))
773 return PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
778 /* Move the check of GUARD outside of LOOP. */
781 hoist_guard (struct loop
*loop
, edge guard
)
783 edge exit
= single_exit (loop
);
784 edge preh
= loop_preheader_edge (loop
);
785 basic_block pre_header
= preh
->src
;
787 edge te
, fe
, e
, new_edge
;
789 basic_block guard_bb
= guard
->src
;
791 gimple_stmt_iterator gsi
;
793 bool fix_dom_of_exit
;
794 gcond
*cond_stmt
, *new_cond_stmt
;
796 bb
= get_immediate_dominator (CDI_DOMINATORS
, exit
->dest
);
797 fix_dom_of_exit
= flow_bb_inside_loop_p (loop
, bb
);
798 gsi
= gsi_last_bb (guard_bb
);
799 stmt
= gsi_stmt (gsi
);
800 gcc_assert (gimple_code (stmt
) == GIMPLE_COND
);
801 cond_stmt
= as_a
<gcond
*> (stmt
);
802 extract_true_false_edges_from_block (guard_bb
, &te
, &fe
);
803 /* Insert guard to PRE_HEADER. */
804 if (!empty_block_p (pre_header
))
805 gsi
= gsi_last_bb (pre_header
);
807 gsi
= gsi_start_bb (pre_header
);
808 /* Create copy of COND_STMT. */
809 new_cond_stmt
= gimple_build_cond (gimple_cond_code (cond_stmt
),
810 gimple_cond_lhs (cond_stmt
),
811 gimple_cond_rhs (cond_stmt
),
812 NULL_TREE
, NULL_TREE
);
813 gsi_insert_after (&gsi
, new_cond_stmt
, GSI_NEW_STMT
);
814 /* Convert COND_STMT to true/false conditional. */
816 gimple_cond_make_false (cond_stmt
);
818 gimple_cond_make_true (cond_stmt
);
819 update_stmt (cond_stmt
);
820 /* Create new loop pre-header. */
821 e
= split_block (pre_header
, last_stmt (pre_header
));
822 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
824 fprintf (dump_file
, " Moving guard %i->%i (prob ",
825 guard
->src
->index
, guard
->dest
->index
);
826 guard
->probability
.dump (dump_file
);
827 fprintf (dump_file
, ") to bb %i, new preheader is %i\n",
828 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 profile_count skip_count
= guard
->src
->count
> 0
851 ? guard
->count
.apply_scale (pre_header
->count
,
853 : guard
->count
.apply_probability (new_edge
->probability
);
855 if (skip_count
> e
->count
)
857 fprintf (dump_file
, " Capping count; expect profile inconsistency\n");
858 skip_count
= e
->count
;
860 new_edge
->count
= skip_count
;
861 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
863 fprintf (dump_file
, " Estimated probability of skipping loop is ");
864 new_edge
->probability
.dump (dump_file
);
865 fprintf (dump_file
, "\n");
868 /* Update profile after the transform:
870 First decrease count of path from newly hoisted loop guard
872 e
->count
-= skip_count
;
873 e
->probability
= new_edge
->probability
.invert ();
874 e
->dest
->count
= e
->count
;
875 e
->dest
->frequency
= EDGE_FREQUENCY (e
);
877 /* ... now update profile to represent that original guard will be optimized
879 guard
->probability
= profile_probability::never ();
880 guard
->count
= profile_count::zero ();
881 not_guard
->probability
= profile_probability::always ();
882 /* This count is wrong (frequency of not_guard does not change),
883 but will be scaled later. */
884 not_guard
->count
= guard
->src
->count
;
886 /* ... finally scale everything in the loop except for guarded basic blocks
887 where profile does not change. */
888 basic_block
*body
= get_loop_body (loop
);
890 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
891 fprintf (dump_file
, " Scaling nonguarded BBs in loop:");
892 for (unsigned int i
= 0; i
< loop
->num_nodes
; i
++)
894 basic_block bb
= body
[i
];
895 if (!dominated_by_p (CDI_DOMINATORS
, bb
, not_guard
->dest
))
897 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
898 fprintf (dump_file
, " %i", bb
->index
);
899 if (e
->probability
.initialized_p ())
900 scale_bbs_frequencies_int (&bb
, 1,
901 e
->probability
.to_reg_br_prob_base (),
907 set_immediate_dominator (CDI_DOMINATORS
, exit
->dest
, pre_header
);
908 /* Add NEW_ADGE argument for all phi in post-header block. */
910 for (gphi_iterator gsi
= gsi_start_phis (bb
);
911 !gsi_end_p (gsi
); gsi_next (&gsi
))
913 gphi
*phi
= gsi
.phi ();
915 if (virtual_operand_p (gimple_phi_result (phi
)))
917 arg
= get_vop_from_header (loop
);
918 if (arg
== NULL_TREE
)
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 /* Use exit edge argument. */
926 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
927 add_phi_arg (phi
, arg
, new_edge
, UNKNOWN_LOCATION
);
931 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
932 fprintf (dump_file
, "\n guard hoisted.\n");
937 /* Return true if phi argument for exit edge can be used
938 for edge around loop. */
941 check_exit_phi (struct loop
*loop
)
943 edge exit
= single_exit (loop
);
944 basic_block pre_header
= loop_preheader_edge (loop
)->src
;
946 for (gphi_iterator gsi
= gsi_start_phis (exit
->dest
);
947 !gsi_end_p (gsi
); gsi_next (&gsi
))
949 gphi
*phi
= gsi
.phi ();
953 if (virtual_operand_p (gimple_phi_result (phi
)))
955 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
956 if (TREE_CODE (arg
) != SSA_NAME
)
958 def
= SSA_NAME_DEF_STMT (arg
);
961 def_bb
= gimple_bb (def
);
964 if (!dominated_by_p (CDI_DOMINATORS
, pre_header
, def_bb
))
965 /* Definition inside loop! */
967 /* Check loop closed phi invariant. */
968 if (!flow_bb_inside_loop_p (def_bb
->loop_father
, pre_header
))
974 /* Loop unswitching pass. */
978 const pass_data pass_data_tree_unswitch
=
980 GIMPLE_PASS
, /* type */
981 "unswitch", /* name */
982 OPTGROUP_LOOP
, /* optinfo_flags */
983 TV_TREE_LOOP_UNSWITCH
, /* tv_id */
984 PROP_cfg
, /* properties_required */
985 0, /* properties_provided */
986 0, /* properties_destroyed */
987 0, /* todo_flags_start */
988 0, /* todo_flags_finish */
991 class pass_tree_unswitch
: public gimple_opt_pass
994 pass_tree_unswitch (gcc::context
*ctxt
)
995 : gimple_opt_pass (pass_data_tree_unswitch
, ctxt
)
998 /* opt_pass methods: */
999 virtual bool gate (function
*) { return flag_unswitch_loops
!= 0; }
1000 virtual unsigned int execute (function
*);
1002 }; // class pass_tree_unswitch
1005 pass_tree_unswitch::execute (function
*fun
)
1007 if (number_of_loops (fun
) <= 1)
1010 return tree_ssa_unswitch_loops ();
1016 make_pass_tree_unswitch (gcc::context
*ctxt
)
1018 return new pass_tree_unswitch (ctxt
);