1 /* Induction variable canonicalization and loop peeling.
2 Copyright (C) 2004-2016 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
32 - complete unrolling (or peeling) when the loops is rolling few enough
34 - simple peeling (i.e. copying few initial iterations prior the loop)
35 when number of iteration estimate is known (typically by the profile
40 #include "coretypes.h"
45 #include "tree-pass.h"
48 #include "gimple-pretty-print.h"
49 #include "fold-const.h"
51 #include "gimple-fold.h"
53 #include "gimple-iterator.h"
55 #include "tree-ssa-loop-manip.h"
56 #include "tree-ssa-loop-niter.h"
57 #include "tree-ssa-loop.h"
58 #include "tree-into-ssa.h"
60 #include "tree-chrec.h"
61 #include "tree-scalar-evolution.h"
63 #include "tree-inline.h"
64 #include "tree-cfgcleanup.h"
67 /* Specifies types of loops that may be unrolled. */
71 UL_SINGLE_ITER
, /* Only loops that exit immediately in the first
73 UL_NO_GROWTH
, /* Only loops whose unrolling will not cause increase
75 UL_ALL
/* All suitable loops. */
78 /* Adds a canonical induction variable to LOOP iterating NITER times. EXIT
79 is the exit edge whose condition is replaced. */
82 create_canonical_iv (struct loop
*loop
, edge exit
, tree niter
)
87 gimple_stmt_iterator incr_at
;
90 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
92 fprintf (dump_file
, "Added canonical iv to loop %d, ", loop
->num
);
93 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
94 fprintf (dump_file
, " iterations.\n");
97 cond
= as_a
<gcond
*> (last_stmt (exit
->src
));
98 in
= EDGE_SUCC (exit
->src
, 0);
100 in
= EDGE_SUCC (exit
->src
, 1);
102 /* Note that we do not need to worry about overflows, since
103 type of niter is always unsigned and all comparisons are
104 just for equality/nonequality -- i.e. everything works
105 with a modulo arithmetics. */
107 type
= TREE_TYPE (niter
);
108 niter
= fold_build2 (PLUS_EXPR
, type
,
110 build_int_cst (type
, 1));
111 incr_at
= gsi_last_bb (in
->src
);
113 build_int_cst (type
, -1),
115 &incr_at
, false, NULL
, &var
);
117 cmp
= (exit
->flags
& EDGE_TRUE_VALUE
) ? EQ_EXPR
: NE_EXPR
;
118 gimple_cond_set_code (cond
, cmp
);
119 gimple_cond_set_lhs (cond
, var
);
120 gimple_cond_set_rhs (cond
, build_int_cst (type
, 0));
124 /* Describe size of loop as detected by tree_estimate_loop_size. */
127 /* Number of instructions in the loop. */
130 /* Number of instructions that will be likely optimized out in
131 peeled iterations of loop (i.e. computation based on induction
132 variable where induction variable starts at known constant.) */
133 int eliminated_by_peeling
;
135 /* Same statistics for last iteration of loop: it is smaller because
136 instructions after exit are not executed. */
138 int last_iteration_eliminated_by_peeling
;
140 /* If some IV computation will become constant. */
143 /* Number of call stmts that are not a builtin and are pure or const
144 present on the hot path. */
145 int num_pure_calls_on_hot_path
;
146 /* Number of call stmts that are not a builtin and are not pure nor const
147 present on the hot path. */
148 int num_non_pure_calls_on_hot_path
;
149 /* Number of statements other than calls in the loop. */
150 int non_call_stmts_on_hot_path
;
151 /* Number of branches seen on the hot path. */
152 int num_branches_on_hot_path
;
155 /* Return true if OP in STMT will be constant after peeling LOOP. */
158 constant_after_peeling (tree op
, gimple
*stmt
, struct loop
*loop
)
162 if (is_gimple_min_invariant (op
))
165 /* We can still fold accesses to constant arrays when index is known. */
166 if (TREE_CODE (op
) != SSA_NAME
)
170 /* First make fast look if we see constant array inside. */
171 while (handled_component_p (base
))
172 base
= TREE_OPERAND (base
, 0);
174 && ctor_for_folding (base
) != error_mark_node
)
175 || CONSTANT_CLASS_P (base
))
177 /* If so, see if we understand all the indices. */
179 while (handled_component_p (base
))
181 if (TREE_CODE (base
) == ARRAY_REF
182 && !constant_after_peeling (TREE_OPERAND (base
, 1), stmt
, loop
))
184 base
= TREE_OPERAND (base
, 0);
191 /* Induction variables are constants. */
192 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op
, &iv
, false))
194 if (!is_gimple_min_invariant (iv
.base
))
196 if (!is_gimple_min_invariant (iv
.step
))
201 /* Computes an estimated number of insns in LOOP.
202 EXIT (if non-NULL) is an exite edge that will be eliminated in all but last
203 iteration of the loop.
204 EDGE_TO_CANCEL (if non-NULL) is an non-exit edge eliminated in the last iteration
206 Return results in SIZE, estimate benefits for complete unrolling exiting by EXIT.
207 Stop estimating after UPPER_BOUND is met. Return true in this case. */
210 tree_estimate_loop_size (struct loop
*loop
, edge exit
, edge edge_to_cancel
,
211 struct loop_size
*size
, int upper_bound
)
213 basic_block
*body
= get_loop_body (loop
);
214 gimple_stmt_iterator gsi
;
217 vec
<basic_block
> path
= get_loop_hot_path (loop
);
220 size
->eliminated_by_peeling
= 0;
221 size
->last_iteration
= 0;
222 size
->last_iteration_eliminated_by_peeling
= 0;
223 size
->num_pure_calls_on_hot_path
= 0;
224 size
->num_non_pure_calls_on_hot_path
= 0;
225 size
->non_call_stmts_on_hot_path
= 0;
226 size
->num_branches_on_hot_path
= 0;
227 size
->constant_iv
= 0;
229 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
230 fprintf (dump_file
, "Estimating sizes for loop %i\n", loop
->num
);
231 for (i
= 0; i
< loop
->num_nodes
; i
++)
233 if (edge_to_cancel
&& body
[i
] != edge_to_cancel
->src
234 && dominated_by_p (CDI_DOMINATORS
, body
[i
], edge_to_cancel
->src
))
238 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
239 fprintf (dump_file
, " BB: %i, after_exit: %i\n", body
[i
]->index
,
242 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
244 gimple
*stmt
= gsi_stmt (gsi
);
245 int num
= estimate_num_insns (stmt
, &eni_size_weights
);
246 bool likely_eliminated
= false;
247 bool likely_eliminated_last
= false;
248 bool likely_eliminated_peeled
= false;
250 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
252 fprintf (dump_file
, " size: %3i ", num
);
253 print_gimple_stmt (dump_file
, gsi_stmt (gsi
), 0, 0);
256 /* Look for reasons why we might optimize this stmt away. */
258 if (!gimple_has_side_effects (stmt
))
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 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 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
),
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
))
298 " Constant expression will be folded away.\n");
299 likely_eliminated
= true;
302 else if ((gimple_code (stmt
) == GIMPLE_COND
303 && constant_after_peeling (gimple_cond_lhs (stmt
), stmt
,
305 && constant_after_peeling (gimple_cond_rhs (stmt
), stmt
,
307 /* We don't simplify all constant compares so make sure
308 they are not both constant already. See PR70288. */
309 && (! is_gimple_min_invariant (gimple_cond_lhs (stmt
))
310 || ! is_gimple_min_invariant
311 (gimple_cond_rhs (stmt
))))
312 || (gimple_code (stmt
) == GIMPLE_SWITCH
313 && constant_after_peeling (gimple_switch_index (
317 && ! is_gimple_min_invariant
319 (as_a
<gswitch
*> (stmt
)))))
321 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
322 fprintf (dump_file
, " Constant conditional.\n");
323 likely_eliminated
= true;
327 size
->overall
+= num
;
328 if (likely_eliminated
|| likely_eliminated_peeled
)
329 size
->eliminated_by_peeling
+= num
;
332 size
->last_iteration
+= num
;
333 if (likely_eliminated
|| likely_eliminated_last
)
334 size
->last_iteration_eliminated_by_peeling
+= num
;
336 if ((size
->overall
* 3 / 2 - size
->eliminated_by_peeling
337 - size
->last_iteration_eliminated_by_peeling
) > upper_bound
)
345 while (path
.length ())
347 basic_block bb
= path
.pop ();
348 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
350 gimple
*stmt
= gsi_stmt (gsi
);
351 if (gimple_code (stmt
) == GIMPLE_CALL
352 && !gimple_inexpensive_call_p (as_a
<gcall
*> (stmt
)))
354 int flags
= gimple_call_flags (stmt
);
355 if (flags
& (ECF_PURE
| ECF_CONST
))
356 size
->num_pure_calls_on_hot_path
++;
358 size
->num_non_pure_calls_on_hot_path
++;
359 size
->num_branches_on_hot_path
++;
361 /* Count inexpensive calls as non-calls, because they will likely
363 else if (gimple_code (stmt
) != GIMPLE_DEBUG
)
364 size
->non_call_stmts_on_hot_path
++;
365 if (((gimple_code (stmt
) == GIMPLE_COND
366 && (!constant_after_peeling (gimple_cond_lhs (stmt
), stmt
, loop
)
367 || constant_after_peeling (gimple_cond_rhs (stmt
), stmt
,
369 || (gimple_code (stmt
) == GIMPLE_SWITCH
370 && !constant_after_peeling (gimple_switch_index (
371 as_a
<gswitch
*> (stmt
)),
373 && (!exit
|| bb
!= exit
->src
))
374 size
->num_branches_on_hot_path
++;
378 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
379 fprintf (dump_file
, "size: %i-%i, last_iteration: %i-%i\n", size
->overall
,
380 size
->eliminated_by_peeling
, size
->last_iteration
,
381 size
->last_iteration_eliminated_by_peeling
);
387 /* Estimate number of insns of completely unrolled loop.
388 It is (NUNROLL + 1) * size of loop body with taking into account
389 the fact that in last copy everything after exit conditional
390 is dead and that some instructions will be eliminated after
393 Loop body is likely going to simplify further, this is difficult
394 to guess, we just decrease the result by 1/3. */
396 static unsigned HOST_WIDE_INT
397 estimated_unrolled_size (struct loop_size
*size
,
398 unsigned HOST_WIDE_INT nunroll
)
400 HOST_WIDE_INT unr_insns
= ((nunroll
)
401 * (HOST_WIDE_INT
) (size
->overall
402 - size
->eliminated_by_peeling
));
405 unr_insns
+= size
->last_iteration
- size
->last_iteration_eliminated_by_peeling
;
407 unr_insns
= unr_insns
* 2 / 3;
414 /* Loop LOOP is known to not loop. See if there is an edge in the loop
415 body that can be remove to make the loop to always exit and at
416 the same time it does not make any code potentially executed
417 during the last iteration dead.
419 After complete unrolling we still may get rid of the conditional
420 on the exit in the last copy even if we have no idea what it does.
421 This is quite common case for loops of form
427 Here we prove the loop to iterate 5 times but we do not know
428 it from induction variable.
430 For now we handle only simple case where there is exit condition
431 just before the latch block and the latch block contains no statements
432 with side effect that may otherwise terminate the execution of loop
433 (such as by EH or by terminating the program or longjmp).
435 In the general case we may want to cancel the paths leading to statements
436 loop-niter identified as having undefined effect in the last iteration.
437 The other cases are hopefully rare and will be cleaned up later. */
440 loop_edge_to_cancel (struct loop
*loop
)
445 gimple_stmt_iterator gsi
;
447 /* We want only one predecestor of the loop. */
448 if (EDGE_COUNT (loop
->latch
->preds
) > 1)
451 exits
= get_loop_exit_edges (loop
);
453 FOR_EACH_VEC_ELT (exits
, i
, edge_to_cancel
)
455 /* Find the other edge than the loop exit
456 leaving the conditoinal. */
457 if (EDGE_COUNT (edge_to_cancel
->src
->succs
) != 2)
459 if (EDGE_SUCC (edge_to_cancel
->src
, 0) == edge_to_cancel
)
460 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 1);
462 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 0);
464 /* We only can handle conditionals. */
465 if (!(edge_to_cancel
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
468 /* We should never have conditionals in the loop latch. */
469 gcc_assert (edge_to_cancel
->dest
!= loop
->header
);
471 /* Check that it leads to loop latch. */
472 if (edge_to_cancel
->dest
!= loop
->latch
)
477 /* Verify that the code in loop latch does nothing that may end program
478 execution without really reaching the exit. This may include
479 non-pure/const function calls, EH statements, volatile ASMs etc. */
480 for (gsi
= gsi_start_bb (loop
->latch
); !gsi_end_p (gsi
); gsi_next (&gsi
))
481 if (gimple_has_side_effects (gsi_stmt (gsi
)))
483 return edge_to_cancel
;
489 /* Remove all tests for exits that are known to be taken after LOOP was
490 peeled NPEELED times. Put gcc_unreachable before every statement
491 known to not be executed. */
494 remove_exits_and_undefined_stmts (struct loop
*loop
, unsigned int npeeled
)
496 struct nb_iter_bound
*elt
;
497 bool changed
= false;
499 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
501 /* If statement is known to be undefined after peeling, turn it
502 into unreachable (or trap when debugging experience is supposed
505 && wi::ltu_p (elt
->bound
, npeeled
))
507 gimple_stmt_iterator gsi
= gsi_for_stmt (elt
->stmt
);
508 gcall
*stmt
= gimple_build_call
509 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
), 0);
510 gimple_set_location (stmt
, gimple_location (elt
->stmt
));
511 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
512 split_block (gimple_bb (stmt
), stmt
);
514 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
516 fprintf (dump_file
, "Forced statement unreachable: ");
517 print_gimple_stmt (dump_file
, elt
->stmt
, 0, 0);
520 /* If we know the exit will be taken after peeling, update. */
521 else if (elt
->is_exit
522 && wi::leu_p (elt
->bound
, npeeled
))
524 basic_block bb
= gimple_bb (elt
->stmt
);
525 edge exit_edge
= EDGE_SUCC (bb
, 0);
527 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
529 fprintf (dump_file
, "Forced exit to be taken: ");
530 print_gimple_stmt (dump_file
, elt
->stmt
, 0, 0);
532 if (!loop_exit_edge_p (loop
, exit_edge
))
533 exit_edge
= EDGE_SUCC (bb
, 1);
534 gcc_checking_assert (loop_exit_edge_p (loop
, exit_edge
));
535 gcond
*cond_stmt
= as_a
<gcond
*> (elt
->stmt
);
536 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
537 gimple_cond_make_true (cond_stmt
);
539 gimple_cond_make_false (cond_stmt
);
540 update_stmt (cond_stmt
);
547 /* Remove all exits that are known to be never taken because of the loop bound
551 remove_redundant_iv_tests (struct loop
*loop
)
553 struct nb_iter_bound
*elt
;
554 bool changed
= false;
556 if (!loop
->any_upper_bound
)
558 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
560 /* Exit is pointless if it won't be taken before loop reaches
562 if (elt
->is_exit
&& loop
->any_upper_bound
563 && wi::ltu_p (loop
->nb_iterations_upper_bound
, elt
->bound
))
565 basic_block bb
= gimple_bb (elt
->stmt
);
566 edge exit_edge
= EDGE_SUCC (bb
, 0);
567 struct tree_niter_desc niter
;
569 if (!loop_exit_edge_p (loop
, exit_edge
))
570 exit_edge
= EDGE_SUCC (bb
, 1);
572 /* Only when we know the actual number of iterations, not
573 just a bound, we can remove the exit. */
574 if (!number_of_iterations_exit (loop
, exit_edge
,
575 &niter
, false, false)
576 || !integer_onep (niter
.assumptions
)
577 || !integer_zerop (niter
.may_be_zero
)
579 || TREE_CODE (niter
.niter
) != INTEGER_CST
580 || !wi::ltu_p (loop
->nb_iterations_upper_bound
,
581 wi::to_widest (niter
.niter
)))
584 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
586 fprintf (dump_file
, "Removed pointless exit: ");
587 print_gimple_stmt (dump_file
, elt
->stmt
, 0, 0);
589 gcond
*cond_stmt
= as_a
<gcond
*> (elt
->stmt
);
590 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
591 gimple_cond_make_false (cond_stmt
);
593 gimple_cond_make_true (cond_stmt
);
594 update_stmt (cond_stmt
);
601 /* Stores loops that will be unlooped and edges that will be removed
602 after we process whole loop tree. */
603 static vec
<loop_p
> loops_to_unloop
;
604 static vec
<int> loops_to_unloop_nunroll
;
605 static vec
<edge
> edges_to_remove
;
606 /* Stores loops that has been peeled. */
607 static bitmap peeled_loops
;
609 /* Cancel all fully unrolled loops by putting __builtin_unreachable
611 We do it after all unrolling since unlooping moves basic blocks
612 across loop boundaries trashing loop closed SSA form as well
613 as SCEV info needed to be intact during unrolling.
615 IRRED_INVALIDATED is used to bookkeep if information about
616 irreducible regions may become invalid as a result
617 of the transformation.
618 LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case
619 when we need to go into loop closed SSA form. */
622 unloop_loops (bitmap loop_closed_ssa_invalidated
,
623 bool *irred_invalidated
)
625 while (loops_to_unloop
.length ())
627 struct loop
*loop
= loops_to_unloop
.pop ();
628 int n_unroll
= loops_to_unloop_nunroll
.pop ();
629 basic_block latch
= loop
->latch
;
630 edge latch_edge
= loop_latch_edge (loop
);
631 int flags
= latch_edge
->flags
;
632 location_t locus
= latch_edge
->goto_locus
;
634 gimple_stmt_iterator gsi
;
636 remove_exits_and_undefined_stmts (loop
, n_unroll
);
638 /* Unloop destroys the latch edge. */
639 unloop (loop
, irred_invalidated
, loop_closed_ssa_invalidated
);
641 /* Create new basic block for the latch edge destination and wire
643 stmt
= gimple_build_call (builtin_decl_implicit (BUILT_IN_UNREACHABLE
), 0);
644 latch_edge
= make_edge (latch
, create_basic_block (NULL
, NULL
, latch
), flags
);
645 latch_edge
->probability
= 0;
646 latch_edge
->count
= 0;
647 latch_edge
->flags
|= flags
;
648 latch_edge
->goto_locus
= locus
;
650 latch_edge
->dest
->loop_father
= current_loops
->tree_root
;
651 latch_edge
->dest
->count
= 0;
652 latch_edge
->dest
->frequency
= 0;
653 set_immediate_dominator (CDI_DOMINATORS
, latch_edge
->dest
, latch_edge
->src
);
655 gsi
= gsi_start_bb (latch_edge
->dest
);
656 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
658 loops_to_unloop
.release ();
659 loops_to_unloop_nunroll
.release ();
661 /* Remove edges in peeled copies. */
664 FOR_EACH_VEC_ELT (edges_to_remove
, i
, e
)
666 bool ok
= remove_path (e
);
669 edges_to_remove
.release ();
672 /* Tries to unroll LOOP completely, i.e. NITER times.
673 UL determines which loops we are allowed to unroll.
674 EXIT is the exit of the loop that should be eliminated.
675 MAXITER specfy bound on number of iterations, -1 if it is
676 not known or too large for HOST_WIDE_INT. The location
677 LOCUS corresponding to the loop is used when emitting
678 a summary of the unroll to the dump file. */
681 try_unroll_loop_completely (struct loop
*loop
,
682 edge exit
, tree niter
,
683 enum unroll_level ul
,
684 HOST_WIDE_INT maxiter
,
687 unsigned HOST_WIDE_INT n_unroll
= 0, ninsns
, unr_insns
;
688 struct loop_size size
;
689 bool n_unroll_found
= false;
690 edge edge_to_cancel
= NULL
;
691 int report_flags
= MSG_OPTIMIZED_LOCATIONS
| TDF_RTL
| TDF_DETAILS
;
693 /* See if we proved number of iterations to be low constant.
695 EXIT is an edge that will be removed in all but last iteration of
698 EDGE_TO_CACNEL is an edge that will be removed from the last iteration
699 of the unrolled sequence and is expected to make the final loop not
702 If the number of execution of loop is determined by standard induction
703 variable test, then EXIT and EDGE_TO_CANCEL are the two edges leaving
705 if (tree_fits_uhwi_p (niter
))
707 n_unroll
= tree_to_uhwi (niter
);
708 n_unroll_found
= true;
709 edge_to_cancel
= EDGE_SUCC (exit
->src
, 0);
710 if (edge_to_cancel
== exit
)
711 edge_to_cancel
= EDGE_SUCC (exit
->src
, 1);
713 /* We do not know the number of iterations and thus we can not eliminate
718 /* See if we can improve our estimate by using recorded loop bounds. */
720 && (!n_unroll_found
|| (unsigned HOST_WIDE_INT
)maxiter
< n_unroll
))
723 n_unroll_found
= true;
724 /* Loop terminates before the IV variable test, so we can not
725 remove it in the last iteration. */
726 edge_to_cancel
= NULL
;
732 if (n_unroll
> (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
))
734 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
735 fprintf (dump_file
, "Not unrolling loop %d "
736 "(--param max-completely-peel-times limit reached).\n",
742 edge_to_cancel
= loop_edge_to_cancel (loop
);
748 if (ul
== UL_SINGLE_ITER
)
751 /* EXIT can be removed only if we are sure it passes first N_UNROLL
753 bool remove_exit
= (exit
&& niter
754 && TREE_CODE (niter
) == INTEGER_CST
755 && wi::leu_p (n_unroll
, wi::to_widest (niter
)));
757 large
= tree_estimate_loop_size
758 (loop
, remove_exit
? exit
: NULL
, edge_to_cancel
, &size
,
759 PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
));
760 ninsns
= size
.overall
;
763 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
764 fprintf (dump_file
, "Not unrolling loop %d: it is too large.\n",
769 unr_insns
= estimated_unrolled_size (&size
, n_unroll
);
770 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
772 fprintf (dump_file
, " Loop size: %d\n", (int) ninsns
);
773 fprintf (dump_file
, " Estimated size after unrolling: %d\n",
777 /* If the code is going to shrink, we don't need to be extra cautious
778 on guessing if the unrolling is going to be profitable. */
780 /* If there is IV variable that will become constant, we save
781 one instruction in the loop prologue we do not account
783 <= ninsns
+ (size
.constant_iv
!= false))
785 /* We unroll only inner loops, because we do not consider it profitable
786 otheriwse. We still can cancel loopback edge of not rolling loop;
787 this is always a good idea. */
788 else if (ul
== UL_NO_GROWTH
)
790 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
791 fprintf (dump_file
, "Not unrolling loop %d: size would grow.\n",
795 /* Outer loops tend to be less interesting candidates for complete
796 unrolling unless we can do a lot of propagation into the inner loop
797 body. For now we disable outer loop unrolling when the code would
799 else if (loop
->inner
)
801 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
802 fprintf (dump_file
, "Not unrolling loop %d: "
803 "it is not innermost and code would grow.\n",
807 /* If there is call on a hot path through the loop, then
808 there is most probably not much to optimize. */
809 else if (size
.num_non_pure_calls_on_hot_path
)
811 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
812 fprintf (dump_file
, "Not unrolling loop %d: "
813 "contains call and code would grow.\n",
817 /* If there is pure/const call in the function, then we
818 can still optimize the unrolled loop body if it contains
819 some other interesting code than the calls and code
820 storing or cumulating the return value. */
821 else if (size
.num_pure_calls_on_hot_path
822 /* One IV increment, one test, one ivtmp store
823 and one useful stmt. That is about minimal loop
825 && (size
.non_call_stmts_on_hot_path
826 <= 3 + size
.num_pure_calls_on_hot_path
))
828 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
829 fprintf (dump_file
, "Not unrolling loop %d: "
830 "contains just pure calls and code would grow.\n",
834 /* Complete unrolling is a major win when control flow is removed and
835 one big basic block is created. If the loop contains control flow
836 the optimization may still be a win because of eliminating the loop
837 overhead but it also may blow the branch predictor tables.
838 Limit number of branches on the hot path through the peeled
840 else if (size
.num_branches_on_hot_path
* (int)n_unroll
841 > PARAM_VALUE (PARAM_MAX_PEEL_BRANCHES
))
843 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
844 fprintf (dump_file
, "Not unrolling loop %d: "
845 " number of branches on hot path in the unrolled sequence"
846 " reach --param max-peel-branches limit.\n",
851 > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
))
853 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
854 fprintf (dump_file
, "Not unrolling loop %d: "
855 "(--param max-completely-peeled-insns limit reached).\n",
859 dump_printf_loc (report_flags
, locus
,
860 "loop turned into non-loop; it never loops.\n");
862 initialize_original_copy_tables ();
863 wont_exit
= sbitmap_alloc (n_unroll
+ 1);
865 && TREE_CODE (niter
) == INTEGER_CST
866 && wi::leu_p (n_unroll
, wi::to_widest (niter
)))
868 bitmap_ones (wont_exit
);
869 if (wi::eq_p (wi::to_widest (niter
), n_unroll
)
871 bitmap_clear_bit (wont_exit
, 0);
876 bitmap_clear (wont_exit
);
879 if (!gimple_duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
881 exit
, &edges_to_remove
,
882 DLTHE_FLAG_UPDATE_FREQ
883 | DLTHE_FLAG_COMPLETTE_PEEL
))
885 free_original_copy_tables ();
887 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
888 fprintf (dump_file
, "Failed to duplicate the loop\n");
893 free_original_copy_tables ();
896 /* Remove the conditional from the last copy of the loop. */
899 gcond
*cond
= as_a
<gcond
*> (last_stmt (edge_to_cancel
->src
));
900 force_edge_cold (edge_to_cancel
, true);
901 if (edge_to_cancel
->flags
& EDGE_TRUE_VALUE
)
902 gimple_cond_make_false (cond
);
904 gimple_cond_make_true (cond
);
906 /* Do not remove the path. Doing so may remove outer loop
907 and confuse bookkeeping code in tree_unroll_loops_completelly. */
910 /* Store the loop for later unlooping and exit removal. */
911 loops_to_unloop
.safe_push (loop
);
912 loops_to_unloop_nunroll
.safe_push (n_unroll
);
914 if (dump_enabled_p ())
917 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
918 "loop turned into non-loop; it never loops\n");
921 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
922 "loop with %d iterations completely unrolled",
923 (int) (n_unroll
+ 1));
925 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
,
926 " (header execution count %d)",
927 (int)loop
->header
->count
);
928 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, "\n");
932 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
935 fprintf (dump_file
, "Exit condition of peeled iterations was "
938 fprintf (dump_file
, "Last iteration exit edge was proved true.\n");
940 fprintf (dump_file
, "Latch of last iteration was marked by "
941 "__builtin_unreachable ().\n");
947 /* Return number of instructions after peeling. */
948 static unsigned HOST_WIDE_INT
949 estimated_peeled_sequence_size (struct loop_size
*size
,
950 unsigned HOST_WIDE_INT npeel
)
952 return MAX (npeel
* (HOST_WIDE_INT
) (size
->overall
953 - size
->eliminated_by_peeling
), 1);
956 /* If the loop is expected to iterate N times and is
957 small enough, duplicate the loop body N+1 times before
958 the loop itself. This way the hot path will never
960 Parameters are the same as for try_unroll_loops_completely */
963 try_peel_loop (struct loop
*loop
,
964 edge exit
, tree niter
,
965 HOST_WIDE_INT maxiter
)
968 struct loop_size size
;
972 if (!flag_peel_loops
|| PARAM_VALUE (PARAM_MAX_PEEL_TIMES
) <= 0
976 if (bitmap_bit_p (peeled_loops
, loop
->num
))
979 fprintf (dump_file
, "Not peeling: loop is already peeled\n");
983 /* Peel only innermost loops.
984 While the code is perfectly capable of peeling non-innermost loops,
985 the heuristics would probably need some improvements. */
989 fprintf (dump_file
, "Not peeling: outer loop\n");
993 if (!optimize_loop_for_speed_p (loop
))
996 fprintf (dump_file
, "Not peeling: cold loop\n");
1000 /* Check if there is an estimate on the number of iterations. */
1001 npeel
= estimated_loop_iterations_int (loop
);
1003 npeel
= likely_max_loop_iterations_int (loop
);
1007 fprintf (dump_file
, "Not peeling: number of iterations is not "
1011 if (maxiter
>= 0 && maxiter
<= npeel
)
1014 fprintf (dump_file
, "Not peeling: upper bound is known so can "
1015 "unroll completely\n");
1019 /* We want to peel estimated number of iterations + 1 (so we never
1020 enter the loop on quick path). Check against PARAM_MAX_PEEL_TIMES
1021 and be sure to avoid overflows. */
1022 if (npeel
> PARAM_VALUE (PARAM_MAX_PEEL_TIMES
) - 1)
1025 fprintf (dump_file
, "Not peeling: rolls too much "
1026 "(%i + 1 > --param max-peel-times)\n", (int) npeel
);
1031 /* Check peeled loops size. */
1032 tree_estimate_loop_size (loop
, exit
, NULL
, &size
,
1033 PARAM_VALUE (PARAM_MAX_PEELED_INSNS
));
1034 if ((peeled_size
= estimated_peeled_sequence_size (&size
, (int) npeel
))
1035 > PARAM_VALUE (PARAM_MAX_PEELED_INSNS
))
1038 fprintf (dump_file
, "Not peeling: peeled sequence size is too large "
1039 "(%i insns > --param max-peel-insns)", peeled_size
);
1043 /* Duplicate possibly eliminating the exits. */
1044 initialize_original_copy_tables ();
1045 wont_exit
= sbitmap_alloc (npeel
+ 1);
1047 && TREE_CODE (niter
) == INTEGER_CST
1048 && wi::leu_p (npeel
, wi::to_widest (niter
)))
1050 bitmap_ones (wont_exit
);
1051 bitmap_clear_bit (wont_exit
, 0);
1056 bitmap_clear (wont_exit
);
1058 if (!gimple_duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1060 exit
, &edges_to_remove
,
1061 DLTHE_FLAG_UPDATE_FREQ
))
1063 free_original_copy_tables ();
1068 free_original_copy_tables ();
1069 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1071 fprintf (dump_file
, "Peeled loop %d, %i times.\n",
1072 loop
->num
, (int) npeel
);
1074 if (loop
->any_estimate
)
1076 if (wi::ltu_p (npeel
, loop
->nb_iterations_estimate
))
1077 loop
->nb_iterations_estimate
-= npeel
;
1079 loop
->nb_iterations_estimate
= 0;
1081 if (loop
->any_upper_bound
)
1083 if (wi::ltu_p (npeel
, loop
->nb_iterations_upper_bound
))
1084 loop
->nb_iterations_upper_bound
-= npeel
;
1086 loop
->nb_iterations_upper_bound
= 0;
1088 if (loop
->any_likely_upper_bound
)
1090 if (wi::ltu_p (npeel
, loop
->nb_iterations_likely_upper_bound
))
1091 loop
->nb_iterations_likely_upper_bound
-= npeel
;
1094 loop
->any_estimate
= true;
1095 loop
->nb_iterations_estimate
= 0;
1096 loop
->nb_iterations_likely_upper_bound
= 0;
1099 gcov_type entry_count
= 0;
1104 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1105 if (e
->src
!= loop
->latch
)
1107 entry_count
+= e
->src
->count
;
1108 entry_freq
+= e
->src
->frequency
;
1109 gcc_assert (!flow_bb_inside_loop_p (loop
, e
->src
));
1112 if (loop
->header
->count
)
1113 scale
= RDIV (entry_count
* REG_BR_PROB_BASE
, loop
->header
->count
);
1114 else if (loop
->header
->frequency
)
1115 scale
= RDIV (entry_freq
* REG_BR_PROB_BASE
, loop
->header
->frequency
);
1116 scale_loop_profile (loop
, scale
, 0);
1117 bitmap_set_bit (peeled_loops
, loop
->num
);
1120 /* Adds a canonical induction variable to LOOP if suitable.
1121 CREATE_IV is true if we may create a new iv. UL determines
1122 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
1123 to determine the number of iterations of a loop by direct evaluation.
1124 Returns true if cfg is changed. */
1127 canonicalize_loop_induction_variables (struct loop
*loop
,
1128 bool create_iv
, enum unroll_level ul
,
1133 HOST_WIDE_INT maxiter
;
1134 bool modified
= false;
1135 location_t locus
= UNKNOWN_LOCATION
;
1137 niter
= number_of_latch_executions (loop
);
1138 exit
= single_exit (loop
);
1139 if (TREE_CODE (niter
) == INTEGER_CST
)
1140 locus
= gimple_location (last_stmt (exit
->src
));
1143 /* If the loop has more than one exit, try checking all of them
1144 for # of iterations determinable through scev. */
1146 niter
= find_loop_niter (loop
, &exit
);
1148 /* Finally if everything else fails, try brute force evaluation. */
1150 && (chrec_contains_undetermined (niter
)
1151 || TREE_CODE (niter
) != INTEGER_CST
))
1152 niter
= find_loop_niter_by_eval (loop
, &exit
);
1155 locus
= gimple_location (last_stmt (exit
->src
));
1157 if (TREE_CODE (niter
) != INTEGER_CST
)
1161 /* We work exceptionally hard here to estimate the bound
1162 by find_loop_niter_by_eval. Be sure to keep it for future. */
1163 if (niter
&& TREE_CODE (niter
) == INTEGER_CST
)
1165 record_niter_bound (loop
, wi::to_widest (niter
),
1166 exit
== single_likely_exit (loop
), true);
1169 /* Force re-computation of loop bounds so we can remove redundant exits. */
1170 maxiter
= max_loop_iterations_int (loop
);
1172 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1173 && TREE_CODE (niter
) == INTEGER_CST
)
1175 fprintf (dump_file
, "Loop %d iterates ", loop
->num
);
1176 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1177 fprintf (dump_file
, " times.\n");
1179 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1182 fprintf (dump_file
, "Loop %d iterates at most %i times.\n", loop
->num
,
1185 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1186 && likely_max_loop_iterations_int (loop
) >= 0)
1188 fprintf (dump_file
, "Loop %d likely iterates at most %i times.\n",
1189 loop
->num
, (int)likely_max_loop_iterations_int (loop
));
1192 /* Remove exits that are known to be never taken based on loop bound.
1193 Needs to be called after compilation of max_loop_iterations_int that
1194 populates the loop bounds. */
1195 modified
|= remove_redundant_iv_tests (loop
);
1197 if (try_unroll_loop_completely (loop
, exit
, niter
, ul
, maxiter
, locus
))
1201 && niter
&& !chrec_contains_undetermined (niter
)
1202 && exit
&& just_once_each_iteration_p (loop
, exit
->src
))
1203 create_canonical_iv (loop
, exit
, niter
);
1206 modified
|= try_peel_loop (loop
, exit
, niter
, maxiter
);
1211 /* The main entry point of the pass. Adds canonical induction variables
1212 to the suitable loops. */
1215 canonicalize_induction_variables (void)
1218 bool changed
= false;
1219 bool irred_invalidated
= false;
1220 bitmap loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
1222 free_numbers_of_iterations_estimates (cfun
);
1223 estimate_numbers_of_iterations ();
1225 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1227 changed
|= canonicalize_loop_induction_variables (loop
,
1228 true, UL_SINGLE_ITER
,
1231 gcc_assert (!need_ssa_update_p (cfun
));
1233 unloop_loops (loop_closed_ssa_invalidated
, &irred_invalidated
);
1234 if (irred_invalidated
1235 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1236 mark_irreducible_loops ();
1238 /* Clean up the information about numbers of iterations, since brute force
1239 evaluation could reveal new information. */
1242 if (!bitmap_empty_p (loop_closed_ssa_invalidated
))
1244 gcc_checking_assert (loops_state_satisfies_p (LOOP_CLOSED_SSA
));
1245 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1247 BITMAP_FREE (loop_closed_ssa_invalidated
);
1250 return TODO_cleanup_cfg
;
1254 /* Propagate constant SSA_NAMEs defined in basic block BB. */
1257 propagate_constants_for_unrolling (basic_block bb
)
1259 /* Look for degenerate PHI nodes with constant argument. */
1260 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); )
1262 gphi
*phi
= gsi
.phi ();
1263 tree result
= gimple_phi_result (phi
);
1264 tree arg
= gimple_phi_arg_def (phi
, 0);
1266 if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (result
)
1267 && gimple_phi_num_args (phi
) == 1
1268 && TREE_CODE (arg
) == INTEGER_CST
)
1270 replace_uses_by (result
, arg
);
1271 gsi_remove (&gsi
, true);
1272 release_ssa_name (result
);
1278 /* Look for assignments to SSA names with constant RHS. */
1279 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
1281 gimple
*stmt
= gsi_stmt (gsi
);
1284 if (is_gimple_assign (stmt
)
1285 && gimple_assign_rhs_code (stmt
) == INTEGER_CST
1286 && (lhs
= gimple_assign_lhs (stmt
), TREE_CODE (lhs
) == SSA_NAME
)
1287 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1289 replace_uses_by (lhs
, gimple_assign_rhs1 (stmt
));
1290 gsi_remove (&gsi
, true);
1291 release_ssa_name (lhs
);
1298 /* Process loops from innermost to outer, stopping at the innermost
1299 loop we unrolled. */
1302 tree_unroll_loops_completely_1 (bool may_increase_size
, bool unroll_outer
,
1303 bitmap father_bbs
, struct loop
*loop
)
1305 struct loop
*loop_father
;
1306 bool changed
= false;
1308 enum unroll_level ul
;
1310 /* Process inner loops first. */
1311 for (inner
= loop
->inner
; inner
!= NULL
; inner
= inner
->next
)
1312 changed
|= tree_unroll_loops_completely_1 (may_increase_size
,
1313 unroll_outer
, father_bbs
,
1316 /* If we changed an inner loop we cannot process outer loops in this
1317 iteration because SSA form is not up-to-date. Continue with
1318 siblings of outer loops instead. */
1322 /* Don't unroll #pragma omp simd loops until the vectorizer
1323 attempts to vectorize those. */
1324 if (loop
->force_vectorize
)
1327 /* Try to unroll this loop. */
1328 loop_father
= loop_outer (loop
);
1332 if (may_increase_size
&& optimize_loop_nest_for_speed_p (loop
)
1333 /* Unroll outermost loops only if asked to do so or they do
1334 not cause code growth. */
1335 && (unroll_outer
|| loop_outer (loop_father
)))
1340 if (canonicalize_loop_induction_variables
1341 (loop
, false, ul
, !flag_tree_loop_ivcanon
))
1343 /* If we'll continue unrolling, we need to propagate constants
1344 within the new basic blocks to fold away induction variable
1345 computations; otherwise, the size might blow up before the
1346 iteration is complete and the IR eventually cleaned up. */
1347 if (loop_outer (loop_father
))
1348 bitmap_set_bit (father_bbs
, loop_father
->header
->index
);
1356 /* Unroll LOOPS completely if they iterate just few times. Unless
1357 MAY_INCREASE_SIZE is true, perform the unrolling only if the
1358 size of the code does not increase. */
1361 tree_unroll_loops_completely (bool may_increase_size
, bool unroll_outer
)
1363 bitmap father_bbs
= BITMAP_ALLOC (NULL
);
1366 bool irred_invalidated
= false;
1371 bitmap loop_closed_ssa_invalidated
= NULL
;
1373 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1374 loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
1376 free_numbers_of_iterations_estimates (cfun
);
1377 estimate_numbers_of_iterations ();
1379 changed
= tree_unroll_loops_completely_1 (may_increase_size
,
1380 unroll_outer
, father_bbs
,
1381 current_loops
->tree_root
);
1386 unloop_loops (loop_closed_ssa_invalidated
, &irred_invalidated
);
1388 /* We can not use TODO_update_ssa_no_phi because VOPS gets confused. */
1389 if (loop_closed_ssa_invalidated
1390 && !bitmap_empty_p (loop_closed_ssa_invalidated
))
1391 rewrite_into_loop_closed_ssa (loop_closed_ssa_invalidated
,
1394 update_ssa (TODO_update_ssa
);
1396 /* father_bbs is a bitmap of loop father header BB indices.
1397 Translate that to what non-root loops these BBs belong to now. */
1399 bitmap fathers
= BITMAP_ALLOC (NULL
);
1400 EXECUTE_IF_SET_IN_BITMAP (father_bbs
, 0, i
, bi
)
1402 basic_block unrolled_loop_bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
1403 if (! unrolled_loop_bb
)
1405 if (loop_outer (unrolled_loop_bb
->loop_father
))
1406 bitmap_set_bit (fathers
,
1407 unrolled_loop_bb
->loop_father
->num
);
1409 bitmap_clear (father_bbs
);
1410 /* Propagate the constants within the new basic blocks. */
1411 EXECUTE_IF_SET_IN_BITMAP (fathers
, 0, i
, bi
)
1413 loop_p father
= get_loop (cfun
, i
);
1414 basic_block
*body
= get_loop_body_in_dom_order (father
);
1415 for (unsigned j
= 0; j
< father
->num_nodes
; j
++)
1416 propagate_constants_for_unrolling (body
[j
]);
1419 BITMAP_FREE (fathers
);
1421 /* This will take care of removing completely unrolled loops
1422 from the loop structures so we can continue unrolling now
1424 if (cleanup_tree_cfg ())
1425 update_ssa (TODO_update_ssa_only_virtuals
);
1427 /* Clean up the information about numbers of iterations, since
1428 complete unrolling might have invalidated it. */
1430 if (flag_checking
&& loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1431 verify_loop_closed_ssa (true);
1433 if (loop_closed_ssa_invalidated
)
1434 BITMAP_FREE (loop_closed_ssa_invalidated
);
1437 && ++iteration
<= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS
));
1439 BITMAP_FREE (father_bbs
);
1441 if (irred_invalidated
1442 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1443 mark_irreducible_loops ();
1448 /* Canonical induction variable creation pass. */
1452 const pass_data pass_data_iv_canon
=
1454 GIMPLE_PASS
, /* type */
1455 "ivcanon", /* name */
1456 OPTGROUP_LOOP
, /* optinfo_flags */
1457 TV_TREE_LOOP_IVCANON
, /* tv_id */
1458 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1459 0, /* properties_provided */
1460 0, /* properties_destroyed */
1461 0, /* todo_flags_start */
1462 0, /* todo_flags_finish */
1465 class pass_iv_canon
: public gimple_opt_pass
1468 pass_iv_canon (gcc::context
*ctxt
)
1469 : gimple_opt_pass (pass_data_iv_canon
, ctxt
)
1472 /* opt_pass methods: */
1473 virtual bool gate (function
*) { return flag_tree_loop_ivcanon
!= 0; }
1474 virtual unsigned int execute (function
*fun
);
1476 }; // class pass_iv_canon
1479 pass_iv_canon::execute (function
*fun
)
1481 if (number_of_loops (fun
) <= 1)
1484 return canonicalize_induction_variables ();
1490 make_pass_iv_canon (gcc::context
*ctxt
)
1492 return new pass_iv_canon (ctxt
);
1495 /* Complete unrolling of loops. */
1499 const pass_data pass_data_complete_unroll
=
1501 GIMPLE_PASS
, /* type */
1502 "cunroll", /* name */
1503 OPTGROUP_LOOP
, /* optinfo_flags */
1504 TV_COMPLETE_UNROLL
, /* tv_id */
1505 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1506 0, /* properties_provided */
1507 0, /* properties_destroyed */
1508 0, /* todo_flags_start */
1509 0, /* todo_flags_finish */
1512 class pass_complete_unroll
: public gimple_opt_pass
1515 pass_complete_unroll (gcc::context
*ctxt
)
1516 : gimple_opt_pass (pass_data_complete_unroll
, ctxt
)
1519 /* opt_pass methods: */
1520 virtual unsigned int execute (function
*);
1522 }; // class pass_complete_unroll
1525 pass_complete_unroll::execute (function
*fun
)
1527 if (number_of_loops (fun
) <= 1)
1530 /* If we ever decide to run loop peeling more than once, we will need to
1531 track loops already peeled in loop structures themselves to avoid
1532 re-peeling the same loop multiple times. */
1533 if (flag_peel_loops
)
1534 peeled_loops
= BITMAP_ALLOC (NULL
);
1535 int val
= tree_unroll_loops_completely (flag_unroll_loops
1537 || optimize
>= 3, true);
1540 BITMAP_FREE (peeled_loops
);
1541 peeled_loops
= NULL
;
1549 make_pass_complete_unroll (gcc::context
*ctxt
)
1551 return new pass_complete_unroll (ctxt
);
1554 /* Complete unrolling of inner loops. */
1558 const pass_data pass_data_complete_unrolli
=
1560 GIMPLE_PASS
, /* type */
1561 "cunrolli", /* name */
1562 OPTGROUP_LOOP
, /* optinfo_flags */
1563 TV_COMPLETE_UNROLL
, /* tv_id */
1564 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1565 0, /* properties_provided */
1566 0, /* properties_destroyed */
1567 0, /* todo_flags_start */
1568 0, /* todo_flags_finish */
1571 class pass_complete_unrolli
: public gimple_opt_pass
1574 pass_complete_unrolli (gcc::context
*ctxt
)
1575 : gimple_opt_pass (pass_data_complete_unrolli
, ctxt
)
1578 /* opt_pass methods: */
1579 virtual bool gate (function
*) { return optimize
>= 2; }
1580 virtual unsigned int execute (function
*);
1582 }; // class pass_complete_unrolli
1585 pass_complete_unrolli::execute (function
*fun
)
1589 loop_optimizer_init (LOOPS_NORMAL
1590 | LOOPS_HAVE_RECORDED_EXITS
);
1591 if (number_of_loops (fun
) > 1)
1594 ret
= tree_unroll_loops_completely (optimize
>= 3, false);
1595 free_numbers_of_iterations_estimates (fun
);
1598 loop_optimizer_finalize ();
1606 make_pass_complete_unrolli (gcc::context
*ctxt
)
1608 return new pass_complete_unrolli (ctxt
);