1 /* Induction variable canonicalization and loop peeling.
2 Copyright (C) 2004-2021 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"
62 #include "tree-inline.h"
63 #include "tree-cfgcleanup.h"
65 #include "tree-ssa-sccvn.h"
68 /* Specifies types of loops that may be unrolled. */
72 UL_SINGLE_ITER
, /* Only loops that exit immediately in the first
74 UL_NO_GROWTH
, /* Only loops whose unrolling will not cause increase
76 UL_ALL
/* All suitable loops. */
79 /* Adds a canonical induction variable to LOOP iterating NITER times. EXIT
80 is the exit edge whose condition is replaced. The ssa versions of the new
81 IV before and after increment will be stored in VAR_BEFORE and VAR_AFTER
82 if they are not NULL. */
85 create_canonical_iv (class loop
*loop
, edge exit
, tree niter
,
86 tree
*var_before
= NULL
, tree
*var_after
= NULL
)
91 gimple_stmt_iterator incr_at
;
94 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
96 fprintf (dump_file
, "Added canonical iv to loop %d, ", loop
->num
);
97 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
98 fprintf (dump_file
, " iterations.\n");
101 cond
= as_a
<gcond
*> (last_stmt (exit
->src
));
102 in
= EDGE_SUCC (exit
->src
, 0);
104 in
= EDGE_SUCC (exit
->src
, 1);
106 /* Note that we do not need to worry about overflows, since
107 type of niter is always unsigned and all comparisons are
108 just for equality/nonequality -- i.e. everything works
109 with a modulo arithmetics. */
111 type
= TREE_TYPE (niter
);
112 niter
= fold_build2 (PLUS_EXPR
, type
,
114 build_int_cst (type
, 1));
115 incr_at
= gsi_last_bb (in
->src
);
117 build_int_cst (type
, -1),
119 &incr_at
, false, var_before
, &var
);
123 cmp
= (exit
->flags
& EDGE_TRUE_VALUE
) ? EQ_EXPR
: NE_EXPR
;
124 gimple_cond_set_code (cond
, cmp
);
125 gimple_cond_set_lhs (cond
, var
);
126 gimple_cond_set_rhs (cond
, build_int_cst (type
, 0));
130 /* Describe size of loop as detected by tree_estimate_loop_size. */
133 /* Number of instructions in the loop. */
136 /* Number of instructions that will be likely optimized out in
137 peeled iterations of loop (i.e. computation based on induction
138 variable where induction variable starts at known constant.) */
139 int eliminated_by_peeling
;
141 /* Same statistics for last iteration of loop: it is smaller because
142 instructions after exit are not executed. */
144 int last_iteration_eliminated_by_peeling
;
146 /* If some IV computation will become constant. */
149 /* Number of call stmts that are not a builtin and are pure or const
150 present on the hot path. */
151 int num_pure_calls_on_hot_path
;
152 /* Number of call stmts that are not a builtin and are not pure nor const
153 present on the hot path. */
154 int num_non_pure_calls_on_hot_path
;
155 /* Number of statements other than calls in the loop. */
156 int non_call_stmts_on_hot_path
;
157 /* Number of branches seen on the hot path. */
158 int num_branches_on_hot_path
;
161 /* Return true if OP in STMT will be constant after peeling LOOP. */
164 constant_after_peeling (tree op
, gimple
*stmt
, class loop
*loop
)
166 if (CONSTANT_CLASS_P (op
))
169 /* We can still fold accesses to constant arrays when index is known. */
170 if (TREE_CODE (op
) != SSA_NAME
)
174 /* First make fast look if we see constant array inside. */
175 while (handled_component_p (base
))
176 base
= TREE_OPERAND (base
, 0);
178 && ctor_for_folding (base
) != error_mark_node
)
179 || CONSTANT_CLASS_P (base
))
181 /* If so, see if we understand all the indices. */
183 while (handled_component_p (base
))
185 if (TREE_CODE (base
) == ARRAY_REF
186 && !constant_after_peeling (TREE_OPERAND (base
, 1), stmt
, loop
))
188 base
= TREE_OPERAND (base
, 0);
195 /* Induction variables are constants when defined in loop. */
196 if (loop_containing_stmt (stmt
) != loop
)
198 tree ev
= analyze_scalar_evolution (loop
, op
);
199 if (chrec_contains_undetermined (ev
)
200 || chrec_contains_symbols (ev
))
205 /* Computes an estimated number of insns in LOOP.
206 EXIT (if non-NULL) is an exite edge that will be eliminated in all but last
207 iteration of the loop.
208 EDGE_TO_CANCEL (if non-NULL) is an non-exit edge eliminated in the last iteration
210 Return results in SIZE, estimate benefits for complete unrolling exiting by EXIT.
211 Stop estimating after UPPER_BOUND is met. Return true in this case. */
214 tree_estimate_loop_size (class loop
*loop
, edge exit
, edge edge_to_cancel
,
215 struct loop_size
*size
, int upper_bound
)
217 basic_block
*body
= get_loop_body (loop
);
218 gimple_stmt_iterator gsi
;
221 auto_vec
<basic_block
> path
= get_loop_hot_path (loop
);
224 size
->eliminated_by_peeling
= 0;
225 size
->last_iteration
= 0;
226 size
->last_iteration_eliminated_by_peeling
= 0;
227 size
->num_pure_calls_on_hot_path
= 0;
228 size
->num_non_pure_calls_on_hot_path
= 0;
229 size
->non_call_stmts_on_hot_path
= 0;
230 size
->num_branches_on_hot_path
= 0;
231 size
->constant_iv
= 0;
233 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
234 fprintf (dump_file
, "Estimating sizes for loop %i\n", loop
->num
);
235 for (i
= 0; i
< loop
->num_nodes
; i
++)
237 if (edge_to_cancel
&& body
[i
] != edge_to_cancel
->src
238 && dominated_by_p (CDI_DOMINATORS
, body
[i
], edge_to_cancel
->src
))
242 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
243 fprintf (dump_file
, " BB: %i, after_exit: %i\n", body
[i
]->index
,
246 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
248 gimple
*stmt
= gsi_stmt (gsi
);
249 int num
= estimate_num_insns (stmt
, &eni_size_weights
);
250 bool likely_eliminated
= false;
251 bool likely_eliminated_last
= false;
252 bool likely_eliminated_peeled
= false;
254 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
256 fprintf (dump_file
, " size: %3i ", num
);
257 print_gimple_stmt (dump_file
, gsi_stmt (gsi
), 0);
260 /* Look for reasons why we might optimize this stmt away. */
262 if (!gimple_has_side_effects (stmt
))
264 /* Exit conditional. */
265 if (exit
&& body
[i
] == exit
->src
266 && stmt
== last_stmt (exit
->src
))
268 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
269 fprintf (dump_file
, " Exit condition will be eliminated "
270 "in peeled copies.\n");
271 likely_eliminated_peeled
= true;
273 if (edge_to_cancel
&& body
[i
] == edge_to_cancel
->src
274 && stmt
== last_stmt (edge_to_cancel
->src
))
276 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
277 fprintf (dump_file
, " Exit condition will be eliminated "
279 likely_eliminated_last
= true;
281 /* Sets of IV variables */
282 if (gimple_code (stmt
) == GIMPLE_ASSIGN
283 && constant_after_peeling (gimple_assign_lhs (stmt
), stmt
, loop
))
285 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
286 fprintf (dump_file
, " Induction variable computation will"
287 " be folded away.\n");
288 likely_eliminated
= true;
290 /* Assignments of IV variables. */
291 else if (gimple_code (stmt
) == GIMPLE_ASSIGN
292 && TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
293 && constant_after_peeling (gimple_assign_rhs1 (stmt
),
295 && (gimple_assign_rhs_class (stmt
) != GIMPLE_BINARY_RHS
296 || constant_after_peeling (gimple_assign_rhs2 (stmt
),
298 && gimple_assign_rhs_class (stmt
) != GIMPLE_TERNARY_RHS
)
300 size
->constant_iv
= true;
301 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
303 " Constant expression will be folded away.\n");
304 likely_eliminated
= true;
307 else if ((gimple_code (stmt
) == GIMPLE_COND
308 && constant_after_peeling (gimple_cond_lhs (stmt
), stmt
,
310 && constant_after_peeling (gimple_cond_rhs (stmt
), stmt
,
312 /* We don't simplify all constant compares so make sure
313 they are not both constant already. See PR70288. */
314 && (! is_gimple_min_invariant (gimple_cond_lhs (stmt
))
315 || ! is_gimple_min_invariant
316 (gimple_cond_rhs (stmt
))))
317 || (gimple_code (stmt
) == GIMPLE_SWITCH
318 && constant_after_peeling (gimple_switch_index (
322 && ! is_gimple_min_invariant
324 (as_a
<gswitch
*> (stmt
)))))
326 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
327 fprintf (dump_file
, " Constant conditional.\n");
328 likely_eliminated
= true;
332 size
->overall
+= num
;
333 if (likely_eliminated
|| likely_eliminated_peeled
)
334 size
->eliminated_by_peeling
+= num
;
337 size
->last_iteration
+= num
;
338 if (likely_eliminated
|| likely_eliminated_last
)
339 size
->last_iteration_eliminated_by_peeling
+= num
;
341 if ((size
->overall
* 3 / 2 - size
->eliminated_by_peeling
342 - size
->last_iteration_eliminated_by_peeling
) > upper_bound
)
349 while (path
.length ())
351 basic_block bb
= path
.pop ();
352 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
354 gimple
*stmt
= gsi_stmt (gsi
);
355 if (gimple_code (stmt
) == GIMPLE_CALL
356 && !gimple_inexpensive_call_p (as_a
<gcall
*> (stmt
)))
358 int flags
= gimple_call_flags (stmt
);
359 if (flags
& (ECF_PURE
| ECF_CONST
))
360 size
->num_pure_calls_on_hot_path
++;
362 size
->num_non_pure_calls_on_hot_path
++;
363 size
->num_branches_on_hot_path
++;
365 /* Count inexpensive calls as non-calls, because they will likely
367 else if (gimple_code (stmt
) != GIMPLE_DEBUG
)
368 size
->non_call_stmts_on_hot_path
++;
369 if (((gimple_code (stmt
) == GIMPLE_COND
370 && (!constant_after_peeling (gimple_cond_lhs (stmt
), stmt
, loop
)
371 || !constant_after_peeling (gimple_cond_rhs (stmt
), stmt
,
373 || (gimple_code (stmt
) == GIMPLE_SWITCH
374 && !constant_after_peeling (gimple_switch_index (
375 as_a
<gswitch
*> (stmt
)),
377 && (!exit
|| bb
!= exit
->src
))
378 size
->num_branches_on_hot_path
++;
382 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
383 fprintf (dump_file
, "size: %i-%i, last_iteration: %i-%i\n", size
->overall
,
384 size
->eliminated_by_peeling
, size
->last_iteration
,
385 size
->last_iteration_eliminated_by_peeling
);
391 /* Estimate number of insns of completely unrolled loop.
392 It is (NUNROLL + 1) * size of loop body with taking into account
393 the fact that in last copy everything after exit conditional
394 is dead and that some instructions will be eliminated after
397 Loop body is likely going to simplify further, this is difficult
398 to guess, we just decrease the result by 1/3. */
400 static unsigned HOST_WIDE_INT
401 estimated_unrolled_size (struct loop_size
*size
,
402 unsigned HOST_WIDE_INT nunroll
)
404 HOST_WIDE_INT unr_insns
= ((nunroll
)
405 * (HOST_WIDE_INT
) (size
->overall
406 - size
->eliminated_by_peeling
));
409 unr_insns
+= size
->last_iteration
- size
->last_iteration_eliminated_by_peeling
;
411 unr_insns
= unr_insns
* 2 / 3;
418 /* Loop LOOP is known to not loop. See if there is an edge in the loop
419 body that can be remove to make the loop to always exit and at
420 the same time it does not make any code potentially executed
421 during the last iteration dead.
423 After complete unrolling we still may get rid of the conditional
424 on the exit in the last copy even if we have no idea what it does.
425 This is quite common case for loops of form
431 Here we prove the loop to iterate 5 times but we do not know
432 it from induction variable.
434 For now we handle only simple case where there is exit condition
435 just before the latch block and the latch block contains no statements
436 with side effect that may otherwise terminate the execution of loop
437 (such as by EH or by terminating the program or longjmp).
439 In the general case we may want to cancel the paths leading to statements
440 loop-niter identified as having undefined effect in the last iteration.
441 The other cases are hopefully rare and will be cleaned up later. */
444 loop_edge_to_cancel (class loop
*loop
)
448 gimple_stmt_iterator gsi
;
450 /* We want only one predecestor of the loop. */
451 if (EDGE_COUNT (loop
->latch
->preds
) > 1)
454 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
456 FOR_EACH_VEC_ELT (exits
, i
, edge_to_cancel
)
458 /* Find the other edge than the loop exit
459 leaving the conditoinal. */
460 if (EDGE_COUNT (edge_to_cancel
->src
->succs
) != 2)
462 if (EDGE_SUCC (edge_to_cancel
->src
, 0) == edge_to_cancel
)
463 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 1);
465 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 0);
467 /* We only can handle conditionals. */
468 if (!(edge_to_cancel
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
471 /* We should never have conditionals in the loop latch. */
472 gcc_assert (edge_to_cancel
->dest
!= loop
->header
);
474 /* Check that it leads to loop latch. */
475 if (edge_to_cancel
->dest
!= loop
->latch
)
478 /* Verify that the code in loop latch does nothing that may end program
479 execution without really reaching the exit. This may include
480 non-pure/const function calls, EH statements, volatile ASMs etc. */
481 for (gsi
= gsi_start_bb (loop
->latch
); !gsi_end_p (gsi
); gsi_next (&gsi
))
482 if (gimple_has_side_effects (gsi_stmt (gsi
)))
484 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 (class loop
*loop
, unsigned int npeeled
)
496 class 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);
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);
532 if (!loop_exit_edge_p (loop
, exit_edge
))
533 exit_edge
= EDGE_SUCC (bb
, 1);
534 exit_edge
->probability
= profile_probability::always ();
535 gcc_checking_assert (loop_exit_edge_p (loop
, exit_edge
));
536 gcond
*cond_stmt
= as_a
<gcond
*> (elt
->stmt
);
537 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
538 gimple_cond_make_true (cond_stmt
);
540 gimple_cond_make_false (cond_stmt
);
541 update_stmt (cond_stmt
);
548 /* Remove all exits that are known to be never taken because of the loop bound
552 remove_redundant_iv_tests (class loop
*loop
)
554 class nb_iter_bound
*elt
;
555 bool changed
= false;
557 if (!loop
->any_upper_bound
)
559 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
561 /* Exit is pointless if it won't be taken before loop reaches
563 if (elt
->is_exit
&& loop
->any_upper_bound
564 && wi::ltu_p (loop
->nb_iterations_upper_bound
, elt
->bound
))
566 basic_block bb
= gimple_bb (elt
->stmt
);
567 edge exit_edge
= EDGE_SUCC (bb
, 0);
568 class tree_niter_desc niter
;
570 if (!loop_exit_edge_p (loop
, exit_edge
))
571 exit_edge
= EDGE_SUCC (bb
, 1);
573 /* Only when we know the actual number of iterations, not
574 just a bound, we can remove the exit. */
575 if (!number_of_iterations_exit (loop
, exit_edge
,
576 &niter
, false, false)
577 || !integer_onep (niter
.assumptions
)
578 || !integer_zerop (niter
.may_be_zero
)
580 || TREE_CODE (niter
.niter
) != INTEGER_CST
581 || !wi::ltu_p (loop
->nb_iterations_upper_bound
,
582 wi::to_widest (niter
.niter
)))
585 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
587 fprintf (dump_file
, "Removed pointless exit: ");
588 print_gimple_stmt (dump_file
, elt
->stmt
, 0);
590 gcond
*cond_stmt
= as_a
<gcond
*> (elt
->stmt
);
591 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
592 gimple_cond_make_false (cond_stmt
);
594 gimple_cond_make_true (cond_stmt
);
595 update_stmt (cond_stmt
);
602 /* Stores loops that will be unlooped and edges that will be removed
603 after we process whole loop tree. */
604 static vec
<loop_p
> loops_to_unloop
;
605 static vec
<int> loops_to_unloop_nunroll
;
606 static vec
<edge
> edges_to_remove
;
607 /* Stores loops that has been peeled. */
608 static bitmap peeled_loops
;
610 /* Cancel all fully unrolled loops by putting __builtin_unreachable
612 We do it after all unrolling since unlooping moves basic blocks
613 across loop boundaries trashing loop closed SSA form as well
614 as SCEV info needed to be intact during unrolling.
616 IRRED_INVALIDATED is used to bookkeep if information about
617 irreducible regions may become invalid as a result
618 of the transformation.
619 LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case
620 when we need to go into loop closed SSA form. */
623 unloop_loops (bitmap loop_closed_ssa_invalidated
,
624 bool *irred_invalidated
)
626 while (loops_to_unloop
.length ())
628 class loop
*loop
= loops_to_unloop
.pop ();
629 int n_unroll
= loops_to_unloop_nunroll
.pop ();
630 basic_block latch
= loop
->latch
;
631 edge latch_edge
= loop_latch_edge (loop
);
632 int flags
= latch_edge
->flags
;
633 location_t locus
= latch_edge
->goto_locus
;
635 gimple_stmt_iterator gsi
;
637 remove_exits_and_undefined_stmts (loop
, n_unroll
);
639 /* Unloop destroys the latch edge. */
640 unloop (loop
, irred_invalidated
, loop_closed_ssa_invalidated
);
642 /* Create new basic block for the latch edge destination and wire
644 stmt
= gimple_build_call (builtin_decl_implicit (BUILT_IN_UNREACHABLE
), 0);
645 latch_edge
= make_edge (latch
, create_basic_block (NULL
, NULL
, latch
), flags
);
646 latch_edge
->probability
= profile_probability::never ();
647 latch_edge
->flags
|= flags
;
648 latch_edge
->goto_locus
= locus
;
650 add_bb_to_loop (latch_edge
->dest
, current_loops
->tree_root
);
651 latch_edge
->dest
->count
= profile_count::zero ();
652 set_immediate_dominator (CDI_DOMINATORS
, latch_edge
->dest
, latch_edge
->src
);
654 gsi
= gsi_start_bb (latch_edge
->dest
);
655 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
657 loops_to_unloop
.release ();
658 loops_to_unloop_nunroll
.release ();
660 /* Remove edges in peeled copies. Given remove_path removes dominated
661 regions we need to cope with removal of already removed paths. */
664 auto_vec
<int, 20> src_bbs
;
665 src_bbs
.reserve_exact (edges_to_remove
.length ());
666 FOR_EACH_VEC_ELT (edges_to_remove
, i
, e
)
667 src_bbs
.quick_push (e
->src
->index
);
668 FOR_EACH_VEC_ELT (edges_to_remove
, i
, e
)
669 if (BASIC_BLOCK_FOR_FN (cfun
, src_bbs
[i
]))
671 bool ok
= remove_path (e
, irred_invalidated
,
672 loop_closed_ssa_invalidated
);
675 edges_to_remove
.release ();
678 /* Tries to unroll LOOP completely, i.e. NITER times.
679 UL determines which loops we are allowed to unroll.
680 EXIT is the exit of the loop that should be eliminated.
681 MAXITER specfy bound on number of iterations, -1 if it is
682 not known or too large for HOST_WIDE_INT. The location
683 LOCUS corresponding to the loop is used when emitting
684 a summary of the unroll to the dump file. */
687 try_unroll_loop_completely (class loop
*loop
,
688 edge exit
, tree niter
, bool may_be_zero
,
689 enum unroll_level ul
,
690 HOST_WIDE_INT maxiter
,
691 dump_user_location_t locus
, bool allow_peel
)
693 unsigned HOST_WIDE_INT n_unroll
= 0;
694 bool n_unroll_found
= false;
695 edge edge_to_cancel
= NULL
;
697 /* See if we proved number of iterations to be low constant.
699 EXIT is an edge that will be removed in all but last iteration of
702 EDGE_TO_CACNEL is an edge that will be removed from the last iteration
703 of the unrolled sequence and is expected to make the final loop not
706 If the number of execution of loop is determined by standard induction
707 variable test, then EXIT and EDGE_TO_CANCEL are the two edges leaving
709 if (tree_fits_uhwi_p (niter
))
711 n_unroll
= tree_to_uhwi (niter
);
712 n_unroll_found
= true;
713 edge_to_cancel
= EDGE_SUCC (exit
->src
, 0);
714 if (edge_to_cancel
== exit
)
715 edge_to_cancel
= EDGE_SUCC (exit
->src
, 1);
717 /* We do not know the number of iterations and thus we cannot eliminate
722 /* See if we can improve our estimate by using recorded loop bounds. */
723 if ((allow_peel
|| maxiter
== 0 || ul
== UL_NO_GROWTH
)
725 && (!n_unroll_found
|| (unsigned HOST_WIDE_INT
)maxiter
< n_unroll
))
728 n_unroll_found
= true;
729 /* Loop terminates before the IV variable test, so we cannot
730 remove it in the last iteration. */
731 edge_to_cancel
= NULL
;
738 && n_unroll
> (unsigned) param_max_completely_peel_times
)
740 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
741 fprintf (dump_file
, "Not unrolling loop %d "
742 "(--param max-completely-peel-times limit reached).\n",
748 edge_to_cancel
= loop_edge_to_cancel (loop
);
752 if (ul
== UL_SINGLE_ITER
)
757 /* If the unrolling factor is too large, bail out. */
758 if (n_unroll
> (unsigned)loop
->unroll
)
760 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
762 "Not unrolling loop %d: "
763 "user didn't want it unrolled completely.\n",
770 struct loop_size size
;
771 /* EXIT can be removed only if we are sure it passes first N_UNROLL
773 bool remove_exit
= (exit
&& niter
774 && TREE_CODE (niter
) == INTEGER_CST
775 && wi::leu_p (n_unroll
, wi::to_widest (niter
)));
777 = tree_estimate_loop_size
778 (loop
, remove_exit
? exit
: NULL
, edge_to_cancel
, &size
,
779 param_max_completely_peeled_insns
);
782 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
783 fprintf (dump_file
, "Not unrolling loop %d: it is too large.\n",
788 unsigned HOST_WIDE_INT ninsns
= size
.overall
;
789 unsigned HOST_WIDE_INT unr_insns
790 = estimated_unrolled_size (&size
, n_unroll
);
791 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
793 fprintf (dump_file
, " Loop size: %d\n", (int) ninsns
);
794 fprintf (dump_file
, " Estimated size after unrolling: %d\n",
798 /* If the code is going to shrink, we don't need to be extra
799 cautious on guessing if the unrolling is going to be
802 /* If there is IV variable that will become constant, we
803 save one instruction in the loop prologue we do not
804 account otherwise. */
805 <= ninsns
+ (size
.constant_iv
!= false))
807 /* We unroll only inner loops, because we do not consider it
808 profitable otheriwse. We still can cancel loopback edge
809 of not rolling loop; this is always a good idea. */
810 else if (ul
== UL_NO_GROWTH
)
812 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
813 fprintf (dump_file
, "Not unrolling loop %d: size would grow.\n",
817 /* Outer loops tend to be less interesting candidates for
818 complete unrolling unless we can do a lot of propagation
819 into the inner loop body. For now we disable outer loop
820 unrolling when the code would grow. */
821 else if (loop
->inner
)
823 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
824 fprintf (dump_file
, "Not unrolling loop %d: "
825 "it is not innermost and code would grow.\n",
829 /* If there is call on a hot path through the loop, then
830 there is most probably not much to optimize. */
831 else if (size
.num_non_pure_calls_on_hot_path
)
833 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
834 fprintf (dump_file
, "Not unrolling loop %d: "
835 "contains call and code would grow.\n",
839 /* If there is pure/const call in the function, then we can
840 still optimize the unrolled loop body if it contains some
841 other interesting code than the calls and code storing or
842 cumulating the return value. */
843 else if (size
.num_pure_calls_on_hot_path
844 /* One IV increment, one test, one ivtmp store and
845 one useful stmt. That is about minimal loop
847 && (size
.non_call_stmts_on_hot_path
848 <= 3 + size
.num_pure_calls_on_hot_path
))
850 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
851 fprintf (dump_file
, "Not unrolling loop %d: "
852 "contains just pure calls and code would grow.\n",
856 /* Complete unrolling is major win when control flow is
857 removed and one big basic block is created. If the loop
858 contains control flow the optimization may still be a win
859 because of eliminating the loop overhead but it also may
860 blow the branch predictor tables. Limit number of
861 branches on the hot path through the peeled sequence. */
862 else if (size
.num_branches_on_hot_path
* (int)n_unroll
863 > param_max_peel_branches
)
865 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
866 fprintf (dump_file
, "Not unrolling loop %d: "
867 "number of branches on hot path in the unrolled "
868 "sequence reaches --param max-peel-branches limit.\n",
873 > (unsigned) param_max_completely_peeled_insns
)
875 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
876 fprintf (dump_file
, "Not unrolling loop %d: "
877 "number of insns in the unrolled sequence reaches "
878 "--param max-completely-peeled-insns limit.\n",
884 if (!dbg_cnt (gimple_unroll
))
887 initialize_original_copy_tables ();
888 auto_sbitmap
wont_exit (n_unroll
+ 1);
890 && TREE_CODE (niter
) == INTEGER_CST
891 && wi::leu_p (n_unroll
, wi::to_widest (niter
)))
893 bitmap_ones (wont_exit
);
894 if (wi::eq_p (wi::to_widest (niter
), n_unroll
)
896 bitmap_clear_bit (wont_exit
, 0);
901 bitmap_clear (wont_exit
);
904 bitmap_clear_bit (wont_exit
, 1);
906 if (!gimple_duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
908 exit
, &edges_to_remove
,
909 DLTHE_FLAG_UPDATE_FREQ
910 | DLTHE_FLAG_COMPLETTE_PEEL
))
912 free_original_copy_tables ();
913 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
914 fprintf (dump_file
, "Failed to duplicate the loop\n");
918 free_original_copy_tables ();
921 /* Remove the conditional from the last copy of the loop. */
924 gcond
*cond
= as_a
<gcond
*> (last_stmt (edge_to_cancel
->src
));
925 force_edge_cold (edge_to_cancel
, true);
926 if (edge_to_cancel
->flags
& EDGE_TRUE_VALUE
)
927 gimple_cond_make_false (cond
);
929 gimple_cond_make_true (cond
);
931 /* Do not remove the path, as doing so may remove outer loop and
932 confuse bookkeeping code in tree_unroll_loops_completely. */
935 /* Store the loop for later unlooping and exit removal. */
936 loops_to_unloop
.safe_push (loop
);
937 loops_to_unloop_nunroll
.safe_push (n_unroll
);
939 if (dump_enabled_p ())
942 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
943 "loop turned into non-loop; it never loops\n");
946 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
947 "loop with %d iterations completely unrolled",
949 if (loop
->header
->count
.initialized_p ())
950 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
,
951 " (header execution count %d)",
952 (int)loop
->header
->count
.to_gcov_type ());
953 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, "\n");
957 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
960 fprintf (dump_file
, "Exit condition of peeled iterations was "
963 fprintf (dump_file
, "Last iteration exit edge was proved true.\n");
965 fprintf (dump_file
, "Latch of last iteration was marked by "
966 "__builtin_unreachable ().\n");
972 /* Return number of instructions after peeling. */
973 static unsigned HOST_WIDE_INT
974 estimated_peeled_sequence_size (struct loop_size
*size
,
975 unsigned HOST_WIDE_INT npeel
)
977 return MAX (npeel
* (HOST_WIDE_INT
) (size
->overall
978 - size
->eliminated_by_peeling
), 1);
981 /* If the loop is expected to iterate N times and is
982 small enough, duplicate the loop body N+1 times before
983 the loop itself. This way the hot path will never
985 Parameters are the same as for try_unroll_loops_completely */
988 try_peel_loop (class loop
*loop
,
989 edge exit
, tree niter
, bool may_be_zero
,
990 HOST_WIDE_INT maxiter
)
993 struct loop_size size
;
997 || param_max_peel_times
<= 0
1001 if (bitmap_bit_p (peeled_loops
, loop
->num
))
1004 fprintf (dump_file
, "Not peeling: loop is already peeled\n");
1008 /* We don't peel loops that will be unrolled as this can duplicate a
1009 loop more times than the user requested. */
1013 fprintf (dump_file
, "Not peeling: user didn't want it peeled.\n");
1017 /* Peel only innermost loops.
1018 While the code is perfectly capable of peeling non-innermost loops,
1019 the heuristics would probably need some improvements. */
1023 fprintf (dump_file
, "Not peeling: outer loop\n");
1027 if (!optimize_loop_for_speed_p (loop
))
1030 fprintf (dump_file
, "Not peeling: cold loop\n");
1034 /* Check if there is an estimate on the number of iterations. */
1035 npeel
= estimated_loop_iterations_int (loop
);
1037 npeel
= likely_max_loop_iterations_int (loop
);
1041 fprintf (dump_file
, "Not peeling: number of iterations is not "
1045 if (maxiter
>= 0 && maxiter
<= npeel
)
1048 fprintf (dump_file
, "Not peeling: upper bound is known so can "
1049 "unroll completely\n");
1053 /* We want to peel estimated number of iterations + 1 (so we never
1054 enter the loop on quick path). Check against PARAM_MAX_PEEL_TIMES
1055 and be sure to avoid overflows. */
1056 if (npeel
> param_max_peel_times
- 1)
1059 fprintf (dump_file
, "Not peeling: rolls too much "
1060 "(%i + 1 > --param max-peel-times)\n", (int) npeel
);
1065 /* Check peeled loops size. */
1066 tree_estimate_loop_size (loop
, exit
, NULL
, &size
,
1067 param_max_peeled_insns
);
1068 if ((peeled_size
= estimated_peeled_sequence_size (&size
, (int) npeel
))
1069 > param_max_peeled_insns
)
1072 fprintf (dump_file
, "Not peeling: peeled sequence size is too large "
1073 "(%i insns > --param max-peel-insns)", peeled_size
);
1077 if (!dbg_cnt (gimple_unroll
))
1080 /* Duplicate possibly eliminating the exits. */
1081 initialize_original_copy_tables ();
1082 auto_sbitmap
wont_exit (npeel
+ 1);
1084 && TREE_CODE (niter
) == INTEGER_CST
1085 && wi::leu_p (npeel
, wi::to_widest (niter
)))
1087 bitmap_ones (wont_exit
);
1088 bitmap_clear_bit (wont_exit
, 0);
1093 bitmap_clear (wont_exit
);
1096 bitmap_clear_bit (wont_exit
, 1);
1097 if (!gimple_duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1099 exit
, &edges_to_remove
,
1100 DLTHE_FLAG_UPDATE_FREQ
))
1102 free_original_copy_tables ();
1105 free_original_copy_tables ();
1106 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1108 fprintf (dump_file
, "Peeled loop %d, %i times.\n",
1109 loop
->num
, (int) npeel
);
1111 if (loop
->any_estimate
)
1113 if (wi::ltu_p (npeel
, loop
->nb_iterations_estimate
))
1114 loop
->nb_iterations_estimate
-= npeel
;
1116 loop
->nb_iterations_estimate
= 0;
1118 if (loop
->any_upper_bound
)
1120 if (wi::ltu_p (npeel
, loop
->nb_iterations_upper_bound
))
1121 loop
->nb_iterations_upper_bound
-= npeel
;
1123 loop
->nb_iterations_upper_bound
= 0;
1125 if (loop
->any_likely_upper_bound
)
1127 if (wi::ltu_p (npeel
, loop
->nb_iterations_likely_upper_bound
))
1128 loop
->nb_iterations_likely_upper_bound
-= npeel
;
1131 loop
->any_estimate
= true;
1132 loop
->nb_iterations_estimate
= 0;
1133 loop
->nb_iterations_likely_upper_bound
= 0;
1136 profile_count entry_count
= profile_count::zero ();
1140 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1141 if (e
->src
!= loop
->latch
)
1143 if (e
->src
->count
.initialized_p ())
1144 entry_count
+= e
->src
->count
;
1145 gcc_assert (!flow_bb_inside_loop_p (loop
, e
->src
));
1147 profile_probability p
;
1148 p
= entry_count
.probability_in (loop
->header
->count
);
1149 scale_loop_profile (loop
, p
, 0);
1150 bitmap_set_bit (peeled_loops
, loop
->num
);
1153 /* Adds a canonical induction variable to LOOP if suitable.
1154 CREATE_IV is true if we may create a new iv. UL determines
1155 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
1156 to determine the number of iterations of a loop by direct evaluation.
1157 Returns true if cfg is changed. */
1160 canonicalize_loop_induction_variables (class loop
*loop
,
1161 bool create_iv
, enum unroll_level ul
,
1162 bool try_eval
, bool allow_peel
)
1166 HOST_WIDE_INT maxiter
;
1167 bool modified
= false;
1168 dump_user_location_t locus
;
1169 class tree_niter_desc niter_desc
;
1170 bool may_be_zero
= false;
1172 /* For unrolling allow conditional constant or zero iterations, thus
1173 perform loop-header copying on-the-fly. */
1174 exit
= single_exit (loop
);
1175 niter
= chrec_dont_know
;
1176 if (exit
&& number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
1178 niter
= niter_desc
.niter
;
1180 = niter_desc
.may_be_zero
&& !integer_zerop (niter_desc
.may_be_zero
);
1182 if (TREE_CODE (niter
) == INTEGER_CST
)
1183 locus
= last_stmt (exit
->src
);
1186 /* For non-constant niter fold may_be_zero into niter again. */
1189 if (COMPARISON_CLASS_P (niter_desc
.may_be_zero
))
1190 niter
= fold_build3 (COND_EXPR
, TREE_TYPE (niter
),
1191 niter_desc
.may_be_zero
,
1192 build_int_cst (TREE_TYPE (niter
), 0), niter
);
1194 niter
= chrec_dont_know
;
1195 may_be_zero
= false;
1198 /* If the loop has more than one exit, try checking all of them
1199 for # of iterations determinable through scev. */
1201 niter
= find_loop_niter (loop
, &exit
);
1203 /* Finally if everything else fails, try brute force evaluation. */
1205 && (chrec_contains_undetermined (niter
)
1206 || TREE_CODE (niter
) != INTEGER_CST
))
1207 niter
= find_loop_niter_by_eval (loop
, &exit
);
1210 locus
= last_stmt (exit
->src
);
1212 if (TREE_CODE (niter
) != INTEGER_CST
)
1216 /* We work exceptionally hard here to estimate the bound
1217 by find_loop_niter_by_eval. Be sure to keep it for future. */
1218 if (niter
&& TREE_CODE (niter
) == INTEGER_CST
)
1220 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
1221 record_niter_bound (loop
, wi::to_widest (niter
),
1222 exit
== single_likely_exit (loop
, exits
), true);
1225 /* Force re-computation of loop bounds so we can remove redundant exits. */
1226 maxiter
= max_loop_iterations_int (loop
);
1228 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1229 && TREE_CODE (niter
) == INTEGER_CST
)
1231 fprintf (dump_file
, "Loop %d iterates ", loop
->num
);
1232 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1233 fprintf (dump_file
, " times.\n");
1235 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1238 fprintf (dump_file
, "Loop %d iterates at most %i times.\n", loop
->num
,
1241 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1242 && likely_max_loop_iterations_int (loop
) >= 0)
1244 fprintf (dump_file
, "Loop %d likely iterates at most %i times.\n",
1245 loop
->num
, (int)likely_max_loop_iterations_int (loop
));
1248 /* Remove exits that are known to be never taken based on loop bound.
1249 Needs to be called after compilation of max_loop_iterations_int that
1250 populates the loop bounds. */
1251 modified
|= remove_redundant_iv_tests (loop
);
1253 if (try_unroll_loop_completely (loop
, exit
, niter
, may_be_zero
, ul
,
1254 maxiter
, locus
, allow_peel
))
1258 && niter
&& !chrec_contains_undetermined (niter
)
1259 && exit
&& just_once_each_iteration_p (loop
, exit
->src
))
1261 tree iv_niter
= niter
;
1264 if (COMPARISON_CLASS_P (niter_desc
.may_be_zero
))
1265 iv_niter
= fold_build3 (COND_EXPR
, TREE_TYPE (iv_niter
),
1266 niter_desc
.may_be_zero
,
1267 build_int_cst (TREE_TYPE (iv_niter
), 0),
1270 iv_niter
= NULL_TREE
;
1273 create_canonical_iv (loop
, exit
, iv_niter
);
1277 modified
|= try_peel_loop (loop
, exit
, niter
, may_be_zero
, maxiter
);
1282 /* The main entry point of the pass. Adds canonical induction variables
1283 to the suitable loops. */
1286 canonicalize_induction_variables (void)
1288 bool changed
= false;
1289 bool irred_invalidated
= false;
1290 bitmap loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
1292 estimate_numbers_of_iterations (cfun
);
1294 for (auto loop
: loops_list (cfun
, LI_FROM_INNERMOST
))
1296 changed
|= canonicalize_loop_induction_variables (loop
,
1297 true, UL_SINGLE_ITER
,
1300 gcc_assert (!need_ssa_update_p (cfun
));
1302 unloop_loops (loop_closed_ssa_invalidated
, &irred_invalidated
);
1303 if (irred_invalidated
1304 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1305 mark_irreducible_loops ();
1307 /* Clean up the information about numbers of iterations, since brute force
1308 evaluation could reveal new information. */
1309 free_numbers_of_iterations_estimates (cfun
);
1312 if (!bitmap_empty_p (loop_closed_ssa_invalidated
))
1314 gcc_checking_assert (loops_state_satisfies_p (LOOP_CLOSED_SSA
));
1315 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1317 BITMAP_FREE (loop_closed_ssa_invalidated
);
1320 return TODO_cleanup_cfg
;
1324 /* Process loops from innermost to outer, stopping at the innermost
1325 loop we unrolled. */
1328 tree_unroll_loops_completely_1 (bool may_increase_size
, bool unroll_outer
,
1329 bitmap father_bbs
, class loop
*loop
)
1331 class loop
*loop_father
;
1332 bool changed
= false;
1334 enum unroll_level ul
;
1335 unsigned num
= number_of_loops (cfun
);
1337 /* Process inner loops first. Don't walk loops added by the recursive
1338 calls because SSA form is not up-to-date. They can be handled in the
1340 bitmap child_father_bbs
= NULL
;
1341 for (inner
= loop
->inner
; inner
!= NULL
; inner
= inner
->next
)
1342 if ((unsigned) inner
->num
< num
)
1344 if (!child_father_bbs
)
1345 child_father_bbs
= BITMAP_ALLOC (NULL
);
1346 if (tree_unroll_loops_completely_1 (may_increase_size
, unroll_outer
,
1347 child_father_bbs
, inner
))
1349 bitmap_ior_into (father_bbs
, child_father_bbs
);
1350 bitmap_clear (child_father_bbs
);
1354 if (child_father_bbs
)
1355 BITMAP_FREE (child_father_bbs
);
1357 /* If we changed an inner loop we cannot process outer loops in this
1358 iteration because SSA form is not up-to-date. Continue with
1359 siblings of outer loops instead. */
1362 /* If we are recorded as father clear all other fathers that
1363 are necessarily covered already to avoid redundant work. */
1364 if (bitmap_bit_p (father_bbs
, loop
->header
->index
))
1366 bitmap_clear (father_bbs
);
1367 bitmap_set_bit (father_bbs
, loop
->header
->index
);
1372 /* Don't unroll #pragma omp simd loops until the vectorizer
1373 attempts to vectorize those. */
1374 if (loop
->force_vectorize
)
1377 /* Try to unroll this loop. */
1378 loop_father
= loop_outer (loop
);
1382 if (loop
->unroll
> 1)
1384 else if (may_increase_size
&& optimize_loop_nest_for_speed_p (loop
)
1385 /* Unroll outermost loops only if asked to do so or they do
1386 not cause code growth. */
1387 && (unroll_outer
|| loop_outer (loop_father
)))
1392 if (canonicalize_loop_induction_variables
1393 (loop
, false, ul
, !flag_tree_loop_ivcanon
, unroll_outer
))
1395 /* If we'll continue unrolling, we need to propagate constants
1396 within the new basic blocks to fold away induction variable
1397 computations; otherwise, the size might blow up before the
1398 iteration is complete and the IR eventually cleaned up. */
1399 if (loop_outer (loop_father
))
1401 /* Once we process our father we will have processed
1402 the fathers of our children as well, so avoid doing
1403 redundant work and clear fathers we've gathered sofar. */
1404 bitmap_clear (father_bbs
);
1405 bitmap_set_bit (father_bbs
, loop_father
->header
->index
);
1407 else if (unroll_outer
)
1408 /* Trigger scalar cleanup once any outermost loop gets unrolled. */
1409 cfun
->pending_TODOs
|= PENDING_TODO_force_next_scalar_cleanup
;
1417 /* Unroll LOOPS completely if they iterate just few times. Unless
1418 MAY_INCREASE_SIZE is true, perform the unrolling only if the
1419 size of the code does not increase. */
1422 tree_unroll_loops_completely (bool may_increase_size
, bool unroll_outer
)
1424 bitmap father_bbs
= BITMAP_ALLOC (NULL
);
1427 bool irred_invalidated
= false;
1429 estimate_numbers_of_iterations (cfun
);
1434 bitmap loop_closed_ssa_invalidated
= NULL
;
1436 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1437 loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
1439 free_numbers_of_iterations_estimates (cfun
);
1440 estimate_numbers_of_iterations (cfun
);
1442 changed
= tree_unroll_loops_completely_1 (may_increase_size
,
1443 unroll_outer
, father_bbs
,
1444 current_loops
->tree_root
);
1449 unloop_loops (loop_closed_ssa_invalidated
, &irred_invalidated
);
1451 /* We cannot use TODO_update_ssa_no_phi because VOPS gets confused. */
1452 if (loop_closed_ssa_invalidated
1453 && !bitmap_empty_p (loop_closed_ssa_invalidated
))
1454 rewrite_into_loop_closed_ssa (loop_closed_ssa_invalidated
,
1457 update_ssa (TODO_update_ssa
);
1459 /* father_bbs is a bitmap of loop father header BB indices.
1460 Translate that to what non-root loops these BBs belong to now. */
1462 bitmap fathers
= BITMAP_ALLOC (NULL
);
1463 EXECUTE_IF_SET_IN_BITMAP (father_bbs
, 0, i
, bi
)
1465 basic_block unrolled_loop_bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
1466 if (! unrolled_loop_bb
)
1468 if (loop_outer (unrolled_loop_bb
->loop_father
))
1469 bitmap_set_bit (fathers
,
1470 unrolled_loop_bb
->loop_father
->num
);
1472 bitmap_clear (father_bbs
);
1473 /* Propagate the constants within the new basic blocks. */
1474 EXECUTE_IF_SET_IN_BITMAP (fathers
, 0, i
, bi
)
1476 loop_p father
= get_loop (cfun
, i
);
1477 bitmap exit_bbs
= BITMAP_ALLOC (NULL
);
1478 loop_exit
*exit
= father
->exits
->next
;
1481 bitmap_set_bit (exit_bbs
, exit
->e
->dest
->index
);
1484 do_rpo_vn (cfun
, loop_preheader_edge (father
), exit_bbs
);
1486 BITMAP_FREE (fathers
);
1488 /* This will take care of removing completely unrolled loops
1489 from the loop structures so we can continue unrolling now
1491 if (cleanup_tree_cfg ())
1492 update_ssa (TODO_update_ssa_only_virtuals
);
1494 /* Clean up the information about numbers of iterations, since
1495 complete unrolling might have invalidated it. */
1497 if (flag_checking
&& loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1498 verify_loop_closed_ssa (true);
1500 if (loop_closed_ssa_invalidated
)
1501 BITMAP_FREE (loop_closed_ssa_invalidated
);
1504 && ++iteration
<= param_max_unroll_iterations
);
1506 BITMAP_FREE (father_bbs
);
1508 if (irred_invalidated
1509 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1510 mark_irreducible_loops ();
1515 /* Canonical induction variable creation pass. */
1519 const pass_data pass_data_iv_canon
=
1521 GIMPLE_PASS
, /* type */
1522 "ivcanon", /* name */
1523 OPTGROUP_LOOP
, /* optinfo_flags */
1524 TV_TREE_LOOP_IVCANON
, /* tv_id */
1525 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1526 0, /* properties_provided */
1527 0, /* properties_destroyed */
1528 0, /* todo_flags_start */
1529 0, /* todo_flags_finish */
1532 class pass_iv_canon
: public gimple_opt_pass
1535 pass_iv_canon (gcc::context
*ctxt
)
1536 : gimple_opt_pass (pass_data_iv_canon
, ctxt
)
1539 /* opt_pass methods: */
1540 virtual bool gate (function
*) { return flag_tree_loop_ivcanon
!= 0; }
1541 virtual unsigned int execute (function
*fun
);
1543 }; // class pass_iv_canon
1546 pass_iv_canon::execute (function
*fun
)
1548 if (number_of_loops (fun
) <= 1)
1551 return canonicalize_induction_variables ();
1557 make_pass_iv_canon (gcc::context
*ctxt
)
1559 return new pass_iv_canon (ctxt
);
1562 /* Complete unrolling of loops. */
1566 const pass_data pass_data_complete_unroll
=
1568 GIMPLE_PASS
, /* type */
1569 "cunroll", /* name */
1570 OPTGROUP_LOOP
, /* optinfo_flags */
1571 TV_COMPLETE_UNROLL
, /* tv_id */
1572 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1573 0, /* properties_provided */
1574 0, /* properties_destroyed */
1575 0, /* todo_flags_start */
1576 0, /* todo_flags_finish */
1579 class pass_complete_unroll
: public gimple_opt_pass
1582 pass_complete_unroll (gcc::context
*ctxt
)
1583 : gimple_opt_pass (pass_data_complete_unroll
, ctxt
)
1586 /* opt_pass methods: */
1587 virtual unsigned int execute (function
*);
1589 }; // class pass_complete_unroll
1592 pass_complete_unroll::execute (function
*fun
)
1594 if (number_of_loops (fun
) <= 1)
1597 /* If we ever decide to run loop peeling more than once, we will need to
1598 track loops already peeled in loop structures themselves to avoid
1599 re-peeling the same loop multiple times. */
1600 if (flag_peel_loops
)
1601 peeled_loops
= BITMAP_ALLOC (NULL
);
1602 unsigned int val
= tree_unroll_loops_completely (flag_cunroll_grow_size
,
1606 BITMAP_FREE (peeled_loops
);
1607 peeled_loops
= NULL
;
1615 make_pass_complete_unroll (gcc::context
*ctxt
)
1617 return new pass_complete_unroll (ctxt
);
1620 /* Complete unrolling of inner loops. */
1624 const pass_data pass_data_complete_unrolli
=
1626 GIMPLE_PASS
, /* type */
1627 "cunrolli", /* name */
1628 OPTGROUP_LOOP
, /* optinfo_flags */
1629 TV_COMPLETE_UNROLL
, /* tv_id */
1630 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1631 0, /* properties_provided */
1632 0, /* properties_destroyed */
1633 0, /* todo_flags_start */
1634 0, /* todo_flags_finish */
1637 class pass_complete_unrolli
: public gimple_opt_pass
1640 pass_complete_unrolli (gcc::context
*ctxt
)
1641 : gimple_opt_pass (pass_data_complete_unrolli
, ctxt
)
1644 /* opt_pass methods: */
1645 virtual bool gate (function
*) { return optimize
>= 2; }
1646 virtual unsigned int execute (function
*);
1648 }; // class pass_complete_unrolli
1651 pass_complete_unrolli::execute (function
*fun
)
1655 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
1656 if (number_of_loops (fun
) > 1)
1659 ret
= tree_unroll_loops_completely (optimize
>= 3, false);
1662 loop_optimizer_finalize ();
1670 make_pass_complete_unrolli (gcc::context
*ctxt
)
1672 return new pass_complete_unrolli (ctxt
);