Daily bump.
[official-gcc.git] / gcc / tree-ssa-loop-ivcanon.c
blob24bf60eaa49291c57d5271babdabbc1d62e89c9d
1 /* Induction variable canonicalization and loop peeling.
2 Copyright (C) 2004-2018 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 - complete 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 "backend.h"
42 #include "tree.h"
43 #include "gimple.h"
44 #include "cfghooks.h"
45 #include "tree-pass.h"
46 #include "ssa.h"
47 #include "cgraph.h"
48 #include "gimple-pretty-print.h"
49 #include "fold-const.h"
50 #include "profile.h"
51 #include "gimple-fold.h"
52 #include "tree-eh.h"
53 #include "gimple-iterator.h"
54 #include "tree-cfg.h"
55 #include "tree-ssa-loop-manip.h"
56 #include "tree-ssa-loop-niter.h"
57 #include "tree-ssa-loop.h"
58 #include "tree-into-ssa.h"
59 #include "cfgloop.h"
60 #include "tree-chrec.h"
61 #include "tree-scalar-evolution.h"
62 #include "params.h"
63 #include "tree-inline.h"
64 #include "tree-cfgcleanup.h"
65 #include "builtins.h"
67 /* Specifies types of loops that may be unrolled. */
69 enum unroll_level
71 UL_SINGLE_ITER, /* Only loops that exit immediately in the first
72 iteration. */
73 UL_NO_GROWTH, /* Only loops whose unrolling will not cause increase
74 of code size. */
75 UL_ALL /* All suitable loops. */
78 /* Adds a canonical induction variable to LOOP iterating NITER times. EXIT
79 is the exit edge whose condition is replaced. The ssa versions of the new
80 IV before and after increment will be stored in VAR_BEFORE and VAR_AFTER
81 if they are not NULL. */
83 void
84 create_canonical_iv (struct loop *loop, edge exit, tree niter,
85 tree *var_before = NULL, tree *var_after = NULL)
87 edge in;
88 tree type, var;
89 gcond *cond;
90 gimple_stmt_iterator incr_at;
91 enum tree_code cmp;
93 if (dump_file && (dump_flags & TDF_DETAILS))
95 fprintf (dump_file, "Added canonical iv to loop %d, ", loop->num);
96 print_generic_expr (dump_file, niter, TDF_SLIM);
97 fprintf (dump_file, " iterations.\n");
100 cond = as_a <gcond *> (last_stmt (exit->src));
101 in = EDGE_SUCC (exit->src, 0);
102 if (in == exit)
103 in = EDGE_SUCC (exit->src, 1);
105 /* Note that we do not need to worry about overflows, since
106 type of niter is always unsigned and all comparisons are
107 just for equality/nonequality -- i.e. everything works
108 with a modulo arithmetics. */
110 type = TREE_TYPE (niter);
111 niter = fold_build2 (PLUS_EXPR, type,
112 niter,
113 build_int_cst (type, 1));
114 incr_at = gsi_last_bb (in->src);
115 create_iv (niter,
116 build_int_cst (type, -1),
117 NULL_TREE, loop,
118 &incr_at, false, var_before, &var);
119 if (var_after)
120 *var_after = var;
122 cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
123 gimple_cond_set_code (cond, cmp);
124 gimple_cond_set_lhs (cond, var);
125 gimple_cond_set_rhs (cond, build_int_cst (type, 0));
126 update_stmt (cond);
129 /* Describe size of loop as detected by tree_estimate_loop_size. */
130 struct loop_size
132 /* Number of instructions in the loop. */
133 int overall;
135 /* Number of instructions that will be likely optimized out in
136 peeled iterations of loop (i.e. computation based on induction
137 variable where induction variable starts at known constant.) */
138 int eliminated_by_peeling;
140 /* Same statistics for last iteration of loop: it is smaller because
141 instructions after exit are not executed. */
142 int last_iteration;
143 int last_iteration_eliminated_by_peeling;
145 /* If some IV computation will become constant. */
146 bool constant_iv;
148 /* Number of call stmts that are not a builtin and are pure or const
149 present on the hot path. */
150 int num_pure_calls_on_hot_path;
151 /* Number of call stmts that are not a builtin and are not pure nor const
152 present on the hot path. */
153 int num_non_pure_calls_on_hot_path;
154 /* Number of statements other than calls in the loop. */
155 int non_call_stmts_on_hot_path;
156 /* Number of branches seen on the hot path. */
157 int num_branches_on_hot_path;
160 /* Return true if OP in STMT will be constant after peeling LOOP. */
162 static bool
163 constant_after_peeling (tree op, gimple *stmt, struct loop *loop)
165 if (is_gimple_min_invariant (op))
166 return true;
168 /* We can still fold accesses to constant arrays when index is known. */
169 if (TREE_CODE (op) != SSA_NAME)
171 tree base = op;
173 /* First make fast look if we see constant array inside. */
174 while (handled_component_p (base))
175 base = TREE_OPERAND (base, 0);
176 if ((DECL_P (base)
177 && ctor_for_folding (base) != error_mark_node)
178 || CONSTANT_CLASS_P (base))
180 /* If so, see if we understand all the indices. */
181 base = op;
182 while (handled_component_p (base))
184 if (TREE_CODE (base) == ARRAY_REF
185 && !constant_after_peeling (TREE_OPERAND (base, 1), stmt, loop))
186 return false;
187 base = TREE_OPERAND (base, 0);
189 return true;
191 return false;
194 /* Induction variables are constants when defined in loop. */
195 if (loop_containing_stmt (stmt) != loop)
196 return false;
197 tree ev = analyze_scalar_evolution (loop, op);
198 if (chrec_contains_undetermined (ev)
199 || chrec_contains_symbols (ev))
200 return false;
201 return true;
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
208 of loop.
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. */
212 static bool
213 tree_estimate_loop_size (struct loop *loop, edge exit, edge edge_to_cancel,
214 struct loop_size *size, int upper_bound)
216 basic_block *body = get_loop_body (loop);
217 gimple_stmt_iterator gsi;
218 unsigned int i;
219 bool after_exit;
220 vec<basic_block> path = get_loop_hot_path (loop);
222 size->overall = 0;
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))
238 after_exit = true;
239 else
240 after_exit = false;
241 if (dump_file && (dump_flags & TDF_DETAILS))
242 fprintf (dump_file, " BB: %i, after_exit: %i\n", body[i]->index,
243 after_exit);
245 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
247 gimple *stmt = gsi_stmt (gsi);
248 int num = estimate_num_insns (stmt, &eni_size_weights);
249 bool likely_eliminated = false;
250 bool likely_eliminated_last = false;
251 bool likely_eliminated_peeled = false;
253 if (dump_file && (dump_flags & TDF_DETAILS))
255 fprintf (dump_file, " size: %3i ", num);
256 print_gimple_stmt (dump_file, gsi_stmt (gsi), 0);
259 /* Look for reasons why we might optimize this stmt away. */
261 if (!gimple_has_side_effects (stmt))
263 /* Exit conditional. */
264 if (exit && body[i] == exit->src
265 && stmt == last_stmt (exit->src))
267 if (dump_file && (dump_flags & TDF_DETAILS))
268 fprintf (dump_file, " Exit condition will be eliminated "
269 "in peeled copies.\n");
270 likely_eliminated_peeled = true;
272 if (edge_to_cancel && body[i] == edge_to_cancel->src
273 && stmt == last_stmt (edge_to_cancel->src))
275 if (dump_file && (dump_flags & TDF_DETAILS))
276 fprintf (dump_file, " Exit condition will be eliminated "
277 "in last copy.\n");
278 likely_eliminated_last = true;
280 /* Sets of IV variables */
281 if (gimple_code (stmt) == GIMPLE_ASSIGN
282 && constant_after_peeling (gimple_assign_lhs (stmt), stmt, loop))
284 if (dump_file && (dump_flags & TDF_DETAILS))
285 fprintf (dump_file, " Induction variable computation will"
286 " be folded away.\n");
287 likely_eliminated = true;
289 /* Assignments of IV variables. */
290 else if (gimple_code (stmt) == GIMPLE_ASSIGN
291 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
292 && constant_after_peeling (gimple_assign_rhs1 (stmt),
293 stmt, loop)
294 && (gimple_assign_rhs_class (stmt) != GIMPLE_BINARY_RHS
295 || constant_after_peeling (gimple_assign_rhs2 (stmt),
296 stmt, loop)))
298 size->constant_iv = true;
299 if (dump_file && (dump_flags & TDF_DETAILS))
300 fprintf (dump_file,
301 " Constant expression will be folded away.\n");
302 likely_eliminated = true;
304 /* Conditionals. */
305 else if ((gimple_code (stmt) == GIMPLE_COND
306 && constant_after_peeling (gimple_cond_lhs (stmt), stmt,
307 loop)
308 && constant_after_peeling (gimple_cond_rhs (stmt), stmt,
309 loop)
310 /* We don't simplify all constant compares so make sure
311 they are not both constant already. See PR70288. */
312 && (! is_gimple_min_invariant (gimple_cond_lhs (stmt))
313 || ! is_gimple_min_invariant
314 (gimple_cond_rhs (stmt))))
315 || (gimple_code (stmt) == GIMPLE_SWITCH
316 && constant_after_peeling (gimple_switch_index (
317 as_a <gswitch *>
318 (stmt)),
319 stmt, loop)
320 && ! is_gimple_min_invariant
321 (gimple_switch_index
322 (as_a <gswitch *> (stmt)))))
324 if (dump_file && (dump_flags & TDF_DETAILS))
325 fprintf (dump_file, " Constant conditional.\n");
326 likely_eliminated = true;
330 size->overall += num;
331 if (likely_eliminated || likely_eliminated_peeled)
332 size->eliminated_by_peeling += num;
333 if (!after_exit)
335 size->last_iteration += num;
336 if (likely_eliminated || likely_eliminated_last)
337 size->last_iteration_eliminated_by_peeling += num;
339 if ((size->overall * 3 / 2 - size->eliminated_by_peeling
340 - size->last_iteration_eliminated_by_peeling) > upper_bound)
342 free (body);
343 path.release ();
344 return true;
348 while (path.length ())
350 basic_block bb = path.pop ();
351 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
353 gimple *stmt = gsi_stmt (gsi);
354 if (gimple_code (stmt) == GIMPLE_CALL
355 && !gimple_inexpensive_call_p (as_a <gcall *> (stmt)))
357 int flags = gimple_call_flags (stmt);
358 if (flags & (ECF_PURE | ECF_CONST))
359 size->num_pure_calls_on_hot_path++;
360 else
361 size->num_non_pure_calls_on_hot_path++;
362 size->num_branches_on_hot_path ++;
364 /* Count inexpensive calls as non-calls, because they will likely
365 expand inline. */
366 else if (gimple_code (stmt) != GIMPLE_DEBUG)
367 size->non_call_stmts_on_hot_path++;
368 if (((gimple_code (stmt) == GIMPLE_COND
369 && (!constant_after_peeling (gimple_cond_lhs (stmt), stmt, loop)
370 || constant_after_peeling (gimple_cond_rhs (stmt), stmt,
371 loop)))
372 || (gimple_code (stmt) == GIMPLE_SWITCH
373 && !constant_after_peeling (gimple_switch_index (
374 as_a <gswitch *> (stmt)),
375 stmt, loop)))
376 && (!exit || bb != exit->src))
377 size->num_branches_on_hot_path++;
380 path.release ();
381 if (dump_file && (dump_flags & TDF_DETAILS))
382 fprintf (dump_file, "size: %i-%i, last_iteration: %i-%i\n", size->overall,
383 size->eliminated_by_peeling, size->last_iteration,
384 size->last_iteration_eliminated_by_peeling);
386 free (body);
387 return false;
390 /* Estimate number of insns of completely unrolled loop.
391 It is (NUNROLL + 1) * size of loop body with taking into account
392 the fact that in last copy everything after exit conditional
393 is dead and that some instructions will be eliminated after
394 peeling.
396 Loop body is likely going to simplify further, this is difficult
397 to guess, we just decrease the result by 1/3. */
399 static unsigned HOST_WIDE_INT
400 estimated_unrolled_size (struct loop_size *size,
401 unsigned HOST_WIDE_INT nunroll)
403 HOST_WIDE_INT unr_insns = ((nunroll)
404 * (HOST_WIDE_INT) (size->overall
405 - size->eliminated_by_peeling));
406 if (!nunroll)
407 unr_insns = 0;
408 unr_insns += size->last_iteration - size->last_iteration_eliminated_by_peeling;
410 unr_insns = unr_insns * 2 / 3;
411 if (unr_insns <= 0)
412 unr_insns = 1;
414 return unr_insns;
417 /* Loop LOOP is known to not loop. See if there is an edge in the loop
418 body that can be remove to make the loop to always exit and at
419 the same time it does not make any code potentially executed
420 during the last iteration dead.
422 After complete unrolling we still may get rid of the conditional
423 on the exit in the last copy even if we have no idea what it does.
424 This is quite common case for loops of form
426 int a[5];
427 for (i=0;i<b;i++)
428 a[i]=0;
430 Here we prove the loop to iterate 5 times but we do not know
431 it from induction variable.
433 For now we handle only simple case where there is exit condition
434 just before the latch block and the latch block contains no statements
435 with side effect that may otherwise terminate the execution of loop
436 (such as by EH or by terminating the program or longjmp).
438 In the general case we may want to cancel the paths leading to statements
439 loop-niter identified as having undefined effect in the last iteration.
440 The other cases are hopefully rare and will be cleaned up later. */
442 static edge
443 loop_edge_to_cancel (struct loop *loop)
445 vec<edge> exits;
446 unsigned i;
447 edge edge_to_cancel;
448 gimple_stmt_iterator gsi;
450 /* We want only one predecestor of the loop. */
451 if (EDGE_COUNT (loop->latch->preds) > 1)
452 return NULL;
454 exits = get_loop_exit_edges (loop);
456 FOR_EACH_VEC_ELT (exits, i, edge_to_cancel)
458 /* Find the other edge than the loop exit
459 leaving the conditoinal. */
460 if (EDGE_COUNT (edge_to_cancel->src->succs) != 2)
461 continue;
462 if (EDGE_SUCC (edge_to_cancel->src, 0) == edge_to_cancel)
463 edge_to_cancel = EDGE_SUCC (edge_to_cancel->src, 1);
464 else
465 edge_to_cancel = EDGE_SUCC (edge_to_cancel->src, 0);
467 /* We only can handle conditionals. */
468 if (!(edge_to_cancel->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
469 continue;
471 /* We should never have conditionals in the loop latch. */
472 gcc_assert (edge_to_cancel->dest != loop->header);
474 /* Check that it leads to loop latch. */
475 if (edge_to_cancel->dest != loop->latch)
476 continue;
478 exits.release ();
480 /* Verify that the code in loop latch does nothing that may end program
481 execution without really reaching the exit. This may include
482 non-pure/const function calls, EH statements, volatile ASMs etc. */
483 for (gsi = gsi_start_bb (loop->latch); !gsi_end_p (gsi); gsi_next (&gsi))
484 if (gimple_has_side_effects (gsi_stmt (gsi)))
485 return NULL;
486 return edge_to_cancel;
488 exits.release ();
489 return NULL;
492 /* Remove all tests for exits that are known to be taken after LOOP was
493 peeled NPEELED times. Put gcc_unreachable before every statement
494 known to not be executed. */
496 static bool
497 remove_exits_and_undefined_stmts (struct loop *loop, unsigned int npeeled)
499 struct nb_iter_bound *elt;
500 bool changed = false;
502 for (elt = loop->bounds; elt; elt = elt->next)
504 /* If statement is known to be undefined after peeling, turn it
505 into unreachable (or trap when debugging experience is supposed
506 to be good). */
507 if (!elt->is_exit
508 && wi::ltu_p (elt->bound, npeeled))
510 gimple_stmt_iterator gsi = gsi_for_stmt (elt->stmt);
511 gcall *stmt = gimple_build_call
512 (builtin_decl_implicit (BUILT_IN_UNREACHABLE), 0);
513 gimple_set_location (stmt, gimple_location (elt->stmt));
514 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
515 split_block (gimple_bb (stmt), stmt);
516 changed = true;
517 if (dump_file && (dump_flags & TDF_DETAILS))
519 fprintf (dump_file, "Forced statement unreachable: ");
520 print_gimple_stmt (dump_file, elt->stmt, 0);
523 /* If we know the exit will be taken after peeling, update. */
524 else if (elt->is_exit
525 && wi::leu_p (elt->bound, npeeled))
527 basic_block bb = gimple_bb (elt->stmt);
528 edge exit_edge = EDGE_SUCC (bb, 0);
530 if (dump_file && (dump_flags & TDF_DETAILS))
532 fprintf (dump_file, "Forced exit to be taken: ");
533 print_gimple_stmt (dump_file, elt->stmt, 0);
535 if (!loop_exit_edge_p (loop, exit_edge))
536 exit_edge = EDGE_SUCC (bb, 1);
537 exit_edge->probability = profile_probability::always ();
538 gcc_checking_assert (loop_exit_edge_p (loop, exit_edge));
539 gcond *cond_stmt = as_a <gcond *> (elt->stmt);
540 if (exit_edge->flags & EDGE_TRUE_VALUE)
541 gimple_cond_make_true (cond_stmt);
542 else
543 gimple_cond_make_false (cond_stmt);
544 update_stmt (cond_stmt);
545 changed = true;
548 return changed;
551 /* Remove all exits that are known to be never taken because of the loop bound
552 discovered. */
554 static bool
555 remove_redundant_iv_tests (struct loop *loop)
557 struct nb_iter_bound *elt;
558 bool changed = false;
560 if (!loop->any_upper_bound)
561 return false;
562 for (elt = loop->bounds; elt; elt = elt->next)
564 /* Exit is pointless if it won't be taken before loop reaches
565 upper bound. */
566 if (elt->is_exit && loop->any_upper_bound
567 && wi::ltu_p (loop->nb_iterations_upper_bound, elt->bound))
569 basic_block bb = gimple_bb (elt->stmt);
570 edge exit_edge = EDGE_SUCC (bb, 0);
571 struct tree_niter_desc niter;
573 if (!loop_exit_edge_p (loop, exit_edge))
574 exit_edge = EDGE_SUCC (bb, 1);
576 /* Only when we know the actual number of iterations, not
577 just a bound, we can remove the exit. */
578 if (!number_of_iterations_exit (loop, exit_edge,
579 &niter, false, false)
580 || !integer_onep (niter.assumptions)
581 || !integer_zerop (niter.may_be_zero)
582 || !niter.niter
583 || TREE_CODE (niter.niter) != INTEGER_CST
584 || !wi::ltu_p (loop->nb_iterations_upper_bound,
585 wi::to_widest (niter.niter)))
586 continue;
588 if (dump_file && (dump_flags & TDF_DETAILS))
590 fprintf (dump_file, "Removed pointless exit: ");
591 print_gimple_stmt (dump_file, elt->stmt, 0);
593 gcond *cond_stmt = as_a <gcond *> (elt->stmt);
594 if (exit_edge->flags & EDGE_TRUE_VALUE)
595 gimple_cond_make_false (cond_stmt);
596 else
597 gimple_cond_make_true (cond_stmt);
598 update_stmt (cond_stmt);
599 changed = true;
602 return changed;
605 /* Stores loops that will be unlooped and edges that will be removed
606 after we process whole loop tree. */
607 static vec<loop_p> loops_to_unloop;
608 static vec<int> loops_to_unloop_nunroll;
609 static vec<edge> edges_to_remove;
610 /* Stores loops that has been peeled. */
611 static bitmap peeled_loops;
613 /* Cancel all fully unrolled loops by putting __builtin_unreachable
614 on the latch edge.
615 We do it after all unrolling since unlooping moves basic blocks
616 across loop boundaries trashing loop closed SSA form as well
617 as SCEV info needed to be intact during unrolling.
619 IRRED_INVALIDATED is used to bookkeep if information about
620 irreducible regions may become invalid as a result
621 of the transformation.
622 LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case
623 when we need to go into loop closed SSA form. */
625 static void
626 unloop_loops (bitmap loop_closed_ssa_invalidated,
627 bool *irred_invalidated)
629 while (loops_to_unloop.length ())
631 struct loop *loop = loops_to_unloop.pop ();
632 int n_unroll = loops_to_unloop_nunroll.pop ();
633 basic_block latch = loop->latch;
634 edge latch_edge = loop_latch_edge (loop);
635 int flags = latch_edge->flags;
636 location_t locus = latch_edge->goto_locus;
637 gcall *stmt;
638 gimple_stmt_iterator gsi;
640 remove_exits_and_undefined_stmts (loop, n_unroll);
642 /* Unloop destroys the latch edge. */
643 unloop (loop, irred_invalidated, loop_closed_ssa_invalidated);
645 /* Create new basic block for the latch edge destination and wire
646 it in. */
647 stmt = gimple_build_call (builtin_decl_implicit (BUILT_IN_UNREACHABLE), 0);
648 latch_edge = make_edge (latch, create_basic_block (NULL, NULL, latch), flags);
649 latch_edge->probability = profile_probability::never ();
650 latch_edge->flags |= flags;
651 latch_edge->goto_locus = locus;
653 add_bb_to_loop (latch_edge->dest, current_loops->tree_root);
654 latch_edge->dest->count = profile_count::zero ();
655 set_immediate_dominator (CDI_DOMINATORS, latch_edge->dest, latch_edge->src);
657 gsi = gsi_start_bb (latch_edge->dest);
658 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
660 loops_to_unloop.release ();
661 loops_to_unloop_nunroll.release ();
663 /* Remove edges in peeled copies. Given remove_path removes dominated
664 regions we need to cope with removal of already removed paths. */
665 unsigned i;
666 edge e;
667 auto_vec<int, 20> src_bbs;
668 src_bbs.reserve_exact (edges_to_remove.length ());
669 FOR_EACH_VEC_ELT (edges_to_remove, i, e)
670 src_bbs.quick_push (e->src->index);
671 FOR_EACH_VEC_ELT (edges_to_remove, i, e)
672 if (BASIC_BLOCK_FOR_FN (cfun, src_bbs[i]))
674 bool ok = remove_path (e, irred_invalidated,
675 loop_closed_ssa_invalidated);
676 gcc_assert (ok);
678 edges_to_remove.release ();
681 /* Tries to unroll LOOP completely, i.e. NITER times.
682 UL determines which loops we are allowed to unroll.
683 EXIT is the exit of the loop that should be eliminated.
684 MAXITER specfy bound on number of iterations, -1 if it is
685 not known or too large for HOST_WIDE_INT. The location
686 LOCUS corresponding to the loop is used when emitting
687 a summary of the unroll to the dump file. */
689 static bool
690 try_unroll_loop_completely (struct loop *loop,
691 edge exit, tree niter, bool may_be_zero,
692 enum unroll_level ul,
693 HOST_WIDE_INT maxiter,
694 location_t locus, bool allow_peel)
696 unsigned HOST_WIDE_INT n_unroll = 0;
697 bool n_unroll_found = false;
698 edge edge_to_cancel = NULL;
700 /* See if we proved number of iterations to be low constant.
702 EXIT is an edge that will be removed in all but last iteration of
703 the loop.
705 EDGE_TO_CACNEL is an edge that will be removed from the last iteration
706 of the unrolled sequence and is expected to make the final loop not
707 rolling.
709 If the number of execution of loop is determined by standard induction
710 variable test, then EXIT and EDGE_TO_CANCEL are the two edges leaving
711 from the iv test. */
712 if (tree_fits_uhwi_p (niter))
714 n_unroll = tree_to_uhwi (niter);
715 n_unroll_found = true;
716 edge_to_cancel = EDGE_SUCC (exit->src, 0);
717 if (edge_to_cancel == exit)
718 edge_to_cancel = EDGE_SUCC (exit->src, 1);
720 /* We do not know the number of iterations and thus we can not eliminate
721 the EXIT edge. */
722 else
723 exit = NULL;
725 /* See if we can improve our estimate by using recorded loop bounds. */
726 if ((allow_peel || maxiter == 0 || ul == UL_NO_GROWTH)
727 && maxiter >= 0
728 && (!n_unroll_found || (unsigned HOST_WIDE_INT)maxiter < n_unroll))
730 n_unroll = maxiter;
731 n_unroll_found = true;
732 /* Loop terminates before the IV variable test, so we can not
733 remove it in the last iteration. */
734 edge_to_cancel = NULL;
737 if (!n_unroll_found)
738 return false;
740 if (!loop->unroll
741 && n_unroll > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES))
743 if (dump_file && (dump_flags & TDF_DETAILS))
744 fprintf (dump_file, "Not unrolling loop %d "
745 "(--param max-completely-peel-times limit reached).\n",
746 loop->num);
747 return false;
750 if (!edge_to_cancel)
751 edge_to_cancel = loop_edge_to_cancel (loop);
753 if (n_unroll)
755 if (ul == UL_SINGLE_ITER)
756 return false;
758 if (loop->unroll)
760 /* If the unrolling factor is too large, bail out. */
761 if (n_unroll > (unsigned)loop->unroll)
763 if (dump_file && (dump_flags & TDF_DETAILS))
764 fprintf (dump_file,
765 "Not unrolling loop %d: "
766 "user didn't want it unrolled completely.\n",
767 loop->num);
768 return false;
771 else
773 struct loop_size size;
774 /* EXIT can be removed only if we are sure it passes first N_UNROLL
775 iterations. */
776 bool remove_exit = (exit && niter
777 && TREE_CODE (niter) == INTEGER_CST
778 && wi::leu_p (n_unroll, wi::to_widest (niter)));
779 bool large
780 = tree_estimate_loop_size
781 (loop, remove_exit ? exit : NULL, edge_to_cancel, &size,
782 PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS));
783 if (large)
785 if (dump_file && (dump_flags & TDF_DETAILS))
786 fprintf (dump_file, "Not unrolling loop %d: it is too large.\n",
787 loop->num);
788 return false;
791 unsigned HOST_WIDE_INT ninsns = size.overall;
792 unsigned HOST_WIDE_INT unr_insns
793 = estimated_unrolled_size (&size, n_unroll);
794 if (dump_file && (dump_flags & TDF_DETAILS))
796 fprintf (dump_file, " Loop size: %d\n", (int) ninsns);
797 fprintf (dump_file, " Estimated size after unrolling: %d\n",
798 (int) unr_insns);
801 /* If the code is going to shrink, we don't need to be extra
802 cautious on guessing if the unrolling is going to be
803 profitable. */
804 if (unr_insns
805 /* If there is IV variable that will become constant, we
806 save one instruction in the loop prologue we do not
807 account otherwise. */
808 <= ninsns + (size.constant_iv != false))
810 /* We unroll only inner loops, because we do not consider it
811 profitable otheriwse. We still can cancel loopback edge
812 of not rolling loop; this is always a good idea. */
813 else if (ul == UL_NO_GROWTH)
815 if (dump_file && (dump_flags & TDF_DETAILS))
816 fprintf (dump_file, "Not unrolling loop %d: size would grow.\n",
817 loop->num);
818 return false;
820 /* Outer loops tend to be less interesting candidates for
821 complete unrolling unless we can do a lot of propagation
822 into the inner loop body. For now we disable outer loop
823 unrolling when the code would grow. */
824 else if (loop->inner)
826 if (dump_file && (dump_flags & TDF_DETAILS))
827 fprintf (dump_file, "Not unrolling loop %d: "
828 "it is not innermost and code would grow.\n",
829 loop->num);
830 return false;
832 /* If there is call on a hot path through the loop, then
833 there is most probably not much to optimize. */
834 else if (size.num_non_pure_calls_on_hot_path)
836 if (dump_file && (dump_flags & TDF_DETAILS))
837 fprintf (dump_file, "Not unrolling loop %d: "
838 "contains call and code would grow.\n",
839 loop->num);
840 return false;
842 /* If there is pure/const call in the function, then we can
843 still optimize the unrolled loop body if it contains some
844 other interesting code than the calls and code storing or
845 cumulating the return value. */
846 else if (size.num_pure_calls_on_hot_path
847 /* One IV increment, one test, one ivtmp store and
848 one useful stmt. That is about minimal loop
849 doing pure call. */
850 && (size.non_call_stmts_on_hot_path
851 <= 3 + size.num_pure_calls_on_hot_path))
853 if (dump_file && (dump_flags & TDF_DETAILS))
854 fprintf (dump_file, "Not unrolling loop %d: "
855 "contains just pure calls and code would grow.\n",
856 loop->num);
857 return false;
859 /* Complete unrolling is major win when control flow is
860 removed and one big basic block is created. If the loop
861 contains control flow the optimization may still be a win
862 because of eliminating the loop overhead but it also may
863 blow the branch predictor tables. Limit number of
864 branches on the hot path through the peeled sequence. */
865 else if (size.num_branches_on_hot_path * (int)n_unroll
866 > PARAM_VALUE (PARAM_MAX_PEEL_BRANCHES))
868 if (dump_file && (dump_flags & TDF_DETAILS))
869 fprintf (dump_file, "Not unrolling loop %d: "
870 "number of branches on hot path in the unrolled "
871 "sequence reaches --param max-peel-branches limit.\n",
872 loop->num);
873 return false;
875 else if (unr_insns
876 > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
878 if (dump_file && (dump_flags & TDF_DETAILS))
879 fprintf (dump_file, "Not unrolling loop %d: "
880 "number of insns in the unrolled sequence reaches "
881 "--param max-completely-peeled-insns limit.\n",
882 loop->num);
883 return false;
887 initialize_original_copy_tables ();
888 auto_sbitmap wont_exit (n_unroll + 1);
889 if (exit && niter
890 && TREE_CODE (niter) == INTEGER_CST
891 && wi::leu_p (n_unroll, wi::to_widest (niter)))
893 bitmap_ones (wont_exit);
894 if (wi::eq_p (wi::to_widest (niter), n_unroll)
895 || edge_to_cancel)
896 bitmap_clear_bit (wont_exit, 0);
898 else
900 exit = NULL;
901 bitmap_clear (wont_exit);
903 if (may_be_zero)
904 bitmap_clear_bit (wont_exit, 1);
906 if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
907 n_unroll, wont_exit,
908 exit, &edges_to_remove,
909 DLTHE_FLAG_UPDATE_FREQ
910 | DLTHE_FLAG_COMPLETTE_PEEL))
912 free_original_copy_tables ();
913 if (dump_file && (dump_flags & TDF_DETAILS))
914 fprintf (dump_file, "Failed to duplicate the loop\n");
915 return false;
918 free_original_copy_tables ();
921 /* Remove the conditional from the last copy of the loop. */
922 if (edge_to_cancel)
924 gcond *cond = as_a <gcond *> (last_stmt (edge_to_cancel->src));
925 force_edge_cold (edge_to_cancel, true);
926 if (edge_to_cancel->flags & EDGE_TRUE_VALUE)
927 gimple_cond_make_false (cond);
928 else
929 gimple_cond_make_true (cond);
930 update_stmt (cond);
931 /* Do not remove the path, as doing so may remove outer loop and
932 confuse bookkeeping code in tree_unroll_loops_completely. */
935 /* Store the loop for later unlooping and exit removal. */
936 loops_to_unloop.safe_push (loop);
937 loops_to_unloop_nunroll.safe_push (n_unroll);
939 if (dump_enabled_p ())
941 if (!n_unroll)
942 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, locus,
943 "loop turned into non-loop; it never loops\n");
944 else
946 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, locus,
947 "loop with %d iterations completely unrolled",
948 (int) n_unroll);
949 if (loop->header->count.initialized_p ())
950 dump_printf (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS,
951 " (header execution count %d)",
952 (int)loop->header->count.to_gcov_type ());
953 dump_printf (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, "\n");
957 if (dump_file && (dump_flags & TDF_DETAILS))
959 if (exit)
960 fprintf (dump_file, "Exit condition of peeled iterations was "
961 "eliminated.\n");
962 if (edge_to_cancel)
963 fprintf (dump_file, "Last iteration exit edge was proved true.\n");
964 else
965 fprintf (dump_file, "Latch of last iteration was marked by "
966 "__builtin_unreachable ().\n");
969 return true;
972 /* Return number of instructions after peeling. */
973 static unsigned HOST_WIDE_INT
974 estimated_peeled_sequence_size (struct loop_size *size,
975 unsigned HOST_WIDE_INT npeel)
977 return MAX (npeel * (HOST_WIDE_INT) (size->overall
978 - size->eliminated_by_peeling), 1);
981 /* If the loop is expected to iterate N times and is
982 small enough, duplicate the loop body N+1 times before
983 the loop itself. This way the hot path will never
984 enter the loop.
985 Parameters are the same as for try_unroll_loops_completely */
987 static bool
988 try_peel_loop (struct loop *loop,
989 edge exit, tree niter, bool may_be_zero,
990 HOST_WIDE_INT maxiter)
992 HOST_WIDE_INT npeel;
993 struct loop_size size;
994 int peeled_size;
996 if (!flag_peel_loops
997 || PARAM_VALUE (PARAM_MAX_PEEL_TIMES) <= 0
998 || !peeled_loops)
999 return false;
1001 if (bitmap_bit_p (peeled_loops, loop->num))
1003 if (dump_file)
1004 fprintf (dump_file, "Not peeling: loop is already peeled\n");
1005 return false;
1008 /* We don't peel loops that will be unrolled as this can duplicate a
1009 loop more times than the user requested. */
1010 if (loop->unroll)
1012 if (dump_file)
1013 fprintf (dump_file, "Not peeling: user didn't want it peeled.\n");
1014 return false;
1017 /* Peel only innermost loops.
1018 While the code is perfectly capable of peeling non-innermost loops,
1019 the heuristics would probably need some improvements. */
1020 if (loop->inner)
1022 if (dump_file)
1023 fprintf (dump_file, "Not peeling: outer loop\n");
1024 return false;
1027 if (!optimize_loop_for_speed_p (loop))
1029 if (dump_file)
1030 fprintf (dump_file, "Not peeling: cold loop\n");
1031 return false;
1034 /* Check if there is an estimate on the number of iterations. */
1035 npeel = estimated_loop_iterations_int (loop);
1036 if (npeel < 0)
1037 npeel = likely_max_loop_iterations_int (loop);
1038 if (npeel < 0)
1040 if (dump_file)
1041 fprintf (dump_file, "Not peeling: number of iterations is not "
1042 "estimated\n");
1043 return false;
1045 if (maxiter >= 0 && maxiter <= npeel)
1047 if (dump_file)
1048 fprintf (dump_file, "Not peeling: upper bound is known so can "
1049 "unroll completely\n");
1050 return false;
1053 /* We want to peel estimated number of iterations + 1 (so we never
1054 enter the loop on quick path). Check against PARAM_MAX_PEEL_TIMES
1055 and be sure to avoid overflows. */
1056 if (npeel > PARAM_VALUE (PARAM_MAX_PEEL_TIMES) - 1)
1058 if (dump_file)
1059 fprintf (dump_file, "Not peeling: rolls too much "
1060 "(%i + 1 > --param max-peel-times)\n", (int) npeel);
1061 return false;
1063 npeel++;
1065 /* Check peeled loops size. */
1066 tree_estimate_loop_size (loop, exit, NULL, &size,
1067 PARAM_VALUE (PARAM_MAX_PEELED_INSNS));
1068 if ((peeled_size = estimated_peeled_sequence_size (&size, (int) npeel))
1069 > PARAM_VALUE (PARAM_MAX_PEELED_INSNS))
1071 if (dump_file)
1072 fprintf (dump_file, "Not peeling: peeled sequence size is too large "
1073 "(%i insns > --param max-peel-insns)", peeled_size);
1074 return false;
1077 /* Duplicate possibly eliminating the exits. */
1078 initialize_original_copy_tables ();
1079 auto_sbitmap wont_exit (npeel + 1);
1080 if (exit && niter
1081 && TREE_CODE (niter) == INTEGER_CST
1082 && wi::leu_p (npeel, wi::to_widest (niter)))
1084 bitmap_ones (wont_exit);
1085 bitmap_clear_bit (wont_exit, 0);
1087 else
1089 exit = NULL;
1090 bitmap_clear (wont_exit);
1092 if (may_be_zero)
1093 bitmap_clear_bit (wont_exit, 1);
1094 if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
1095 npeel, wont_exit,
1096 exit, &edges_to_remove,
1097 DLTHE_FLAG_UPDATE_FREQ))
1099 free_original_copy_tables ();
1100 return false;
1102 free_original_copy_tables ();
1103 if (dump_file && (dump_flags & TDF_DETAILS))
1105 fprintf (dump_file, "Peeled loop %d, %i times.\n",
1106 loop->num, (int) npeel);
1108 if (loop->any_estimate)
1110 if (wi::ltu_p (npeel, loop->nb_iterations_estimate))
1111 loop->nb_iterations_estimate -= npeel;
1112 else
1113 loop->nb_iterations_estimate = 0;
1115 if (loop->any_upper_bound)
1117 if (wi::ltu_p (npeel, loop->nb_iterations_upper_bound))
1118 loop->nb_iterations_upper_bound -= npeel;
1119 else
1120 loop->nb_iterations_upper_bound = 0;
1122 if (loop->any_likely_upper_bound)
1124 if (wi::ltu_p (npeel, loop->nb_iterations_likely_upper_bound))
1125 loop->nb_iterations_likely_upper_bound -= npeel;
1126 else
1128 loop->any_estimate = true;
1129 loop->nb_iterations_estimate = 0;
1130 loop->nb_iterations_likely_upper_bound = 0;
1133 profile_count entry_count = profile_count::zero ();
1135 edge e;
1136 edge_iterator ei;
1137 FOR_EACH_EDGE (e, ei, loop->header->preds)
1138 if (e->src != loop->latch)
1140 if (e->src->count.initialized_p ())
1141 entry_count = e->src->count + e->src->count;
1142 gcc_assert (!flow_bb_inside_loop_p (loop, e->src));
1144 profile_probability p = profile_probability::very_unlikely ();
1145 p = entry_count.probability_in (loop->header->count);
1146 scale_loop_profile (loop, p, 0);
1147 bitmap_set_bit (peeled_loops, loop->num);
1148 return true;
1150 /* Adds a canonical induction variable to LOOP if suitable.
1151 CREATE_IV is true if we may create a new iv. UL determines
1152 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
1153 to determine the number of iterations of a loop by direct evaluation.
1154 Returns true if cfg is changed. */
1156 static bool
1157 canonicalize_loop_induction_variables (struct loop *loop,
1158 bool create_iv, enum unroll_level ul,
1159 bool try_eval, bool allow_peel)
1161 edge exit = NULL;
1162 tree niter;
1163 HOST_WIDE_INT maxiter;
1164 bool modified = false;
1165 location_t locus = UNKNOWN_LOCATION;
1166 struct tree_niter_desc niter_desc;
1167 bool may_be_zero = false;
1169 /* For unrolling allow conditional constant or zero iterations, thus
1170 perform loop-header copying on-the-fly. */
1171 exit = single_exit (loop);
1172 niter = chrec_dont_know;
1173 if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
1175 niter = niter_desc.niter;
1176 may_be_zero
1177 = niter_desc.may_be_zero && !integer_zerop (niter_desc.may_be_zero);
1179 if (TREE_CODE (niter) == INTEGER_CST)
1180 locus = gimple_location (last_stmt (exit->src));
1181 else
1183 /* For non-constant niter fold may_be_zero into niter again. */
1184 if (may_be_zero)
1186 if (COMPARISON_CLASS_P (niter_desc.may_be_zero))
1187 niter = fold_build3 (COND_EXPR, TREE_TYPE (niter),
1188 niter_desc.may_be_zero,
1189 build_int_cst (TREE_TYPE (niter), 0), niter);
1190 else
1191 niter = chrec_dont_know;
1192 may_be_zero = false;
1195 /* If the loop has more than one exit, try checking all of them
1196 for # of iterations determinable through scev. */
1197 if (!exit)
1198 niter = find_loop_niter (loop, &exit);
1200 /* Finally if everything else fails, try brute force evaluation. */
1201 if (try_eval
1202 && (chrec_contains_undetermined (niter)
1203 || TREE_CODE (niter) != INTEGER_CST))
1204 niter = find_loop_niter_by_eval (loop, &exit);
1206 if (exit)
1207 locus = gimple_location (last_stmt (exit->src));
1209 if (TREE_CODE (niter) != INTEGER_CST)
1210 exit = NULL;
1213 /* We work exceptionally hard here to estimate the bound
1214 by find_loop_niter_by_eval. Be sure to keep it for future. */
1215 if (niter && TREE_CODE (niter) == INTEGER_CST)
1217 record_niter_bound (loop, wi::to_widest (niter),
1218 exit == single_likely_exit (loop), true);
1221 /* Force re-computation of loop bounds so we can remove redundant exits. */
1222 maxiter = max_loop_iterations_int (loop);
1224 if (dump_file && (dump_flags & TDF_DETAILS)
1225 && TREE_CODE (niter) == INTEGER_CST)
1227 fprintf (dump_file, "Loop %d iterates ", loop->num);
1228 print_generic_expr (dump_file, niter, TDF_SLIM);
1229 fprintf (dump_file, " times.\n");
1231 if (dump_file && (dump_flags & TDF_DETAILS)
1232 && maxiter >= 0)
1234 fprintf (dump_file, "Loop %d iterates at most %i times.\n", loop->num,
1235 (int)maxiter);
1237 if (dump_file && (dump_flags & TDF_DETAILS)
1238 && likely_max_loop_iterations_int (loop) >= 0)
1240 fprintf (dump_file, "Loop %d likely iterates at most %i times.\n",
1241 loop->num, (int)likely_max_loop_iterations_int (loop));
1244 /* Remove exits that are known to be never taken based on loop bound.
1245 Needs to be called after compilation of max_loop_iterations_int that
1246 populates the loop bounds. */
1247 modified |= remove_redundant_iv_tests (loop);
1249 if (try_unroll_loop_completely (loop, exit, niter, may_be_zero, ul,
1250 maxiter, locus, allow_peel))
1251 return true;
1253 if (create_iv
1254 && niter && !chrec_contains_undetermined (niter)
1255 && exit && just_once_each_iteration_p (loop, exit->src))
1257 tree iv_niter = niter;
1258 if (may_be_zero)
1260 if (COMPARISON_CLASS_P (niter_desc.may_be_zero))
1261 iv_niter = fold_build3 (COND_EXPR, TREE_TYPE (iv_niter),
1262 niter_desc.may_be_zero,
1263 build_int_cst (TREE_TYPE (iv_niter), 0),
1264 iv_niter);
1265 else
1266 iv_niter = NULL_TREE;
1268 if (iv_niter)
1269 create_canonical_iv (loop, exit, iv_niter);
1272 if (ul == UL_ALL)
1273 modified |= try_peel_loop (loop, exit, niter, may_be_zero, maxiter);
1275 return modified;
1278 /* The main entry point of the pass. Adds canonical induction variables
1279 to the suitable loops. */
1281 unsigned int
1282 canonicalize_induction_variables (void)
1284 struct loop *loop;
1285 bool changed = false;
1286 bool irred_invalidated = false;
1287 bitmap loop_closed_ssa_invalidated = BITMAP_ALLOC (NULL);
1289 estimate_numbers_of_iterations (cfun);
1291 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1293 changed |= canonicalize_loop_induction_variables (loop,
1294 true, UL_SINGLE_ITER,
1295 true, false);
1297 gcc_assert (!need_ssa_update_p (cfun));
1299 unloop_loops (loop_closed_ssa_invalidated, &irred_invalidated);
1300 if (irred_invalidated
1301 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1302 mark_irreducible_loops ();
1304 /* Clean up the information about numbers of iterations, since brute force
1305 evaluation could reveal new information. */
1306 free_numbers_of_iterations_estimates (cfun);
1307 scev_reset ();
1309 if (!bitmap_empty_p (loop_closed_ssa_invalidated))
1311 gcc_checking_assert (loops_state_satisfies_p (LOOP_CLOSED_SSA));
1312 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1314 BITMAP_FREE (loop_closed_ssa_invalidated);
1316 if (changed)
1317 return TODO_cleanup_cfg;
1318 return 0;
1321 /* Propagate constant SSA_NAMEs defined in basic block BB. */
1323 static void
1324 propagate_constants_for_unrolling (basic_block bb)
1326 /* Look for degenerate PHI nodes with constant argument. */
1327 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
1329 gphi *phi = gsi.phi ();
1330 tree result = gimple_phi_result (phi);
1331 tree arg = gimple_phi_arg_def (phi, 0);
1333 if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (result)
1334 && gimple_phi_num_args (phi) == 1
1335 && CONSTANT_CLASS_P (arg))
1337 replace_uses_by (result, arg);
1338 gsi_remove (&gsi, true);
1339 release_ssa_name (result);
1341 else
1342 gsi_next (&gsi);
1345 /* Look for assignments to SSA names with constant RHS. */
1346 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
1348 gimple *stmt = gsi_stmt (gsi);
1349 tree lhs;
1351 if (is_gimple_assign (stmt)
1352 && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_constant
1353 && (lhs = gimple_assign_lhs (stmt), TREE_CODE (lhs) == SSA_NAME)
1354 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1356 replace_uses_by (lhs, gimple_assign_rhs1 (stmt));
1357 gsi_remove (&gsi, true);
1358 release_ssa_name (lhs);
1360 else
1361 gsi_next (&gsi);
1365 /* Process loops from innermost to outer, stopping at the innermost
1366 loop we unrolled. */
1368 static bool
1369 tree_unroll_loops_completely_1 (bool may_increase_size, bool unroll_outer,
1370 bitmap father_bbs, struct loop *loop)
1372 struct loop *loop_father;
1373 bool changed = false;
1374 struct loop *inner;
1375 enum unroll_level ul;
1376 unsigned num = number_of_loops (cfun);
1378 /* Process inner loops first. Don't walk loops added by the recursive
1379 calls because SSA form is not up-to-date. They can be handled in the
1380 next iteration. */
1381 for (inner = loop->inner; inner != NULL; inner = inner->next)
1382 if ((unsigned) inner->num < num)
1383 changed |= tree_unroll_loops_completely_1 (may_increase_size,
1384 unroll_outer, father_bbs,
1385 inner);
1387 /* If we changed an inner loop we cannot process outer loops in this
1388 iteration because SSA form is not up-to-date. Continue with
1389 siblings of outer loops instead. */
1390 if (changed)
1391 return true;
1393 /* Don't unroll #pragma omp simd loops until the vectorizer
1394 attempts to vectorize those. */
1395 if (loop->force_vectorize)
1396 return false;
1398 /* Try to unroll this loop. */
1399 loop_father = loop_outer (loop);
1400 if (!loop_father)
1401 return false;
1403 if (loop->unroll > 1)
1404 ul = UL_ALL;
1405 else if (may_increase_size && optimize_loop_nest_for_speed_p (loop)
1406 /* Unroll outermost loops only if asked to do so or they do
1407 not cause code growth. */
1408 && (unroll_outer || loop_outer (loop_father)))
1409 ul = UL_ALL;
1410 else
1411 ul = UL_NO_GROWTH;
1413 if (canonicalize_loop_induction_variables
1414 (loop, false, ul, !flag_tree_loop_ivcanon, unroll_outer))
1416 /* If we'll continue unrolling, we need to propagate constants
1417 within the new basic blocks to fold away induction variable
1418 computations; otherwise, the size might blow up before the
1419 iteration is complete and the IR eventually cleaned up. */
1420 if (loop_outer (loop_father))
1421 bitmap_set_bit (father_bbs, loop_father->header->index);
1423 return true;
1426 return false;
1429 /* Unroll LOOPS completely if they iterate just few times. Unless
1430 MAY_INCREASE_SIZE is true, perform the unrolling only if the
1431 size of the code does not increase. */
1433 static unsigned int
1434 tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)
1436 bitmap father_bbs = BITMAP_ALLOC (NULL);
1437 bool changed;
1438 int iteration = 0;
1439 bool irred_invalidated = false;
1441 estimate_numbers_of_iterations (cfun);
1445 changed = false;
1446 bitmap loop_closed_ssa_invalidated = NULL;
1448 if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
1449 loop_closed_ssa_invalidated = BITMAP_ALLOC (NULL);
1451 free_numbers_of_iterations_estimates (cfun);
1452 estimate_numbers_of_iterations (cfun);
1454 changed = tree_unroll_loops_completely_1 (may_increase_size,
1455 unroll_outer, father_bbs,
1456 current_loops->tree_root);
1457 if (changed)
1459 unsigned i;
1461 unloop_loops (loop_closed_ssa_invalidated, &irred_invalidated);
1463 /* We can not use TODO_update_ssa_no_phi because VOPS gets confused. */
1464 if (loop_closed_ssa_invalidated
1465 && !bitmap_empty_p (loop_closed_ssa_invalidated))
1466 rewrite_into_loop_closed_ssa (loop_closed_ssa_invalidated,
1467 TODO_update_ssa);
1468 else
1469 update_ssa (TODO_update_ssa);
1471 /* father_bbs is a bitmap of loop father header BB indices.
1472 Translate that to what non-root loops these BBs belong to now. */
1473 bitmap_iterator bi;
1474 bitmap fathers = BITMAP_ALLOC (NULL);
1475 EXECUTE_IF_SET_IN_BITMAP (father_bbs, 0, i, bi)
1477 basic_block unrolled_loop_bb = BASIC_BLOCK_FOR_FN (cfun, i);
1478 if (! unrolled_loop_bb)
1479 continue;
1480 if (loop_outer (unrolled_loop_bb->loop_father))
1481 bitmap_set_bit (fathers,
1482 unrolled_loop_bb->loop_father->num);
1484 bitmap_clear (father_bbs);
1485 /* Propagate the constants within the new basic blocks. */
1486 EXECUTE_IF_SET_IN_BITMAP (fathers, 0, i, bi)
1488 loop_p father = get_loop (cfun, i);
1489 basic_block *body = get_loop_body_in_dom_order (father);
1490 for (unsigned j = 0; j < father->num_nodes; j++)
1491 propagate_constants_for_unrolling (body[j]);
1492 free (body);
1494 BITMAP_FREE (fathers);
1496 /* This will take care of removing completely unrolled loops
1497 from the loop structures so we can continue unrolling now
1498 innermost loops. */
1499 if (cleanup_tree_cfg ())
1500 update_ssa (TODO_update_ssa_only_virtuals);
1502 /* Clean up the information about numbers of iterations, since
1503 complete unrolling might have invalidated it. */
1504 scev_reset ();
1505 if (flag_checking && loops_state_satisfies_p (LOOP_CLOSED_SSA))
1506 verify_loop_closed_ssa (true);
1508 if (loop_closed_ssa_invalidated)
1509 BITMAP_FREE (loop_closed_ssa_invalidated);
1511 while (changed
1512 && ++iteration <= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS));
1514 BITMAP_FREE (father_bbs);
1516 if (irred_invalidated
1517 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1518 mark_irreducible_loops ();
1520 return 0;
1523 /* Canonical induction variable creation pass. */
1525 namespace {
1527 const pass_data pass_data_iv_canon =
1529 GIMPLE_PASS, /* type */
1530 "ivcanon", /* name */
1531 OPTGROUP_LOOP, /* optinfo_flags */
1532 TV_TREE_LOOP_IVCANON, /* tv_id */
1533 ( PROP_cfg | PROP_ssa ), /* properties_required */
1534 0, /* properties_provided */
1535 0, /* properties_destroyed */
1536 0, /* todo_flags_start */
1537 0, /* todo_flags_finish */
1540 class pass_iv_canon : public gimple_opt_pass
1542 public:
1543 pass_iv_canon (gcc::context *ctxt)
1544 : gimple_opt_pass (pass_data_iv_canon, ctxt)
1547 /* opt_pass methods: */
1548 virtual bool gate (function *) { return flag_tree_loop_ivcanon != 0; }
1549 virtual unsigned int execute (function *fun);
1551 }; // class pass_iv_canon
1553 unsigned int
1554 pass_iv_canon::execute (function *fun)
1556 if (number_of_loops (fun) <= 1)
1557 return 0;
1559 return canonicalize_induction_variables ();
1562 } // anon namespace
1564 gimple_opt_pass *
1565 make_pass_iv_canon (gcc::context *ctxt)
1567 return new pass_iv_canon (ctxt);
1570 /* Complete unrolling of loops. */
1572 namespace {
1574 const pass_data pass_data_complete_unroll =
1576 GIMPLE_PASS, /* type */
1577 "cunroll", /* name */
1578 OPTGROUP_LOOP, /* optinfo_flags */
1579 TV_COMPLETE_UNROLL, /* tv_id */
1580 ( PROP_cfg | PROP_ssa ), /* properties_required */
1581 0, /* properties_provided */
1582 0, /* properties_destroyed */
1583 0, /* todo_flags_start */
1584 0, /* todo_flags_finish */
1587 class pass_complete_unroll : public gimple_opt_pass
1589 public:
1590 pass_complete_unroll (gcc::context *ctxt)
1591 : gimple_opt_pass (pass_data_complete_unroll, ctxt)
1594 /* opt_pass methods: */
1595 virtual unsigned int execute (function *);
1597 }; // class pass_complete_unroll
1599 unsigned int
1600 pass_complete_unroll::execute (function *fun)
1602 if (number_of_loops (fun) <= 1)
1603 return 0;
1605 /* If we ever decide to run loop peeling more than once, we will need to
1606 track loops already peeled in loop structures themselves to avoid
1607 re-peeling the same loop multiple times. */
1608 if (flag_peel_loops)
1609 peeled_loops = BITMAP_ALLOC (NULL);
1610 unsigned int val = tree_unroll_loops_completely (flag_unroll_loops
1611 || flag_peel_loops
1612 || optimize >= 3, true);
1613 if (peeled_loops)
1615 BITMAP_FREE (peeled_loops);
1616 peeled_loops = NULL;
1618 return val;
1621 } // anon namespace
1623 gimple_opt_pass *
1624 make_pass_complete_unroll (gcc::context *ctxt)
1626 return new pass_complete_unroll (ctxt);
1629 /* Complete unrolling of inner loops. */
1631 namespace {
1633 const pass_data pass_data_complete_unrolli =
1635 GIMPLE_PASS, /* type */
1636 "cunrolli", /* name */
1637 OPTGROUP_LOOP, /* optinfo_flags */
1638 TV_COMPLETE_UNROLL, /* tv_id */
1639 ( PROP_cfg | PROP_ssa ), /* properties_required */
1640 0, /* properties_provided */
1641 0, /* properties_destroyed */
1642 0, /* todo_flags_start */
1643 0, /* todo_flags_finish */
1646 class pass_complete_unrolli : public gimple_opt_pass
1648 public:
1649 pass_complete_unrolli (gcc::context *ctxt)
1650 : gimple_opt_pass (pass_data_complete_unrolli, ctxt)
1653 /* opt_pass methods: */
1654 virtual bool gate (function *) { return optimize >= 2; }
1655 virtual unsigned int execute (function *);
1657 }; // class pass_complete_unrolli
1659 unsigned int
1660 pass_complete_unrolli::execute (function *fun)
1662 unsigned ret = 0;
1664 loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
1665 if (number_of_loops (fun) > 1)
1667 scev_initialize ();
1668 ret = tree_unroll_loops_completely (optimize >= 3, false);
1669 scev_finalize ();
1671 loop_optimizer_finalize ();
1673 return ret;
1676 } // anon namespace
1678 gimple_opt_pass *
1679 make_pass_complete_unrolli (gcc::context *ctxt)
1681 return new pass_complete_unrolli (ctxt);