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
, struct loop_size
*size
,
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
, after_exit
);
241 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
243 gimple
*stmt
= gsi_stmt (gsi
);
244 int num
= estimate_num_insns (stmt
, &eni_size_weights
);
245 bool likely_eliminated
= false;
246 bool likely_eliminated_last
= false;
247 bool likely_eliminated_peeled
= false;
249 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
251 fprintf (dump_file
, " size: %3i ", num
);
252 print_gimple_stmt (dump_file
, gsi_stmt (gsi
), 0, 0);
255 /* Look for reasons why we might optimize this stmt away. */
257 if (gimple_has_side_effects (stmt
))
259 /* Exit conditional. */
260 else if (exit
&& body
[i
] == exit
->src
261 && stmt
== last_stmt (exit
->src
))
263 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
264 fprintf (dump_file
, " Exit condition will be eliminated "
265 "in peeled copies.\n");
266 likely_eliminated_peeled
= true;
268 else if (edge_to_cancel
&& body
[i
] == edge_to_cancel
->src
269 && stmt
== last_stmt (edge_to_cancel
->src
))
271 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
272 fprintf (dump_file
, " Exit condition will be eliminated "
274 likely_eliminated_last
= true;
276 /* Sets of IV variables */
277 else if (gimple_code (stmt
) == GIMPLE_ASSIGN
278 && constant_after_peeling (gimple_assign_lhs (stmt
), stmt
, loop
))
280 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
281 fprintf (dump_file
, " Induction variable computation will"
282 " be folded away.\n");
283 likely_eliminated
= true;
285 /* Assignments of IV variables. */
286 else if (gimple_code (stmt
) == GIMPLE_ASSIGN
287 && TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
288 && constant_after_peeling (gimple_assign_rhs1 (stmt
), stmt
, loop
)
289 && (gimple_assign_rhs_class (stmt
) != GIMPLE_BINARY_RHS
290 || constant_after_peeling (gimple_assign_rhs2 (stmt
),
293 size
->constant_iv
= true;
294 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
295 fprintf (dump_file
, " Constant expression will be folded away.\n");
296 likely_eliminated
= true;
299 else if ((gimple_code (stmt
) == GIMPLE_COND
300 && constant_after_peeling (gimple_cond_lhs (stmt
), stmt
, loop
)
301 && constant_after_peeling (gimple_cond_rhs (stmt
), stmt
, loop
)
302 /* We don't simplify all constant compares so make sure
303 they are not both constant already. See PR70288. */
304 && (! is_gimple_min_invariant (gimple_cond_lhs (stmt
))
305 || ! is_gimple_min_invariant (gimple_cond_rhs (stmt
))))
306 || (gimple_code (stmt
) == GIMPLE_SWITCH
307 && constant_after_peeling (gimple_switch_index (
308 as_a
<gswitch
*> (stmt
)),
310 && ! is_gimple_min_invariant (gimple_switch_index (
311 as_a
<gswitch
*> (stmt
)))))
313 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
314 fprintf (dump_file
, " Constant conditional.\n");
315 likely_eliminated
= true;
318 size
->overall
+= num
;
319 if (likely_eliminated
|| likely_eliminated_peeled
)
320 size
->eliminated_by_peeling
+= num
;
323 size
->last_iteration
+= num
;
324 if (likely_eliminated
|| likely_eliminated_last
)
325 size
->last_iteration_eliminated_by_peeling
+= num
;
327 if ((size
->overall
* 3 / 2 - size
->eliminated_by_peeling
328 - size
->last_iteration_eliminated_by_peeling
) > upper_bound
)
336 while (path
.length ())
338 basic_block bb
= path
.pop ();
339 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
341 gimple
*stmt
= gsi_stmt (gsi
);
342 if (gimple_code (stmt
) == GIMPLE_CALL
)
344 int flags
= gimple_call_flags (stmt
);
345 tree decl
= gimple_call_fndecl (stmt
);
347 if (decl
&& DECL_IS_BUILTIN (decl
)
348 && is_inexpensive_builtin (decl
))
350 else if (flags
& (ECF_PURE
| ECF_CONST
))
351 size
->num_pure_calls_on_hot_path
++;
353 size
->num_non_pure_calls_on_hot_path
++;
354 size
->num_branches_on_hot_path
++;
356 else if (gimple_code (stmt
) != GIMPLE_CALL
357 && gimple_code (stmt
) != GIMPLE_DEBUG
)
358 size
->non_call_stmts_on_hot_path
++;
359 if (((gimple_code (stmt
) == GIMPLE_COND
360 && (!constant_after_peeling (gimple_cond_lhs (stmt
), stmt
, loop
)
361 || constant_after_peeling (gimple_cond_rhs (stmt
), stmt
, loop
)))
362 || (gimple_code (stmt
) == GIMPLE_SWITCH
363 && !constant_after_peeling (gimple_switch_index (
364 as_a
<gswitch
*> (stmt
)),
366 && (!exit
|| bb
!= exit
->src
))
367 size
->num_branches_on_hot_path
++;
371 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
372 fprintf (dump_file
, "size: %i-%i, last_iteration: %i-%i\n", size
->overall
,
373 size
->eliminated_by_peeling
, size
->last_iteration
,
374 size
->last_iteration_eliminated_by_peeling
);
380 /* Estimate number of insns of completely unrolled loop.
381 It is (NUNROLL + 1) * size of loop body with taking into account
382 the fact that in last copy everything after exit conditional
383 is dead and that some instructions will be eliminated after
386 Loop body is likely going to simplify further, this is difficult
387 to guess, we just decrease the result by 1/3. */
389 static unsigned HOST_WIDE_INT
390 estimated_unrolled_size (struct loop_size
*size
,
391 unsigned HOST_WIDE_INT nunroll
)
393 HOST_WIDE_INT unr_insns
= ((nunroll
)
394 * (HOST_WIDE_INT
) (size
->overall
395 - size
->eliminated_by_peeling
));
398 unr_insns
+= size
->last_iteration
- size
->last_iteration_eliminated_by_peeling
;
400 unr_insns
= unr_insns
* 2 / 3;
407 /* Loop LOOP is known to not loop. See if there is an edge in the loop
408 body that can be remove to make the loop to always exit and at
409 the same time it does not make any code potentially executed
410 during the last iteration dead.
412 After complete unrolling we still may get rid of the conditional
413 on the exit in the last copy even if we have no idea what it does.
414 This is quite common case for loops of form
420 Here we prove the loop to iterate 5 times but we do not know
421 it from induction variable.
423 For now we handle only simple case where there is exit condition
424 just before the latch block and the latch block contains no statements
425 with side effect that may otherwise terminate the execution of loop
426 (such as by EH or by terminating the program or longjmp).
428 In the general case we may want to cancel the paths leading to statements
429 loop-niter identified as having undefined effect in the last iteration.
430 The other cases are hopefully rare and will be cleaned up later. */
433 loop_edge_to_cancel (struct loop
*loop
)
438 gimple_stmt_iterator gsi
;
440 /* We want only one predecestor of the loop. */
441 if (EDGE_COUNT (loop
->latch
->preds
) > 1)
444 exits
= get_loop_exit_edges (loop
);
446 FOR_EACH_VEC_ELT (exits
, i
, edge_to_cancel
)
448 /* Find the other edge than the loop exit
449 leaving the conditoinal. */
450 if (EDGE_COUNT (edge_to_cancel
->src
->succs
) != 2)
452 if (EDGE_SUCC (edge_to_cancel
->src
, 0) == edge_to_cancel
)
453 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 1);
455 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 0);
457 /* We only can handle conditionals. */
458 if (!(edge_to_cancel
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
461 /* We should never have conditionals in the loop latch. */
462 gcc_assert (edge_to_cancel
->dest
!= loop
->header
);
464 /* Check that it leads to loop latch. */
465 if (edge_to_cancel
->dest
!= loop
->latch
)
470 /* Verify that the code in loop latch does nothing that may end program
471 execution without really reaching the exit. This may include
472 non-pure/const function calls, EH statements, volatile ASMs etc. */
473 for (gsi
= gsi_start_bb (loop
->latch
); !gsi_end_p (gsi
); gsi_next (&gsi
))
474 if (gimple_has_side_effects (gsi_stmt (gsi
)))
476 return edge_to_cancel
;
482 /* Remove all tests for exits that are known to be taken after LOOP was
483 peeled NPEELED times. Put gcc_unreachable before every statement
484 known to not be executed. */
487 remove_exits_and_undefined_stmts (struct loop
*loop
, unsigned int npeeled
)
489 struct nb_iter_bound
*elt
;
490 bool changed
= false;
492 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
494 /* If statement is known to be undefined after peeling, turn it
495 into unreachable (or trap when debugging experience is supposed
498 && wi::ltu_p (elt
->bound
, npeeled
))
500 gimple_stmt_iterator gsi
= gsi_for_stmt (elt
->stmt
);
501 gcall
*stmt
= gimple_build_call
502 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
), 0);
503 gimple_set_location (stmt
, gimple_location (elt
->stmt
));
504 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
505 split_block (gimple_bb (stmt
), stmt
);
507 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
509 fprintf (dump_file
, "Forced statement unreachable: ");
510 print_gimple_stmt (dump_file
, elt
->stmt
, 0, 0);
513 /* If we know the exit will be taken after peeling, update. */
514 else if (elt
->is_exit
515 && wi::leu_p (elt
->bound
, npeeled
))
517 basic_block bb
= gimple_bb (elt
->stmt
);
518 edge exit_edge
= EDGE_SUCC (bb
, 0);
520 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
522 fprintf (dump_file
, "Forced exit to be taken: ");
523 print_gimple_stmt (dump_file
, elt
->stmt
, 0, 0);
525 if (!loop_exit_edge_p (loop
, exit_edge
))
526 exit_edge
= EDGE_SUCC (bb
, 1);
527 gcc_checking_assert (loop_exit_edge_p (loop
, exit_edge
));
528 gcond
*cond_stmt
= as_a
<gcond
*> (elt
->stmt
);
529 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
530 gimple_cond_make_true (cond_stmt
);
532 gimple_cond_make_false (cond_stmt
);
533 update_stmt (cond_stmt
);
540 /* Remove all exits that are known to be never taken because of the loop bound
544 remove_redundant_iv_tests (struct loop
*loop
)
546 struct nb_iter_bound
*elt
;
547 bool changed
= false;
549 if (!loop
->any_upper_bound
)
551 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
553 /* Exit is pointless if it won't be taken before loop reaches
555 if (elt
->is_exit
&& loop
->any_upper_bound
556 && wi::ltu_p (loop
->nb_iterations_upper_bound
, elt
->bound
))
558 basic_block bb
= gimple_bb (elt
->stmt
);
559 edge exit_edge
= EDGE_SUCC (bb
, 0);
560 struct tree_niter_desc niter
;
562 if (!loop_exit_edge_p (loop
, exit_edge
))
563 exit_edge
= EDGE_SUCC (bb
, 1);
565 /* Only when we know the actual number of iterations, not
566 just a bound, we can remove the exit. */
567 if (!number_of_iterations_exit (loop
, exit_edge
,
568 &niter
, false, false)
569 || !integer_onep (niter
.assumptions
)
570 || !integer_zerop (niter
.may_be_zero
)
572 || TREE_CODE (niter
.niter
) != INTEGER_CST
573 || !wi::ltu_p (loop
->nb_iterations_upper_bound
,
574 wi::to_widest (niter
.niter
)))
577 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
579 fprintf (dump_file
, "Removed pointless exit: ");
580 print_gimple_stmt (dump_file
, elt
->stmt
, 0, 0);
582 gcond
*cond_stmt
= as_a
<gcond
*> (elt
->stmt
);
583 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
584 gimple_cond_make_false (cond_stmt
);
586 gimple_cond_make_true (cond_stmt
);
587 update_stmt (cond_stmt
);
594 /* Stores loops that will be unlooped and edges that will be removed
595 after we process whole loop tree. */
596 static vec
<loop_p
> loops_to_unloop
;
597 static vec
<int> loops_to_unloop_nunroll
;
598 static vec
<edge
> edges_to_remove
;
599 /* Stores loops that has been peeled. */
600 static bitmap peeled_loops
;
602 /* Cancel all fully unrolled loops by putting __builtin_unreachable
604 We do it after all unrolling since unlooping moves basic blocks
605 across loop boundaries trashing loop closed SSA form as well
606 as SCEV info needed to be intact during unrolling.
608 IRRED_INVALIDATED is used to bookkeep if information about
609 irreducible regions may become invalid as a result
610 of the transformation.
611 LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case
612 when we need to go into loop closed SSA form. */
615 unloop_loops (bitmap loop_closed_ssa_invalidated
,
616 bool *irred_invalidated
)
618 /* First remove edges in peeled copies. */
621 FOR_EACH_VEC_ELT (edges_to_remove
, i
, e
)
623 bool ok
= remove_path (e
);
626 edges_to_remove
.release ();
628 while (loops_to_unloop
.length ())
630 struct loop
*loop
= loops_to_unloop
.pop ();
631 int n_unroll
= loops_to_unloop_nunroll
.pop ();
632 basic_block latch
= loop
->latch
;
633 edge latch_edge
= loop_latch_edge (loop
);
634 int flags
= latch_edge
->flags
;
635 location_t locus
= latch_edge
->goto_locus
;
637 gimple_stmt_iterator gsi
;
639 remove_exits_and_undefined_stmts (loop
, n_unroll
);
641 /* Unloop destroys the latch edge. */
642 unloop (loop
, irred_invalidated
, loop_closed_ssa_invalidated
);
644 /* Create new basic block for the latch edge destination and wire
646 stmt
= gimple_build_call (builtin_decl_implicit (BUILT_IN_UNREACHABLE
), 0);
647 latch_edge
= make_edge (latch
, create_basic_block (NULL
, NULL
, latch
), flags
);
648 latch_edge
->probability
= 0;
649 latch_edge
->count
= 0;
650 latch_edge
->flags
|= flags
;
651 latch_edge
->goto_locus
= locus
;
653 latch_edge
->dest
->loop_father
= current_loops
->tree_root
;
654 latch_edge
->dest
->count
= 0;
655 latch_edge
->dest
->frequency
= 0;
656 set_immediate_dominator (CDI_DOMINATORS
, latch_edge
->dest
, latch_edge
->src
);
658 gsi
= gsi_start_bb (latch_edge
->dest
);
659 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
661 loops_to_unloop
.release ();
662 loops_to_unloop_nunroll
.release ();
665 /* Tries to unroll LOOP completely, i.e. NITER times.
666 UL determines which loops we are allowed to unroll.
667 EXIT is the exit of the loop that should be eliminated.
668 MAXITER specfy bound on number of iterations, -1 if it is
669 not known or too large for HOST_WIDE_INT. The location
670 LOCUS corresponding to the loop is used when emitting
671 a summary of the unroll to the dump file. */
674 try_unroll_loop_completely (struct loop
*loop
,
675 edge exit
, tree niter
,
676 enum unroll_level ul
,
677 HOST_WIDE_INT maxiter
,
680 unsigned HOST_WIDE_INT n_unroll
= 0, ninsns
, unr_insns
;
681 struct loop_size size
;
682 bool n_unroll_found
= false;
683 edge edge_to_cancel
= NULL
;
684 int report_flags
= MSG_OPTIMIZED_LOCATIONS
| TDF_RTL
| TDF_DETAILS
;
686 /* See if we proved number of iterations to be low constant.
688 EXIT is an edge that will be removed in all but last iteration of
691 EDGE_TO_CACNEL is an edge that will be removed from the last iteration
692 of the unrolled sequence and is expected to make the final loop not
695 If the number of execution of loop is determined by standard induction
696 variable test, then EXIT and EDGE_TO_CANCEL are the two edges leaving
698 if (tree_fits_uhwi_p (niter
))
700 n_unroll
= tree_to_uhwi (niter
);
701 n_unroll_found
= true;
702 edge_to_cancel
= EDGE_SUCC (exit
->src
, 0);
703 if (edge_to_cancel
== exit
)
704 edge_to_cancel
= EDGE_SUCC (exit
->src
, 1);
706 /* We do not know the number of iterations and thus we can not eliminate
711 /* See if we can improve our estimate by using recorded loop bounds. */
713 && (!n_unroll_found
|| (unsigned HOST_WIDE_INT
)maxiter
< n_unroll
))
716 n_unroll_found
= true;
717 /* Loop terminates before the IV variable test, so we can not
718 remove it in the last iteration. */
719 edge_to_cancel
= NULL
;
725 if (n_unroll
> (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
))
727 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
728 fprintf (dump_file
, "Not unrolling loop %d "
729 "(--param max-completely-peel-times limit reached).\n",
735 edge_to_cancel
= loop_edge_to_cancel (loop
);
741 if (ul
== UL_SINGLE_ITER
)
744 /* EXIT can be removed only if we are sure it passes first N_UNROLL
746 bool remove_exit
= (exit
&& niter
747 && TREE_CODE (niter
) == INTEGER_CST
748 && wi::leu_p (n_unroll
, wi::to_widest (niter
)));
750 large
= tree_estimate_loop_size
751 (loop
, remove_exit
? exit
: NULL
, edge_to_cancel
, &size
,
752 PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
));
753 ninsns
= size
.overall
;
756 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
757 fprintf (dump_file
, "Not unrolling loop %d: it is too large.\n",
762 unr_insns
= estimated_unrolled_size (&size
, n_unroll
);
763 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
765 fprintf (dump_file
, " Loop size: %d\n", (int) ninsns
);
766 fprintf (dump_file
, " Estimated size after unrolling: %d\n",
770 /* If the code is going to shrink, we don't need to be extra cautious
771 on guessing if the unrolling is going to be profitable. */
773 /* If there is IV variable that will become constant, we save
774 one instruction in the loop prologue we do not account
776 <= ninsns
+ (size
.constant_iv
!= false))
778 /* We unroll only inner loops, because we do not consider it profitable
779 otheriwse. We still can cancel loopback edge of not rolling loop;
780 this is always a good idea. */
781 else if (ul
== UL_NO_GROWTH
)
783 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
784 fprintf (dump_file
, "Not unrolling loop %d: size would grow.\n",
788 /* Outer loops tend to be less interesting candidates for complete
789 unrolling unless we can do a lot of propagation into the inner loop
790 body. For now we disable outer loop unrolling when the code would
792 else if (loop
->inner
)
794 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
795 fprintf (dump_file
, "Not unrolling loop %d: "
796 "it is not innermost and code would grow.\n",
800 /* If there is call on a hot path through the loop, then
801 there is most probably not much to optimize. */
802 else if (size
.num_non_pure_calls_on_hot_path
)
804 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
805 fprintf (dump_file
, "Not unrolling loop %d: "
806 "contains call and code would grow.\n",
810 /* If there is pure/const call in the function, then we
811 can still optimize the unrolled loop body if it contains
812 some other interesting code than the calls and code
813 storing or cumulating the return value. */
814 else if (size
.num_pure_calls_on_hot_path
815 /* One IV increment, one test, one ivtmp store
816 and one useful stmt. That is about minimal loop
818 && (size
.non_call_stmts_on_hot_path
819 <= 3 + size
.num_pure_calls_on_hot_path
))
821 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
822 fprintf (dump_file
, "Not unrolling loop %d: "
823 "contains just pure calls and code would grow.\n",
827 /* Complete unrolling is a major win when control flow is removed and
828 one big basic block is created. If the loop contains control flow
829 the optimization may still be a win because of eliminating the loop
830 overhead but it also may blow the branch predictor tables.
831 Limit number of branches on the hot path through the peeled
833 else if (size
.num_branches_on_hot_path
* (int)n_unroll
834 > PARAM_VALUE (PARAM_MAX_PEEL_BRANCHES
))
836 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
837 fprintf (dump_file
, "Not unrolling loop %d: "
838 " number of branches on hot path in the unrolled sequence"
839 " reach --param max-peel-branches limit.\n",
844 > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
))
846 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
847 fprintf (dump_file
, "Not unrolling loop %d: "
848 "(--param max-completely-peeled-insns limit reached).\n",
852 dump_printf_loc (report_flags
, locus
,
853 "loop turned into non-loop; it never loops.\n");
855 initialize_original_copy_tables ();
856 wont_exit
= sbitmap_alloc (n_unroll
+ 1);
858 && TREE_CODE (niter
) == INTEGER_CST
859 && wi::leu_p (n_unroll
, wi::to_widest (niter
)))
861 bitmap_ones (wont_exit
);
862 if (wi::eq_p (wi::to_widest (niter
), n_unroll
)
864 bitmap_clear_bit (wont_exit
, 0);
869 bitmap_clear (wont_exit
);
872 if (!gimple_duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
874 exit
, &edges_to_remove
,
875 DLTHE_FLAG_UPDATE_FREQ
876 | DLTHE_FLAG_COMPLETTE_PEEL
))
878 free_original_copy_tables ();
880 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
881 fprintf (dump_file
, "Failed to duplicate the loop\n");
886 free_original_copy_tables ();
889 /* Remove the conditional from the last copy of the loop. */
892 gcond
*cond
= as_a
<gcond
*> (last_stmt (edge_to_cancel
->src
));
893 force_edge_cold (edge_to_cancel
, true);
894 if (edge_to_cancel
->flags
& EDGE_TRUE_VALUE
)
895 gimple_cond_make_false (cond
);
897 gimple_cond_make_true (cond
);
899 /* Do not remove the path. Doing so may remove outer loop
900 and confuse bookkeeping code in tree_unroll_loops_completelly. */
903 /* Store the loop for later unlooping and exit removal. */
904 loops_to_unloop
.safe_push (loop
);
905 loops_to_unloop_nunroll
.safe_push (n_unroll
);
907 if (dump_enabled_p ())
910 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
911 "loop turned into non-loop; it never loops\n");
914 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
915 "loop with %d iterations completely unrolled",
916 (int) (n_unroll
+ 1));
918 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
,
919 " (header execution count %d)",
920 (int)loop
->header
->count
);
921 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, "\n");
925 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
928 fprintf (dump_file
, "Exit condition of peeled iterations was "
931 fprintf (dump_file
, "Last iteration exit edge was proved true.\n");
933 fprintf (dump_file
, "Latch of last iteration was marked by "
934 "__builtin_unreachable ().\n");
940 /* Return number of instructions after peeling. */
941 static unsigned HOST_WIDE_INT
942 estimated_peeled_sequence_size (struct loop_size
*size
,
943 unsigned HOST_WIDE_INT npeel
)
945 return MAX (npeel
* (HOST_WIDE_INT
) (size
->overall
946 - size
->eliminated_by_peeling
), 1);
949 /* If the loop is expected to iterate N times and is
950 small enough, duplicate the loop body N+1 times before
951 the loop itself. This way the hot path will never
953 Parameters are the same as for try_unroll_loops_completely */
956 try_peel_loop (struct loop
*loop
,
957 edge exit
, tree niter
,
958 HOST_WIDE_INT maxiter
)
961 struct loop_size size
;
965 if (!flag_peel_loops
|| PARAM_VALUE (PARAM_MAX_PEEL_TIMES
) <= 0
969 if (bitmap_bit_p (peeled_loops
, loop
->num
))
972 fprintf (dump_file
, "Not peeling: loop is already peeled\n");
976 /* Peel only innermost loops.
977 While the code is perfectly capable of peeling non-innermost loops,
978 the heuristics would probably need some improvements. */
982 fprintf (dump_file
, "Not peeling: outer loop\n");
986 if (!optimize_loop_for_speed_p (loop
))
989 fprintf (dump_file
, "Not peeling: cold loop\n");
993 /* Check if there is an estimate on the number of iterations. */
994 npeel
= estimated_loop_iterations_int (loop
);
996 npeel
= likely_max_loop_iterations_int (loop
);
1000 fprintf (dump_file
, "Not peeling: number of iterations is not "
1004 if (maxiter
>= 0 && maxiter
<= npeel
)
1007 fprintf (dump_file
, "Not peeling: upper bound is known so can "
1008 "unroll completely\n");
1012 /* We want to peel estimated number of iterations + 1 (so we never
1013 enter the loop on quick path). Check against PARAM_MAX_PEEL_TIMES
1014 and be sure to avoid overflows. */
1015 if (npeel
> PARAM_VALUE (PARAM_MAX_PEEL_TIMES
) - 1)
1018 fprintf (dump_file
, "Not peeling: rolls too much "
1019 "(%i + 1 > --param max-peel-times)\n", (int) npeel
);
1024 /* Check peeled loops size. */
1025 tree_estimate_loop_size (loop
, exit
, NULL
, &size
,
1026 PARAM_VALUE (PARAM_MAX_PEELED_INSNS
));
1027 if ((peeled_size
= estimated_peeled_sequence_size (&size
, (int) npeel
))
1028 > PARAM_VALUE (PARAM_MAX_PEELED_INSNS
))
1031 fprintf (dump_file
, "Not peeling: peeled sequence size is too large "
1032 "(%i insns > --param max-peel-insns)", peeled_size
);
1036 /* Duplicate possibly eliminating the exits. */
1037 initialize_original_copy_tables ();
1038 wont_exit
= sbitmap_alloc (npeel
+ 1);
1040 && TREE_CODE (niter
) == INTEGER_CST
1041 && wi::leu_p (npeel
, wi::to_widest (niter
)))
1043 bitmap_ones (wont_exit
);
1044 bitmap_clear_bit (wont_exit
, 0);
1049 bitmap_clear (wont_exit
);
1051 if (!gimple_duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1053 exit
, &edges_to_remove
,
1054 DLTHE_FLAG_UPDATE_FREQ
))
1056 free_original_copy_tables ();
1061 free_original_copy_tables ();
1062 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1064 fprintf (dump_file
, "Peeled loop %d, %i times.\n",
1065 loop
->num
, (int) npeel
);
1067 if (loop
->any_estimate
)
1069 if (wi::ltu_p (npeel
, loop
->nb_iterations_estimate
))
1070 loop
->nb_iterations_estimate
-= npeel
;
1072 loop
->nb_iterations_estimate
= 0;
1074 if (loop
->any_upper_bound
)
1076 if (wi::ltu_p (npeel
, loop
->nb_iterations_upper_bound
))
1077 loop
->nb_iterations_upper_bound
-= npeel
;
1079 loop
->nb_iterations_upper_bound
= 0;
1081 if (loop
->any_likely_upper_bound
)
1083 if (wi::ltu_p (npeel
, loop
->nb_iterations_likely_upper_bound
))
1084 loop
->nb_iterations_likely_upper_bound
-= npeel
;
1087 loop
->any_estimate
= true;
1088 loop
->nb_iterations_estimate
= 0;
1089 loop
->nb_iterations_likely_upper_bound
= 0;
1092 gcov_type entry_count
= 0;
1097 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1098 if (e
->src
!= loop
->latch
)
1100 entry_count
+= e
->src
->count
;
1101 entry_freq
+= e
->src
->frequency
;
1102 gcc_assert (!flow_bb_inside_loop_p (loop
, e
->src
));
1105 if (loop
->header
->count
)
1106 scale
= RDIV (entry_count
* REG_BR_PROB_BASE
, loop
->header
->count
);
1107 else if (loop
->header
->frequency
)
1108 scale
= RDIV (entry_freq
* REG_BR_PROB_BASE
, loop
->header
->frequency
);
1109 scale_loop_profile (loop
, scale
, 0);
1110 bitmap_set_bit (peeled_loops
, loop
->num
);
1113 /* Adds a canonical induction variable to LOOP if suitable.
1114 CREATE_IV is true if we may create a new iv. UL determines
1115 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
1116 to determine the number of iterations of a loop by direct evaluation.
1117 Returns true if cfg is changed. */
1120 canonicalize_loop_induction_variables (struct loop
*loop
,
1121 bool create_iv
, enum unroll_level ul
,
1126 HOST_WIDE_INT maxiter
;
1127 bool modified
= false;
1128 location_t locus
= UNKNOWN_LOCATION
;
1130 niter
= number_of_latch_executions (loop
);
1131 exit
= single_exit (loop
);
1132 if (TREE_CODE (niter
) == INTEGER_CST
)
1133 locus
= gimple_location (last_stmt (exit
->src
));
1136 /* If the loop has more than one exit, try checking all of them
1137 for # of iterations determinable through scev. */
1139 niter
= find_loop_niter (loop
, &exit
);
1141 /* Finally if everything else fails, try brute force evaluation. */
1143 && (chrec_contains_undetermined (niter
)
1144 || TREE_CODE (niter
) != INTEGER_CST
))
1145 niter
= find_loop_niter_by_eval (loop
, &exit
);
1148 locus
= gimple_location (last_stmt (exit
->src
));
1150 if (TREE_CODE (niter
) != INTEGER_CST
)
1154 /* We work exceptionally hard here to estimate the bound
1155 by find_loop_niter_by_eval. Be sure to keep it for future. */
1156 if (niter
&& TREE_CODE (niter
) == INTEGER_CST
)
1158 record_niter_bound (loop
, wi::to_widest (niter
),
1159 exit
== single_likely_exit (loop
), true);
1162 /* Force re-computation of loop bounds so we can remove redundant exits. */
1163 maxiter
= max_loop_iterations_int (loop
);
1165 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1166 && TREE_CODE (niter
) == INTEGER_CST
)
1168 fprintf (dump_file
, "Loop %d iterates ", loop
->num
);
1169 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1170 fprintf (dump_file
, " times.\n");
1172 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1175 fprintf (dump_file
, "Loop %d iterates at most %i times.\n", loop
->num
,
1178 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1179 && likely_max_loop_iterations_int (loop
) >= 0)
1181 fprintf (dump_file
, "Loop %d likely iterates at most %i times.\n",
1182 loop
->num
, (int)likely_max_loop_iterations_int (loop
));
1185 /* Remove exits that are known to be never taken based on loop bound.
1186 Needs to be called after compilation of max_loop_iterations_int that
1187 populates the loop bounds. */
1188 modified
|= remove_redundant_iv_tests (loop
);
1190 if (try_unroll_loop_completely (loop
, exit
, niter
, ul
, maxiter
, locus
))
1194 && niter
&& !chrec_contains_undetermined (niter
)
1195 && exit
&& just_once_each_iteration_p (loop
, exit
->src
))
1196 create_canonical_iv (loop
, exit
, niter
);
1199 modified
|= try_peel_loop (loop
, exit
, niter
, maxiter
);
1204 /* The main entry point of the pass. Adds canonical induction variables
1205 to the suitable loops. */
1208 canonicalize_induction_variables (void)
1211 bool changed
= false;
1212 bool irred_invalidated
= false;
1213 bitmap loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
1215 free_numbers_of_iterations_estimates (cfun
);
1216 estimate_numbers_of_iterations ();
1218 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1220 changed
|= canonicalize_loop_induction_variables (loop
,
1221 true, UL_SINGLE_ITER
,
1224 gcc_assert (!need_ssa_update_p (cfun
));
1226 unloop_loops (loop_closed_ssa_invalidated
, &irred_invalidated
);
1227 if (irred_invalidated
1228 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1229 mark_irreducible_loops ();
1231 /* Clean up the information about numbers of iterations, since brute force
1232 evaluation could reveal new information. */
1235 if (!bitmap_empty_p (loop_closed_ssa_invalidated
))
1237 gcc_checking_assert (loops_state_satisfies_p (LOOP_CLOSED_SSA
));
1238 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1240 BITMAP_FREE (loop_closed_ssa_invalidated
);
1243 return TODO_cleanup_cfg
;
1247 /* Propagate constant SSA_NAMEs defined in basic block BB. */
1250 propagate_constants_for_unrolling (basic_block bb
)
1252 /* Look for degenerate PHI nodes with constant argument. */
1253 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); )
1255 gphi
*phi
= gsi
.phi ();
1256 tree result
= gimple_phi_result (phi
);
1257 tree arg
= gimple_phi_arg_def (phi
, 0);
1259 if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (result
)
1260 && gimple_phi_num_args (phi
) == 1
1261 && TREE_CODE (arg
) == INTEGER_CST
)
1263 replace_uses_by (result
, arg
);
1264 gsi_remove (&gsi
, true);
1265 release_ssa_name (result
);
1271 /* Look for assignments to SSA names with constant RHS. */
1272 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
1274 gimple
*stmt
= gsi_stmt (gsi
);
1277 if (is_gimple_assign (stmt
)
1278 && gimple_assign_rhs_code (stmt
) == INTEGER_CST
1279 && (lhs
= gimple_assign_lhs (stmt
), TREE_CODE (lhs
) == SSA_NAME
)
1280 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1282 replace_uses_by (lhs
, gimple_assign_rhs1 (stmt
));
1283 gsi_remove (&gsi
, true);
1284 release_ssa_name (lhs
);
1291 /* Process loops from innermost to outer, stopping at the innermost
1292 loop we unrolled. */
1295 tree_unroll_loops_completely_1 (bool may_increase_size
, bool unroll_outer
,
1296 bitmap father_bbs
, struct loop
*loop
)
1298 struct loop
*loop_father
;
1299 bool changed
= false;
1301 enum unroll_level ul
;
1303 /* Process inner loops first. */
1304 for (inner
= loop
->inner
; inner
!= NULL
; inner
= inner
->next
)
1305 changed
|= tree_unroll_loops_completely_1 (may_increase_size
,
1306 unroll_outer
, father_bbs
,
1309 /* If we changed an inner loop we cannot process outer loops in this
1310 iteration because SSA form is not up-to-date. Continue with
1311 siblings of outer loops instead. */
1315 /* Don't unroll #pragma omp simd loops until the vectorizer
1316 attempts to vectorize those. */
1317 if (loop
->force_vectorize
)
1320 /* Try to unroll this loop. */
1321 loop_father
= loop_outer (loop
);
1325 if (may_increase_size
&& optimize_loop_nest_for_speed_p (loop
)
1326 /* Unroll outermost loops only if asked to do so or they do
1327 not cause code growth. */
1328 && (unroll_outer
|| loop_outer (loop_father
)))
1333 if (canonicalize_loop_induction_variables
1334 (loop
, false, ul
, !flag_tree_loop_ivcanon
))
1336 /* If we'll continue unrolling, we need to propagate constants
1337 within the new basic blocks to fold away induction variable
1338 computations; otherwise, the size might blow up before the
1339 iteration is complete and the IR eventually cleaned up. */
1340 if (loop_outer (loop_father
))
1341 bitmap_set_bit (father_bbs
, loop_father
->header
->index
);
1349 /* Unroll LOOPS completely if they iterate just few times. Unless
1350 MAY_INCREASE_SIZE is true, perform the unrolling only if the
1351 size of the code does not increase. */
1354 tree_unroll_loops_completely (bool may_increase_size
, bool unroll_outer
)
1356 bitmap father_bbs
= BITMAP_ALLOC (NULL
);
1359 bool irred_invalidated
= false;
1364 bitmap loop_closed_ssa_invalidated
= NULL
;
1366 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1367 loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
1369 free_numbers_of_iterations_estimates (cfun
);
1370 estimate_numbers_of_iterations ();
1372 changed
= tree_unroll_loops_completely_1 (may_increase_size
,
1373 unroll_outer
, father_bbs
,
1374 current_loops
->tree_root
);
1379 unloop_loops (loop_closed_ssa_invalidated
, &irred_invalidated
);
1381 /* We can not use TODO_update_ssa_no_phi because VOPS gets confused. */
1382 if (loop_closed_ssa_invalidated
1383 && !bitmap_empty_p (loop_closed_ssa_invalidated
))
1384 rewrite_into_loop_closed_ssa (loop_closed_ssa_invalidated
,
1387 update_ssa (TODO_update_ssa
);
1389 /* father_bbs is a bitmap of loop father header BB indices.
1390 Translate that to what non-root loops these BBs belong to now. */
1392 bitmap fathers
= BITMAP_ALLOC (NULL
);
1393 EXECUTE_IF_SET_IN_BITMAP (father_bbs
, 0, i
, bi
)
1395 basic_block unrolled_loop_bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
1396 if (! unrolled_loop_bb
)
1398 if (loop_outer (unrolled_loop_bb
->loop_father
))
1399 bitmap_set_bit (fathers
,
1400 unrolled_loop_bb
->loop_father
->num
);
1402 bitmap_clear (father_bbs
);
1403 /* Propagate the constants within the new basic blocks. */
1404 EXECUTE_IF_SET_IN_BITMAP (fathers
, 0, i
, bi
)
1406 loop_p father
= get_loop (cfun
, i
);
1407 basic_block
*body
= get_loop_body_in_dom_order (father
);
1408 for (unsigned j
= 0; j
< father
->num_nodes
; j
++)
1409 propagate_constants_for_unrolling (body
[j
]);
1412 BITMAP_FREE (fathers
);
1414 /* This will take care of removing completely unrolled loops
1415 from the loop structures so we can continue unrolling now
1417 if (cleanup_tree_cfg ())
1418 update_ssa (TODO_update_ssa_only_virtuals
);
1420 /* Clean up the information about numbers of iterations, since
1421 complete unrolling might have invalidated it. */
1423 if (flag_checking
&& loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1424 verify_loop_closed_ssa (true);
1426 if (loop_closed_ssa_invalidated
)
1427 BITMAP_FREE (loop_closed_ssa_invalidated
);
1430 && ++iteration
<= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS
));
1432 BITMAP_FREE (father_bbs
);
1434 if (irred_invalidated
1435 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1436 mark_irreducible_loops ();
1441 /* Canonical induction variable creation pass. */
1445 const pass_data pass_data_iv_canon
=
1447 GIMPLE_PASS
, /* type */
1448 "ivcanon", /* name */
1449 OPTGROUP_LOOP
, /* optinfo_flags */
1450 TV_TREE_LOOP_IVCANON
, /* tv_id */
1451 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1452 0, /* properties_provided */
1453 0, /* properties_destroyed */
1454 0, /* todo_flags_start */
1455 0, /* todo_flags_finish */
1458 class pass_iv_canon
: public gimple_opt_pass
1461 pass_iv_canon (gcc::context
*ctxt
)
1462 : gimple_opt_pass (pass_data_iv_canon
, ctxt
)
1465 /* opt_pass methods: */
1466 virtual bool gate (function
*) { return flag_tree_loop_ivcanon
!= 0; }
1467 virtual unsigned int execute (function
*fun
);
1469 }; // class pass_iv_canon
1472 pass_iv_canon::execute (function
*fun
)
1474 if (number_of_loops (fun
) <= 1)
1477 return canonicalize_induction_variables ();
1483 make_pass_iv_canon (gcc::context
*ctxt
)
1485 return new pass_iv_canon (ctxt
);
1488 /* Complete unrolling of loops. */
1492 const pass_data pass_data_complete_unroll
=
1494 GIMPLE_PASS
, /* type */
1495 "cunroll", /* name */
1496 OPTGROUP_LOOP
, /* optinfo_flags */
1497 TV_COMPLETE_UNROLL
, /* tv_id */
1498 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1499 0, /* properties_provided */
1500 0, /* properties_destroyed */
1501 0, /* todo_flags_start */
1502 0, /* todo_flags_finish */
1505 class pass_complete_unroll
: public gimple_opt_pass
1508 pass_complete_unroll (gcc::context
*ctxt
)
1509 : gimple_opt_pass (pass_data_complete_unroll
, ctxt
)
1512 /* opt_pass methods: */
1513 virtual unsigned int execute (function
*);
1515 }; // class pass_complete_unroll
1518 pass_complete_unroll::execute (function
*fun
)
1520 if (number_of_loops (fun
) <= 1)
1523 /* If we ever decide to run loop peeling more than once, we will need to
1524 track loops already peeled in loop structures themselves to avoid
1525 re-peeling the same loop multiple times. */
1526 if (flag_peel_loops
)
1527 peeled_loops
= BITMAP_ALLOC (NULL
);
1528 int val
= tree_unroll_loops_completely (flag_unroll_loops
1530 || optimize
>= 3, true);
1533 BITMAP_FREE (peeled_loops
);
1534 peeled_loops
= NULL
;
1542 make_pass_complete_unroll (gcc::context
*ctxt
)
1544 return new pass_complete_unroll (ctxt
);
1547 /* Complete unrolling of inner loops. */
1551 const pass_data pass_data_complete_unrolli
=
1553 GIMPLE_PASS
, /* type */
1554 "cunrolli", /* name */
1555 OPTGROUP_LOOP
, /* optinfo_flags */
1556 TV_COMPLETE_UNROLL
, /* tv_id */
1557 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1558 0, /* properties_provided */
1559 0, /* properties_destroyed */
1560 0, /* todo_flags_start */
1561 0, /* todo_flags_finish */
1564 class pass_complete_unrolli
: public gimple_opt_pass
1567 pass_complete_unrolli (gcc::context
*ctxt
)
1568 : gimple_opt_pass (pass_data_complete_unrolli
, ctxt
)
1571 /* opt_pass methods: */
1572 virtual bool gate (function
*) { return optimize
>= 2; }
1573 virtual unsigned int execute (function
*);
1575 }; // class pass_complete_unrolli
1578 pass_complete_unrolli::execute (function
*fun
)
1582 loop_optimizer_init (LOOPS_NORMAL
1583 | LOOPS_HAVE_RECORDED_EXITS
);
1584 if (number_of_loops (fun
) > 1)
1587 ret
= tree_unroll_loops_completely (optimize
>= 3, false);
1588 free_numbers_of_iterations_estimates (fun
);
1591 loop_optimizer_finalize ();
1599 make_pass_complete_unrolli (gcc::context
*ctxt
)
1601 return new pass_complete_unrolli (ctxt
);