1 /* Induction variable canonicalization and loop peeling.
2 Copyright (C) 2004-2013 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/>. */
20 /* This pass detects the loops that iterate a constant number of times,
21 adds a canonical induction variable (step -1, tested against 0)
22 and replaces the exit test. This enables the less powerful rtl
23 level analysis to use this information.
25 This might spoil the code in some cases (by increasing register pressure).
26 Note that in the case the new variable is not needed, ivopts will get rid
27 of it, so it might only be a problem when there are no other linear induction
28 variables. In that case the created optimization possibilities are likely
31 Additionally in case we detect that it is beneficial to unroll the
32 loop completely, we do it right here to expose the optimization
33 possibilities to the following passes. */
37 #include "coretypes.h"
41 #include "basic-block.h"
42 #include "gimple-pretty-print.h"
43 #include "tree-flow.h"
45 #include "tree-pass.h"
46 #include "tree-chrec.h"
47 #include "tree-scalar-evolution.h"
50 #include "tree-inline.h"
53 /* Specifies types of loops that may be unrolled. */
57 UL_SINGLE_ITER, /* Only loops that exit immediately in the first
59 UL_NO_GROWTH, /* Only loops whose unrolling will not cause increase
61 UL_ALL /* All suitable loops. */
64 /* Adds a canonical induction variable to LOOP iterating NITER times. EXIT
65 is the exit edge whose condition is replaced. */
68 create_canonical_iv (struct loop *loop, edge exit, tree niter)
73 gimple_stmt_iterator incr_at;
76 if (dump_file && (dump_flags & TDF_DETAILS))
78 fprintf (dump_file, "Added canonical iv to loop %d, ", loop->num);
79 print_generic_expr (dump_file, niter, TDF_SLIM);
80 fprintf (dump_file, " iterations.\n");
83 cond = last_stmt (exit->src);
84 in = EDGE_SUCC (exit->src, 0);
86 in = EDGE_SUCC (exit->src, 1);
88 /* Note that we do not need to worry about overflows, since
89 type of niter is always unsigned and all comparisons are
90 just for equality/nonequality -- i.e. everything works
91 with a modulo arithmetics. */
93 type = TREE_TYPE (niter);
94 niter = fold_build2 (PLUS_EXPR, type,
96 build_int_cst (type, 1));
97 incr_at = gsi_last_bb (in->src);
99 build_int_cst (type, -1),
101 &incr_at, false, NULL, &var);
103 cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
104 gimple_cond_set_code (cond, cmp);
105 gimple_cond_set_lhs (cond, var);
106 gimple_cond_set_rhs (cond, build_int_cst (type, 0));
110 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */
113 tree_num_loop_insns (struct loop *loop, eni_weights *weights)
115 basic_block *body = get_loop_body (loop);
116 gimple_stmt_iterator gsi;
117 unsigned size = 0, i;
119 for (i = 0; i < loop->num_nodes; i++)
120 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
121 size += estimate_num_insns (gsi_stmt (gsi), weights);
127 /* Describe size of loop as detected by tree_estimate_loop_size. */
130 /* Number of instructions in the loop. */
133 /* Number of instructions that will be likely optimized out in
134 peeled iterations of loop (i.e. computation based on induction
135 variable where induction variable starts at known constant.) */
136 int eliminated_by_peeling;
138 /* Same statistics for last iteration of loop: it is smaller because
139 instructions after exit are not executed. */
141 int last_iteration_eliminated_by_peeling;
143 /* If some IV computation will become constant. */
146 /* Number of call stmts that are not a builtin and are pure or const
147 present on the hot path. */
148 int num_pure_calls_on_hot_path;
149 /* Number of call stmts that are not a builtin and are not pure nor const
150 present on the hot path. */
151 int num_non_pure_calls_on_hot_path;
152 /* Number of statements other than calls in the loop. */
153 int non_call_stmts_on_hot_path;
154 /* Number of branches seen on the hot path. */
155 int num_branches_on_hot_path;
158 /* Return true if OP in STMT will be constant after peeling LOOP. */
161 constant_after_peeling (tree op, gimple stmt, struct loop *loop)
165 if (is_gimple_min_invariant (op))
168 /* We can still fold accesses to constant arrays when index is known. */
169 if (TREE_CODE (op) != SSA_NAME)
173 /* First make fast look if we see constant array inside. */
174 while (handled_component_p (base))
175 base = TREE_OPERAND (base, 0);
177 && ctor_for_folding (base) != error_mark_node)
178 || CONSTANT_CLASS_P (base))
180 /* If so, see if we understand all the indices. */
182 while (handled_component_p (base))
184 if (TREE_CODE (base) == ARRAY_REF
185 && !constant_after_peeling (TREE_OPERAND (base, 1), stmt, loop))
187 base = TREE_OPERAND (base, 0);
194 /* Induction variables are constants. */
195 if (!simple_iv (loop, loop_containing_stmt (stmt), op, &iv, false))
197 if (!is_gimple_min_invariant (iv.base))
199 if (!is_gimple_min_invariant (iv.step))
204 /* Computes an estimated number of insns in LOOP.
205 EXIT (if non-NULL) is an exite edge that will be eliminated in all but last
206 iteration of the loop.
207 EDGE_TO_CANCEL (if non-NULL) is an non-exit edge eliminated in the last iteration
209 Return results in SIZE, estimate benefits for complete unrolling exiting by EXIT.
210 Stop estimating after UPPER_BOUND is met. Return true in this case. */
213 tree_estimate_loop_size (struct loop *loop, edge exit, edge edge_to_cancel, struct loop_size *size,
216 basic_block *body = get_loop_body (loop);
217 gimple_stmt_iterator gsi;
220 vec<basic_block> path = get_loop_hot_path (loop);
223 size->eliminated_by_peeling = 0;
224 size->last_iteration = 0;
225 size->last_iteration_eliminated_by_peeling = 0;
226 size->num_pure_calls_on_hot_path = 0;
227 size->num_non_pure_calls_on_hot_path = 0;
228 size->non_call_stmts_on_hot_path = 0;
229 size->num_branches_on_hot_path = 0;
230 size->constant_iv = 0;
232 if (dump_file && (dump_flags & TDF_DETAILS))
233 fprintf (dump_file, "Estimating sizes for loop %i\n", loop->num);
234 for (i = 0; i < loop->num_nodes; i++)
236 if (edge_to_cancel && body[i] != edge_to_cancel->src
237 && dominated_by_p (CDI_DOMINATORS, body[i], edge_to_cancel->src))
241 if (dump_file && (dump_flags & TDF_DETAILS))
242 fprintf (dump_file, " BB: %i, after_exit: %i\n", body[i]->index, after_exit);
244 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
246 gimple stmt = gsi_stmt (gsi);
247 int num = estimate_num_insns (stmt, &eni_size_weights);
248 bool likely_eliminated = false;
249 bool likely_eliminated_last = false;
250 bool likely_eliminated_peeled = false;
252 if (dump_file && (dump_flags & TDF_DETAILS))
254 fprintf (dump_file, " size: %3i ", num);
255 print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, 0);
258 /* Look for reasons why we might optimize this stmt away. */
260 if (gimple_has_side_effects (stmt))
262 /* Exit conditional. */
263 else if (exit && body[i] == exit->src
264 && stmt == last_stmt (exit->src))
266 if (dump_file && (dump_flags & TDF_DETAILS))
267 fprintf (dump_file, " Exit condition will be eliminated "
268 "in peeled copies.\n");
269 likely_eliminated_peeled = true;
271 else if (edge_to_cancel && body[i] == edge_to_cancel->src
272 && stmt == last_stmt (edge_to_cancel->src))
274 if (dump_file && (dump_flags & TDF_DETAILS))
275 fprintf (dump_file, " Exit condition will be eliminated "
277 likely_eliminated_last = true;
279 /* Sets of IV variables */
280 else if (gimple_code (stmt) == GIMPLE_ASSIGN
281 && constant_after_peeling (gimple_assign_lhs (stmt), stmt, loop))
283 if (dump_file && (dump_flags & TDF_DETAILS))
284 fprintf (dump_file, " Induction variable computation will"
285 " be folded away.\n");
286 likely_eliminated = true;
288 /* Assignments of IV variables. */
289 else if (gimple_code (stmt) == GIMPLE_ASSIGN
290 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
291 && constant_after_peeling (gimple_assign_rhs1 (stmt), stmt, loop)
292 && (gimple_assign_rhs_class (stmt) != GIMPLE_BINARY_RHS
293 || constant_after_peeling (gimple_assign_rhs2 (stmt),
296 size->constant_iv = true;
297 if (dump_file && (dump_flags & TDF_DETAILS))
298 fprintf (dump_file, " Constant expression will be folded away.\n");
299 likely_eliminated = true;
302 else if ((gimple_code (stmt) == GIMPLE_COND
303 && constant_after_peeling (gimple_cond_lhs (stmt), stmt, loop)
304 && constant_after_peeling (gimple_cond_rhs (stmt), stmt, loop))
305 || (gimple_code (stmt) == GIMPLE_SWITCH
306 && constant_after_peeling (gimple_switch_index (stmt), stmt, loop)))
308 if (dump_file && (dump_flags & TDF_DETAILS))
309 fprintf (dump_file, " Constant conditional.\n");
310 likely_eliminated = true;
313 size->overall += num;
314 if (likely_eliminated || likely_eliminated_peeled)
315 size->eliminated_by_peeling += num;
318 size->last_iteration += num;
319 if (likely_eliminated || likely_eliminated_last)
320 size->last_iteration_eliminated_by_peeling += num;
322 if ((size->overall * 3 / 2 - size->eliminated_by_peeling
323 - size->last_iteration_eliminated_by_peeling) > upper_bound)
331 while (path.length ())
333 basic_block bb = path.pop ();
334 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
336 gimple stmt = gsi_stmt (gsi);
337 if (gimple_code (stmt) == GIMPLE_CALL)
339 int flags = gimple_call_flags (stmt);
340 tree decl = gimple_call_fndecl (stmt);
342 if (decl && DECL_IS_BUILTIN (decl)
343 && is_inexpensive_builtin (decl))
345 else if (flags & (ECF_PURE | ECF_CONST))
346 size->num_pure_calls_on_hot_path++;
348 size->num_non_pure_calls_on_hot_path++;
349 size->num_branches_on_hot_path ++;
351 else if (gimple_code (stmt) != GIMPLE_CALL
352 && gimple_code (stmt) != GIMPLE_DEBUG)
353 size->non_call_stmts_on_hot_path++;
354 if (((gimple_code (stmt) == GIMPLE_COND
355 && (!constant_after_peeling (gimple_cond_lhs (stmt), stmt, loop)
356 || constant_after_peeling (gimple_cond_rhs (stmt), stmt, loop)))
357 || (gimple_code (stmt) == GIMPLE_SWITCH
358 && !constant_after_peeling (gimple_switch_index (stmt), stmt, loop)))
359 && (!exit || bb != exit->src))
360 size->num_branches_on_hot_path++;
364 if (dump_file && (dump_flags & TDF_DETAILS))
365 fprintf (dump_file, "size: %i-%i, last_iteration: %i-%i\n", size->overall,
366 size->eliminated_by_peeling, size->last_iteration,
367 size->last_iteration_eliminated_by_peeling);
373 /* Estimate number of insns of completely unrolled loop.
374 It is (NUNROLL + 1) * size of loop body with taking into account
375 the fact that in last copy everything after exit conditional
376 is dead and that some instructions will be eliminated after
379 Loop body is likely going to simplify further, this is difficult
380 to guess, we just decrease the result by 1/3. */
382 static unsigned HOST_WIDE_INT
383 estimated_unrolled_size (struct loop_size *size,
384 unsigned HOST_WIDE_INT nunroll)
386 HOST_WIDE_INT unr_insns = ((nunroll)
387 * (HOST_WIDE_INT) (size->overall
388 - size->eliminated_by_peeling));
391 unr_insns += size->last_iteration - size->last_iteration_eliminated_by_peeling;
393 unr_insns = unr_insns * 2 / 3;
400 /* Loop LOOP is known to not loop. See if there is an edge in the loop
401 body that can be remove to make the loop to always exit and at
402 the same time it does not make any code potentially executed
403 during the last iteration dead.
405 After complette unrolling we still may get rid of the conditional
406 on the exit in the last copy even if we have no idea what it does.
407 This is quite common case for loops of form
413 Here we prove the loop to iterate 5 times but we do not know
414 it from induction variable.
416 For now we handle only simple case where there is exit condition
417 just before the latch block and the latch block contains no statements
418 with side effect that may otherwise terminate the execution of loop
419 (such as by EH or by terminating the program or longjmp).
421 In the general case we may want to cancel the paths leading to statements
422 loop-niter identified as having undefined effect in the last iteration.
423 The other cases are hopefully rare and will be cleaned up later. */
426 loop_edge_to_cancel (struct loop *loop)
431 gimple_stmt_iterator gsi;
433 /* We want only one predecestor of the loop. */
434 if (EDGE_COUNT (loop->latch->preds) > 1)
437 exits = get_loop_exit_edges (loop);
439 FOR_EACH_VEC_ELT (exits, i, edge_to_cancel)
441 /* Find the other edge than the loop exit
442 leaving the conditoinal. */
443 if (EDGE_COUNT (edge_to_cancel->src->succs) != 2)
445 if (EDGE_SUCC (edge_to_cancel->src, 0) == edge_to_cancel)
446 edge_to_cancel = EDGE_SUCC (edge_to_cancel->src, 1);
448 edge_to_cancel = EDGE_SUCC (edge_to_cancel->src, 0);
450 /* We only can handle conditionals. */
451 if (!(edge_to_cancel->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
454 /* We should never have conditionals in the loop latch. */
455 gcc_assert (edge_to_cancel->dest != loop->header);
457 /* Check that it leads to loop latch. */
458 if (edge_to_cancel->dest != loop->latch)
463 /* Verify that the code in loop latch does nothing that may end program
464 execution without really reaching the exit. This may include
465 non-pure/const function calls, EH statements, volatile ASMs etc. */
466 for (gsi = gsi_start_bb (loop->latch); !gsi_end_p (gsi); gsi_next (&gsi))
467 if (gimple_has_side_effects (gsi_stmt (gsi)))
469 return edge_to_cancel;
475 /* Remove all tests for exits that are known to be taken after LOOP was
476 peeled NPEELED times. Put gcc_unreachable before every statement
477 known to not be executed. */
480 remove_exits_and_undefined_stmts (struct loop *loop, unsigned int npeeled)
482 struct nb_iter_bound *elt;
483 bool changed = false;
485 for (elt = loop->bounds; elt; elt = elt->next)
487 /* If statement is known to be undefined after peeling, turn it
488 into unreachable (or trap when debugging experience is supposed
491 && elt->bound.ltu_p (max_wide_int (npeeled)))
493 gimple_stmt_iterator gsi = gsi_for_stmt (elt->stmt);
494 gimple stmt = gimple_build_call
495 (builtin_decl_implicit (BUILT_IN_UNREACHABLE), 0);
497 gimple_set_location (stmt, gimple_location (elt->stmt));
498 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
500 if (dump_file && (dump_flags & TDF_DETAILS))
502 fprintf (dump_file, "Forced statement unreachable: ");
503 print_gimple_stmt (dump_file, elt->stmt, 0, 0);
506 /* If we know the exit will be taken after peeling, update. */
507 else if (elt->is_exit
508 && elt->bound.leu_p (max_wide_int (npeeled)))
510 basic_block bb = gimple_bb (elt->stmt);
511 edge exit_edge = EDGE_SUCC (bb, 0);
513 if (dump_file && (dump_flags & TDF_DETAILS))
515 fprintf (dump_file, "Forced exit to be taken: ");
516 print_gimple_stmt (dump_file, elt->stmt, 0, 0);
518 if (!loop_exit_edge_p (loop, exit_edge))
519 exit_edge = EDGE_SUCC (bb, 1);
520 gcc_checking_assert (loop_exit_edge_p (loop, exit_edge));
521 if (exit_edge->flags & EDGE_TRUE_VALUE)
522 gimple_cond_make_true (elt->stmt);
524 gimple_cond_make_false (elt->stmt);
525 update_stmt (elt->stmt);
532 /* Remove all exits that are known to be never taken because of the loop bound
536 remove_redundant_iv_tests (struct loop *loop)
538 struct nb_iter_bound *elt;
539 bool changed = false;
541 if (!loop->any_upper_bound)
543 for (elt = loop->bounds; elt; elt = elt->next)
545 /* Exit is pointless if it won't be taken before loop reaches
547 if (elt->is_exit && loop->any_upper_bound
548 && loop->nb_iterations_upper_bound.ltu_p (elt->bound))
550 basic_block bb = gimple_bb (elt->stmt);
551 edge exit_edge = EDGE_SUCC (bb, 0);
552 struct tree_niter_desc niter;
554 if (!loop_exit_edge_p (loop, exit_edge))
555 exit_edge = EDGE_SUCC (bb, 1);
557 /* Only when we know the actual number of iterations, not
558 just a bound, we can remove the exit. */
559 if (!number_of_iterations_exit (loop, exit_edge,
560 &niter, false, false)
561 || !integer_onep (niter.assumptions)
562 || !integer_zerop (niter.may_be_zero)
564 || TREE_CODE (niter.niter) != INTEGER_CST
565 || !loop->nb_iterations_upper_bound.ltu_p (niter.niter))
568 if (dump_file && (dump_flags & TDF_DETAILS))
570 fprintf (dump_file, "Removed pointless exit: ");
571 print_gimple_stmt (dump_file, elt->stmt, 0, 0);
573 if (exit_edge->flags & EDGE_TRUE_VALUE)
574 gimple_cond_make_false (elt->stmt);
576 gimple_cond_make_true (elt->stmt);
577 update_stmt (elt->stmt);
584 /* Stores loops that will be unlooped after we process whole loop tree. */
585 static vec<loop_p> loops_to_unloop;
586 static vec<int> loops_to_unloop_nunroll;
588 /* Cancel all fully unrolled loops by putting __builtin_unreachable
590 We do it after all unrolling since unlooping moves basic blocks
591 across loop boundaries trashing loop closed SSA form as well
592 as SCEV info needed to be intact during unrolling.
594 IRRED_INVALIDATED is used to bookkeep if information about
595 irreducible regions may become invalid as a result
596 of the transformation.
597 LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case
598 when we need to go into loop closed SSA form. */
601 unloop_loops (bitmap loop_closed_ssa_invalidated,
602 bool *irred_invalidated)
604 while (loops_to_unloop.length ())
606 struct loop *loop = loops_to_unloop.pop ();
607 int n_unroll = loops_to_unloop_nunroll.pop ();
608 basic_block latch = loop->latch;
609 edge latch_edge = loop_latch_edge (loop);
610 int flags = latch_edge->flags;
611 location_t locus = latch_edge->goto_locus;
613 gimple_stmt_iterator gsi;
615 remove_exits_and_undefined_stmts (loop, n_unroll);
617 /* Unloop destroys the latch edge. */
618 unloop (loop, irred_invalidated, loop_closed_ssa_invalidated);
620 /* Create new basic block for the latch edge destination and wire
622 stmt = gimple_build_call (builtin_decl_implicit (BUILT_IN_UNREACHABLE), 0);
623 latch_edge = make_edge (latch, create_basic_block (NULL, NULL, latch), flags);
624 latch_edge->probability = 0;
625 latch_edge->count = 0;
626 latch_edge->flags |= flags;
627 latch_edge->goto_locus = locus;
629 latch_edge->dest->loop_father = current_loops->tree_root;
630 latch_edge->dest->count = 0;
631 latch_edge->dest->frequency = 0;
632 set_immediate_dominator (CDI_DOMINATORS, latch_edge->dest, latch_edge->src);
634 gsi = gsi_start_bb (latch_edge->dest);
635 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
637 loops_to_unloop.release ();
638 loops_to_unloop_nunroll.release ();
641 /* Tries to unroll LOOP completely, i.e. NITER times.
642 UL determines which loops we are allowed to unroll.
643 EXIT is the exit of the loop that should be eliminated.
644 MAXITER specfy bound on number of iterations, -1 if it is
645 not known or too large for HOST_WIDE_INT. The location
646 LOCUS corresponding to the loop is used when emitting
647 a summary of the unroll to the dump file. */
650 try_unroll_loop_completely (struct loop *loop,
651 edge exit, tree niter,
652 enum unroll_level ul,
653 HOST_WIDE_INT maxiter,
656 unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns;
658 struct loop_size size;
659 bool n_unroll_found = false;
660 edge edge_to_cancel = NULL;
662 /* See if we proved number of iterations to be low constant.
664 EXIT is an edge that will be removed in all but last iteration of
667 EDGE_TO_CACNEL is an edge that will be removed from the last iteration
668 of the unrolled sequence and is expected to make the final loop not
671 If the number of execution of loop is determined by standard induction
672 variable test, then EXIT and EDGE_TO_CANCEL are the two edges leaving
674 if (tree_fits_uhwi_p (niter))
676 n_unroll = tree_to_uhwi (niter);
677 n_unroll_found = true;
678 edge_to_cancel = EDGE_SUCC (exit->src, 0);
679 if (edge_to_cancel == exit)
680 edge_to_cancel = EDGE_SUCC (exit->src, 1);
682 /* We do not know the number of iterations and thus we can not eliminate
687 /* See if we can improve our estimate by using recorded loop bounds. */
689 && (!n_unroll_found || (unsigned HOST_WIDE_INT)maxiter < n_unroll))
692 n_unroll_found = true;
693 /* Loop terminates before the IV variable test, so we can not
694 remove it in the last iteration. */
695 edge_to_cancel = NULL;
701 max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
702 if (n_unroll > max_unroll)
706 edge_to_cancel = loop_edge_to_cancel (loop);
714 vec<edge> to_remove = vNULL;
715 if (ul == UL_SINGLE_ITER)
718 large = tree_estimate_loop_size
719 (loop, exit, edge_to_cancel, &size,
720 PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS));
721 ninsns = size.overall;
724 if (dump_file && (dump_flags & TDF_DETAILS))
725 fprintf (dump_file, "Not unrolling loop %d: it is too large.\n",
730 unr_insns = estimated_unrolled_size (&size, n_unroll);
731 if (dump_file && (dump_flags & TDF_DETAILS))
733 fprintf (dump_file, " Loop size: %d\n", (int) ninsns);
734 fprintf (dump_file, " Estimated size after unrolling: %d\n",
738 /* If the code is going to shrink, we don't need to be extra cautious
739 on guessing if the unrolling is going to be profitable. */
741 /* If there is IV variable that will become constant, we save
742 one instruction in the loop prologue we do not account
744 <= ninsns + (size.constant_iv != false))
746 /* We unroll only inner loops, because we do not consider it profitable
747 otheriwse. We still can cancel loopback edge of not rolling loop;
748 this is always a good idea. */
749 else if (ul == UL_NO_GROWTH)
751 if (dump_file && (dump_flags & TDF_DETAILS))
752 fprintf (dump_file, "Not unrolling loop %d: size would grow.\n",
756 /* Outer loops tend to be less interesting candidates for complette
757 unrolling unless we can do a lot of propagation into the inner loop
758 body. For now we disable outer loop unrolling when the code would
760 else if (loop->inner)
762 if (dump_file && (dump_flags & TDF_DETAILS))
763 fprintf (dump_file, "Not unrolling loop %d: "
764 "it is not innermost and code would grow.\n",
768 /* If there is call on a hot path through the loop, then
769 there is most probably not much to optimize. */
770 else if (size.num_non_pure_calls_on_hot_path)
772 if (dump_file && (dump_flags & TDF_DETAILS))
773 fprintf (dump_file, "Not unrolling loop %d: "
774 "contains call and code would grow.\n",
778 /* If there is pure/const call in the function, then we
779 can still optimize the unrolled loop body if it contains
780 some other interesting code than the calls and code
781 storing or cumulating the return value. */
782 else if (size.num_pure_calls_on_hot_path
783 /* One IV increment, one test, one ivtmp store
784 and one useful stmt. That is about minimal loop
786 && (size.non_call_stmts_on_hot_path
787 <= 3 + size.num_pure_calls_on_hot_path))
789 if (dump_file && (dump_flags & TDF_DETAILS))
790 fprintf (dump_file, "Not unrolling loop %d: "
791 "contains just pure calls and code would grow.\n",
795 /* Complette unrolling is major win when control flow is removed and
796 one big basic block is created. If the loop contains control flow
797 the optimization may still be a win because of eliminating the loop
798 overhead but it also may blow the branch predictor tables.
799 Limit number of branches on the hot path through the peeled
801 else if (size.num_branches_on_hot_path * (int)n_unroll
802 > PARAM_VALUE (PARAM_MAX_PEEL_BRANCHES))
804 if (dump_file && (dump_flags & TDF_DETAILS))
805 fprintf (dump_file, "Not unrolling loop %d: "
806 " number of branches on hot path in the unrolled sequence"
807 " reach --param max-peel-branches limit.\n",
812 > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
814 if (dump_file && (dump_flags & TDF_DETAILS))
815 fprintf (dump_file, "Not unrolling loop %d: "
816 "(--param max-completely-peeled-insns limit reached).\n",
821 initialize_original_copy_tables ();
822 wont_exit = sbitmap_alloc (n_unroll + 1);
823 bitmap_ones (wont_exit);
824 bitmap_clear_bit (wont_exit, 0);
826 if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
829 DLTHE_FLAG_UPDATE_FREQ
830 | DLTHE_FLAG_COMPLETTE_PEEL))
832 free_original_copy_tables ();
834 if (dump_file && (dump_flags & TDF_DETAILS))
835 fprintf (dump_file, "Failed to duplicate the loop\n");
839 FOR_EACH_VEC_ELT (to_remove, i, e)
841 bool ok = remove_path (e);
845 to_remove.release ();
847 free_original_copy_tables ();
851 /* Remove the conditional from the last copy of the loop. */
854 cond = last_stmt (edge_to_cancel->src);
855 if (edge_to_cancel->flags & EDGE_TRUE_VALUE)
856 gimple_cond_make_false (cond);
858 gimple_cond_make_true (cond);
860 /* Do not remove the path. Doing so may remove outer loop
861 and confuse bookkeeping code in tree_unroll_loops_completelly. */
864 /* Store the loop for later unlooping and exit removal. */
865 loops_to_unloop.safe_push (loop);
866 loops_to_unloop_nunroll.safe_push (n_unroll);
868 if (dump_enabled_p ())
871 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, locus,
872 "loop turned into non-loop; it never loops\n");
875 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, locus,
876 "loop with %d iterations completely unrolled",
877 (int) (n_unroll + 1));
879 dump_printf (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS,
880 " (header execution count %d)",
881 (int)loop->header->count);
882 dump_printf (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, "\n");
886 if (dump_file && (dump_flags & TDF_DETAILS))
889 fprintf (dump_file, "Exit condition of peeled iterations was "
892 fprintf (dump_file, "Last iteration exit edge was proved true.\n");
894 fprintf (dump_file, "Latch of last iteration was marked by "
895 "__builtin_unreachable ().\n");
901 /* Adds a canonical induction variable to LOOP if suitable.
902 CREATE_IV is true if we may create a new iv. UL determines
903 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
904 to determine the number of iterations of a loop by direct evaluation.
905 Returns true if cfg is changed. */
908 canonicalize_loop_induction_variables (struct loop *loop,
909 bool create_iv, enum unroll_level ul,
914 HOST_WIDE_INT maxiter;
915 bool modified = false;
916 location_t locus = UNKNOWN_LOCATION;
918 niter = number_of_latch_executions (loop);
919 exit = single_exit (loop);
920 if (TREE_CODE (niter) == INTEGER_CST)
921 locus = gimple_location (last_stmt (exit->src));
924 /* If the loop has more than one exit, try checking all of them
925 for # of iterations determinable through scev. */
927 niter = find_loop_niter (loop, &exit);
929 /* Finally if everything else fails, try brute force evaluation. */
931 && (chrec_contains_undetermined (niter)
932 || TREE_CODE (niter) != INTEGER_CST))
933 niter = find_loop_niter_by_eval (loop, &exit);
936 locus = gimple_location (last_stmt (exit->src));
938 if (TREE_CODE (niter) != INTEGER_CST)
942 /* We work exceptionally hard here to estimate the bound
943 by find_loop_niter_by_eval. Be sure to keep it for future. */
944 if (niter && TREE_CODE (niter) == INTEGER_CST)
946 record_niter_bound (loop, niter,
947 exit == single_likely_exit (loop), true);
950 /* Force re-computation of loop bounds so we can remove redundant exits. */
951 maxiter = max_loop_iterations_int (loop);
953 if (dump_file && (dump_flags & TDF_DETAILS)
954 && TREE_CODE (niter) == INTEGER_CST)
956 fprintf (dump_file, "Loop %d iterates ", loop->num);
957 print_generic_expr (dump_file, niter, TDF_SLIM);
958 fprintf (dump_file, " times.\n");
960 if (dump_file && (dump_flags & TDF_DETAILS)
963 fprintf (dump_file, "Loop %d iterates at most %i times.\n", loop->num,
967 /* Remove exits that are known to be never taken based on loop bound.
968 Needs to be called after compilation of max_loop_iterations_int that
969 populates the loop bounds. */
970 modified |= remove_redundant_iv_tests (loop);
972 if (try_unroll_loop_completely (loop, exit, niter, ul, maxiter, locus))
976 && niter && !chrec_contains_undetermined (niter)
977 && exit && just_once_each_iteration_p (loop, exit->src))
978 create_canonical_iv (loop, exit, niter);
983 /* The main entry point of the pass. Adds canonical induction variables
984 to the suitable loops. */
987 canonicalize_induction_variables (void)
991 bool changed = false;
992 bool irred_invalidated = false;
993 bitmap loop_closed_ssa_invalidated = BITMAP_ALLOC (NULL);
995 free_numbers_of_iterations_estimates ();
996 estimate_numbers_of_iterations ();
998 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
1000 changed |= canonicalize_loop_induction_variables (loop,
1001 true, UL_SINGLE_ITER,
1004 gcc_assert (!need_ssa_update_p (cfun));
1006 unloop_loops (loop_closed_ssa_invalidated, &irred_invalidated);
1007 if (irred_invalidated
1008 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1009 mark_irreducible_loops ();
1011 /* Clean up the information about numbers of iterations, since brute force
1012 evaluation could reveal new information. */
1015 if (!bitmap_empty_p (loop_closed_ssa_invalidated))
1017 gcc_checking_assert (loops_state_satisfies_p (LOOP_CLOSED_SSA));
1018 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1020 BITMAP_FREE (loop_closed_ssa_invalidated);
1023 return TODO_cleanup_cfg;
1027 /* Propagate VAL into all uses of SSA_NAME. */
1030 propagate_into_all_uses (tree ssa_name, tree val)
1032 imm_use_iterator iter;
1035 FOR_EACH_IMM_USE_STMT (use_stmt, iter, ssa_name)
1037 gimple_stmt_iterator use_stmt_gsi = gsi_for_stmt (use_stmt);
1040 FOR_EACH_IMM_USE_ON_STMT (use, iter)
1043 if (is_gimple_assign (use_stmt)
1044 && get_gimple_rhs_class (gimple_assign_rhs_code (use_stmt))
1045 == GIMPLE_SINGLE_RHS)
1047 tree rhs = gimple_assign_rhs1 (use_stmt);
1049 if (TREE_CODE (rhs) == ADDR_EXPR)
1050 recompute_tree_invariant_for_addr_expr (rhs);
1053 fold_stmt_inplace (&use_stmt_gsi);
1054 update_stmt (use_stmt);
1055 maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt);
1059 /* Propagate constant SSA_NAMEs defined in basic block BB. */
1062 propagate_constants_for_unrolling (basic_block bb)
1064 gimple_stmt_iterator gsi;
1066 /* Look for degenerate PHI nodes with constant argument. */
1067 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
1069 gimple phi = gsi_stmt (gsi);
1070 tree result = gimple_phi_result (phi);
1071 tree arg = gimple_phi_arg_def (phi, 0);
1073 if (gimple_phi_num_args (phi) == 1 && TREE_CODE (arg) == INTEGER_CST)
1075 propagate_into_all_uses (result, arg);
1076 gsi_remove (&gsi, true);
1077 release_ssa_name (result);
1083 /* Look for assignments to SSA names with constant RHS. */
1084 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
1086 gimple stmt = gsi_stmt (gsi);
1089 if (is_gimple_assign (stmt)
1090 && gimple_assign_rhs_code (stmt) == INTEGER_CST
1091 && (lhs = gimple_assign_lhs (stmt), TREE_CODE (lhs) == SSA_NAME)
1092 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1094 propagate_into_all_uses (lhs, gimple_assign_rhs1 (stmt));
1095 gsi_remove (&gsi, true);
1096 release_ssa_name (lhs);
1103 /* Process loops from innermost to outer, stopping at the innermost
1104 loop we unrolled. */
1107 tree_unroll_loops_completely_1 (bool may_increase_size, bool unroll_outer,
1108 vec<loop_p, va_stack>& father_stack,
1111 struct loop *loop_father;
1112 bool changed = false;
1114 enum unroll_level ul;
1116 /* Process inner loops first. */
1117 for (inner = loop->inner; inner != NULL; inner = inner->next)
1118 changed |= tree_unroll_loops_completely_1 (may_increase_size,
1119 unroll_outer, father_stack,
1122 /* If we changed an inner loop we cannot process outer loops in this
1123 iteration because SSA form is not up-to-date. Continue with
1124 siblings of outer loops instead. */
1128 /* Don't unroll #pragma omp simd loops until the vectorizer
1129 attempts to vectorize those. */
1130 if (loop->force_vect)
1133 /* Try to unroll this loop. */
1134 loop_father = loop_outer (loop);
1138 if (may_increase_size && optimize_loop_nest_for_speed_p (loop)
1139 /* Unroll outermost loops only if asked to do so or they do
1140 not cause code growth. */
1141 && (unroll_outer || loop_outer (loop_father)))
1146 if (canonicalize_loop_induction_variables
1147 (loop, false, ul, !flag_tree_loop_ivcanon))
1149 /* If we'll continue unrolling, we need to propagate constants
1150 within the new basic blocks to fold away induction variable
1151 computations; otherwise, the size might blow up before the
1152 iteration is complete and the IR eventually cleaned up. */
1153 if (loop_outer (loop_father) && !loop_father->aux)
1155 father_stack.safe_push (loop_father);
1156 loop_father->aux = loop_father;
1165 /* Unroll LOOPS completely if they iterate just few times. Unless
1166 MAY_INCREASE_SIZE is true, perform the unrolling only if the
1167 size of the code does not increase. */
1170 tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)
1172 vec<loop_p, va_stack> father_stack;
1175 bool irred_invalidated = false;
1177 vec_stack_alloc (loop_p, father_stack, 16);
1181 bitmap loop_closed_ssa_invalidated = NULL;
1183 if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
1184 loop_closed_ssa_invalidated = BITMAP_ALLOC (NULL);
1186 free_numbers_of_iterations_estimates ();
1187 estimate_numbers_of_iterations ();
1189 changed = tree_unroll_loops_completely_1 (may_increase_size,
1190 unroll_outer, father_stack,
1191 current_loops->tree_root);
1197 /* Be sure to skip unlooped loops while procesing father_stack
1199 FOR_EACH_VEC_ELT (loops_to_unloop, i, iter)
1200 (*iter)->aux = NULL;
1201 FOR_EACH_VEC_ELT (father_stack, i, iter)
1204 unloop_loops (loop_closed_ssa_invalidated, &irred_invalidated);
1206 /* We can not use TODO_update_ssa_no_phi because VOPS gets confused. */
1207 if (loop_closed_ssa_invalidated
1208 && !bitmap_empty_p (loop_closed_ssa_invalidated))
1209 rewrite_into_loop_closed_ssa (loop_closed_ssa_invalidated,
1212 update_ssa (TODO_update_ssa);
1214 /* Propagate the constants within the new basic blocks. */
1215 FOR_EACH_VEC_ELT (father_stack, i, iter)
1219 basic_block *body = get_loop_body_in_dom_order (*iter);
1220 for (j = 0; j < (*iter)->num_nodes; j++)
1221 propagate_constants_for_unrolling (body[j]);
1223 (*iter)->aux = NULL;
1225 father_stack.truncate (0);
1227 /* This will take care of removing completely unrolled loops
1228 from the loop structures so we can continue unrolling now
1230 if (cleanup_tree_cfg ())
1231 update_ssa (TODO_update_ssa_only_virtuals);
1233 /* Clean up the information about numbers of iterations, since
1234 complete unrolling might have invalidated it. */
1236 #ifdef ENABLE_CHECKING
1237 if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
1238 verify_loop_closed_ssa (true);
1241 if (loop_closed_ssa_invalidated)
1242 BITMAP_FREE (loop_closed_ssa_invalidated);
1245 && ++iteration <= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS));
1247 father_stack.release ();
1249 if (irred_invalidated
1250 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1251 mark_irreducible_loops ();