1 /* Induction variable canonicalization and loop peeling.
2 Copyright (C) 2004-2017 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
)
160 if (is_gimple_min_invariant (op
))
163 /* We can still fold accesses to constant arrays when index is known. */
164 if (TREE_CODE (op
) != SSA_NAME
)
168 /* First make fast look if we see constant array inside. */
169 while (handled_component_p (base
))
170 base
= TREE_OPERAND (base
, 0);
172 && ctor_for_folding (base
) != error_mark_node
)
173 || CONSTANT_CLASS_P (base
))
175 /* If so, see if we understand all the indices. */
177 while (handled_component_p (base
))
179 if (TREE_CODE (base
) == ARRAY_REF
180 && !constant_after_peeling (TREE_OPERAND (base
, 1), stmt
, loop
))
182 base
= TREE_OPERAND (base
, 0);
189 /* Induction variables are constants when defined in loop. */
190 if (loop_containing_stmt (stmt
) != loop
)
192 tree ev
= analyze_scalar_evolution (loop
, op
);
193 if (chrec_contains_undetermined (ev
)
194 || chrec_contains_symbols (ev
))
199 /* Computes an estimated number of insns in LOOP.
200 EXIT (if non-NULL) is an exite edge that will be eliminated in all but last
201 iteration of the loop.
202 EDGE_TO_CANCEL (if non-NULL) is an non-exit edge eliminated in the last iteration
204 Return results in SIZE, estimate benefits for complete unrolling exiting by EXIT.
205 Stop estimating after UPPER_BOUND is met. Return true in this case. */
208 tree_estimate_loop_size (struct loop
*loop
, edge exit
, edge edge_to_cancel
,
209 struct loop_size
*size
, int upper_bound
)
211 basic_block
*body
= get_loop_body (loop
);
212 gimple_stmt_iterator gsi
;
215 vec
<basic_block
> path
= get_loop_hot_path (loop
);
218 size
->eliminated_by_peeling
= 0;
219 size
->last_iteration
= 0;
220 size
->last_iteration_eliminated_by_peeling
= 0;
221 size
->num_pure_calls_on_hot_path
= 0;
222 size
->num_non_pure_calls_on_hot_path
= 0;
223 size
->non_call_stmts_on_hot_path
= 0;
224 size
->num_branches_on_hot_path
= 0;
225 size
->constant_iv
= 0;
227 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
228 fprintf (dump_file
, "Estimating sizes for loop %i\n", loop
->num
);
229 for (i
= 0; i
< loop
->num_nodes
; i
++)
231 if (edge_to_cancel
&& body
[i
] != edge_to_cancel
->src
232 && dominated_by_p (CDI_DOMINATORS
, body
[i
], edge_to_cancel
->src
))
236 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
237 fprintf (dump_file
, " BB: %i, after_exit: %i\n", body
[i
]->index
,
240 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
242 gimple
*stmt
= gsi_stmt (gsi
);
243 int num
= estimate_num_insns (stmt
, &eni_size_weights
);
244 bool likely_eliminated
= false;
245 bool likely_eliminated_last
= false;
246 bool likely_eliminated_peeled
= false;
248 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
250 fprintf (dump_file
, " size: %3i ", num
);
251 print_gimple_stmt (dump_file
, gsi_stmt (gsi
), 0);
254 /* Look for reasons why we might optimize this stmt away. */
256 if (!gimple_has_side_effects (stmt
))
258 /* Exit conditional. */
259 if (exit
&& body
[i
] == exit
->src
260 && stmt
== last_stmt (exit
->src
))
262 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
263 fprintf (dump_file
, " Exit condition will be eliminated "
264 "in peeled copies.\n");
265 likely_eliminated_peeled
= true;
267 if (edge_to_cancel
&& body
[i
] == edge_to_cancel
->src
268 && stmt
== last_stmt (edge_to_cancel
->src
))
270 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
271 fprintf (dump_file
, " Exit condition will be eliminated "
273 likely_eliminated_last
= true;
275 /* Sets of IV variables */
276 if (gimple_code (stmt
) == GIMPLE_ASSIGN
277 && constant_after_peeling (gimple_assign_lhs (stmt
), stmt
, loop
))
279 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
280 fprintf (dump_file
, " Induction variable computation will"
281 " be folded away.\n");
282 likely_eliminated
= true;
284 /* Assignments of IV variables. */
285 else if (gimple_code (stmt
) == GIMPLE_ASSIGN
286 && TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
287 && constant_after_peeling (gimple_assign_rhs1 (stmt
),
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
))
296 " 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
,
303 && constant_after_peeling (gimple_cond_rhs (stmt
), stmt
,
305 /* We don't simplify all constant compares so make sure
306 they are not both constant already. See PR70288. */
307 && (! is_gimple_min_invariant (gimple_cond_lhs (stmt
))
308 || ! is_gimple_min_invariant
309 (gimple_cond_rhs (stmt
))))
310 || (gimple_code (stmt
) == GIMPLE_SWITCH
311 && constant_after_peeling (gimple_switch_index (
315 && ! is_gimple_min_invariant
317 (as_a
<gswitch
*> (stmt
)))))
319 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
320 fprintf (dump_file
, " Constant conditional.\n");
321 likely_eliminated
= true;
325 size
->overall
+= num
;
326 if (likely_eliminated
|| likely_eliminated_peeled
)
327 size
->eliminated_by_peeling
+= num
;
330 size
->last_iteration
+= num
;
331 if (likely_eliminated
|| likely_eliminated_last
)
332 size
->last_iteration_eliminated_by_peeling
+= num
;
334 if ((size
->overall
* 3 / 2 - size
->eliminated_by_peeling
335 - size
->last_iteration_eliminated_by_peeling
) > upper_bound
)
343 while (path
.length ())
345 basic_block bb
= path
.pop ();
346 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
348 gimple
*stmt
= gsi_stmt (gsi
);
349 if (gimple_code (stmt
) == GIMPLE_CALL
350 && !gimple_inexpensive_call_p (as_a
<gcall
*> (stmt
)))
352 int flags
= gimple_call_flags (stmt
);
353 if (flags
& (ECF_PURE
| ECF_CONST
))
354 size
->num_pure_calls_on_hot_path
++;
356 size
->num_non_pure_calls_on_hot_path
++;
357 size
->num_branches_on_hot_path
++;
359 /* Count inexpensive calls as non-calls, because they will likely
361 else if (gimple_code (stmt
) != GIMPLE_DEBUG
)
362 size
->non_call_stmts_on_hot_path
++;
363 if (((gimple_code (stmt
) == GIMPLE_COND
364 && (!constant_after_peeling (gimple_cond_lhs (stmt
), stmt
, loop
)
365 || constant_after_peeling (gimple_cond_rhs (stmt
), stmt
,
367 || (gimple_code (stmt
) == GIMPLE_SWITCH
368 && !constant_after_peeling (gimple_switch_index (
369 as_a
<gswitch
*> (stmt
)),
371 && (!exit
|| bb
!= exit
->src
))
372 size
->num_branches_on_hot_path
++;
376 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
377 fprintf (dump_file
, "size: %i-%i, last_iteration: %i-%i\n", size
->overall
,
378 size
->eliminated_by_peeling
, size
->last_iteration
,
379 size
->last_iteration_eliminated_by_peeling
);
385 /* Estimate number of insns of completely unrolled loop.
386 It is (NUNROLL + 1) * size of loop body with taking into account
387 the fact that in last copy everything after exit conditional
388 is dead and that some instructions will be eliminated after
391 Loop body is likely going to simplify further, this is difficult
392 to guess, we just decrease the result by 1/3. */
394 static unsigned HOST_WIDE_INT
395 estimated_unrolled_size (struct loop_size
*size
,
396 unsigned HOST_WIDE_INT nunroll
)
398 HOST_WIDE_INT unr_insns
= ((nunroll
)
399 * (HOST_WIDE_INT
) (size
->overall
400 - size
->eliminated_by_peeling
));
403 unr_insns
+= size
->last_iteration
- size
->last_iteration_eliminated_by_peeling
;
405 unr_insns
= unr_insns
* 2 / 3;
412 /* Loop LOOP is known to not loop. See if there is an edge in the loop
413 body that can be remove to make the loop to always exit and at
414 the same time it does not make any code potentially executed
415 during the last iteration dead.
417 After complete unrolling we still may get rid of the conditional
418 on the exit in the last copy even if we have no idea what it does.
419 This is quite common case for loops of form
425 Here we prove the loop to iterate 5 times but we do not know
426 it from induction variable.
428 For now we handle only simple case where there is exit condition
429 just before the latch block and the latch block contains no statements
430 with side effect that may otherwise terminate the execution of loop
431 (such as by EH or by terminating the program or longjmp).
433 In the general case we may want to cancel the paths leading to statements
434 loop-niter identified as having undefined effect in the last iteration.
435 The other cases are hopefully rare and will be cleaned up later. */
438 loop_edge_to_cancel (struct loop
*loop
)
443 gimple_stmt_iterator gsi
;
445 /* We want only one predecestor of the loop. */
446 if (EDGE_COUNT (loop
->latch
->preds
) > 1)
449 exits
= get_loop_exit_edges (loop
);
451 FOR_EACH_VEC_ELT (exits
, i
, edge_to_cancel
)
453 /* Find the other edge than the loop exit
454 leaving the conditoinal. */
455 if (EDGE_COUNT (edge_to_cancel
->src
->succs
) != 2)
457 if (EDGE_SUCC (edge_to_cancel
->src
, 0) == edge_to_cancel
)
458 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 1);
460 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 0);
462 /* We only can handle conditionals. */
463 if (!(edge_to_cancel
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
466 /* We should never have conditionals in the loop latch. */
467 gcc_assert (edge_to_cancel
->dest
!= loop
->header
);
469 /* Check that it leads to loop latch. */
470 if (edge_to_cancel
->dest
!= loop
->latch
)
475 /* Verify that the code in loop latch does nothing that may end program
476 execution without really reaching the exit. This may include
477 non-pure/const function calls, EH statements, volatile ASMs etc. */
478 for (gsi
= gsi_start_bb (loop
->latch
); !gsi_end_p (gsi
); gsi_next (&gsi
))
479 if (gimple_has_side_effects (gsi_stmt (gsi
)))
481 return edge_to_cancel
;
487 /* Remove all tests for exits that are known to be taken after LOOP was
488 peeled NPEELED times. Put gcc_unreachable before every statement
489 known to not be executed. */
492 remove_exits_and_undefined_stmts (struct loop
*loop
, unsigned int npeeled
)
494 struct nb_iter_bound
*elt
;
495 bool changed
= false;
497 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
499 /* If statement is known to be undefined after peeling, turn it
500 into unreachable (or trap when debugging experience is supposed
503 && wi::ltu_p (elt
->bound
, npeeled
))
505 gimple_stmt_iterator gsi
= gsi_for_stmt (elt
->stmt
);
506 gcall
*stmt
= gimple_build_call
507 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
), 0);
508 gimple_set_location (stmt
, gimple_location (elt
->stmt
));
509 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
510 split_block (gimple_bb (stmt
), stmt
);
512 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
514 fprintf (dump_file
, "Forced statement unreachable: ");
515 print_gimple_stmt (dump_file
, elt
->stmt
, 0);
518 /* If we know the exit will be taken after peeling, update. */
519 else if (elt
->is_exit
520 && wi::leu_p (elt
->bound
, npeeled
))
522 basic_block bb
= gimple_bb (elt
->stmt
);
523 edge exit_edge
= EDGE_SUCC (bb
, 0);
525 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
527 fprintf (dump_file
, "Forced exit to be taken: ");
528 print_gimple_stmt (dump_file
, elt
->stmt
, 0);
530 if (!loop_exit_edge_p (loop
, exit_edge
))
531 exit_edge
= EDGE_SUCC (bb
, 1);
532 exit_edge
->probability
= profile_probability::always ();
533 gcc_checking_assert (loop_exit_edge_p (loop
, exit_edge
));
534 gcond
*cond_stmt
= as_a
<gcond
*> (elt
->stmt
);
535 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
536 gimple_cond_make_true (cond_stmt
);
538 gimple_cond_make_false (cond_stmt
);
539 update_stmt (cond_stmt
);
546 /* Remove all exits that are known to be never taken because of the loop bound
550 remove_redundant_iv_tests (struct loop
*loop
)
552 struct nb_iter_bound
*elt
;
553 bool changed
= false;
555 if (!loop
->any_upper_bound
)
557 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
559 /* Exit is pointless if it won't be taken before loop reaches
561 if (elt
->is_exit
&& loop
->any_upper_bound
562 && wi::ltu_p (loop
->nb_iterations_upper_bound
, elt
->bound
))
564 basic_block bb
= gimple_bb (elt
->stmt
);
565 edge exit_edge
= EDGE_SUCC (bb
, 0);
566 struct tree_niter_desc niter
;
568 if (!loop_exit_edge_p (loop
, exit_edge
))
569 exit_edge
= EDGE_SUCC (bb
, 1);
571 /* Only when we know the actual number of iterations, not
572 just a bound, we can remove the exit. */
573 if (!number_of_iterations_exit (loop
, exit_edge
,
574 &niter
, false, false)
575 || !integer_onep (niter
.assumptions
)
576 || !integer_zerop (niter
.may_be_zero
)
578 || TREE_CODE (niter
.niter
) != INTEGER_CST
579 || !wi::ltu_p (loop
->nb_iterations_upper_bound
,
580 wi::to_widest (niter
.niter
)))
583 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
585 fprintf (dump_file
, "Removed pointless exit: ");
586 print_gimple_stmt (dump_file
, elt
->stmt
, 0);
588 gcond
*cond_stmt
= as_a
<gcond
*> (elt
->stmt
);
589 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
590 gimple_cond_make_false (cond_stmt
);
592 gimple_cond_make_true (cond_stmt
);
593 update_stmt (cond_stmt
);
600 /* Stores loops that will be unlooped and edges that will be removed
601 after we process whole loop tree. */
602 static vec
<loop_p
> loops_to_unloop
;
603 static vec
<int> loops_to_unloop_nunroll
;
604 static vec
<edge
> edges_to_remove
;
605 /* Stores loops that has been peeled. */
606 static bitmap peeled_loops
;
608 /* Cancel all fully unrolled loops by putting __builtin_unreachable
610 We do it after all unrolling since unlooping moves basic blocks
611 across loop boundaries trashing loop closed SSA form as well
612 as SCEV info needed to be intact during unrolling.
614 IRRED_INVALIDATED is used to bookkeep if information about
615 irreducible regions may become invalid as a result
616 of the transformation.
617 LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case
618 when we need to go into loop closed SSA form. */
621 unloop_loops (bitmap loop_closed_ssa_invalidated
,
622 bool *irred_invalidated
)
624 while (loops_to_unloop
.length ())
626 struct loop
*loop
= loops_to_unloop
.pop ();
627 int n_unroll
= loops_to_unloop_nunroll
.pop ();
628 basic_block latch
= loop
->latch
;
629 edge latch_edge
= loop_latch_edge (loop
);
630 int flags
= latch_edge
->flags
;
631 location_t locus
= latch_edge
->goto_locus
;
633 gimple_stmt_iterator gsi
;
635 remove_exits_and_undefined_stmts (loop
, n_unroll
);
637 /* Unloop destroys the latch edge. */
638 unloop (loop
, irred_invalidated
, loop_closed_ssa_invalidated
);
640 /* Create new basic block for the latch edge destination and wire
642 stmt
= gimple_build_call (builtin_decl_implicit (BUILT_IN_UNREACHABLE
), 0);
643 latch_edge
= make_edge (latch
, create_basic_block (NULL
, NULL
, latch
), flags
);
644 latch_edge
->probability
= profile_probability::never ();
645 latch_edge
->flags
|= flags
;
646 latch_edge
->goto_locus
= locus
;
648 add_bb_to_loop (latch_edge
->dest
, current_loops
->tree_root
);
649 latch_edge
->dest
->count
= profile_count::zero ();
650 set_immediate_dominator (CDI_DOMINATORS
, latch_edge
->dest
, latch_edge
->src
);
652 gsi
= gsi_start_bb (latch_edge
->dest
);
653 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
655 loops_to_unloop
.release ();
656 loops_to_unloop_nunroll
.release ();
658 /* Remove edges in peeled copies. */
661 FOR_EACH_VEC_ELT (edges_to_remove
, i
, e
)
663 bool ok
= remove_path (e
, irred_invalidated
, loop_closed_ssa_invalidated
);
666 edges_to_remove
.release ();
669 /* Tries to unroll LOOP completely, i.e. NITER times.
670 UL determines which loops we are allowed to unroll.
671 EXIT is the exit of the loop that should be eliminated.
672 MAXITER specfy bound on number of iterations, -1 if it is
673 not known or too large for HOST_WIDE_INT. The location
674 LOCUS corresponding to the loop is used when emitting
675 a summary of the unroll to the dump file. */
678 try_unroll_loop_completely (struct loop
*loop
,
679 edge exit
, tree niter
,
680 enum unroll_level ul
,
681 HOST_WIDE_INT maxiter
,
682 location_t locus
, bool allow_peel
)
684 unsigned HOST_WIDE_INT n_unroll
= 0;
685 bool n_unroll_found
= false;
686 edge edge_to_cancel
= NULL
;
688 /* See if we proved number of iterations to be low constant.
690 EXIT is an edge that will be removed in all but last iteration of
693 EDGE_TO_CACNEL is an edge that will be removed from the last iteration
694 of the unrolled sequence and is expected to make the final loop not
697 If the number of execution of loop is determined by standard induction
698 variable test, then EXIT and EDGE_TO_CANCEL are the two edges leaving
700 if (tree_fits_uhwi_p (niter
))
702 n_unroll
= tree_to_uhwi (niter
);
703 n_unroll_found
= true;
704 edge_to_cancel
= EDGE_SUCC (exit
->src
, 0);
705 if (edge_to_cancel
== exit
)
706 edge_to_cancel
= EDGE_SUCC (exit
->src
, 1);
708 /* We do not know the number of iterations and thus we can not eliminate
713 /* See if we can improve our estimate by using recorded loop bounds. */
714 if ((allow_peel
|| maxiter
== 0 || ul
== UL_NO_GROWTH
)
716 && (!n_unroll_found
|| (unsigned HOST_WIDE_INT
)maxiter
< n_unroll
))
719 n_unroll_found
= true;
720 /* Loop terminates before the IV variable test, so we can not
721 remove it in the last iteration. */
722 edge_to_cancel
= NULL
;
729 && n_unroll
> (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
))
731 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
732 fprintf (dump_file
, "Not unrolling loop %d "
733 "(--param max-completely-peel-times limit reached).\n",
739 edge_to_cancel
= loop_edge_to_cancel (loop
);
743 if (ul
== UL_SINGLE_ITER
)
748 /* If the unrolling factor is too large, bail out. */
749 if (n_unroll
> (unsigned)loop
->unroll
)
751 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
753 "Not unrolling loop %d: "
754 "user didn't want it unrolled completely.\n",
761 struct loop_size size
;
762 /* EXIT can be removed only if we are sure it passes first N_UNROLL
764 bool remove_exit
= (exit
&& niter
765 && TREE_CODE (niter
) == INTEGER_CST
766 && wi::leu_p (n_unroll
, wi::to_widest (niter
)));
768 = tree_estimate_loop_size
769 (loop
, remove_exit
? exit
: NULL
, edge_to_cancel
, &size
,
770 PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
));
773 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
774 fprintf (dump_file
, "Not unrolling loop %d: it is too large.\n",
779 unsigned HOST_WIDE_INT ninsns
= size
.overall
;
780 unsigned HOST_WIDE_INT unr_insns
781 = estimated_unrolled_size (&size
, n_unroll
);
782 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
784 fprintf (dump_file
, " Loop size: %d\n", (int) ninsns
);
785 fprintf (dump_file
, " Estimated size after unrolling: %d\n",
789 /* If the code is going to shrink, we don't need to be extra
790 cautious on guessing if the unrolling is going to be
793 /* If there is IV variable that will become constant, we
794 save one instruction in the loop prologue we do not
795 account otherwise. */
796 <= ninsns
+ (size
.constant_iv
!= false))
798 /* We unroll only inner loops, because we do not consider it
799 profitable otheriwse. We still can cancel loopback edge
800 of not rolling loop; this is always a good idea. */
801 else if (ul
== UL_NO_GROWTH
)
803 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
804 fprintf (dump_file
, "Not unrolling loop %d: size would grow.\n",
808 /* Outer loops tend to be less interesting candidates for
809 complete unrolling unless we can do a lot of propagation
810 into the inner loop body. For now we disable outer loop
811 unrolling when the code would grow. */
812 else if (loop
->inner
)
814 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
815 fprintf (dump_file
, "Not unrolling loop %d: "
816 "it is not innermost and code would grow.\n",
820 /* If there is call on a hot path through the loop, then
821 there is most probably not much to optimize. */
822 else if (size
.num_non_pure_calls_on_hot_path
)
824 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
825 fprintf (dump_file
, "Not unrolling loop %d: "
826 "contains call and code would grow.\n",
830 /* If there is pure/const call in the function, then we can
831 still optimize the unrolled loop body if it contains some
832 other interesting code than the calls and code storing or
833 cumulating the return value. */
834 else if (size
.num_pure_calls_on_hot_path
835 /* One IV increment, one test, one ivtmp store and
836 one useful stmt. That is about minimal loop
838 && (size
.non_call_stmts_on_hot_path
839 <= 3 + size
.num_pure_calls_on_hot_path
))
841 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
842 fprintf (dump_file
, "Not unrolling loop %d: "
843 "contains just pure calls and code would grow.\n",
847 /* Complete unrolling is major win when control flow is
848 removed and one big basic block is created. If the loop
849 contains control flow the optimization may still be a win
850 because of eliminating the loop overhead but it also may
851 blow the branch predictor tables. Limit number of
852 branches on the hot path through the peeled sequence. */
853 else if (size
.num_branches_on_hot_path
* (int)n_unroll
854 > PARAM_VALUE (PARAM_MAX_PEEL_BRANCHES
))
856 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
857 fprintf (dump_file
, "Not unrolling loop %d: "
858 "number of branches on hot path in the unrolled "
859 "sequence reaches --param max-peel-branches limit.\n",
864 > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
))
866 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
867 fprintf (dump_file
, "Not unrolling loop %d: "
868 "number of insns in the unrolled sequence reaches "
869 "--param max-completely-peeled-insns limit.\n",
875 initialize_original_copy_tables ();
876 auto_sbitmap
wont_exit (n_unroll
+ 1);
878 && TREE_CODE (niter
) == INTEGER_CST
879 && wi::leu_p (n_unroll
, wi::to_widest (niter
)))
881 bitmap_ones (wont_exit
);
882 if (wi::eq_p (wi::to_widest (niter
), n_unroll
)
884 bitmap_clear_bit (wont_exit
, 0);
889 bitmap_clear (wont_exit
);
892 if (!gimple_duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
894 exit
, &edges_to_remove
,
895 DLTHE_FLAG_UPDATE_FREQ
896 | DLTHE_FLAG_COMPLETTE_PEEL
))
898 free_original_copy_tables ();
899 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
900 fprintf (dump_file
, "Failed to duplicate the loop\n");
904 free_original_copy_tables ();
907 /* Remove the conditional from the last copy of the loop. */
910 gcond
*cond
= as_a
<gcond
*> (last_stmt (edge_to_cancel
->src
));
911 force_edge_cold (edge_to_cancel
, true);
912 if (edge_to_cancel
->flags
& EDGE_TRUE_VALUE
)
913 gimple_cond_make_false (cond
);
915 gimple_cond_make_true (cond
);
917 /* Do not remove the path, as doing so may remove outer loop and
918 confuse bookkeeping code in tree_unroll_loops_completely. */
921 /* Store the loop for later unlooping and exit removal. */
922 loops_to_unloop
.safe_push (loop
);
923 loops_to_unloop_nunroll
.safe_push (n_unroll
);
925 if (dump_enabled_p ())
928 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
929 "loop turned into non-loop; it never loops\n");
932 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
933 "loop with %d iterations completely unrolled",
935 if (loop
->header
->count
.initialized_p ())
936 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
,
937 " (header execution count %d)",
938 (int)loop
->header
->count
.to_gcov_type ());
939 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, "\n");
943 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
946 fprintf (dump_file
, "Exit condition of peeled iterations was "
949 fprintf (dump_file
, "Last iteration exit edge was proved true.\n");
951 fprintf (dump_file
, "Latch of last iteration was marked by "
952 "__builtin_unreachable ().\n");
958 /* Return number of instructions after peeling. */
959 static unsigned HOST_WIDE_INT
960 estimated_peeled_sequence_size (struct loop_size
*size
,
961 unsigned HOST_WIDE_INT npeel
)
963 return MAX (npeel
* (HOST_WIDE_INT
) (size
->overall
964 - size
->eliminated_by_peeling
), 1);
967 /* If the loop is expected to iterate N times and is
968 small enough, duplicate the loop body N+1 times before
969 the loop itself. This way the hot path will never
971 Parameters are the same as for try_unroll_loops_completely */
974 try_peel_loop (struct loop
*loop
,
975 edge exit
, tree niter
,
976 HOST_WIDE_INT maxiter
)
979 struct loop_size size
;
983 || PARAM_VALUE (PARAM_MAX_PEEL_TIMES
) <= 0
987 if (bitmap_bit_p (peeled_loops
, loop
->num
))
990 fprintf (dump_file
, "Not peeling: loop is already peeled\n");
994 /* We don't peel loops that will be unrolled as this can duplicate a
995 loop more times than the user requested. */
999 fprintf (dump_file
, "Not peeling: user didn't want it peeled.\n");
1003 /* Peel only innermost loops.
1004 While the code is perfectly capable of peeling non-innermost loops,
1005 the heuristics would probably need some improvements. */
1009 fprintf (dump_file
, "Not peeling: outer loop\n");
1013 if (!optimize_loop_for_speed_p (loop
))
1016 fprintf (dump_file
, "Not peeling: cold loop\n");
1020 /* Check if there is an estimate on the number of iterations. */
1021 npeel
= estimated_loop_iterations_int (loop
);
1023 npeel
= likely_max_loop_iterations_int (loop
);
1027 fprintf (dump_file
, "Not peeling: number of iterations is not "
1031 if (maxiter
>= 0 && maxiter
<= npeel
)
1034 fprintf (dump_file
, "Not peeling: upper bound is known so can "
1035 "unroll completely\n");
1039 /* We want to peel estimated number of iterations + 1 (so we never
1040 enter the loop on quick path). Check against PARAM_MAX_PEEL_TIMES
1041 and be sure to avoid overflows. */
1042 if (npeel
> PARAM_VALUE (PARAM_MAX_PEEL_TIMES
) - 1)
1045 fprintf (dump_file
, "Not peeling: rolls too much "
1046 "(%i + 1 > --param max-peel-times)\n", (int) npeel
);
1051 /* Check peeled loops size. */
1052 tree_estimate_loop_size (loop
, exit
, NULL
, &size
,
1053 PARAM_VALUE (PARAM_MAX_PEELED_INSNS
));
1054 if ((peeled_size
= estimated_peeled_sequence_size (&size
, (int) npeel
))
1055 > PARAM_VALUE (PARAM_MAX_PEELED_INSNS
))
1058 fprintf (dump_file
, "Not peeling: peeled sequence size is too large "
1059 "(%i insns > --param max-peel-insns)", peeled_size
);
1063 /* Duplicate possibly eliminating the exits. */
1064 initialize_original_copy_tables ();
1065 auto_sbitmap
wont_exit (npeel
+ 1);
1067 && TREE_CODE (niter
) == INTEGER_CST
1068 && wi::leu_p (npeel
, wi::to_widest (niter
)))
1070 bitmap_ones (wont_exit
);
1071 bitmap_clear_bit (wont_exit
, 0);
1076 bitmap_clear (wont_exit
);
1078 if (!gimple_duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1080 exit
, &edges_to_remove
,
1081 DLTHE_FLAG_UPDATE_FREQ
))
1083 free_original_copy_tables ();
1086 free_original_copy_tables ();
1087 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1089 fprintf (dump_file
, "Peeled loop %d, %i times.\n",
1090 loop
->num
, (int) npeel
);
1092 if (loop
->any_estimate
)
1094 if (wi::ltu_p (npeel
, loop
->nb_iterations_estimate
))
1095 loop
->nb_iterations_estimate
-= npeel
;
1097 loop
->nb_iterations_estimate
= 0;
1099 if (loop
->any_upper_bound
)
1101 if (wi::ltu_p (npeel
, loop
->nb_iterations_upper_bound
))
1102 loop
->nb_iterations_upper_bound
-= npeel
;
1104 loop
->nb_iterations_upper_bound
= 0;
1106 if (loop
->any_likely_upper_bound
)
1108 if (wi::ltu_p (npeel
, loop
->nb_iterations_likely_upper_bound
))
1109 loop
->nb_iterations_likely_upper_bound
-= npeel
;
1112 loop
->any_estimate
= true;
1113 loop
->nb_iterations_estimate
= 0;
1114 loop
->nb_iterations_likely_upper_bound
= 0;
1117 profile_count entry_count
= profile_count::zero ();
1121 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1122 if (e
->src
!= loop
->latch
)
1124 if (e
->src
->count
.initialized_p ())
1125 entry_count
= e
->src
->count
+ e
->src
->count
;
1126 gcc_assert (!flow_bb_inside_loop_p (loop
, e
->src
));
1128 profile_probability p
= profile_probability::very_unlikely ();
1129 p
= entry_count
.probability_in (loop
->header
->count
);
1130 scale_loop_profile (loop
, p
, 0);
1131 bitmap_set_bit (peeled_loops
, loop
->num
);
1134 /* Adds a canonical induction variable to LOOP if suitable.
1135 CREATE_IV is true if we may create a new iv. UL determines
1136 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
1137 to determine the number of iterations of a loop by direct evaluation.
1138 Returns true if cfg is changed. */
1141 canonicalize_loop_induction_variables (struct loop
*loop
,
1142 bool create_iv
, enum unroll_level ul
,
1143 bool try_eval
, bool allow_peel
)
1147 HOST_WIDE_INT maxiter
;
1148 bool modified
= false;
1149 location_t locus
= UNKNOWN_LOCATION
;
1151 niter
= number_of_latch_executions (loop
);
1152 exit
= single_exit (loop
);
1153 if (TREE_CODE (niter
) == INTEGER_CST
)
1154 locus
= gimple_location (last_stmt (exit
->src
));
1157 /* If the loop has more than one exit, try checking all of them
1158 for # of iterations determinable through scev. */
1160 niter
= find_loop_niter (loop
, &exit
);
1162 /* Finally if everything else fails, try brute force evaluation. */
1164 && (chrec_contains_undetermined (niter
)
1165 || TREE_CODE (niter
) != INTEGER_CST
))
1166 niter
= find_loop_niter_by_eval (loop
, &exit
);
1169 locus
= gimple_location (last_stmt (exit
->src
));
1171 if (TREE_CODE (niter
) != INTEGER_CST
)
1175 /* We work exceptionally hard here to estimate the bound
1176 by find_loop_niter_by_eval. Be sure to keep it for future. */
1177 if (niter
&& TREE_CODE (niter
) == INTEGER_CST
)
1179 record_niter_bound (loop
, wi::to_widest (niter
),
1180 exit
== single_likely_exit (loop
), true);
1183 /* Force re-computation of loop bounds so we can remove redundant exits. */
1184 maxiter
= max_loop_iterations_int (loop
);
1186 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1187 && TREE_CODE (niter
) == INTEGER_CST
)
1189 fprintf (dump_file
, "Loop %d iterates ", loop
->num
);
1190 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1191 fprintf (dump_file
, " times.\n");
1193 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1196 fprintf (dump_file
, "Loop %d iterates at most %i times.\n", loop
->num
,
1199 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1200 && likely_max_loop_iterations_int (loop
) >= 0)
1202 fprintf (dump_file
, "Loop %d likely iterates at most %i times.\n",
1203 loop
->num
, (int)likely_max_loop_iterations_int (loop
));
1206 /* Remove exits that are known to be never taken based on loop bound.
1207 Needs to be called after compilation of max_loop_iterations_int that
1208 populates the loop bounds. */
1209 modified
|= remove_redundant_iv_tests (loop
);
1211 if (try_unroll_loop_completely (loop
, exit
, niter
, ul
, maxiter
, locus
,
1216 && niter
&& !chrec_contains_undetermined (niter
)
1217 && exit
&& just_once_each_iteration_p (loop
, exit
->src
))
1218 create_canonical_iv (loop
, exit
, niter
);
1221 modified
|= try_peel_loop (loop
, exit
, niter
, maxiter
);
1226 /* The main entry point of the pass. Adds canonical induction variables
1227 to the suitable loops. */
1230 canonicalize_induction_variables (void)
1233 bool changed
= false;
1234 bool irred_invalidated
= false;
1235 bitmap loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
1237 estimate_numbers_of_iterations (cfun
);
1239 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1241 changed
|= canonicalize_loop_induction_variables (loop
,
1242 true, UL_SINGLE_ITER
,
1245 gcc_assert (!need_ssa_update_p (cfun
));
1247 unloop_loops (loop_closed_ssa_invalidated
, &irred_invalidated
);
1248 if (irred_invalidated
1249 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1250 mark_irreducible_loops ();
1252 /* Clean up the information about numbers of iterations, since brute force
1253 evaluation could reveal new information. */
1254 free_numbers_of_iterations_estimates (cfun
);
1257 if (!bitmap_empty_p (loop_closed_ssa_invalidated
))
1259 gcc_checking_assert (loops_state_satisfies_p (LOOP_CLOSED_SSA
));
1260 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1262 BITMAP_FREE (loop_closed_ssa_invalidated
);
1265 return TODO_cleanup_cfg
;
1269 /* Propagate constant SSA_NAMEs defined in basic block BB. */
1272 propagate_constants_for_unrolling (basic_block bb
)
1274 /* Look for degenerate PHI nodes with constant argument. */
1275 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); )
1277 gphi
*phi
= gsi
.phi ();
1278 tree result
= gimple_phi_result (phi
);
1279 tree arg
= gimple_phi_arg_def (phi
, 0);
1281 if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (result
)
1282 && gimple_phi_num_args (phi
) == 1
1283 && CONSTANT_CLASS_P (arg
))
1285 replace_uses_by (result
, arg
);
1286 gsi_remove (&gsi
, true);
1287 release_ssa_name (result
);
1293 /* Look for assignments to SSA names with constant RHS. */
1294 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
1296 gimple
*stmt
= gsi_stmt (gsi
);
1299 if (is_gimple_assign (stmt
)
1300 && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt
)) == tcc_constant
1301 && (lhs
= gimple_assign_lhs (stmt
), TREE_CODE (lhs
) == SSA_NAME
)
1302 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1304 replace_uses_by (lhs
, gimple_assign_rhs1 (stmt
));
1305 gsi_remove (&gsi
, true);
1306 release_ssa_name (lhs
);
1313 /* Process loops from innermost to outer, stopping at the innermost
1314 loop we unrolled. */
1317 tree_unroll_loops_completely_1 (bool may_increase_size
, bool unroll_outer
,
1318 bitmap father_bbs
, struct loop
*loop
)
1320 struct loop
*loop_father
;
1321 bool changed
= false;
1323 enum unroll_level ul
;
1325 /* Process inner loops first. */
1326 for (inner
= loop
->inner
; inner
!= NULL
; inner
= inner
->next
)
1327 changed
|= tree_unroll_loops_completely_1 (may_increase_size
,
1328 unroll_outer
, father_bbs
,
1331 /* If we changed an inner loop we cannot process outer loops in this
1332 iteration because SSA form is not up-to-date. Continue with
1333 siblings of outer loops instead. */
1337 /* Don't unroll #pragma omp simd loops until the vectorizer
1338 attempts to vectorize those. */
1339 if (loop
->force_vectorize
)
1342 /* Try to unroll this loop. */
1343 loop_father
= loop_outer (loop
);
1347 if (loop
->unroll
> 1)
1349 else if (may_increase_size
&& optimize_loop_nest_for_speed_p (loop
)
1350 /* Unroll outermost loops only if asked to do so or they do
1351 not cause code growth. */
1352 && (unroll_outer
|| loop_outer (loop_father
)))
1357 if (canonicalize_loop_induction_variables
1358 (loop
, false, ul
, !flag_tree_loop_ivcanon
, unroll_outer
))
1360 /* If we'll continue unrolling, we need to propagate constants
1361 within the new basic blocks to fold away induction variable
1362 computations; otherwise, the size might blow up before the
1363 iteration is complete and the IR eventually cleaned up. */
1364 if (loop_outer (loop_father
))
1365 bitmap_set_bit (father_bbs
, loop_father
->header
->index
);
1373 /* Unroll LOOPS completely if they iterate just few times. Unless
1374 MAY_INCREASE_SIZE is true, perform the unrolling only if the
1375 size of the code does not increase. */
1378 tree_unroll_loops_completely (bool may_increase_size
, bool unroll_outer
)
1380 bitmap father_bbs
= BITMAP_ALLOC (NULL
);
1383 bool irred_invalidated
= false;
1385 estimate_numbers_of_iterations (cfun
);
1390 bitmap loop_closed_ssa_invalidated
= NULL
;
1392 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1393 loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
1395 free_numbers_of_iterations_estimates (cfun
);
1396 estimate_numbers_of_iterations (cfun
);
1398 changed
= tree_unroll_loops_completely_1 (may_increase_size
,
1399 unroll_outer
, father_bbs
,
1400 current_loops
->tree_root
);
1405 unloop_loops (loop_closed_ssa_invalidated
, &irred_invalidated
);
1407 /* We can not use TODO_update_ssa_no_phi because VOPS gets confused. */
1408 if (loop_closed_ssa_invalidated
1409 && !bitmap_empty_p (loop_closed_ssa_invalidated
))
1410 rewrite_into_loop_closed_ssa (loop_closed_ssa_invalidated
,
1413 update_ssa (TODO_update_ssa
);
1415 /* father_bbs is a bitmap of loop father header BB indices.
1416 Translate that to what non-root loops these BBs belong to now. */
1418 bitmap fathers
= BITMAP_ALLOC (NULL
);
1419 EXECUTE_IF_SET_IN_BITMAP (father_bbs
, 0, i
, bi
)
1421 basic_block unrolled_loop_bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
1422 if (! unrolled_loop_bb
)
1424 if (loop_outer (unrolled_loop_bb
->loop_father
))
1425 bitmap_set_bit (fathers
,
1426 unrolled_loop_bb
->loop_father
->num
);
1428 bitmap_clear (father_bbs
);
1429 /* Propagate the constants within the new basic blocks. */
1430 EXECUTE_IF_SET_IN_BITMAP (fathers
, 0, i
, bi
)
1432 loop_p father
= get_loop (cfun
, i
);
1433 basic_block
*body
= get_loop_body_in_dom_order (father
);
1434 for (unsigned j
= 0; j
< father
->num_nodes
; j
++)
1435 propagate_constants_for_unrolling (body
[j
]);
1438 BITMAP_FREE (fathers
);
1440 /* This will take care of removing completely unrolled loops
1441 from the loop structures so we can continue unrolling now
1443 if (cleanup_tree_cfg ())
1444 update_ssa (TODO_update_ssa_only_virtuals
);
1446 /* Clean up the information about numbers of iterations, since
1447 complete unrolling might have invalidated it. */
1449 if (flag_checking
&& loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1450 verify_loop_closed_ssa (true);
1452 if (loop_closed_ssa_invalidated
)
1453 BITMAP_FREE (loop_closed_ssa_invalidated
);
1456 && ++iteration
<= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS
));
1458 BITMAP_FREE (father_bbs
);
1460 if (irred_invalidated
1461 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1462 mark_irreducible_loops ();
1467 /* Canonical induction variable creation pass. */
1471 const pass_data pass_data_iv_canon
=
1473 GIMPLE_PASS
, /* type */
1474 "ivcanon", /* name */
1475 OPTGROUP_LOOP
, /* optinfo_flags */
1476 TV_TREE_LOOP_IVCANON
, /* tv_id */
1477 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1478 0, /* properties_provided */
1479 0, /* properties_destroyed */
1480 0, /* todo_flags_start */
1481 0, /* todo_flags_finish */
1484 class pass_iv_canon
: public gimple_opt_pass
1487 pass_iv_canon (gcc::context
*ctxt
)
1488 : gimple_opt_pass (pass_data_iv_canon
, ctxt
)
1491 /* opt_pass methods: */
1492 virtual bool gate (function
*) { return flag_tree_loop_ivcanon
!= 0; }
1493 virtual unsigned int execute (function
*fun
);
1495 }; // class pass_iv_canon
1498 pass_iv_canon::execute (function
*fun
)
1500 if (number_of_loops (fun
) <= 1)
1503 return canonicalize_induction_variables ();
1509 make_pass_iv_canon (gcc::context
*ctxt
)
1511 return new pass_iv_canon (ctxt
);
1514 /* Complete unrolling of loops. */
1518 const pass_data pass_data_complete_unroll
=
1520 GIMPLE_PASS
, /* type */
1521 "cunroll", /* name */
1522 OPTGROUP_LOOP
, /* optinfo_flags */
1523 TV_COMPLETE_UNROLL
, /* tv_id */
1524 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1525 0, /* properties_provided */
1526 0, /* properties_destroyed */
1527 0, /* todo_flags_start */
1528 0, /* todo_flags_finish */
1531 class pass_complete_unroll
: public gimple_opt_pass
1534 pass_complete_unroll (gcc::context
*ctxt
)
1535 : gimple_opt_pass (pass_data_complete_unroll
, ctxt
)
1538 /* opt_pass methods: */
1539 virtual unsigned int execute (function
*);
1541 }; // class pass_complete_unroll
1544 pass_complete_unroll::execute (function
*fun
)
1546 if (number_of_loops (fun
) <= 1)
1549 /* If we ever decide to run loop peeling more than once, we will need to
1550 track loops already peeled in loop structures themselves to avoid
1551 re-peeling the same loop multiple times. */
1552 if (flag_peel_loops
)
1553 peeled_loops
= BITMAP_ALLOC (NULL
);
1554 unsigned int val
= tree_unroll_loops_completely (flag_unroll_loops
1556 || optimize
>= 3, true);
1559 BITMAP_FREE (peeled_loops
);
1560 peeled_loops
= NULL
;
1568 make_pass_complete_unroll (gcc::context
*ctxt
)
1570 return new pass_complete_unroll (ctxt
);
1573 /* Complete unrolling of inner loops. */
1577 const pass_data pass_data_complete_unrolli
=
1579 GIMPLE_PASS
, /* type */
1580 "cunrolli", /* name */
1581 OPTGROUP_LOOP
, /* optinfo_flags */
1582 TV_COMPLETE_UNROLL
, /* tv_id */
1583 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1584 0, /* properties_provided */
1585 0, /* properties_destroyed */
1586 0, /* todo_flags_start */
1587 0, /* todo_flags_finish */
1590 class pass_complete_unrolli
: public gimple_opt_pass
1593 pass_complete_unrolli (gcc::context
*ctxt
)
1594 : gimple_opt_pass (pass_data_complete_unrolli
, ctxt
)
1597 /* opt_pass methods: */
1598 virtual bool gate (function
*) { return optimize
>= 2; }
1599 virtual unsigned int execute (function
*);
1601 }; // class pass_complete_unrolli
1604 pass_complete_unrolli::execute (function
*fun
)
1608 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
1609 if (number_of_loops (fun
) > 1)
1612 ret
= tree_unroll_loops_completely (optimize
>= 3, false);
1615 loop_optimizer_finalize ();
1623 make_pass_complete_unrolli (gcc::context
*ctxt
)
1625 return new pass_complete_unrolli (ctxt
);