1 /* Induction variable canonicalization and loop peeling.
2 Copyright (C) 2004-2023 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-iterator.h"
52 #include "gimple-fold.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
*> (*gsi_last_bb (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
);
116 create_iv (niter
, PLUS_EXPR
,
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
== *gsi_last_bb (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
== *gsi_last_bb (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 location_t loc
= gimple_location (elt
->stmt
);
509 gcall
*stmt
= gimple_build_builtin_unreachable (loc
);
510 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
511 split_block (gimple_bb (stmt
), stmt
);
513 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
515 fprintf (dump_file
, "Forced statement unreachable: ");
516 print_gimple_stmt (dump_file
, elt
->stmt
, 0);
519 /* If we know the exit will be taken after peeling, update. */
520 else if (elt
->is_exit
521 && wi::leu_p (elt
->bound
, npeeled
))
523 basic_block bb
= gimple_bb (elt
->stmt
);
524 edge exit_edge
= EDGE_SUCC (bb
, 0);
526 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
528 fprintf (dump_file
, "Forced exit to be taken: ");
529 print_gimple_stmt (dump_file
, elt
->stmt
, 0);
531 if (!loop_exit_edge_p (loop
, exit_edge
))
532 exit_edge
= EDGE_SUCC (bb
, 1);
533 exit_edge
->probability
= profile_probability::always ();
534 gcc_checking_assert (loop_exit_edge_p (loop
, exit_edge
));
535 gcond
*cond_stmt
= as_a
<gcond
*> (elt
->stmt
);
536 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
537 gimple_cond_make_true (cond_stmt
);
539 gimple_cond_make_false (cond_stmt
);
540 update_stmt (cond_stmt
);
547 /* Remove all exits that are known to be never taken because of the loop bound
551 remove_redundant_iv_tests (class loop
*loop
)
553 class nb_iter_bound
*elt
;
554 bool changed
= false;
556 if (!loop
->any_upper_bound
)
558 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
560 /* Exit is pointless if it won't be taken before loop reaches
562 if (elt
->is_exit
&& loop
->any_upper_bound
563 && wi::ltu_p (loop
->nb_iterations_upper_bound
, elt
->bound
))
565 basic_block bb
= gimple_bb (elt
->stmt
);
566 edge exit_edge
= EDGE_SUCC (bb
, 0);
567 class tree_niter_desc niter
;
569 if (!loop_exit_edge_p (loop
, exit_edge
))
570 exit_edge
= EDGE_SUCC (bb
, 1);
572 /* Only when we know the actual number of iterations, not
573 just a bound, we can remove the exit. */
574 if (!number_of_iterations_exit (loop
, exit_edge
,
575 &niter
, false, false)
576 || !integer_onep (niter
.assumptions
)
577 || !integer_zerop (niter
.may_be_zero
)
579 || TREE_CODE (niter
.niter
) != INTEGER_CST
580 || !wi::ltu_p (loop
->nb_iterations_upper_bound
,
581 wi::to_widest (niter
.niter
)))
584 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
586 fprintf (dump_file
, "Removed pointless exit: ");
587 print_gimple_stmt (dump_file
, elt
->stmt
, 0);
589 gcond
*cond_stmt
= as_a
<gcond
*> (elt
->stmt
);
590 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
591 gimple_cond_make_false (cond_stmt
);
593 gimple_cond_make_true (cond_stmt
);
594 update_stmt (cond_stmt
);
601 /* Stores loops that will be unlooped and edges that will be removed
602 after we process whole loop tree. */
603 static vec
<loop_p
> loops_to_unloop
;
604 static vec
<int> loops_to_unloop_nunroll
;
605 static vec
<edge
> edges_to_remove
;
606 /* Stores loops that has been peeled. */
607 static bitmap peeled_loops
;
609 /* Cancel all fully unrolled loops by putting __builtin_unreachable
611 We do it after all unrolling since unlooping moves basic blocks
612 across loop boundaries trashing loop closed SSA form as well
613 as SCEV info needed to be intact during unrolling.
615 IRRED_INVALIDATED is used to bookkeep if information about
616 irreducible regions may become invalid as a result
617 of the transformation.
618 LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case
619 when we need to go into loop closed SSA form. */
622 unloop_loops (vec
<class loop
*> &loops_to_unloop
,
623 vec
<int> &loops_to_unloop_nunroll
,
624 bitmap loop_closed_ssa_invalidated
,
625 bool *irred_invalidated
)
627 while (loops_to_unloop
.length ())
629 class loop
*loop
= loops_to_unloop
.pop ();
630 int n_unroll
= loops_to_unloop_nunroll
.pop ();
631 basic_block latch
= loop
->latch
;
632 edge latch_edge
= loop_latch_edge (loop
);
633 int flags
= latch_edge
->flags
;
634 location_t locus
= latch_edge
->goto_locus
;
636 gimple_stmt_iterator gsi
;
638 remove_exits_and_undefined_stmts (loop
, n_unroll
);
640 /* Unloop destroys the latch edge. */
641 unloop (loop
, irred_invalidated
, loop_closed_ssa_invalidated
);
643 /* Create new basic block for the latch edge destination and wire
645 stmt
= gimple_build_builtin_unreachable (locus
);
646 latch_edge
= make_edge (latch
, create_basic_block (NULL
, NULL
, latch
), flags
);
647 latch_edge
->probability
= profile_probability::never ();
648 latch_edge
->flags
|= flags
;
649 latch_edge
->goto_locus
= locus
;
651 add_bb_to_loop (latch_edge
->dest
, current_loops
->tree_root
);
652 latch_edge
->dest
->count
= profile_count::zero ();
653 set_immediate_dominator (CDI_DOMINATORS
, latch_edge
->dest
, latch_edge
->src
);
655 gsi
= gsi_start_bb (latch_edge
->dest
);
656 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
659 /* Remove edges in peeled copies. Given remove_path removes dominated
660 regions we need to cope with removal of already removed paths. */
663 auto_vec
<int, 20> src_bbs
;
664 src_bbs
.reserve_exact (edges_to_remove
.length ());
665 FOR_EACH_VEC_ELT (edges_to_remove
, i
, e
)
666 src_bbs
.quick_push (e
->src
->index
);
667 FOR_EACH_VEC_ELT (edges_to_remove
, i
, e
)
668 if (BASIC_BLOCK_FOR_FN (cfun
, src_bbs
[i
]))
670 bool ok
= remove_path (e
, irred_invalidated
,
671 loop_closed_ssa_invalidated
);
674 edges_to_remove
.release ();
677 /* Tries to unroll LOOP completely, i.e. NITER times.
678 UL determines which loops we are allowed to unroll.
679 EXIT is the exit of the loop that should be eliminated.
680 MAXITER specfy bound on number of iterations, -1 if it is
681 not known or too large for HOST_WIDE_INT. The location
682 LOCUS corresponding to the loop is used when emitting
683 a summary of the unroll to the dump file. */
686 try_unroll_loop_completely (class loop
*loop
,
687 edge exit
, tree niter
, bool may_be_zero
,
688 enum unroll_level ul
,
689 HOST_WIDE_INT maxiter
,
690 dump_user_location_t locus
, bool allow_peel
)
692 unsigned HOST_WIDE_INT n_unroll
= 0;
693 bool n_unroll_found
= false;
694 edge edge_to_cancel
= NULL
;
696 /* See if we proved number of iterations to be low constant.
698 EXIT is an edge that will be removed in all but last iteration of
701 EDGE_TO_CACNEL is an edge that will be removed from the last iteration
702 of the unrolled sequence and is expected to make the final loop not
705 If the number of execution of loop is determined by standard induction
706 variable test, then EXIT and EDGE_TO_CANCEL are the two edges leaving
708 if (tree_fits_uhwi_p (niter
))
710 n_unroll
= tree_to_uhwi (niter
);
711 n_unroll_found
= true;
712 edge_to_cancel
= EDGE_SUCC (exit
->src
, 0);
713 if (edge_to_cancel
== exit
)
714 edge_to_cancel
= EDGE_SUCC (exit
->src
, 1);
716 /* We do not know the number of iterations and thus we cannot eliminate
721 /* See if we can improve our estimate by using recorded loop bounds. */
722 if ((maxiter
== 0 || ul
!= UL_SINGLE_ITER
)
724 && (!n_unroll_found
|| (unsigned HOST_WIDE_INT
)maxiter
< n_unroll
))
727 n_unroll_found
= true;
728 /* Loop terminates before the IV variable test, so we cannot
729 remove it in the last iteration. */
730 edge_to_cancel
= NULL
;
731 /* If we do not allow peeling and we iterate just allow cases
732 that do not grow code. */
733 if (!allow_peel
&& maxiter
!= 0)
741 && n_unroll
> (unsigned) param_max_completely_peel_times
)
743 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
744 fprintf (dump_file
, "Not unrolling loop %d "
745 "(--param max-completely-peel-times limit reached).\n",
751 edge_to_cancel
= loop_edge_to_cancel (loop
);
755 if (ul
== UL_SINGLE_ITER
)
760 /* If the unrolling factor is too large, bail out. */
761 if (n_unroll
> (unsigned)loop
->unroll
)
763 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
765 "Not unrolling loop %d: "
766 "user didn't want it unrolled completely.\n",
773 struct loop_size size
;
774 /* EXIT can be removed only if we are sure it passes first N_UNROLL
776 bool remove_exit
= (exit
&& niter
777 && TREE_CODE (niter
) == INTEGER_CST
778 && wi::leu_p (n_unroll
, wi::to_widest (niter
)));
780 = tree_estimate_loop_size
781 (loop
, remove_exit
? exit
: NULL
, edge_to_cancel
, &size
,
782 param_max_completely_peeled_insns
);
785 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
786 fprintf (dump_file
, "Not unrolling loop %d: it is too large.\n",
791 unsigned HOST_WIDE_INT ninsns
= size
.overall
;
792 unsigned HOST_WIDE_INT unr_insns
793 = estimated_unrolled_size (&size
, n_unroll
);
794 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
796 fprintf (dump_file
, " Loop size: %d\n", (int) ninsns
);
797 fprintf (dump_file
, " Estimated size after unrolling: %d\n",
801 /* If the code is going to shrink, we don't need to be extra
802 cautious on guessing if the unrolling is going to be
805 /* If there is IV variable that will become constant, we
806 save one instruction in the loop prologue we do not
807 account otherwise. */
808 <= ninsns
+ (size
.constant_iv
!= false))
810 /* We unroll only inner loops, because we do not consider it
811 profitable otheriwse. We still can cancel loopback edge
812 of not rolling loop; this is always a good idea. */
813 else if (ul
== UL_NO_GROWTH
)
815 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
816 fprintf (dump_file
, "Not unrolling loop %d: size would grow.\n",
820 /* Outer loops tend to be less interesting candidates for
821 complete unrolling unless we can do a lot of propagation
822 into the inner loop body. For now we disable outer loop
823 unrolling when the code would grow. */
824 else if (loop
->inner
)
826 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
827 fprintf (dump_file
, "Not unrolling loop %d: "
828 "it is not innermost and code would grow.\n",
832 /* If there is call on a hot path through the loop, then
833 there is most probably not much to optimize. */
834 else if (size
.num_non_pure_calls_on_hot_path
)
836 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
837 fprintf (dump_file
, "Not unrolling loop %d: "
838 "contains call and code would grow.\n",
842 /* If there is pure/const call in the function, then we can
843 still optimize the unrolled loop body if it contains some
844 other interesting code than the calls and code storing or
845 cumulating the return value. */
846 else if (size
.num_pure_calls_on_hot_path
847 /* One IV increment, one test, one ivtmp store and
848 one useful stmt. That is about minimal loop
850 && (size
.non_call_stmts_on_hot_path
851 <= 3 + size
.num_pure_calls_on_hot_path
))
853 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
854 fprintf (dump_file
, "Not unrolling loop %d: "
855 "contains just pure calls and code would grow.\n",
859 /* Complete unrolling is major win when control flow is
860 removed and one big basic block is created. If the loop
861 contains control flow the optimization may still be a win
862 because of eliminating the loop overhead but it also may
863 blow the branch predictor tables. Limit number of
864 branches on the hot path through the peeled sequence. */
865 else if (size
.num_branches_on_hot_path
* (int)n_unroll
866 > param_max_peel_branches
)
868 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
869 fprintf (dump_file
, "Not unrolling loop %d: "
870 "number of branches on hot path in the unrolled "
871 "sequence reaches --param max-peel-branches limit.\n",
876 > (unsigned) param_max_completely_peeled_insns
)
878 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
879 fprintf (dump_file
, "Not unrolling loop %d: "
880 "number of insns in the unrolled sequence reaches "
881 "--param max-completely-peeled-insns limit.\n",
887 if (!dbg_cnt (gimple_unroll
))
890 initialize_original_copy_tables ();
891 auto_sbitmap
wont_exit (n_unroll
+ 1);
893 && TREE_CODE (niter
) == INTEGER_CST
894 && wi::leu_p (n_unroll
, wi::to_widest (niter
)))
896 bitmap_ones (wont_exit
);
897 if (wi::eq_p (wi::to_widest (niter
), n_unroll
)
899 bitmap_clear_bit (wont_exit
, 0);
904 bitmap_clear (wont_exit
);
907 bitmap_clear_bit (wont_exit
, 1);
909 if (!gimple_duplicate_loop_body_to_header_edge (
910 loop
, loop_preheader_edge (loop
), n_unroll
, wont_exit
, exit
,
912 DLTHE_FLAG_UPDATE_FREQ
| DLTHE_FLAG_COMPLETTE_PEEL
))
914 free_original_copy_tables ();
915 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
916 fprintf (dump_file
, "Failed to duplicate the loop\n");
920 free_original_copy_tables ();
923 /* Remove the conditional from the last copy of the loop. */
926 gcond
*cond
= as_a
<gcond
*> (*gsi_last_bb (edge_to_cancel
->src
));
927 force_edge_cold (edge_to_cancel
, true);
928 if (edge_to_cancel
->flags
& EDGE_TRUE_VALUE
)
929 gimple_cond_make_false (cond
);
931 gimple_cond_make_true (cond
);
933 /* Do not remove the path, as doing so may remove outer loop and
934 confuse bookkeeping code in tree_unroll_loops_completely. */
937 /* Store the loop for later unlooping and exit removal. */
938 loops_to_unloop
.safe_push (loop
);
939 loops_to_unloop_nunroll
.safe_push (n_unroll
);
941 if (dump_enabled_p ())
944 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
945 "loop turned into non-loop; it never loops\n");
948 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
949 "loop with %d iterations completely unrolled",
951 if (loop
->header
->count
.initialized_p ())
952 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
,
953 " (header execution count %d)",
954 (int)loop
->header
->count
.to_gcov_type ());
955 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, "\n");
959 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
962 fprintf (dump_file
, "Exit condition of peeled iterations was "
965 fprintf (dump_file
, "Last iteration exit edge was proved true.\n");
967 fprintf (dump_file
, "Latch of last iteration was marked by "
968 "__builtin_unreachable ().\n");
974 /* Return number of instructions after peeling. */
975 static unsigned HOST_WIDE_INT
976 estimated_peeled_sequence_size (struct loop_size
*size
,
977 unsigned HOST_WIDE_INT npeel
)
979 return MAX (npeel
* (HOST_WIDE_INT
) (size
->overall
980 - size
->eliminated_by_peeling
), 1);
983 /* Update loop estimates after peeling LOOP by NPEEL.
984 If PRECISE is false only likely exists were duplicated and thus
985 do not update any estimates that are supposed to be always reliable. */
987 adjust_loop_info_after_peeling (class loop
*loop
, int npeel
, bool precise
)
989 if (loop
->any_estimate
)
991 /* Since peeling is mostly about loops where first few
992 iterations are special, it is not quite correct to
993 assume that the remaining iterations will behave
994 the same way. However we do not have better info
995 so update the esitmate, since it is likely better
996 than keeping it as it is.
998 Remove it if it looks wrong.
1000 TODO: We likely want to special case the situation where
1001 peeling is optimizing out exit edges and only update
1003 if (wi::leu_p (npeel
, loop
->nb_iterations_estimate
))
1004 loop
->nb_iterations_estimate
-= npeel
;
1006 loop
->any_estimate
= false;
1008 if (loop
->any_upper_bound
&& precise
)
1010 if (wi::leu_p (npeel
, loop
->nb_iterations_upper_bound
))
1011 loop
->nb_iterations_upper_bound
-= npeel
;
1014 /* Peeling maximal number of iterations or more
1015 makes no sense and is a bug.
1016 We should peel completely. */
1020 if (loop
->any_likely_upper_bound
)
1022 if (wi::leu_p (npeel
, loop
->nb_iterations_likely_upper_bound
))
1023 loop
->nb_iterations_likely_upper_bound
-= npeel
;
1026 loop
->any_estimate
= true;
1027 loop
->nb_iterations_estimate
= 0;
1028 loop
->nb_iterations_likely_upper_bound
= 0;
1033 /* If the loop is expected to iterate N times and is
1034 small enough, duplicate the loop body N+1 times before
1035 the loop itself. This way the hot path will never
1037 Parameters are the same as for try_unroll_loops_completely */
1040 try_peel_loop (class loop
*loop
,
1041 edge exit
, tree niter
, bool may_be_zero
,
1042 HOST_WIDE_INT maxiter
)
1044 HOST_WIDE_INT npeel
;
1045 struct loop_size size
;
1048 if (!flag_peel_loops
1049 || param_max_peel_times
<= 0
1053 if (bitmap_bit_p (peeled_loops
, loop
->num
))
1056 fprintf (dump_file
, "Not peeling: loop is already peeled\n");
1060 /* We don't peel loops that will be unrolled as this can duplicate a
1061 loop more times than the user requested. */
1065 fprintf (dump_file
, "Not peeling: user didn't want it peeled.\n");
1069 /* Peel only innermost loops.
1070 While the code is perfectly capable of peeling non-innermost loops,
1071 the heuristics would probably need some improvements. */
1075 fprintf (dump_file
, "Not peeling: outer loop\n");
1079 if (!optimize_loop_for_speed_p (loop
))
1082 fprintf (dump_file
, "Not peeling: cold loop\n");
1086 /* Check if there is an estimate on the number of iterations. */
1087 npeel
= estimated_loop_iterations_int (loop
);
1089 npeel
= likely_max_loop_iterations_int (loop
);
1093 fprintf (dump_file
, "Not peeling: number of iterations is not "
1097 if (maxiter
>= 0 && maxiter
<= npeel
)
1100 fprintf (dump_file
, "Not peeling: upper bound is known so can "
1101 "unroll completely\n");
1105 /* We want to peel estimated number of iterations + 1 (so we never
1106 enter the loop on quick path). Check against PARAM_MAX_PEEL_TIMES
1107 and be sure to avoid overflows. */
1108 if (npeel
> param_max_peel_times
- 1)
1111 fprintf (dump_file
, "Not peeling: rolls too much "
1112 "(%i + 1 > --param max-peel-times)\n", (int) npeel
);
1117 /* Check peeled loops size. */
1118 tree_estimate_loop_size (loop
, exit
, NULL
, &size
,
1119 param_max_peeled_insns
);
1120 if ((peeled_size
= estimated_peeled_sequence_size (&size
, (int) npeel
))
1121 > param_max_peeled_insns
)
1124 fprintf (dump_file
, "Not peeling: peeled sequence size is too large "
1125 "(%i insns > --param max-peel-insns)", peeled_size
);
1129 if (!dbg_cnt (gimple_unroll
))
1132 /* Duplicate possibly eliminating the exits. */
1133 initialize_original_copy_tables ();
1134 auto_sbitmap
wont_exit (npeel
+ 1);
1136 && TREE_CODE (niter
) == INTEGER_CST
1137 && wi::leu_p (npeel
, wi::to_widest (niter
)))
1139 bitmap_ones (wont_exit
);
1140 bitmap_clear_bit (wont_exit
, 0);
1145 bitmap_clear (wont_exit
);
1148 bitmap_clear_bit (wont_exit
, 1);
1149 if (!gimple_duplicate_loop_body_to_header_edge (
1150 loop
, loop_preheader_edge (loop
), npeel
, wont_exit
, exit
,
1151 &edges_to_remove
, DLTHE_FLAG_UPDATE_FREQ
))
1153 free_original_copy_tables ();
1156 free_original_copy_tables ();
1157 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1159 fprintf (dump_file
, "Peeled loop %d, %i times.\n",
1160 loop
->num
, (int) npeel
);
1162 adjust_loop_info_after_peeling (loop
, npeel
, true);
1163 profile_count entry_count
= profile_count::zero ();
1167 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1168 if (e
->src
!= loop
->latch
)
1170 if (e
->src
->count
.initialized_p ())
1171 entry_count
+= e
->src
->count
;
1172 gcc_assert (!flow_bb_inside_loop_p (loop
, e
->src
));
1174 profile_probability p
;
1175 p
= entry_count
.probability_in (loop
->header
->count
);
1176 scale_loop_profile (loop
, p
, 0);
1177 bitmap_set_bit (peeled_loops
, loop
->num
);
1180 /* Adds a canonical induction variable to LOOP if suitable.
1181 CREATE_IV is true if we may create a new iv. UL determines
1182 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
1183 to determine the number of iterations of a loop by direct evaluation.
1184 Returns true if cfg is changed. */
1187 canonicalize_loop_induction_variables (class loop
*loop
,
1188 bool create_iv
, enum unroll_level ul
,
1189 bool try_eval
, bool allow_peel
)
1193 HOST_WIDE_INT maxiter
;
1194 bool modified
= false;
1195 dump_user_location_t locus
;
1196 class tree_niter_desc niter_desc
;
1197 bool may_be_zero
= false;
1199 /* For unrolling allow conditional constant or zero iterations, thus
1200 perform loop-header copying on-the-fly. */
1201 exit
= single_exit (loop
);
1202 niter
= chrec_dont_know
;
1203 if (exit
&& number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
1205 niter
= niter_desc
.niter
;
1207 = niter_desc
.may_be_zero
&& !integer_zerop (niter_desc
.may_be_zero
);
1209 if (TREE_CODE (niter
) == INTEGER_CST
)
1210 locus
= last_nondebug_stmt (exit
->src
);
1213 /* For non-constant niter fold may_be_zero into niter again. */
1216 if (COMPARISON_CLASS_P (niter_desc
.may_be_zero
))
1217 niter
= fold_build3 (COND_EXPR
, TREE_TYPE (niter
),
1218 niter_desc
.may_be_zero
,
1219 build_int_cst (TREE_TYPE (niter
), 0), niter
);
1221 niter
= chrec_dont_know
;
1222 may_be_zero
= false;
1225 /* If the loop has more than one exit, try checking all of them
1226 for # of iterations determinable through scev. */
1228 niter
= find_loop_niter (loop
, &exit
);
1230 /* Finally if everything else fails, try brute force evaluation. */
1232 && (chrec_contains_undetermined (niter
)
1233 || TREE_CODE (niter
) != INTEGER_CST
))
1234 niter
= find_loop_niter_by_eval (loop
, &exit
);
1237 locus
= last_nondebug_stmt (exit
->src
);
1239 if (TREE_CODE (niter
) != INTEGER_CST
)
1243 /* We work exceptionally hard here to estimate the bound
1244 by find_loop_niter_by_eval. Be sure to keep it for future. */
1245 if (niter
&& TREE_CODE (niter
) == INTEGER_CST
)
1247 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
1248 record_niter_bound (loop
, wi::to_widest (niter
),
1249 exit
== single_likely_exit (loop
, exits
), true);
1252 /* Force re-computation of loop bounds so we can remove redundant exits. */
1253 maxiter
= max_loop_iterations_int (loop
);
1255 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1256 && TREE_CODE (niter
) == INTEGER_CST
)
1258 fprintf (dump_file
, "Loop %d iterates ", loop
->num
);
1259 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1260 fprintf (dump_file
, " times.\n");
1262 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1265 fprintf (dump_file
, "Loop %d iterates at most %i times.\n", loop
->num
,
1268 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1269 && likely_max_loop_iterations_int (loop
) >= 0)
1271 fprintf (dump_file
, "Loop %d likely iterates at most %i times.\n",
1272 loop
->num
, (int)likely_max_loop_iterations_int (loop
));
1275 /* Remove exits that are known to be never taken based on loop bound.
1276 Needs to be called after compilation of max_loop_iterations_int that
1277 populates the loop bounds. */
1278 modified
|= remove_redundant_iv_tests (loop
);
1280 if (try_unroll_loop_completely (loop
, exit
, niter
, may_be_zero
, ul
,
1281 maxiter
, locus
, allow_peel
))
1285 && niter
&& !chrec_contains_undetermined (niter
)
1286 && exit
&& just_once_each_iteration_p (loop
, exit
->src
))
1288 tree iv_niter
= niter
;
1291 if (COMPARISON_CLASS_P (niter_desc
.may_be_zero
))
1292 iv_niter
= fold_build3 (COND_EXPR
, TREE_TYPE (iv_niter
),
1293 niter_desc
.may_be_zero
,
1294 build_int_cst (TREE_TYPE (iv_niter
), 0),
1297 iv_niter
= NULL_TREE
;
1300 create_canonical_iv (loop
, exit
, iv_niter
);
1304 modified
|= try_peel_loop (loop
, exit
, niter
, may_be_zero
, maxiter
);
1309 /* The main entry point of the pass. Adds canonical induction variables
1310 to the suitable loops. */
1313 canonicalize_induction_variables (void)
1315 bool changed
= false;
1316 bool irred_invalidated
= false;
1317 bitmap loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
1319 estimate_numbers_of_iterations (cfun
);
1321 for (auto loop
: loops_list (cfun
, LI_FROM_INNERMOST
))
1323 changed
|= canonicalize_loop_induction_variables (loop
,
1324 true, UL_SINGLE_ITER
,
1327 gcc_assert (!need_ssa_update_p (cfun
));
1329 unloop_loops (loops_to_unloop
, loops_to_unloop_nunroll
,
1330 loop_closed_ssa_invalidated
, &irred_invalidated
);
1331 loops_to_unloop
.release ();
1332 loops_to_unloop_nunroll
.release ();
1333 if (irred_invalidated
1334 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1335 mark_irreducible_loops ();
1337 /* Clean up the information about numbers of iterations, since brute force
1338 evaluation could reveal new information. */
1339 free_numbers_of_iterations_estimates (cfun
);
1342 if (!bitmap_empty_p (loop_closed_ssa_invalidated
))
1344 gcc_checking_assert (loops_state_satisfies_p (LOOP_CLOSED_SSA
));
1345 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1347 BITMAP_FREE (loop_closed_ssa_invalidated
);
1350 return TODO_cleanup_cfg
;
1354 /* Process loops from innermost to outer, stopping at the innermost
1355 loop we unrolled. */
1358 tree_unroll_loops_completely_1 (bool may_increase_size
, bool unroll_outer
,
1359 bitmap father_bbs
, class loop
*loop
)
1361 class loop
*loop_father
;
1362 bool changed
= false;
1364 enum unroll_level ul
;
1365 unsigned num
= number_of_loops (cfun
);
1367 /* Process inner loops first. Don't walk loops added by the recursive
1368 calls because SSA form is not up-to-date. They can be handled in the
1370 bitmap child_father_bbs
= NULL
;
1371 for (inner
= loop
->inner
; inner
!= NULL
; inner
= inner
->next
)
1372 if ((unsigned) inner
->num
< num
)
1374 if (!child_father_bbs
)
1375 child_father_bbs
= BITMAP_ALLOC (NULL
);
1376 if (tree_unroll_loops_completely_1 (may_increase_size
, unroll_outer
,
1377 child_father_bbs
, inner
))
1379 bitmap_ior_into (father_bbs
, child_father_bbs
);
1380 bitmap_clear (child_father_bbs
);
1384 if (child_father_bbs
)
1385 BITMAP_FREE (child_father_bbs
);
1387 /* If we changed an inner loop we cannot process outer loops in this
1388 iteration because SSA form is not up-to-date. Continue with
1389 siblings of outer loops instead. */
1392 /* If we are recorded as father clear all other fathers that
1393 are necessarily covered already to avoid redundant work. */
1394 if (bitmap_bit_p (father_bbs
, loop
->header
->index
))
1396 bitmap_clear (father_bbs
);
1397 bitmap_set_bit (father_bbs
, loop
->header
->index
);
1402 /* Don't unroll #pragma omp simd loops until the vectorizer
1403 attempts to vectorize those. */
1404 if (loop
->force_vectorize
)
1407 /* Try to unroll this loop. */
1408 loop_father
= loop_outer (loop
);
1412 if (loop
->unroll
> 1)
1414 else if (may_increase_size
&& optimize_loop_nest_for_speed_p (loop
)
1415 /* Unroll outermost loops only if asked to do so or they do
1416 not cause code growth. */
1417 && (unroll_outer
|| loop_outer (loop_father
)))
1422 if (canonicalize_loop_induction_variables
1423 (loop
, false, ul
, !flag_tree_loop_ivcanon
, unroll_outer
))
1425 /* If we'll continue unrolling, we need to propagate constants
1426 within the new basic blocks to fold away induction variable
1427 computations; otherwise, the size might blow up before the
1428 iteration is complete and the IR eventually cleaned up. */
1429 if (loop_outer (loop_father
))
1431 /* Once we process our father we will have processed
1432 the fathers of our children as well, so avoid doing
1433 redundant work and clear fathers we've gathered sofar. */
1434 bitmap_clear (father_bbs
);
1435 bitmap_set_bit (father_bbs
, loop_father
->header
->index
);
1437 else if (unroll_outer
)
1438 /* Trigger scalar cleanup once any outermost loop gets unrolled. */
1439 cfun
->pending_TODOs
|= PENDING_TODO_force_next_scalar_cleanup
;
1447 /* Unroll LOOPS completely if they iterate just few times. Unless
1448 MAY_INCREASE_SIZE is true, perform the unrolling only if the
1449 size of the code does not increase. */
1452 tree_unroll_loops_completely (bool may_increase_size
, bool unroll_outer
)
1454 bitmap father_bbs
= BITMAP_ALLOC (NULL
);
1457 bool irred_invalidated
= false;
1459 estimate_numbers_of_iterations (cfun
);
1464 bitmap loop_closed_ssa_invalidated
= NULL
;
1466 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1467 loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
1469 free_numbers_of_iterations_estimates (cfun
);
1470 estimate_numbers_of_iterations (cfun
);
1472 changed
= tree_unroll_loops_completely_1 (may_increase_size
,
1473 unroll_outer
, father_bbs
,
1474 current_loops
->tree_root
);
1479 unloop_loops (loops_to_unloop
,
1480 loops_to_unloop_nunroll
,
1481 loop_closed_ssa_invalidated
,
1482 &irred_invalidated
);
1483 loops_to_unloop
.release ();
1484 loops_to_unloop_nunroll
.release ();
1486 /* We cannot use TODO_update_ssa_no_phi because VOPS gets confused. */
1487 if (loop_closed_ssa_invalidated
1488 && !bitmap_empty_p (loop_closed_ssa_invalidated
))
1489 rewrite_into_loop_closed_ssa (loop_closed_ssa_invalidated
,
1492 update_ssa (TODO_update_ssa
);
1494 /* father_bbs is a bitmap of loop father header BB indices.
1495 Translate that to what non-root loops these BBs belong to now. */
1497 bitmap fathers
= BITMAP_ALLOC (NULL
);
1498 EXECUTE_IF_SET_IN_BITMAP (father_bbs
, 0, i
, bi
)
1500 basic_block unrolled_loop_bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
1501 if (! unrolled_loop_bb
)
1503 if (loop_outer (unrolled_loop_bb
->loop_father
))
1504 bitmap_set_bit (fathers
,
1505 unrolled_loop_bb
->loop_father
->num
);
1507 bitmap_clear (father_bbs
);
1508 /* Propagate the constants within the new basic blocks. */
1509 EXECUTE_IF_SET_IN_BITMAP (fathers
, 0, i
, bi
)
1511 loop_p father
= get_loop (cfun
, i
);
1512 bitmap exit_bbs
= BITMAP_ALLOC (NULL
);
1513 loop_exit
*exit
= father
->exits
->next
;
1516 bitmap_set_bit (exit_bbs
, exit
->e
->dest
->index
);
1519 do_rpo_vn (cfun
, loop_preheader_edge (father
), exit_bbs
);
1521 BITMAP_FREE (fathers
);
1523 /* This will take care of removing completely unrolled loops
1524 from the loop structures so we can continue unrolling now
1526 if (cleanup_tree_cfg ())
1527 update_ssa (TODO_update_ssa_only_virtuals
);
1529 /* Clean up the information about numbers of iterations, since
1530 complete unrolling might have invalidated it. */
1532 if (flag_checking
&& loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1533 verify_loop_closed_ssa (true);
1535 if (loop_closed_ssa_invalidated
)
1536 BITMAP_FREE (loop_closed_ssa_invalidated
);
1539 && ++iteration
<= param_max_unroll_iterations
);
1541 BITMAP_FREE (father_bbs
);
1543 if (irred_invalidated
1544 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1545 mark_irreducible_loops ();
1550 /* Canonical induction variable creation pass. */
1554 const pass_data pass_data_iv_canon
=
1556 GIMPLE_PASS
, /* type */
1557 "ivcanon", /* name */
1558 OPTGROUP_LOOP
, /* optinfo_flags */
1559 TV_TREE_LOOP_IVCANON
, /* tv_id */
1560 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1561 0, /* properties_provided */
1562 0, /* properties_destroyed */
1563 0, /* todo_flags_start */
1564 0, /* todo_flags_finish */
1567 class pass_iv_canon
: public gimple_opt_pass
1570 pass_iv_canon (gcc::context
*ctxt
)
1571 : gimple_opt_pass (pass_data_iv_canon
, ctxt
)
1574 /* opt_pass methods: */
1575 bool gate (function
*) final override
{ return flag_tree_loop_ivcanon
!= 0; }
1576 unsigned int execute (function
*fun
) final override
;
1578 }; // class pass_iv_canon
1581 pass_iv_canon::execute (function
*fun
)
1583 if (number_of_loops (fun
) <= 1)
1586 return canonicalize_induction_variables ();
1592 make_pass_iv_canon (gcc::context
*ctxt
)
1594 return new pass_iv_canon (ctxt
);
1597 /* Complete unrolling of loops. */
1601 const pass_data pass_data_complete_unroll
=
1603 GIMPLE_PASS
, /* type */
1604 "cunroll", /* name */
1605 OPTGROUP_LOOP
, /* optinfo_flags */
1606 TV_COMPLETE_UNROLL
, /* tv_id */
1607 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1608 0, /* properties_provided */
1609 0, /* properties_destroyed */
1610 0, /* todo_flags_start */
1611 0, /* todo_flags_finish */
1614 class pass_complete_unroll
: public gimple_opt_pass
1617 pass_complete_unroll (gcc::context
*ctxt
)
1618 : gimple_opt_pass (pass_data_complete_unroll
, ctxt
)
1621 /* opt_pass methods: */
1622 unsigned int execute (function
*) final override
;
1624 }; // class pass_complete_unroll
1627 pass_complete_unroll::execute (function
*fun
)
1629 if (number_of_loops (fun
) <= 1)
1632 /* If we ever decide to run loop peeling more than once, we will need to
1633 track loops already peeled in loop structures themselves to avoid
1634 re-peeling the same loop multiple times. */
1635 if (flag_peel_loops
)
1636 peeled_loops
= BITMAP_ALLOC (NULL
);
1637 unsigned int val
= tree_unroll_loops_completely (flag_cunroll_grow_size
,
1641 BITMAP_FREE (peeled_loops
);
1642 peeled_loops
= NULL
;
1650 make_pass_complete_unroll (gcc::context
*ctxt
)
1652 return new pass_complete_unroll (ctxt
);
1655 /* Complete unrolling of inner loops. */
1659 const pass_data pass_data_complete_unrolli
=
1661 GIMPLE_PASS
, /* type */
1662 "cunrolli", /* name */
1663 OPTGROUP_LOOP
, /* optinfo_flags */
1664 TV_COMPLETE_UNROLL
, /* tv_id */
1665 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1666 0, /* properties_provided */
1667 0, /* properties_destroyed */
1668 0, /* todo_flags_start */
1669 0, /* todo_flags_finish */
1672 class pass_complete_unrolli
: public gimple_opt_pass
1675 pass_complete_unrolli (gcc::context
*ctxt
)
1676 : gimple_opt_pass (pass_data_complete_unrolli
, ctxt
)
1679 /* opt_pass methods: */
1680 bool gate (function
*) final override
{ return optimize
>= 2; }
1681 unsigned int execute (function
*) final override
;
1683 }; // class pass_complete_unrolli
1686 pass_complete_unrolli::execute (function
*fun
)
1690 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
1691 if (number_of_loops (fun
) > 1)
1694 ret
= tree_unroll_loops_completely (optimize
>= 3, false);
1697 loop_optimizer_finalize ();
1705 make_pass_complete_unrolli (gcc::context
*ctxt
)
1707 return new pass_complete_unrolli (ctxt
);