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 int p
= prob_true
.initialized_p () ? prob_true
.to_reg_br_prob_base ()
494 : REG_BR_PROB_BASE
/ 2;
495 return loop_version (loop
, unshare_expr (cond
),
498 p
, REG_BR_PROB_BASE
- p
,
502 /* Unswitch outer loops by hoisting invariant guard on
503 inner loop without code duplication. */
505 tree_unswitch_outer_loop (struct loop
*loop
)
508 HOST_WIDE_INT iterations
;
510 gcc_assert (loop
->inner
);
511 if (loop
->inner
->next
)
513 /* Accept loops with single exit only which is not from inner loop. */
514 exit
= single_exit (loop
);
515 if (!exit
|| exit
->src
->loop_father
!= loop
)
517 /* Check that phi argument of exit edge is not defined inside loop. */
518 if (!check_exit_phi (loop
))
520 /* If the loop is not expected to iterate, there is no need
522 iterations
= estimated_loop_iterations_int (loop
);
524 iterations
= likely_max_loop_iterations_int (loop
);
525 if (iterations
>= 0 && iterations
<= 1)
527 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
528 fprintf (dump_file
, ";; Not unswitching, loop is not expected"
533 bool changed
= false;
534 while ((guard
= find_loop_guard (loop
)))
537 rewrite_virtuals_into_loop_closed_ssa (loop
);
538 hoist_guard (loop
, guard
);
544 /* Checks if the body of the LOOP is within an invariant guard. If this
545 is the case, returns the edge that jumps over the real body of the loop,
546 otherwise returns NULL. */
549 find_loop_guard (struct loop
*loop
)
551 basic_block header
= loop
->header
;
552 edge guard_edge
, te
, fe
;
553 basic_block
*body
= NULL
;
558 /* We check for the following situation:
567 nvar = phi(orig, bvar) ... for all variables changed in body;
577 1) cond1 is loop invariant
578 2) If cond1 is false, then the loop is essentially empty; i.e.,
579 a) nothing in something1, something2 and something3 has side
581 b) anything defined in something1, something2 and something3
582 is not used outside of the loop. */
587 if (single_succ_p (header
))
588 header
= single_succ (header
);
591 cond
= dyn_cast
<gcond
*> (last_stmt (header
));
594 extract_true_false_edges_from_block (header
, &te
, &fe
);
595 /* Make sure to skip earlier hoisted guards that are left
596 in place as if (true). */
597 if (gimple_cond_true_p (cond
))
599 else if (gimple_cond_false_p (cond
))
606 if (!flow_bb_inside_loop_p (loop
, te
->dest
)
607 || !flow_bb_inside_loop_p (loop
, fe
->dest
))
610 if (just_once_each_iteration_p (loop
, te
->dest
)
611 || (single_succ_p (te
->dest
)
612 && just_once_each_iteration_p (loop
, single_succ (te
->dest
))))
614 if (just_once_each_iteration_p (loop
, fe
->dest
))
618 else if (just_once_each_iteration_p (loop
, fe
->dest
)
619 || (single_succ_p (fe
->dest
)
620 && just_once_each_iteration_p (loop
, single_succ (fe
->dest
))))
625 /* Guard edge must skip inner loop. */
626 if (!dominated_by_p (CDI_DOMINATORS
, loop
->inner
->header
,
627 guard_edge
== fe
? te
->dest
: fe
->dest
))
629 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
630 fprintf (dump_file
, "Guard edge %d --> %d is not around the loop!\n",
631 guard_edge
->src
->index
, guard_edge
->dest
->index
);
634 if (guard_edge
->dest
== loop
->latch
)
636 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
637 fprintf (dump_file
, "Guard edge destination is loop latch.\n");
641 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
643 "Considering guard %d -> %d in loop %d\n",
644 guard_edge
->src
->index
, guard_edge
->dest
->index
, loop
->num
);
645 /* Check if condition operands do not have definitions inside loop since
646 any bb copying is not performed. */
647 FOR_EACH_SSA_TREE_OPERAND (use
, cond
, iter
, SSA_OP_USE
)
649 gimple
*def
= SSA_NAME_DEF_STMT (use
);
650 basic_block def_bb
= gimple_bb (def
);
652 && flow_bb_inside_loop_p (loop
, def_bb
))
654 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
655 fprintf (dump_file
, " guard operands have definitions"
661 body
= get_loop_body (loop
);
662 for (i
= 0; i
< loop
->num_nodes
; i
++)
664 basic_block bb
= body
[i
];
665 if (bb
->loop_father
!= loop
)
667 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
669 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
670 fprintf (dump_file
, "Block %d is marked as irreducible in loop\n",
675 if (!empty_bb_without_guard_p (loop
, bb
))
677 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
678 fprintf (dump_file
, " block %d has side effects\n", bb
->index
);
684 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
685 fprintf (dump_file
, " suitable to hoist\n");
693 1) no statement in BB has side effects
694 2) assuming that edge GUARD is always taken, all definitions in BB
695 are noy used outside of the loop.
696 KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
697 PROCESSED is a set of ssa names for that we already tested whether they
698 are invariant or not. */
701 empty_bb_without_guard_p (struct loop
*loop
, basic_block bb
)
703 basic_block exit_bb
= single_exit (loop
)->src
;
704 bool may_be_used_outside
= (bb
== exit_bb
705 || !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
));
709 /* Phi nodes do not have side effects, but their results might be used
710 outside of the loop. */
711 if (may_be_used_outside
)
713 for (gphi_iterator gsi
= gsi_start_phis (bb
);
714 !gsi_end_p (gsi
); gsi_next (&gsi
))
716 gphi
*phi
= gsi
.phi ();
717 name
= PHI_RESULT (phi
);
718 if (virtual_operand_p (name
))
721 if (used_outside_loop_p (loop
, name
))
726 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
727 !gsi_end_p (gsi
); gsi_next (&gsi
))
729 gimple
*stmt
= gsi_stmt (gsi
);
730 if (gimple_has_side_effects (stmt
))
733 if (gimple_vdef(stmt
))
736 FOR_EACH_SSA_TREE_OPERAND (name
, stmt
, op_iter
, SSA_OP_DEF
)
738 if (may_be_used_outside
739 && used_outside_loop_p (loop
, name
))
746 /* Return true if NAME is used outside of LOOP. */
749 used_outside_loop_p (struct loop
*loop
, tree name
)
754 FOR_EACH_IMM_USE_FAST (use
, it
, name
)
756 gimple
*stmt
= USE_STMT (use
);
757 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
764 /* Return argument for loop preheader edge in header virtual phi if any. */
767 get_vop_from_header (struct loop
*loop
)
769 for (gphi_iterator gsi
= gsi_start_phis (loop
->header
);
770 !gsi_end_p (gsi
); gsi_next (&gsi
))
772 gphi
*phi
= gsi
.phi ();
773 if (!virtual_operand_p (gimple_phi_result (phi
)))
775 return PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
780 /* Move the check of GUARD outside of LOOP. */
783 hoist_guard (struct loop
*loop
, edge guard
)
785 edge exit
= single_exit (loop
);
786 edge preh
= loop_preheader_edge (loop
);
787 basic_block pre_header
= preh
->src
;
789 edge te
, fe
, e
, new_edge
;
791 basic_block guard_bb
= guard
->src
;
793 gimple_stmt_iterator gsi
;
795 bool fix_dom_of_exit
;
796 gcond
*cond_stmt
, *new_cond_stmt
;
798 bb
= get_immediate_dominator (CDI_DOMINATORS
, exit
->dest
);
799 fix_dom_of_exit
= flow_bb_inside_loop_p (loop
, bb
);
800 gsi
= gsi_last_bb (guard_bb
);
801 stmt
= gsi_stmt (gsi
);
802 gcc_assert (gimple_code (stmt
) == GIMPLE_COND
);
803 cond_stmt
= as_a
<gcond
*> (stmt
);
804 extract_true_false_edges_from_block (guard_bb
, &te
, &fe
);
805 /* Insert guard to PRE_HEADER. */
806 if (!empty_block_p (pre_header
))
807 gsi
= gsi_last_bb (pre_header
);
809 gsi
= gsi_start_bb (pre_header
);
810 /* Create copy of COND_STMT. */
811 new_cond_stmt
= gimple_build_cond (gimple_cond_code (cond_stmt
),
812 gimple_cond_lhs (cond_stmt
),
813 gimple_cond_rhs (cond_stmt
),
814 NULL_TREE
, NULL_TREE
);
815 gsi_insert_after (&gsi
, new_cond_stmt
, GSI_NEW_STMT
);
816 /* Convert COND_STMT to true/false conditional. */
818 gimple_cond_make_false (cond_stmt
);
820 gimple_cond_make_true (cond_stmt
);
821 update_stmt (cond_stmt
);
822 /* Create new loop pre-header. */
823 e
= split_block (pre_header
, last_stmt (pre_header
));
824 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
826 fprintf (dump_file
, " Moving guard %i->%i (prob ",
827 guard
->src
->index
, guard
->dest
->index
);
828 guard
->probability
.dump (dump_file
);
829 fprintf (dump_file
, ") to bb %i, new preheader is %i\n",
830 e
->src
->index
, e
->dest
->index
);
833 gcc_assert (loop_preheader_edge (loop
)->src
== e
->dest
);
837 e
->flags
= EDGE_TRUE_VALUE
;
838 flags
|= EDGE_FALSE_VALUE
;
843 e
->flags
= EDGE_FALSE_VALUE
;
844 flags
|= EDGE_TRUE_VALUE
;
847 new_edge
= make_edge (pre_header
, exit
->dest
, flags
);
849 /* Determine the probability that we skip the loop. Assume that loop has
850 same average number of iterations regardless outcome of guard. */
851 new_edge
->probability
= guard
->probability
;
852 profile_count skip_count
= guard
->src
->count
> 0
853 ? guard
->count
.apply_scale (pre_header
->count
,
855 : guard
->count
.apply_probability (new_edge
->probability
);
857 if (skip_count
> e
->count
)
859 fprintf (dump_file
, " Capping count; expect profile inconsistency\n");
860 skip_count
= e
->count
;
862 new_edge
->count
= skip_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
->count
-= skip_count
;
875 e
->probability
= new_edge
->probability
.invert ();
876 e
->dest
->count
= e
->count
;
877 e
->dest
->frequency
= EDGE_FREQUENCY (e
);
879 /* ... now update profile to represent that original guard will be optimized
881 guard
->probability
= profile_probability::never ();
882 guard
->count
= profile_count::zero ();
883 not_guard
->probability
= profile_probability::always ();
884 /* This count is wrong (frequency of not_guard does not change),
885 but will be scaled later. */
886 not_guard
->count
= guard
->src
->count
;
888 /* ... finally scale everything in the loop except for guarded basic blocks
889 where profile does not change. */
890 basic_block
*body
= get_loop_body (loop
);
892 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
893 fprintf (dump_file
, " Scaling nonguarded BBs in loop:");
894 for (unsigned int i
= 0; i
< loop
->num_nodes
; i
++)
896 basic_block bb
= body
[i
];
897 if (!dominated_by_p (CDI_DOMINATORS
, bb
, not_guard
->dest
))
899 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
900 fprintf (dump_file
, " %i", bb
->index
);
901 if (e
->probability
.initialized_p ())
902 scale_bbs_frequencies_int (&bb
, 1,
903 e
->probability
.to_reg_br_prob_base (),
909 set_immediate_dominator (CDI_DOMINATORS
, exit
->dest
, pre_header
);
910 /* Add NEW_ADGE argument for all phi in post-header block. */
912 for (gphi_iterator gsi
= gsi_start_phis (bb
);
913 !gsi_end_p (gsi
); gsi_next (&gsi
))
915 gphi
*phi
= gsi
.phi ();
917 if (virtual_operand_p (gimple_phi_result (phi
)))
919 arg
= get_vop_from_header (loop
);
920 if (arg
== NULL_TREE
)
921 /* Use exit edge argument. */
922 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
923 add_phi_arg (phi
, arg
, new_edge
, UNKNOWN_LOCATION
);
927 /* Use exit edge argument. */
928 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
929 add_phi_arg (phi
, arg
, new_edge
, UNKNOWN_LOCATION
);
933 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
934 fprintf (dump_file
, "\n guard hoisted.\n");
939 /* Return true if phi argument for exit edge can be used
940 for edge around loop. */
943 check_exit_phi (struct loop
*loop
)
945 edge exit
= single_exit (loop
);
946 basic_block pre_header
= loop_preheader_edge (loop
)->src
;
948 for (gphi_iterator gsi
= gsi_start_phis (exit
->dest
);
949 !gsi_end_p (gsi
); gsi_next (&gsi
))
951 gphi
*phi
= gsi
.phi ();
955 if (virtual_operand_p (gimple_phi_result (phi
)))
957 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
958 if (TREE_CODE (arg
) != SSA_NAME
)
960 def
= SSA_NAME_DEF_STMT (arg
);
963 def_bb
= gimple_bb (def
);
966 if (!dominated_by_p (CDI_DOMINATORS
, pre_header
, def_bb
))
967 /* Definition inside loop! */
969 /* Check loop closed phi invariant. */
970 if (!flow_bb_inside_loop_p (def_bb
->loop_father
, pre_header
))
976 /* Loop unswitching pass. */
980 const pass_data pass_data_tree_unswitch
=
982 GIMPLE_PASS
, /* type */
983 "unswitch", /* name */
984 OPTGROUP_LOOP
, /* optinfo_flags */
985 TV_TREE_LOOP_UNSWITCH
, /* tv_id */
986 PROP_cfg
, /* properties_required */
987 0, /* properties_provided */
988 0, /* properties_destroyed */
989 0, /* todo_flags_start */
990 0, /* todo_flags_finish */
993 class pass_tree_unswitch
: public gimple_opt_pass
996 pass_tree_unswitch (gcc::context
*ctxt
)
997 : gimple_opt_pass (pass_data_tree_unswitch
, ctxt
)
1000 /* opt_pass methods: */
1001 virtual bool gate (function
*) { return flag_unswitch_loops
!= 0; }
1002 virtual unsigned int execute (function
*);
1004 }; // class pass_tree_unswitch
1007 pass_tree_unswitch::execute (function
*fun
)
1009 if (number_of_loops (fun
) <= 1)
1012 return tree_ssa_unswitch_loops ();
1018 make_pass_tree_unswitch (gcc::context
*ctxt
)
1020 return new pass_tree_unswitch (ctxt
);