1 /* Induction variable canonicalization and loop peeling.
2 Copyright (C) 2004-2015 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"
46 #include "fold-const.h"
50 #include "hard-reg-set.h"
53 #include "dominance.h"
55 #include "basic-block.h"
56 #include "gimple-pretty-print.h"
57 #include "tree-ssa-alias.h"
58 #include "internal-fn.h"
59 #include "gimple-fold.h"
61 #include "gimple-expr.h"
64 #include "gimple-iterator.h"
65 #include "gimple-ssa.h"
66 #include "plugin-api.h"
70 #include "tree-phinodes.h"
71 #include "ssa-iterators.h"
72 #include "stringpool.h"
73 #include "tree-ssanames.h"
74 #include "tree-ssa-loop-manip.h"
75 #include "tree-ssa-loop-niter.h"
76 #include "tree-ssa-loop.h"
77 #include "tree-into-ssa.h"
79 #include "tree-pass.h"
80 #include "tree-chrec.h"
81 #include "tree-scalar-evolution.h"
84 #include "tree-inline.h"
86 #include "tree-cfgcleanup.h"
89 /* Specifies types of loops that may be unrolled. */
93 UL_SINGLE_ITER
, /* Only loops that exit immediately in the first
95 UL_NO_GROWTH
, /* Only loops whose unrolling will not cause increase
97 UL_ALL
/* All suitable loops. */
100 /* Adds a canonical induction variable to LOOP iterating NITER times. EXIT
101 is the exit edge whose condition is replaced. */
104 create_canonical_iv (struct loop
*loop
, edge exit
, tree niter
)
109 gimple_stmt_iterator incr_at
;
112 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
114 fprintf (dump_file
, "Added canonical iv to loop %d, ", loop
->num
);
115 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
116 fprintf (dump_file
, " iterations.\n");
119 cond
= as_a
<gcond
*> (last_stmt (exit
->src
));
120 in
= EDGE_SUCC (exit
->src
, 0);
122 in
= EDGE_SUCC (exit
->src
, 1);
124 /* Note that we do not need to worry about overflows, since
125 type of niter is always unsigned and all comparisons are
126 just for equality/nonequality -- i.e. everything works
127 with a modulo arithmetics. */
129 type
= TREE_TYPE (niter
);
130 niter
= fold_build2 (PLUS_EXPR
, type
,
132 build_int_cst (type
, 1));
133 incr_at
= gsi_last_bb (in
->src
);
135 build_int_cst (type
, -1),
137 &incr_at
, false, NULL
, &var
);
139 cmp
= (exit
->flags
& EDGE_TRUE_VALUE
) ? EQ_EXPR
: NE_EXPR
;
140 gimple_cond_set_code (cond
, cmp
);
141 gimple_cond_set_lhs (cond
, var
);
142 gimple_cond_set_rhs (cond
, build_int_cst (type
, 0));
146 /* Describe size of loop as detected by tree_estimate_loop_size. */
149 /* Number of instructions in the loop. */
152 /* Number of instructions that will be likely optimized out in
153 peeled iterations of loop (i.e. computation based on induction
154 variable where induction variable starts at known constant.) */
155 int eliminated_by_peeling
;
157 /* Same statistics for last iteration of loop: it is smaller because
158 instructions after exit are not executed. */
160 int last_iteration_eliminated_by_peeling
;
162 /* If some IV computation will become constant. */
165 /* Number of call stmts that are not a builtin and are pure or const
166 present on the hot path. */
167 int num_pure_calls_on_hot_path
;
168 /* Number of call stmts that are not a builtin and are not pure nor const
169 present on the hot path. */
170 int num_non_pure_calls_on_hot_path
;
171 /* Number of statements other than calls in the loop. */
172 int non_call_stmts_on_hot_path
;
173 /* Number of branches seen on the hot path. */
174 int num_branches_on_hot_path
;
177 /* Return true if OP in STMT will be constant after peeling LOOP. */
180 constant_after_peeling (tree op
, gimple stmt
, struct loop
*loop
)
184 if (is_gimple_min_invariant (op
))
187 /* We can still fold accesses to constant arrays when index is known. */
188 if (TREE_CODE (op
) != SSA_NAME
)
192 /* First make fast look if we see constant array inside. */
193 while (handled_component_p (base
))
194 base
= TREE_OPERAND (base
, 0);
196 && ctor_for_folding (base
) != error_mark_node
)
197 || CONSTANT_CLASS_P (base
))
199 /* If so, see if we understand all the indices. */
201 while (handled_component_p (base
))
203 if (TREE_CODE (base
) == ARRAY_REF
204 && !constant_after_peeling (TREE_OPERAND (base
, 1), stmt
, loop
))
206 base
= TREE_OPERAND (base
, 0);
213 /* Induction variables are constants. */
214 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op
, &iv
, false))
216 if (!is_gimple_min_invariant (iv
.base
))
218 if (!is_gimple_min_invariant (iv
.step
))
223 /* Computes an estimated number of insns in LOOP.
224 EXIT (if non-NULL) is an exite edge that will be eliminated in all but last
225 iteration of the loop.
226 EDGE_TO_CANCEL (if non-NULL) is an non-exit edge eliminated in the last iteration
228 Return results in SIZE, estimate benefits for complete unrolling exiting by EXIT.
229 Stop estimating after UPPER_BOUND is met. Return true in this case. */
232 tree_estimate_loop_size (struct loop
*loop
, edge exit
, edge edge_to_cancel
, struct loop_size
*size
,
235 basic_block
*body
= get_loop_body (loop
);
236 gimple_stmt_iterator gsi
;
239 vec
<basic_block
> path
= get_loop_hot_path (loop
);
242 size
->eliminated_by_peeling
= 0;
243 size
->last_iteration
= 0;
244 size
->last_iteration_eliminated_by_peeling
= 0;
245 size
->num_pure_calls_on_hot_path
= 0;
246 size
->num_non_pure_calls_on_hot_path
= 0;
247 size
->non_call_stmts_on_hot_path
= 0;
248 size
->num_branches_on_hot_path
= 0;
249 size
->constant_iv
= 0;
251 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
252 fprintf (dump_file
, "Estimating sizes for loop %i\n", loop
->num
);
253 for (i
= 0; i
< loop
->num_nodes
; i
++)
255 if (edge_to_cancel
&& body
[i
] != edge_to_cancel
->src
256 && dominated_by_p (CDI_DOMINATORS
, body
[i
], edge_to_cancel
->src
))
260 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
261 fprintf (dump_file
, " BB: %i, after_exit: %i\n", body
[i
]->index
, after_exit
);
263 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
265 gimple stmt
= gsi_stmt (gsi
);
266 int num
= estimate_num_insns (stmt
, &eni_size_weights
);
267 bool likely_eliminated
= false;
268 bool likely_eliminated_last
= false;
269 bool likely_eliminated_peeled
= false;
271 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
273 fprintf (dump_file
, " size: %3i ", num
);
274 print_gimple_stmt (dump_file
, gsi_stmt (gsi
), 0, 0);
277 /* Look for reasons why we might optimize this stmt away. */
279 if (gimple_has_side_effects (stmt
))
281 /* Exit conditional. */
282 else if (exit
&& body
[i
] == exit
->src
283 && stmt
== last_stmt (exit
->src
))
285 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
286 fprintf (dump_file
, " Exit condition will be eliminated "
287 "in peeled copies.\n");
288 likely_eliminated_peeled
= true;
290 else if (edge_to_cancel
&& body
[i
] == edge_to_cancel
->src
291 && stmt
== last_stmt (edge_to_cancel
->src
))
293 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
294 fprintf (dump_file
, " Exit condition will be eliminated "
296 likely_eliminated_last
= true;
298 /* Sets of IV variables */
299 else if (gimple_code (stmt
) == GIMPLE_ASSIGN
300 && constant_after_peeling (gimple_assign_lhs (stmt
), stmt
, loop
))
302 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
303 fprintf (dump_file
, " Induction variable computation will"
304 " be folded away.\n");
305 likely_eliminated
= true;
307 /* Assignments of IV variables. */
308 else if (gimple_code (stmt
) == GIMPLE_ASSIGN
309 && TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
310 && constant_after_peeling (gimple_assign_rhs1 (stmt
), stmt
, loop
)
311 && (gimple_assign_rhs_class (stmt
) != GIMPLE_BINARY_RHS
312 || constant_after_peeling (gimple_assign_rhs2 (stmt
),
315 size
->constant_iv
= true;
316 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
317 fprintf (dump_file
, " Constant expression will be folded away.\n");
318 likely_eliminated
= true;
321 else if ((gimple_code (stmt
) == GIMPLE_COND
322 && constant_after_peeling (gimple_cond_lhs (stmt
), stmt
, loop
)
323 && constant_after_peeling (gimple_cond_rhs (stmt
), stmt
, loop
))
324 || (gimple_code (stmt
) == GIMPLE_SWITCH
325 && constant_after_peeling (gimple_switch_index (
326 as_a
<gswitch
*> (stmt
)),
329 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
330 fprintf (dump_file
, " Constant conditional.\n");
331 likely_eliminated
= true;
334 size
->overall
+= num
;
335 if (likely_eliminated
|| likely_eliminated_peeled
)
336 size
->eliminated_by_peeling
+= num
;
339 size
->last_iteration
+= num
;
340 if (likely_eliminated
|| likely_eliminated_last
)
341 size
->last_iteration_eliminated_by_peeling
+= num
;
343 if ((size
->overall
* 3 / 2 - size
->eliminated_by_peeling
344 - size
->last_iteration_eliminated_by_peeling
) > upper_bound
)
352 while (path
.length ())
354 basic_block bb
= path
.pop ();
355 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
357 gimple stmt
= gsi_stmt (gsi
);
358 if (gimple_code (stmt
) == GIMPLE_CALL
)
360 int flags
= gimple_call_flags (stmt
);
361 tree decl
= gimple_call_fndecl (stmt
);
363 if (decl
&& DECL_IS_BUILTIN (decl
)
364 && is_inexpensive_builtin (decl
))
366 else if (flags
& (ECF_PURE
| ECF_CONST
))
367 size
->num_pure_calls_on_hot_path
++;
369 size
->num_non_pure_calls_on_hot_path
++;
370 size
->num_branches_on_hot_path
++;
372 else if (gimple_code (stmt
) != GIMPLE_CALL
373 && gimple_code (stmt
) != GIMPLE_DEBUG
)
374 size
->non_call_stmts_on_hot_path
++;
375 if (((gimple_code (stmt
) == GIMPLE_COND
376 && (!constant_after_peeling (gimple_cond_lhs (stmt
), stmt
, loop
)
377 || constant_after_peeling (gimple_cond_rhs (stmt
), stmt
, loop
)))
378 || (gimple_code (stmt
) == GIMPLE_SWITCH
379 && !constant_after_peeling (gimple_switch_index (
380 as_a
<gswitch
*> (stmt
)),
382 && (!exit
|| bb
!= exit
->src
))
383 size
->num_branches_on_hot_path
++;
387 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
388 fprintf (dump_file
, "size: %i-%i, last_iteration: %i-%i\n", size
->overall
,
389 size
->eliminated_by_peeling
, size
->last_iteration
,
390 size
->last_iteration_eliminated_by_peeling
);
396 /* Estimate number of insns of completely unrolled loop.
397 It is (NUNROLL + 1) * size of loop body with taking into account
398 the fact that in last copy everything after exit conditional
399 is dead and that some instructions will be eliminated after
402 Loop body is likely going to simplify further, this is difficult
403 to guess, we just decrease the result by 1/3. */
405 static unsigned HOST_WIDE_INT
406 estimated_unrolled_size (struct loop_size
*size
,
407 unsigned HOST_WIDE_INT nunroll
)
409 HOST_WIDE_INT unr_insns
= ((nunroll
)
410 * (HOST_WIDE_INT
) (size
->overall
411 - size
->eliminated_by_peeling
));
414 unr_insns
+= size
->last_iteration
- size
->last_iteration_eliminated_by_peeling
;
416 unr_insns
= unr_insns
* 2 / 3;
423 /* Loop LOOP is known to not loop. See if there is an edge in the loop
424 body that can be remove to make the loop to always exit and at
425 the same time it does not make any code potentially executed
426 during the last iteration dead.
428 After complete unrolling we still may get rid of the conditional
429 on the exit in the last copy even if we have no idea what it does.
430 This is quite common case for loops of form
436 Here we prove the loop to iterate 5 times but we do not know
437 it from induction variable.
439 For now we handle only simple case where there is exit condition
440 just before the latch block and the latch block contains no statements
441 with side effect that may otherwise terminate the execution of loop
442 (such as by EH or by terminating the program or longjmp).
444 In the general case we may want to cancel the paths leading to statements
445 loop-niter identified as having undefined effect in the last iteration.
446 The other cases are hopefully rare and will be cleaned up later. */
449 loop_edge_to_cancel (struct loop
*loop
)
454 gimple_stmt_iterator gsi
;
456 /* We want only one predecestor of the loop. */
457 if (EDGE_COUNT (loop
->latch
->preds
) > 1)
460 exits
= get_loop_exit_edges (loop
);
462 FOR_EACH_VEC_ELT (exits
, i
, edge_to_cancel
)
464 /* Find the other edge than the loop exit
465 leaving the conditoinal. */
466 if (EDGE_COUNT (edge_to_cancel
->src
->succs
) != 2)
468 if (EDGE_SUCC (edge_to_cancel
->src
, 0) == edge_to_cancel
)
469 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 1);
471 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 0);
473 /* We only can handle conditionals. */
474 if (!(edge_to_cancel
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
477 /* We should never have conditionals in the loop latch. */
478 gcc_assert (edge_to_cancel
->dest
!= loop
->header
);
480 /* Check that it leads to loop latch. */
481 if (edge_to_cancel
->dest
!= loop
->latch
)
486 /* Verify that the code in loop latch does nothing that may end program
487 execution without really reaching the exit. This may include
488 non-pure/const function calls, EH statements, volatile ASMs etc. */
489 for (gsi
= gsi_start_bb (loop
->latch
); !gsi_end_p (gsi
); gsi_next (&gsi
))
490 if (gimple_has_side_effects (gsi_stmt (gsi
)))
492 return edge_to_cancel
;
498 /* Remove all tests for exits that are known to be taken after LOOP was
499 peeled NPEELED times. Put gcc_unreachable before every statement
500 known to not be executed. */
503 remove_exits_and_undefined_stmts (struct loop
*loop
, unsigned int npeeled
)
505 struct nb_iter_bound
*elt
;
506 bool changed
= false;
508 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
510 /* If statement is known to be undefined after peeling, turn it
511 into unreachable (or trap when debugging experience is supposed
514 && wi::ltu_p (elt
->bound
, npeeled
))
516 gimple_stmt_iterator gsi
= gsi_for_stmt (elt
->stmt
);
517 gcall
*stmt
= gimple_build_call
518 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
), 0);
519 gimple_set_location (stmt
, gimple_location (elt
->stmt
));
520 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
521 split_block (gimple_bb (stmt
), stmt
);
523 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
525 fprintf (dump_file
, "Forced statement unreachable: ");
526 print_gimple_stmt (dump_file
, elt
->stmt
, 0, 0);
529 /* If we know the exit will be taken after peeling, update. */
530 else if (elt
->is_exit
531 && wi::leu_p (elt
->bound
, npeeled
))
533 basic_block bb
= gimple_bb (elt
->stmt
);
534 edge exit_edge
= EDGE_SUCC (bb
, 0);
536 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
538 fprintf (dump_file
, "Forced exit to be taken: ");
539 print_gimple_stmt (dump_file
, elt
->stmt
, 0, 0);
541 if (!loop_exit_edge_p (loop
, exit_edge
))
542 exit_edge
= EDGE_SUCC (bb
, 1);
543 gcc_checking_assert (loop_exit_edge_p (loop
, exit_edge
));
544 gcond
*cond_stmt
= as_a
<gcond
*> (elt
->stmt
);
545 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
546 gimple_cond_make_true (cond_stmt
);
548 gimple_cond_make_false (cond_stmt
);
549 update_stmt (cond_stmt
);
556 /* Remove all exits that are known to be never taken because of the loop bound
560 remove_redundant_iv_tests (struct loop
*loop
)
562 struct nb_iter_bound
*elt
;
563 bool changed
= false;
565 if (!loop
->any_upper_bound
)
567 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
569 /* Exit is pointless if it won't be taken before loop reaches
571 if (elt
->is_exit
&& loop
->any_upper_bound
572 && wi::ltu_p (loop
->nb_iterations_upper_bound
, elt
->bound
))
574 basic_block bb
= gimple_bb (elt
->stmt
);
575 edge exit_edge
= EDGE_SUCC (bb
, 0);
576 struct tree_niter_desc niter
;
578 if (!loop_exit_edge_p (loop
, exit_edge
))
579 exit_edge
= EDGE_SUCC (bb
, 1);
581 /* Only when we know the actual number of iterations, not
582 just a bound, we can remove the exit. */
583 if (!number_of_iterations_exit (loop
, exit_edge
,
584 &niter
, false, false)
585 || !integer_onep (niter
.assumptions
)
586 || !integer_zerop (niter
.may_be_zero
)
588 || TREE_CODE (niter
.niter
) != INTEGER_CST
589 || !wi::ltu_p (loop
->nb_iterations_upper_bound
,
590 wi::to_widest (niter
.niter
)))
593 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
595 fprintf (dump_file
, "Removed pointless exit: ");
596 print_gimple_stmt (dump_file
, elt
->stmt
, 0, 0);
598 gcond
*cond_stmt
= as_a
<gcond
*> (elt
->stmt
);
599 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
600 gimple_cond_make_false (cond_stmt
);
602 gimple_cond_make_true (cond_stmt
);
603 update_stmt (cond_stmt
);
610 /* Stores loops that will be unlooped after we process whole loop tree. */
611 static vec
<loop_p
> loops_to_unloop
;
612 static vec
<int> loops_to_unloop_nunroll
;
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 struct 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
= 0;
651 latch_edge
->count
= 0;
652 latch_edge
->flags
|= flags
;
653 latch_edge
->goto_locus
= locus
;
655 latch_edge
->dest
->loop_father
= current_loops
->tree_root
;
656 latch_edge
->dest
->count
= 0;
657 latch_edge
->dest
->frequency
= 0;
658 set_immediate_dominator (CDI_DOMINATORS
, latch_edge
->dest
, latch_edge
->src
);
660 gsi
= gsi_start_bb (latch_edge
->dest
);
661 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
663 loops_to_unloop
.release ();
664 loops_to_unloop_nunroll
.release ();
667 /* Tries to unroll LOOP completely, i.e. NITER times.
668 UL determines which loops we are allowed to unroll.
669 EXIT is the exit of the loop that should be eliminated.
670 MAXITER specfy bound on number of iterations, -1 if it is
671 not known or too large for HOST_WIDE_INT. The location
672 LOCUS corresponding to the loop is used when emitting
673 a summary of the unroll to the dump file. */
676 try_unroll_loop_completely (struct loop
*loop
,
677 edge exit
, tree niter
,
678 enum unroll_level ul
,
679 HOST_WIDE_INT maxiter
,
682 unsigned HOST_WIDE_INT n_unroll
= 0, ninsns
, unr_insns
;
683 struct loop_size size
;
684 bool n_unroll_found
= false;
685 edge edge_to_cancel
= NULL
;
686 int report_flags
= MSG_OPTIMIZED_LOCATIONS
| TDF_RTL
| TDF_DETAILS
;
688 /* See if we proved number of iterations to be low constant.
690 EXIT is an edge that will be removed in all but last iteration of
693 EDGE_TO_CACNEL is an edge that will be removed from the last iteration
694 of the unrolled sequence and is expected to make the final loop not
697 If the number of execution of loop is determined by standard induction
698 variable test, then EXIT and EDGE_TO_CANCEL are the two edges leaving
700 if (tree_fits_uhwi_p (niter
))
702 n_unroll
= tree_to_uhwi (niter
);
703 n_unroll_found
= true;
704 edge_to_cancel
= EDGE_SUCC (exit
->src
, 0);
705 if (edge_to_cancel
== exit
)
706 edge_to_cancel
= EDGE_SUCC (exit
->src
, 1);
708 /* We do not know the number of iterations and thus we can not eliminate
713 /* See if we can improve our estimate by using recorded loop bounds. */
715 && (!n_unroll_found
|| (unsigned HOST_WIDE_INT
)maxiter
< n_unroll
))
718 n_unroll_found
= true;
719 /* Loop terminates before the IV variable test, so we can not
720 remove it in the last iteration. */
721 edge_to_cancel
= NULL
;
727 if (n_unroll
> (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
))
729 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
730 fprintf (dump_file
, "Not unrolling loop %d "
731 "(--param max-completely-peeled-times limit reached).\n",
737 edge_to_cancel
= loop_edge_to_cancel (loop
);
745 vec
<edge
> to_remove
= vNULL
;
746 if (ul
== UL_SINGLE_ITER
)
749 large
= tree_estimate_loop_size
750 (loop
, exit
, edge_to_cancel
, &size
,
751 PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
));
752 ninsns
= size
.overall
;
755 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
756 fprintf (dump_file
, "Not unrolling loop %d: it is too large.\n",
761 unr_insns
= estimated_unrolled_size (&size
, n_unroll
);
762 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
764 fprintf (dump_file
, " Loop size: %d\n", (int) ninsns
);
765 fprintf (dump_file
, " Estimated size after unrolling: %d\n",
769 /* If the code is going to shrink, we don't need to be extra cautious
770 on guessing if the unrolling is going to be profitable. */
772 /* If there is IV variable that will become constant, we save
773 one instruction in the loop prologue we do not account
775 <= ninsns
+ (size
.constant_iv
!= false))
777 /* We unroll only inner loops, because we do not consider it profitable
778 otheriwse. We still can cancel loopback edge of not rolling loop;
779 this is always a good idea. */
780 else if (ul
== UL_NO_GROWTH
)
782 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
783 fprintf (dump_file
, "Not unrolling loop %d: size would grow.\n",
787 /* Outer loops tend to be less interesting candidates for complete
788 unrolling unless we can do a lot of propagation into the inner loop
789 body. For now we disable outer loop unrolling when the code would
791 else if (loop
->inner
)
793 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
794 fprintf (dump_file
, "Not unrolling loop %d: "
795 "it is not innermost and code would grow.\n",
799 /* If there is call on a hot path through the loop, then
800 there is most probably not much to optimize. */
801 else if (size
.num_non_pure_calls_on_hot_path
)
803 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
804 fprintf (dump_file
, "Not unrolling loop %d: "
805 "contains call and code would grow.\n",
809 /* If there is pure/const call in the function, then we
810 can still optimize the unrolled loop body if it contains
811 some other interesting code than the calls and code
812 storing or cumulating the return value. */
813 else if (size
.num_pure_calls_on_hot_path
814 /* One IV increment, one test, one ivtmp store
815 and one useful stmt. That is about minimal loop
817 && (size
.non_call_stmts_on_hot_path
818 <= 3 + size
.num_pure_calls_on_hot_path
))
820 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
821 fprintf (dump_file
, "Not unrolling loop %d: "
822 "contains just pure calls and code would grow.\n",
826 /* Complette unrolling is major win when control flow is removed and
827 one big basic block is created. If the loop contains control flow
828 the optimization may still be a win because of eliminating the loop
829 overhead but it also may blow the branch predictor tables.
830 Limit number of branches on the hot path through the peeled
832 else if (size
.num_branches_on_hot_path
* (int)n_unroll
833 > PARAM_VALUE (PARAM_MAX_PEEL_BRANCHES
))
835 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
836 fprintf (dump_file
, "Not unrolling loop %d: "
837 " number of branches on hot path in the unrolled sequence"
838 " reach --param max-peel-branches limit.\n",
843 > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
))
845 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
846 fprintf (dump_file
, "Not unrolling loop %d: "
847 "(--param max-completely-peeled-insns limit reached).\n",
851 dump_printf_loc (report_flags
, locus
,
852 "loop turned into non-loop; it never loops.\n");
854 initialize_original_copy_tables ();
855 wont_exit
= sbitmap_alloc (n_unroll
+ 1);
856 bitmap_ones (wont_exit
);
857 bitmap_clear_bit (wont_exit
, 0);
859 if (!gimple_duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
862 DLTHE_FLAG_UPDATE_FREQ
863 | DLTHE_FLAG_COMPLETTE_PEEL
))
865 free_original_copy_tables ();
867 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
868 fprintf (dump_file
, "Failed to duplicate the loop\n");
872 FOR_EACH_VEC_ELT (to_remove
, i
, e
)
874 bool ok
= remove_path (e
);
878 to_remove
.release ();
880 free_original_copy_tables ();
884 /* Remove the conditional from the last copy of the loop. */
887 gcond
*cond
= as_a
<gcond
*> (last_stmt (edge_to_cancel
->src
));
888 if (edge_to_cancel
->flags
& EDGE_TRUE_VALUE
)
889 gimple_cond_make_false (cond
);
891 gimple_cond_make_true (cond
);
893 /* Do not remove the path. Doing so may remove outer loop
894 and confuse bookkeeping code in tree_unroll_loops_completelly. */
897 /* Store the loop for later unlooping and exit removal. */
898 loops_to_unloop
.safe_push (loop
);
899 loops_to_unloop_nunroll
.safe_push (n_unroll
);
901 if (dump_enabled_p ())
904 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
905 "loop turned into non-loop; it never loops\n");
908 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
909 "loop with %d iterations completely unrolled",
910 (int) (n_unroll
+ 1));
912 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
,
913 " (header execution count %d)",
914 (int)loop
->header
->count
);
915 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, "\n");
919 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
922 fprintf (dump_file
, "Exit condition of peeled iterations was "
925 fprintf (dump_file
, "Last iteration exit edge was proved true.\n");
927 fprintf (dump_file
, "Latch of last iteration was marked by "
928 "__builtin_unreachable ().\n");
934 /* Return number of instructions after peeling. */
935 static unsigned HOST_WIDE_INT
936 estimated_peeled_sequence_size (struct loop_size
*size
,
937 unsigned HOST_WIDE_INT npeel
)
939 return MAX (npeel
* (HOST_WIDE_INT
) (size
->overall
940 - size
->eliminated_by_peeling
), 1);
943 /* If the loop is expected to iterate N times and is
944 small enough, duplicate the loop body N+1 times before
945 the loop itself. This way the hot path will never
947 Parameters are the same as for try_unroll_loops_completely */
950 try_peel_loop (struct loop
*loop
,
951 edge exit
, tree niter
,
952 HOST_WIDE_INT maxiter
)
955 struct loop_size size
;
959 vec
<edge
> to_remove
= vNULL
;
962 /* If the iteration bound is known and large, then we can safely eliminate
963 the check in peeled copies. */
964 if (TREE_CODE (niter
) != INTEGER_CST
)
967 if (!flag_peel_loops
|| PARAM_VALUE (PARAM_MAX_PEEL_TIMES
) <= 0)
970 /* Peel only innermost loops. */
974 fprintf (dump_file
, "Not peeling: outer loop\n");
978 if (!optimize_loop_for_speed_p (loop
))
981 fprintf (dump_file
, "Not peeling: cold loop\n");
985 /* Check if there is an estimate on the number of iterations. */
986 npeel
= estimated_loop_iterations_int (loop
);
990 fprintf (dump_file
, "Not peeling: number of iterations is not "
994 if (maxiter
>= 0 && maxiter
<= npeel
)
997 fprintf (dump_file
, "Not peeling: upper bound is known so can "
998 "unroll completely\n");
1002 /* We want to peel estimated number of iterations + 1 (so we never
1003 enter the loop on quick path). Check against PARAM_MAX_PEEL_TIMES
1004 and be sure to avoid overflows. */
1005 if (npeel
> PARAM_VALUE (PARAM_MAX_PEEL_TIMES
) - 1)
1008 fprintf (dump_file
, "Not peeling: rolls too much "
1009 "(%i + 1 > --param max-peel-times)\n", npeel
);
1014 /* Check peeled loops size. */
1015 tree_estimate_loop_size (loop
, exit
, NULL
, &size
,
1016 PARAM_VALUE (PARAM_MAX_PEELED_INSNS
));
1017 if ((peeled_size
= estimated_peeled_sequence_size (&size
, npeel
))
1018 > PARAM_VALUE (PARAM_MAX_PEELED_INSNS
))
1021 fprintf (dump_file
, "Not peeling: peeled sequence size is too large "
1022 "(%i insns > --param max-peel-insns)", peeled_size
);
1026 /* Duplicate possibly eliminating the exits. */
1027 initialize_original_copy_tables ();
1028 wont_exit
= sbitmap_alloc (npeel
+ 1);
1029 bitmap_ones (wont_exit
);
1030 bitmap_clear_bit (wont_exit
, 0);
1031 if (!gimple_duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1034 DLTHE_FLAG_UPDATE_FREQ
1035 | DLTHE_FLAG_COMPLETTE_PEEL
))
1037 free_original_copy_tables ();
1041 FOR_EACH_VEC_ELT (to_remove
, i
, e
)
1043 bool ok
= remove_path (e
);
1047 free_original_copy_tables ();
1048 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1050 fprintf (dump_file
, "Peeled loop %d, %i times.\n",
1053 if (loop
->any_upper_bound
)
1054 loop
->nb_iterations_upper_bound
-= npeel
;
1055 loop
->nb_iterations_estimate
= 0;
1056 /* Make sure to mark loop cold so we do not try to peel it more. */
1057 scale_loop_profile (loop
, 1, 0);
1058 loop
->header
->count
= 0;
1061 /* Adds a canonical induction variable to LOOP if suitable.
1062 CREATE_IV is true if we may create a new iv. UL determines
1063 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
1064 to determine the number of iterations of a loop by direct evaluation.
1065 Returns true if cfg is changed. */
1068 canonicalize_loop_induction_variables (struct loop
*loop
,
1069 bool create_iv
, enum unroll_level ul
,
1074 HOST_WIDE_INT maxiter
;
1075 bool modified
= false;
1076 location_t locus
= UNKNOWN_LOCATION
;
1078 niter
= number_of_latch_executions (loop
);
1079 exit
= single_exit (loop
);
1080 if (TREE_CODE (niter
) == INTEGER_CST
)
1081 locus
= gimple_location (last_stmt (exit
->src
));
1084 /* If the loop has more than one exit, try checking all of them
1085 for # of iterations determinable through scev. */
1087 niter
= find_loop_niter (loop
, &exit
);
1089 /* Finally if everything else fails, try brute force evaluation. */
1091 && (chrec_contains_undetermined (niter
)
1092 || TREE_CODE (niter
) != INTEGER_CST
))
1093 niter
= find_loop_niter_by_eval (loop
, &exit
);
1096 locus
= gimple_location (last_stmt (exit
->src
));
1098 if (TREE_CODE (niter
) != INTEGER_CST
)
1102 /* We work exceptionally hard here to estimate the bound
1103 by find_loop_niter_by_eval. Be sure to keep it for future. */
1104 if (niter
&& TREE_CODE (niter
) == INTEGER_CST
)
1106 record_niter_bound (loop
, wi::to_widest (niter
),
1107 exit
== single_likely_exit (loop
), true);
1110 /* Force re-computation of loop bounds so we can remove redundant exits. */
1111 maxiter
= max_loop_iterations_int (loop
);
1113 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1114 && TREE_CODE (niter
) == INTEGER_CST
)
1116 fprintf (dump_file
, "Loop %d iterates ", loop
->num
);
1117 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1118 fprintf (dump_file
, " times.\n");
1120 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1123 fprintf (dump_file
, "Loop %d iterates at most %i times.\n", loop
->num
,
1127 /* Remove exits that are known to be never taken based on loop bound.
1128 Needs to be called after compilation of max_loop_iterations_int that
1129 populates the loop bounds. */
1130 modified
|= remove_redundant_iv_tests (loop
);
1132 if (try_unroll_loop_completely (loop
, exit
, niter
, ul
, maxiter
, locus
))
1136 && niter
&& !chrec_contains_undetermined (niter
)
1137 && exit
&& just_once_each_iteration_p (loop
, exit
->src
))
1138 create_canonical_iv (loop
, exit
, niter
);
1141 modified
|= try_peel_loop (loop
, exit
, niter
, maxiter
);
1146 /* The main entry point of the pass. Adds canonical induction variables
1147 to the suitable loops. */
1150 canonicalize_induction_variables (void)
1153 bool changed
= false;
1154 bool irred_invalidated
= false;
1155 bitmap loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
1157 free_numbers_of_iterations_estimates ();
1158 estimate_numbers_of_iterations ();
1160 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1162 changed
|= canonicalize_loop_induction_variables (loop
,
1163 true, UL_SINGLE_ITER
,
1166 gcc_assert (!need_ssa_update_p (cfun
));
1168 unloop_loops (loop_closed_ssa_invalidated
, &irred_invalidated
);
1169 if (irred_invalidated
1170 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1171 mark_irreducible_loops ();
1173 /* Clean up the information about numbers of iterations, since brute force
1174 evaluation could reveal new information. */
1177 if (!bitmap_empty_p (loop_closed_ssa_invalidated
))
1179 gcc_checking_assert (loops_state_satisfies_p (LOOP_CLOSED_SSA
));
1180 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1182 BITMAP_FREE (loop_closed_ssa_invalidated
);
1185 return TODO_cleanup_cfg
;
1189 /* Propagate VAL into all uses of SSA_NAME. */
1192 propagate_into_all_uses (tree ssa_name
, tree val
)
1194 imm_use_iterator iter
;
1197 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, ssa_name
)
1199 gimple_stmt_iterator use_stmt_gsi
= gsi_for_stmt (use_stmt
);
1202 FOR_EACH_IMM_USE_ON_STMT (use
, iter
)
1205 if (is_gimple_assign (use_stmt
)
1206 && get_gimple_rhs_class (gimple_assign_rhs_code (use_stmt
))
1207 == GIMPLE_SINGLE_RHS
)
1209 tree rhs
= gimple_assign_rhs1 (use_stmt
);
1211 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1212 recompute_tree_invariant_for_addr_expr (rhs
);
1215 fold_stmt_inplace (&use_stmt_gsi
);
1216 update_stmt (use_stmt
);
1217 maybe_clean_or_replace_eh_stmt (use_stmt
, use_stmt
);
1221 /* Propagate constant SSA_NAMEs defined in basic block BB. */
1224 propagate_constants_for_unrolling (basic_block bb
)
1226 /* Look for degenerate PHI nodes with constant argument. */
1227 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); )
1229 gphi
*phi
= gsi
.phi ();
1230 tree result
= gimple_phi_result (phi
);
1231 tree arg
= gimple_phi_arg_def (phi
, 0);
1233 if (gimple_phi_num_args (phi
) == 1 && TREE_CODE (arg
) == INTEGER_CST
)
1235 propagate_into_all_uses (result
, arg
);
1236 gsi_remove (&gsi
, true);
1237 release_ssa_name (result
);
1243 /* Look for assignments to SSA names with constant RHS. */
1244 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
1246 gimple stmt
= gsi_stmt (gsi
);
1249 if (is_gimple_assign (stmt
)
1250 && gimple_assign_rhs_code (stmt
) == INTEGER_CST
1251 && (lhs
= gimple_assign_lhs (stmt
), TREE_CODE (lhs
) == SSA_NAME
)
1252 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1254 propagate_into_all_uses (lhs
, gimple_assign_rhs1 (stmt
));
1255 gsi_remove (&gsi
, true);
1256 release_ssa_name (lhs
);
1263 /* Process loops from innermost to outer, stopping at the innermost
1264 loop we unrolled. */
1267 tree_unroll_loops_completely_1 (bool may_increase_size
, bool unroll_outer
,
1268 vec
<loop_p
, va_heap
>& father_stack
,
1271 struct loop
*loop_father
;
1272 bool changed
= false;
1274 enum unroll_level ul
;
1276 /* Process inner loops first. */
1277 for (inner
= loop
->inner
; inner
!= NULL
; inner
= inner
->next
)
1278 changed
|= tree_unroll_loops_completely_1 (may_increase_size
,
1279 unroll_outer
, father_stack
,
1282 /* If we changed an inner loop we cannot process outer loops in this
1283 iteration because SSA form is not up-to-date. Continue with
1284 siblings of outer loops instead. */
1288 /* Don't unroll #pragma omp simd loops until the vectorizer
1289 attempts to vectorize those. */
1290 if (loop
->force_vectorize
)
1293 /* Try to unroll this loop. */
1294 loop_father
= loop_outer (loop
);
1298 if (may_increase_size
&& optimize_loop_nest_for_speed_p (loop
)
1299 /* Unroll outermost loops only if asked to do so or they do
1300 not cause code growth. */
1301 && (unroll_outer
|| loop_outer (loop_father
)))
1306 if (canonicalize_loop_induction_variables
1307 (loop
, false, ul
, !flag_tree_loop_ivcanon
))
1309 /* If we'll continue unrolling, we need to propagate constants
1310 within the new basic blocks to fold away induction variable
1311 computations; otherwise, the size might blow up before the
1312 iteration is complete and the IR eventually cleaned up. */
1313 if (loop_outer (loop_father
) && !loop_father
->aux
)
1315 father_stack
.safe_push (loop_father
);
1316 loop_father
->aux
= loop_father
;
1325 /* Unroll LOOPS completely if they iterate just few times. Unless
1326 MAY_INCREASE_SIZE is true, perform the unrolling only if the
1327 size of the code does not increase. */
1330 tree_unroll_loops_completely (bool may_increase_size
, bool unroll_outer
)
1332 auto_vec
<loop_p
, 16> father_stack
;
1335 bool irred_invalidated
= false;
1340 bitmap loop_closed_ssa_invalidated
= NULL
;
1342 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1343 loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
1345 free_numbers_of_iterations_estimates ();
1346 estimate_numbers_of_iterations ();
1348 changed
= tree_unroll_loops_completely_1 (may_increase_size
,
1349 unroll_outer
, father_stack
,
1350 current_loops
->tree_root
);
1356 /* Be sure to skip unlooped loops while procesing father_stack
1358 FOR_EACH_VEC_ELT (loops_to_unloop
, i
, iter
)
1359 (*iter
)->aux
= NULL
;
1360 FOR_EACH_VEC_ELT (father_stack
, i
, iter
)
1363 unloop_loops (loop_closed_ssa_invalidated
, &irred_invalidated
);
1365 /* We can not use TODO_update_ssa_no_phi because VOPS gets confused. */
1366 if (loop_closed_ssa_invalidated
1367 && !bitmap_empty_p (loop_closed_ssa_invalidated
))
1368 rewrite_into_loop_closed_ssa (loop_closed_ssa_invalidated
,
1371 update_ssa (TODO_update_ssa
);
1373 /* Propagate the constants within the new basic blocks. */
1374 FOR_EACH_VEC_ELT (father_stack
, i
, iter
)
1378 basic_block
*body
= get_loop_body_in_dom_order (*iter
);
1379 for (j
= 0; j
< (*iter
)->num_nodes
; j
++)
1380 propagate_constants_for_unrolling (body
[j
]);
1382 (*iter
)->aux
= NULL
;
1384 father_stack
.truncate (0);
1386 /* This will take care of removing completely unrolled loops
1387 from the loop structures so we can continue unrolling now
1389 if (cleanup_tree_cfg ())
1390 update_ssa (TODO_update_ssa_only_virtuals
);
1392 /* Clean up the information about numbers of iterations, since
1393 complete unrolling might have invalidated it. */
1395 #ifdef ENABLE_CHECKING
1396 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1397 verify_loop_closed_ssa (true);
1400 if (loop_closed_ssa_invalidated
)
1401 BITMAP_FREE (loop_closed_ssa_invalidated
);
1404 && ++iteration
<= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS
));
1406 father_stack
.release ();
1408 if (irred_invalidated
1409 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1410 mark_irreducible_loops ();
1415 /* Canonical induction variable creation pass. */
1419 const pass_data pass_data_iv_canon
=
1421 GIMPLE_PASS
, /* type */
1422 "ivcanon", /* name */
1423 OPTGROUP_LOOP
, /* optinfo_flags */
1424 TV_TREE_LOOP_IVCANON
, /* tv_id */
1425 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1426 0, /* properties_provided */
1427 0, /* properties_destroyed */
1428 0, /* todo_flags_start */
1429 0, /* todo_flags_finish */
1432 class pass_iv_canon
: public gimple_opt_pass
1435 pass_iv_canon (gcc::context
*ctxt
)
1436 : gimple_opt_pass (pass_data_iv_canon
, ctxt
)
1439 /* opt_pass methods: */
1440 virtual bool gate (function
*) { return flag_tree_loop_ivcanon
!= 0; }
1441 virtual unsigned int execute (function
*fun
);
1443 }; // class pass_iv_canon
1446 pass_iv_canon::execute (function
*fun
)
1448 if (number_of_loops (fun
) <= 1)
1451 return canonicalize_induction_variables ();
1457 make_pass_iv_canon (gcc::context
*ctxt
)
1459 return new pass_iv_canon (ctxt
);
1462 /* Complete unrolling of loops. */
1466 const pass_data pass_data_complete_unroll
=
1468 GIMPLE_PASS
, /* type */
1469 "cunroll", /* name */
1470 OPTGROUP_LOOP
, /* optinfo_flags */
1471 TV_COMPLETE_UNROLL
, /* tv_id */
1472 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1473 0, /* properties_provided */
1474 0, /* properties_destroyed */
1475 0, /* todo_flags_start */
1476 0, /* todo_flags_finish */
1479 class pass_complete_unroll
: public gimple_opt_pass
1482 pass_complete_unroll (gcc::context
*ctxt
)
1483 : gimple_opt_pass (pass_data_complete_unroll
, ctxt
)
1486 /* opt_pass methods: */
1487 virtual unsigned int execute (function
*);
1489 }; // class pass_complete_unroll
1492 pass_complete_unroll::execute (function
*fun
)
1494 if (number_of_loops (fun
) <= 1)
1497 return tree_unroll_loops_completely (flag_unroll_loops
1499 || optimize
>= 3, true);
1505 make_pass_complete_unroll (gcc::context
*ctxt
)
1507 return new pass_complete_unroll (ctxt
);
1510 /* Complete unrolling of inner loops. */
1514 const pass_data pass_data_complete_unrolli
=
1516 GIMPLE_PASS
, /* type */
1517 "cunrolli", /* name */
1518 OPTGROUP_LOOP
, /* optinfo_flags */
1519 TV_COMPLETE_UNROLL
, /* tv_id */
1520 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1521 0, /* properties_provided */
1522 0, /* properties_destroyed */
1523 0, /* todo_flags_start */
1524 0, /* todo_flags_finish */
1527 class pass_complete_unrolli
: public gimple_opt_pass
1530 pass_complete_unrolli (gcc::context
*ctxt
)
1531 : gimple_opt_pass (pass_data_complete_unrolli
, ctxt
)
1534 /* opt_pass methods: */
1535 virtual bool gate (function
*) { return optimize
>= 2; }
1536 virtual unsigned int execute (function
*);
1538 }; // class pass_complete_unrolli
1541 pass_complete_unrolli::execute (function
*fun
)
1545 loop_optimizer_init (LOOPS_NORMAL
1546 | LOOPS_HAVE_RECORDED_EXITS
);
1547 if (number_of_loops (fun
) > 1)
1550 ret
= tree_unroll_loops_completely (optimize
>= 3, false);
1551 free_numbers_of_iterations_estimates ();
1554 loop_optimizer_finalize ();
1562 make_pass_complete_unrolli (gcc::context
*ctxt
)
1564 return new pass_complete_unrolli (ctxt
);