2 Copyright (C) 2004-2016 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"
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 struct loop
*tree_unswitch_loop (struct loop
*, basic_block
, tree
);
78 static bool tree_unswitch_single_loop (struct loop
*, int);
79 static tree
tree_may_unswitch_on (basic_block
, struct loop
*);
80 static bool tree_unswitch_outer_loop (struct loop
*);
81 static edge
find_loop_guard (struct loop
*);
82 static bool empty_bb_without_guard_p (struct loop
*, basic_block
);
83 static bool used_outside_loop_p (struct loop
*, tree
);
84 static void hoist_guard (struct loop
*, edge
);
85 static bool check_exit_phi (struct loop
*);
86 static tree
get_vop_from_header (struct loop
*);
88 /* Main entry point. Perform loop unswitching on all suitable loops. */
91 tree_ssa_unswitch_loops (void)
96 /* Go through all loops starting from innermost. */
97 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
100 /* Unswitch innermost loop. */
101 changed
|= tree_unswitch_single_loop (loop
, 0);
103 changed
|= tree_unswitch_outer_loop (loop
);
107 return TODO_cleanup_cfg
;
111 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
112 basic blocks (for what it means see comments below). */
115 tree_may_unswitch_on (basic_block bb
, struct loop
*loop
)
123 /* BB must end in a simple conditional jump. */
124 last
= last_stmt (bb
);
125 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
127 stmt
= as_a
<gcond
*> (last
);
129 /* To keep the things simple, we do not directly remove the conditions,
130 but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite
131 loop where we would unswitch again on such a condition. */
132 if (gimple_cond_true_p (stmt
) || gimple_cond_false_p (stmt
))
135 /* Condition must be invariant. */
136 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
138 /* Unswitching on undefined values would introduce undefined
139 behavior that the original program might never exercise. */
140 if (ssa_undefined_value_p (use
, true))
142 def
= SSA_NAME_DEF_STMT (use
);
143 def_bb
= gimple_bb (def
);
145 && flow_bb_inside_loop_p (loop
, def_bb
))
149 cond
= build2 (gimple_cond_code (stmt
), boolean_type_node
,
150 gimple_cond_lhs (stmt
), gimple_cond_rhs (stmt
));
155 /* Simplifies COND using checks in front of the entry of the LOOP. Just very
156 simplish (sufficient to prevent us from duplicating loop in unswitching
160 simplify_using_entry_checks (struct loop
*loop
, tree cond
)
162 edge e
= loop_preheader_edge (loop
);
167 stmt
= last_stmt (e
->src
);
169 && gimple_code (stmt
) == GIMPLE_COND
170 && gimple_cond_code (stmt
) == TREE_CODE (cond
)
171 && operand_equal_p (gimple_cond_lhs (stmt
),
172 TREE_OPERAND (cond
, 0), 0)
173 && operand_equal_p (gimple_cond_rhs (stmt
),
174 TREE_OPERAND (cond
, 1), 0))
175 return (e
->flags
& EDGE_TRUE_VALUE
177 : boolean_false_node
);
179 if (!single_pred_p (e
->src
))
182 e
= single_pred_edge (e
->src
);
183 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
188 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow
189 it to grow too much, it is too easy to create example on that the code would
190 grow exponentially. */
193 tree_unswitch_single_loop (struct loop
*loop
, int num
)
198 tree cond
= NULL_TREE
;
200 bool changed
= false;
201 HOST_WIDE_INT iterations
;
203 /* Perform initial tests if unswitch is eligible. */
206 /* Do not unswitch in cold regions. */
207 if (optimize_loop_for_size_p (loop
))
209 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
210 fprintf (dump_file
, ";; Not unswitching cold loops\n");
214 /* The loop should not be too large, to limit code growth. */
215 if (tree_num_loop_insns (loop
, &eni_size_weights
)
216 > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS
))
218 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
219 fprintf (dump_file
, ";; Not unswitching, loop too big\n");
223 /* If the loop is not expected to iterate, there is no need
225 iterations
= estimated_loop_iterations_int (loop
);
227 iterations
= max_loop_iterations_int (loop
);
228 if (iterations
>= 0 && iterations
<= 1)
230 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
231 fprintf (dump_file
, ";; Not unswitching, loop is not expected"
238 bbs
= get_loop_body (loop
);
239 found
= loop
->num_nodes
;
243 /* Find a bb to unswitch on. */
244 for (; i
< loop
->num_nodes
; i
++)
245 if ((cond
= tree_may_unswitch_on (bbs
[i
], loop
)))
248 if (i
== loop
->num_nodes
)
251 && num
> PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL
)
252 && (dump_flags
& TDF_DETAILS
))
253 fprintf (dump_file
, ";; Not unswitching anymore, hit max level\n");
255 if (found
== loop
->num_nodes
)
263 cond
= simplify_using_entry_checks (loop
, cond
);
264 stmt
= last_stmt (bbs
[i
]);
265 if (integer_nonzerop (cond
))
267 /* Remove false path. */
268 gimple_cond_set_condition_from_tree (as_a
<gcond
*> (stmt
),
272 else if (integer_zerop (cond
))
274 /* Remove true path. */
275 gimple_cond_set_condition_from_tree (as_a
<gcond
*> (stmt
),
279 /* Do not unswitch too much. */
280 else if (num
> PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL
))
285 /* In nested tree_unswitch_single_loop first optimize all conditions
286 using entry checks, then discover still reachable blocks in the
287 loop and find the condition only among those still reachable bbs. */
290 if (found
== loop
->num_nodes
)
307 basic_block
*tos
, *worklist
;
309 /* When called recursively, first do a quick discovery
310 of reachable bbs after the above changes and only
311 consider conditions in still reachable bbs. */
312 tos
= worklist
= XNEWVEC (basic_block
, loop
->num_nodes
);
314 for (i
= 0; i
< loop
->num_nodes
; i
++)
315 bbs
[i
]->flags
&= ~BB_REACHABLE
;
317 /* Start with marking header. */
319 bbs
[0]->flags
|= BB_REACHABLE
;
321 /* Iterate: find everything reachable from what we've already seen
322 within the same innermost loop. Don't look through false edges
323 if condition is always true or true edges if condition is
325 while (tos
!= worklist
)
327 basic_block b
= *--tos
;
332 if (EDGE_COUNT (b
->succs
) == 2)
334 gimple
*stmt
= last_stmt (b
);
336 && gimple_code (stmt
) == GIMPLE_COND
)
338 gcond
*cond_stmt
= as_a
<gcond
*> (stmt
);
339 if (gimple_cond_true_p (cond_stmt
))
340 flags
= EDGE_FALSE_VALUE
;
341 else if (gimple_cond_false_p (cond_stmt
))
342 flags
= EDGE_TRUE_VALUE
;
346 FOR_EACH_EDGE (e
, ei
, b
->succs
)
348 basic_block dest
= e
->dest
;
350 if (dest
->loop_father
== loop
351 && !(dest
->flags
& BB_REACHABLE
)
352 && !(e
->flags
& flags
))
355 dest
->flags
|= BB_REACHABLE
;
362 /* Find a bb to unswitch on. */
363 for (; found
< loop
->num_nodes
; found
++)
364 if ((bbs
[found
]->flags
& BB_REACHABLE
)
365 && (cond
= tree_may_unswitch_on (bbs
[found
], loop
)))
368 if (found
== loop
->num_nodes
)
375 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
376 fprintf (dump_file
, ";; Unswitching loop\n");
378 initialize_original_copy_tables ();
379 /* Unswitch the loop on this condition. */
380 nloop
= tree_unswitch_loop (loop
, bbs
[found
], cond
);
383 free_original_copy_tables ();
388 /* Update the SSA form after unswitching. */
389 update_ssa (TODO_update_ssa
);
390 free_original_copy_tables ();
392 /* Invoke itself on modified loops. */
393 tree_unswitch_single_loop (nloop
, num
+ 1);
394 tree_unswitch_single_loop (loop
, num
+ 1);
399 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
400 unswitching of innermost loops. COND is the condition determining which
401 loop is entered -- the new loop is entered if COND is true. Returns NULL
402 if impossible, new loop otherwise. */
405 tree_unswitch_loop (struct loop
*loop
,
406 basic_block unswitch_on
, tree cond
)
409 edge edge_true
, edge_false
;
411 /* Some sanity checking. */
412 gcc_assert (flow_bb_inside_loop_p (loop
, unswitch_on
));
413 gcc_assert (EDGE_COUNT (unswitch_on
->succs
) == 2);
414 gcc_assert (loop
->inner
== NULL
);
416 extract_true_false_edges_from_block (unswitch_on
, &edge_true
, &edge_false
);
417 prob_true
= edge_true
->probability
;
418 return loop_version (loop
, unshare_expr (cond
),
419 NULL
, prob_true
, prob_true
,
420 REG_BR_PROB_BASE
- prob_true
, false);
423 /* Unswitch outer loops by hoisting invariant guard on
424 inner loop without code duplication. */
426 tree_unswitch_outer_loop (struct loop
*loop
)
429 HOST_WIDE_INT iterations
;
431 gcc_assert (loop
->inner
);
432 if (loop
->inner
->next
)
434 /* Accept loops with single exit only which is not from inner loop. */
435 exit
= single_exit (loop
);
436 if (!exit
|| exit
->src
->loop_father
!= loop
)
438 /* Check that phi argument of exit edge is not defined inside loop. */
439 if (!check_exit_phi (loop
))
441 /* If the loop is not expected to iterate, there is no need
443 iterations
= estimated_loop_iterations_int (loop
);
445 iterations
= max_loop_iterations_int (loop
);
446 if (iterations
>= 0 && iterations
<= 1)
448 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
449 fprintf (dump_file
, ";; Not unswitching, loop is not expected"
454 guard
= find_loop_guard (loop
);
457 hoist_guard (loop
, guard
);
458 update_ssa (TODO_update_ssa
);
464 /* Checks if the body of the LOOP is within an invariant guard. If this
465 is the case, returns the edge that jumps over the real body of the loop,
466 otherwise returns NULL. */
469 find_loop_guard (struct loop
*loop
)
471 basic_block header
= loop
->header
;
472 edge guard_edge
, te
, fe
;
473 basic_block
*body
= NULL
;
478 /* We check for the following situation:
487 nvar = phi(orig, bvar) ... for all variables changed in body;
497 1) cond1 is loop invariant
498 2) If cond1 is false, then the loop is essentially empty; i.e.,
499 a) nothing in something1, something2 and something3 has side
501 b) anything defined in something1, something2 and something3
502 is not used outside of the loop. */
504 while (single_succ_p (header
))
505 header
= single_succ (header
);
506 if (!last_stmt (header
)
507 || gimple_code (last_stmt (header
)) != GIMPLE_COND
)
510 extract_true_false_edges_from_block (header
, &te
, &fe
);
511 if (!flow_bb_inside_loop_p (loop
, te
->dest
)
512 || !flow_bb_inside_loop_p (loop
, fe
->dest
))
515 if (just_once_each_iteration_p (loop
, te
->dest
)
516 || (single_succ_p (te
->dest
)
517 && just_once_each_iteration_p (loop
, single_succ (te
->dest
))))
519 if (just_once_each_iteration_p (loop
, fe
->dest
))
523 else if (just_once_each_iteration_p (loop
, fe
->dest
)
524 || (single_succ_p (fe
->dest
)
525 && just_once_each_iteration_p (loop
, single_succ (fe
->dest
))))
530 /* Guard edge must skip inner loop. */
531 if (!dominated_by_p (CDI_DOMINATORS
, loop
->inner
->header
,
532 guard_edge
== fe
? te
->dest
: fe
->dest
))
534 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
535 fprintf (dump_file
, "Guard edge %d --> %d is not around the loop!\n",
536 guard_edge
->src
->index
, guard_edge
->dest
->index
);
539 if (guard_edge
->dest
== loop
->latch
)
541 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
542 fprintf (dump_file
, "Guard edge destination is loop latch.\n");
546 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
548 "Considering guard %d -> %d in loop %d\n",
549 guard_edge
->src
->index
, guard_edge
->dest
->index
, loop
->num
);
550 /* Check if condition operands do not have definitions inside loop since
551 any bb copying is not performed. */
552 FOR_EACH_SSA_TREE_OPERAND (use
, last_stmt (header
), iter
, SSA_OP_USE
)
554 gimple
*def
= SSA_NAME_DEF_STMT (use
);
555 basic_block def_bb
= gimple_bb (def
);
557 && flow_bb_inside_loop_p (loop
, def_bb
))
559 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
560 fprintf (dump_file
, " guard operands have definitions"
566 body
= get_loop_body (loop
);
567 for (i
= 0; i
< loop
->num_nodes
; i
++)
569 basic_block bb
= body
[i
];
570 if (bb
->loop_father
!= loop
)
572 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
574 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
575 fprintf (dump_file
, "Block %d is marked as irreducible in loop\n",
580 if (!empty_bb_without_guard_p (loop
, bb
))
582 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
583 fprintf (dump_file
, " block %d has side effects\n", bb
->index
);
589 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
590 fprintf (dump_file
, " suitable to hoist\n");
598 1) no statement in BB has side effects
599 2) assuming that edge GUARD is always taken, all definitions in BB
600 are noy used outside of the loop.
601 KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
602 PROCESSED is a set of ssa names for that we already tested whether they
603 are invariant or not. */
606 empty_bb_without_guard_p (struct loop
*loop
, basic_block bb
)
608 basic_block exit_bb
= single_exit (loop
)->src
;
609 bool may_be_used_outside
= (bb
== exit_bb
610 || !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
));
614 /* Phi nodes do not have side effects, but their results might be used
615 outside of the loop. */
616 if (may_be_used_outside
)
618 for (gphi_iterator gsi
= gsi_start_phis (bb
);
619 !gsi_end_p (gsi
); gsi_next (&gsi
))
621 gphi
*phi
= gsi
.phi ();
622 name
= PHI_RESULT (phi
);
623 if (virtual_operand_p (name
))
626 if (used_outside_loop_p (loop
, name
))
631 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
632 !gsi_end_p (gsi
); gsi_next (&gsi
))
634 gimple
*stmt
= gsi_stmt (gsi
);
635 if (gimple_has_side_effects (stmt
))
638 if (gimple_vdef(stmt
))
641 FOR_EACH_SSA_TREE_OPERAND (name
, stmt
, op_iter
, SSA_OP_DEF
)
643 if (may_be_used_outside
644 && used_outside_loop_p (loop
, name
))
651 /* Return true if NAME is used outside of LOOP. */
654 used_outside_loop_p (struct loop
*loop
, tree name
)
659 FOR_EACH_IMM_USE_FAST (use
, it
, name
)
661 gimple
*stmt
= USE_STMT (use
);
662 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
669 /* Return argument for loop preheader edge in header virtual phi if any. */
672 get_vop_from_header (struct loop
*loop
)
674 for (gphi_iterator gsi
= gsi_start_phis (loop
->header
);
675 !gsi_end_p (gsi
); gsi_next (&gsi
))
677 gphi
*phi
= gsi
.phi ();
678 if (!virtual_operand_p (gimple_phi_result (phi
)))
680 return PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
685 /* Move the check of GUARD outside of LOOP. */
688 hoist_guard (struct loop
*loop
, edge guard
)
690 edge exit
= single_exit (loop
);
691 edge preh
= loop_preheader_edge (loop
);
692 basic_block pre_header
= preh
->src
;
694 edge te
, fe
, e
, new_edge
;
696 basic_block guard_bb
= guard
->src
;
697 gimple_stmt_iterator gsi
;
699 bool fix_dom_of_exit
;
700 gcond
*cond_stmt
, *new_cond_stmt
;
702 bb
= get_immediate_dominator (CDI_DOMINATORS
, exit
->dest
);
703 fix_dom_of_exit
= flow_bb_inside_loop_p (loop
, bb
);
704 gsi
= gsi_last_bb (guard_bb
);
705 stmt
= gsi_stmt (gsi
);
706 gcc_assert (gimple_code (stmt
) == GIMPLE_COND
);
707 cond_stmt
= as_a
<gcond
*> (stmt
);
708 extract_true_false_edges_from_block (guard_bb
, &te
, &fe
);
709 /* Insert guard to PRE_HEADER. */
710 if (!empty_block_p (pre_header
))
711 gsi
= gsi_last_bb (pre_header
);
713 gsi
= gsi_start_bb (pre_header
);
714 /* Create copy of COND_STMT. */
715 new_cond_stmt
= gimple_build_cond (gimple_cond_code (cond_stmt
),
716 gimple_cond_lhs (cond_stmt
),
717 gimple_cond_rhs (cond_stmt
),
718 NULL_TREE
, NULL_TREE
);
719 gsi_insert_after (&gsi
, new_cond_stmt
, GSI_NEW_STMT
);
720 /* Convert COND_STMT to true/false conditional. */
722 gimple_cond_make_false (cond_stmt
);
724 gimple_cond_make_true (cond_stmt
);
725 update_stmt (cond_stmt
);
726 /* Create new loop pre-header. */
727 e
= split_block (pre_header
, last_stmt (pre_header
));
728 gcc_assert (loop_preheader_edge (loop
)->src
== e
->dest
);
731 e
->flags
= EDGE_TRUE_VALUE
;
732 flags
|= EDGE_FALSE_VALUE
;
736 e
->flags
= EDGE_FALSE_VALUE
;
737 flags
|= EDGE_TRUE_VALUE
;
739 new_edge
= make_edge (pre_header
, exit
->dest
, flags
);
741 set_immediate_dominator (CDI_DOMINATORS
, exit
->dest
, pre_header
);
742 /* Add NEW_ADGE argument for all phi in post-header block. */
744 for (gphi_iterator gsi
= gsi_start_phis (bb
);
745 !gsi_end_p (gsi
); gsi_next (&gsi
))
747 gphi
*phi
= gsi
.phi ();
749 if (virtual_operand_p (gimple_phi_result (phi
)))
751 arg
= get_vop_from_header (loop
);
752 if (arg
== NULL_TREE
)
753 /* Use exit edge argument. */
754 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
755 add_phi_arg (phi
, arg
, new_edge
, UNKNOWN_LOCATION
);
759 /* Use exit edge argument. */
760 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
761 add_phi_arg (phi
, arg
, new_edge
, UNKNOWN_LOCATION
);
765 mark_virtual_operands_for_renaming (cfun
);
766 update_ssa (TODO_update_ssa
);
767 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
768 fprintf (dump_file
, " guard hoisted.\n");
771 /* Return true if phi argument for exit edge can be used
772 for edge around loop. */
775 check_exit_phi (struct loop
*loop
)
777 edge exit
= single_exit (loop
);
778 basic_block pre_header
= loop_preheader_edge (loop
)->src
;
780 for (gphi_iterator gsi
= gsi_start_phis (exit
->dest
);
781 !gsi_end_p (gsi
); gsi_next (&gsi
))
783 gphi
*phi
= gsi
.phi ();
787 if (virtual_operand_p (gimple_phi_result (phi
)))
789 arg
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
790 if (TREE_CODE (arg
) != SSA_NAME
)
792 def
= SSA_NAME_DEF_STMT (arg
);
795 def_bb
= gimple_bb (def
);
798 if (!dominated_by_p (CDI_DOMINATORS
, pre_header
, def_bb
))
799 /* Definition inside loop! */
801 /* Check loop closed phi invariant. */
802 if (!flow_bb_inside_loop_p (def_bb
->loop_father
, pre_header
))
808 /* Loop unswitching pass. */
812 const pass_data pass_data_tree_unswitch
=
814 GIMPLE_PASS
, /* type */
815 "unswitch", /* name */
816 OPTGROUP_LOOP
, /* optinfo_flags */
817 TV_TREE_LOOP_UNSWITCH
, /* tv_id */
818 PROP_cfg
, /* properties_required */
819 0, /* properties_provided */
820 0, /* properties_destroyed */
821 0, /* todo_flags_start */
822 0, /* todo_flags_finish */
825 class pass_tree_unswitch
: public gimple_opt_pass
828 pass_tree_unswitch (gcc::context
*ctxt
)
829 : gimple_opt_pass (pass_data_tree_unswitch
, ctxt
)
832 /* opt_pass methods: */
833 virtual bool gate (function
*) { return flag_unswitch_loops
!= 0; }
834 virtual unsigned int execute (function
*);
836 }; // class pass_tree_unswitch
839 pass_tree_unswitch::execute (function
*fun
)
841 if (number_of_loops (fun
) <= 1)
844 return tree_ssa_unswitch_loops ();
850 make_pass_tree_unswitch (gcc::context
*ctxt
)
852 return new pass_tree_unswitch (ctxt
);