* tree.h (TYPE_OVERFLOW_SANITIZED): Define.
[official-gcc.git] / gcc / tree-ssa-loop-ivcanon.c
blob73ad46aedacb1a576e46c9f3c6fc16d21023f892
1 /* Induction variable canonicalization and loop peeling.
2 Copyright (C) 2004-2014 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
9 later version.
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
14 for more details.
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
29 to pay up.
31 We also perform
32 - complette unrolling (or peeling) when the loops is rolling few enough
33 times
34 - simple peeling (i.e. copying few initial iterations prior the loop)
35 when number of iteration estimate is known (typically by the profile
36 info). */
38 #include "config.h"
39 #include "system.h"
40 #include "coretypes.h"
41 #include "tm.h"
42 #include "tree.h"
43 #include "tm_p.h"
44 #include "profile.h"
45 #include "predict.h"
46 #include "vec.h"
47 #include "hashtab.h"
48 #include "hash-set.h"
49 #include "machmode.h"
50 #include "hard-reg-set.h"
51 #include "input.h"
52 #include "function.h"
53 #include "dominance.h"
54 #include "cfg.h"
55 #include "basic-block.h"
56 #include "gimple-pretty-print.h"
57 #include "tree-ssa-alias.h"
58 #include "internal-fn.h"
59 #include "gimple-fold.h"
60 #include "tree-eh.h"
61 #include "gimple-expr.h"
62 #include "is-a.h"
63 #include "gimple.h"
64 #include "gimple-iterator.h"
65 #include "gimple-ssa.h"
66 #include "hash-map.h"
67 #include "plugin-api.h"
68 #include "ipa-ref.h"
69 #include "cgraph.h"
70 #include "tree-cfg.h"
71 #include "tree-phinodes.h"
72 #include "ssa-iterators.h"
73 #include "stringpool.h"
74 #include "tree-ssanames.h"
75 #include "tree-ssa-loop-manip.h"
76 #include "tree-ssa-loop-niter.h"
77 #include "tree-ssa-loop.h"
78 #include "tree-into-ssa.h"
79 #include "cfgloop.h"
80 #include "tree-pass.h"
81 #include "tree-chrec.h"
82 #include "tree-scalar-evolution.h"
83 #include "params.h"
84 #include "flags.h"
85 #include "tree-inline.h"
86 #include "target.h"
87 #include "tree-cfgcleanup.h"
88 #include "builtins.h"
90 /* Specifies types of loops that may be unrolled. */
92 enum unroll_level
94 UL_SINGLE_ITER, /* Only loops that exit immediately in the first
95 iteration. */
96 UL_NO_GROWTH, /* Only loops whose unrolling will not cause increase
97 of code size. */
98 UL_ALL /* All suitable loops. */
101 /* Adds a canonical induction variable to LOOP iterating NITER times. EXIT
102 is the exit edge whose condition is replaced. */
104 static void
105 create_canonical_iv (struct loop *loop, edge exit, tree niter)
107 edge in;
108 tree type, var;
109 gimple cond;
110 gimple_stmt_iterator incr_at;
111 enum tree_code cmp;
113 if (dump_file && (dump_flags & TDF_DETAILS))
115 fprintf (dump_file, "Added canonical iv to loop %d, ", loop->num);
116 print_generic_expr (dump_file, niter, TDF_SLIM);
117 fprintf (dump_file, " iterations.\n");
120 cond = last_stmt (exit->src);
121 in = EDGE_SUCC (exit->src, 0);
122 if (in == exit)
123 in = EDGE_SUCC (exit->src, 1);
125 /* Note that we do not need to worry about overflows, since
126 type of niter is always unsigned and all comparisons are
127 just for equality/nonequality -- i.e. everything works
128 with a modulo arithmetics. */
130 type = TREE_TYPE (niter);
131 niter = fold_build2 (PLUS_EXPR, type,
132 niter,
133 build_int_cst (type, 1));
134 incr_at = gsi_last_bb (in->src);
135 create_iv (niter,
136 build_int_cst (type, -1),
137 NULL_TREE, loop,
138 &incr_at, false, NULL, &var);
140 cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
141 gimple_cond_set_code (cond, cmp);
142 gimple_cond_set_lhs (cond, var);
143 gimple_cond_set_rhs (cond, build_int_cst (type, 0));
144 update_stmt (cond);
147 /* Describe size of loop as detected by tree_estimate_loop_size. */
148 struct loop_size
150 /* Number of instructions in the loop. */
151 int overall;
153 /* Number of instructions that will be likely optimized out in
154 peeled iterations of loop (i.e. computation based on induction
155 variable where induction variable starts at known constant.) */
156 int eliminated_by_peeling;
158 /* Same statistics for last iteration of loop: it is smaller because
159 instructions after exit are not executed. */
160 int last_iteration;
161 int last_iteration_eliminated_by_peeling;
163 /* If some IV computation will become constant. */
164 bool constant_iv;
166 /* Number of call stmts that are not a builtin and are pure or const
167 present on the hot path. */
168 int num_pure_calls_on_hot_path;
169 /* Number of call stmts that are not a builtin and are not pure nor const
170 present on the hot path. */
171 int num_non_pure_calls_on_hot_path;
172 /* Number of statements other than calls in the loop. */
173 int non_call_stmts_on_hot_path;
174 /* Number of branches seen on the hot path. */
175 int num_branches_on_hot_path;
178 /* Return true if OP in STMT will be constant after peeling LOOP. */
180 static bool
181 constant_after_peeling (tree op, gimple stmt, struct loop *loop)
183 affine_iv iv;
185 if (is_gimple_min_invariant (op))
186 return true;
188 /* We can still fold accesses to constant arrays when index is known. */
189 if (TREE_CODE (op) != SSA_NAME)
191 tree base = op;
193 /* First make fast look if we see constant array inside. */
194 while (handled_component_p (base))
195 base = TREE_OPERAND (base, 0);
196 if ((DECL_P (base)
197 && ctor_for_folding (base) != error_mark_node)
198 || CONSTANT_CLASS_P (base))
200 /* If so, see if we understand all the indices. */
201 base = op;
202 while (handled_component_p (base))
204 if (TREE_CODE (base) == ARRAY_REF
205 && !constant_after_peeling (TREE_OPERAND (base, 1), stmt, loop))
206 return false;
207 base = TREE_OPERAND (base, 0);
209 return true;
211 return false;
214 /* Induction variables are constants. */
215 if (!simple_iv (loop, loop_containing_stmt (stmt), op, &iv, false))
216 return false;
217 if (!is_gimple_min_invariant (iv.base))
218 return false;
219 if (!is_gimple_min_invariant (iv.step))
220 return false;
221 return true;
224 /* Computes an estimated number of insns in LOOP.
225 EXIT (if non-NULL) is an exite edge that will be eliminated in all but last
226 iteration of the loop.
227 EDGE_TO_CANCEL (if non-NULL) is an non-exit edge eliminated in the last iteration
228 of loop.
229 Return results in SIZE, estimate benefits for complete unrolling exiting by EXIT.
230 Stop estimating after UPPER_BOUND is met. Return true in this case. */
232 static bool
233 tree_estimate_loop_size (struct loop *loop, edge exit, edge edge_to_cancel, struct loop_size *size,
234 int upper_bound)
236 basic_block *body = get_loop_body (loop);
237 gimple_stmt_iterator gsi;
238 unsigned int i;
239 bool after_exit;
240 vec<basic_block> path = get_loop_hot_path (loop);
242 size->overall = 0;
243 size->eliminated_by_peeling = 0;
244 size->last_iteration = 0;
245 size->last_iteration_eliminated_by_peeling = 0;
246 size->num_pure_calls_on_hot_path = 0;
247 size->num_non_pure_calls_on_hot_path = 0;
248 size->non_call_stmts_on_hot_path = 0;
249 size->num_branches_on_hot_path = 0;
250 size->constant_iv = 0;
252 if (dump_file && (dump_flags & TDF_DETAILS))
253 fprintf (dump_file, "Estimating sizes for loop %i\n", loop->num);
254 for (i = 0; i < loop->num_nodes; i++)
256 if (edge_to_cancel && body[i] != edge_to_cancel->src
257 && dominated_by_p (CDI_DOMINATORS, body[i], edge_to_cancel->src))
258 after_exit = true;
259 else
260 after_exit = false;
261 if (dump_file && (dump_flags & TDF_DETAILS))
262 fprintf (dump_file, " BB: %i, after_exit: %i\n", body[i]->index, after_exit);
264 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
266 gimple stmt = gsi_stmt (gsi);
267 int num = estimate_num_insns (stmt, &eni_size_weights);
268 bool likely_eliminated = false;
269 bool likely_eliminated_last = false;
270 bool likely_eliminated_peeled = false;
272 if (dump_file && (dump_flags & TDF_DETAILS))
274 fprintf (dump_file, " size: %3i ", num);
275 print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, 0);
278 /* Look for reasons why we might optimize this stmt away. */
280 if (gimple_has_side_effects (stmt))
282 /* Exit conditional. */
283 else if (exit && body[i] == exit->src
284 && stmt == last_stmt (exit->src))
286 if (dump_file && (dump_flags & TDF_DETAILS))
287 fprintf (dump_file, " Exit condition will be eliminated "
288 "in peeled copies.\n");
289 likely_eliminated_peeled = true;
291 else if (edge_to_cancel && body[i] == edge_to_cancel->src
292 && stmt == last_stmt (edge_to_cancel->src))
294 if (dump_file && (dump_flags & TDF_DETAILS))
295 fprintf (dump_file, " Exit condition will be eliminated "
296 "in last copy.\n");
297 likely_eliminated_last = true;
299 /* Sets of IV variables */
300 else if (gimple_code (stmt) == GIMPLE_ASSIGN
301 && constant_after_peeling (gimple_assign_lhs (stmt), stmt, loop))
303 if (dump_file && (dump_flags & TDF_DETAILS))
304 fprintf (dump_file, " Induction variable computation will"
305 " be folded away.\n");
306 likely_eliminated = true;
308 /* Assignments of IV variables. */
309 else if (gimple_code (stmt) == GIMPLE_ASSIGN
310 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
311 && constant_after_peeling (gimple_assign_rhs1 (stmt), stmt, loop)
312 && (gimple_assign_rhs_class (stmt) != GIMPLE_BINARY_RHS
313 || constant_after_peeling (gimple_assign_rhs2 (stmt),
314 stmt, loop)))
316 size->constant_iv = true;
317 if (dump_file && (dump_flags & TDF_DETAILS))
318 fprintf (dump_file, " Constant expression will be folded away.\n");
319 likely_eliminated = true;
321 /* Conditionals. */
322 else if ((gimple_code (stmt) == GIMPLE_COND
323 && constant_after_peeling (gimple_cond_lhs (stmt), stmt, loop)
324 && constant_after_peeling (gimple_cond_rhs (stmt), stmt, loop))
325 || (gimple_code (stmt) == GIMPLE_SWITCH
326 && constant_after_peeling (gimple_switch_index (stmt), stmt, loop)))
328 if (dump_file && (dump_flags & TDF_DETAILS))
329 fprintf (dump_file, " Constant conditional.\n");
330 likely_eliminated = true;
333 size->overall += num;
334 if (likely_eliminated || likely_eliminated_peeled)
335 size->eliminated_by_peeling += num;
336 if (!after_exit)
338 size->last_iteration += num;
339 if (likely_eliminated || likely_eliminated_last)
340 size->last_iteration_eliminated_by_peeling += num;
342 if ((size->overall * 3 / 2 - size->eliminated_by_peeling
343 - size->last_iteration_eliminated_by_peeling) > upper_bound)
345 free (body);
346 path.release ();
347 return true;
351 while (path.length ())
353 basic_block bb = path.pop ();
354 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
356 gimple stmt = gsi_stmt (gsi);
357 if (gimple_code (stmt) == GIMPLE_CALL)
359 int flags = gimple_call_flags (stmt);
360 tree decl = gimple_call_fndecl (stmt);
362 if (decl && DECL_IS_BUILTIN (decl)
363 && is_inexpensive_builtin (decl))
365 else if (flags & (ECF_PURE | ECF_CONST))
366 size->num_pure_calls_on_hot_path++;
367 else
368 size->num_non_pure_calls_on_hot_path++;
369 size->num_branches_on_hot_path ++;
371 else if (gimple_code (stmt) != GIMPLE_CALL
372 && gimple_code (stmt) != GIMPLE_DEBUG)
373 size->non_call_stmts_on_hot_path++;
374 if (((gimple_code (stmt) == GIMPLE_COND
375 && (!constant_after_peeling (gimple_cond_lhs (stmt), stmt, loop)
376 || constant_after_peeling (gimple_cond_rhs (stmt), stmt, loop)))
377 || (gimple_code (stmt) == GIMPLE_SWITCH
378 && !constant_after_peeling (gimple_switch_index (stmt), stmt, loop)))
379 && (!exit || bb != exit->src))
380 size->num_branches_on_hot_path++;
383 path.release ();
384 if (dump_file && (dump_flags & TDF_DETAILS))
385 fprintf (dump_file, "size: %i-%i, last_iteration: %i-%i\n", size->overall,
386 size->eliminated_by_peeling, size->last_iteration,
387 size->last_iteration_eliminated_by_peeling);
389 free (body);
390 return false;
393 /* Estimate number of insns of completely unrolled loop.
394 It is (NUNROLL + 1) * size of loop body with taking into account
395 the fact that in last copy everything after exit conditional
396 is dead and that some instructions will be eliminated after
397 peeling.
399 Loop body is likely going to simplify further, this is difficult
400 to guess, we just decrease the result by 1/3. */
402 static unsigned HOST_WIDE_INT
403 estimated_unrolled_size (struct loop_size *size,
404 unsigned HOST_WIDE_INT nunroll)
406 HOST_WIDE_INT unr_insns = ((nunroll)
407 * (HOST_WIDE_INT) (size->overall
408 - size->eliminated_by_peeling));
409 if (!nunroll)
410 unr_insns = 0;
411 unr_insns += size->last_iteration - size->last_iteration_eliminated_by_peeling;
413 unr_insns = unr_insns * 2 / 3;
414 if (unr_insns <= 0)
415 unr_insns = 1;
417 return unr_insns;
420 /* Loop LOOP is known to not loop. See if there is an edge in the loop
421 body that can be remove to make the loop to always exit and at
422 the same time it does not make any code potentially executed
423 during the last iteration dead.
425 After complette unrolling we still may get rid of the conditional
426 on the exit in the last copy even if we have no idea what it does.
427 This is quite common case for loops of form
429 int a[5];
430 for (i=0;i<b;i++)
431 a[i]=0;
433 Here we prove the loop to iterate 5 times but we do not know
434 it from induction variable.
436 For now we handle only simple case where there is exit condition
437 just before the latch block and the latch block contains no statements
438 with side effect that may otherwise terminate the execution of loop
439 (such as by EH or by terminating the program or longjmp).
441 In the general case we may want to cancel the paths leading to statements
442 loop-niter identified as having undefined effect in the last iteration.
443 The other cases are hopefully rare and will be cleaned up later. */
445 static edge
446 loop_edge_to_cancel (struct loop *loop)
448 vec<edge> exits;
449 unsigned i;
450 edge edge_to_cancel;
451 gimple_stmt_iterator gsi;
453 /* We want only one predecestor of the loop. */
454 if (EDGE_COUNT (loop->latch->preds) > 1)
455 return NULL;
457 exits = get_loop_exit_edges (loop);
459 FOR_EACH_VEC_ELT (exits, i, edge_to_cancel)
461 /* Find the other edge than the loop exit
462 leaving the conditoinal. */
463 if (EDGE_COUNT (edge_to_cancel->src->succs) != 2)
464 continue;
465 if (EDGE_SUCC (edge_to_cancel->src, 0) == edge_to_cancel)
466 edge_to_cancel = EDGE_SUCC (edge_to_cancel->src, 1);
467 else
468 edge_to_cancel = EDGE_SUCC (edge_to_cancel->src, 0);
470 /* We only can handle conditionals. */
471 if (!(edge_to_cancel->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
472 continue;
474 /* We should never have conditionals in the loop latch. */
475 gcc_assert (edge_to_cancel->dest != loop->header);
477 /* Check that it leads to loop latch. */
478 if (edge_to_cancel->dest != loop->latch)
479 continue;
481 exits.release ();
483 /* Verify that the code in loop latch does nothing that may end program
484 execution without really reaching the exit. This may include
485 non-pure/const function calls, EH statements, volatile ASMs etc. */
486 for (gsi = gsi_start_bb (loop->latch); !gsi_end_p (gsi); gsi_next (&gsi))
487 if (gimple_has_side_effects (gsi_stmt (gsi)))
488 return NULL;
489 return edge_to_cancel;
491 exits.release ();
492 return NULL;
495 /* Remove all tests for exits that are known to be taken after LOOP was
496 peeled NPEELED times. Put gcc_unreachable before every statement
497 known to not be executed. */
499 static bool
500 remove_exits_and_undefined_stmts (struct loop *loop, unsigned int npeeled)
502 struct nb_iter_bound *elt;
503 bool changed = false;
505 for (elt = loop->bounds; elt; elt = elt->next)
507 /* If statement is known to be undefined after peeling, turn it
508 into unreachable (or trap when debugging experience is supposed
509 to be good). */
510 if (!elt->is_exit
511 && wi::ltu_p (elt->bound, npeeled))
513 gimple_stmt_iterator gsi = gsi_for_stmt (elt->stmt);
514 gimple stmt = gimple_build_call
515 (builtin_decl_implicit (BUILT_IN_UNREACHABLE), 0);
517 gimple_set_location (stmt, gimple_location (elt->stmt));
518 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
519 changed = true;
520 if (dump_file && (dump_flags & TDF_DETAILS))
522 fprintf (dump_file, "Forced statement unreachable: ");
523 print_gimple_stmt (dump_file, elt->stmt, 0, 0);
526 /* If we know the exit will be taken after peeling, update. */
527 else if (elt->is_exit
528 && wi::leu_p (elt->bound, npeeled))
530 basic_block bb = gimple_bb (elt->stmt);
531 edge exit_edge = EDGE_SUCC (bb, 0);
533 if (dump_file && (dump_flags & TDF_DETAILS))
535 fprintf (dump_file, "Forced exit to be taken: ");
536 print_gimple_stmt (dump_file, elt->stmt, 0, 0);
538 if (!loop_exit_edge_p (loop, exit_edge))
539 exit_edge = EDGE_SUCC (bb, 1);
540 gcc_checking_assert (loop_exit_edge_p (loop, exit_edge));
541 if (exit_edge->flags & EDGE_TRUE_VALUE)
542 gimple_cond_make_true (elt->stmt);
543 else
544 gimple_cond_make_false (elt->stmt);
545 update_stmt (elt->stmt);
546 changed = true;
549 return changed;
552 /* Remove all exits that are known to be never taken because of the loop bound
553 discovered. */
555 static bool
556 remove_redundant_iv_tests (struct loop *loop)
558 struct nb_iter_bound *elt;
559 bool changed = false;
561 if (!loop->any_upper_bound)
562 return false;
563 for (elt = loop->bounds; elt; elt = elt->next)
565 /* Exit is pointless if it won't be taken before loop reaches
566 upper bound. */
567 if (elt->is_exit && loop->any_upper_bound
568 && wi::ltu_p (loop->nb_iterations_upper_bound, elt->bound))
570 basic_block bb = gimple_bb (elt->stmt);
571 edge exit_edge = EDGE_SUCC (bb, 0);
572 struct tree_niter_desc niter;
574 if (!loop_exit_edge_p (loop, exit_edge))
575 exit_edge = EDGE_SUCC (bb, 1);
577 /* Only when we know the actual number of iterations, not
578 just a bound, we can remove the exit. */
579 if (!number_of_iterations_exit (loop, exit_edge,
580 &niter, false, false)
581 || !integer_onep (niter.assumptions)
582 || !integer_zerop (niter.may_be_zero)
583 || !niter.niter
584 || TREE_CODE (niter.niter) != INTEGER_CST
585 || !wi::ltu_p (loop->nb_iterations_upper_bound,
586 wi::to_widest (niter.niter)))
587 continue;
589 if (dump_file && (dump_flags & TDF_DETAILS))
591 fprintf (dump_file, "Removed pointless exit: ");
592 print_gimple_stmt (dump_file, elt->stmt, 0, 0);
594 if (exit_edge->flags & EDGE_TRUE_VALUE)
595 gimple_cond_make_false (elt->stmt);
596 else
597 gimple_cond_make_true (elt->stmt);
598 update_stmt (elt->stmt);
599 changed = true;
602 return changed;
605 /* Stores loops that will be unlooped after we process whole loop tree. */
606 static vec<loop_p> loops_to_unloop;
607 static vec<int> loops_to_unloop_nunroll;
609 /* Cancel all fully unrolled loops by putting __builtin_unreachable
610 on the latch edge.
611 We do it after all unrolling since unlooping moves basic blocks
612 across loop boundaries trashing loop closed SSA form as well
613 as SCEV info needed to be intact during unrolling.
615 IRRED_INVALIDATED is used to bookkeep if information about
616 irreducible regions may become invalid as a result
617 of the transformation.
618 LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case
619 when we need to go into loop closed SSA form. */
621 static void
622 unloop_loops (bitmap loop_closed_ssa_invalidated,
623 bool *irred_invalidated)
625 while (loops_to_unloop.length ())
627 struct loop *loop = loops_to_unloop.pop ();
628 int n_unroll = loops_to_unloop_nunroll.pop ();
629 basic_block latch = loop->latch;
630 edge latch_edge = loop_latch_edge (loop);
631 int flags = latch_edge->flags;
632 location_t locus = latch_edge->goto_locus;
633 gimple stmt;
634 gimple_stmt_iterator gsi;
636 remove_exits_and_undefined_stmts (loop, n_unroll);
638 /* Unloop destroys the latch edge. */
639 unloop (loop, irred_invalidated, loop_closed_ssa_invalidated);
641 /* Create new basic block for the latch edge destination and wire
642 it in. */
643 stmt = gimple_build_call (builtin_decl_implicit (BUILT_IN_UNREACHABLE), 0);
644 latch_edge = make_edge (latch, create_basic_block (NULL, NULL, latch), flags);
645 latch_edge->probability = 0;
646 latch_edge->count = 0;
647 latch_edge->flags |= flags;
648 latch_edge->goto_locus = locus;
650 latch_edge->dest->loop_father = current_loops->tree_root;
651 latch_edge->dest->count = 0;
652 latch_edge->dest->frequency = 0;
653 set_immediate_dominator (CDI_DOMINATORS, latch_edge->dest, latch_edge->src);
655 gsi = gsi_start_bb (latch_edge->dest);
656 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
658 loops_to_unloop.release ();
659 loops_to_unloop_nunroll.release ();
662 /* Tries to unroll LOOP completely, i.e. NITER times.
663 UL determines which loops we are allowed to unroll.
664 EXIT is the exit of the loop that should be eliminated.
665 MAXITER specfy bound on number of iterations, -1 if it is
666 not known or too large for HOST_WIDE_INT. The location
667 LOCUS corresponding to the loop is used when emitting
668 a summary of the unroll to the dump file. */
670 static bool
671 try_unroll_loop_completely (struct loop *loop,
672 edge exit, tree niter,
673 enum unroll_level ul,
674 HOST_WIDE_INT maxiter,
675 location_t locus)
677 unsigned HOST_WIDE_INT n_unroll = 0, ninsns, max_unroll, unr_insns;
678 gimple cond;
679 struct loop_size size;
680 bool n_unroll_found = false;
681 edge edge_to_cancel = NULL;
682 int report_flags = MSG_OPTIMIZED_LOCATIONS | TDF_RTL | TDF_DETAILS;
684 /* See if we proved number of iterations to be low constant.
686 EXIT is an edge that will be removed in all but last iteration of
687 the loop.
689 EDGE_TO_CACNEL is an edge that will be removed from the last iteration
690 of the unrolled sequence and is expected to make the final loop not
691 rolling.
693 If the number of execution of loop is determined by standard induction
694 variable test, then EXIT and EDGE_TO_CANCEL are the two edges leaving
695 from the iv test. */
696 if (tree_fits_uhwi_p (niter))
698 n_unroll = tree_to_uhwi (niter);
699 n_unroll_found = true;
700 edge_to_cancel = EDGE_SUCC (exit->src, 0);
701 if (edge_to_cancel == exit)
702 edge_to_cancel = EDGE_SUCC (exit->src, 1);
704 /* We do not know the number of iterations and thus we can not eliminate
705 the EXIT edge. */
706 else
707 exit = NULL;
709 /* See if we can improve our estimate by using recorded loop bounds. */
710 if (maxiter >= 0
711 && (!n_unroll_found || (unsigned HOST_WIDE_INT)maxiter < n_unroll))
713 n_unroll = maxiter;
714 n_unroll_found = true;
715 /* Loop terminates before the IV variable test, so we can not
716 remove it in the last iteration. */
717 edge_to_cancel = NULL;
720 if (!n_unroll_found)
721 return false;
723 max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
724 if (n_unroll > max_unroll)
725 return false;
727 if (!edge_to_cancel)
728 edge_to_cancel = loop_edge_to_cancel (loop);
730 if (n_unroll)
732 sbitmap wont_exit;
733 edge e;
734 unsigned i;
735 bool large;
736 vec<edge> to_remove = vNULL;
737 if (ul == UL_SINGLE_ITER)
738 return false;
740 large = tree_estimate_loop_size
741 (loop, exit, edge_to_cancel, &size,
742 PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS));
743 ninsns = size.overall;
744 if (large)
746 if (dump_file && (dump_flags & TDF_DETAILS))
747 fprintf (dump_file, "Not unrolling loop %d: it is too large.\n",
748 loop->num);
749 return false;
752 unr_insns = estimated_unrolled_size (&size, n_unroll);
753 if (dump_file && (dump_flags & TDF_DETAILS))
755 fprintf (dump_file, " Loop size: %d\n", (int) ninsns);
756 fprintf (dump_file, " Estimated size after unrolling: %d\n",
757 (int) unr_insns);
760 /* If the code is going to shrink, we don't need to be extra cautious
761 on guessing if the unrolling is going to be profitable. */
762 if (unr_insns
763 /* If there is IV variable that will become constant, we save
764 one instruction in the loop prologue we do not account
765 otherwise. */
766 <= ninsns + (size.constant_iv != false))
768 /* We unroll only inner loops, because we do not consider it profitable
769 otheriwse. We still can cancel loopback edge of not rolling loop;
770 this is always a good idea. */
771 else if (ul == UL_NO_GROWTH)
773 if (dump_file && (dump_flags & TDF_DETAILS))
774 fprintf (dump_file, "Not unrolling loop %d: size would grow.\n",
775 loop->num);
776 return false;
778 /* Outer loops tend to be less interesting candidates for complette
779 unrolling unless we can do a lot of propagation into the inner loop
780 body. For now we disable outer loop unrolling when the code would
781 grow. */
782 else if (loop->inner)
784 if (dump_file && (dump_flags & TDF_DETAILS))
785 fprintf (dump_file, "Not unrolling loop %d: "
786 "it is not innermost and code would grow.\n",
787 loop->num);
788 return false;
790 /* If there is call on a hot path through the loop, then
791 there is most probably not much to optimize. */
792 else if (size.num_non_pure_calls_on_hot_path)
794 if (dump_file && (dump_flags & TDF_DETAILS))
795 fprintf (dump_file, "Not unrolling loop %d: "
796 "contains call and code would grow.\n",
797 loop->num);
798 return false;
800 /* If there is pure/const call in the function, then we
801 can still optimize the unrolled loop body if it contains
802 some other interesting code than the calls and code
803 storing or cumulating the return value. */
804 else if (size.num_pure_calls_on_hot_path
805 /* One IV increment, one test, one ivtmp store
806 and one useful stmt. That is about minimal loop
807 doing pure call. */
808 && (size.non_call_stmts_on_hot_path
809 <= 3 + size.num_pure_calls_on_hot_path))
811 if (dump_file && (dump_flags & TDF_DETAILS))
812 fprintf (dump_file, "Not unrolling loop %d: "
813 "contains just pure calls and code would grow.\n",
814 loop->num);
815 return false;
817 /* Complette unrolling is major win when control flow is removed and
818 one big basic block is created. If the loop contains control flow
819 the optimization may still be a win because of eliminating the loop
820 overhead but it also may blow the branch predictor tables.
821 Limit number of branches on the hot path through the peeled
822 sequence. */
823 else if (size.num_branches_on_hot_path * (int)n_unroll
824 > PARAM_VALUE (PARAM_MAX_PEEL_BRANCHES))
826 if (dump_file && (dump_flags & TDF_DETAILS))
827 fprintf (dump_file, "Not unrolling loop %d: "
828 " number of branches on hot path in the unrolled sequence"
829 " reach --param max-peel-branches limit.\n",
830 loop->num);
831 return false;
833 else if (unr_insns
834 > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
836 if (dump_file && (dump_flags & TDF_DETAILS))
837 fprintf (dump_file, "Not unrolling loop %d: "
838 "(--param max-completely-peeled-insns limit reached).\n",
839 loop->num);
840 return false;
842 dump_printf_loc (report_flags, locus,
843 "loop turned into non-loop; it never loops.\n");
845 initialize_original_copy_tables ();
846 wont_exit = sbitmap_alloc (n_unroll + 1);
847 bitmap_ones (wont_exit);
848 bitmap_clear_bit (wont_exit, 0);
850 if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
851 n_unroll, wont_exit,
852 exit, &to_remove,
853 DLTHE_FLAG_UPDATE_FREQ
854 | DLTHE_FLAG_COMPLETTE_PEEL))
856 free_original_copy_tables ();
857 free (wont_exit);
858 if (dump_file && (dump_flags & TDF_DETAILS))
859 fprintf (dump_file, "Failed to duplicate the loop\n");
860 return false;
863 FOR_EACH_VEC_ELT (to_remove, i, e)
865 bool ok = remove_path (e);
866 gcc_assert (ok);
869 to_remove.release ();
870 free (wont_exit);
871 free_original_copy_tables ();
875 /* Remove the conditional from the last copy of the loop. */
876 if (edge_to_cancel)
878 cond = last_stmt (edge_to_cancel->src);
879 if (edge_to_cancel->flags & EDGE_TRUE_VALUE)
880 gimple_cond_make_false (cond);
881 else
882 gimple_cond_make_true (cond);
883 update_stmt (cond);
884 /* Do not remove the path. Doing so may remove outer loop
885 and confuse bookkeeping code in tree_unroll_loops_completelly. */
888 /* Store the loop for later unlooping and exit removal. */
889 loops_to_unloop.safe_push (loop);
890 loops_to_unloop_nunroll.safe_push (n_unroll);
892 if (dump_enabled_p ())
894 if (!n_unroll)
895 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, locus,
896 "loop turned into non-loop; it never loops\n");
897 else
899 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, locus,
900 "loop with %d iterations completely unrolled",
901 (int) (n_unroll + 1));
902 if (profile_info)
903 dump_printf (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS,
904 " (header execution count %d)",
905 (int)loop->header->count);
906 dump_printf (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, "\n");
910 if (dump_file && (dump_flags & TDF_DETAILS))
912 if (exit)
913 fprintf (dump_file, "Exit condition of peeled iterations was "
914 "eliminated.\n");
915 if (edge_to_cancel)
916 fprintf (dump_file, "Last iteration exit edge was proved true.\n");
917 else
918 fprintf (dump_file, "Latch of last iteration was marked by "
919 "__builtin_unreachable ().\n");
922 return true;
925 /* Return number of instructions after peeling. */
926 static unsigned HOST_WIDE_INT
927 estimated_peeled_sequence_size (struct loop_size *size,
928 unsigned HOST_WIDE_INT npeel)
930 return MAX (npeel * (HOST_WIDE_INT) (size->overall
931 - size->eliminated_by_peeling), 1);
934 /* If the loop is expected to iterate N times and is
935 small enough, duplicate the loop body N+1 times before
936 the loop itself. This way the hot path will never
937 enter the loop.
938 Parameters are the same as for try_unroll_loops_completely */
940 static bool
941 try_peel_loop (struct loop *loop,
942 edge exit, tree niter,
943 HOST_WIDE_INT maxiter)
945 int npeel;
946 struct loop_size size;
947 int peeled_size;
948 sbitmap wont_exit;
949 unsigned i;
950 vec<edge> to_remove = vNULL;
951 edge e;
953 /* If the iteration bound is known and large, then we can safely eliminate
954 the check in peeled copies. */
955 if (TREE_CODE (niter) != INTEGER_CST)
956 exit = NULL;
958 if (!flag_peel_loops || PARAM_VALUE (PARAM_MAX_PEEL_TIMES) <= 0)
959 return false;
961 /* Peel only innermost loops. */
962 if (loop->inner)
964 if (dump_file)
965 fprintf (dump_file, "Not peeling: outer loop\n");
966 return false;
969 if (!optimize_loop_for_speed_p (loop))
971 if (dump_file)
972 fprintf (dump_file, "Not peeling: cold loop\n");
973 return false;
976 /* Check if there is an estimate on the number of iterations. */
977 npeel = estimated_loop_iterations_int (loop);
978 if (npeel < 0)
980 if (dump_file)
981 fprintf (dump_file, "Not peeling: number of iterations is not "
982 "estimated\n");
983 return false;
985 if (maxiter >= 0 && maxiter <= npeel)
987 if (dump_file)
988 fprintf (dump_file, "Not peeling: upper bound is known so can "
989 "unroll complettely\n");
990 return false;
993 /* We want to peel estimated number of iterations + 1 (so we never
994 enter the loop on quick path). Check against PARAM_MAX_PEEL_TIMES
995 and be sure to avoid overflows. */
996 if (npeel > PARAM_VALUE (PARAM_MAX_PEEL_TIMES) - 1)
998 if (dump_file)
999 fprintf (dump_file, "Not peeling: rolls too much "
1000 "(%i + 1 > --param max-peel-times)\n", npeel);
1001 return false;
1003 npeel++;
1005 /* Check peeled loops size. */
1006 tree_estimate_loop_size (loop, exit, NULL, &size,
1007 PARAM_VALUE (PARAM_MAX_PEELED_INSNS));
1008 if ((peeled_size = estimated_peeled_sequence_size (&size, npeel))
1009 > PARAM_VALUE (PARAM_MAX_PEELED_INSNS))
1011 if (dump_file)
1012 fprintf (dump_file, "Not peeling: peeled sequence size is too large "
1013 "(%i insns > --param max-peel-insns)", peeled_size);
1014 return false;
1017 /* Duplicate possibly eliminating the exits. */
1018 initialize_original_copy_tables ();
1019 wont_exit = sbitmap_alloc (npeel + 1);
1020 bitmap_ones (wont_exit);
1021 bitmap_clear_bit (wont_exit, 0);
1022 if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
1023 npeel, wont_exit,
1024 exit, &to_remove,
1025 DLTHE_FLAG_UPDATE_FREQ
1026 | DLTHE_FLAG_COMPLETTE_PEEL))
1028 free_original_copy_tables ();
1029 free (wont_exit);
1030 return false;
1032 FOR_EACH_VEC_ELT (to_remove, i, e)
1034 bool ok = remove_path (e);
1035 gcc_assert (ok);
1037 free (wont_exit);
1038 free_original_copy_tables ();
1039 if (dump_file && (dump_flags & TDF_DETAILS))
1041 fprintf (dump_file, "Peeled loop %d, %i times.\n",
1042 loop->num, npeel);
1044 if (loop->any_upper_bound)
1045 loop->nb_iterations_upper_bound -= npeel;
1046 loop->nb_iterations_estimate = 0;
1047 /* Make sure to mark loop cold so we do not try to peel it more. */
1048 scale_loop_profile (loop, 1, 0);
1049 loop->header->count = 0;
1050 return true;
1052 /* Adds a canonical induction variable to LOOP if suitable.
1053 CREATE_IV is true if we may create a new iv. UL determines
1054 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
1055 to determine the number of iterations of a loop by direct evaluation.
1056 Returns true if cfg is changed. */
1058 static bool
1059 canonicalize_loop_induction_variables (struct loop *loop,
1060 bool create_iv, enum unroll_level ul,
1061 bool try_eval)
1063 edge exit = NULL;
1064 tree niter;
1065 HOST_WIDE_INT maxiter;
1066 bool modified = false;
1067 location_t locus = UNKNOWN_LOCATION;
1069 niter = number_of_latch_executions (loop);
1070 exit = single_exit (loop);
1071 if (TREE_CODE (niter) == INTEGER_CST)
1072 locus = gimple_location (last_stmt (exit->src));
1073 else
1075 /* If the loop has more than one exit, try checking all of them
1076 for # of iterations determinable through scev. */
1077 if (!exit)
1078 niter = find_loop_niter (loop, &exit);
1080 /* Finally if everything else fails, try brute force evaluation. */
1081 if (try_eval
1082 && (chrec_contains_undetermined (niter)
1083 || TREE_CODE (niter) != INTEGER_CST))
1084 niter = find_loop_niter_by_eval (loop, &exit);
1086 if (exit)
1087 locus = gimple_location (last_stmt (exit->src));
1089 if (TREE_CODE (niter) != INTEGER_CST)
1090 exit = NULL;
1093 /* We work exceptionally hard here to estimate the bound
1094 by find_loop_niter_by_eval. Be sure to keep it for future. */
1095 if (niter && TREE_CODE (niter) == INTEGER_CST)
1097 record_niter_bound (loop, wi::to_widest (niter),
1098 exit == single_likely_exit (loop), true);
1101 /* Force re-computation of loop bounds so we can remove redundant exits. */
1102 maxiter = max_loop_iterations_int (loop);
1104 if (dump_file && (dump_flags & TDF_DETAILS)
1105 && TREE_CODE (niter) == INTEGER_CST)
1107 fprintf (dump_file, "Loop %d iterates ", loop->num);
1108 print_generic_expr (dump_file, niter, TDF_SLIM);
1109 fprintf (dump_file, " times.\n");
1111 if (dump_file && (dump_flags & TDF_DETAILS)
1112 && maxiter >= 0)
1114 fprintf (dump_file, "Loop %d iterates at most %i times.\n", loop->num,
1115 (int)maxiter);
1118 /* Remove exits that are known to be never taken based on loop bound.
1119 Needs to be called after compilation of max_loop_iterations_int that
1120 populates the loop bounds. */
1121 modified |= remove_redundant_iv_tests (loop);
1123 if (try_unroll_loop_completely (loop, exit, niter, ul, maxiter, locus))
1124 return true;
1126 if (create_iv
1127 && niter && !chrec_contains_undetermined (niter)
1128 && exit && just_once_each_iteration_p (loop, exit->src))
1129 create_canonical_iv (loop, exit, niter);
1131 if (ul == UL_ALL)
1132 modified |= try_peel_loop (loop, exit, niter, maxiter);
1134 return modified;
1137 /* The main entry point of the pass. Adds canonical induction variables
1138 to the suitable loops. */
1140 unsigned int
1141 canonicalize_induction_variables (void)
1143 struct loop *loop;
1144 bool changed = false;
1145 bool irred_invalidated = false;
1146 bitmap loop_closed_ssa_invalidated = BITMAP_ALLOC (NULL);
1148 free_numbers_of_iterations_estimates ();
1149 estimate_numbers_of_iterations ();
1151 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1153 changed |= canonicalize_loop_induction_variables (loop,
1154 true, UL_SINGLE_ITER,
1155 true);
1157 gcc_assert (!need_ssa_update_p (cfun));
1159 unloop_loops (loop_closed_ssa_invalidated, &irred_invalidated);
1160 if (irred_invalidated
1161 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1162 mark_irreducible_loops ();
1164 /* Clean up the information about numbers of iterations, since brute force
1165 evaluation could reveal new information. */
1166 scev_reset ();
1168 if (!bitmap_empty_p (loop_closed_ssa_invalidated))
1170 gcc_checking_assert (loops_state_satisfies_p (LOOP_CLOSED_SSA));
1171 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1173 BITMAP_FREE (loop_closed_ssa_invalidated);
1175 if (changed)
1176 return TODO_cleanup_cfg;
1177 return 0;
1180 /* Propagate VAL into all uses of SSA_NAME. */
1182 static void
1183 propagate_into_all_uses (tree ssa_name, tree val)
1185 imm_use_iterator iter;
1186 gimple use_stmt;
1188 FOR_EACH_IMM_USE_STMT (use_stmt, iter, ssa_name)
1190 gimple_stmt_iterator use_stmt_gsi = gsi_for_stmt (use_stmt);
1191 use_operand_p use;
1193 FOR_EACH_IMM_USE_ON_STMT (use, iter)
1194 SET_USE (use, val);
1196 if (is_gimple_assign (use_stmt)
1197 && get_gimple_rhs_class (gimple_assign_rhs_code (use_stmt))
1198 == GIMPLE_SINGLE_RHS)
1200 tree rhs = gimple_assign_rhs1 (use_stmt);
1202 if (TREE_CODE (rhs) == ADDR_EXPR)
1203 recompute_tree_invariant_for_addr_expr (rhs);
1206 fold_stmt_inplace (&use_stmt_gsi);
1207 update_stmt (use_stmt);
1208 maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt);
1212 /* Propagate constant SSA_NAMEs defined in basic block BB. */
1214 static void
1215 propagate_constants_for_unrolling (basic_block bb)
1217 gimple_stmt_iterator gsi;
1219 /* Look for degenerate PHI nodes with constant argument. */
1220 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
1222 gimple phi = gsi_stmt (gsi);
1223 tree result = gimple_phi_result (phi);
1224 tree arg = gimple_phi_arg_def (phi, 0);
1226 if (gimple_phi_num_args (phi) == 1 && TREE_CODE (arg) == INTEGER_CST)
1228 propagate_into_all_uses (result, arg);
1229 gsi_remove (&gsi, true);
1230 release_ssa_name (result);
1232 else
1233 gsi_next (&gsi);
1236 /* Look for assignments to SSA names with constant RHS. */
1237 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
1239 gimple stmt = gsi_stmt (gsi);
1240 tree lhs;
1242 if (is_gimple_assign (stmt)
1243 && gimple_assign_rhs_code (stmt) == INTEGER_CST
1244 && (lhs = gimple_assign_lhs (stmt), TREE_CODE (lhs) == SSA_NAME)
1245 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1247 propagate_into_all_uses (lhs, gimple_assign_rhs1 (stmt));
1248 gsi_remove (&gsi, true);
1249 release_ssa_name (lhs);
1251 else
1252 gsi_next (&gsi);
1256 /* Process loops from innermost to outer, stopping at the innermost
1257 loop we unrolled. */
1259 static bool
1260 tree_unroll_loops_completely_1 (bool may_increase_size, bool unroll_outer,
1261 vec<loop_p, va_heap>& father_stack,
1262 struct loop *loop)
1264 struct loop *loop_father;
1265 bool changed = false;
1266 struct loop *inner;
1267 enum unroll_level ul;
1269 /* Process inner loops first. */
1270 for (inner = loop->inner; inner != NULL; inner = inner->next)
1271 changed |= tree_unroll_loops_completely_1 (may_increase_size,
1272 unroll_outer, father_stack,
1273 inner);
1275 /* If we changed an inner loop we cannot process outer loops in this
1276 iteration because SSA form is not up-to-date. Continue with
1277 siblings of outer loops instead. */
1278 if (changed)
1279 return true;
1281 /* Don't unroll #pragma omp simd loops until the vectorizer
1282 attempts to vectorize those. */
1283 if (loop->force_vectorize)
1284 return false;
1286 /* Try to unroll this loop. */
1287 loop_father = loop_outer (loop);
1288 if (!loop_father)
1289 return false;
1291 if (may_increase_size && optimize_loop_nest_for_speed_p (loop)
1292 /* Unroll outermost loops only if asked to do so or they do
1293 not cause code growth. */
1294 && (unroll_outer || loop_outer (loop_father)))
1295 ul = UL_ALL;
1296 else
1297 ul = UL_NO_GROWTH;
1299 if (canonicalize_loop_induction_variables
1300 (loop, false, ul, !flag_tree_loop_ivcanon))
1302 /* If we'll continue unrolling, we need to propagate constants
1303 within the new basic blocks to fold away induction variable
1304 computations; otherwise, the size might blow up before the
1305 iteration is complete and the IR eventually cleaned up. */
1306 if (loop_outer (loop_father) && !loop_father->aux)
1308 father_stack.safe_push (loop_father);
1309 loop_father->aux = loop_father;
1312 return true;
1315 return false;
1318 /* Unroll LOOPS completely if they iterate just few times. Unless
1319 MAY_INCREASE_SIZE is true, perform the unrolling only if the
1320 size of the code does not increase. */
1322 unsigned int
1323 tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)
1325 auto_vec<loop_p, 16> father_stack;
1326 bool changed;
1327 int iteration = 0;
1328 bool irred_invalidated = false;
1332 changed = false;
1333 bitmap loop_closed_ssa_invalidated = NULL;
1335 if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
1336 loop_closed_ssa_invalidated = BITMAP_ALLOC (NULL);
1338 free_numbers_of_iterations_estimates ();
1339 estimate_numbers_of_iterations ();
1341 changed = tree_unroll_loops_completely_1 (may_increase_size,
1342 unroll_outer, father_stack,
1343 current_loops->tree_root);
1344 if (changed)
1346 struct loop **iter;
1347 unsigned i;
1349 /* Be sure to skip unlooped loops while procesing father_stack
1350 array. */
1351 FOR_EACH_VEC_ELT (loops_to_unloop, i, iter)
1352 (*iter)->aux = NULL;
1353 FOR_EACH_VEC_ELT (father_stack, i, iter)
1354 if (!(*iter)->aux)
1355 *iter = NULL;
1356 unloop_loops (loop_closed_ssa_invalidated, &irred_invalidated);
1358 /* We can not use TODO_update_ssa_no_phi because VOPS gets confused. */
1359 if (loop_closed_ssa_invalidated
1360 && !bitmap_empty_p (loop_closed_ssa_invalidated))
1361 rewrite_into_loop_closed_ssa (loop_closed_ssa_invalidated,
1362 TODO_update_ssa);
1363 else
1364 update_ssa (TODO_update_ssa);
1366 /* Propagate the constants within the new basic blocks. */
1367 FOR_EACH_VEC_ELT (father_stack, i, iter)
1368 if (*iter)
1370 unsigned j;
1371 basic_block *body = get_loop_body_in_dom_order (*iter);
1372 for (j = 0; j < (*iter)->num_nodes; j++)
1373 propagate_constants_for_unrolling (body[j]);
1374 free (body);
1375 (*iter)->aux = NULL;
1377 father_stack.truncate (0);
1379 /* This will take care of removing completely unrolled loops
1380 from the loop structures so we can continue unrolling now
1381 innermost loops. */
1382 if (cleanup_tree_cfg ())
1383 update_ssa (TODO_update_ssa_only_virtuals);
1385 /* Clean up the information about numbers of iterations, since
1386 complete unrolling might have invalidated it. */
1387 scev_reset ();
1388 #ifdef ENABLE_CHECKING
1389 if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
1390 verify_loop_closed_ssa (true);
1391 #endif
1393 if (loop_closed_ssa_invalidated)
1394 BITMAP_FREE (loop_closed_ssa_invalidated);
1396 while (changed
1397 && ++iteration <= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS));
1399 father_stack.release ();
1401 if (irred_invalidated
1402 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1403 mark_irreducible_loops ();
1405 return 0;
1408 /* Canonical induction variable creation pass. */
1410 namespace {
1412 const pass_data pass_data_iv_canon =
1414 GIMPLE_PASS, /* type */
1415 "ivcanon", /* name */
1416 OPTGROUP_LOOP, /* optinfo_flags */
1417 TV_TREE_LOOP_IVCANON, /* tv_id */
1418 ( PROP_cfg | PROP_ssa ), /* properties_required */
1419 0, /* properties_provided */
1420 0, /* properties_destroyed */
1421 0, /* todo_flags_start */
1422 0, /* todo_flags_finish */
1425 class pass_iv_canon : public gimple_opt_pass
1427 public:
1428 pass_iv_canon (gcc::context *ctxt)
1429 : gimple_opt_pass (pass_data_iv_canon, ctxt)
1432 /* opt_pass methods: */
1433 virtual bool gate (function *) { return flag_tree_loop_ivcanon != 0; }
1434 virtual unsigned int execute (function *fun);
1436 }; // class pass_iv_canon
1438 unsigned int
1439 pass_iv_canon::execute (function *fun)
1441 if (number_of_loops (fun) <= 1)
1442 return 0;
1444 return canonicalize_induction_variables ();
1447 } // anon namespace
1449 gimple_opt_pass *
1450 make_pass_iv_canon (gcc::context *ctxt)
1452 return new pass_iv_canon (ctxt);
1455 /* Complete unrolling of loops. */
1457 namespace {
1459 const pass_data pass_data_complete_unroll =
1461 GIMPLE_PASS, /* type */
1462 "cunroll", /* name */
1463 OPTGROUP_LOOP, /* optinfo_flags */
1464 TV_COMPLETE_UNROLL, /* tv_id */
1465 ( PROP_cfg | PROP_ssa ), /* properties_required */
1466 0, /* properties_provided */
1467 0, /* properties_destroyed */
1468 0, /* todo_flags_start */
1469 0, /* todo_flags_finish */
1472 class pass_complete_unroll : public gimple_opt_pass
1474 public:
1475 pass_complete_unroll (gcc::context *ctxt)
1476 : gimple_opt_pass (pass_data_complete_unroll, ctxt)
1479 /* opt_pass methods: */
1480 virtual unsigned int execute (function *);
1482 }; // class pass_complete_unroll
1484 unsigned int
1485 pass_complete_unroll::execute (function *fun)
1487 if (number_of_loops (fun) <= 1)
1488 return 0;
1490 return tree_unroll_loops_completely (flag_unroll_loops
1491 || flag_peel_loops
1492 || optimize >= 3, true);
1495 } // anon namespace
1497 gimple_opt_pass *
1498 make_pass_complete_unroll (gcc::context *ctxt)
1500 return new pass_complete_unroll (ctxt);
1503 /* Complete unrolling of inner loops. */
1505 namespace {
1507 const pass_data pass_data_complete_unrolli =
1509 GIMPLE_PASS, /* type */
1510 "cunrolli", /* name */
1511 OPTGROUP_LOOP, /* optinfo_flags */
1512 TV_COMPLETE_UNROLL, /* tv_id */
1513 ( PROP_cfg | PROP_ssa ), /* properties_required */
1514 0, /* properties_provided */
1515 0, /* properties_destroyed */
1516 0, /* todo_flags_start */
1517 0, /* todo_flags_finish */
1520 class pass_complete_unrolli : public gimple_opt_pass
1522 public:
1523 pass_complete_unrolli (gcc::context *ctxt)
1524 : gimple_opt_pass (pass_data_complete_unrolli, ctxt)
1527 /* opt_pass methods: */
1528 virtual bool gate (function *) { return optimize >= 2; }
1529 virtual unsigned int execute (function *);
1531 }; // class pass_complete_unrolli
1533 unsigned int
1534 pass_complete_unrolli::execute (function *fun)
1536 unsigned ret = 0;
1538 loop_optimizer_init (LOOPS_NORMAL
1539 | LOOPS_HAVE_RECORDED_EXITS);
1540 if (number_of_loops (fun) > 1)
1542 scev_initialize ();
1543 ret = tree_unroll_loops_completely (optimize >= 3, false);
1544 free_numbers_of_iterations_estimates ();
1545 scev_finalize ();
1547 loop_optimizer_finalize ();
1549 return ret;
1552 } // anon namespace
1554 gimple_opt_pass *
1555 make_pass_complete_unrolli (gcc::context *ctxt)
1557 return new pass_complete_unrolli (ctxt);