2 Copyright (C) 2004-2015 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"
27 #include "hard-reg-set.h"
30 #include "fold-const.h"
32 #include "internal-fn.h"
36 #include "tree-ssa-loop-niter.h"
37 #include "tree-ssa-loop.h"
38 #include "tree-into-ssa.h"
41 #include "tree-pass.h"
42 #include "tree-inline.h"
43 #include "gimple-iterator.h"
46 /* This file implements the loop unswitching, i.e. transformation of loops like
59 where inv is the loop invariant, into
78 Inv is considered invariant iff the values it compares are both invariant;
79 tree-ssa-loop-im.c ensures that all the suitable conditions are in this
82 static struct loop
*tree_unswitch_loop (struct loop
*, basic_block
, tree
);
83 static bool tree_unswitch_single_loop (struct loop
*, int);
84 static tree
tree_may_unswitch_on (basic_block
, struct loop
*);
85 static bool tree_unswitch_outer_loop (struct loop
*);
86 static edge
find_loop_guard (struct loop
*);
87 static bool empty_bb_without_guard_p (struct loop
*, basic_block
);
88 static bool used_outside_loop_p (struct loop
*, tree
);
89 static void hoist_guard (struct loop
*, edge
);
90 static bool check_exit_phi (struct loop
*);
91 static tree
get_vop_from_header (struct loop
*);
93 /* Main entry point. Perform loop unswitching on all suitable loops. */
96 tree_ssa_unswitch_loops (void)
101 /* Go through all loops starting from innermost. */
102 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
105 /* Unswitch innermost loop. */
106 changed
|= tree_unswitch_single_loop (loop
, 0);
108 changed
|= tree_unswitch_outer_loop (loop
);
112 return TODO_cleanup_cfg
;
116 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
117 basic blocks (for what it means see comments below). */
120 tree_may_unswitch_on (basic_block bb
, struct loop
*loop
)
128 /* BB must end in a simple conditional jump. */
129 last
= last_stmt (bb
);
130 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
132 stmt
= as_a
<gcond
*> (last
);
134 /* To keep the things simple, we do not directly remove the conditions,
135 but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite
136 loop where we would unswitch again on such a condition. */
137 if (gimple_cond_true_p (stmt
) || gimple_cond_false_p (stmt
))
140 /* Condition must be invariant. */
141 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
143 /* Unswitching on undefined values would introduce undefined
144 behavior that the original program might never exercise. */
145 if (ssa_undefined_value_p (use
, true))
147 def
= SSA_NAME_DEF_STMT (use
);
148 def_bb
= gimple_bb (def
);
150 && flow_bb_inside_loop_p (loop
, def_bb
))
154 cond
= build2 (gimple_cond_code (stmt
), boolean_type_node
,
155 gimple_cond_lhs (stmt
), gimple_cond_rhs (stmt
));
160 /* Simplifies COND using checks in front of the entry of the LOOP. Just very
161 simplish (sufficient to prevent us from duplicating loop in unswitching
165 simplify_using_entry_checks (struct loop
*loop
, tree cond
)
167 edge e
= loop_preheader_edge (loop
);
172 stmt
= last_stmt (e
->src
);
174 && gimple_code (stmt
) == GIMPLE_COND
175 && gimple_cond_code (stmt
) == TREE_CODE (cond
)
176 && operand_equal_p (gimple_cond_lhs (stmt
),
177 TREE_OPERAND (cond
, 0), 0)
178 && operand_equal_p (gimple_cond_rhs (stmt
),
179 TREE_OPERAND (cond
, 1), 0))
180 return (e
->flags
& EDGE_TRUE_VALUE
182 : boolean_false_node
);
184 if (!single_pred_p (e
->src
))
187 e
= single_pred_edge (e
->src
);
188 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
193 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow
194 it to grow too much, it is too easy to create example on that the code would
195 grow exponentially. */
198 tree_unswitch_single_loop (struct loop
*loop
, int num
)
203 tree cond
= NULL_TREE
;
205 bool changed
= false;
206 HOST_WIDE_INT iterations
;
208 /* Perform initial tests if unswitch is eligible. */
211 /* Do not unswitch in cold regions. */
212 if (optimize_loop_for_size_p (loop
))
214 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
215 fprintf (dump_file
, ";; Not unswitching cold loops\n");
219 /* The loop should not be too large, to limit code growth. */
220 if (tree_num_loop_insns (loop
, &eni_size_weights
)
221 > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS
))
223 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
224 fprintf (dump_file
, ";; Not unswitching, loop too big\n");
228 /* If the loop is not expected to iterate, there is no need
230 iterations
= estimated_loop_iterations_int (loop
);
231 if (iterations
>= 0 && iterations
<= 1)
233 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
234 fprintf (dump_file
, ";; Not unswitching, loop is not expected"
241 bbs
= get_loop_body (loop
);
242 found
= loop
->num_nodes
;
246 /* Find a bb to unswitch on. */
247 for (; i
< loop
->num_nodes
; i
++)
248 if ((cond
= tree_may_unswitch_on (bbs
[i
], loop
)))
251 if (i
== loop
->num_nodes
)
254 && num
> PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL
)
255 && (dump_flags
& TDF_DETAILS
))
256 fprintf (dump_file
, ";; Not unswitching anymore, hit max level\n");
258 if (found
== loop
->num_nodes
)
266 cond
= simplify_using_entry_checks (loop
, cond
);
267 stmt
= last_stmt (bbs
[i
]);
268 if (integer_nonzerop (cond
))
270 /* Remove false path. */
271 gimple_cond_set_condition_from_tree (as_a
<gcond
*> (stmt
),
275 else if (integer_zerop (cond
))
277 /* Remove true path. */
278 gimple_cond_set_condition_from_tree (as_a
<gcond
*> (stmt
),
282 /* Do not unswitch too much. */
283 else if (num
> PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL
))
288 /* In nested tree_unswitch_single_loop first optimize all conditions
289 using entry checks, then discover still reachable blocks in the
290 loop and find the condition only among those still reachable bbs. */
293 if (found
== loop
->num_nodes
)
310 basic_block
*tos
, *worklist
;
312 /* When called recursively, first do a quick discovery
313 of reachable bbs after the above changes and only
314 consider conditions in still reachable bbs. */
315 tos
= worklist
= XNEWVEC (basic_block
, loop
->num_nodes
);
317 for (i
= 0; i
< loop
->num_nodes
; i
++)
318 bbs
[i
]->flags
&= ~BB_REACHABLE
;
320 /* Start with marking header. */
322 bbs
[0]->flags
|= BB_REACHABLE
;
324 /* Iterate: find everything reachable from what we've already seen
325 within the same innermost loop. Don't look through false edges
326 if condition is always true or true edges if condition is
328 while (tos
!= worklist
)
330 basic_block b
= *--tos
;
335 if (EDGE_COUNT (b
->succs
) == 2)
337 gimple
*stmt
= last_stmt (b
);
339 && gimple_code (stmt
) == GIMPLE_COND
)
341 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
342 if (gimple_cond_true_p (cond_stmt
))
343 flags
= EDGE_FALSE_VALUE
;
344 else if (gimple_cond_false_p (cond_stmt
))
345 flags
= EDGE_TRUE_VALUE
;
349 FOR_EACH_EDGE (e
, ei
, b
->succs
)
351 basic_block dest
= e
->dest
;
353 if (dest
->loop_father
== loop
354 && !(dest
->flags
& BB_REACHABLE
)
355 && !(e
->flags
& flags
))
358 dest
->flags
|= BB_REACHABLE
;
365 /* Find a bb to unswitch on. */
366 for (; found
< loop
->num_nodes
; found
++)
367 if ((bbs
[found
]->flags
& BB_REACHABLE
)
368 && (cond
= tree_may_unswitch_on (bbs
[found
], loop
)))
371 if (found
== loop
->num_nodes
)
378 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
379 fprintf (dump_file
, ";; Unswitching loop\n");
381 initialize_original_copy_tables ();
382 /* Unswitch the loop on this condition. */
383 nloop
= tree_unswitch_loop (loop
, bbs
[found
], cond
);
386 free_original_copy_tables ();
391 /* Update the SSA form after unswitching. */
392 update_ssa (TODO_update_ssa
);
393 free_original_copy_tables ();
395 /* Invoke itself on modified loops. */
396 tree_unswitch_single_loop (nloop
, num
+ 1);
397 tree_unswitch_single_loop (loop
, num
+ 1);
402 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
403 unswitching of innermost loops. COND is the condition determining which
404 loop is entered -- the new loop is entered if COND is true. Returns NULL
405 if impossible, new loop otherwise. */
408 tree_unswitch_loop (struct loop
*loop
,
409 basic_block unswitch_on
, tree cond
)
412 edge edge_true
, edge_false
;
414 /* Some sanity checking. */
415 gcc_assert (flow_bb_inside_loop_p (loop
, unswitch_on
));
416 gcc_assert (EDGE_COUNT (unswitch_on
->succs
) == 2);
417 gcc_assert (loop
->inner
== NULL
);
419 extract_true_false_edges_from_block (unswitch_on
, &edge_true
, &edge_false
);
420 prob_true
= edge_true
->probability
;
421 return loop_version (loop
, unshare_expr (cond
),
422 NULL
, prob_true
, prob_true
,
423 REG_BR_PROB_BASE
- prob_true
, false);
426 /* Unswitch outer loops by hoisting invariant guard on
427 inner loop without code duplication. */
429 tree_unswitch_outer_loop (struct loop
*loop
)
432 HOST_WIDE_INT iterations
;
434 gcc_assert (loop
->inner
);
435 if (loop
->inner
->next
)
437 /* Accept loops with single exit only. */
438 exit
= single_exit (loop
);
441 /* Check that phi argument of exit edge is not defined inside loop. */
442 if (!check_exit_phi (loop
))
444 /* If the loop is not expected to iterate, there is no need
446 iterations
= estimated_loop_iterations_int (loop
);
447 if (iterations
>= 0 && iterations
<= 1)
449 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
450 fprintf (dump_file
, ";; Not unswitching, loop is not expected"
455 guard
= find_loop_guard (loop
);
458 hoist_guard (loop
, guard
);
459 update_ssa (TODO_update_ssa
);
465 /* Checks if the body of the LOOP is within an invariant guard. If this
466 is the case, returns the edge that jumps over the real body of the loop,
467 otherwise returns NULL. */
470 find_loop_guard (struct loop
*loop
)
472 basic_block header
= loop
->header
;
473 edge guard_edge
, te
, fe
;
474 basic_block
*body
= NULL
;
479 /* We check for the following situation:
488 nvar = phi(orig, bvar) ... for all variables changed in body;
498 1) cond1 is loop invariant
499 2) If cond1 is false, then the loop is essentially empty; i.e.,
500 a) nothing in something1, something2 and something3 has side
502 b) anything defined in something1, something2 and something3
503 is not used outside of the loop. */
505 while (single_succ_p (header
))
506 header
= single_succ (header
);
507 if (!last_stmt (header
)
508 || gimple_code (last_stmt (header
)) != GIMPLE_COND
)
511 extract_true_false_edges_from_block (header
, &te
, &fe
);
512 if (!flow_bb_inside_loop_p (loop
, te
->dest
)
513 || !flow_bb_inside_loop_p (loop
, fe
->dest
))
516 if (just_once_each_iteration_p (loop
, te
->dest
)
517 || (single_succ_p (te
->dest
)
518 && just_once_each_iteration_p (loop
, single_succ (te
->dest
))))
520 if (just_once_each_iteration_p (loop
, fe
->dest
))
524 else if (just_once_each_iteration_p (loop
, fe
->dest
)
525 || (single_succ_p (fe
->dest
)
526 && just_once_each_iteration_p (loop
, single_succ (fe
->dest
))))
531 /* Guard edge must skip inner loop. */
532 if (!dominated_by_p (CDI_DOMINATORS
, loop
->inner
->header
,
533 guard_edge
== fe
? te
->dest
: fe
->dest
))
535 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
536 fprintf (dump_file
, "Guard edge %d --> %d is not around the loop!\n",
537 guard_edge
->src
->index
, guard_edge
->dest
->index
);
541 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
543 "Considering guard %d -> %d in loop %d\n",
544 guard_edge
->src
->index
, guard_edge
->dest
->index
, loop
->num
);
545 /* Check if condition operands do not have definitions inside loop since
546 any bb copying is not performed. */
547 FOR_EACH_SSA_TREE_OPERAND (use
, last_stmt (header
), iter
, SSA_OP_USE
)
549 gimple
*def
= SSA_NAME_DEF_STMT (use
);
550 basic_block def_bb
= gimple_bb (def
);
552 && flow_bb_inside_loop_p (loop
, def_bb
))
554 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
555 fprintf (dump_file
, " guard operands have definitions"
561 body
= get_loop_body (loop
);
562 for (i
= 0; i
< loop
->num_nodes
; i
++)
564 basic_block bb
= body
[i
];
565 if (bb
->loop_father
!= loop
)
567 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
569 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
570 fprintf (dump_file
, "Block %d is marked as irreducible in loop\n",
575 if (!empty_bb_without_guard_p (loop
, bb
))
577 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
578 fprintf (dump_file
, " block %d has side effects\n", bb
->index
);
584 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
585 fprintf (dump_file
, " suitable to hoist\n");
593 1) no statement in BB has side effects
594 2) assuming that edge GUARD is always taken, all definitions in BB
595 are noy used outside of the loop.
596 KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
597 PROCESSED is a set of ssa names for that we already tested whether they
598 are invariant or not. */
601 empty_bb_without_guard_p (struct loop
*loop
, basic_block bb
)
603 basic_block exit_bb
= single_exit (loop
)->src
;
604 bool may_be_used_outside
= (bb
== exit_bb
605 || !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
));
609 /* Phi nodes do not have side effects, but their results might be used
610 outside of the loop. */
611 if (may_be_used_outside
)
613 for (gphi_iterator gsi
= gsi_start_phis (bb
);
614 !gsi_end_p (gsi
); gsi_next (&gsi
))
616 gphi
*phi
= gsi
.phi ();
617 name
= PHI_RESULT (phi
);
618 if (virtual_operand_p (name
))
621 if (used_outside_loop_p (loop
, name
))
626 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
627 !gsi_end_p (gsi
); gsi_next (&gsi
))
629 gimple
*stmt
= gsi_stmt (gsi
);
630 if (gimple_has_side_effects (stmt
))
633 if (gimple_vdef(stmt
))
636 FOR_EACH_SSA_TREE_OPERAND (name
, stmt
, op_iter
, SSA_OP_DEF
)
638 if (may_be_used_outside
639 && used_outside_loop_p (loop
, name
))
646 /* Return true if NAME is used outside of LOOP. */
649 used_outside_loop_p (struct loop
*loop
, tree name
)
654 FOR_EACH_IMM_USE_FAST (use
, it
, name
)
656 gimple
*stmt
= USE_STMT (use
);
657 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
664 /* Return argument for loop preheader edge in header virtual phi if any. */
667 get_vop_from_header (struct loop
*loop
)
669 for (gphi_iterator gsi
= gsi_start_phis (loop
->header
);
670 !gsi_end_p (gsi
); gsi_next (&gsi
))
672 gphi
*phi
= gsi
.phi ();
673 if (!virtual_operand_p (gimple_phi_result (phi
)))
675 return PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
680 /* Move the check of GUARD outside of LOOP. */
683 hoist_guard (struct loop
*loop
, edge guard
)
685 edge exit
= single_exit (loop
);
686 edge preh
= loop_preheader_edge (loop
);
687 basic_block pre_header
= preh
->src
;
689 edge te
, fe
, e
, new_edge
;
691 basic_block guard_bb
= guard
->src
;
692 gimple_stmt_iterator gsi
;
694 bool fix_dom_of_exit
;
695 gcond
*cond_stmt
, *new_cond_stmt
;
697 bb
= get_immediate_dominator (CDI_DOMINATORS
, exit
->dest
);
698 fix_dom_of_exit
= flow_bb_inside_loop_p (loop
, bb
);
699 gsi
= gsi_last_bb (guard_bb
);
700 stmt
= gsi_stmt (gsi
);
701 gcc_assert (gimple_code (stmt
) == GIMPLE_COND
);
702 cond_stmt
= as_a
<gcond
*> (stmt
);
703 extract_true_false_edges_from_block (guard_bb
, &te
, &fe
);
704 /* Insert guard to PRE_HEADER. */
705 if (!empty_block_p (pre_header
))
706 gsi
= gsi_last_bb (pre_header
);
708 gsi
= gsi_start_bb (pre_header
);
709 /* Create copy of COND_STMT. */
710 new_cond_stmt
= gimple_build_cond (gimple_cond_code (cond_stmt
),
711 gimple_cond_lhs (cond_stmt
),
712 gimple_cond_rhs (cond_stmt
),
713 NULL_TREE
, NULL_TREE
);
714 gsi_insert_after (&gsi
, new_cond_stmt
, GSI_NEW_STMT
);
715 /* Convert COND_STMT to true/false conditional. */
717 gimple_cond_make_false (cond_stmt
);
719 gimple_cond_make_true (cond_stmt
);
720 update_stmt (cond_stmt
);
721 /* Create new loop pre-header. */
722 e
= split_block (pre_header
, last_stmt (pre_header
));
723 gcc_assert (loop_preheader_edge (loop
)->src
== e
->dest
);
726 e
->flags
= EDGE_TRUE_VALUE
;
727 flags
|= EDGE_FALSE_VALUE
;
731 e
->flags
= EDGE_FALSE_VALUE
;
732 flags
|= EDGE_TRUE_VALUE
;
734 new_edge
= make_edge (pre_header
, exit
->dest
, flags
);
736 set_immediate_dominator (CDI_DOMINATORS
, exit
->dest
, pre_header
);
737 /* Add NEW_ADGE argument for all phi in post-header block. */
739 for (gphi_iterator gsi
= gsi_start_phis (bb
);
740 !gsi_end_p (gsi
); gsi_next (&gsi
))
742 gphi
*phi
= gsi
.phi ();
744 if (virtual_operand_p (gimple_phi_result (phi
)))
746 arg
= get_vop_from_header (loop
);
747 if (arg
== NULL_TREE
)
748 /* Use exit edge argument. */
749 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
750 add_phi_arg (phi
, arg
, new_edge
, UNKNOWN_LOCATION
);
754 /* Use exit edge argument. */
755 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
756 add_phi_arg (phi
, arg
, new_edge
, UNKNOWN_LOCATION
);
760 mark_virtual_operands_for_renaming (cfun
);
761 update_ssa (TODO_update_ssa
);
762 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
763 fprintf (dump_file
, " guard hoisted.\n");
766 /* Return true if phi argument for exit edge can be used
767 for edge around loop. */
770 check_exit_phi (struct loop
*loop
)
772 edge exit
= single_exit (loop
);
773 basic_block pre_header
= loop_preheader_edge (loop
)->src
;
775 for (gphi_iterator gsi
= gsi_start_phis (exit
->dest
);
776 !gsi_end_p (gsi
); gsi_next (&gsi
))
778 gphi
*phi
= gsi
.phi ();
782 if (virtual_operand_p (gimple_phi_result (phi
)))
784 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
785 if (TREE_CODE (arg
) != SSA_NAME
)
787 def
= SSA_NAME_DEF_STMT (arg
);
790 def_bb
= gimple_bb (def
);
793 if (!dominated_by_p (CDI_DOMINATORS
, pre_header
, def_bb
))
794 /* Definition inside loop! */
796 /* Check loop closed phi invariant. */
797 if (!flow_bb_inside_loop_p (def_bb
->loop_father
, pre_header
))
803 /* Loop unswitching pass. */
807 const pass_data pass_data_tree_unswitch
=
809 GIMPLE_PASS
, /* type */
810 "unswitch", /* name */
811 OPTGROUP_LOOP
, /* optinfo_flags */
812 TV_TREE_LOOP_UNSWITCH
, /* tv_id */
813 PROP_cfg
, /* properties_required */
814 0, /* properties_provided */
815 0, /* properties_destroyed */
816 0, /* todo_flags_start */
817 0, /* todo_flags_finish */
820 class pass_tree_unswitch
: public gimple_opt_pass
823 pass_tree_unswitch (gcc::context
*ctxt
)
824 : gimple_opt_pass (pass_data_tree_unswitch
, ctxt
)
827 /* opt_pass methods: */
828 virtual bool gate (function
*) { return flag_unswitch_loops
!= 0; }
829 virtual unsigned int execute (function
*);
831 }; // class pass_tree_unswitch
834 pass_tree_unswitch::execute (function
*fun
)
836 if (number_of_loops (fun
) <= 1)
839 return tree_ssa_unswitch_loops ();
845 make_pass_tree_unswitch (gcc::context
*ctxt
)
847 return new pass_tree_unswitch (ctxt
);