1 /* Induction variable canonicalization and loop peeling.
2 Copyright (C) 2004, 2005, 2007, 2008, 2010, 2012
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This pass detects the loops that iterate a constant number of times,
22 adds a canonical induction variable (step -1, tested against 0)
23 and replaces the exit test. This enables the less powerful rtl
24 level analysis to use this information.
26 This might spoil the code in some cases (by increasing register pressure).
27 Note that in the case the new variable is not needed, ivopts will get rid
28 of it, so it might only be a problem when there are no other linear induction
29 variables. In that case the created optimization possibilities are likely
32 Additionally in case we detect that it is beneficial to unroll the
33 loop completely, we do it right here to expose the optimization
34 possibilities to the following passes. */
38 #include "coretypes.h"
42 #include "basic-block.h"
43 #include "gimple-pretty-print.h"
44 #include "tree-flow.h"
46 #include "tree-pass.h"
47 #include "tree-chrec.h"
48 #include "tree-scalar-evolution.h"
51 #include "tree-inline.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 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */
114 tree_num_loop_insns (struct loop
*loop
, eni_weights
*weights
)
116 basic_block
*body
= get_loop_body (loop
);
117 gimple_stmt_iterator gsi
;
118 unsigned size
= 0, i
;
120 for (i
= 0; i
< loop
->num_nodes
; i
++)
121 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
122 size
+= estimate_num_insns (gsi_stmt (gsi
), weights
);
128 /* Describe size of loop as detected by tree_estimate_loop_size. */
131 /* Number of instructions in the loop. */
134 /* Number of instructions that will be likely optimized out in
135 peeled iterations of loop (i.e. computation based on induction
136 variable where induction variable starts at known constant.) */
137 int eliminated_by_peeling
;
139 /* Same statistics for last iteration of loop: it is smaller because
140 instructions after exit are not executed. */
142 int last_iteration_eliminated_by_peeling
;
144 /* If some IV computation will become constant. */
147 /* Number of call stmts that are not a builtin and are pure or const
148 present on the hot path. */
149 int num_pure_calls_on_hot_path
;
150 /* Number of call stmts that are not a builtin and are not pure nor const
151 present on the hot path. */
152 int num_non_pure_calls_on_hot_path
;
153 /* Number of statements other than calls in the loop. */
154 int non_call_stmts_on_hot_path
;
155 /* Number of branches seen on the hot path. */
156 int num_branches_on_hot_path
;
159 /* Return true if OP in STMT will be constant after peeling LOOP. */
162 constant_after_peeling (tree op
, gimple stmt
, struct loop
*loop
)
166 if (is_gimple_min_invariant (op
))
169 /* We can still fold accesses to constant arrays when index is known. */
170 if (TREE_CODE (op
) != SSA_NAME
)
174 /* First make fast look if we see constant array inside. */
175 while (handled_component_p (base
))
176 base
= TREE_OPERAND (base
, 0);
178 && const_value_known_p (base
))
179 || CONSTANT_CLASS_P (base
))
181 /* If so, see if we understand all the indices. */
183 while (handled_component_p (base
))
185 if (TREE_CODE (base
) == ARRAY_REF
186 && !constant_after_peeling (TREE_OPERAND (base
, 1), stmt
, loop
))
188 base
= TREE_OPERAND (base
, 0);
195 /* Induction variables are constants. */
196 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op
, &iv
, false))
198 if (!is_gimple_min_invariant (iv
.base
))
200 if (!is_gimple_min_invariant (iv
.step
))
205 /* Computes an estimated number of insns in LOOP.
206 EXIT (if non-NULL) is an exite edge that will be eliminated in all but last
207 iteration of the loop.
208 EDGE_TO_CANCEL (if non-NULL) is an non-exit edge eliminated in the last iteration
210 Return results in SIZE, estimate benefits for complete unrolling exiting by EXIT.
211 Stop estimating after UPPER_BOUND is met. Return true in this case */
214 tree_estimate_loop_size (struct loop
*loop
, edge exit
, edge edge_to_cancel
, struct loop_size
*size
,
217 basic_block
*body
= get_loop_body (loop
);
218 gimple_stmt_iterator gsi
;
221 vec
<basic_block
> path
= get_loop_hot_path (loop
);
224 size
->eliminated_by_peeling
= 0;
225 size
->last_iteration
= 0;
226 size
->last_iteration_eliminated_by_peeling
= 0;
227 size
->num_pure_calls_on_hot_path
= 0;
228 size
->num_non_pure_calls_on_hot_path
= 0;
229 size
->non_call_stmts_on_hot_path
= 0;
230 size
->num_branches_on_hot_path
= 0;
231 size
->constant_iv
= 0;
233 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
234 fprintf (dump_file
, "Estimating sizes for loop %i\n", loop
->num
);
235 for (i
= 0; i
< loop
->num_nodes
; i
++)
237 if (edge_to_cancel
&& body
[i
] != edge_to_cancel
->src
238 && dominated_by_p (CDI_DOMINATORS
, body
[i
], edge_to_cancel
->src
))
242 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
243 fprintf (dump_file
, " BB: %i, after_exit: %i\n", body
[i
]->index
, 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, 0);
259 /* Look for reasons why we might optimize this stmt away. */
261 /* Exit conditional. */
262 if (exit
&& body
[i
] == exit
->src
263 && stmt
== last_stmt (exit
->src
))
265 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
266 fprintf (dump_file
, " Exit condition will be eliminated "
267 "in peeled copies.\n");
268 likely_eliminated_peeled
= true;
270 else if (edge_to_cancel
&& body
[i
] == edge_to_cancel
->src
271 && stmt
== last_stmt (edge_to_cancel
->src
))
273 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
274 fprintf (dump_file
, " Exit condition will be eliminated "
276 likely_eliminated_last
= true;
278 /* Sets of IV variables */
279 else if (gimple_code (stmt
) == GIMPLE_ASSIGN
280 && constant_after_peeling (gimple_assign_lhs (stmt
), stmt
, loop
))
282 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
283 fprintf (dump_file
, " Induction variable computation will"
284 " be folded away.\n");
285 likely_eliminated
= true;
287 /* Assignments of IV variables. */
288 else if (gimple_code (stmt
) == GIMPLE_ASSIGN
289 && TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
290 && constant_after_peeling (gimple_assign_rhs1 (stmt
), stmt
, loop
)
291 && (gimple_assign_rhs_class (stmt
) != GIMPLE_BINARY_RHS
292 || constant_after_peeling (gimple_assign_rhs2 (stmt
),
295 size
->constant_iv
= true;
296 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
297 fprintf (dump_file
, " Constant expression will be folded away.\n");
298 likely_eliminated
= true;
301 else if ((gimple_code (stmt
) == GIMPLE_COND
302 && constant_after_peeling (gimple_cond_lhs (stmt
), stmt
, loop
)
303 && constant_after_peeling (gimple_cond_rhs (stmt
), stmt
, loop
))
304 || (gimple_code (stmt
) == GIMPLE_SWITCH
305 && constant_after_peeling (gimple_switch_index (stmt
), stmt
, loop
)))
307 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
308 fprintf (dump_file
, " Constant conditional.\n");
309 likely_eliminated
= true;
312 size
->overall
+= num
;
313 if (likely_eliminated
|| likely_eliminated_peeled
)
314 size
->eliminated_by_peeling
+= num
;
317 size
->last_iteration
+= num
;
318 if (likely_eliminated
|| likely_eliminated_last
)
319 size
->last_iteration_eliminated_by_peeling
+= num
;
321 if ((size
->overall
* 3 / 2 - size
->eliminated_by_peeling
322 - size
->last_iteration_eliminated_by_peeling
) > upper_bound
)
329 while (path
.length ())
331 basic_block bb
= path
.pop ();
332 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
334 gimple stmt
= gsi_stmt (gsi
);
335 if (gimple_code (stmt
) == GIMPLE_CALL
)
337 int flags
= gimple_call_flags (stmt
);
338 tree decl
= gimple_call_fndecl (stmt
);
340 if (decl
&& DECL_IS_BUILTIN (decl
)
341 && is_inexpensive_builtin (decl
))
343 else if (flags
& (ECF_PURE
| ECF_CONST
))
344 size
->num_pure_calls_on_hot_path
++;
346 size
->num_non_pure_calls_on_hot_path
++;
347 size
->num_branches_on_hot_path
++;
349 else if (gimple_code (stmt
) != GIMPLE_CALL
350 && gimple_code (stmt
) != GIMPLE_DEBUG
)
351 size
->non_call_stmts_on_hot_path
++;
352 if (((gimple_code (stmt
) == GIMPLE_COND
353 && (!constant_after_peeling (gimple_cond_lhs (stmt
), stmt
, loop
)
354 || constant_after_peeling (gimple_cond_rhs (stmt
), stmt
, loop
)))
355 || (gimple_code (stmt
) == GIMPLE_SWITCH
356 && !constant_after_peeling (gimple_switch_index (stmt
), stmt
, loop
)))
357 && (!exit
|| bb
!= exit
->src
))
358 size
->num_branches_on_hot_path
++;
362 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
363 fprintf (dump_file
, "size: %i-%i, last_iteration: %i-%i\n", size
->overall
,
364 size
->eliminated_by_peeling
, size
->last_iteration
,
365 size
->last_iteration_eliminated_by_peeling
);
371 /* Estimate number of insns of completely unrolled loop.
372 It is (NUNROLL + 1) * size of loop body with taking into account
373 the fact that in last copy everything after exit conditional
374 is dead and that some instructions will be eliminated after
377 Loop body is likely going to simplify futher, this is difficult
378 to guess, we just decrease the result by 1/3. */
380 static unsigned HOST_WIDE_INT
381 estimated_unrolled_size (struct loop_size
*size
,
382 unsigned HOST_WIDE_INT nunroll
)
384 HOST_WIDE_INT unr_insns
= ((nunroll
)
385 * (HOST_WIDE_INT
) (size
->overall
386 - size
->eliminated_by_peeling
));
389 unr_insns
+= size
->last_iteration
- size
->last_iteration_eliminated_by_peeling
;
391 unr_insns
= unr_insns
* 2 / 3;
398 /* Loop LOOP is known to not loop. See if there is an edge in the loop
399 body that can be remove to make the loop to always exit and at
400 the same time it does not make any code potentially executed
401 during the last iteration dead.
403 After complette unrolling we still may get rid of the conditional
404 on the exit in the last copy even if we have no idea what it does.
405 This is quite common case for loops of form
411 Here we prove the loop to iterate 5 times but we do not know
412 it from induction variable.
414 For now we handle only simple case where there is exit condition
415 just before the latch block and the latch block contains no statements
416 with side effect that may otherwise terminate the execution of loop
417 (such as by EH or by terminating the program or longjmp).
419 In the general case we may want to cancel the paths leading to statements
420 loop-niter identified as having undefined effect in the last iteration.
421 The other cases are hopefully rare and will be cleaned up later. */
424 loop_edge_to_cancel (struct loop
*loop
)
429 gimple_stmt_iterator gsi
;
431 /* We want only one predecestor of the loop. */
432 if (EDGE_COUNT (loop
->latch
->preds
) > 1)
435 exits
= get_loop_exit_edges (loop
);
437 FOR_EACH_VEC_ELT (exits
, i
, edge_to_cancel
)
439 /* Find the other edge than the loop exit
440 leaving the conditoinal. */
441 if (EDGE_COUNT (edge_to_cancel
->src
->succs
) != 2)
443 if (EDGE_SUCC (edge_to_cancel
->src
, 0) == edge_to_cancel
)
444 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 1);
446 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 0);
448 /* We only can handle conditionals. */
449 if (!(edge_to_cancel
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
452 /* We should never have conditionals in the loop latch. */
453 gcc_assert (edge_to_cancel
->dest
!= loop
->header
);
455 /* Check that it leads to loop latch. */
456 if (edge_to_cancel
->dest
!= loop
->latch
)
461 /* Verify that the code in loop latch does nothing that may end program
462 execution without really reaching the exit. This may include
463 non-pure/const function calls, EH statements, volatile ASMs etc. */
464 for (gsi
= gsi_start_bb (loop
->latch
); !gsi_end_p (gsi
); gsi_next (&gsi
))
465 if (gimple_has_side_effects (gsi_stmt (gsi
)))
467 return edge_to_cancel
;
473 /* Remove all tests for exits that are known to be taken after LOOP was
474 peeled NPEELED times. Put gcc_unreachable before every statement
475 known to not be executed. */
478 remove_exits_and_undefined_stmts (struct loop
*loop
, unsigned int npeeled
)
480 struct nb_iter_bound
*elt
;
481 bool changed
= false;
483 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
485 /* If statement is known to be undefined after peeling, turn it
486 into unreachable (or trap when debugging experience is supposed
489 && elt
->bound
.ult (double_int::from_uhwi (npeeled
)))
491 gimple_stmt_iterator gsi
= gsi_for_stmt (elt
->stmt
);
492 gimple stmt
= gimple_build_call
493 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
), 0);
495 gimple_set_location (stmt
, gimple_location (elt
->stmt
));
496 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
498 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
500 fprintf (dump_file
, "Forced statement unreachable: ");
501 print_gimple_stmt (dump_file
, elt
->stmt
, 0, 0);
504 /* If we know the exit will be taken after peeling, update. */
505 else if (elt
->is_exit
506 && elt
->bound
.ule (double_int::from_uhwi (npeeled
)))
508 basic_block bb
= gimple_bb (elt
->stmt
);
509 edge exit_edge
= EDGE_SUCC (bb
, 0);
511 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
513 fprintf (dump_file
, "Forced exit to be taken: ");
514 print_gimple_stmt (dump_file
, elt
->stmt
, 0, 0);
516 if (!loop_exit_edge_p (loop
, exit_edge
))
517 exit_edge
= EDGE_SUCC (bb
, 1);
518 gcc_checking_assert (loop_exit_edge_p (loop
, exit_edge
));
519 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
520 gimple_cond_make_true (elt
->stmt
);
522 gimple_cond_make_false (elt
->stmt
);
523 update_stmt (elt
->stmt
);
530 /* Remove all exits that are known to be never taken because of the loop bound
534 remove_redundant_iv_tests (struct loop
*loop
)
536 struct nb_iter_bound
*elt
;
537 bool changed
= false;
539 if (!loop
->any_upper_bound
)
541 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
543 /* Exit is pointless if it won't be taken before loop reaches
545 if (elt
->is_exit
&& loop
->any_upper_bound
546 && loop
->nb_iterations_upper_bound
.ult (elt
->bound
))
548 basic_block bb
= gimple_bb (elt
->stmt
);
549 edge exit_edge
= EDGE_SUCC (bb
, 0);
550 struct tree_niter_desc niter
;
552 if (!loop_exit_edge_p (loop
, exit_edge
))
553 exit_edge
= EDGE_SUCC (bb
, 1);
555 /* Only when we know the actual number of iterations, not
556 just a bound, we can remove the exit. */
557 if (!number_of_iterations_exit (loop
, exit_edge
,
558 &niter
, false, false)
559 || !integer_onep (niter
.assumptions
)
560 || !integer_zerop (niter
.may_be_zero
)
562 || TREE_CODE (niter
.niter
) != INTEGER_CST
563 || !loop
->nb_iterations_upper_bound
.ult
564 (tree_to_double_int (niter
.niter
)))
567 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
569 fprintf (dump_file
, "Removed pointless exit: ");
570 print_gimple_stmt (dump_file
, elt
->stmt
, 0, 0);
572 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
573 gimple_cond_make_false (elt
->stmt
);
575 gimple_cond_make_true (elt
->stmt
);
576 update_stmt (elt
->stmt
);
583 /* Stores loops that will be unlooped after we process whole loop tree. */
584 static vec
<loop_p
> loops_to_unloop
;
585 static vec
<int> loops_to_unloop_nunroll
;
587 /* Cancel all fully unrolled loops by putting __builtin_unreachable
589 We do it after all unrolling since unlooping moves basic blocks
590 across loop boundaries trashing loop closed SSA form as well
591 as SCEV info needed to be intact during unrolling.
593 IRRED_INVALIDATED is used to bookkeep if information about
594 irreducible regions may become invalid as a result
595 of the transformation.
596 LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case
597 when we need to go into loop closed SSA form. */
600 unloop_loops (bitmap loop_closed_ssa_invalidated
,
601 bool *irred_invalidated
)
603 while (loops_to_unloop
.length ())
605 struct loop
*loop
= loops_to_unloop
.pop ();
606 int n_unroll
= loops_to_unloop_nunroll
.pop ();
607 basic_block latch
= loop
->latch
;
608 edge latch_edge
= loop_latch_edge (loop
);
609 int flags
= latch_edge
->flags
;
610 location_t locus
= latch_edge
->goto_locus
;
612 gimple_stmt_iterator gsi
;
614 remove_exits_and_undefined_stmts (loop
, n_unroll
);
616 /* Unloop destroys the latch edge. */
617 unloop (loop
, irred_invalidated
, loop_closed_ssa_invalidated
);
619 /* Create new basic block for the latch edge destination and wire
621 stmt
= gimple_build_call (builtin_decl_implicit (BUILT_IN_UNREACHABLE
), 0);
622 latch_edge
= make_edge (latch
, create_basic_block (NULL
, NULL
, latch
), flags
);
623 latch_edge
->probability
= 0;
624 latch_edge
->count
= 0;
625 latch_edge
->flags
|= flags
;
626 latch_edge
->goto_locus
= locus
;
628 latch_edge
->dest
->loop_father
= current_loops
->tree_root
;
629 latch_edge
->dest
->count
= 0;
630 latch_edge
->dest
->frequency
= 0;
631 set_immediate_dominator (CDI_DOMINATORS
, latch_edge
->dest
, latch_edge
->src
);
633 gsi
= gsi_start_bb (latch_edge
->dest
);
634 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
636 loops_to_unloop
.release ();
637 loops_to_unloop_nunroll
.release ();
640 /* Tries to unroll LOOP completely, i.e. NITER times.
641 UL determines which loops we are allowed to unroll.
642 EXIT is the exit of the loop that should be eliminated.
643 MAXITER specfy bound on number of iterations, -1 if it is
644 not known or too large for HOST_WIDE_INT. */
647 try_unroll_loop_completely (struct loop
*loop
,
648 edge exit
, tree niter
,
649 enum unroll_level ul
,
650 HOST_WIDE_INT maxiter
)
652 unsigned HOST_WIDE_INT n_unroll
, ninsns
, max_unroll
, unr_insns
;
654 struct loop_size size
;
655 bool n_unroll_found
= false;
656 edge edge_to_cancel
= NULL
;
659 /* See if we proved number of iterations to be low constant.
661 EXIT is an edge that will be removed in all but last iteration of
664 EDGE_TO_CACNEL is an edge that will be removed from the last iteration
665 of the unrolled sequence and is expected to make the final loop not
668 If the number of execution of loop is determined by standard induction
669 variable test, then EXIT and EDGE_TO_CANCEL are the two edges leaving
671 if (host_integerp (niter
, 1))
673 n_unroll
= tree_low_cst (niter
, 1);
674 n_unroll_found
= true;
675 edge_to_cancel
= EDGE_SUCC (exit
->src
, 0);
676 if (edge_to_cancel
== exit
)
677 edge_to_cancel
= EDGE_SUCC (exit
->src
, 1);
679 /* We do not know the number of iterations and thus we can not eliminate
684 /* See if we can improve our estimate by using recorded loop bounds. */
686 && (!n_unroll_found
|| (unsigned HOST_WIDE_INT
)maxiter
< n_unroll
))
689 n_unroll_found
= true;
690 /* Loop terminates before the IV variable test, so we can not
691 remove it in the last iteration. */
692 edge_to_cancel
= NULL
;
698 max_unroll
= PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
);
699 if (n_unroll
> max_unroll
)
703 edge_to_cancel
= loop_edge_to_cancel (loop
);
711 vec
<edge
> to_remove
= vNULL
;
712 if (ul
== UL_SINGLE_ITER
)
715 large
= tree_estimate_loop_size
716 (loop
, exit
, edge_to_cancel
, &size
,
717 PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
));
718 ninsns
= size
.overall
;
721 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
722 fprintf (dump_file
, "Not unrolling loop %d: it is too large.\n",
727 unr_insns
= estimated_unrolled_size (&size
, n_unroll
);
728 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
730 fprintf (dump_file
, " Loop size: %d\n", (int) ninsns
);
731 fprintf (dump_file
, " Estimated size after unrolling: %d\n",
735 /* If the code is going to shrink, we don't need to be extra cautious
736 on guessing if the unrolling is going to be profitable. */
738 /* If there is IV variable that will become constant, we save
739 one instruction in the loop prologue we do not account
741 <= ninsns
+ (size
.constant_iv
!= false))
743 /* We unroll only inner loops, because we do not consider it profitable
744 otheriwse. We still can cancel loopback edge of not rolling loop;
745 this is always a good idea. */
746 else if (ul
== UL_NO_GROWTH
)
748 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
749 fprintf (dump_file
, "Not unrolling loop %d: size would grow.\n",
753 /* Outer loops tend to be less interesting candidates for complette
754 unrolling unless we can do a lot of propagation into the inner loop
755 body. For now we disable outer loop unrolling when the code would
757 else if (loop
->inner
)
759 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
760 fprintf (dump_file
, "Not unrolling loop %d: "
761 "it is not innermost and code would grow.\n",
765 /* If there is call on a hot path through the loop, then
766 there is most probably not much to optimize. */
767 else if (size
.num_non_pure_calls_on_hot_path
)
769 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
770 fprintf (dump_file
, "Not unrolling loop %d: "
771 "contains call and code would grow.\n",
775 /* If there is pure/const call in the function, then we
776 can still optimize the unrolled loop body if it contains
777 some other interesting code than the calls and code
778 storing or cumulating the return value. */
779 else if (size
.num_pure_calls_on_hot_path
780 /* One IV increment, one test, one ivtmp store
781 and one usefull stmt. That is about minimal loop
783 && (size
.non_call_stmts_on_hot_path
784 <= 3 + size
.num_pure_calls_on_hot_path
))
786 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
787 fprintf (dump_file
, "Not unrolling loop %d: "
788 "contains just pure calls and code would grow.\n",
792 /* Complette unrolling is major win when control flow is removed and
793 one big basic block is created. If the loop contains control flow
794 the optimization may still be a win because of eliminating the loop
795 overhead but it also may blow the branch predictor tables.
796 Limit number of branches on the hot path through the peeled
798 else if (size
.num_branches_on_hot_path
* (int)n_unroll
799 > PARAM_VALUE (PARAM_MAX_PEEL_BRANCHES
))
801 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
802 fprintf (dump_file
, "Not unrolling loop %d: "
803 " number of branches on hot path in the unrolled sequence"
804 " reach --param max-peel-branches limit.\n",
809 > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
))
811 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
812 fprintf (dump_file
, "Not unrolling loop %d: "
813 "(--param max-completely-peeled-insns limit reached).\n",
818 initialize_original_copy_tables ();
819 wont_exit
= sbitmap_alloc (n_unroll
+ 1);
820 bitmap_ones (wont_exit
);
821 bitmap_clear_bit (wont_exit
, 0);
823 if (!gimple_duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
826 DLTHE_FLAG_UPDATE_FREQ
827 | DLTHE_FLAG_COMPLETTE_PEEL
))
829 free_original_copy_tables ();
831 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
832 fprintf (dump_file
, "Failed to duplicate the loop\n");
836 FOR_EACH_VEC_ELT (to_remove
, i
, e
)
838 bool ok
= remove_path (e
);
842 to_remove
.release ();
844 free_original_copy_tables ();
848 /* Remove the conditional from the last copy of the loop. */
851 cond
= last_stmt (edge_to_cancel
->src
);
852 if (edge_to_cancel
->flags
& EDGE_TRUE_VALUE
)
853 gimple_cond_make_false (cond
);
855 gimple_cond_make_true (cond
);
857 /* Do not remove the path. Doing so may remove outer loop
858 and confuse bookkeeping code in tree_unroll_loops_completelly. */
861 /* Store the loop for later unlooping and exit removal. */
862 loops_to_unloop
.safe_push (loop
);
863 loops_to_unloop_nunroll
.safe_push (n_unroll
);
865 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
868 fprintf (dump_file
, "Turned loop %d to non-loop; it never loops.\n",
871 fprintf (dump_file
, "Unrolled loop %d completely "
872 "(duplicated %i times).\n", num
, (int)n_unroll
);
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;
902 niter
= number_of_latch_executions (loop
);
903 if (TREE_CODE (niter
) == INTEGER_CST
)
904 exit
= single_exit (loop
);
907 /* If the loop has more than one exit, try checking all of them
908 for # of iterations determinable through scev. */
909 if (!single_exit (loop
))
910 niter
= find_loop_niter (loop
, &exit
);
912 /* Finally if everything else fails, try brute force evaluation. */
914 && (chrec_contains_undetermined (niter
)
915 || TREE_CODE (niter
) != INTEGER_CST
))
916 niter
= find_loop_niter_by_eval (loop
, &exit
);
918 if (TREE_CODE (niter
) != INTEGER_CST
)
922 /* We work exceptionally hard here to estimate the bound
923 by find_loop_niter_by_eval. Be sure to keep it for future. */
924 if (niter
&& TREE_CODE (niter
) == INTEGER_CST
)
926 record_niter_bound (loop
, tree_to_double_int (niter
),
927 exit
== single_likely_exit (loop
), true);
930 /* Force re-computation of loop bounds so we can remove redundant exits. */
931 maxiter
= max_loop_iterations_int (loop
);
933 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
934 && TREE_CODE (niter
) == INTEGER_CST
)
936 fprintf (dump_file
, "Loop %d iterates ", loop
->num
);
937 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
938 fprintf (dump_file
, " times.\n");
940 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
943 fprintf (dump_file
, "Loop %d iterates at most %i times.\n", loop
->num
,
947 /* Remove exits that are known to be never taken based on loop bound.
948 Needs to be called after compilation of max_loop_iterations_int that
949 populates the loop bounds. */
950 modified
|= remove_redundant_iv_tests (loop
);
952 if (try_unroll_loop_completely (loop
, exit
, niter
, ul
, maxiter
))
956 && niter
&& !chrec_contains_undetermined (niter
)
957 && exit
&& just_once_each_iteration_p (loop
, exit
->src
))
958 create_canonical_iv (loop
, exit
, niter
);
963 /* The main entry point of the pass. Adds canonical induction variables
964 to the suitable loops. */
967 canonicalize_induction_variables (void)
971 bool changed
= false;
972 bool irred_invalidated
= false;
973 bitmap loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
975 free_numbers_of_iterations_estimates ();
976 estimate_numbers_of_iterations ();
978 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
980 changed
|= canonicalize_loop_induction_variables (loop
,
981 true, UL_SINGLE_ITER
,
984 gcc_assert (!need_ssa_update_p (cfun
));
986 unloop_loops (loop_closed_ssa_invalidated
, &irred_invalidated
);
987 if (irred_invalidated
988 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
989 mark_irreducible_loops ();
991 /* Clean up the information about numbers of iterations, since brute force
992 evaluation could reveal new information. */
995 if (!bitmap_empty_p (loop_closed_ssa_invalidated
))
997 gcc_checking_assert (loops_state_satisfies_p (LOOP_CLOSED_SSA
));
998 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1000 BITMAP_FREE (loop_closed_ssa_invalidated
);
1003 return TODO_cleanup_cfg
;
1007 /* Propagate VAL into all uses of SSA_NAME. */
1010 propagate_into_all_uses (tree ssa_name
, tree val
)
1012 imm_use_iterator iter
;
1015 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, ssa_name
)
1017 gimple_stmt_iterator use_stmt_gsi
= gsi_for_stmt (use_stmt
);
1020 FOR_EACH_IMM_USE_ON_STMT (use
, iter
)
1023 if (is_gimple_assign (use_stmt
)
1024 && get_gimple_rhs_class (gimple_assign_rhs_code (use_stmt
))
1025 == GIMPLE_SINGLE_RHS
)
1027 tree rhs
= gimple_assign_rhs1 (use_stmt
);
1029 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1030 recompute_tree_invariant_for_addr_expr (rhs
);
1033 fold_stmt_inplace (&use_stmt_gsi
);
1034 update_stmt (use_stmt
);
1035 maybe_clean_or_replace_eh_stmt (use_stmt
, use_stmt
);
1039 /* Propagate constant SSA_NAMEs defined in basic block BB. */
1042 propagate_constants_for_unrolling (basic_block bb
)
1044 gimple_stmt_iterator gsi
;
1046 /* Look for degenerate PHI nodes with constant argument. */
1047 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); )
1049 gimple phi
= gsi_stmt (gsi
);
1050 tree result
= gimple_phi_result (phi
);
1051 tree arg
= gimple_phi_arg_def (phi
, 0);
1053 if (gimple_phi_num_args (phi
) == 1 && TREE_CODE (arg
) == INTEGER_CST
)
1055 propagate_into_all_uses (result
, arg
);
1056 gsi_remove (&gsi
, true);
1057 release_ssa_name (result
);
1063 /* Look for assignments to SSA names with constant RHS. */
1064 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
1066 gimple stmt
= gsi_stmt (gsi
);
1069 if (is_gimple_assign (stmt
)
1070 && (lhs
= gimple_assign_lhs (stmt
), TREE_CODE (lhs
) == SSA_NAME
)
1071 && gimple_assign_rhs_code (stmt
) == INTEGER_CST
)
1073 propagate_into_all_uses (lhs
, gimple_assign_rhs1 (stmt
));
1074 gsi_remove (&gsi
, true);
1075 release_ssa_name (lhs
);
1082 /* Unroll LOOPS completely if they iterate just few times. Unless
1083 MAY_INCREASE_SIZE is true, perform the unrolling only if the
1084 size of the code does not increase. */
1087 tree_unroll_loops_completely (bool may_increase_size
, bool unroll_outer
)
1089 vec
<loop_p
, va_stack
> father_stack
;
1093 enum unroll_level ul
;
1095 bool irred_invalidated
= false;
1097 vec_stack_alloc (loop_p
, father_stack
, 16);
1101 bitmap loop_closed_ssa_invalidated
= NULL
;
1103 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1104 loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
1106 free_numbers_of_iterations_estimates ();
1107 estimate_numbers_of_iterations ();
1109 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1111 struct loop
*loop_father
= loop_outer (loop
);
1113 if (may_increase_size
&& optimize_loop_nest_for_speed_p (loop
)
1114 /* Unroll outermost loops only if asked to do so or they do
1115 not cause code growth. */
1116 && (unroll_outer
|| loop_outer (loop_father
)))
1121 if (canonicalize_loop_induction_variables
1122 (loop
, false, ul
, !flag_tree_loop_ivcanon
))
1125 /* If we'll continue unrolling, we need to propagate constants
1126 within the new basic blocks to fold away induction variable
1127 computations; otherwise, the size might blow up before the
1128 iteration is complete and the IR eventually cleaned up. */
1129 if (loop_outer (loop_father
) && !loop_father
->aux
)
1131 father_stack
.safe_push (loop_father
);
1132 loop_father
->aux
= loop_father
;
1142 /* Be sure to skip unlooped loops while procesing father_stack
1144 FOR_EACH_VEC_ELT (loops_to_unloop
, i
, iter
)
1145 (*iter
)->aux
= NULL
;
1146 FOR_EACH_VEC_ELT (father_stack
, i
, iter
)
1149 unloop_loops (loop_closed_ssa_invalidated
, &irred_invalidated
);
1151 /* We can not use TODO_update_ssa_no_phi because VOPS gets confused. */
1152 if (loop_closed_ssa_invalidated
1153 && !bitmap_empty_p (loop_closed_ssa_invalidated
))
1154 rewrite_into_loop_closed_ssa (loop_closed_ssa_invalidated
,
1157 update_ssa (TODO_update_ssa
);
1159 /* Propagate the constants within the new basic blocks. */
1160 FOR_EACH_VEC_ELT (father_stack
, i
, iter
)
1164 basic_block
*body
= get_loop_body_in_dom_order (*iter
);
1165 for (j
= 0; j
< (*iter
)->num_nodes
; j
++)
1166 propagate_constants_for_unrolling (body
[j
]);
1168 (*iter
)->aux
= NULL
;
1170 father_stack
.truncate (0);
1172 /* This will take care of removing completely unrolled loops
1173 from the loop structures so we can continue unrolling now
1175 if (cleanup_tree_cfg ())
1176 update_ssa (TODO_update_ssa_only_virtuals
);
1178 /* Clean up the information about numbers of iterations, since
1179 complete unrolling might have invalidated it. */
1181 #ifdef ENABLE_CHECKING
1182 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1183 verify_loop_closed_ssa (true);
1186 if (loop_closed_ssa_invalidated
)
1187 BITMAP_FREE (loop_closed_ssa_invalidated
);
1190 && ++iteration
<= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS
));
1192 father_stack
.release ();
1194 if (irred_invalidated
1195 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1196 mark_irreducible_loops ();