1/* Induction variable canonicalization and loop peeling.
2 Copyright (C) 2004-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it
7under the terms of the GNU General Public License as published by the
8Free Software Foundation; either version 3, or (at your option) any
9later version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT
12ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
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.
24
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.
30
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). */
37
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"
66
67/* Specifies types of loops that may be unrolled. */
68
69enum unroll_level
70{
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. */
76};
77
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. */
82
83void
84create_canonical_iv (struct loop *loop, edge exit, tree niter,
85 tree *var_before = NULL, tree *var_after = NULL)
86{
87 edge in;
88 tree type, var;
89 gcond *cond;
90 gimple_stmt_iterator incr_at;
91 enum tree_code cmp;
92
93 if (dump_file && (dump_flags & TDF_DETAILS))
94 {
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");
98 }
99
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);
104
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. */
109
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;
121
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);
127}
128
129/* Describe size of loop as detected by tree_estimate_loop_size. */
130struct loop_size
131{
132 /* Number of instructions in the loop. */
133 int overall;
134
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;
139
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;
144
145 /* If some IV computation will become constant. */
146 bool constant_iv;
147
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;
158};
159
160/* Return true if OP in STMT will be constant after peeling LOOP. */
161
162static bool
163constant_after_peeling (tree op, gimple *stmt, struct loop *loop)
164{
165 if (is_gimple_min_invariant (op))
166 return true;
167
168 /* We can still fold accesses to constant arrays when index is known. */
169 if (TREE_CODE (op) != SSA_NAME)
170 {
171 tree base = op;
172
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))
179 {
180 /* If so, see if we understand all the indices. */
181 base = op;
182 while (handled_component_p (base))
183 {
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);
188 }
189 return true;
190 }
191 return false;
192 }
193
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;
202}
203
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. */
211
212static bool
213tree_estimate_loop_size (struct loop *loop, edge exit, edge edge_to_cancel,
214 struct loop_size *size, int upper_bound)
215{
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);
221
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;
231
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++)
235 {
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);
244
245 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
246 {
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;
252
253 if (dump_file && (dump_flags & TDF_DETAILS))
254 {
255 fprintf (dump_file, " size: %3i ", num);
256 print_gimple_stmt (dump_file, gsi_stmt (gsi), 0);
257 }
258
259 /* Look for reasons why we might optimize this stmt away. */
260
261 if (!gimple_has_side_effects (stmt))
262 {
263 /* Exit conditional. */
264 if (exit && body[i] == exit->src
265 && stmt == last_stmt (exit->src))
266 {
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;
271 }
272 if (edge_to_cancel && body[i] == edge_to_cancel->src
273 && stmt == last_stmt (edge_to_cancel->src))
274 {
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;
279 }
280 /* Sets of IV variables */
281 if (gimple_code (stmt) == GIMPLE_ASSIGN
282 && constant_after_peeling (gimple_assign_lhs (stmt), stmt, loop))
283 {
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;
288 }
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)))
297 {
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;
303 }
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)))))
323 {
324 if (dump_file && (dump_flags & TDF_DETAILS))
325 fprintf (dump_file, " Constant conditional.\n");
326 likely_eliminated = true;
327 }
328 }
329
330 size->overall += num;
331 if (likely_eliminated || likely_eliminated_peeled)
332 size->eliminated_by_peeling += num;
333 if (!after_exit)
334 {
335 size->last_iteration += num;
336 if (likely_eliminated || likely_eliminated_last)
337 size->last_iteration_eliminated_by_peeling += num;
338 }
339 if ((size->overall * 3 / 2 - size->eliminated_by_peeling
340 - size->last_iteration_eliminated_by_peeling) > upper_bound)
341 {
342 free (body);
343 path.release ();
344 return true;
345 }
346 }
347 }
348 while (path.length ())
349 {
350 basic_block bb = path.pop ();
351 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
352 {
353 gimple *stmt = gsi_stmt (gsi);
354 if (gimple_code (stmt) == GIMPLE_CALL
355 && !gimple_inexpensive_call_p (as_a <gcall *> (stmt)))
356 {
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 ++;
363 }
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++;
378 }
379 }
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);
385
386 free (body);
387 return false;
388}
389
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.
395
396 Loop body is likely going to simplify further, this is difficult
397 to guess, we just decrease the result by 1/3. */
398
399static unsigned HOST_WIDE_INT
400estimated_unrolled_size (struct loop_size *size,
401 unsigned HOST_WIDE_INT nunroll)
402{
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;
409
410 unr_insns = unr_insns * 2 / 3;
411 if (unr_insns <= 0)
412 unr_insns = 1;
413
414 return unr_insns;
415}
416
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.
421
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
425
426 int a[5];
427 for (i=0;i<b;i++)
428 a[i]=0;
429
430 Here we prove the loop to iterate 5 times but we do not know
431 it from induction variable.
432
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).
437
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. */
441
442static edge
443loop_edge_to_cancel (struct loop *loop)
444{
445 vec<edge> exits;
446 unsigned i;
447 edge edge_to_cancel;
448 gimple_stmt_iterator gsi;
449
450 /* We want only one predecestor of the loop. */
451 if (EDGE_COUNT (loop->latch->preds) > 1)
452 return NULL;
453
454 exits = get_loop_exit_edges (loop);
455
456 FOR_EACH_VEC_ELT (exits, i, edge_to_cancel)
457 {
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);
466
467 /* We only can handle conditionals. */
468 if (!(edge_to_cancel->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
469 continue;
470
471 /* We should never have conditionals in the loop latch. */
472 gcc_assert (edge_to_cancel->dest != loop->header);
473
474 /* Check that it leads to loop latch. */
475 if (edge_to_cancel->dest != loop->latch)
476 continue;
477
478 exits.release ();
479
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;
487 }
488 exits.release ();
489 return NULL;
490}
491
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. */
495
496static bool
497remove_exits_and_undefined_stmts (struct loop *loop, unsigned int npeeled)
498{
499 struct nb_iter_bound *elt;
500 bool changed = false;
501
502 for (elt = loop->bounds; elt; elt = elt->next)
503 {
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))
509 {
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))
518 {
519 fprintf (dump_file, "Forced statement unreachable: ");
520 print_gimple_stmt (dump_file, elt->stmt, 0);
521 }
522 }
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))
526 {
527 basic_block bb = gimple_bb (elt->stmt);
528 edge exit_edge = EDGE_SUCC (bb, 0);
529
530 if (dump_file && (dump_flags & TDF_DETAILS))
531 {
532 fprintf (dump_file, "Forced exit to be taken: ");
533 print_gimple_stmt (dump_file, elt->stmt, 0);
534 }
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;
546 }
547 }
548 return changed;
549}
550
551/* Remove all exits that are known to be never taken because of the loop bound
552 discovered. */
553
554static bool
555remove_redundant_iv_tests (struct loop *loop)
556{
557 struct nb_iter_bound *elt;
558 bool changed = false;
559
560 if (!loop->any_upper_bound)
561 return false;
562 for (elt = loop->bounds; elt; elt = elt->next)
563 {
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))
568 {
569 basic_block bb = gimple_bb (elt->stmt);
570 edge exit_edge = EDGE_SUCC (bb, 0);
571 struct tree_niter_desc niter;
572
573 if (!loop_exit_edge_p (loop, exit_edge))
574 exit_edge = EDGE_SUCC (bb, 1);
575
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;
587
588 if (dump_file && (dump_flags & TDF_DETAILS))
589 {
590 fprintf (dump_file, "Removed pointless exit: ");
591 print_gimple_stmt (dump_file, elt->stmt, 0);
592 }
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;
600 }
601 }
602 return changed;
603}
604
605/* Stores loops that will be unlooped and edges that will be removed
606 after we process whole loop tree. */
607static vec<loop_p> loops_to_unloop;
608static vec<int> loops_to_unloop_nunroll;
609static vec<edge> edges_to_remove;
610/* Stores loops that has been peeled. */
611static bitmap peeled_loops;
612
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.
618
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. */
624
625static void
626unloop_loops (bitmap loop_closed_ssa_invalidated,
627 bool *irred_invalidated)
628{
629 while (loops_to_unloop.length ())
630 {
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;
639
640 remove_exits_and_undefined_stmts (loop, n_unroll);
641
642 /* Unloop destroys the latch edge. */
643 unloop (loop, irred_invalidated, loop_closed_ssa_invalidated);
644
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;
652
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);
656
657 gsi = gsi_start_bb (latch_edge->dest);
658 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
659 }
660 loops_to_unloop.release ();
661 loops_to_unloop_nunroll.release ();
662
663 /* Remove edges in peeled copies. */
664 unsigned i;
665 edge e;
666 FOR_EACH_VEC_ELT (edges_to_remove, i, e)
667 {
668 bool ok = remove_path (e, irred_invalidated, loop_closed_ssa_invalidated);
669 gcc_assert (ok);
670 }
671 edges_to_remove.release ();
672}
673
674/* Tries to unroll LOOP completely, i.e. NITER times.
675 UL determines which loops we are allowed to unroll.
676 EXIT is the exit of the loop that should be eliminated.
677 MAXITER specfy bound on number of iterations, -1 if it is
678 not known or too large for HOST_WIDE_INT. The location
679 LOCUS corresponding to the loop is used when emitting
680 a summary of the unroll to the dump file. */
681
682static bool
683try_unroll_loop_completely (struct loop *loop,
684 edge exit, tree niter,
685 enum unroll_level ul,
686 HOST_WIDE_INT maxiter,
687 location_t locus, bool allow_peel)
688{
689 unsigned HOST_WIDE_INT n_unroll = 0;
690 bool n_unroll_found = false;
691 edge edge_to_cancel = NULL;
692
693 /* See if we proved number of iterations to be low constant.
694
695 EXIT is an edge that will be removed in all but last iteration of
696 the loop.
697
698 EDGE_TO_CACNEL is an edge that will be removed from the last iteration
699 of the unrolled sequence and is expected to make the final loop not
700 rolling.
701
702 If the number of execution of loop is determined by standard induction
703 variable test, then EXIT and EDGE_TO_CANCEL are the two edges leaving
704 from the iv test. */
705 if (tree_fits_uhwi_p (niter))
706 {
707 n_unroll = tree_to_uhwi (niter);
708 n_unroll_found = true;
709 edge_to_cancel = EDGE_SUCC (exit->src, 0);
710 if (edge_to_cancel == exit)
711 edge_to_cancel = EDGE_SUCC (exit->src, 1);
712 }
713 /* We do not know the number of iterations and thus we can not eliminate
714 the EXIT edge. */
715 else
716 exit = NULL;
717
718 /* See if we can improve our estimate by using recorded loop bounds. */
719 if ((allow_peel || maxiter == 0 || ul == UL_NO_GROWTH)
720 && maxiter >= 0
721 && (!n_unroll_found || (unsigned HOST_WIDE_INT)maxiter < n_unroll))
722 {
723 n_unroll = maxiter;
724 n_unroll_found = true;
725 /* Loop terminates before the IV variable test, so we can not
726 remove it in the last iteration. */
727 edge_to_cancel = NULL;
728 }
729
730 if (!n_unroll_found)
731 return false;
732
733 if (!loop->unroll
734 && n_unroll > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES))
735 {
736 if (dump_file && (dump_flags & TDF_DETAILS))
737 fprintf (dump_file, "Not unrolling loop %d "
738 "(--param max-completely-peel-times limit reached).\n",
739 loop->num);
740 return false;
741 }
742
743 if (!edge_to_cancel)
744 edge_to_cancel = loop_edge_to_cancel (loop);
745
746 if (n_unroll)
747 {
748 if (ul == UL_SINGLE_ITER)
749 return false;
750
751 if (loop->unroll)
752 {
753 /* If the unrolling factor is too large, bail out. */
754 if (n_unroll > (unsigned)loop->unroll)
755 {
756 if (dump_file && (dump_flags & TDF_DETAILS))
757 fprintf (dump_file,
758 "Not unrolling loop %d: "
759 "user didn't want it unrolled completely.\n",
760 loop->num);
761 return false;
762 }
763 }
764 else
765 {
766 struct loop_size size;
767 /* EXIT can be removed only if we are sure it passes first N_UNROLL
768 iterations. */
769 bool remove_exit = (exit && niter
770 && TREE_CODE (niter) == INTEGER_CST
771 && wi::leu_p (n_unroll, wi::to_widest (niter)));
772 bool large
773 = tree_estimate_loop_size
774 (loop, remove_exit ? exit : NULL, edge_to_cancel, &size,
775 PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS));
776 if (large)
777 {
778 if (dump_file && (dump_flags & TDF_DETAILS))
779 fprintf (dump_file, "Not unrolling loop %d: it is too large.\n",
780 loop->num);
781 return false;
782 }
783
784 unsigned HOST_WIDE_INT ninsns = size.overall;
785 unsigned HOST_WIDE_INT unr_insns
786 = estimated_unrolled_size (&size, n_unroll);
787 if (dump_file && (dump_flags & TDF_DETAILS))
788 {
789 fprintf (dump_file, " Loop size: %d\n", (int) ninsns);
790 fprintf (dump_file, " Estimated size after unrolling: %d\n",
791 (int) unr_insns);
792 }
793
794 /* If the code is going to shrink, we don't need to be extra
795 cautious on guessing if the unrolling is going to be
796 profitable. */
797 if (unr_insns
798 /* If there is IV variable that will become constant, we
799 save one instruction in the loop prologue we do not
800 account otherwise. */
801 <= ninsns + (size.constant_iv != false))
802 ;
803 /* We unroll only inner loops, because we do not consider it
804 profitable otheriwse. We still can cancel loopback edge
805 of not rolling loop; this is always a good idea. */
806 else if (ul == UL_NO_GROWTH)
807 {
808 if (dump_file && (dump_flags & TDF_DETAILS))
809 fprintf (dump_file, "Not unrolling loop %d: size would grow.\n",
810 loop->num);
811 return false;
812 }
813 /* Outer loops tend to be less interesting candidates for
814 complete unrolling unless we can do a lot of propagation
815 into the inner loop body. For now we disable outer loop
816 unrolling when the code would grow. */
817 else if (loop->inner)
818 {
819 if (dump_file && (dump_flags & TDF_DETAILS))
820 fprintf (dump_file, "Not unrolling loop %d: "
821 "it is not innermost and code would grow.\n",
822 loop->num);
823 return false;
824 }
825 /* If there is call on a hot path through the loop, then
826 there is most probably not much to optimize. */
827 else if (size.num_non_pure_calls_on_hot_path)
828 {
829 if (dump_file && (dump_flags & TDF_DETAILS))
830 fprintf (dump_file, "Not unrolling loop %d: "
831 "contains call and code would grow.\n",
832 loop->num);
833 return false;
834 }
835 /* If there is pure/const call in the function, then we can
836 still optimize the unrolled loop body if it contains some
837 other interesting code than the calls and code storing or
838 cumulating the return value. */
839 else if (size.num_pure_calls_on_hot_path
840 /* One IV increment, one test, one ivtmp store and
841 one useful stmt. That is about minimal loop
842 doing pure call. */
843 && (size.non_call_stmts_on_hot_path
844 <= 3 + size.num_pure_calls_on_hot_path))
845 {
846 if (dump_file && (dump_flags & TDF_DETAILS))
847 fprintf (dump_file, "Not unrolling loop %d: "
848 "contains just pure calls and code would grow.\n",
849 loop->num);
850 return false;
851 }
852 /* Complete unrolling is major win when control flow is
853 removed and one big basic block is created. If the loop
854 contains control flow the optimization may still be a win
855 because of eliminating the loop overhead but it also may
856 blow the branch predictor tables. Limit number of
857 branches on the hot path through the peeled sequence. */
858 else if (size.num_branches_on_hot_path * (int)n_unroll
859 > PARAM_VALUE (PARAM_MAX_PEEL_BRANCHES))
860 {
861 if (dump_file && (dump_flags & TDF_DETAILS))
862 fprintf (dump_file, "Not unrolling loop %d: "
863 "number of branches on hot path in the unrolled "
864 "sequence reaches --param max-peel-branches limit.\n",
865 loop->num);
866 return false;
867 }
868 else if (unr_insns
869 > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
870 {
871 if (dump_file && (dump_flags & TDF_DETAILS))
872 fprintf (dump_file, "Not unrolling loop %d: "
873 "number of insns in the unrolled sequence reaches "
874 "--param max-completely-peeled-insns limit.\n",
875 loop->num);
876 return false;
877 }
878 }
879
880 initialize_original_copy_tables ();
881 auto_sbitmap wont_exit (n_unroll + 1);
882 if (exit && niter
883 && TREE_CODE (niter) == INTEGER_CST
884 && wi::leu_p (n_unroll, wi::to_widest (niter)))
885 {
886 bitmap_ones (wont_exit);
887 if (wi::eq_p (wi::to_widest (niter), n_unroll)
888 || edge_to_cancel)
889 bitmap_clear_bit (wont_exit, 0);
890 }
891 else
892 {
893 exit = NULL;
894 bitmap_clear (wont_exit);
895 }
896
897 if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
898 n_unroll, wont_exit,
899 exit, &edges_to_remove,
900 DLTHE_FLAG_UPDATE_FREQ
901 | DLTHE_FLAG_COMPLETTE_PEEL))
902 {
903 free_original_copy_tables ();
904 if (dump_file && (dump_flags & TDF_DETAILS))
905 fprintf (dump_file, "Failed to duplicate the loop\n");
906 return false;
907 }
908
909 free_original_copy_tables ();
910 }
911
912 /* Remove the conditional from the last copy of the loop. */
913 if (edge_to_cancel)
914 {
915 gcond *cond = as_a <gcond *> (last_stmt (edge_to_cancel->src));
916 force_edge_cold (edge_to_cancel, true);
917 if (edge_to_cancel->flags & EDGE_TRUE_VALUE)
918 gimple_cond_make_false (cond);
919 else
920 gimple_cond_make_true (cond);
921 update_stmt (cond);
922 /* Do not remove the path, as doing so may remove outer loop and
923 confuse bookkeeping code in tree_unroll_loops_completely. */
924 }
925
926 /* Store the loop for later unlooping and exit removal. */
927 loops_to_unloop.safe_push (loop);
928 loops_to_unloop_nunroll.safe_push (n_unroll);
929
930 if (dump_enabled_p ())
931 {
932 if (!n_unroll)
933 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, locus,
934 "loop turned into non-loop; it never loops\n");
935 else
936 {
937 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, locus,
938 "loop with %d iterations completely unrolled",
939 (int) n_unroll);
940 if (loop->header->count.initialized_p ())
941 dump_printf (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS,
942 " (header execution count %d)",
943 (int)loop->header->count.to_gcov_type ());
944 dump_printf (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, "\n");
945 }
946 }
947
948 if (dump_file && (dump_flags & TDF_DETAILS))
949 {
950 if (exit)
951 fprintf (dump_file, "Exit condition of peeled iterations was "
952 "eliminated.\n");
953 if (edge_to_cancel)
954 fprintf (dump_file, "Last iteration exit edge was proved true.\n");
955 else
956 fprintf (dump_file, "Latch of last iteration was marked by "
957 "__builtin_unreachable ().\n");
958 }
959
960 return true;
961}
962
963/* Return number of instructions after peeling. */
964static unsigned HOST_WIDE_INT
965estimated_peeled_sequence_size (struct loop_size *size,
966 unsigned HOST_WIDE_INT npeel)
967{
968 return MAX (npeel * (HOST_WIDE_INT) (size->overall
969 - size->eliminated_by_peeling), 1);
970}
971
972/* If the loop is expected to iterate N times and is
973 small enough, duplicate the loop body N+1 times before
974 the loop itself. This way the hot path will never
975 enter the loop.
976 Parameters are the same as for try_unroll_loops_completely */
977
978static bool
979try_peel_loop (struct loop *loop,
980 edge exit, tree niter,
981 HOST_WIDE_INT maxiter)
982{
983 HOST_WIDE_INT npeel;
984 struct loop_size size;
985 int peeled_size;
986
987 if (!flag_peel_loops
988 || PARAM_VALUE (PARAM_MAX_PEEL_TIMES) <= 0
989 || !peeled_loops)
990 return false;
991
992 if (bitmap_bit_p (peeled_loops, loop->num))
993 {
994 if (dump_file)
995 fprintf (dump_file, "Not peeling: loop is already peeled\n");
996 return false;
997 }
998
999 /* We don't peel loops that will be unrolled as this can duplicate a
1000 loop more times than the user requested. */
1001 if (loop->unroll)
1002 {
1003 if (dump_file)
1004 fprintf (dump_file, "Not peeling: user didn't want it peeled.\n");
1005 return false;
1006 }
1007
1008 /* Peel only innermost loops.
1009 While the code is perfectly capable of peeling non-innermost loops,
1010 the heuristics would probably need some improvements. */
1011 if (loop->inner)
1012 {
1013 if (dump_file)
1014 fprintf (dump_file, "Not peeling: outer loop\n");
1015 return false;
1016 }
1017
1018 if (!optimize_loop_for_speed_p (loop))
1019 {
1020 if (dump_file)
1021 fprintf (dump_file, "Not peeling: cold loop\n");
1022 return false;
1023 }
1024
1025 /* Check if there is an estimate on the number of iterations. */
1026 npeel = estimated_loop_iterations_int (loop);
1027 if (npeel < 0)
1028 npeel = likely_max_loop_iterations_int (loop);
1029 if (npeel < 0)
1030 {
1031 if (dump_file)
1032 fprintf (dump_file, "Not peeling: number of iterations is not "
1033 "estimated\n");
1034 return false;
1035 }
1036 if (maxiter >= 0 && maxiter <= npeel)
1037 {
1038 if (dump_file)
1039 fprintf (dump_file, "Not peeling: upper bound is known so can "
1040 "unroll completely\n");
1041 return false;
1042 }
1043
1044 /* We want to peel estimated number of iterations + 1 (so we never
1045 enter the loop on quick path). Check against PARAM_MAX_PEEL_TIMES
1046 and be sure to avoid overflows. */
1047 if (npeel > PARAM_VALUE (PARAM_MAX_PEEL_TIMES) - 1)
1048 {
1049 if (dump_file)
1050 fprintf (dump_file, "Not peeling: rolls too much "
1051 "(%i + 1 > --param max-peel-times)\n", (int) npeel);
1052 return false;
1053 }
1054 npeel++;
1055
1056 /* Check peeled loops size. */
1057 tree_estimate_loop_size (loop, exit, NULL, &size,
1058 PARAM_VALUE (PARAM_MAX_PEELED_INSNS));
1059 if ((peeled_size = estimated_peeled_sequence_size (&size, (int) npeel))
1060 > PARAM_VALUE (PARAM_MAX_PEELED_INSNS))
1061 {
1062 if (dump_file)
1063 fprintf (dump_file, "Not peeling: peeled sequence size is too large "
1064 "(%i insns > --param max-peel-insns)", peeled_size);
1065 return false;
1066 }
1067
1068 /* Duplicate possibly eliminating the exits. */
1069 initialize_original_copy_tables ();
1070 auto_sbitmap wont_exit (npeel + 1);
1071 if (exit && niter
1072 && TREE_CODE (niter) == INTEGER_CST
1073 && wi::leu_p (npeel, wi::to_widest (niter)))
1074 {
1075 bitmap_ones (wont_exit);
1076 bitmap_clear_bit (wont_exit, 0);
1077 }
1078 else
1079 {
1080 exit = NULL;
1081 bitmap_clear (wont_exit);
1082 }
1083 if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
1084 npeel, wont_exit,
1085 exit, &edges_to_remove,
1086 DLTHE_FLAG_UPDATE_FREQ))
1087 {
1088 free_original_copy_tables ();
1089 return false;
1090 }
1091 free_original_copy_tables ();
1092 if (dump_file && (dump_flags & TDF_DETAILS))
1093 {
1094 fprintf (dump_file, "Peeled loop %d, %i times.\n",
1095 loop->num, (int) npeel);
1096 }
1097 if (loop->any_estimate)
1098 {
1099 if (wi::ltu_p (npeel, loop->nb_iterations_estimate))
1100 loop->nb_iterations_estimate -= npeel;
1101 else
1102 loop->nb_iterations_estimate = 0;
1103 }
1104 if (loop->any_upper_bound)
1105 {
1106 if (wi::ltu_p (npeel, loop->nb_iterations_upper_bound))
1107 loop->nb_iterations_upper_bound -= npeel;
1108 else
1109 loop->nb_iterations_upper_bound = 0;
1110 }
1111 if (loop->any_likely_upper_bound)
1112 {
1113 if (wi::ltu_p (npeel, loop->nb_iterations_likely_upper_bound))
1114 loop->nb_iterations_likely_upper_bound -= npeel;
1115 else
1116 {
1117 loop->any_estimate = true;
1118 loop->nb_iterations_estimate = 0;
1119 loop->nb_iterations_likely_upper_bound = 0;
1120 }
1121 }
1122 profile_count entry_count = profile_count::zero ();
1123
1124 edge e;
1125 edge_iterator ei;
1126 FOR_EACH_EDGE (e, ei, loop->header->preds)
1127 if (e->src != loop->latch)
1128 {
1129 if (e->src->count.initialized_p ())
1130 entry_count = e->src->count + e->src->count;
1131 gcc_assert (!flow_bb_inside_loop_p (loop, e->src));
1132 }
1133 profile_probability p = profile_probability::very_unlikely ();
1134 p = entry_count.probability_in (loop->header->count);
1135 scale_loop_profile (loop, p, 0);
1136 bitmap_set_bit (peeled_loops, loop->num);
1137 return true;
1138}
1139/* Adds a canonical induction variable to LOOP if suitable.
1140 CREATE_IV is true if we may create a new iv. UL determines
1141 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
1142 to determine the number of iterations of a loop by direct evaluation.
1143 Returns true if cfg is changed. */
1144
1145static bool
1146canonicalize_loop_induction_variables (struct loop *loop,
1147 bool create_iv, enum unroll_level ul,
1148 bool try_eval, bool allow_peel)
1149{
1150 edge exit = NULL;
1151 tree niter;
1152 HOST_WIDE_INT maxiter;
1153 bool modified = false;
1154 location_t locus = UNKNOWN_LOCATION;
1155
1156 niter = number_of_latch_executions (loop);
1157 exit = single_exit (loop);
1158 if (TREE_CODE (niter) == INTEGER_CST)
1159 locus = gimple_location (last_stmt (exit->src));
1160 else
1161 {
1162 /* If the loop has more than one exit, try checking all of them
1163 for # of iterations determinable through scev. */
1164 if (!exit)
1165 niter = find_loop_niter (loop, &exit);
1166
1167 /* Finally if everything else fails, try brute force evaluation. */
1168 if (try_eval
1169 && (chrec_contains_undetermined (niter)
1170 || TREE_CODE (niter) != INTEGER_CST))
1171 niter = find_loop_niter_by_eval (loop, &exit);
1172
1173 if (exit)
1174 locus = gimple_location (last_stmt (exit->src));
1175
1176 if (TREE_CODE (niter) != INTEGER_CST)
1177 exit = NULL;
1178 }
1179
1180 /* We work exceptionally hard here to estimate the bound
1181 by find_loop_niter_by_eval. Be sure to keep it for future. */
1182 if (niter && TREE_CODE (niter) == INTEGER_CST)
1183 {
1184 record_niter_bound (loop, wi::to_widest (niter),
1185 exit == single_likely_exit (loop), true);
1186 }
1187
1188 /* Force re-computation of loop bounds so we can remove redundant exits. */
1189 maxiter = max_loop_iterations_int (loop);
1190
1191 if (dump_file && (dump_flags & TDF_DETAILS)
1192 && TREE_CODE (niter) == INTEGER_CST)
1193 {
1194 fprintf (dump_file, "Loop %d iterates ", loop->num);
1195 print_generic_expr (dump_file, niter, TDF_SLIM);
1196 fprintf (dump_file, " times.\n");
1197 }
1198 if (dump_file && (dump_flags & TDF_DETAILS)
1199 && maxiter >= 0)
1200 {
1201 fprintf (dump_file, "Loop %d iterates at most %i times.\n", loop->num,
1202 (int)maxiter);
1203 }
1204 if (dump_file && (dump_flags & TDF_DETAILS)
1205 && likely_max_loop_iterations_int (loop) >= 0)
1206 {
1207 fprintf (dump_file, "Loop %d likely iterates at most %i times.\n",
1208 loop->num, (int)likely_max_loop_iterations_int (loop));
1209 }
1210
1211 /* Remove exits that are known to be never taken based on loop bound.
1212 Needs to be called after compilation of max_loop_iterations_int that
1213 populates the loop bounds. */
1214 modified |= remove_redundant_iv_tests (loop);
1215
1216 if (try_unroll_loop_completely (loop, exit, niter, ul, maxiter, locus,
1217 allow_peel))
1218 return true;
1219
1220 if (create_iv
1221 && niter && !chrec_contains_undetermined (niter)
1222 && exit && just_once_each_iteration_p (loop, exit->src))
1223 create_canonical_iv (loop, exit, niter);
1224
1225 if (ul == UL_ALL)
1226 modified |= try_peel_loop (loop, exit, niter, maxiter);
1227
1228 return modified;
1229}
1230
1231/* The main entry point of the pass. Adds canonical induction variables
1232 to the suitable loops. */
1233
1234unsigned int
1235canonicalize_induction_variables (void)
1236{
1237 struct loop *loop;
1238 bool changed = false;
1239 bool irred_invalidated = false;
1240 bitmap loop_closed_ssa_invalidated = BITMAP_ALLOC (NULL);
1241
1242 estimate_numbers_of_iterations (cfun);
1243
1244 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1245 {
1246 changed |= canonicalize_loop_induction_variables (loop,
1247 true, UL_SINGLE_ITER,
1248 true, false);
1249 }
1250 gcc_assert (!need_ssa_update_p (cfun));
1251
1252 unloop_loops (loop_closed_ssa_invalidated, &irred_invalidated);
1253 if (irred_invalidated
1254 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1255 mark_irreducible_loops ();
1256
1257 /* Clean up the information about numbers of iterations, since brute force
1258 evaluation could reveal new information. */
1259 free_numbers_of_iterations_estimates (cfun);
1260 scev_reset ();
1261
1262 if (!bitmap_empty_p (loop_closed_ssa_invalidated))
1263 {
1264 gcc_checking_assert (loops_state_satisfies_p (LOOP_CLOSED_SSA));
1265 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1266 }
1267 BITMAP_FREE (loop_closed_ssa_invalidated);
1268
1269 if (changed)
1270 return TODO_cleanup_cfg;
1271 return 0;
1272}
1273
1274/* Propagate constant SSA_NAMEs defined in basic block BB. */
1275
1276static void
1277propagate_constants_for_unrolling (basic_block bb)
1278{
1279 /* Look for degenerate PHI nodes with constant argument. */
1280 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
1281 {
1282 gphi *phi = gsi.phi ();
1283 tree result = gimple_phi_result (phi);
1284 tree arg = gimple_phi_arg_def (phi, 0);
1285
1286 if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (result)
1287 && gimple_phi_num_args (phi) == 1
1288 && CONSTANT_CLASS_P (arg))
1289 {
1290 replace_uses_by (result, arg);
1291 gsi_remove (&gsi, true);
1292 release_ssa_name (result);
1293 }
1294 else
1295 gsi_next (&gsi);
1296 }
1297
1298 /* Look for assignments to SSA names with constant RHS. */
1299 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
1300 {
1301 gimple *stmt = gsi_stmt (gsi);
1302 tree lhs;
1303
1304 if (is_gimple_assign (stmt)
1305 && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_constant
1306 && (lhs = gimple_assign_lhs (stmt), TREE_CODE (lhs) == SSA_NAME)
1307 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1308 {
1309 replace_uses_by (lhs, gimple_assign_rhs1 (stmt));
1310 gsi_remove (&gsi, true);
1311 release_ssa_name (lhs);
1312 }
1313 else
1314 gsi_next (&gsi);
1315 }
1316}
1317
1318/* Process loops from innermost to outer, stopping at the innermost
1319 loop we unrolled. */
1320
1321static bool
1322tree_unroll_loops_completely_1 (bool may_increase_size, bool unroll_outer,
1323 bitmap father_bbs, struct loop *loop)
1324{
1325 struct loop *loop_father;
1326 bool changed = false;
1327 struct loop *inner;
1328 enum unroll_level ul;
1329
1330 /* Process inner loops first. */
1331 for (inner = loop->inner; inner != NULL; inner = inner->next)
1332 changed |= tree_unroll_loops_completely_1 (may_increase_size,
1333 unroll_outer, father_bbs,
1334 inner);
1335
1336 /* If we changed an inner loop we cannot process outer loops in this
1337 iteration because SSA form is not up-to-date. Continue with
1338 siblings of outer loops instead. */
1339 if (changed)
1340 return true;
1341
1342 /* Don't unroll #pragma omp simd loops until the vectorizer
1343 attempts to vectorize those. */
1344 if (loop->force_vectorize)
1345 return false;
1346
1347 /* Try to unroll this loop. */
1348 loop_father = loop_outer (loop);
1349 if (!loop_father)
1350 return false;
1351
1352 if (loop->unroll > 1)
1353 ul = UL_ALL;
1354 else if (may_increase_size && optimize_loop_nest_for_speed_p (loop)
1355 /* Unroll outermost loops only if asked to do so or they do
1356 not cause code growth. */
1357 && (unroll_outer || loop_outer (loop_father)))
1358 ul = UL_ALL;
1359 else
1360 ul = UL_NO_GROWTH;
1361
1362 if (canonicalize_loop_induction_variables
1363 (loop, false, ul, !flag_tree_loop_ivcanon, unroll_outer))
1364 {
1365 /* If we'll continue unrolling, we need to propagate constants
1366 within the new basic blocks to fold away induction variable
1367 computations; otherwise, the size might blow up before the
1368 iteration is complete and the IR eventually cleaned up. */
1369 if (loop_outer (loop_father))
1370 bitmap_set_bit (father_bbs, loop_father->header->index);
1371
1372 return true;
1373 }
1374
1375 return false;
1376}
1377
1378/* Unroll LOOPS completely if they iterate just few times. Unless
1379 MAY_INCREASE_SIZE is true, perform the unrolling only if the
1380 size of the code does not increase. */
1381
1382static unsigned int
1383tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)
1384{
1385 bitmap father_bbs = BITMAP_ALLOC (NULL);
1386 bool changed;
1387 int iteration = 0;
1388 bool irred_invalidated = false;
1389
1390 estimate_numbers_of_iterations (cfun);
1391
1392 do
1393 {
1394 changed = false;
1395 bitmap loop_closed_ssa_invalidated = NULL;
1396
1397 if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
1398 loop_closed_ssa_invalidated = BITMAP_ALLOC (NULL);
1399
1400 free_numbers_of_iterations_estimates (cfun);
1401 estimate_numbers_of_iterations (cfun);
1402
1403 changed = tree_unroll_loops_completely_1 (may_increase_size,
1404 unroll_outer, father_bbs,
1405 current_loops->tree_root);
1406 if (changed)
1407 {
1408 unsigned i;
1409
1410 unloop_loops (loop_closed_ssa_invalidated, &irred_invalidated);
1411
1412 /* We can not use TODO_update_ssa_no_phi because VOPS gets confused. */
1413 if (loop_closed_ssa_invalidated
1414 && !bitmap_empty_p (loop_closed_ssa_invalidated))
1415 rewrite_into_loop_closed_ssa (loop_closed_ssa_invalidated,
1416 TODO_update_ssa);
1417 else
1418 update_ssa (TODO_update_ssa);
1419
1420 /* father_bbs is a bitmap of loop father header BB indices.
1421 Translate that to what non-root loops these BBs belong to now. */
1422 bitmap_iterator bi;
1423 bitmap fathers = BITMAP_ALLOC (NULL);
1424 EXECUTE_IF_SET_IN_BITMAP (father_bbs, 0, i, bi)
1425 {
1426 basic_block unrolled_loop_bb = BASIC_BLOCK_FOR_FN (cfun, i);
1427 if (! unrolled_loop_bb)
1428 continue;
1429 if (loop_outer (unrolled_loop_bb->loop_father))
1430 bitmap_set_bit (fathers,
1431 unrolled_loop_bb->loop_father->num);
1432 }
1433 bitmap_clear (father_bbs);
1434 /* Propagate the constants within the new basic blocks. */
1435 EXECUTE_IF_SET_IN_BITMAP (fathers, 0, i, bi)
1436 {
1437 loop_p father = get_loop (cfun, i);
1438 basic_block *body = get_loop_body_in_dom_order (father);
1439 for (unsigned j = 0; j < father->num_nodes; j++)
1440 propagate_constants_for_unrolling (body[j]);
1441 free (body);
1442 }
1443 BITMAP_FREE (fathers);
1444
1445 /* This will take care of removing completely unrolled loops
1446 from the loop structures so we can continue unrolling now
1447 innermost loops. */
1448 if (cleanup_tree_cfg ())
1449 update_ssa (TODO_update_ssa_only_virtuals);
1450
1451 /* Clean up the information about numbers of iterations, since
1452 complete unrolling might have invalidated it. */
1453 scev_reset ();
1454 if (flag_checking && loops_state_satisfies_p (LOOP_CLOSED_SSA))
1455 verify_loop_closed_ssa (true);
1456 }
1457 if (loop_closed_ssa_invalidated)
1458 BITMAP_FREE (loop_closed_ssa_invalidated);
1459 }
1460 while (changed
1461 && ++iteration <= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS));
1462
1463 BITMAP_FREE (father_bbs);
1464
1465 if (irred_invalidated
1466 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1467 mark_irreducible_loops ();
1468
1469 return 0;
1470}
1471
1472/* Canonical induction variable creation pass. */
1473
1474namespace {
1475
1476const pass_data pass_data_iv_canon =
1477{
1478 GIMPLE_PASS, /* type */
1479 "ivcanon", /* name */
1480 OPTGROUP_LOOP, /* optinfo_flags */
1481 TV_TREE_LOOP_IVCANON, /* tv_id */
1482 ( PROP_cfg | PROP_ssa ), /* properties_required */
1483 0, /* properties_provided */
1484 0, /* properties_destroyed */
1485 0, /* todo_flags_start */
1486 0, /* todo_flags_finish */
1487};
1488
1489class pass_iv_canon : public gimple_opt_pass
1490{
1491public:
1492 pass_iv_canon (gcc::context *ctxt)
1493 : gimple_opt_pass (pass_data_iv_canon, ctxt)
1494 {}
1495
1496 /* opt_pass methods: */
1497 virtual bool gate (function *) { return flag_tree_loop_ivcanon != 0; }
1498 virtual unsigned int execute (function *fun);
1499
1500}; // class pass_iv_canon
1501
1502unsigned int
1503pass_iv_canon::execute (function *fun)
1504{
1505 if (number_of_loops (fun) <= 1)
1506 return 0;
1507
1508 return canonicalize_induction_variables ();
1509}
1510
1511} // anon namespace
1512
1513gimple_opt_pass *
1514make_pass_iv_canon (gcc::context *ctxt)
1515{
1516 return new pass_iv_canon (ctxt);
1517}
1518
1519/* Complete unrolling of loops. */
1520
1521namespace {
1522
1523const pass_data pass_data_complete_unroll =
1524{
1525 GIMPLE_PASS, /* type */
1526 "cunroll", /* name */
1527 OPTGROUP_LOOP, /* optinfo_flags */
1528 TV_COMPLETE_UNROLL, /* tv_id */
1529 ( PROP_cfg | PROP_ssa ), /* properties_required */
1530 0, /* properties_provided */
1531 0, /* properties_destroyed */
1532 0, /* todo_flags_start */
1533 0, /* todo_flags_finish */
1534};
1535
1536class pass_complete_unroll : public gimple_opt_pass
1537{
1538public:
1539 pass_complete_unroll (gcc::context *ctxt)
1540 : gimple_opt_pass (pass_data_complete_unroll, ctxt)
1541 {}
1542
1543 /* opt_pass methods: */
1544 virtual unsigned int execute (function *);
1545
1546}; // class pass_complete_unroll
1547
1548unsigned int
1549pass_complete_unroll::execute (function *fun)
1550{
1551 if (number_of_loops (fun) <= 1)
1552 return 0;
1553
1554 /* If we ever decide to run loop peeling more than once, we will need to
1555 track loops already peeled in loop structures themselves to avoid
1556 re-peeling the same loop multiple times. */
1557 if (flag_peel_loops)
1558 peeled_loops = BITMAP_ALLOC (NULL);
1559 unsigned int val = tree_unroll_loops_completely (flag_unroll_loops
1560 || flag_peel_loops
1561 || optimize >= 3, true);
1562 if (peeled_loops)
1563 {
1564 BITMAP_FREE (peeled_loops);
1565 peeled_loops = NULL;
1566 }
1567 return val;
1568}
1569
1570} // anon namespace
1571
1572gimple_opt_pass *
1573make_pass_complete_unroll (gcc::context *ctxt)
1574{
1575 return new pass_complete_unroll (ctxt);
1576}
1577
1578/* Complete unrolling of inner loops. */
1579
1580namespace {
1581
1582const pass_data pass_data_complete_unrolli =
1583{
1584 GIMPLE_PASS, /* type */
1585 "cunrolli", /* name */
1586 OPTGROUP_LOOP, /* optinfo_flags */
1587 TV_COMPLETE_UNROLL, /* tv_id */
1588 ( PROP_cfg | PROP_ssa ), /* properties_required */
1589 0, /* properties_provided */
1590 0, /* properties_destroyed */
1591 0, /* todo_flags_start */
1592 0, /* todo_flags_finish */
1593};
1594
1595class pass_complete_unrolli : public gimple_opt_pass
1596{
1597public:
1598 pass_complete_unrolli (gcc::context *ctxt)
1599 : gimple_opt_pass (pass_data_complete_unrolli, ctxt)
1600 {}
1601
1602 /* opt_pass methods: */
1603 virtual bool gate (function *) { return optimize >= 2; }
1604 virtual unsigned int execute (function *);
1605
1606}; // class pass_complete_unrolli
1607
1608unsigned int
1609pass_complete_unrolli::execute (function *fun)
1610{
1611 unsigned ret = 0;
1612
1613 loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
1614 if (number_of_loops (fun) > 1)
1615 {
1616 scev_initialize ();
1617 ret = tree_unroll_loops_completely (optimize >= 3, false);
1618 scev_finalize ();
1619 }
1620 loop_optimizer_finalize ();
1621
1622 return ret;
1623}
1624
1625} // anon namespace
1626
1627gimple_opt_pass *
1628make_pass_complete_unrolli (gcc::context *ctxt)
1629{
1630 return new pass_complete_unrolli (ctxt);
1631}
1632
1633
1634