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"
66 #include "tree-vectorizer.h" /* For find_loop_location */
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
*> (*gsi_last_bb (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
);
117 create_iv (niter
, PLUS_EXPR
,
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 (CONSTANT_CLASS_P (op
))
170 /* Get at the actual SSA operand. */
171 if (handled_component_p (op
)
172 && TREE_CODE (TREE_OPERAND (op
, 0)) == SSA_NAME
)
173 op
= TREE_OPERAND (op
, 0);
175 /* We can still fold accesses to constant arrays when index is known. */
176 if (TREE_CODE (op
) != SSA_NAME
)
180 /* First make fast look if we see constant array inside. */
181 while (handled_component_p (base
))
182 base
= TREE_OPERAND (base
, 0);
184 && ctor_for_folding (base
) != error_mark_node
)
185 || CONSTANT_CLASS_P (base
))
187 /* If so, see if we understand all the indices. */
189 while (handled_component_p (base
))
191 if (TREE_CODE (base
) == ARRAY_REF
192 && !constant_after_peeling (TREE_OPERAND (base
, 1), stmt
, loop
))
194 base
= TREE_OPERAND (base
, 0);
201 /* Induction variables are constants when defined in loop. */
202 if (loop_containing_stmt (stmt
) != loop
)
204 tree ev
= analyze_scalar_evolution (loop
, op
);
205 if (chrec_contains_undetermined (ev
)
206 || chrec_contains_symbols (ev
))
208 if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (op
)))
210 gassign
*ass
= nullptr;
212 if (is_a
<gassign
*> (SSA_NAME_DEF_STMT (op
)))
214 ass
= as_a
<gassign
*> (SSA_NAME_DEF_STMT (op
));
215 if (TREE_CODE (gimple_assign_rhs1 (ass
)) == SSA_NAME
)
216 phi
= dyn_cast
<gphi
*>
217 (SSA_NAME_DEF_STMT (gimple_assign_rhs1 (ass
)));
219 else if (is_a
<gphi
*> (SSA_NAME_DEF_STMT (op
)))
221 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (op
));
222 if (gimple_bb (phi
) == loop
->header
)
224 tree def
= gimple_phi_arg_def_from_edge
225 (phi
, loop_latch_edge (loop
));
226 if (TREE_CODE (def
) == SSA_NAME
227 && is_a
<gassign
*> (SSA_NAME_DEF_STMT (def
)))
228 ass
= as_a
<gassign
*> (SSA_NAME_DEF_STMT (def
));
233 tree rhs1
= gimple_assign_rhs1 (ass
);
234 if (gimple_assign_rhs_class (ass
) == GIMPLE_BINARY_RHS
235 && CONSTANT_CLASS_P (gimple_assign_rhs2 (ass
))
236 && rhs1
== gimple_phi_result (phi
)
237 && gimple_bb (phi
) == loop
->header
238 && (gimple_phi_arg_def_from_edge (phi
, loop_latch_edge (loop
))
239 == gimple_assign_lhs (ass
))
240 && (CONSTANT_CLASS_P (gimple_phi_arg_def_from_edge
241 (phi
, loop_preheader_edge (loop
)))))
250 /* Computes an estimated number of insns in LOOP.
251 EXIT (if non-NULL) is an exite edge that will be eliminated in all but last
252 iteration of the loop.
253 EDGE_TO_CANCEL (if non-NULL) is an non-exit edge eliminated in the last iteration
255 Return results in SIZE, estimate benefits for complete unrolling exiting by EXIT.
256 Stop estimating after UPPER_BOUND is met. Return true in this case. */
259 tree_estimate_loop_size (class loop
*loop
, edge exit
, edge edge_to_cancel
,
260 struct loop_size
*size
, int upper_bound
)
262 basic_block
*body
= get_loop_body (loop
);
263 gimple_stmt_iterator gsi
;
266 auto_vec
<basic_block
> path
= get_loop_hot_path (loop
);
269 size
->eliminated_by_peeling
= 0;
270 size
->last_iteration
= 0;
271 size
->last_iteration_eliminated_by_peeling
= 0;
272 size
->num_pure_calls_on_hot_path
= 0;
273 size
->num_non_pure_calls_on_hot_path
= 0;
274 size
->non_call_stmts_on_hot_path
= 0;
275 size
->num_branches_on_hot_path
= 0;
276 size
->constant_iv
= 0;
278 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
279 fprintf (dump_file
, "Estimating sizes for loop %i\n", loop
->num
);
280 for (i
= 0; i
< loop
->num_nodes
; i
++)
282 if (edge_to_cancel
&& body
[i
] != edge_to_cancel
->src
283 && dominated_by_p (CDI_DOMINATORS
, body
[i
], edge_to_cancel
->src
))
287 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
288 fprintf (dump_file
, " BB: %i, after_exit: %i\n", body
[i
]->index
,
291 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
293 gimple
*stmt
= gsi_stmt (gsi
);
294 int num
= estimate_num_insns (stmt
, &eni_size_weights
);
295 bool likely_eliminated
= false;
296 bool likely_eliminated_last
= false;
297 bool likely_eliminated_peeled
= false;
299 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
301 fprintf (dump_file
, " size: %3i ", num
);
302 print_gimple_stmt (dump_file
, gsi_stmt (gsi
), 0);
305 /* Look for reasons why we might optimize this stmt away. */
307 if (!gimple_has_side_effects (stmt
))
309 /* Exit conditional. */
310 if (exit
&& body
[i
] == exit
->src
311 && stmt
== *gsi_last_bb (exit
->src
))
313 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
314 fprintf (dump_file
, " Exit condition will be eliminated "
315 "in peeled copies.\n");
316 likely_eliminated_peeled
= true;
318 if (edge_to_cancel
&& body
[i
] == edge_to_cancel
->src
319 && stmt
== *gsi_last_bb (edge_to_cancel
->src
))
321 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
322 fprintf (dump_file
, " Exit condition will be eliminated "
324 likely_eliminated_last
= true;
326 /* Sets of IV variables */
327 if (gimple_code (stmt
) == GIMPLE_ASSIGN
328 && constant_after_peeling (gimple_assign_lhs (stmt
), stmt
, loop
))
330 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
331 fprintf (dump_file
, " Induction variable computation will"
332 " be folded away.\n");
333 likely_eliminated
= true;
335 /* Assignments of IV variables. */
336 else if (gimple_code (stmt
) == GIMPLE_ASSIGN
337 && TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
338 && constant_after_peeling (gimple_assign_rhs1 (stmt
),
340 && (gimple_assign_rhs_class (stmt
) != GIMPLE_BINARY_RHS
341 || constant_after_peeling (gimple_assign_rhs2 (stmt
),
343 && gimple_assign_rhs_class (stmt
) != GIMPLE_TERNARY_RHS
)
345 size
->constant_iv
= true;
346 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
348 " Constant expression will be folded away.\n");
349 likely_eliminated
= true;
352 else if ((gimple_code (stmt
) == GIMPLE_COND
353 && constant_after_peeling (gimple_cond_lhs (stmt
), stmt
,
355 && constant_after_peeling (gimple_cond_rhs (stmt
), stmt
,
357 /* We don't simplify all constant compares so make sure
358 they are not both constant already. See PR70288. */
359 && (! is_gimple_min_invariant (gimple_cond_lhs (stmt
))
360 || ! is_gimple_min_invariant
361 (gimple_cond_rhs (stmt
))))
362 || (gimple_code (stmt
) == GIMPLE_SWITCH
363 && constant_after_peeling (gimple_switch_index (
367 && ! is_gimple_min_invariant
369 (as_a
<gswitch
*> (stmt
)))))
371 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
372 fprintf (dump_file
, " Constant conditional.\n");
373 likely_eliminated
= true;
377 size
->overall
+= num
;
378 if (likely_eliminated
|| likely_eliminated_peeled
)
379 size
->eliminated_by_peeling
+= num
;
382 size
->last_iteration
+= num
;
383 if (likely_eliminated
|| likely_eliminated_last
)
384 size
->last_iteration_eliminated_by_peeling
+= num
;
386 if ((size
->overall
* 3 / 2 - size
->eliminated_by_peeling
387 - size
->last_iteration_eliminated_by_peeling
) > upper_bound
)
394 while (path
.length ())
396 basic_block bb
= path
.pop ();
397 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
399 gimple
*stmt
= gsi_stmt (gsi
);
400 if (gimple_code (stmt
) == GIMPLE_CALL
401 && !gimple_inexpensive_call_p (as_a
<gcall
*> (stmt
)))
403 int flags
= gimple_call_flags (stmt
);
404 if (flags
& (ECF_PURE
| ECF_CONST
))
405 size
->num_pure_calls_on_hot_path
++;
407 size
->num_non_pure_calls_on_hot_path
++;
408 size
->num_branches_on_hot_path
++;
410 /* Count inexpensive calls as non-calls, because they will likely
412 else if (gimple_code (stmt
) != GIMPLE_DEBUG
)
413 size
->non_call_stmts_on_hot_path
++;
414 if (((gimple_code (stmt
) == GIMPLE_COND
415 && (!constant_after_peeling (gimple_cond_lhs (stmt
), stmt
, loop
)
416 || !constant_after_peeling (gimple_cond_rhs (stmt
), stmt
,
418 || (gimple_code (stmt
) == GIMPLE_SWITCH
419 && !constant_after_peeling (gimple_switch_index (
420 as_a
<gswitch
*> (stmt
)),
422 && (!exit
|| bb
!= exit
->src
))
423 size
->num_branches_on_hot_path
++;
427 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
428 fprintf (dump_file
, "size: %i-%i, last_iteration: %i-%i\n", size
->overall
,
429 size
->eliminated_by_peeling
, size
->last_iteration
,
430 size
->last_iteration_eliminated_by_peeling
);
436 /* Estimate number of insns of completely unrolled loop.
437 It is (NUNROLL + 1) * size of loop body with taking into account
438 the fact that in last copy everything after exit conditional
439 is dead and that some instructions will be eliminated after
442 Loop body is likely going to simplify further, this is difficult
443 to guess, we just decrease the result by 1/3. */
445 static unsigned HOST_WIDE_INT
446 estimated_unrolled_size (struct loop_size
*size
,
447 unsigned HOST_WIDE_INT nunroll
)
449 HOST_WIDE_INT unr_insns
= ((nunroll
)
450 * (HOST_WIDE_INT
) (size
->overall
451 - size
->eliminated_by_peeling
));
454 unr_insns
+= size
->last_iteration
- size
->last_iteration_eliminated_by_peeling
;
456 unr_insns
= unr_insns
* 2 / 3;
463 /* Loop LOOP is known to not loop. See if there is an edge in the loop
464 body that can be remove to make the loop to always exit and at
465 the same time it does not make any code potentially executed
466 during the last iteration dead.
468 After complete unrolling we still may get rid of the conditional
469 on the exit in the last copy even if we have no idea what it does.
470 This is quite common case for loops of form
476 Here we prove the loop to iterate 5 times but we do not know
477 it from induction variable.
479 For now we handle only simple case where there is exit condition
480 just before the latch block and the latch block contains no statements
481 with side effect that may otherwise terminate the execution of loop
482 (such as by EH or by terminating the program or longjmp).
484 In the general case we may want to cancel the paths leading to statements
485 loop-niter identified as having undefined effect in the last iteration.
486 The other cases are hopefully rare and will be cleaned up later. */
489 loop_edge_to_cancel (class loop
*loop
)
493 gimple_stmt_iterator gsi
;
495 /* We want only one predecestor of the loop. */
496 if (EDGE_COUNT (loop
->latch
->preds
) > 1)
499 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
501 FOR_EACH_VEC_ELT (exits
, i
, edge_to_cancel
)
503 /* Find the other edge than the loop exit
504 leaving the conditoinal. */
505 if (EDGE_COUNT (edge_to_cancel
->src
->succs
) != 2)
507 if (EDGE_SUCC (edge_to_cancel
->src
, 0) == edge_to_cancel
)
508 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 1);
510 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 0);
512 /* We only can handle conditionals. */
513 if (!(edge_to_cancel
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
516 /* We should never have conditionals in the loop latch. */
517 gcc_assert (edge_to_cancel
->dest
!= loop
->header
);
519 /* Check that it leads to loop latch. */
520 if (edge_to_cancel
->dest
!= loop
->latch
)
523 /* Verify that the code in loop latch does nothing that may end program
524 execution without really reaching the exit. This may include
525 non-pure/const function calls, EH statements, volatile ASMs etc. */
526 for (gsi
= gsi_start_bb (loop
->latch
); !gsi_end_p (gsi
); gsi_next (&gsi
))
527 if (gimple_has_side_effects (gsi_stmt (gsi
)))
529 return edge_to_cancel
;
534 /* Remove all tests for exits that are known to be taken after LOOP was
535 peeled NPEELED times. Put gcc_unreachable before every statement
536 known to not be executed. */
539 remove_exits_and_undefined_stmts (class loop
*loop
, unsigned int npeeled
)
541 class nb_iter_bound
*elt
;
542 bool changed
= false;
544 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
546 /* If statement is known to be undefined after peeling, turn it
547 into unreachable (or trap when debugging experience is supposed
550 && wi::ltu_p (elt
->bound
, npeeled
))
552 gimple_stmt_iterator gsi
= gsi_for_stmt (elt
->stmt
);
553 location_t loc
= gimple_location (elt
->stmt
);
554 gcall
*stmt
= gimple_build_builtin_unreachable (loc
);
555 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
556 split_block (gimple_bb (stmt
), stmt
);
558 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
560 fprintf (dump_file
, "Forced statement unreachable: ");
561 print_gimple_stmt (dump_file
, elt
->stmt
, 0);
564 /* If we know the exit will be taken after peeling, update. */
565 else if (elt
->is_exit
566 && wi::leu_p (elt
->bound
, npeeled
))
568 basic_block bb
= gimple_bb (elt
->stmt
);
569 edge exit_edge
= EDGE_SUCC (bb
, 0);
571 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
573 fprintf (dump_file
, "Forced exit to be taken: ");
574 print_gimple_stmt (dump_file
, elt
->stmt
, 0);
576 if (!loop_exit_edge_p (loop
, exit_edge
))
577 exit_edge
= EDGE_SUCC (bb
, 1);
578 exit_edge
->probability
= profile_probability::always ();
579 gcc_checking_assert (loop_exit_edge_p (loop
, exit_edge
));
580 gcond
*cond_stmt
= as_a
<gcond
*> (elt
->stmt
);
581 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
582 gimple_cond_make_true (cond_stmt
);
584 gimple_cond_make_false (cond_stmt
);
585 update_stmt (cond_stmt
);
592 /* Remove all exits that are known to be never taken because of the loop bound
596 remove_redundant_iv_tests (class loop
*loop
)
598 class nb_iter_bound
*elt
;
599 bool changed
= false;
601 if (!loop
->any_upper_bound
)
603 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
605 /* Exit is pointless if it won't be taken before loop reaches
607 if (elt
->is_exit
&& loop
->any_upper_bound
608 && wi::ltu_p (loop
->nb_iterations_upper_bound
, elt
->bound
))
610 basic_block bb
= gimple_bb (elt
->stmt
);
611 edge exit_edge
= EDGE_SUCC (bb
, 0);
612 class tree_niter_desc niter
;
614 if (!loop_exit_edge_p (loop
, exit_edge
))
615 exit_edge
= EDGE_SUCC (bb
, 1);
617 /* Only when we know the actual number of iterations, not
618 just a bound, we can remove the exit. */
619 if (!number_of_iterations_exit (loop
, exit_edge
,
620 &niter
, false, false)
621 || !integer_onep (niter
.assumptions
)
622 || !integer_zerop (niter
.may_be_zero
)
624 || TREE_CODE (niter
.niter
) != INTEGER_CST
625 || !wi::ltu_p (widest_int::from (loop
->nb_iterations_upper_bound
,
627 wi::to_widest (niter
.niter
)))
630 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
632 fprintf (dump_file
, "Removed pointless exit: ");
633 print_gimple_stmt (dump_file
, elt
->stmt
, 0);
635 gcond
*cond_stmt
= as_a
<gcond
*> (elt
->stmt
);
636 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
637 gimple_cond_make_false (cond_stmt
);
639 gimple_cond_make_true (cond_stmt
);
640 update_stmt (cond_stmt
);
647 /* Stores loops that will be unlooped and edges that will be removed
648 after we process whole loop tree. */
649 static vec
<loop_p
> loops_to_unloop
;
650 static vec
<int> loops_to_unloop_nunroll
;
651 static vec
<edge
> edges_to_remove
;
652 /* Stores loops that has been peeled. */
653 static bitmap peeled_loops
;
655 /* Cancel all fully unrolled loops by putting __builtin_unreachable
657 We do it after all unrolling since unlooping moves basic blocks
658 across loop boundaries trashing loop closed SSA form as well
659 as SCEV info needed to be intact during unrolling.
661 IRRED_INVALIDATED is used to bookkeep if information about
662 irreducible regions may become invalid as a result
663 of the transformation.
664 LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case
665 when we need to go into loop closed SSA form. */
668 unloop_loops (vec
<class loop
*> &loops_to_unloop
,
669 vec
<int> &loops_to_unloop_nunroll
,
670 bitmap loop_closed_ssa_invalidated
,
671 bool *irred_invalidated
)
673 while (loops_to_unloop
.length ())
675 class loop
*loop
= loops_to_unloop
.pop ();
676 int n_unroll
= loops_to_unloop_nunroll
.pop ();
677 basic_block latch
= loop
->latch
;
678 edge latch_edge
= loop_latch_edge (loop
);
679 int flags
= latch_edge
->flags
;
680 location_t locus
= latch_edge
->goto_locus
;
682 gimple_stmt_iterator gsi
;
684 remove_exits_and_undefined_stmts (loop
, n_unroll
);
686 /* Unloop destroys the latch edge. */
687 unloop (loop
, irred_invalidated
, loop_closed_ssa_invalidated
);
689 /* Create new basic block for the latch edge destination and wire
691 stmt
= gimple_build_builtin_unreachable (locus
);
692 latch_edge
= make_edge (latch
, create_basic_block (NULL
, NULL
, latch
), flags
);
693 latch_edge
->probability
= profile_probability::never ();
694 latch_edge
->flags
|= flags
;
695 latch_edge
->goto_locus
= locus
;
697 add_bb_to_loop (latch_edge
->dest
, current_loops
->tree_root
);
698 latch_edge
->dest
->count
= profile_count::zero ();
699 set_immediate_dominator (CDI_DOMINATORS
, latch_edge
->dest
, latch_edge
->src
);
701 gsi
= gsi_start_bb (latch_edge
->dest
);
702 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
705 /* Remove edges in peeled copies. Given remove_path removes dominated
706 regions we need to cope with removal of already removed paths. */
709 auto_vec
<int, 20> src_bbs
;
710 src_bbs
.reserve_exact (edges_to_remove
.length ());
711 FOR_EACH_VEC_ELT (edges_to_remove
, i
, e
)
712 src_bbs
.quick_push (e
->src
->index
);
713 FOR_EACH_VEC_ELT (edges_to_remove
, i
, e
)
714 if (BASIC_BLOCK_FOR_FN (cfun
, src_bbs
[i
]))
716 bool ok
= remove_path (e
, irred_invalidated
,
717 loop_closed_ssa_invalidated
);
720 edges_to_remove
.release ();
723 /* Tries to unroll LOOP completely, i.e. NITER times.
724 UL determines which loops we are allowed to unroll.
725 EXIT is the exit of the loop that should be eliminated.
726 MAXITER specfy bound on number of iterations, -1 if it is
727 not known or too large for HOST_WIDE_INT. The location
728 LOCUS corresponding to the loop is used when emitting
729 a summary of the unroll to the dump file. */
732 try_unroll_loop_completely (class loop
*loop
,
733 edge exit
, tree niter
, bool may_be_zero
,
734 enum unroll_level ul
,
735 HOST_WIDE_INT maxiter
,
736 dump_user_location_t locus
, bool allow_peel
)
738 unsigned HOST_WIDE_INT n_unroll
= 0;
739 bool n_unroll_found
= false;
740 edge edge_to_cancel
= NULL
;
742 /* See if we proved number of iterations to be low constant.
744 EXIT is an edge that will be removed in all but last iteration of
747 EDGE_TO_CACNEL is an edge that will be removed from the last iteration
748 of the unrolled sequence and is expected to make the final loop not
751 If the number of execution of loop is determined by standard induction
752 variable test, then EXIT and EDGE_TO_CANCEL are the two edges leaving
754 if (tree_fits_uhwi_p (niter
))
756 n_unroll
= tree_to_uhwi (niter
);
757 n_unroll_found
= true;
758 edge_to_cancel
= EDGE_SUCC (exit
->src
, 0);
759 if (edge_to_cancel
== exit
)
760 edge_to_cancel
= EDGE_SUCC (exit
->src
, 1);
762 /* We do not know the number of iterations and thus we cannot eliminate
767 /* See if we can improve our estimate by using recorded loop bounds. */
768 if ((maxiter
== 0 || ul
!= UL_SINGLE_ITER
)
770 && (!n_unroll_found
|| (unsigned HOST_WIDE_INT
)maxiter
< n_unroll
))
773 n_unroll_found
= true;
774 /* Loop terminates before the IV variable test, so we cannot
775 remove it in the last iteration. */
776 edge_to_cancel
= NULL
;
777 /* If we do not allow peeling and we iterate just allow cases
778 that do not grow code. */
779 if (!allow_peel
&& maxiter
!= 0)
787 && n_unroll
> (unsigned) param_max_completely_peel_times
)
789 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
790 fprintf (dump_file
, "Not unrolling loop %d "
791 "(--param max-completely-peel-times limit reached).\n",
797 edge_to_cancel
= loop_edge_to_cancel (loop
);
801 if (ul
== UL_SINGLE_ITER
)
806 /* If the unrolling factor is too large, bail out. */
807 if (n_unroll
> (unsigned)loop
->unroll
)
809 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
811 "Not unrolling loop %d: "
812 "user didn't want it unrolled completely.\n",
819 struct loop_size size
;
820 /* EXIT can be removed only if we are sure it passes first N_UNROLL
822 bool remove_exit
= (exit
&& niter
823 && TREE_CODE (niter
) == INTEGER_CST
824 && wi::leu_p (n_unroll
, wi::to_widest (niter
)));
826 = tree_estimate_loop_size
827 (loop
, remove_exit
? exit
: NULL
, edge_to_cancel
, &size
,
828 param_max_completely_peeled_insns
);
831 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
832 fprintf (dump_file
, "Not unrolling loop %d: it is too large.\n",
837 unsigned HOST_WIDE_INT ninsns
= size
.overall
;
838 unsigned HOST_WIDE_INT unr_insns
839 = estimated_unrolled_size (&size
, n_unroll
);
840 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
842 fprintf (dump_file
, " Loop size: %d\n", (int) ninsns
);
843 fprintf (dump_file
, " Estimated size after unrolling: %d\n",
847 /* If the code is going to shrink, we don't need to be extra
848 cautious on guessing if the unrolling is going to be
851 /* If there is IV variable that will become constant, we
852 save one instruction in the loop prologue we do not
853 account otherwise. */
854 <= ninsns
+ (size
.constant_iv
!= false))
856 /* We unroll only inner loops, because we do not consider it
857 profitable otheriwse. We still can cancel loopback edge
858 of not rolling loop; this is always a good idea. */
859 else if (ul
== UL_NO_GROWTH
)
861 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
862 fprintf (dump_file
, "Not unrolling loop %d: size would grow.\n",
866 /* Outer loops tend to be less interesting candidates for
867 complete unrolling unless we can do a lot of propagation
868 into the inner loop body. For now we disable outer loop
869 unrolling when the code would grow. */
870 else if (loop
->inner
)
872 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
873 fprintf (dump_file
, "Not unrolling loop %d: "
874 "it is not innermost and code would grow.\n",
878 /* If there is call on a hot path through the loop, then
879 there is most probably not much to optimize. */
880 else if (size
.num_non_pure_calls_on_hot_path
)
882 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
883 fprintf (dump_file
, "Not unrolling loop %d: "
884 "contains call and code would grow.\n",
888 /* If there is pure/const call in the function, then we can
889 still optimize the unrolled loop body if it contains some
890 other interesting code than the calls and code storing or
891 cumulating the return value. */
892 else if (size
.num_pure_calls_on_hot_path
893 /* One IV increment, one test, one ivtmp store and
894 one useful stmt. That is about minimal loop
896 && (size
.non_call_stmts_on_hot_path
897 <= 3 + size
.num_pure_calls_on_hot_path
))
899 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
900 fprintf (dump_file
, "Not unrolling loop %d: "
901 "contains just pure calls and code would grow.\n",
905 /* Complete unrolling is major win when control flow is
906 removed and one big basic block is created. If the loop
907 contains control flow the optimization may still be a win
908 because of eliminating the loop overhead but it also may
909 blow the branch predictor tables. Limit number of
910 branches on the hot path through the peeled sequence. */
911 else if (size
.num_branches_on_hot_path
* (int)n_unroll
912 > param_max_peel_branches
)
914 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
915 fprintf (dump_file
, "Not unrolling loop %d: "
916 "number of branches on hot path in the unrolled "
917 "sequence reaches --param max-peel-branches limit.\n",
922 > (unsigned) param_max_completely_peeled_insns
)
924 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
925 fprintf (dump_file
, "Not unrolling loop %d: "
926 "number of insns in the unrolled sequence reaches "
927 "--param max-completely-peeled-insns limit.\n",
933 if (!dbg_cnt (gimple_unroll
))
936 initialize_original_copy_tables ();
937 auto_sbitmap
wont_exit (n_unroll
+ 1);
939 && TREE_CODE (niter
) == INTEGER_CST
940 && wi::leu_p (n_unroll
, wi::to_widest (niter
)))
942 bitmap_ones (wont_exit
);
943 if (wi::eq_p (wi::to_widest (niter
), n_unroll
)
945 bitmap_clear_bit (wont_exit
, 0);
950 bitmap_clear (wont_exit
);
953 bitmap_clear_bit (wont_exit
, 1);
955 /* If loop was originally estimated to iterate too many times,
956 reduce the profile to avoid new profile inconsistencies. */
957 scale_loop_profile (loop
, profile_probability::always (), n_unroll
);
959 if (!gimple_duplicate_loop_body_to_header_edge (
960 loop
, loop_preheader_edge (loop
), n_unroll
, wont_exit
, exit
,
962 DLTHE_FLAG_UPDATE_FREQ
| DLTHE_FLAG_COMPLETTE_PEEL
))
964 free_original_copy_tables ();
965 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
966 fprintf (dump_file
, "Failed to duplicate the loop\n");
970 free_original_copy_tables ();
973 scale_loop_profile (loop
, profile_probability::always (), 0);
975 /* Remove the conditional from the last copy of the loop. */
978 gcond
*cond
= as_a
<gcond
*> (*gsi_last_bb (edge_to_cancel
->src
));
979 force_edge_cold (edge_to_cancel
, true);
980 if (edge_to_cancel
->flags
& EDGE_TRUE_VALUE
)
981 gimple_cond_make_false (cond
);
983 gimple_cond_make_true (cond
);
985 /* Do not remove the path, as doing so may remove outer loop and
986 confuse bookkeeping code in tree_unroll_loops_completely. */
989 /* Store the loop for later unlooping and exit removal. */
990 loops_to_unloop
.safe_push (loop
);
991 loops_to_unloop_nunroll
.safe_push (n_unroll
);
993 if (dump_enabled_p ())
996 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
997 "loop turned into non-loop; it never loops\n");
1000 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
1001 "loop with %d iterations completely unrolled",
1003 if (loop
->header
->count
.initialized_p ())
1004 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
,
1005 " (header execution count %d)",
1006 (int)loop
->header
->count
.to_gcov_type ());
1007 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, "\n");
1011 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1014 fprintf (dump_file
, "Exit condition of peeled iterations was "
1017 fprintf (dump_file
, "Last iteration exit edge was proved true.\n");
1019 fprintf (dump_file
, "Latch of last iteration was marked by "
1020 "__builtin_unreachable ().\n");
1026 /* Return number of instructions after peeling. */
1027 static unsigned HOST_WIDE_INT
1028 estimated_peeled_sequence_size (struct loop_size
*size
,
1029 unsigned HOST_WIDE_INT npeel
)
1031 return MAX (npeel
* (HOST_WIDE_INT
) (size
->overall
1032 - size
->eliminated_by_peeling
), 1);
1035 /* Update loop estimates after peeling LOOP by NPEEL.
1036 If PRECISE is false only likely exists were duplicated and thus
1037 do not update any estimates that are supposed to be always reliable. */
1039 adjust_loop_info_after_peeling (class loop
*loop
, int npeel
, bool precise
)
1041 if (loop
->any_estimate
)
1043 /* Since peeling is mostly about loops where first few
1044 iterations are special, it is not quite correct to
1045 assume that the remaining iterations will behave
1046 the same way. However we do not have better info
1047 so update the esitmate, since it is likely better
1048 than keeping it as it is.
1050 Remove it if it looks wrong.
1052 TODO: We likely want to special case the situation where
1053 peeling is optimizing out exit edges and only update
1055 if (wi::leu_p (npeel
, loop
->nb_iterations_estimate
))
1056 loop
->nb_iterations_estimate
-= npeel
;
1058 loop
->any_estimate
= false;
1060 if (loop
->any_upper_bound
&& precise
)
1062 if (wi::leu_p (npeel
, loop
->nb_iterations_upper_bound
))
1063 loop
->nb_iterations_upper_bound
-= npeel
;
1066 /* Peeling maximal number of iterations or more
1067 makes no sense and is a bug.
1068 We should peel completely. */
1072 if (loop
->any_likely_upper_bound
)
1074 if (wi::leu_p (npeel
, loop
->nb_iterations_likely_upper_bound
))
1075 loop
->nb_iterations_likely_upper_bound
-= npeel
;
1078 loop
->any_estimate
= true;
1079 loop
->nb_iterations_estimate
= 0;
1080 loop
->nb_iterations_likely_upper_bound
= 0;
1085 /* If the loop is expected to iterate N times and is
1086 small enough, duplicate the loop body N+1 times before
1087 the loop itself. This way the hot path will never
1089 Parameters are the same as for try_unroll_loops_completely */
1092 try_peel_loop (class loop
*loop
,
1093 edge exit
, tree niter
, bool may_be_zero
,
1094 HOST_WIDE_INT maxiter
)
1096 HOST_WIDE_INT npeel
;
1097 struct loop_size size
;
1100 if (!flag_peel_loops
1101 || param_max_peel_times
<= 0
1105 if (bitmap_bit_p (peeled_loops
, loop
->num
))
1108 fprintf (dump_file
, "Not peeling: loop is already peeled\n");
1112 /* We don't peel loops that will be unrolled as this can duplicate a
1113 loop more times than the user requested. */
1117 fprintf (dump_file
, "Not peeling: user didn't want it peeled.\n");
1121 /* Peel only innermost loops.
1122 While the code is perfectly capable of peeling non-innermost loops,
1123 the heuristics would probably need some improvements. */
1127 fprintf (dump_file
, "Not peeling: outer loop\n");
1131 if (!optimize_loop_for_speed_p (loop
))
1134 fprintf (dump_file
, "Not peeling: cold loop\n");
1138 /* Check if there is an estimate on the number of iterations. */
1139 npeel
= estimated_loop_iterations_int (loop
);
1141 npeel
= likely_max_loop_iterations_int (loop
);
1145 fprintf (dump_file
, "Not peeling: number of iterations is not "
1149 if (maxiter
>= 0 && maxiter
<= npeel
)
1152 fprintf (dump_file
, "Not peeling: upper bound is known so can "
1153 "unroll completely\n");
1157 /* We want to peel estimated number of iterations + 1 (so we never
1158 enter the loop on quick path). Check against PARAM_MAX_PEEL_TIMES
1159 and be sure to avoid overflows. */
1160 if (npeel
> param_max_peel_times
- 1)
1163 fprintf (dump_file
, "Not peeling: rolls too much "
1164 "(%i + 1 > --param max-peel-times)\n", (int) npeel
);
1169 /* Check peeled loops size. */
1170 tree_estimate_loop_size (loop
, exit
, NULL
, &size
,
1171 param_max_peeled_insns
);
1172 if ((peeled_size
= estimated_peeled_sequence_size (&size
, (int) npeel
))
1173 > param_max_peeled_insns
)
1176 fprintf (dump_file
, "Not peeling: peeled sequence size is too large "
1177 "(%i insns > --param max-peel-insns)", peeled_size
);
1181 if (!dbg_cnt (gimple_unroll
))
1184 /* Duplicate possibly eliminating the exits. */
1185 initialize_original_copy_tables ();
1186 auto_sbitmap
wont_exit (npeel
+ 1);
1188 && TREE_CODE (niter
) == INTEGER_CST
1189 && wi::leu_p (npeel
, wi::to_widest (niter
)))
1191 bitmap_ones (wont_exit
);
1192 bitmap_clear_bit (wont_exit
, 0);
1197 bitmap_clear (wont_exit
);
1200 bitmap_clear_bit (wont_exit
, 1);
1202 if (!gimple_duplicate_loop_body_to_header_edge (
1203 loop
, loop_preheader_edge (loop
), npeel
, wont_exit
, exit
,
1204 &edges_to_remove
, DLTHE_FLAG_UPDATE_FREQ
))
1206 free_original_copy_tables ();
1209 free_original_copy_tables ();
1210 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1212 fprintf (dump_file
, "Peeled loop %d, %i times.\n",
1213 loop
->num
, (int) npeel
);
1215 adjust_loop_info_after_peeling (loop
, npeel
, true);
1217 bitmap_set_bit (peeled_loops
, loop
->num
);
1220 /* Adds a canonical induction variable to LOOP if suitable.
1221 CREATE_IV is true if we may create a new iv. UL determines
1222 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
1223 to determine the number of iterations of a loop by direct evaluation.
1224 Returns true if cfg is changed. */
1227 canonicalize_loop_induction_variables (class loop
*loop
,
1228 bool create_iv
, enum unroll_level ul
,
1229 bool try_eval
, bool allow_peel
)
1233 HOST_WIDE_INT maxiter
;
1234 bool modified
= false;
1235 class tree_niter_desc niter_desc
;
1236 bool may_be_zero
= false;
1238 /* For unrolling allow conditional constant or zero iterations, thus
1239 perform loop-header copying on-the-fly. */
1240 exit
= single_exit (loop
);
1241 niter
= chrec_dont_know
;
1242 if (exit
&& number_of_iterations_exit (loop
, exit
, &niter_desc
, false))
1244 niter
= niter_desc
.niter
;
1246 = niter_desc
.may_be_zero
&& !integer_zerop (niter_desc
.may_be_zero
);
1248 if (TREE_CODE (niter
) != INTEGER_CST
)
1250 /* For non-constant niter fold may_be_zero into niter again. */
1253 if (COMPARISON_CLASS_P (niter_desc
.may_be_zero
))
1254 niter
= fold_build3 (COND_EXPR
, TREE_TYPE (niter
),
1255 niter_desc
.may_be_zero
,
1256 build_int_cst (TREE_TYPE (niter
), 0), niter
);
1258 niter
= chrec_dont_know
;
1259 may_be_zero
= false;
1262 /* If the loop has more than one exit, try checking all of them
1263 for # of iterations determinable through scev. */
1265 niter
= find_loop_niter (loop
, &exit
);
1267 /* Finally if everything else fails, try brute force evaluation. */
1269 && (chrec_contains_undetermined (niter
)
1270 || TREE_CODE (niter
) != INTEGER_CST
))
1271 niter
= find_loop_niter_by_eval (loop
, &exit
);
1273 if (TREE_CODE (niter
) != INTEGER_CST
)
1277 /* We work exceptionally hard here to estimate the bound
1278 by find_loop_niter_by_eval. Be sure to keep it for future. */
1279 if (niter
&& TREE_CODE (niter
) == INTEGER_CST
)
1281 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
1282 record_niter_bound (loop
, wi::to_widest (niter
),
1283 exit
== single_likely_exit (loop
, exits
), true);
1286 /* Force re-computation of loop bounds so we can remove redundant exits. */
1287 maxiter
= max_loop_iterations_int (loop
);
1289 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1290 && TREE_CODE (niter
) == INTEGER_CST
)
1292 fprintf (dump_file
, "Loop %d iterates ", loop
->num
);
1293 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1294 fprintf (dump_file
, " times.\n");
1296 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1299 fprintf (dump_file
, "Loop %d iterates at most %i times.\n", loop
->num
,
1302 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1303 && likely_max_loop_iterations_int (loop
) >= 0)
1305 fprintf (dump_file
, "Loop %d likely iterates at most %i times.\n",
1306 loop
->num
, (int)likely_max_loop_iterations_int (loop
));
1309 /* Remove exits that are known to be never taken based on loop bound.
1310 Needs to be called after compilation of max_loop_iterations_int that
1311 populates the loop bounds. */
1312 modified
|= remove_redundant_iv_tests (loop
);
1314 dump_user_location_t locus
= find_loop_location (loop
);
1315 if (try_unroll_loop_completely (loop
, exit
, niter
, may_be_zero
, ul
,
1316 maxiter
, locus
, allow_peel
))
1320 && niter
&& !chrec_contains_undetermined (niter
)
1321 && exit
&& just_once_each_iteration_p (loop
, exit
->src
))
1323 tree iv_niter
= niter
;
1326 if (COMPARISON_CLASS_P (niter_desc
.may_be_zero
))
1327 iv_niter
= fold_build3 (COND_EXPR
, TREE_TYPE (iv_niter
),
1328 niter_desc
.may_be_zero
,
1329 build_int_cst (TREE_TYPE (iv_niter
), 0),
1332 iv_niter
= NULL_TREE
;
1335 create_canonical_iv (loop
, exit
, iv_niter
);
1339 modified
|= try_peel_loop (loop
, exit
, niter
, may_be_zero
, maxiter
);
1344 /* The main entry point of the pass. Adds canonical induction variables
1345 to the suitable loops. */
1348 canonicalize_induction_variables (void)
1350 bool changed
= false;
1351 bool irred_invalidated
= false;
1352 bitmap loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
1354 estimate_numbers_of_iterations (cfun
);
1356 for (auto loop
: loops_list (cfun
, LI_FROM_INNERMOST
))
1358 changed
|= canonicalize_loop_induction_variables (loop
,
1359 true, UL_SINGLE_ITER
,
1362 gcc_assert (!need_ssa_update_p (cfun
));
1364 unloop_loops (loops_to_unloop
, loops_to_unloop_nunroll
,
1365 loop_closed_ssa_invalidated
, &irred_invalidated
);
1366 loops_to_unloop
.release ();
1367 loops_to_unloop_nunroll
.release ();
1368 if (irred_invalidated
1369 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1370 mark_irreducible_loops ();
1372 /* Clean up the information about numbers of iterations, since brute force
1373 evaluation could reveal new information. */
1374 free_numbers_of_iterations_estimates (cfun
);
1377 if (!bitmap_empty_p (loop_closed_ssa_invalidated
))
1379 gcc_checking_assert (loops_state_satisfies_p (LOOP_CLOSED_SSA
));
1380 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1382 BITMAP_FREE (loop_closed_ssa_invalidated
);
1385 return TODO_cleanup_cfg
;
1389 /* Process loops from innermost to outer, stopping at the innermost
1390 loop we unrolled. */
1393 tree_unroll_loops_completely_1 (bool may_increase_size
, bool unroll_outer
,
1394 bitmap father_bbs
, class loop
*loop
)
1396 class loop
*loop_father
;
1397 bool changed
= false;
1399 enum unroll_level ul
;
1400 unsigned num
= number_of_loops (cfun
);
1402 /* Process inner loops first. Don't walk loops added by the recursive
1403 calls because SSA form is not up-to-date. They can be handled in the
1405 bitmap child_father_bbs
= NULL
;
1406 for (inner
= loop
->inner
; inner
!= NULL
; inner
= inner
->next
)
1407 if ((unsigned) inner
->num
< num
)
1409 if (!child_father_bbs
)
1410 child_father_bbs
= BITMAP_ALLOC (NULL
);
1411 if (tree_unroll_loops_completely_1 (may_increase_size
, unroll_outer
,
1412 child_father_bbs
, inner
))
1414 bitmap_ior_into (father_bbs
, child_father_bbs
);
1415 bitmap_clear (child_father_bbs
);
1419 if (child_father_bbs
)
1420 BITMAP_FREE (child_father_bbs
);
1422 /* If we changed an inner loop we cannot process outer loops in this
1423 iteration because SSA form is not up-to-date. Continue with
1424 siblings of outer loops instead. */
1427 /* If we are recorded as father clear all other fathers that
1428 are necessarily covered already to avoid redundant work. */
1429 if (bitmap_bit_p (father_bbs
, loop
->header
->index
))
1431 bitmap_clear (father_bbs
);
1432 bitmap_set_bit (father_bbs
, loop
->header
->index
);
1437 /* Don't unroll #pragma omp simd loops until the vectorizer
1438 attempts to vectorize those. */
1439 if (loop
->force_vectorize
)
1442 /* Try to unroll this loop. */
1443 loop_father
= loop_outer (loop
);
1447 if (loop
->unroll
> 1)
1449 else if (may_increase_size
&& optimize_loop_nest_for_speed_p (loop
)
1450 /* Unroll outermost loops only if asked to do so or they do
1451 not cause code growth. */
1452 && (unroll_outer
|| loop_outer (loop_father
)))
1457 if (canonicalize_loop_induction_variables
1458 (loop
, false, ul
, !flag_tree_loop_ivcanon
, unroll_outer
))
1460 /* If we'll continue unrolling, we need to propagate constants
1461 within the new basic blocks to fold away induction variable
1462 computations; otherwise, the size might blow up before the
1463 iteration is complete and the IR eventually cleaned up. */
1464 if (loop_outer (loop_father
))
1466 /* Once we process our father we will have processed
1467 the fathers of our children as well, so avoid doing
1468 redundant work and clear fathers we've gathered sofar. */
1469 bitmap_clear (father_bbs
);
1470 bitmap_set_bit (father_bbs
, loop_father
->header
->index
);
1472 else if (unroll_outer
)
1473 /* Trigger scalar cleanup once any outermost loop gets unrolled. */
1474 cfun
->pending_TODOs
|= PENDING_TODO_force_next_scalar_cleanup
;
1482 /* Unroll LOOPS completely if they iterate just few times. Unless
1483 MAY_INCREASE_SIZE is true, perform the unrolling only if the
1484 size of the code does not increase. */
1487 tree_unroll_loops_completely (bool may_increase_size
, bool unroll_outer
)
1489 bitmap father_bbs
= BITMAP_ALLOC (NULL
);
1492 bool irred_invalidated
= false;
1494 estimate_numbers_of_iterations (cfun
);
1499 bitmap loop_closed_ssa_invalidated
= NULL
;
1501 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1502 loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
1504 free_numbers_of_iterations_estimates (cfun
);
1505 estimate_numbers_of_iterations (cfun
);
1507 changed
= tree_unroll_loops_completely_1 (may_increase_size
,
1508 unroll_outer
, father_bbs
,
1509 current_loops
->tree_root
);
1514 unloop_loops (loops_to_unloop
,
1515 loops_to_unloop_nunroll
,
1516 loop_closed_ssa_invalidated
,
1517 &irred_invalidated
);
1518 loops_to_unloop
.release ();
1519 loops_to_unloop_nunroll
.release ();
1521 /* We cannot use TODO_update_ssa_no_phi because VOPS gets confused. */
1522 if (loop_closed_ssa_invalidated
1523 && !bitmap_empty_p (loop_closed_ssa_invalidated
))
1524 rewrite_into_loop_closed_ssa (loop_closed_ssa_invalidated
,
1527 update_ssa (TODO_update_ssa
);
1529 /* father_bbs is a bitmap of loop father header BB indices.
1530 Translate that to what non-root loops these BBs belong to now. */
1532 bitmap fathers
= BITMAP_ALLOC (NULL
);
1533 EXECUTE_IF_SET_IN_BITMAP (father_bbs
, 0, i
, bi
)
1535 basic_block unrolled_loop_bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
1536 if (! unrolled_loop_bb
)
1538 if (loop_outer (unrolled_loop_bb
->loop_father
))
1539 bitmap_set_bit (fathers
,
1540 unrolled_loop_bb
->loop_father
->num
);
1542 bitmap_clear (father_bbs
);
1543 /* Propagate the constants within the new basic blocks. */
1544 EXECUTE_IF_SET_IN_BITMAP (fathers
, 0, i
, bi
)
1546 loop_p father
= get_loop (cfun
, i
);
1547 bitmap exit_bbs
= BITMAP_ALLOC (NULL
);
1548 loop_exit
*exit
= father
->exits
->next
;
1551 bitmap_set_bit (exit_bbs
, exit
->e
->dest
->index
);
1554 do_rpo_vn (cfun
, loop_preheader_edge (father
), exit_bbs
);
1556 BITMAP_FREE (fathers
);
1558 /* Clean up the information about numbers of iterations, since
1559 complete unrolling might have invalidated it. */
1562 /* This will take care of removing completely unrolled loops
1563 from the loop structures so we can continue unrolling now
1565 if (cleanup_tree_cfg ())
1566 update_ssa (TODO_update_ssa_only_virtuals
);
1568 if (flag_checking
&& loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1569 verify_loop_closed_ssa (true);
1571 if (loop_closed_ssa_invalidated
)
1572 BITMAP_FREE (loop_closed_ssa_invalidated
);
1575 && ++iteration
<= param_max_unroll_iterations
);
1577 BITMAP_FREE (father_bbs
);
1579 if (irred_invalidated
1580 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1581 mark_irreducible_loops ();
1586 /* Canonical induction variable creation pass. */
1590 const pass_data pass_data_iv_canon
=
1592 GIMPLE_PASS
, /* type */
1593 "ivcanon", /* name */
1594 OPTGROUP_LOOP
, /* optinfo_flags */
1595 TV_TREE_LOOP_IVCANON
, /* tv_id */
1596 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1597 0, /* properties_provided */
1598 0, /* properties_destroyed */
1599 0, /* todo_flags_start */
1600 0, /* todo_flags_finish */
1603 class pass_iv_canon
: public gimple_opt_pass
1606 pass_iv_canon (gcc::context
*ctxt
)
1607 : gimple_opt_pass (pass_data_iv_canon
, ctxt
)
1610 /* opt_pass methods: */
1611 bool gate (function
*) final override
{ return flag_tree_loop_ivcanon
!= 0; }
1612 unsigned int execute (function
*fun
) final override
;
1614 }; // class pass_iv_canon
1617 pass_iv_canon::execute (function
*fun
)
1619 if (number_of_loops (fun
) <= 1)
1622 return canonicalize_induction_variables ();
1628 make_pass_iv_canon (gcc::context
*ctxt
)
1630 return new pass_iv_canon (ctxt
);
1633 /* Complete unrolling of loops. */
1637 const pass_data pass_data_complete_unroll
=
1639 GIMPLE_PASS
, /* type */
1640 "cunroll", /* name */
1641 OPTGROUP_LOOP
, /* optinfo_flags */
1642 TV_COMPLETE_UNROLL
, /* tv_id */
1643 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1644 0, /* properties_provided */
1645 0, /* properties_destroyed */
1646 0, /* todo_flags_start */
1647 0, /* todo_flags_finish */
1650 class pass_complete_unroll
: public gimple_opt_pass
1653 pass_complete_unroll (gcc::context
*ctxt
)
1654 : gimple_opt_pass (pass_data_complete_unroll
, ctxt
)
1657 /* opt_pass methods: */
1658 unsigned int execute (function
*) final override
;
1660 }; // class pass_complete_unroll
1663 pass_complete_unroll::execute (function
*fun
)
1665 if (number_of_loops (fun
) <= 1)
1668 /* If we ever decide to run loop peeling more than once, we will need to
1669 track loops already peeled in loop structures themselves to avoid
1670 re-peeling the same loop multiple times. */
1671 if (flag_peel_loops
)
1672 peeled_loops
= BITMAP_ALLOC (NULL
);
1673 unsigned int val
= tree_unroll_loops_completely (flag_cunroll_grow_size
,
1677 BITMAP_FREE (peeled_loops
);
1678 peeled_loops
= NULL
;
1686 make_pass_complete_unroll (gcc::context
*ctxt
)
1688 return new pass_complete_unroll (ctxt
);
1691 /* Complete unrolling of inner loops. */
1695 const pass_data pass_data_complete_unrolli
=
1697 GIMPLE_PASS
, /* type */
1698 "cunrolli", /* name */
1699 OPTGROUP_LOOP
, /* optinfo_flags */
1700 TV_COMPLETE_UNROLL
, /* tv_id */
1701 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1702 0, /* properties_provided */
1703 0, /* properties_destroyed */
1704 0, /* todo_flags_start */
1705 0, /* todo_flags_finish */
1708 class pass_complete_unrolli
: public gimple_opt_pass
1711 pass_complete_unrolli (gcc::context
*ctxt
)
1712 : gimple_opt_pass (pass_data_complete_unrolli
, ctxt
)
1715 /* opt_pass methods: */
1716 bool gate (function
*) final override
{ return optimize
>= 2; }
1717 unsigned int execute (function
*) final override
;
1719 }; // class pass_complete_unrolli
1722 pass_complete_unrolli::execute (function
*fun
)
1726 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
1727 if (number_of_loops (fun
) > 1)
1730 ret
= tree_unroll_loops_completely (optimize
>= 3, false);
1733 loop_optimizer_finalize ();
1741 make_pass_complete_unrolli (gcc::context
*ctxt
)
1743 return new pass_complete_unrolli (ctxt
);