1 /* Induction variable canonicalization and loop peeling.
2 Copyright (C) 2004-2019 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This pass detects the loops that iterate a constant number of times,
21 adds a canonical induction variable (step -1, tested against 0)
22 and replaces the exit test. This enables the less powerful rtl
23 level analysis to use this information.
25 This might spoil the code in some cases (by increasing register pressure).
26 Note that in the case the new variable is not needed, ivopts will get rid
27 of it, so it might only be a problem when there are no other linear induction
28 variables. In that case the created optimization possibilities are likely
32 - complete unrolling (or peeling) when the loops is rolling few enough
34 - simple peeling (i.e. copying few initial iterations prior the loop)
35 when number of iteration estimate is known (typically by the profile
40 #include "coretypes.h"
45 #include "tree-pass.h"
48 #include "gimple-pretty-print.h"
49 #include "fold-const.h"
51 #include "gimple-fold.h"
53 #include "gimple-iterator.h"
55 #include "tree-ssa-loop-manip.h"
56 #include "tree-ssa-loop-niter.h"
57 #include "tree-ssa-loop.h"
58 #include "tree-into-ssa.h"
60 #include "tree-chrec.h"
61 #include "tree-scalar-evolution.h"
63 #include "tree-inline.h"
64 #include "tree-cfgcleanup.h"
66 #include "tree-ssa-sccvn.h"
69 /* Specifies types of loops that may be unrolled. */
73 UL_SINGLE_ITER
, /* Only loops that exit immediately in the first
75 UL_NO_GROWTH
, /* Only loops whose unrolling will not cause increase
77 UL_ALL
/* All suitable loops. */
80 /* Adds a canonical induction variable to LOOP iterating NITER times. EXIT
81 is the exit edge whose condition is replaced. The ssa versions of the new
82 IV before and after increment will be stored in VAR_BEFORE and VAR_AFTER
83 if they are not NULL. */
86 create_canonical_iv (class loop
*loop
, edge exit
, tree niter
,
87 tree
*var_before
= NULL
, tree
*var_after
= NULL
)
92 gimple_stmt_iterator incr_at
;
95 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
97 fprintf (dump_file
, "Added canonical iv to loop %d, ", loop
->num
);
98 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
99 fprintf (dump_file
, " iterations.\n");
102 cond
= as_a
<gcond
*> (last_stmt (exit
->src
));
103 in
= EDGE_SUCC (exit
->src
, 0);
105 in
= EDGE_SUCC (exit
->src
, 1);
107 /* Note that we do not need to worry about overflows, since
108 type of niter is always unsigned and all comparisons are
109 just for equality/nonequality -- i.e. everything works
110 with a modulo arithmetics. */
112 type
= TREE_TYPE (niter
);
113 niter
= fold_build2 (PLUS_EXPR
, type
,
115 build_int_cst (type
, 1));
116 incr_at
= gsi_last_bb (in
->src
);
118 build_int_cst (type
, -1),
120 &incr_at
, false, var_before
, &var
);
124 cmp
= (exit
->flags
& EDGE_TRUE_VALUE
) ? EQ_EXPR
: NE_EXPR
;
125 gimple_cond_set_code (cond
, cmp
);
126 gimple_cond_set_lhs (cond
, var
);
127 gimple_cond_set_rhs (cond
, build_int_cst (type
, 0));
131 /* Describe size of loop as detected by tree_estimate_loop_size. */
134 /* Number of instructions in the loop. */
137 /* Number of instructions that will be likely optimized out in
138 peeled iterations of loop (i.e. computation based on induction
139 variable where induction variable starts at known constant.) */
140 int eliminated_by_peeling
;
142 /* Same statistics for last iteration of loop: it is smaller because
143 instructions after exit are not executed. */
145 int last_iteration_eliminated_by_peeling
;
147 /* If some IV computation will become constant. */
150 /* Number of call stmts that are not a builtin and are pure or const
151 present on the hot path. */
152 int num_pure_calls_on_hot_path
;
153 /* Number of call stmts that are not a builtin and are not pure nor const
154 present on the hot path. */
155 int num_non_pure_calls_on_hot_path
;
156 /* Number of statements other than calls in the loop. */
157 int non_call_stmts_on_hot_path
;
158 /* Number of branches seen on the hot path. */
159 int num_branches_on_hot_path
;
162 /* Return true if OP in STMT will be constant after peeling LOOP. */
165 constant_after_peeling (tree op
, gimple
*stmt
, class loop
*loop
)
167 if (is_gimple_min_invariant (op
))
170 /* We can still fold accesses to constant arrays when index is known. */
171 if (TREE_CODE (op
) != SSA_NAME
)
175 /* First make fast look if we see constant array inside. */
176 while (handled_component_p (base
))
177 base
= TREE_OPERAND (base
, 0);
179 && ctor_for_folding (base
) != error_mark_node
)
180 || CONSTANT_CLASS_P (base
))
182 /* If so, see if we understand all the indices. */
184 while (handled_component_p (base
))
186 if (TREE_CODE (base
) == ARRAY_REF
187 && !constant_after_peeling (TREE_OPERAND (base
, 1), stmt
, loop
))
189 base
= TREE_OPERAND (base
, 0);
196 /* Induction variables are constants when defined in loop. */
197 if (loop_containing_stmt (stmt
) != loop
)
199 tree ev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, op
));
200 if (chrec_contains_undetermined (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 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
),
299 size
->constant_iv
= true;
300 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
302 " Constant expression will be folded away.\n");
303 likely_eliminated
= true;
306 else if ((gimple_code (stmt
) == GIMPLE_COND
307 && constant_after_peeling (gimple_cond_lhs (stmt
), stmt
,
309 && constant_after_peeling (gimple_cond_rhs (stmt
), stmt
,
311 /* We don't simplify all constant compares so make sure
312 they are not both constant already. See PR70288. */
313 && (! is_gimple_min_invariant (gimple_cond_lhs (stmt
))
314 || ! is_gimple_min_invariant
315 (gimple_cond_rhs (stmt
))))
316 || (gimple_code (stmt
) == GIMPLE_SWITCH
317 && constant_after_peeling (gimple_switch_index (
321 && ! is_gimple_min_invariant
323 (as_a
<gswitch
*> (stmt
)))))
325 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
326 fprintf (dump_file
, " Constant conditional.\n");
327 likely_eliminated
= true;
331 size
->overall
+= num
;
332 if (likely_eliminated
|| likely_eliminated_peeled
)
333 size
->eliminated_by_peeling
+= num
;
336 size
->last_iteration
+= num
;
337 if (likely_eliminated
|| likely_eliminated_last
)
338 size
->last_iteration_eliminated_by_peeling
+= num
;
340 if ((size
->overall
* 3 / 2 - size
->eliminated_by_peeling
341 - 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
)
449 gimple_stmt_iterator gsi
;
451 /* We want only one predecestor of the loop. */
452 if (EDGE_COUNT (loop
->latch
->preds
) > 1)
455 exits
= get_loop_exit_edges (loop
);
457 FOR_EACH_VEC_ELT (exits
, i
, edge_to_cancel
)
459 /* Find the other edge than the loop exit
460 leaving the conditoinal. */
461 if (EDGE_COUNT (edge_to_cancel
->src
->succs
) != 2)
463 if (EDGE_SUCC (edge_to_cancel
->src
, 0) == edge_to_cancel
)
464 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 1);
466 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 0);
468 /* We only can handle conditionals. */
469 if (!(edge_to_cancel
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
472 /* We should never have conditionals in the loop latch. */
473 gcc_assert (edge_to_cancel
->dest
!= loop
->header
);
475 /* Check that it leads to loop latch. */
476 if (edge_to_cancel
->dest
!= loop
->latch
)
481 /* Verify that the code in loop latch does nothing that may end program
482 execution without really reaching the exit. This may include
483 non-pure/const function calls, EH statements, volatile ASMs etc. */
484 for (gsi
= gsi_start_bb (loop
->latch
); !gsi_end_p (gsi
); gsi_next (&gsi
))
485 if (gimple_has_side_effects (gsi_stmt (gsi
)))
487 return edge_to_cancel
;
493 /* Remove all tests for exits that are known to be taken after LOOP was
494 peeled NPEELED times. Put gcc_unreachable before every statement
495 known to not be executed. */
498 remove_exits_and_undefined_stmts (class loop
*loop
, unsigned int npeeled
)
500 class nb_iter_bound
*elt
;
501 bool changed
= false;
503 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
505 /* If statement is known to be undefined after peeling, turn it
506 into unreachable (or trap when debugging experience is supposed
509 && wi::ltu_p (elt
->bound
, npeeled
))
511 gimple_stmt_iterator gsi
= gsi_for_stmt (elt
->stmt
);
512 gcall
*stmt
= gimple_build_call
513 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
), 0);
514 gimple_set_location (stmt
, gimple_location (elt
->stmt
));
515 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
516 split_block (gimple_bb (stmt
), stmt
);
518 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
520 fprintf (dump_file
, "Forced statement unreachable: ");
521 print_gimple_stmt (dump_file
, elt
->stmt
, 0);
524 /* If we know the exit will be taken after peeling, update. */
525 else if (elt
->is_exit
526 && wi::leu_p (elt
->bound
, npeeled
))
528 basic_block bb
= gimple_bb (elt
->stmt
);
529 edge exit_edge
= EDGE_SUCC (bb
, 0);
531 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
533 fprintf (dump_file
, "Forced exit to be taken: ");
534 print_gimple_stmt (dump_file
, elt
->stmt
, 0);
536 if (!loop_exit_edge_p (loop
, exit_edge
))
537 exit_edge
= EDGE_SUCC (bb
, 1);
538 exit_edge
->probability
= profile_probability::always ();
539 gcc_checking_assert (loop_exit_edge_p (loop
, exit_edge
));
540 gcond
*cond_stmt
= as_a
<gcond
*> (elt
->stmt
);
541 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
542 gimple_cond_make_true (cond_stmt
);
544 gimple_cond_make_false (cond_stmt
);
545 update_stmt (cond_stmt
);
552 /* Remove all exits that are known to be never taken because of the loop bound
556 remove_redundant_iv_tests (class loop
*loop
)
558 class nb_iter_bound
*elt
;
559 bool changed
= false;
561 if (!loop
->any_upper_bound
)
563 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
565 /* Exit is pointless if it won't be taken before loop reaches
567 if (elt
->is_exit
&& loop
->any_upper_bound
568 && wi::ltu_p (loop
->nb_iterations_upper_bound
, elt
->bound
))
570 basic_block bb
= gimple_bb (elt
->stmt
);
571 edge exit_edge
= EDGE_SUCC (bb
, 0);
572 class tree_niter_desc niter
;
574 if (!loop_exit_edge_p (loop
, exit_edge
))
575 exit_edge
= EDGE_SUCC (bb
, 1);
577 /* Only when we know the actual number of iterations, not
578 just a bound, we can remove the exit. */
579 if (!number_of_iterations_exit (loop
, exit_edge
,
580 &niter
, false, false)
581 || !integer_onep (niter
.assumptions
)
582 || !integer_zerop (niter
.may_be_zero
)
584 || TREE_CODE (niter
.niter
) != INTEGER_CST
585 || !wi::ltu_p (loop
->nb_iterations_upper_bound
,
586 wi::to_widest (niter
.niter
)))
589 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
591 fprintf (dump_file
, "Removed pointless exit: ");
592 print_gimple_stmt (dump_file
, elt
->stmt
, 0);
594 gcond
*cond_stmt
= as_a
<gcond
*> (elt
->stmt
);
595 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
596 gimple_cond_make_false (cond_stmt
);
598 gimple_cond_make_true (cond_stmt
);
599 update_stmt (cond_stmt
);
606 /* Stores loops that will be unlooped and edges that will be removed
607 after we process whole loop tree. */
608 static vec
<loop_p
> loops_to_unloop
;
609 static vec
<int> loops_to_unloop_nunroll
;
610 static vec
<edge
> edges_to_remove
;
611 /* Stores loops that has been peeled. */
612 static bitmap peeled_loops
;
614 /* Cancel all fully unrolled loops by putting __builtin_unreachable
616 We do it after all unrolling since unlooping moves basic blocks
617 across loop boundaries trashing loop closed SSA form as well
618 as SCEV info needed to be intact during unrolling.
620 IRRED_INVALIDATED is used to bookkeep if information about
621 irreducible regions may become invalid as a result
622 of the transformation.
623 LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case
624 when we need to go into loop closed SSA form. */
627 unloop_loops (bitmap loop_closed_ssa_invalidated
,
628 bool *irred_invalidated
)
630 while (loops_to_unloop
.length ())
632 class loop
*loop
= loops_to_unloop
.pop ();
633 int n_unroll
= loops_to_unloop_nunroll
.pop ();
634 basic_block latch
= loop
->latch
;
635 edge latch_edge
= loop_latch_edge (loop
);
636 int flags
= latch_edge
->flags
;
637 location_t locus
= latch_edge
->goto_locus
;
639 gimple_stmt_iterator gsi
;
641 remove_exits_and_undefined_stmts (loop
, n_unroll
);
643 /* Unloop destroys the latch edge. */
644 unloop (loop
, irred_invalidated
, loop_closed_ssa_invalidated
);
646 /* Create new basic block for the latch edge destination and wire
648 stmt
= gimple_build_call (builtin_decl_implicit (BUILT_IN_UNREACHABLE
), 0);
649 latch_edge
= make_edge (latch
, create_basic_block (NULL
, NULL
, latch
), flags
);
650 latch_edge
->probability
= profile_probability::never ();
651 latch_edge
->flags
|= flags
;
652 latch_edge
->goto_locus
= locus
;
654 add_bb_to_loop (latch_edge
->dest
, current_loops
->tree_root
);
655 latch_edge
->dest
->count
= profile_count::zero ();
656 set_immediate_dominator (CDI_DOMINATORS
, latch_edge
->dest
, latch_edge
->src
);
658 gsi
= gsi_start_bb (latch_edge
->dest
);
659 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
661 loops_to_unloop
.release ();
662 loops_to_unloop_nunroll
.release ();
664 /* Remove edges in peeled copies. Given remove_path removes dominated
665 regions we need to cope with removal of already removed paths. */
668 auto_vec
<int, 20> src_bbs
;
669 src_bbs
.reserve_exact (edges_to_remove
.length ());
670 FOR_EACH_VEC_ELT (edges_to_remove
, i
, e
)
671 src_bbs
.quick_push (e
->src
->index
);
672 FOR_EACH_VEC_ELT (edges_to_remove
, i
, e
)
673 if (BASIC_BLOCK_FOR_FN (cfun
, src_bbs
[i
]))
675 bool ok
= remove_path (e
, irred_invalidated
,
676 loop_closed_ssa_invalidated
);
679 edges_to_remove
.release ();
682 /* Tries to unroll LOOP completely, i.e. NITER times.
683 UL determines which loops we are allowed to unroll.
684 EXIT is the exit of the loop that should be eliminated.
685 MAXITER specfy bound on number of iterations, -1 if it is
686 not known or too large for HOST_WIDE_INT. The location
687 LOCUS corresponding to the loop is used when emitting
688 a summary of the unroll to the dump file. */
691 try_unroll_loop_completely (class loop
*loop
,
692 edge exit
, tree niter
, bool may_be_zero
,
693 enum unroll_level ul
,
694 HOST_WIDE_INT maxiter
,
695 dump_user_location_t locus
, bool allow_peel
)
697 unsigned HOST_WIDE_INT n_unroll
= 0;
698 bool n_unroll_found
= false;
699 edge edge_to_cancel
= NULL
;
701 /* See if we proved number of iterations to be low constant.
703 EXIT is an edge that will be removed in all but last iteration of
706 EDGE_TO_CACNEL is an edge that will be removed from the last iteration
707 of the unrolled sequence and is expected to make the final loop not
710 If the number of execution of loop is determined by standard induction
711 variable test, then EXIT and EDGE_TO_CANCEL are the two edges leaving
713 if (tree_fits_uhwi_p (niter
))
715 n_unroll
= tree_to_uhwi (niter
);
716 n_unroll_found
= true;
717 edge_to_cancel
= EDGE_SUCC (exit
->src
, 0);
718 if (edge_to_cancel
== exit
)
719 edge_to_cancel
= EDGE_SUCC (exit
->src
, 1);
721 /* We do not know the number of iterations and thus we cannot eliminate
726 /* See if we can improve our estimate by using recorded loop bounds. */
727 if ((allow_peel
|| maxiter
== 0 || ul
== UL_NO_GROWTH
)
729 && (!n_unroll_found
|| (unsigned HOST_WIDE_INT
)maxiter
< n_unroll
))
732 n_unroll_found
= true;
733 /* Loop terminates before the IV variable test, so we cannot
734 remove it in the last iteration. */
735 edge_to_cancel
= NULL
;
742 && n_unroll
> (unsigned) param_max_completely_peel_times
)
744 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
745 fprintf (dump_file
, "Not unrolling loop %d "
746 "(--param max-completely-peel-times limit reached).\n",
752 edge_to_cancel
= loop_edge_to_cancel (loop
);
756 if (ul
== UL_SINGLE_ITER
)
761 /* If the unrolling factor is too large, bail out. */
762 if (n_unroll
> (unsigned)loop
->unroll
)
764 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
766 "Not unrolling loop %d: "
767 "user didn't want it unrolled completely.\n",
774 struct loop_size size
;
775 /* EXIT can be removed only if we are sure it passes first N_UNROLL
777 bool remove_exit
= (exit
&& niter
778 && TREE_CODE (niter
) == INTEGER_CST
779 && wi::leu_p (n_unroll
, wi::to_widest (niter
)));
781 = tree_estimate_loop_size
782 (loop
, remove_exit
? exit
: NULL
, edge_to_cancel
, &size
,
783 param_max_completely_peeled_insns
);
786 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
787 fprintf (dump_file
, "Not unrolling loop %d: it is too large.\n",
792 unsigned HOST_WIDE_INT ninsns
= size
.overall
;
793 unsigned HOST_WIDE_INT unr_insns
794 = estimated_unrolled_size (&size
, n_unroll
);
795 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
797 fprintf (dump_file
, " Loop size: %d\n", (int) ninsns
);
798 fprintf (dump_file
, " Estimated size after unrolling: %d\n",
802 /* If the code is going to shrink, we don't need to be extra
803 cautious on guessing if the unrolling is going to be
806 /* If there is IV variable that will become constant, we
807 save one instruction in the loop prologue we do not
808 account otherwise. */
809 <= ninsns
+ (size
.constant_iv
!= false))
811 /* We unroll only inner loops, because we do not consider it
812 profitable otheriwse. We still can cancel loopback edge
813 of not rolling loop; this is always a good idea. */
814 else if (ul
== UL_NO_GROWTH
)
816 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
817 fprintf (dump_file
, "Not unrolling loop %d: size would grow.\n",
821 /* Outer loops tend to be less interesting candidates for
822 complete unrolling unless we can do a lot of propagation
823 into the inner loop body. For now we disable outer loop
824 unrolling when the code would grow. */
825 else if (loop
->inner
)
827 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
828 fprintf (dump_file
, "Not unrolling loop %d: "
829 "it is not innermost and code would grow.\n",
833 /* If there is call on a hot path through the loop, then
834 there is most probably not much to optimize. */
835 else if (size
.num_non_pure_calls_on_hot_path
)
837 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
838 fprintf (dump_file
, "Not unrolling loop %d: "
839 "contains call and code would grow.\n",
843 /* If there is pure/const call in the function, then we can
844 still optimize the unrolled loop body if it contains some
845 other interesting code than the calls and code storing or
846 cumulating the return value. */
847 else if (size
.num_pure_calls_on_hot_path
848 /* One IV increment, one test, one ivtmp store and
849 one useful stmt. That is about minimal loop
851 && (size
.non_call_stmts_on_hot_path
852 <= 3 + size
.num_pure_calls_on_hot_path
))
854 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
855 fprintf (dump_file
, "Not unrolling loop %d: "
856 "contains just pure calls and code would grow.\n",
860 /* Complete unrolling is major win when control flow is
861 removed and one big basic block is created. If the loop
862 contains control flow the optimization may still be a win
863 because of eliminating the loop overhead but it also may
864 blow the branch predictor tables. Limit number of
865 branches on the hot path through the peeled sequence. */
866 else if (size
.num_branches_on_hot_path
* (int)n_unroll
867 > param_max_peel_branches
)
869 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
870 fprintf (dump_file
, "Not unrolling loop %d: "
871 "number of branches on hot path in the unrolled "
872 "sequence reaches --param max-peel-branches limit.\n",
877 > (unsigned) param_max_completely_peeled_insns
)
879 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
880 fprintf (dump_file
, "Not unrolling loop %d: "
881 "number of insns in the unrolled sequence reaches "
882 "--param max-completely-peeled-insns limit.\n",
888 if (!dbg_cnt (gimple_unroll
))
891 initialize_original_copy_tables ();
892 auto_sbitmap
wont_exit (n_unroll
+ 1);
894 && TREE_CODE (niter
) == INTEGER_CST
895 && wi::leu_p (n_unroll
, wi::to_widest (niter
)))
897 bitmap_ones (wont_exit
);
898 if (wi::eq_p (wi::to_widest (niter
), n_unroll
)
900 bitmap_clear_bit (wont_exit
, 0);
905 bitmap_clear (wont_exit
);
908 bitmap_clear_bit (wont_exit
, 1);
910 if (!gimple_duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
912 exit
, &edges_to_remove
,
913 DLTHE_FLAG_UPDATE_FREQ
914 | DLTHE_FLAG_COMPLETTE_PEEL
))
916 free_original_copy_tables ();
917 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
918 fprintf (dump_file
, "Failed to duplicate the loop\n");
922 free_original_copy_tables ();
925 /* Remove the conditional from the last copy of the loop. */
928 gcond
*cond
= as_a
<gcond
*> (last_stmt (edge_to_cancel
->src
));
929 force_edge_cold (edge_to_cancel
, true);
930 if (edge_to_cancel
->flags
& EDGE_TRUE_VALUE
)
931 gimple_cond_make_false (cond
);
933 gimple_cond_make_true (cond
);
935 /* Do not remove the path, as doing so may remove outer loop and
936 confuse bookkeeping code in tree_unroll_loops_completely. */
939 /* Store the loop for later unlooping and exit removal. */
940 loops_to_unloop
.safe_push (loop
);
941 loops_to_unloop_nunroll
.safe_push (n_unroll
);
943 if (dump_enabled_p ())
946 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
947 "loop turned into non-loop; it never loops\n");
950 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
951 "loop with %d iterations completely unrolled",
953 if (loop
->header
->count
.initialized_p ())
954 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
,
955 " (header execution count %d)",
956 (int)loop
->header
->count
.to_gcov_type ());
957 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, "\n");
961 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
964 fprintf (dump_file
, "Exit condition of peeled iterations was "
967 fprintf (dump_file
, "Last iteration exit edge was proved true.\n");
969 fprintf (dump_file
, "Latch of last iteration was marked by "
970 "__builtin_unreachable ().\n");
976 /* Return number of instructions after peeling. */
977 static unsigned HOST_WIDE_INT
978 estimated_peeled_sequence_size (struct loop_size
*size
,
979 unsigned HOST_WIDE_INT npeel
)
981 return MAX (npeel
* (HOST_WIDE_INT
) (size
->overall
982 - size
->eliminated_by_peeling
), 1);
985 /* If the loop is expected to iterate N times and is
986 small enough, duplicate the loop body N+1 times before
987 the loop itself. This way the hot path will never
989 Parameters are the same as for try_unroll_loops_completely */
992 try_peel_loop (class loop
*loop
,
993 edge exit
, tree niter
, bool may_be_zero
,
994 HOST_WIDE_INT maxiter
)
997 struct loop_size size
;
1000 if (!flag_peel_loops
1001 || param_max_peel_times
<= 0
1005 if (bitmap_bit_p (peeled_loops
, loop
->num
))
1008 fprintf (dump_file
, "Not peeling: loop is already peeled\n");
1012 /* We don't peel loops that will be unrolled as this can duplicate a
1013 loop more times than the user requested. */
1017 fprintf (dump_file
, "Not peeling: user didn't want it peeled.\n");
1021 /* Peel only innermost loops.
1022 While the code is perfectly capable of peeling non-innermost loops,
1023 the heuristics would probably need some improvements. */
1027 fprintf (dump_file
, "Not peeling: outer loop\n");
1031 if (!optimize_loop_for_speed_p (loop
))
1034 fprintf (dump_file
, "Not peeling: cold loop\n");
1038 /* Check if there is an estimate on the number of iterations. */
1039 npeel
= estimated_loop_iterations_int (loop
);
1041 npeel
= likely_max_loop_iterations_int (loop
);
1045 fprintf (dump_file
, "Not peeling: number of iterations is not "
1049 if (maxiter
>= 0 && maxiter
<= npeel
)
1052 fprintf (dump_file
, "Not peeling: upper bound is known so can "
1053 "unroll completely\n");
1057 /* We want to peel estimated number of iterations + 1 (so we never
1058 enter the loop on quick path). Check against PARAM_MAX_PEEL_TIMES
1059 and be sure to avoid overflows. */
1060 if (npeel
> param_max_peel_times
- 1)
1063 fprintf (dump_file
, "Not peeling: rolls too much "
1064 "(%i + 1 > --param max-peel-times)\n", (int) npeel
);
1069 /* Check peeled loops size. */
1070 tree_estimate_loop_size (loop
, exit
, NULL
, &size
,
1071 param_max_peeled_insns
);
1072 if ((peeled_size
= estimated_peeled_sequence_size (&size
, (int) npeel
))
1073 > param_max_peeled_insns
)
1076 fprintf (dump_file
, "Not peeling: peeled sequence size is too large "
1077 "(%i insns > --param max-peel-insns)", peeled_size
);
1081 if (!dbg_cnt (gimple_unroll
))
1084 /* Duplicate possibly eliminating the exits. */
1085 initialize_original_copy_tables ();
1086 auto_sbitmap
wont_exit (npeel
+ 1);
1088 && TREE_CODE (niter
) == INTEGER_CST
1089 && wi::leu_p (npeel
, wi::to_widest (niter
)))
1091 bitmap_ones (wont_exit
);
1092 bitmap_clear_bit (wont_exit
, 0);
1097 bitmap_clear (wont_exit
);
1100 bitmap_clear_bit (wont_exit
, 1);
1101 if (!gimple_duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1103 exit
, &edges_to_remove
,
1104 DLTHE_FLAG_UPDATE_FREQ
))
1106 free_original_copy_tables ();
1109 free_original_copy_tables ();
1110 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1112 fprintf (dump_file
, "Peeled loop %d, %i times.\n",
1113 loop
->num
, (int) npeel
);
1115 if (loop
->any_estimate
)
1117 if (wi::ltu_p (npeel
, loop
->nb_iterations_estimate
))
1118 loop
->nb_iterations_estimate
-= npeel
;
1120 loop
->nb_iterations_estimate
= 0;
1122 if (loop
->any_upper_bound
)
1124 if (wi::ltu_p (npeel
, loop
->nb_iterations_upper_bound
))
1125 loop
->nb_iterations_upper_bound
-= npeel
;
1127 loop
->nb_iterations_upper_bound
= 0;
1129 if (loop
->any_likely_upper_bound
)
1131 if (wi::ltu_p (npeel
, loop
->nb_iterations_likely_upper_bound
))
1132 loop
->nb_iterations_likely_upper_bound
-= npeel
;
1135 loop
->any_estimate
= true;
1136 loop
->nb_iterations_estimate
= 0;
1137 loop
->nb_iterations_likely_upper_bound
= 0;
1140 profile_count entry_count
= profile_count::zero ();
1144 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1145 if (e
->src
!= loop
->latch
)
1147 if (e
->src
->count
.initialized_p ())
1148 entry_count
+= e
->src
->count
;
1149 gcc_assert (!flow_bb_inside_loop_p (loop
, e
->src
));
1151 profile_probability p
;
1152 p
= entry_count
.probability_in (loop
->header
->count
);
1153 scale_loop_profile (loop
, p
, 0);
1154 bitmap_set_bit (peeled_loops
, loop
->num
);
1157 /* Adds a canonical induction variable to LOOP if suitable.
1158 CREATE_IV is true if we may create a new iv. UL determines
1159 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
1160 to determine the number of iterations of a loop by direct evaluation.
1161 Returns true if cfg is changed. */
1164 canonicalize_loop_induction_variables (class loop
*loop
,
1165 bool create_iv
, enum unroll_level ul
,
1166 bool try_eval
, bool allow_peel
)
1170 HOST_WIDE_INT maxiter
;
1171 bool modified
= false;
1172 dump_user_location_t locus
;
1173 class tree_niter_desc niter_desc
;
1174 bool may_be_zero
= false;
1176 /* For unrolling allow conditional constant or zero iterations, thus
1177 perform loop-header copying on-the-fly. */
1178 exit
= single_exit (loop
);
1179 niter
= chrec_dont_know
;
1180 if (exit
&& number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
1182 niter
= niter_desc
.niter
;
1184 = niter_desc
.may_be_zero
&& !integer_zerop (niter_desc
.may_be_zero
);
1186 if (TREE_CODE (niter
) == INTEGER_CST
)
1187 locus
= last_stmt (exit
->src
);
1190 /* For non-constant niter fold may_be_zero into niter again. */
1193 if (COMPARISON_CLASS_P (niter_desc
.may_be_zero
))
1194 niter
= fold_build3 (COND_EXPR
, TREE_TYPE (niter
),
1195 niter_desc
.may_be_zero
,
1196 build_int_cst (TREE_TYPE (niter
), 0), niter
);
1198 niter
= chrec_dont_know
;
1199 may_be_zero
= false;
1202 /* If the loop has more than one exit, try checking all of them
1203 for # of iterations determinable through scev. */
1205 niter
= find_loop_niter (loop
, &exit
);
1207 /* Finally if everything else fails, try brute force evaluation. */
1209 && (chrec_contains_undetermined (niter
)
1210 || TREE_CODE (niter
) != INTEGER_CST
))
1211 niter
= find_loop_niter_by_eval (loop
, &exit
);
1214 locus
= last_stmt (exit
->src
);
1216 if (TREE_CODE (niter
) != INTEGER_CST
)
1220 /* We work exceptionally hard here to estimate the bound
1221 by find_loop_niter_by_eval. Be sure to keep it for future. */
1222 if (niter
&& TREE_CODE (niter
) == INTEGER_CST
)
1224 record_niter_bound (loop
, wi::to_widest (niter
),
1225 exit
== single_likely_exit (loop
), true);
1228 /* Force re-computation of loop bounds so we can remove redundant exits. */
1229 maxiter
= max_loop_iterations_int (loop
);
1231 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1232 && TREE_CODE (niter
) == INTEGER_CST
)
1234 fprintf (dump_file
, "Loop %d iterates ", loop
->num
);
1235 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1236 fprintf (dump_file
, " times.\n");
1238 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1241 fprintf (dump_file
, "Loop %d iterates at most %i times.\n", loop
->num
,
1244 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1245 && likely_max_loop_iterations_int (loop
) >= 0)
1247 fprintf (dump_file
, "Loop %d likely iterates at most %i times.\n",
1248 loop
->num
, (int)likely_max_loop_iterations_int (loop
));
1251 /* Remove exits that are known to be never taken based on loop bound.
1252 Needs to be called after compilation of max_loop_iterations_int that
1253 populates the loop bounds. */
1254 modified
|= remove_redundant_iv_tests (loop
);
1256 if (try_unroll_loop_completely (loop
, exit
, niter
, may_be_zero
, ul
,
1257 maxiter
, locus
, allow_peel
))
1261 && niter
&& !chrec_contains_undetermined (niter
)
1262 && exit
&& just_once_each_iteration_p (loop
, exit
->src
))
1264 tree iv_niter
= niter
;
1267 if (COMPARISON_CLASS_P (niter_desc
.may_be_zero
))
1268 iv_niter
= fold_build3 (COND_EXPR
, TREE_TYPE (iv_niter
),
1269 niter_desc
.may_be_zero
,
1270 build_int_cst (TREE_TYPE (iv_niter
), 0),
1273 iv_niter
= NULL_TREE
;
1276 create_canonical_iv (loop
, exit
, iv_niter
);
1280 modified
|= try_peel_loop (loop
, exit
, niter
, may_be_zero
, maxiter
);
1285 /* The main entry point of the pass. Adds canonical induction variables
1286 to the suitable loops. */
1289 canonicalize_induction_variables (void)
1292 bool changed
= false;
1293 bool irred_invalidated
= false;
1294 bitmap loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
1296 estimate_numbers_of_iterations (cfun
);
1298 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1300 changed
|= canonicalize_loop_induction_variables (loop
,
1301 true, UL_SINGLE_ITER
,
1304 gcc_assert (!need_ssa_update_p (cfun
));
1306 unloop_loops (loop_closed_ssa_invalidated
, &irred_invalidated
);
1307 if (irred_invalidated
1308 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1309 mark_irreducible_loops ();
1311 /* Clean up the information about numbers of iterations, since brute force
1312 evaluation could reveal new information. */
1313 free_numbers_of_iterations_estimates (cfun
);
1316 if (!bitmap_empty_p (loop_closed_ssa_invalidated
))
1318 gcc_checking_assert (loops_state_satisfies_p (LOOP_CLOSED_SSA
));
1319 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1321 BITMAP_FREE (loop_closed_ssa_invalidated
);
1324 return TODO_cleanup_cfg
;
1328 /* Process loops from innermost to outer, stopping at the innermost
1329 loop we unrolled. */
1332 tree_unroll_loops_completely_1 (bool may_increase_size
, bool unroll_outer
,
1333 bitmap father_bbs
, class loop
*loop
)
1335 class loop
*loop_father
;
1336 bool changed
= false;
1338 enum unroll_level ul
;
1339 unsigned num
= number_of_loops (cfun
);
1341 /* Process inner loops first. Don't walk loops added by the recursive
1342 calls because SSA form is not up-to-date. They can be handled in the
1344 bitmap child_father_bbs
= NULL
;
1345 for (inner
= loop
->inner
; inner
!= NULL
; inner
= inner
->next
)
1346 if ((unsigned) inner
->num
< num
)
1348 if (!child_father_bbs
)
1349 child_father_bbs
= BITMAP_ALLOC (NULL
);
1350 if (tree_unroll_loops_completely_1 (may_increase_size
, unroll_outer
,
1351 child_father_bbs
, inner
))
1353 bitmap_ior_into (father_bbs
, child_father_bbs
);
1354 bitmap_clear (child_father_bbs
);
1358 if (child_father_bbs
)
1359 BITMAP_FREE (child_father_bbs
);
1361 /* If we changed an inner loop we cannot process outer loops in this
1362 iteration because SSA form is not up-to-date. Continue with
1363 siblings of outer loops instead. */
1366 /* If we are recorded as father clear all other fathers that
1367 are necessarily covered already to avoid redundant work. */
1368 if (bitmap_bit_p (father_bbs
, loop
->header
->index
))
1370 bitmap_clear (father_bbs
);
1371 bitmap_set_bit (father_bbs
, loop
->header
->index
);
1376 /* Don't unroll #pragma omp simd loops until the vectorizer
1377 attempts to vectorize those. */
1378 if (loop
->force_vectorize
)
1381 /* Try to unroll this loop. */
1382 loop_father
= loop_outer (loop
);
1386 if (loop
->unroll
> 1)
1388 else if (may_increase_size
&& optimize_loop_nest_for_speed_p (loop
)
1389 /* Unroll outermost loops only if asked to do so or they do
1390 not cause code growth. */
1391 && (unroll_outer
|| loop_outer (loop_father
)))
1396 if (canonicalize_loop_induction_variables
1397 (loop
, false, ul
, !flag_tree_loop_ivcanon
, unroll_outer
))
1399 /* If we'll continue unrolling, we need to propagate constants
1400 within the new basic blocks to fold away induction variable
1401 computations; otherwise, the size might blow up before the
1402 iteration is complete and the IR eventually cleaned up. */
1403 if (loop_outer (loop_father
))
1405 /* Once we process our father we will have processed
1406 the fathers of our children as well, so avoid doing
1407 redundant work and clear fathers we've gathered sofar. */
1408 bitmap_clear (father_bbs
);
1409 bitmap_set_bit (father_bbs
, loop_father
->header
->index
);
1418 /* Unroll LOOPS completely if they iterate just few times. Unless
1419 MAY_INCREASE_SIZE is true, perform the unrolling only if the
1420 size of the code does not increase. */
1423 tree_unroll_loops_completely (bool may_increase_size
, bool unroll_outer
)
1425 bitmap father_bbs
= BITMAP_ALLOC (NULL
);
1428 bool irred_invalidated
= false;
1430 estimate_numbers_of_iterations (cfun
);
1435 bitmap loop_closed_ssa_invalidated
= NULL
;
1437 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1438 loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
1440 free_numbers_of_iterations_estimates (cfun
);
1441 estimate_numbers_of_iterations (cfun
);
1443 changed
= tree_unroll_loops_completely_1 (may_increase_size
,
1444 unroll_outer
, father_bbs
,
1445 current_loops
->tree_root
);
1450 unloop_loops (loop_closed_ssa_invalidated
, &irred_invalidated
);
1452 /* We cannot use TODO_update_ssa_no_phi because VOPS gets confused. */
1453 if (loop_closed_ssa_invalidated
1454 && !bitmap_empty_p (loop_closed_ssa_invalidated
))
1455 rewrite_into_loop_closed_ssa (loop_closed_ssa_invalidated
,
1458 update_ssa (TODO_update_ssa
);
1460 /* father_bbs is a bitmap of loop father header BB indices.
1461 Translate that to what non-root loops these BBs belong to now. */
1463 bitmap fathers
= BITMAP_ALLOC (NULL
);
1464 EXECUTE_IF_SET_IN_BITMAP (father_bbs
, 0, i
, bi
)
1466 basic_block unrolled_loop_bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
1467 if (! unrolled_loop_bb
)
1469 if (loop_outer (unrolled_loop_bb
->loop_father
))
1470 bitmap_set_bit (fathers
,
1471 unrolled_loop_bb
->loop_father
->num
);
1473 bitmap_clear (father_bbs
);
1474 /* Propagate the constants within the new basic blocks. */
1475 EXECUTE_IF_SET_IN_BITMAP (fathers
, 0, i
, bi
)
1477 loop_p father
= get_loop (cfun
, i
);
1478 bitmap exit_bbs
= BITMAP_ALLOC (NULL
);
1479 loop_exit
*exit
= father
->exits
->next
;
1482 bitmap_set_bit (exit_bbs
, exit
->e
->dest
->index
);
1485 do_rpo_vn (cfun
, loop_preheader_edge (father
), exit_bbs
);
1487 BITMAP_FREE (fathers
);
1489 /* This will take care of removing completely unrolled loops
1490 from the loop structures so we can continue unrolling now
1492 if (cleanup_tree_cfg ())
1493 update_ssa (TODO_update_ssa_only_virtuals
);
1495 /* Clean up the information about numbers of iterations, since
1496 complete unrolling might have invalidated it. */
1498 if (flag_checking
&& loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1499 verify_loop_closed_ssa (true);
1501 if (loop_closed_ssa_invalidated
)
1502 BITMAP_FREE (loop_closed_ssa_invalidated
);
1505 && ++iteration
<= param_max_unroll_iterations
);
1507 BITMAP_FREE (father_bbs
);
1509 if (irred_invalidated
1510 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1511 mark_irreducible_loops ();
1516 /* Canonical induction variable creation pass. */
1520 const pass_data pass_data_iv_canon
=
1522 GIMPLE_PASS
, /* type */
1523 "ivcanon", /* name */
1524 OPTGROUP_LOOP
, /* optinfo_flags */
1525 TV_TREE_LOOP_IVCANON
, /* tv_id */
1526 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1527 0, /* properties_provided */
1528 0, /* properties_destroyed */
1529 0, /* todo_flags_start */
1530 0, /* todo_flags_finish */
1533 class pass_iv_canon
: public gimple_opt_pass
1536 pass_iv_canon (gcc::context
*ctxt
)
1537 : gimple_opt_pass (pass_data_iv_canon
, ctxt
)
1540 /* opt_pass methods: */
1541 virtual bool gate (function
*) { return flag_tree_loop_ivcanon
!= 0; }
1542 virtual unsigned int execute (function
*fun
);
1544 }; // class pass_iv_canon
1547 pass_iv_canon::execute (function
*fun
)
1549 if (number_of_loops (fun
) <= 1)
1552 return canonicalize_induction_variables ();
1558 make_pass_iv_canon (gcc::context
*ctxt
)
1560 return new pass_iv_canon (ctxt
);
1563 /* Complete unrolling of loops. */
1567 const pass_data pass_data_complete_unroll
=
1569 GIMPLE_PASS
, /* type */
1570 "cunroll", /* name */
1571 OPTGROUP_LOOP
, /* optinfo_flags */
1572 TV_COMPLETE_UNROLL
, /* tv_id */
1573 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1574 0, /* properties_provided */
1575 0, /* properties_destroyed */
1576 0, /* todo_flags_start */
1577 0, /* todo_flags_finish */
1580 class pass_complete_unroll
: public gimple_opt_pass
1583 pass_complete_unroll (gcc::context
*ctxt
)
1584 : gimple_opt_pass (pass_data_complete_unroll
, ctxt
)
1587 /* opt_pass methods: */
1588 virtual unsigned int execute (function
*);
1590 }; // class pass_complete_unroll
1593 pass_complete_unroll::execute (function
*fun
)
1595 if (number_of_loops (fun
) <= 1)
1598 /* If we ever decide to run loop peeling more than once, we will need to
1599 track loops already peeled in loop structures themselves to avoid
1600 re-peeling the same loop multiple times. */
1601 if (flag_peel_loops
)
1602 peeled_loops
= BITMAP_ALLOC (NULL
);
1603 unsigned int val
= tree_unroll_loops_completely (flag_unroll_loops
1605 || optimize
>= 3, true);
1608 BITMAP_FREE (peeled_loops
);
1609 peeled_loops
= NULL
;
1617 make_pass_complete_unroll (gcc::context
*ctxt
)
1619 return new pass_complete_unroll (ctxt
);
1622 /* Complete unrolling of inner loops. */
1626 const pass_data pass_data_complete_unrolli
=
1628 GIMPLE_PASS
, /* type */
1629 "cunrolli", /* name */
1630 OPTGROUP_LOOP
, /* optinfo_flags */
1631 TV_COMPLETE_UNROLL
, /* tv_id */
1632 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1633 0, /* properties_provided */
1634 0, /* properties_destroyed */
1635 0, /* todo_flags_start */
1636 0, /* todo_flags_finish */
1639 class pass_complete_unrolli
: public gimple_opt_pass
1642 pass_complete_unrolli (gcc::context
*ctxt
)
1643 : gimple_opt_pass (pass_data_complete_unrolli
, ctxt
)
1646 /* opt_pass methods: */
1647 virtual bool gate (function
*) { return optimize
>= 2; }
1648 virtual unsigned int execute (function
*);
1650 }; // class pass_complete_unrolli
1653 pass_complete_unrolli::execute (function
*fun
)
1657 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
1658 if (number_of_loops (fun
) > 1)
1661 ret
= tree_unroll_loops_completely (optimize
>= 3, false);
1664 loop_optimizer_finalize ();
1672 make_pass_complete_unrolli (gcc::context
*ctxt
)
1674 return new pass_complete_unrolli (ctxt
);