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);
226 if (iterations >= 0 && iterations <= 1)
228 if (dump_file && (dump_flags & TDF_DETAILS))
229 fprintf (dump_file, ";; Not unswitching, loop is not expected"
236 bbs = get_loop_body (loop);
237 found = loop->num_nodes;
241 /* Find a bb to unswitch on. */
242 for (; i < loop->num_nodes; i++)
243 if ((cond = tree_may_unswitch_on (bbs[i], loop)))
246 if (i == loop->num_nodes)
249 && num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)
250 && (dump_flags & TDF_DETAILS))
251 fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
253 if (found == loop->num_nodes)
261 cond = simplify_using_entry_checks (loop, cond);
262 stmt = last_stmt (bbs[i]);
263 if (integer_nonzerop (cond))
265 /* Remove false path. */
266 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
270 else if (integer_zerop (cond))
272 /* Remove true path. */
273 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
277 /* Do not unswitch too much. */
278 else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
283 /* In nested tree_unswitch_single_loop first optimize all conditions
284 using entry checks, then discover still reachable blocks in the
285 loop and find the condition only among those still reachable bbs. */
288 if (found == loop->num_nodes)
305 basic_block *tos, *worklist;
307 /* When called recursively, first do a quick discovery
308 of reachable bbs after the above changes and only
309 consider conditions in still reachable bbs. */
310 tos = worklist = XNEWVEC (basic_block, loop->num_nodes);
312 for (i = 0; i < loop->num_nodes; i++)
313 bbs[i]->flags &= ~BB_REACHABLE;
315 /* Start with marking header. */
317 bbs[0]->flags |= BB_REACHABLE;
319 /* Iterate: find everything reachable from what we've already seen
320 within the same innermost loop. Don't look through false edges
321 if condition is always true or true edges if condition is
323 while (tos != worklist)
325 basic_block b = *--tos;
330 if (EDGE_COUNT (b->succs) == 2)
332 gimple *stmt = last_stmt (b);
334 && gimple_code (stmt) == GIMPLE_COND)
336 gcond *cond_stmt = as_a <gcond *> (stmt);
337 if (gimple_cond_true_p (cond_stmt))
338 flags = EDGE_FALSE_VALUE;
339 else if (gimple_cond_false_p (cond_stmt))
340 flags = EDGE_TRUE_VALUE;
344 FOR_EACH_EDGE (e, ei, b->succs)
346 basic_block dest = e->dest;
348 if (dest->loop_father == loop
349 && !(dest->flags & BB_REACHABLE)
350 && !(e->flags & flags))
353 dest->flags |= BB_REACHABLE;
360 /* Find a bb to unswitch on. */
361 for (; found < loop->num_nodes; found++)
362 if ((bbs[found]->flags & BB_REACHABLE)
363 && (cond = tree_may_unswitch_on (bbs[found], loop)))
366 if (found == loop->num_nodes)
373 if (dump_file && (dump_flags & TDF_DETAILS))
374 fprintf (dump_file, ";; Unswitching loop\n");
376 initialize_original_copy_tables ();
377 /* Unswitch the loop on this condition. */
378 nloop = tree_unswitch_loop (loop, bbs[found], cond);
381 free_original_copy_tables ();
386 /* Update the SSA form after unswitching. */
387 update_ssa (TODO_update_ssa);
388 free_original_copy_tables ();
390 /* Invoke itself on modified loops. */
391 tree_unswitch_single_loop (nloop, num + 1);
392 tree_unswitch_single_loop (loop, num + 1);
397 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
398 unswitching of innermost loops. COND is the condition determining which
399 loop is entered -- the new loop is entered if COND is true. Returns NULL
400 if impossible, new loop otherwise. */
403 tree_unswitch_loop (struct loop *loop,
404 basic_block unswitch_on, tree cond)
407 edge edge_true, edge_false;
409 /* Some sanity checking. */
410 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
411 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
412 gcc_assert (loop->inner == NULL);
414 extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
415 prob_true = edge_true->probability;
416 return loop_version (loop, unshare_expr (cond),
417 NULL, prob_true, prob_true,
418 REG_BR_PROB_BASE - prob_true, false);
421 /* Unswitch outer loops by hoisting invariant guard on
422 inner loop without code duplication. */
424 tree_unswitch_outer_loop (struct loop *loop)
427 HOST_WIDE_INT iterations;
429 gcc_assert (loop->inner);
430 if (loop->inner->next)
432 /* Accept loops with single exit only which is not from inner loop. */
433 exit = single_exit (loop);
434 if (!exit || exit->src->loop_father != loop)
436 /* Check that phi argument of exit edge is not defined inside loop. */
437 if (!check_exit_phi (loop))
439 /* If the loop is not expected to iterate, there is no need
441 iterations = estimated_loop_iterations_int (loop);
442 if (iterations >= 0 && iterations <= 1)
444 if (dump_file && (dump_flags & TDF_DETAILS))
445 fprintf (dump_file, ";; Not unswitching, loop is not expected"
450 guard = find_loop_guard (loop);
453 hoist_guard (loop, guard);
454 update_ssa (TODO_update_ssa);
460 /* Checks if the body of the LOOP is within an invariant guard. If this
461 is the case, returns the edge that jumps over the real body of the loop,
462 otherwise returns NULL. */
465 find_loop_guard (struct loop *loop)
467 basic_block header = loop->header;
468 edge guard_edge, te, fe;
469 basic_block *body = NULL;
474 /* We check for the following situation:
483 nvar = phi(orig, bvar) ... for all variables changed in body;
493 1) cond1 is loop invariant
494 2) If cond1 is false, then the loop is essentially empty; i.e.,
495 a) nothing in something1, something2 and something3 has side
497 b) anything defined in something1, something2 and something3
498 is not used outside of the loop. */
500 while (single_succ_p (header))
501 header = single_succ (header);
502 if (!last_stmt (header)
503 || gimple_code (last_stmt (header)) != GIMPLE_COND)
506 extract_true_false_edges_from_block (header, &te, &fe);
507 if (!flow_bb_inside_loop_p (loop, te->dest)
508 || !flow_bb_inside_loop_p (loop, fe->dest))
511 if (just_once_each_iteration_p (loop, te->dest)
512 || (single_succ_p (te->dest)
513 && just_once_each_iteration_p (loop, single_succ (te->dest))))
515 if (just_once_each_iteration_p (loop, fe->dest))
519 else if (just_once_each_iteration_p (loop, fe->dest)
520 || (single_succ_p (fe->dest)
521 && just_once_each_iteration_p (loop, single_succ (fe->dest))))
526 /* Guard edge must skip inner loop. */
527 if (!dominated_by_p (CDI_DOMINATORS, loop->inner->header,
528 guard_edge == fe ? te->dest : fe->dest))
530 if (dump_file && (dump_flags & TDF_DETAILS))
531 fprintf (dump_file, "Guard edge %d --> %d is not around the loop!\n",
532 guard_edge->src->index, guard_edge->dest->index);
535 if (guard_edge->dest == loop->latch)
537 if (dump_file && (dump_flags & TDF_DETAILS))
538 fprintf (dump_file, "Guard edge destination is loop latch.\n");
542 if (dump_file && (dump_flags & TDF_DETAILS))
544 "Considering guard %d -> %d in loop %d\n",
545 guard_edge->src->index, guard_edge->dest->index, loop->num);
546 /* Check if condition operands do not have definitions inside loop since
547 any bb copying is not performed. */
548 FOR_EACH_SSA_TREE_OPERAND (use, last_stmt (header), iter, SSA_OP_USE)
550 gimple *def = SSA_NAME_DEF_STMT (use);
551 basic_block def_bb = gimple_bb (def);
553 && flow_bb_inside_loop_p (loop, def_bb))
555 if (dump_file && (dump_flags & TDF_DETAILS))
556 fprintf (dump_file, " guard operands have definitions"
562 body = get_loop_body (loop);
563 for (i = 0; i < loop->num_nodes; i++)
565 basic_block bb = body[i];
566 if (bb->loop_father != loop)
568 if (bb->flags & BB_IRREDUCIBLE_LOOP)
570 if (dump_file && (dump_flags & TDF_DETAILS))
571 fprintf (dump_file, "Block %d is marked as irreducible in loop\n",
576 if (!empty_bb_without_guard_p (loop, bb))
578 if (dump_file && (dump_flags & TDF_DETAILS))
579 fprintf (dump_file, " block %d has side effects\n", bb->index);
585 if (dump_file && (dump_flags & TDF_DETAILS))
586 fprintf (dump_file, " suitable to hoist\n");
594 1) no statement in BB has side effects
595 2) assuming that edge GUARD is always taken, all definitions in BB
596 are noy used outside of the loop.
597 KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
598 PROCESSED is a set of ssa names for that we already tested whether they
599 are invariant or not. */
602 empty_bb_without_guard_p (struct loop *loop, basic_block bb)
604 basic_block exit_bb = single_exit (loop)->src;
605 bool may_be_used_outside = (bb == exit_bb
606 || !dominated_by_p (CDI_DOMINATORS, bb, exit_bb));
610 /* Phi nodes do not have side effects, but their results might be used
611 outside of the loop. */
612 if (may_be_used_outside)
614 for (gphi_iterator gsi = gsi_start_phis (bb);
615 !gsi_end_p (gsi); gsi_next (&gsi))
617 gphi *phi = gsi.phi ();
618 name = PHI_RESULT (phi);
619 if (virtual_operand_p (name))
622 if (used_outside_loop_p (loop, name))
627 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
628 !gsi_end_p (gsi); gsi_next (&gsi))
630 gimple *stmt = gsi_stmt (gsi);
631 if (gimple_has_side_effects (stmt))
634 if (gimple_vdef(stmt))
637 FOR_EACH_SSA_TREE_OPERAND (name, stmt, op_iter, SSA_OP_DEF)
639 if (may_be_used_outside
640 && used_outside_loop_p (loop, name))
647 /* Return true if NAME is used outside of LOOP. */
650 used_outside_loop_p (struct loop *loop, tree name)
655 FOR_EACH_IMM_USE_FAST (use, it, name)
657 gimple *stmt = USE_STMT (use);
658 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
665 /* Return argument for loop preheader edge in header virtual phi if any. */
668 get_vop_from_header (struct loop *loop)
670 for (gphi_iterator gsi = gsi_start_phis (loop->header);
671 !gsi_end_p (gsi); gsi_next (&gsi))
673 gphi *phi = gsi.phi ();
674 if (!virtual_operand_p (gimple_phi_result (phi)))
676 return PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
681 /* Move the check of GUARD outside of LOOP. */
684 hoist_guard (struct loop *loop, edge guard)
686 edge exit = single_exit (loop);
687 edge preh = loop_preheader_edge (loop);
688 basic_block pre_header = preh->src;
690 edge te, fe, e, new_edge;
692 basic_block guard_bb = guard->src;
693 gimple_stmt_iterator gsi;
695 bool fix_dom_of_exit;
696 gcond *cond_stmt, *new_cond_stmt;
698 bb = get_immediate_dominator (CDI_DOMINATORS, exit->dest);
699 fix_dom_of_exit = flow_bb_inside_loop_p (loop, bb);
700 gsi = gsi_last_bb (guard_bb);
701 stmt = gsi_stmt (gsi);
702 gcc_assert (gimple_code (stmt) == GIMPLE_COND);
703 cond_stmt = as_a <gcond *> (stmt);
704 extract_true_false_edges_from_block (guard_bb, &te, &fe);
705 /* Insert guard to PRE_HEADER. */
706 if (!empty_block_p (pre_header))
707 gsi = gsi_last_bb (pre_header);
709 gsi = gsi_start_bb (pre_header);
710 /* Create copy of COND_STMT. */
711 new_cond_stmt = gimple_build_cond (gimple_cond_code (cond_stmt),
712 gimple_cond_lhs (cond_stmt),
713 gimple_cond_rhs (cond_stmt),
714 NULL_TREE, NULL_TREE);
715 gsi_insert_after (&gsi, new_cond_stmt, GSI_NEW_STMT);
716 /* Convert COND_STMT to true/false conditional. */
718 gimple_cond_make_false (cond_stmt);
720 gimple_cond_make_true (cond_stmt);
721 update_stmt (cond_stmt);
722 /* Create new loop pre-header. */
723 e = split_block (pre_header, last_stmt (pre_header));
724 gcc_assert (loop_preheader_edge (loop)->src == e->dest);
727 e->flags = EDGE_TRUE_VALUE;
728 flags |= EDGE_FALSE_VALUE;
732 e->flags = EDGE_FALSE_VALUE;
733 flags |= EDGE_TRUE_VALUE;
735 new_edge = make_edge (pre_header, exit->dest, flags);
737 set_immediate_dominator (CDI_DOMINATORS, exit->dest, pre_header);
738 /* Add NEW_ADGE argument for all phi in post-header block. */
740 for (gphi_iterator gsi = gsi_start_phis (bb);
741 !gsi_end_p (gsi); gsi_next (&gsi))
743 gphi *phi = gsi.phi ();
745 if (virtual_operand_p (gimple_phi_result (phi)))
747 arg = get_vop_from_header (loop);
748 if (arg == NULL_TREE)
749 /* Use exit edge argument. */
750 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
751 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
755 /* Use exit edge argument. */
756 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
757 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
761 mark_virtual_operands_for_renaming (cfun);
762 update_ssa (TODO_update_ssa);
763 if (dump_file && (dump_flags & TDF_DETAILS))
764 fprintf (dump_file, " guard hoisted.\n");
767 /* Return true if phi argument for exit edge can be used
768 for edge around loop. */
771 check_exit_phi (struct loop *loop)
773 edge exit = single_exit (loop);
774 basic_block pre_header = loop_preheader_edge (loop)->src;
776 for (gphi_iterator gsi = gsi_start_phis (exit->dest);
777 !gsi_end_p (gsi); gsi_next (&gsi))
779 gphi *phi = gsi.phi ();
783 if (virtual_operand_p (gimple_phi_result (phi)))
785 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
786 if (TREE_CODE (arg) != SSA_NAME)
788 def = SSA_NAME_DEF_STMT (arg);
791 def_bb = gimple_bb (def);
794 if (!dominated_by_p (CDI_DOMINATORS, pre_header, def_bb))
795 /* Definition inside loop! */
797 /* Check loop closed phi invariant. */
798 if (!flow_bb_inside_loop_p (def_bb->loop_father, pre_header))
804 /* Loop unswitching pass. */
808 const pass_data pass_data_tree_unswitch =
810 GIMPLE_PASS, /* type */
811 "unswitch", /* name */
812 OPTGROUP_LOOP, /* optinfo_flags */
813 TV_TREE_LOOP_UNSWITCH, /* tv_id */
814 PROP_cfg, /* properties_required */
815 0, /* properties_provided */
816 0, /* properties_destroyed */
817 0, /* todo_flags_start */
818 0, /* todo_flags_finish */
821 class pass_tree_unswitch : public gimple_opt_pass
824 pass_tree_unswitch (gcc::context *ctxt)
825 : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
828 /* opt_pass methods: */
829 virtual bool gate (function *) { return flag_unswitch_loops != 0; }
830 virtual unsigned int execute (function *);
832 }; // class pass_tree_unswitch
835 pass_tree_unswitch::execute (function *fun)
837 if (number_of_loops (fun) <= 1)
840 return tree_ssa_unswitch_loops ();
846 make_pass_tree_unswitch (gcc::context *ctxt)
848 return new pass_tree_unswitch (ctxt);