1 /* Induction variable canonicalization and loop peeling.
2 Copyright (C) 2004-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This pass detects the loops that iterate a constant number of times,
21 adds a canonical induction variable (step -1, tested against 0)
22 and replaces the exit test. This enables the less powerful rtl
23 level analysis to use this information.
25 This might spoil the code in some cases (by increasing register pressure).
26 Note that in the case the new variable is not needed, ivopts will get rid
27 of it, so it might only be a problem when there are no other linear induction
28 variables. In that case the created optimization possibilities are likely
31 Additionally in case we detect that it is beneficial to unroll the
32 loop completely, we do it right here to expose the optimization
33 possibilities to the following passes. */
37 #include "coretypes.h"
41 #include "basic-block.h"
42 #include "gimple-pretty-print.h"
45 #include "tree-pass.h"
46 #include "tree-chrec.h"
47 #include "tree-scalar-evolution.h"
50 #include "tree-inline.h"
52 #include "tree-cfgcleanup.h"
54 /* Specifies types of loops that may be unrolled. */
58 UL_SINGLE_ITER
, /* Only loops that exit immediately in the first
60 UL_NO_GROWTH
, /* Only loops whose unrolling will not cause increase
62 UL_ALL
/* All suitable loops. */
65 /* Adds a canonical induction variable to LOOP iterating NITER times. EXIT
66 is the exit edge whose condition is replaced. */
69 create_canonical_iv (struct loop
*loop
, edge exit
, tree niter
)
74 gimple_stmt_iterator incr_at
;
77 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
79 fprintf (dump_file
, "Added canonical iv to loop %d, ", loop
->num
);
80 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
81 fprintf (dump_file
, " iterations.\n");
84 cond
= last_stmt (exit
->src
);
85 in
= EDGE_SUCC (exit
->src
, 0);
87 in
= EDGE_SUCC (exit
->src
, 1);
89 /* Note that we do not need to worry about overflows, since
90 type of niter is always unsigned and all comparisons are
91 just for equality/nonequality -- i.e. everything works
92 with a modulo arithmetics. */
94 type
= TREE_TYPE (niter
);
95 niter
= fold_build2 (PLUS_EXPR
, type
,
97 build_int_cst (type
, 1));
98 incr_at
= gsi_last_bb (in
->src
);
100 build_int_cst (type
, -1),
102 &incr_at
, false, NULL
, &var
);
104 cmp
= (exit
->flags
& EDGE_TRUE_VALUE
) ? EQ_EXPR
: NE_EXPR
;
105 gimple_cond_set_code (cond
, cmp
);
106 gimple_cond_set_lhs (cond
, var
);
107 gimple_cond_set_rhs (cond
, build_int_cst (type
, 0));
111 /* Describe size of loop as detected by tree_estimate_loop_size. */
114 /* Number of instructions in the loop. */
117 /* Number of instructions that will be likely optimized out in
118 peeled iterations of loop (i.e. computation based on induction
119 variable where induction variable starts at known constant.) */
120 int eliminated_by_peeling
;
122 /* Same statistics for last iteration of loop: it is smaller because
123 instructions after exit are not executed. */
125 int last_iteration_eliminated_by_peeling
;
127 /* If some IV computation will become constant. */
130 /* Number of call stmts that are not a builtin and are pure or const
131 present on the hot path. */
132 int num_pure_calls_on_hot_path
;
133 /* Number of call stmts that are not a builtin and are not pure nor const
134 present on the hot path. */
135 int num_non_pure_calls_on_hot_path
;
136 /* Number of statements other than calls in the loop. */
137 int non_call_stmts_on_hot_path
;
138 /* Number of branches seen on the hot path. */
139 int num_branches_on_hot_path
;
142 /* Return true if OP in STMT will be constant after peeling LOOP. */
145 constant_after_peeling (tree op
, gimple stmt
, struct loop
*loop
)
149 if (is_gimple_min_invariant (op
))
152 /* We can still fold accesses to constant arrays when index is known. */
153 if (TREE_CODE (op
) != SSA_NAME
)
157 /* First make fast look if we see constant array inside. */
158 while (handled_component_p (base
))
159 base
= TREE_OPERAND (base
, 0);
161 && ctor_for_folding (base
) != error_mark_node
)
162 || CONSTANT_CLASS_P (base
))
164 /* If so, see if we understand all the indices. */
166 while (handled_component_p (base
))
168 if (TREE_CODE (base
) == ARRAY_REF
169 && !constant_after_peeling (TREE_OPERAND (base
, 1), stmt
, loop
))
171 base
= TREE_OPERAND (base
, 0);
178 /* Induction variables are constants. */
179 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op
, &iv
, false))
181 if (!is_gimple_min_invariant (iv
.base
))
183 if (!is_gimple_min_invariant (iv
.step
))
188 /* Computes an estimated number of insns in LOOP.
189 EXIT (if non-NULL) is an exite edge that will be eliminated in all but last
190 iteration of the loop.
191 EDGE_TO_CANCEL (if non-NULL) is an non-exit edge eliminated in the last iteration
193 Return results in SIZE, estimate benefits for complete unrolling exiting by EXIT.
194 Stop estimating after UPPER_BOUND is met. Return true in this case. */
197 tree_estimate_loop_size (struct loop
*loop
, edge exit
, edge edge_to_cancel
, struct loop_size
*size
,
200 basic_block
*body
= get_loop_body (loop
);
201 gimple_stmt_iterator gsi
;
204 vec
<basic_block
> path
= get_loop_hot_path (loop
);
207 size
->eliminated_by_peeling
= 0;
208 size
->last_iteration
= 0;
209 size
->last_iteration_eliminated_by_peeling
= 0;
210 size
->num_pure_calls_on_hot_path
= 0;
211 size
->num_non_pure_calls_on_hot_path
= 0;
212 size
->non_call_stmts_on_hot_path
= 0;
213 size
->num_branches_on_hot_path
= 0;
214 size
->constant_iv
= 0;
216 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
217 fprintf (dump_file
, "Estimating sizes for loop %i\n", loop
->num
);
218 for (i
= 0; i
< loop
->num_nodes
; i
++)
220 if (edge_to_cancel
&& body
[i
] != edge_to_cancel
->src
221 && dominated_by_p (CDI_DOMINATORS
, body
[i
], edge_to_cancel
->src
))
225 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
226 fprintf (dump_file
, " BB: %i, after_exit: %i\n", body
[i
]->index
, after_exit
);
228 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
230 gimple stmt
= gsi_stmt (gsi
);
231 int num
= estimate_num_insns (stmt
, &eni_size_weights
);
232 bool likely_eliminated
= false;
233 bool likely_eliminated_last
= false;
234 bool likely_eliminated_peeled
= false;
236 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
238 fprintf (dump_file
, " size: %3i ", num
);
239 print_gimple_stmt (dump_file
, gsi_stmt (gsi
), 0, 0);
242 /* Look for reasons why we might optimize this stmt away. */
244 if (gimple_has_side_effects (stmt
))
246 /* Exit conditional. */
247 else if (exit
&& body
[i
] == exit
->src
248 && stmt
== last_stmt (exit
->src
))
250 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
251 fprintf (dump_file
, " Exit condition will be eliminated "
252 "in peeled copies.\n");
253 likely_eliminated_peeled
= true;
255 else if (edge_to_cancel
&& body
[i
] == edge_to_cancel
->src
256 && stmt
== last_stmt (edge_to_cancel
->src
))
258 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
259 fprintf (dump_file
, " Exit condition will be eliminated "
261 likely_eliminated_last
= true;
263 /* Sets of IV variables */
264 else if (gimple_code (stmt
) == GIMPLE_ASSIGN
265 && constant_after_peeling (gimple_assign_lhs (stmt
), stmt
, loop
))
267 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
268 fprintf (dump_file
, " Induction variable computation will"
269 " be folded away.\n");
270 likely_eliminated
= true;
272 /* Assignments of IV variables. */
273 else if (gimple_code (stmt
) == GIMPLE_ASSIGN
274 && TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
275 && constant_after_peeling (gimple_assign_rhs1 (stmt
), stmt
, loop
)
276 && (gimple_assign_rhs_class (stmt
) != GIMPLE_BINARY_RHS
277 || constant_after_peeling (gimple_assign_rhs2 (stmt
),
280 size
->constant_iv
= true;
281 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
282 fprintf (dump_file
, " Constant expression will be folded away.\n");
283 likely_eliminated
= true;
286 else if ((gimple_code (stmt
) == GIMPLE_COND
287 && constant_after_peeling (gimple_cond_lhs (stmt
), stmt
, loop
)
288 && constant_after_peeling (gimple_cond_rhs (stmt
), stmt
, loop
))
289 || (gimple_code (stmt
) == GIMPLE_SWITCH
290 && constant_after_peeling (gimple_switch_index (stmt
), stmt
, loop
)))
292 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
293 fprintf (dump_file
, " Constant conditional.\n");
294 likely_eliminated
= true;
297 size
->overall
+= num
;
298 if (likely_eliminated
|| likely_eliminated_peeled
)
299 size
->eliminated_by_peeling
+= num
;
302 size
->last_iteration
+= num
;
303 if (likely_eliminated
|| likely_eliminated_last
)
304 size
->last_iteration_eliminated_by_peeling
+= num
;
306 if ((size
->overall
* 3 / 2 - size
->eliminated_by_peeling
307 - size
->last_iteration_eliminated_by_peeling
) > upper_bound
)
315 while (path
.length ())
317 basic_block bb
= path
.pop ();
318 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
320 gimple stmt
= gsi_stmt (gsi
);
321 if (gimple_code (stmt
) == GIMPLE_CALL
)
323 int flags
= gimple_call_flags (stmt
);
324 tree decl
= gimple_call_fndecl (stmt
);
326 if (decl
&& DECL_IS_BUILTIN (decl
)
327 && is_inexpensive_builtin (decl
))
329 else if (flags
& (ECF_PURE
| ECF_CONST
))
330 size
->num_pure_calls_on_hot_path
++;
332 size
->num_non_pure_calls_on_hot_path
++;
333 size
->num_branches_on_hot_path
++;
335 else if (gimple_code (stmt
) != GIMPLE_CALL
336 && gimple_code (stmt
) != GIMPLE_DEBUG
)
337 size
->non_call_stmts_on_hot_path
++;
338 if (((gimple_code (stmt
) == GIMPLE_COND
339 && (!constant_after_peeling (gimple_cond_lhs (stmt
), stmt
, loop
)
340 || constant_after_peeling (gimple_cond_rhs (stmt
), stmt
, loop
)))
341 || (gimple_code (stmt
) == GIMPLE_SWITCH
342 && !constant_after_peeling (gimple_switch_index (stmt
), stmt
, loop
)))
343 && (!exit
|| bb
!= exit
->src
))
344 size
->num_branches_on_hot_path
++;
348 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
349 fprintf (dump_file
, "size: %i-%i, last_iteration: %i-%i\n", size
->overall
,
350 size
->eliminated_by_peeling
, size
->last_iteration
,
351 size
->last_iteration_eliminated_by_peeling
);
357 /* Estimate number of insns of completely unrolled loop.
358 It is (NUNROLL + 1) * size of loop body with taking into account
359 the fact that in last copy everything after exit conditional
360 is dead and that some instructions will be eliminated after
363 Loop body is likely going to simplify further, this is difficult
364 to guess, we just decrease the result by 1/3. */
366 static unsigned HOST_WIDE_INT
367 estimated_unrolled_size (struct loop_size
*size
,
368 unsigned HOST_WIDE_INT nunroll
)
370 HOST_WIDE_INT unr_insns
= ((nunroll
)
371 * (HOST_WIDE_INT
) (size
->overall
372 - size
->eliminated_by_peeling
));
375 unr_insns
+= size
->last_iteration
- size
->last_iteration_eliminated_by_peeling
;
377 unr_insns
= unr_insns
* 2 / 3;
384 /* Loop LOOP is known to not loop. See if there is an edge in the loop
385 body that can be remove to make the loop to always exit and at
386 the same time it does not make any code potentially executed
387 during the last iteration dead.
389 After complette unrolling we still may get rid of the conditional
390 on the exit in the last copy even if we have no idea what it does.
391 This is quite common case for loops of form
397 Here we prove the loop to iterate 5 times but we do not know
398 it from induction variable.
400 For now we handle only simple case where there is exit condition
401 just before the latch block and the latch block contains no statements
402 with side effect that may otherwise terminate the execution of loop
403 (such as by EH or by terminating the program or longjmp).
405 In the general case we may want to cancel the paths leading to statements
406 loop-niter identified as having undefined effect in the last iteration.
407 The other cases are hopefully rare and will be cleaned up later. */
410 loop_edge_to_cancel (struct loop
*loop
)
415 gimple_stmt_iterator gsi
;
417 /* We want only one predecestor of the loop. */
418 if (EDGE_COUNT (loop
->latch
->preds
) > 1)
421 exits
= get_loop_exit_edges (loop
);
423 FOR_EACH_VEC_ELT (exits
, i
, edge_to_cancel
)
425 /* Find the other edge than the loop exit
426 leaving the conditoinal. */
427 if (EDGE_COUNT (edge_to_cancel
->src
->succs
) != 2)
429 if (EDGE_SUCC (edge_to_cancel
->src
, 0) == edge_to_cancel
)
430 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 1);
432 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 0);
434 /* We only can handle conditionals. */
435 if (!(edge_to_cancel
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
438 /* We should never have conditionals in the loop latch. */
439 gcc_assert (edge_to_cancel
->dest
!= loop
->header
);
441 /* Check that it leads to loop latch. */
442 if (edge_to_cancel
->dest
!= loop
->latch
)
447 /* Verify that the code in loop latch does nothing that may end program
448 execution without really reaching the exit. This may include
449 non-pure/const function calls, EH statements, volatile ASMs etc. */
450 for (gsi
= gsi_start_bb (loop
->latch
); !gsi_end_p (gsi
); gsi_next (&gsi
))
451 if (gimple_has_side_effects (gsi_stmt (gsi
)))
453 return edge_to_cancel
;
459 /* Remove all tests for exits that are known to be taken after LOOP was
460 peeled NPEELED times. Put gcc_unreachable before every statement
461 known to not be executed. */
464 remove_exits_and_undefined_stmts (struct loop
*loop
, unsigned int npeeled
)
466 struct nb_iter_bound
*elt
;
467 bool changed
= false;
469 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
471 /* If statement is known to be undefined after peeling, turn it
472 into unreachable (or trap when debugging experience is supposed
475 && wi::ltu_p (elt
->bound
, npeeled
))
477 gimple_stmt_iterator gsi
= gsi_for_stmt (elt
->stmt
);
478 gimple stmt
= gimple_build_call
479 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
), 0);
481 gimple_set_location (stmt
, gimple_location (elt
->stmt
));
482 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
484 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
486 fprintf (dump_file
, "Forced statement unreachable: ");
487 print_gimple_stmt (dump_file
, elt
->stmt
, 0, 0);
490 /* If we know the exit will be taken after peeling, update. */
491 else if (elt
->is_exit
492 && wi::leu_p (elt
->bound
, npeeled
))
494 basic_block bb
= gimple_bb (elt
->stmt
);
495 edge exit_edge
= EDGE_SUCC (bb
, 0);
497 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
499 fprintf (dump_file
, "Forced exit to be taken: ");
500 print_gimple_stmt (dump_file
, elt
->stmt
, 0, 0);
502 if (!loop_exit_edge_p (loop
, exit_edge
))
503 exit_edge
= EDGE_SUCC (bb
, 1);
504 gcc_checking_assert (loop_exit_edge_p (loop
, exit_edge
));
505 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
506 gimple_cond_make_true (elt
->stmt
);
508 gimple_cond_make_false (elt
->stmt
);
509 update_stmt (elt
->stmt
);
516 /* Remove all exits that are known to be never taken because of the loop bound
520 remove_redundant_iv_tests (struct loop
*loop
)
522 struct nb_iter_bound
*elt
;
523 bool changed
= false;
525 if (!loop
->any_upper_bound
)
527 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
529 /* Exit is pointless if it won't be taken before loop reaches
531 if (elt
->is_exit
&& loop
->any_upper_bound
532 && wi::ltu_p (loop
->nb_iterations_upper_bound
, elt
->bound
))
534 basic_block bb
= gimple_bb (elt
->stmt
);
535 edge exit_edge
= EDGE_SUCC (bb
, 0);
536 struct tree_niter_desc niter
;
538 if (!loop_exit_edge_p (loop
, exit_edge
))
539 exit_edge
= EDGE_SUCC (bb
, 1);
541 /* Only when we know the actual number of iterations, not
542 just a bound, we can remove the exit. */
543 if (!number_of_iterations_exit (loop
, exit_edge
,
544 &niter
, false, false)
545 || !integer_onep (niter
.assumptions
)
546 || !integer_zerop (niter
.may_be_zero
)
548 || TREE_CODE (niter
.niter
) != INTEGER_CST
549 || !wi::ltu_p (loop
->nb_iterations_upper_bound
,
550 wi::to_widest (niter
.niter
)))
553 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
555 fprintf (dump_file
, "Removed pointless exit: ");
556 print_gimple_stmt (dump_file
, elt
->stmt
, 0, 0);
558 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
559 gimple_cond_make_false (elt
->stmt
);
561 gimple_cond_make_true (elt
->stmt
);
562 update_stmt (elt
->stmt
);
569 /* Stores loops that will be unlooped after we process whole loop tree. */
570 static vec
<loop_p
> loops_to_unloop
;
571 static vec
<int> loops_to_unloop_nunroll
;
573 /* Cancel all fully unrolled loops by putting __builtin_unreachable
575 We do it after all unrolling since unlooping moves basic blocks
576 across loop boundaries trashing loop closed SSA form as well
577 as SCEV info needed to be intact during unrolling.
579 IRRED_INVALIDATED is used to bookkeep if information about
580 irreducible regions may become invalid as a result
581 of the transformation.
582 LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case
583 when we need to go into loop closed SSA form. */
586 unloop_loops (bitmap loop_closed_ssa_invalidated
,
587 bool *irred_invalidated
)
589 while (loops_to_unloop
.length ())
591 struct loop
*loop
= loops_to_unloop
.pop ();
592 int n_unroll
= loops_to_unloop_nunroll
.pop ();
593 basic_block latch
= loop
->latch
;
594 edge latch_edge
= loop_latch_edge (loop
);
595 int flags
= latch_edge
->flags
;
596 location_t locus
= latch_edge
->goto_locus
;
598 gimple_stmt_iterator gsi
;
600 remove_exits_and_undefined_stmts (loop
, n_unroll
);
602 /* Unloop destroys the latch edge. */
603 unloop (loop
, irred_invalidated
, loop_closed_ssa_invalidated
);
605 /* Create new basic block for the latch edge destination and wire
607 stmt
= gimple_build_call (builtin_decl_implicit (BUILT_IN_UNREACHABLE
), 0);
608 latch_edge
= make_edge (latch
, create_basic_block (NULL
, NULL
, latch
), flags
);
609 latch_edge
->probability
= 0;
610 latch_edge
->count
= 0;
611 latch_edge
->flags
|= flags
;
612 latch_edge
->goto_locus
= locus
;
614 latch_edge
->dest
->loop_father
= current_loops
->tree_root
;
615 latch_edge
->dest
->count
= 0;
616 latch_edge
->dest
->frequency
= 0;
617 set_immediate_dominator (CDI_DOMINATORS
, latch_edge
->dest
, latch_edge
->src
);
619 gsi
= gsi_start_bb (latch_edge
->dest
);
620 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
622 loops_to_unloop
.release ();
623 loops_to_unloop_nunroll
.release ();
626 /* Tries to unroll LOOP completely, i.e. NITER times.
627 UL determines which loops we are allowed to unroll.
628 EXIT is the exit of the loop that should be eliminated.
629 MAXITER specfy bound on number of iterations, -1 if it is
630 not known or too large for HOST_WIDE_INT. The location
631 LOCUS corresponding to the loop is used when emitting
632 a summary of the unroll to the dump file. */
635 try_unroll_loop_completely (struct loop
*loop
,
636 edge exit
, tree niter
,
637 enum unroll_level ul
,
638 HOST_WIDE_INT maxiter
,
641 unsigned HOST_WIDE_INT n_unroll
, ninsns
, max_unroll
, unr_insns
;
643 struct loop_size size
;
644 bool n_unroll_found
= false;
645 edge edge_to_cancel
= NULL
;
647 /* See if we proved number of iterations to be low constant.
649 EXIT is an edge that will be removed in all but last iteration of
652 EDGE_TO_CACNEL is an edge that will be removed from the last iteration
653 of the unrolled sequence and is expected to make the final loop not
656 If the number of execution of loop is determined by standard induction
657 variable test, then EXIT and EDGE_TO_CANCEL are the two edges leaving
659 if (tree_fits_uhwi_p (niter
))
661 n_unroll
= tree_to_uhwi (niter
);
662 n_unroll_found
= true;
663 edge_to_cancel
= EDGE_SUCC (exit
->src
, 0);
664 if (edge_to_cancel
== exit
)
665 edge_to_cancel
= EDGE_SUCC (exit
->src
, 1);
667 /* We do not know the number of iterations and thus we can not eliminate
672 /* See if we can improve our estimate by using recorded loop bounds. */
674 && (!n_unroll_found
|| (unsigned HOST_WIDE_INT
)maxiter
< n_unroll
))
677 n_unroll_found
= true;
678 /* Loop terminates before the IV variable test, so we can not
679 remove it in the last iteration. */
680 edge_to_cancel
= NULL
;
686 max_unroll
= PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
);
687 if (n_unroll
> max_unroll
)
691 edge_to_cancel
= loop_edge_to_cancel (loop
);
699 vec
<edge
> to_remove
= vNULL
;
700 if (ul
== UL_SINGLE_ITER
)
703 large
= tree_estimate_loop_size
704 (loop
, exit
, edge_to_cancel
, &size
,
705 PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
));
706 ninsns
= size
.overall
;
709 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
710 fprintf (dump_file
, "Not unrolling loop %d: it is too large.\n",
715 unr_insns
= estimated_unrolled_size (&size
, n_unroll
);
716 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
718 fprintf (dump_file
, " Loop size: %d\n", (int) ninsns
);
719 fprintf (dump_file
, " Estimated size after unrolling: %d\n",
723 /* If the code is going to shrink, we don't need to be extra cautious
724 on guessing if the unrolling is going to be profitable. */
726 /* If there is IV variable that will become constant, we save
727 one instruction in the loop prologue we do not account
729 <= ninsns
+ (size
.constant_iv
!= false))
731 /* We unroll only inner loops, because we do not consider it profitable
732 otheriwse. We still can cancel loopback edge of not rolling loop;
733 this is always a good idea. */
734 else if (ul
== UL_NO_GROWTH
)
736 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
737 fprintf (dump_file
, "Not unrolling loop %d: size would grow.\n",
741 /* Outer loops tend to be less interesting candidates for complette
742 unrolling unless we can do a lot of propagation into the inner loop
743 body. For now we disable outer loop unrolling when the code would
745 else if (loop
->inner
)
747 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
748 fprintf (dump_file
, "Not unrolling loop %d: "
749 "it is not innermost and code would grow.\n",
753 /* If there is call on a hot path through the loop, then
754 there is most probably not much to optimize. */
755 else if (size
.num_non_pure_calls_on_hot_path
)
757 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
758 fprintf (dump_file
, "Not unrolling loop %d: "
759 "contains call and code would grow.\n",
763 /* If there is pure/const call in the function, then we
764 can still optimize the unrolled loop body if it contains
765 some other interesting code than the calls and code
766 storing or cumulating the return value. */
767 else if (size
.num_pure_calls_on_hot_path
768 /* One IV increment, one test, one ivtmp store
769 and one useful stmt. That is about minimal loop
771 && (size
.non_call_stmts_on_hot_path
772 <= 3 + size
.num_pure_calls_on_hot_path
))
774 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
775 fprintf (dump_file
, "Not unrolling loop %d: "
776 "contains just pure calls and code would grow.\n",
780 /* Complette unrolling is major win when control flow is removed and
781 one big basic block is created. If the loop contains control flow
782 the optimization may still be a win because of eliminating the loop
783 overhead but it also may blow the branch predictor tables.
784 Limit number of branches on the hot path through the peeled
786 else if (size
.num_branches_on_hot_path
* (int)n_unroll
787 > PARAM_VALUE (PARAM_MAX_PEEL_BRANCHES
))
789 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
790 fprintf (dump_file
, "Not unrolling loop %d: "
791 " number of branches on hot path in the unrolled sequence"
792 " reach --param max-peel-branches limit.\n",
797 > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
))
799 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
800 fprintf (dump_file
, "Not unrolling loop %d: "
801 "(--param max-completely-peeled-insns limit reached).\n",
806 initialize_original_copy_tables ();
807 wont_exit
= sbitmap_alloc (n_unroll
+ 1);
808 bitmap_ones (wont_exit
);
809 bitmap_clear_bit (wont_exit
, 0);
811 if (!gimple_duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
814 DLTHE_FLAG_UPDATE_FREQ
815 | DLTHE_FLAG_COMPLETTE_PEEL
))
817 free_original_copy_tables ();
819 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
820 fprintf (dump_file
, "Failed to duplicate the loop\n");
824 FOR_EACH_VEC_ELT (to_remove
, i
, e
)
826 bool ok
= remove_path (e
);
830 to_remove
.release ();
832 free_original_copy_tables ();
836 /* Remove the conditional from the last copy of the loop. */
839 cond
= last_stmt (edge_to_cancel
->src
);
840 if (edge_to_cancel
->flags
& EDGE_TRUE_VALUE
)
841 gimple_cond_make_false (cond
);
843 gimple_cond_make_true (cond
);
845 /* Do not remove the path. Doing so may remove outer loop
846 and confuse bookkeeping code in tree_unroll_loops_completelly. */
849 /* Store the loop for later unlooping and exit removal. */
850 loops_to_unloop
.safe_push (loop
);
851 loops_to_unloop_nunroll
.safe_push (n_unroll
);
853 if (dump_enabled_p ())
856 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
857 "loop turned into non-loop; it never loops\n");
860 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
861 "loop with %d iterations completely unrolled",
862 (int) (n_unroll
+ 1));
864 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
,
865 " (header execution count %d)",
866 (int)loop
->header
->count
);
867 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, "\n");
871 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
874 fprintf (dump_file
, "Exit condition of peeled iterations was "
877 fprintf (dump_file
, "Last iteration exit edge was proved true.\n");
879 fprintf (dump_file
, "Latch of last iteration was marked by "
880 "__builtin_unreachable ().\n");
886 /* Adds a canonical induction variable to LOOP if suitable.
887 CREATE_IV is true if we may create a new iv. UL determines
888 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
889 to determine the number of iterations of a loop by direct evaluation.
890 Returns true if cfg is changed. */
893 canonicalize_loop_induction_variables (struct loop
*loop
,
894 bool create_iv
, enum unroll_level ul
,
899 HOST_WIDE_INT maxiter
;
900 bool modified
= false;
901 location_t locus
= UNKNOWN_LOCATION
;
903 niter
= number_of_latch_executions (loop
);
904 exit
= single_exit (loop
);
905 if (TREE_CODE (niter
) == INTEGER_CST
)
906 locus
= gimple_location (last_stmt (exit
->src
));
909 /* If the loop has more than one exit, try checking all of them
910 for # of iterations determinable through scev. */
912 niter
= find_loop_niter (loop
, &exit
);
914 /* Finally if everything else fails, try brute force evaluation. */
916 && (chrec_contains_undetermined (niter
)
917 || TREE_CODE (niter
) != INTEGER_CST
))
918 niter
= find_loop_niter_by_eval (loop
, &exit
);
921 locus
= gimple_location (last_stmt (exit
->src
));
923 if (TREE_CODE (niter
) != INTEGER_CST
)
927 /* We work exceptionally hard here to estimate the bound
928 by find_loop_niter_by_eval. Be sure to keep it for future. */
929 if (niter
&& TREE_CODE (niter
) == INTEGER_CST
)
931 record_niter_bound (loop
, wi::to_widest (niter
),
932 exit
== single_likely_exit (loop
), true);
935 /* Force re-computation of loop bounds so we can remove redundant exits. */
936 maxiter
= max_loop_iterations_int (loop
);
938 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
939 && TREE_CODE (niter
) == INTEGER_CST
)
941 fprintf (dump_file
, "Loop %d iterates ", loop
->num
);
942 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
943 fprintf (dump_file
, " times.\n");
945 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
948 fprintf (dump_file
, "Loop %d iterates at most %i times.\n", loop
->num
,
952 /* Remove exits that are known to be never taken based on loop bound.
953 Needs to be called after compilation of max_loop_iterations_int that
954 populates the loop bounds. */
955 modified
|= remove_redundant_iv_tests (loop
);
957 if (try_unroll_loop_completely (loop
, exit
, niter
, ul
, maxiter
, locus
))
961 && niter
&& !chrec_contains_undetermined (niter
)
962 && exit
&& just_once_each_iteration_p (loop
, exit
->src
))
963 create_canonical_iv (loop
, exit
, niter
);
968 /* The main entry point of the pass. Adds canonical induction variables
969 to the suitable loops. */
972 canonicalize_induction_variables (void)
976 bool changed
= false;
977 bool irred_invalidated
= false;
978 bitmap loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
980 free_numbers_of_iterations_estimates ();
981 estimate_numbers_of_iterations ();
983 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
985 changed
|= canonicalize_loop_induction_variables (loop
,
986 true, UL_SINGLE_ITER
,
989 gcc_assert (!need_ssa_update_p (cfun
));
991 unloop_loops (loop_closed_ssa_invalidated
, &irred_invalidated
);
992 if (irred_invalidated
993 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
994 mark_irreducible_loops ();
996 /* Clean up the information about numbers of iterations, since brute force
997 evaluation could reveal new information. */
1000 if (!bitmap_empty_p (loop_closed_ssa_invalidated
))
1002 gcc_checking_assert (loops_state_satisfies_p (LOOP_CLOSED_SSA
));
1003 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1005 BITMAP_FREE (loop_closed_ssa_invalidated
);
1008 return TODO_cleanup_cfg
;
1012 /* Propagate VAL into all uses of SSA_NAME. */
1015 propagate_into_all_uses (tree ssa_name
, tree val
)
1017 imm_use_iterator iter
;
1020 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, ssa_name
)
1022 gimple_stmt_iterator use_stmt_gsi
= gsi_for_stmt (use_stmt
);
1025 FOR_EACH_IMM_USE_ON_STMT (use
, iter
)
1028 if (is_gimple_assign (use_stmt
)
1029 && get_gimple_rhs_class (gimple_assign_rhs_code (use_stmt
))
1030 == GIMPLE_SINGLE_RHS
)
1032 tree rhs
= gimple_assign_rhs1 (use_stmt
);
1034 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1035 recompute_tree_invariant_for_addr_expr (rhs
);
1038 fold_stmt_inplace (&use_stmt_gsi
);
1039 update_stmt (use_stmt
);
1040 maybe_clean_or_replace_eh_stmt (use_stmt
, use_stmt
);
1044 /* Propagate constant SSA_NAMEs defined in basic block BB. */
1047 propagate_constants_for_unrolling (basic_block bb
)
1049 gimple_stmt_iterator gsi
;
1051 /* Look for degenerate PHI nodes with constant argument. */
1052 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); )
1054 gimple phi
= gsi_stmt (gsi
);
1055 tree result
= gimple_phi_result (phi
);
1056 tree arg
= gimple_phi_arg_def (phi
, 0);
1058 if (gimple_phi_num_args (phi
) == 1 && TREE_CODE (arg
) == INTEGER_CST
)
1060 propagate_into_all_uses (result
, arg
);
1061 gsi_remove (&gsi
, true);
1062 release_ssa_name (result
);
1068 /* Look for assignments to SSA names with constant RHS. */
1069 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
1071 gimple stmt
= gsi_stmt (gsi
);
1074 if (is_gimple_assign (stmt
)
1075 && gimple_assign_rhs_code (stmt
) == INTEGER_CST
1076 && (lhs
= gimple_assign_lhs (stmt
), TREE_CODE (lhs
) == SSA_NAME
)
1077 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1079 propagate_into_all_uses (lhs
, gimple_assign_rhs1 (stmt
));
1080 gsi_remove (&gsi
, true);
1081 release_ssa_name (lhs
);
1088 /* Process loops from innermost to outer, stopping at the innermost
1089 loop we unrolled. */
1092 tree_unroll_loops_completely_1 (bool may_increase_size
, bool unroll_outer
,
1093 vec
<loop_p
, va_stack
>& father_stack
,
1096 struct loop
*loop_father
;
1097 bool changed
= false;
1099 enum unroll_level ul
;
1101 /* Process inner loops first. */
1102 for (inner
= loop
->inner
; inner
!= NULL
; inner
= inner
->next
)
1103 changed
|= tree_unroll_loops_completely_1 (may_increase_size
,
1104 unroll_outer
, father_stack
,
1107 /* If we changed an inner loop we cannot process outer loops in this
1108 iteration because SSA form is not up-to-date. Continue with
1109 siblings of outer loops instead. */
1113 /* Don't unroll #pragma omp simd loops until the vectorizer
1114 attempts to vectorize those. */
1115 if (loop
->force_vect
)
1118 /* Try to unroll this loop. */
1119 loop_father
= loop_outer (loop
);
1123 if (may_increase_size
&& optimize_loop_nest_for_speed_p (loop
)
1124 /* Unroll outermost loops only if asked to do so or they do
1125 not cause code growth. */
1126 && (unroll_outer
|| loop_outer (loop_father
)))
1131 if (canonicalize_loop_induction_variables
1132 (loop
, false, ul
, !flag_tree_loop_ivcanon
))
1134 /* If we'll continue unrolling, we need to propagate constants
1135 within the new basic blocks to fold away induction variable
1136 computations; otherwise, the size might blow up before the
1137 iteration is complete and the IR eventually cleaned up. */
1138 if (loop_outer (loop_father
) && !loop_father
->aux
)
1140 father_stack
.safe_push (loop_father
);
1141 loop_father
->aux
= loop_father
;
1150 /* Unroll LOOPS completely if they iterate just few times. Unless
1151 MAY_INCREASE_SIZE is true, perform the unrolling only if the
1152 size of the code does not increase. */
1155 tree_unroll_loops_completely (bool may_increase_size
, bool unroll_outer
)
1157 vec
<loop_p
, va_stack
> father_stack
;
1160 bool irred_invalidated
= false;
1162 vec_stack_alloc (loop_p
, father_stack
, 16);
1166 bitmap loop_closed_ssa_invalidated
= NULL
;
1168 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1169 loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
1171 free_numbers_of_iterations_estimates ();
1172 estimate_numbers_of_iterations ();
1174 changed
= tree_unroll_loops_completely_1 (may_increase_size
,
1175 unroll_outer
, father_stack
,
1176 current_loops
->tree_root
);
1182 /* Be sure to skip unlooped loops while procesing father_stack
1184 FOR_EACH_VEC_ELT (loops_to_unloop
, i
, iter
)
1185 (*iter
)->aux
= NULL
;
1186 FOR_EACH_VEC_ELT (father_stack
, i
, iter
)
1189 unloop_loops (loop_closed_ssa_invalidated
, &irred_invalidated
);
1191 /* We can not use TODO_update_ssa_no_phi because VOPS gets confused. */
1192 if (loop_closed_ssa_invalidated
1193 && !bitmap_empty_p (loop_closed_ssa_invalidated
))
1194 rewrite_into_loop_closed_ssa (loop_closed_ssa_invalidated
,
1197 update_ssa (TODO_update_ssa
);
1199 /* Propagate the constants within the new basic blocks. */
1200 FOR_EACH_VEC_ELT (father_stack
, i
, iter
)
1204 basic_block
*body
= get_loop_body_in_dom_order (*iter
);
1205 for (j
= 0; j
< (*iter
)->num_nodes
; j
++)
1206 propagate_constants_for_unrolling (body
[j
]);
1208 (*iter
)->aux
= NULL
;
1210 father_stack
.truncate (0);
1212 /* This will take care of removing completely unrolled loops
1213 from the loop structures so we can continue unrolling now
1215 if (cleanup_tree_cfg ())
1216 update_ssa (TODO_update_ssa_only_virtuals
);
1218 /* Clean up the information about numbers of iterations, since
1219 complete unrolling might have invalidated it. */
1221 #ifdef ENABLE_CHECKING
1222 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1223 verify_loop_closed_ssa (true);
1226 if (loop_closed_ssa_invalidated
)
1227 BITMAP_FREE (loop_closed_ssa_invalidated
);
1230 && ++iteration
<= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS
));
1232 father_stack
.release ();
1234 if (irred_invalidated
1235 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1236 mark_irreducible_loops ();
1241 /* Canonical induction variable creation pass. */
1244 tree_ssa_loop_ivcanon (void)
1246 if (number_of_loops (cfun
) <= 1)
1249 return canonicalize_induction_variables ();
1253 gate_tree_ssa_loop_ivcanon (void)
1255 return flag_tree_loop_ivcanon
!= 0;
1260 const pass_data pass_data_iv_canon
=
1262 GIMPLE_PASS
, /* type */
1263 "ivcanon", /* name */
1264 OPTGROUP_LOOP
, /* optinfo_flags */
1265 true, /* has_gate */
1266 true, /* has_execute */
1267 TV_TREE_LOOP_IVCANON
, /* tv_id */
1268 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1269 0, /* properties_provided */
1270 0, /* properties_destroyed */
1271 0, /* todo_flags_start */
1272 0, /* todo_flags_finish */
1275 class pass_iv_canon
: public gimple_opt_pass
1278 pass_iv_canon (gcc::context
*ctxt
)
1279 : gimple_opt_pass (pass_data_iv_canon
, ctxt
)
1282 /* opt_pass methods: */
1283 bool gate () { return gate_tree_ssa_loop_ivcanon (); }
1284 unsigned int execute () { return tree_ssa_loop_ivcanon (); }
1286 }; // class pass_iv_canon
1291 make_pass_iv_canon (gcc::context
*ctxt
)
1293 return new pass_iv_canon (ctxt
);
1296 /* Complete unrolling of loops. */
1299 tree_complete_unroll (void)
1301 if (number_of_loops (cfun
) <= 1)
1304 return tree_unroll_loops_completely (flag_unroll_loops
1306 || optimize
>= 3, true);
1310 gate_tree_complete_unroll (void)
1317 const pass_data pass_data_complete_unroll
=
1319 GIMPLE_PASS
, /* type */
1320 "cunroll", /* name */
1321 OPTGROUP_LOOP
, /* optinfo_flags */
1322 true, /* has_gate */
1323 true, /* has_execute */
1324 TV_COMPLETE_UNROLL
, /* tv_id */
1325 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1326 0, /* properties_provided */
1327 0, /* properties_destroyed */
1328 0, /* todo_flags_start */
1329 0, /* todo_flags_finish */
1332 class pass_complete_unroll
: public gimple_opt_pass
1335 pass_complete_unroll (gcc::context
*ctxt
)
1336 : gimple_opt_pass (pass_data_complete_unroll
, ctxt
)
1339 /* opt_pass methods: */
1340 bool gate () { return gate_tree_complete_unroll (); }
1341 unsigned int execute () { return tree_complete_unroll (); }
1343 }; // class pass_complete_unroll
1348 make_pass_complete_unroll (gcc::context
*ctxt
)
1350 return new pass_complete_unroll (ctxt
);
1353 /* Complete unrolling of inner loops. */
1356 tree_complete_unroll_inner (void)
1360 loop_optimizer_init (LOOPS_NORMAL
1361 | LOOPS_HAVE_RECORDED_EXITS
);
1362 if (number_of_loops (cfun
) > 1)
1365 ret
= tree_unroll_loops_completely (optimize
>= 3, false);
1366 free_numbers_of_iterations_estimates ();
1369 loop_optimizer_finalize ();
1375 gate_tree_complete_unroll_inner (void)
1377 return optimize
>= 2;
1382 const pass_data pass_data_complete_unrolli
=
1384 GIMPLE_PASS
, /* type */
1385 "cunrolli", /* name */
1386 OPTGROUP_LOOP
, /* optinfo_flags */
1387 true, /* has_gate */
1388 true, /* has_execute */
1389 TV_COMPLETE_UNROLL
, /* tv_id */
1390 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1391 0, /* properties_provided */
1392 0, /* properties_destroyed */
1393 0, /* todo_flags_start */
1394 TODO_verify_flow
, /* todo_flags_finish */
1397 class pass_complete_unrolli
: public gimple_opt_pass
1400 pass_complete_unrolli (gcc::context
*ctxt
)
1401 : gimple_opt_pass (pass_data_complete_unrolli
, ctxt
)
1404 /* opt_pass methods: */
1405 bool gate () { return gate_tree_complete_unroll_inner (); }
1406 unsigned int execute () { return tree_complete_unroll_inner (); }
1408 }; // class pass_complete_unrolli
1413 make_pass_complete_unrolli (gcc::context
*ctxt
)
1415 return new pass_complete_unrolli (ctxt
);