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"
43 #include "tree-flow.h"
45 #include "tree-pass.h"
46 #include "tree-chrec.h"
47 #include "tree-scalar-evolution.h"
50 #include "tree-inline.h"
53 /* Specifies types of loops that may be unrolled. */
57 UL_SINGLE_ITER
, /* Only loops that exit immediately in the first
59 UL_NO_GROWTH
, /* Only loops whose unrolling will not cause increase
61 UL_ALL
/* All suitable loops. */
64 /* Adds a canonical induction variable to LOOP iterating NITER times. EXIT
65 is the exit edge whose condition is replaced. */
68 create_canonical_iv (struct loop
*loop
, edge exit
, tree niter
)
73 gimple_stmt_iterator incr_at
;
76 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
78 fprintf (dump_file
, "Added canonical iv to loop %d, ", loop
->num
);
79 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
80 fprintf (dump_file
, " iterations.\n");
83 cond
= last_stmt (exit
->src
);
84 in
= EDGE_SUCC (exit
->src
, 0);
86 in
= EDGE_SUCC (exit
->src
, 1);
88 /* Note that we do not need to worry about overflows, since
89 type of niter is always unsigned and all comparisons are
90 just for equality/nonequality -- i.e. everything works
91 with a modulo arithmetics. */
93 type
= TREE_TYPE (niter
);
94 niter
= fold_build2 (PLUS_EXPR
, type
,
96 build_int_cst (type
, 1));
97 incr_at
= gsi_last_bb (in
->src
);
99 build_int_cst (type
, -1),
101 &incr_at
, false, NULL
, &var
);
103 cmp
= (exit
->flags
& EDGE_TRUE_VALUE
) ? EQ_EXPR
: NE_EXPR
;
104 gimple_cond_set_code (cond
, cmp
);
105 gimple_cond_set_lhs (cond
, var
);
106 gimple_cond_set_rhs (cond
, build_int_cst (type
, 0));
110 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */
113 tree_num_loop_insns (struct loop
*loop
, eni_weights
*weights
)
115 basic_block
*body
= get_loop_body (loop
);
116 gimple_stmt_iterator gsi
;
117 unsigned size
= 0, i
;
119 for (i
= 0; i
< loop
->num_nodes
; i
++)
120 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
121 size
+= estimate_num_insns (gsi_stmt (gsi
), weights
);
127 /* Describe size of loop as detected by tree_estimate_loop_size. */
130 /* Number of instructions in the loop. */
133 /* Number of instructions that will be likely optimized out in
134 peeled iterations of loop (i.e. computation based on induction
135 variable where induction variable starts at known constant.) */
136 int eliminated_by_peeling
;
138 /* Same statistics for last iteration of loop: it is smaller because
139 instructions after exit are not executed. */
141 int last_iteration_eliminated_by_peeling
;
143 /* If some IV computation will become constant. */
146 /* Number of call stmts that are not a builtin and are pure or const
147 present on the hot path. */
148 int num_pure_calls_on_hot_path
;
149 /* Number of call stmts that are not a builtin and are not pure nor const
150 present on the hot path. */
151 int num_non_pure_calls_on_hot_path
;
152 /* Number of statements other than calls in the loop. */
153 int non_call_stmts_on_hot_path
;
154 /* Number of branches seen on the hot path. */
155 int num_branches_on_hot_path
;
158 /* Return true if OP in STMT will be constant after peeling LOOP. */
161 constant_after_peeling (tree op
, gimple stmt
, struct loop
*loop
)
165 if (is_gimple_min_invariant (op
))
168 /* We can still fold accesses to constant arrays when index is known. */
169 if (TREE_CODE (op
) != SSA_NAME
)
173 /* First make fast look if we see constant array inside. */
174 while (handled_component_p (base
))
175 base
= TREE_OPERAND (base
, 0);
177 && const_value_known_p (base
))
178 || CONSTANT_CLASS_P (base
))
180 /* If so, see if we understand all the indices. */
182 while (handled_component_p (base
))
184 if (TREE_CODE (base
) == ARRAY_REF
185 && !constant_after_peeling (TREE_OPERAND (base
, 1), stmt
, loop
))
187 base
= TREE_OPERAND (base
, 0);
194 /* Induction variables are constants. */
195 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op
, &iv
, false))
197 if (!is_gimple_min_invariant (iv
.base
))
199 if (!is_gimple_min_invariant (iv
.step
))
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
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 */
213 tree_estimate_loop_size (struct loop
*loop
, edge exit
, edge edge_to_cancel
, struct loop_size
*size
,
216 basic_block
*body
= get_loop_body (loop
);
217 gimple_stmt_iterator gsi
;
220 vec
<basic_block
> path
= get_loop_hot_path (loop
);
223 size
->eliminated_by_peeling
= 0;
224 size
->last_iteration
= 0;
225 size
->last_iteration_eliminated_by_peeling
= 0;
226 size
->num_pure_calls_on_hot_path
= 0;
227 size
->num_non_pure_calls_on_hot_path
= 0;
228 size
->non_call_stmts_on_hot_path
= 0;
229 size
->num_branches_on_hot_path
= 0;
230 size
->constant_iv
= 0;
232 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
233 fprintf (dump_file
, "Estimating sizes for loop %i\n", loop
->num
);
234 for (i
= 0; i
< loop
->num_nodes
; i
++)
236 if (edge_to_cancel
&& body
[i
] != edge_to_cancel
->src
237 && dominated_by_p (CDI_DOMINATORS
, body
[i
], edge_to_cancel
->src
))
241 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
242 fprintf (dump_file
, " BB: %i, after_exit: %i\n", body
[i
]->index
, after_exit
);
244 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
246 gimple stmt
= gsi_stmt (gsi
);
247 int num
= estimate_num_insns (stmt
, &eni_size_weights
);
248 bool likely_eliminated
= false;
249 bool likely_eliminated_last
= false;
250 bool likely_eliminated_peeled
= false;
252 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
254 fprintf (dump_file
, " size: %3i ", num
);
255 print_gimple_stmt (dump_file
, gsi_stmt (gsi
), 0, 0);
258 /* Look for reasons why we might optimize this stmt away. */
260 /* Exit conditional. */
261 if (exit
&& body
[i
] == exit
->src
262 && stmt
== last_stmt (exit
->src
))
264 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
265 fprintf (dump_file
, " Exit condition will be eliminated "
266 "in peeled copies.\n");
267 likely_eliminated_peeled
= true;
269 else if (edge_to_cancel
&& body
[i
] == edge_to_cancel
->src
270 && stmt
== last_stmt (edge_to_cancel
->src
))
272 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
273 fprintf (dump_file
, " Exit condition will be eliminated "
275 likely_eliminated_last
= true;
277 /* Sets of IV variables */
278 else if (gimple_code (stmt
) == GIMPLE_ASSIGN
279 && constant_after_peeling (gimple_assign_lhs (stmt
), stmt
, loop
))
281 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
282 fprintf (dump_file
, " Induction variable computation will"
283 " be folded away.\n");
284 likely_eliminated
= true;
286 /* Assignments of IV variables. */
287 else if (gimple_code (stmt
) == GIMPLE_ASSIGN
288 && TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
289 && constant_after_peeling (gimple_assign_rhs1 (stmt
), stmt
, loop
)
290 && (gimple_assign_rhs_class (stmt
) != GIMPLE_BINARY_RHS
291 || constant_after_peeling (gimple_assign_rhs2 (stmt
),
294 size
->constant_iv
= true;
295 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
296 fprintf (dump_file
, " Constant expression will be folded away.\n");
297 likely_eliminated
= true;
300 else if ((gimple_code (stmt
) == GIMPLE_COND
301 && constant_after_peeling (gimple_cond_lhs (stmt
), stmt
, loop
)
302 && constant_after_peeling (gimple_cond_rhs (stmt
), stmt
, loop
))
303 || (gimple_code (stmt
) == GIMPLE_SWITCH
304 && constant_after_peeling (gimple_switch_index (stmt
), stmt
, loop
)))
306 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
307 fprintf (dump_file
, " Constant conditional.\n");
308 likely_eliminated
= true;
311 size
->overall
+= num
;
312 if (likely_eliminated
|| likely_eliminated_peeled
)
313 size
->eliminated_by_peeling
+= num
;
316 size
->last_iteration
+= num
;
317 if (likely_eliminated
|| likely_eliminated_last
)
318 size
->last_iteration_eliminated_by_peeling
+= num
;
320 if ((size
->overall
* 3 / 2 - size
->eliminated_by_peeling
321 - size
->last_iteration_eliminated_by_peeling
) > upper_bound
)
328 while (path
.length ())
330 basic_block bb
= path
.pop ();
331 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
333 gimple stmt
= gsi_stmt (gsi
);
334 if (gimple_code (stmt
) == GIMPLE_CALL
)
336 int flags
= gimple_call_flags (stmt
);
337 tree decl
= gimple_call_fndecl (stmt
);
339 if (decl
&& DECL_IS_BUILTIN (decl
)
340 && is_inexpensive_builtin (decl
))
342 else if (flags
& (ECF_PURE
| ECF_CONST
))
343 size
->num_pure_calls_on_hot_path
++;
345 size
->num_non_pure_calls_on_hot_path
++;
346 size
->num_branches_on_hot_path
++;
348 else if (gimple_code (stmt
) != GIMPLE_CALL
349 && gimple_code (stmt
) != GIMPLE_DEBUG
)
350 size
->non_call_stmts_on_hot_path
++;
351 if (((gimple_code (stmt
) == GIMPLE_COND
352 && (!constant_after_peeling (gimple_cond_lhs (stmt
), stmt
, loop
)
353 || constant_after_peeling (gimple_cond_rhs (stmt
), stmt
, loop
)))
354 || (gimple_code (stmt
) == GIMPLE_SWITCH
355 && !constant_after_peeling (gimple_switch_index (stmt
), stmt
, loop
)))
356 && (!exit
|| bb
!= exit
->src
))
357 size
->num_branches_on_hot_path
++;
361 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
362 fprintf (dump_file
, "size: %i-%i, last_iteration: %i-%i\n", size
->overall
,
363 size
->eliminated_by_peeling
, size
->last_iteration
,
364 size
->last_iteration_eliminated_by_peeling
);
370 /* Estimate number of insns of completely unrolled loop.
371 It is (NUNROLL + 1) * size of loop body with taking into account
372 the fact that in last copy everything after exit conditional
373 is dead and that some instructions will be eliminated after
376 Loop body is likely going to simplify futher, this is difficult
377 to guess, we just decrease the result by 1/3. */
379 static unsigned HOST_WIDE_INT
380 estimated_unrolled_size (struct loop_size
*size
,
381 unsigned HOST_WIDE_INT nunroll
)
383 HOST_WIDE_INT unr_insns
= ((nunroll
)
384 * (HOST_WIDE_INT
) (size
->overall
385 - size
->eliminated_by_peeling
));
388 unr_insns
+= size
->last_iteration
- size
->last_iteration_eliminated_by_peeling
;
390 unr_insns
= unr_insns
* 2 / 3;
397 /* Loop LOOP is known to not loop. See if there is an edge in the loop
398 body that can be remove to make the loop to always exit and at
399 the same time it does not make any code potentially executed
400 during the last iteration dead.
402 After complette unrolling we still may get rid of the conditional
403 on the exit in the last copy even if we have no idea what it does.
404 This is quite common case for loops of form
410 Here we prove the loop to iterate 5 times but we do not know
411 it from induction variable.
413 For now we handle only simple case where there is exit condition
414 just before the latch block and the latch block contains no statements
415 with side effect that may otherwise terminate the execution of loop
416 (such as by EH or by terminating the program or longjmp).
418 In the general case we may want to cancel the paths leading to statements
419 loop-niter identified as having undefined effect in the last iteration.
420 The other cases are hopefully rare and will be cleaned up later. */
423 loop_edge_to_cancel (struct loop
*loop
)
428 gimple_stmt_iterator gsi
;
430 /* We want only one predecestor of the loop. */
431 if (EDGE_COUNT (loop
->latch
->preds
) > 1)
434 exits
= get_loop_exit_edges (loop
);
436 FOR_EACH_VEC_ELT (exits
, i
, edge_to_cancel
)
438 /* Find the other edge than the loop exit
439 leaving the conditoinal. */
440 if (EDGE_COUNT (edge_to_cancel
->src
->succs
) != 2)
442 if (EDGE_SUCC (edge_to_cancel
->src
, 0) == edge_to_cancel
)
443 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 1);
445 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 0);
447 /* We only can handle conditionals. */
448 if (!(edge_to_cancel
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
451 /* We should never have conditionals in the loop latch. */
452 gcc_assert (edge_to_cancel
->dest
!= loop
->header
);
454 /* Check that it leads to loop latch. */
455 if (edge_to_cancel
->dest
!= loop
->latch
)
460 /* Verify that the code in loop latch does nothing that may end program
461 execution without really reaching the exit. This may include
462 non-pure/const function calls, EH statements, volatile ASMs etc. */
463 for (gsi
= gsi_start_bb (loop
->latch
); !gsi_end_p (gsi
); gsi_next (&gsi
))
464 if (gimple_has_side_effects (gsi_stmt (gsi
)))
466 return edge_to_cancel
;
472 /* Remove all tests for exits that are known to be taken after LOOP was
473 peeled NPEELED times. Put gcc_unreachable before every statement
474 known to not be executed. */
477 remove_exits_and_undefined_stmts (struct loop
*loop
, unsigned int npeeled
)
479 struct nb_iter_bound
*elt
;
480 bool changed
= false;
482 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
484 /* If statement is known to be undefined after peeling, turn it
485 into unreachable (or trap when debugging experience is supposed
488 && elt
->bound
.ult (double_int::from_uhwi (npeeled
)))
490 gimple_stmt_iterator gsi
= gsi_for_stmt (elt
->stmt
);
491 gimple stmt
= gimple_build_call
492 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
), 0);
494 gimple_set_location (stmt
, gimple_location (elt
->stmt
));
495 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
497 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
499 fprintf (dump_file
, "Forced statement unreachable: ");
500 print_gimple_stmt (dump_file
, elt
->stmt
, 0, 0);
503 /* If we know the exit will be taken after peeling, update. */
504 else if (elt
->is_exit
505 && elt
->bound
.ule (double_int::from_uhwi (npeeled
)))
507 basic_block bb
= gimple_bb (elt
->stmt
);
508 edge exit_edge
= EDGE_SUCC (bb
, 0);
510 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
512 fprintf (dump_file
, "Forced exit to be taken: ");
513 print_gimple_stmt (dump_file
, elt
->stmt
, 0, 0);
515 if (!loop_exit_edge_p (loop
, exit_edge
))
516 exit_edge
= EDGE_SUCC (bb
, 1);
517 gcc_checking_assert (loop_exit_edge_p (loop
, exit_edge
));
518 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
519 gimple_cond_make_true (elt
->stmt
);
521 gimple_cond_make_false (elt
->stmt
);
522 update_stmt (elt
->stmt
);
529 /* Remove all exits that are known to be never taken because of the loop bound
533 remove_redundant_iv_tests (struct loop
*loop
)
535 struct nb_iter_bound
*elt
;
536 bool changed
= false;
538 if (!loop
->any_upper_bound
)
540 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
542 /* Exit is pointless if it won't be taken before loop reaches
544 if (elt
->is_exit
&& loop
->any_upper_bound
545 && loop
->nb_iterations_upper_bound
.ult (elt
->bound
))
547 basic_block bb
= gimple_bb (elt
->stmt
);
548 edge exit_edge
= EDGE_SUCC (bb
, 0);
549 struct tree_niter_desc niter
;
551 if (!loop_exit_edge_p (loop
, exit_edge
))
552 exit_edge
= EDGE_SUCC (bb
, 1);
554 /* Only when we know the actual number of iterations, not
555 just a bound, we can remove the exit. */
556 if (!number_of_iterations_exit (loop
, exit_edge
,
557 &niter
, false, false)
558 || !integer_onep (niter
.assumptions
)
559 || !integer_zerop (niter
.may_be_zero
)
561 || TREE_CODE (niter
.niter
) != INTEGER_CST
562 || !loop
->nb_iterations_upper_bound
.ult
563 (tree_to_double_int (niter
.niter
)))
566 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
568 fprintf (dump_file
, "Removed pointless exit: ");
569 print_gimple_stmt (dump_file
, elt
->stmt
, 0, 0);
571 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
572 gimple_cond_make_false (elt
->stmt
);
574 gimple_cond_make_true (elt
->stmt
);
575 update_stmt (elt
->stmt
);
582 /* Stores loops that will be unlooped after we process whole loop tree. */
583 static vec
<loop_p
> loops_to_unloop
;
584 static vec
<int> loops_to_unloop_nunroll
;
586 /* Cancel all fully unrolled loops by putting __builtin_unreachable
588 We do it after all unrolling since unlooping moves basic blocks
589 across loop boundaries trashing loop closed SSA form as well
590 as SCEV info needed to be intact during unrolling.
592 IRRED_INVALIDATED is used to bookkeep if information about
593 irreducible regions may become invalid as a result
594 of the transformation.
595 LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case
596 when we need to go into loop closed SSA form. */
599 unloop_loops (bitmap loop_closed_ssa_invalidated
,
600 bool *irred_invalidated
)
602 while (loops_to_unloop
.length ())
604 struct loop
*loop
= loops_to_unloop
.pop ();
605 int n_unroll
= loops_to_unloop_nunroll
.pop ();
606 basic_block latch
= loop
->latch
;
607 edge latch_edge
= loop_latch_edge (loop
);
608 int flags
= latch_edge
->flags
;
609 location_t locus
= latch_edge
->goto_locus
;
611 gimple_stmt_iterator gsi
;
613 remove_exits_and_undefined_stmts (loop
, n_unroll
);
615 /* Unloop destroys the latch edge. */
616 unloop (loop
, irred_invalidated
, loop_closed_ssa_invalidated
);
618 /* Create new basic block for the latch edge destination and wire
620 stmt
= gimple_build_call (builtin_decl_implicit (BUILT_IN_UNREACHABLE
), 0);
621 latch_edge
= make_edge (latch
, create_basic_block (NULL
, NULL
, latch
), flags
);
622 latch_edge
->probability
= 0;
623 latch_edge
->count
= 0;
624 latch_edge
->flags
|= flags
;
625 latch_edge
->goto_locus
= locus
;
627 latch_edge
->dest
->loop_father
= current_loops
->tree_root
;
628 latch_edge
->dest
->count
= 0;
629 latch_edge
->dest
->frequency
= 0;
630 set_immediate_dominator (CDI_DOMINATORS
, latch_edge
->dest
, latch_edge
->src
);
632 gsi
= gsi_start_bb (latch_edge
->dest
);
633 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
635 loops_to_unloop
.release ();
636 loops_to_unloop_nunroll
.release ();
639 /* Tries to unroll LOOP completely, i.e. NITER times.
640 UL determines which loops we are allowed to unroll.
641 EXIT is the exit of the loop that should be eliminated.
642 MAXITER specfy bound on number of iterations, -1 if it is
643 not known or too large for HOST_WIDE_INT. The location
644 LOCUS corresponding to the loop is used when emitting
645 a summary of the unroll to the dump file. */
648 try_unroll_loop_completely (struct loop
*loop
,
649 edge exit
, tree niter
,
650 enum unroll_level ul
,
651 HOST_WIDE_INT maxiter
,
654 unsigned HOST_WIDE_INT n_unroll
, ninsns
, max_unroll
, unr_insns
;
656 struct loop_size size
;
657 bool n_unroll_found
= false;
658 edge edge_to_cancel
= NULL
;
660 /* See if we proved number of iterations to be low constant.
662 EXIT is an edge that will be removed in all but last iteration of
665 EDGE_TO_CACNEL is an edge that will be removed from the last iteration
666 of the unrolled sequence and is expected to make the final loop not
669 If the number of execution of loop is determined by standard induction
670 variable test, then EXIT and EDGE_TO_CANCEL are the two edges leaving
672 if (host_integerp (niter
, 1))
674 n_unroll
= tree_low_cst (niter
, 1);
675 n_unroll_found
= true;
676 edge_to_cancel
= EDGE_SUCC (exit
->src
, 0);
677 if (edge_to_cancel
== exit
)
678 edge_to_cancel
= EDGE_SUCC (exit
->src
, 1);
680 /* We do not know the number of iterations and thus we can not eliminate
685 /* See if we can improve our estimate by using recorded loop bounds. */
687 && (!n_unroll_found
|| (unsigned HOST_WIDE_INT
)maxiter
< n_unroll
))
690 n_unroll_found
= true;
691 /* Loop terminates before the IV variable test, so we can not
692 remove it in the last iteration. */
693 edge_to_cancel
= NULL
;
699 max_unroll
= PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
);
700 if (n_unroll
> max_unroll
)
704 edge_to_cancel
= loop_edge_to_cancel (loop
);
712 vec
<edge
> to_remove
= vNULL
;
713 if (ul
== UL_SINGLE_ITER
)
716 large
= tree_estimate_loop_size
717 (loop
, exit
, edge_to_cancel
, &size
,
718 PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
));
719 ninsns
= size
.overall
;
722 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
723 fprintf (dump_file
, "Not unrolling loop %d: it is too large.\n",
728 unr_insns
= estimated_unrolled_size (&size
, n_unroll
);
729 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
731 fprintf (dump_file
, " Loop size: %d\n", (int) ninsns
);
732 fprintf (dump_file
, " Estimated size after unrolling: %d\n",
736 /* If the code is going to shrink, we don't need to be extra cautious
737 on guessing if the unrolling is going to be profitable. */
739 /* If there is IV variable that will become constant, we save
740 one instruction in the loop prologue we do not account
742 <= ninsns
+ (size
.constant_iv
!= false))
744 /* We unroll only inner loops, because we do not consider it profitable
745 otheriwse. We still can cancel loopback edge of not rolling loop;
746 this is always a good idea. */
747 else if (ul
== UL_NO_GROWTH
)
749 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
750 fprintf (dump_file
, "Not unrolling loop %d: size would grow.\n",
754 /* Outer loops tend to be less interesting candidates for complette
755 unrolling unless we can do a lot of propagation into the inner loop
756 body. For now we disable outer loop unrolling when the code would
758 else if (loop
->inner
)
760 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
761 fprintf (dump_file
, "Not unrolling loop %d: "
762 "it is not innermost and code would grow.\n",
766 /* If there is call on a hot path through the loop, then
767 there is most probably not much to optimize. */
768 else if (size
.num_non_pure_calls_on_hot_path
)
770 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
771 fprintf (dump_file
, "Not unrolling loop %d: "
772 "contains call and code would grow.\n",
776 /* If there is pure/const call in the function, then we
777 can still optimize the unrolled loop body if it contains
778 some other interesting code than the calls and code
779 storing or cumulating the return value. */
780 else if (size
.num_pure_calls_on_hot_path
781 /* One IV increment, one test, one ivtmp store
782 and one usefull stmt. That is about minimal loop
784 && (size
.non_call_stmts_on_hot_path
785 <= 3 + size
.num_pure_calls_on_hot_path
))
787 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
788 fprintf (dump_file
, "Not unrolling loop %d: "
789 "contains just pure calls and code would grow.\n",
793 /* Complette unrolling is major win when control flow is removed and
794 one big basic block is created. If the loop contains control flow
795 the optimization may still be a win because of eliminating the loop
796 overhead but it also may blow the branch predictor tables.
797 Limit number of branches on the hot path through the peeled
799 else if (size
.num_branches_on_hot_path
* (int)n_unroll
800 > PARAM_VALUE (PARAM_MAX_PEEL_BRANCHES
))
802 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
803 fprintf (dump_file
, "Not unrolling loop %d: "
804 " number of branches on hot path in the unrolled sequence"
805 " reach --param max-peel-branches limit.\n",
810 > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
))
812 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
813 fprintf (dump_file
, "Not unrolling loop %d: "
814 "(--param max-completely-peeled-insns limit reached).\n",
819 initialize_original_copy_tables ();
820 wont_exit
= sbitmap_alloc (n_unroll
+ 1);
821 bitmap_ones (wont_exit
);
822 bitmap_clear_bit (wont_exit
, 0);
824 if (!gimple_duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
827 DLTHE_FLAG_UPDATE_FREQ
828 | DLTHE_FLAG_COMPLETTE_PEEL
))
830 free_original_copy_tables ();
832 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
833 fprintf (dump_file
, "Failed to duplicate the loop\n");
837 FOR_EACH_VEC_ELT (to_remove
, i
, e
)
839 bool ok
= remove_path (e
);
843 to_remove
.release ();
845 free_original_copy_tables ();
849 /* Remove the conditional from the last copy of the loop. */
852 cond
= last_stmt (edge_to_cancel
->src
);
853 if (edge_to_cancel
->flags
& EDGE_TRUE_VALUE
)
854 gimple_cond_make_false (cond
);
856 gimple_cond_make_true (cond
);
858 /* Do not remove the path. Doing so may remove outer loop
859 and confuse bookkeeping code in tree_unroll_loops_completelly. */
862 /* Store the loop for later unlooping and exit removal. */
863 loops_to_unloop
.safe_push (loop
);
864 loops_to_unloop_nunroll
.safe_push (n_unroll
);
866 if (dump_enabled_p ())
869 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
870 "Turned loop into non-loop; it never loops.\n");
873 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
874 "Completely unroll loop %d times", (int)n_unroll
);
876 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
,
877 " (header execution count %d)",
878 (int)loop
->header
->count
);
879 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, "\n");
883 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
886 fprintf (dump_file
, "Exit condition of peeled iterations was "
889 fprintf (dump_file
, "Last iteration exit edge was proved true.\n");
891 fprintf (dump_file
, "Latch of last iteration was marked by "
892 "__builtin_unreachable ().\n");
898 /* Adds a canonical induction variable to LOOP if suitable.
899 CREATE_IV is true if we may create a new iv. UL determines
900 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
901 to determine the number of iterations of a loop by direct evaluation.
902 Returns true if cfg is changed. */
905 canonicalize_loop_induction_variables (struct loop
*loop
,
906 bool create_iv
, enum unroll_level ul
,
911 HOST_WIDE_INT maxiter
;
912 bool modified
= false;
913 location_t locus
= UNKNOWN_LOCATION
;
915 niter
= number_of_latch_executions (loop
);
916 exit
= single_exit (loop
);
917 if (TREE_CODE (niter
) == INTEGER_CST
)
918 locus
= gimple_location (last_stmt (exit
->src
));
921 /* If the loop has more than one exit, try checking all of them
922 for # of iterations determinable through scev. */
924 niter
= find_loop_niter (loop
, &exit
);
926 /* Finally if everything else fails, try brute force evaluation. */
928 && (chrec_contains_undetermined (niter
)
929 || TREE_CODE (niter
) != INTEGER_CST
))
930 niter
= find_loop_niter_by_eval (loop
, &exit
);
933 locus
= gimple_location (last_stmt (exit
->src
));
935 if (TREE_CODE (niter
) != INTEGER_CST
)
939 /* We work exceptionally hard here to estimate the bound
940 by find_loop_niter_by_eval. Be sure to keep it for future. */
941 if (niter
&& TREE_CODE (niter
) == INTEGER_CST
)
943 record_niter_bound (loop
, tree_to_double_int (niter
),
944 exit
== single_likely_exit (loop
), true);
947 /* Force re-computation of loop bounds so we can remove redundant exits. */
948 maxiter
= max_loop_iterations_int (loop
);
950 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
951 && TREE_CODE (niter
) == INTEGER_CST
)
953 fprintf (dump_file
, "Loop %d iterates ", loop
->num
);
954 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
955 fprintf (dump_file
, " times.\n");
957 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
960 fprintf (dump_file
, "Loop %d iterates at most %i times.\n", loop
->num
,
964 /* Remove exits that are known to be never taken based on loop bound.
965 Needs to be called after compilation of max_loop_iterations_int that
966 populates the loop bounds. */
967 modified
|= remove_redundant_iv_tests (loop
);
969 if (try_unroll_loop_completely (loop
, exit
, niter
, ul
, maxiter
, locus
))
973 && niter
&& !chrec_contains_undetermined (niter
)
974 && exit
&& just_once_each_iteration_p (loop
, exit
->src
))
975 create_canonical_iv (loop
, exit
, niter
);
980 /* The main entry point of the pass. Adds canonical induction variables
981 to the suitable loops. */
984 canonicalize_induction_variables (void)
988 bool changed
= false;
989 bool irred_invalidated
= false;
990 bitmap loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
992 free_numbers_of_iterations_estimates ();
993 estimate_numbers_of_iterations ();
995 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
997 changed
|= canonicalize_loop_induction_variables (loop
,
998 true, UL_SINGLE_ITER
,
1001 gcc_assert (!need_ssa_update_p (cfun
));
1003 unloop_loops (loop_closed_ssa_invalidated
, &irred_invalidated
);
1004 if (irred_invalidated
1005 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1006 mark_irreducible_loops ();
1008 /* Clean up the information about numbers of iterations, since brute force
1009 evaluation could reveal new information. */
1012 if (!bitmap_empty_p (loop_closed_ssa_invalidated
))
1014 gcc_checking_assert (loops_state_satisfies_p (LOOP_CLOSED_SSA
));
1015 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1017 BITMAP_FREE (loop_closed_ssa_invalidated
);
1020 return TODO_cleanup_cfg
;
1024 /* Propagate VAL into all uses of SSA_NAME. */
1027 propagate_into_all_uses (tree ssa_name
, tree val
)
1029 imm_use_iterator iter
;
1032 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, ssa_name
)
1034 gimple_stmt_iterator use_stmt_gsi
= gsi_for_stmt (use_stmt
);
1037 FOR_EACH_IMM_USE_ON_STMT (use
, iter
)
1040 if (is_gimple_assign (use_stmt
)
1041 && get_gimple_rhs_class (gimple_assign_rhs_code (use_stmt
))
1042 == GIMPLE_SINGLE_RHS
)
1044 tree rhs
= gimple_assign_rhs1 (use_stmt
);
1046 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1047 recompute_tree_invariant_for_addr_expr (rhs
);
1050 fold_stmt_inplace (&use_stmt_gsi
);
1051 update_stmt (use_stmt
);
1052 maybe_clean_or_replace_eh_stmt (use_stmt
, use_stmt
);
1056 /* Propagate constant SSA_NAMEs defined in basic block BB. */
1059 propagate_constants_for_unrolling (basic_block bb
)
1061 gimple_stmt_iterator gsi
;
1063 /* Look for degenerate PHI nodes with constant argument. */
1064 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); )
1066 gimple phi
= gsi_stmt (gsi
);
1067 tree result
= gimple_phi_result (phi
);
1068 tree arg
= gimple_phi_arg_def (phi
, 0);
1070 if (gimple_phi_num_args (phi
) == 1 && TREE_CODE (arg
) == INTEGER_CST
)
1072 propagate_into_all_uses (result
, arg
);
1073 gsi_remove (&gsi
, true);
1074 release_ssa_name (result
);
1080 /* Look for assignments to SSA names with constant RHS. */
1081 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
1083 gimple stmt
= gsi_stmt (gsi
);
1086 if (is_gimple_assign (stmt
)
1087 && (lhs
= gimple_assign_lhs (stmt
), TREE_CODE (lhs
) == SSA_NAME
)
1088 && gimple_assign_rhs_code (stmt
) == INTEGER_CST
)
1090 propagate_into_all_uses (lhs
, gimple_assign_rhs1 (stmt
));
1091 gsi_remove (&gsi
, true);
1092 release_ssa_name (lhs
);
1099 /* Unroll LOOPS completely if they iterate just few times. Unless
1100 MAY_INCREASE_SIZE is true, perform the unrolling only if the
1101 size of the code does not increase. */
1104 tree_unroll_loops_completely (bool may_increase_size
, bool unroll_outer
)
1106 vec
<loop_p
, va_stack
> father_stack
;
1110 enum unroll_level ul
;
1112 bool irred_invalidated
= false;
1114 vec_stack_alloc (loop_p
, father_stack
, 16);
1118 bitmap loop_closed_ssa_invalidated
= NULL
;
1120 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1121 loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
1123 free_numbers_of_iterations_estimates ();
1124 estimate_numbers_of_iterations ();
1126 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1128 struct loop
*loop_father
= loop_outer (loop
);
1130 if (may_increase_size
&& optimize_loop_nest_for_speed_p (loop
)
1131 /* Unroll outermost loops only if asked to do so or they do
1132 not cause code growth. */
1133 && (unroll_outer
|| loop_outer (loop_father
)))
1138 if (canonicalize_loop_induction_variables
1139 (loop
, false, ul
, !flag_tree_loop_ivcanon
))
1142 /* If we'll continue unrolling, we need to propagate constants
1143 within the new basic blocks to fold away induction variable
1144 computations; otherwise, the size might blow up before the
1145 iteration is complete and the IR eventually cleaned up. */
1146 if (loop_outer (loop_father
) && !loop_father
->aux
)
1148 father_stack
.safe_push (loop_father
);
1149 loop_father
->aux
= loop_father
;
1159 /* Be sure to skip unlooped loops while procesing father_stack
1161 FOR_EACH_VEC_ELT (loops_to_unloop
, i
, iter
)
1162 (*iter
)->aux
= NULL
;
1163 FOR_EACH_VEC_ELT (father_stack
, i
, iter
)
1166 unloop_loops (loop_closed_ssa_invalidated
, &irred_invalidated
);
1168 /* We can not use TODO_update_ssa_no_phi because VOPS gets confused. */
1169 if (loop_closed_ssa_invalidated
1170 && !bitmap_empty_p (loop_closed_ssa_invalidated
))
1171 rewrite_into_loop_closed_ssa (loop_closed_ssa_invalidated
,
1174 update_ssa (TODO_update_ssa
);
1176 /* Propagate the constants within the new basic blocks. */
1177 FOR_EACH_VEC_ELT (father_stack
, i
, iter
)
1181 basic_block
*body
= get_loop_body_in_dom_order (*iter
);
1182 for (j
= 0; j
< (*iter
)->num_nodes
; j
++)
1183 propagate_constants_for_unrolling (body
[j
]);
1185 (*iter
)->aux
= NULL
;
1187 father_stack
.truncate (0);
1189 /* This will take care of removing completely unrolled loops
1190 from the loop structures so we can continue unrolling now
1192 if (cleanup_tree_cfg ())
1193 update_ssa (TODO_update_ssa_only_virtuals
);
1195 /* Clean up the information about numbers of iterations, since
1196 complete unrolling might have invalidated it. */
1198 #ifdef ENABLE_CHECKING
1199 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1200 verify_loop_closed_ssa (true);
1203 if (loop_closed_ssa_invalidated
)
1204 BITMAP_FREE (loop_closed_ssa_invalidated
);
1207 && ++iteration
<= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS
));
1209 father_stack
.release ();
1211 if (irred_invalidated
1212 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1213 mark_irreducible_loops ();