1 /* Induction variable canonicalization and loop peeling.
2 Copyright (C) 2004-2014 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 - complette 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 "basic-block.h"
46 #include "gimple-pretty-print.h"
47 #include "tree-ssa-alias.h"
48 #include "internal-fn.h"
49 #include "gimple-fold.h"
51 #include "gimple-expr.h"
54 #include "gimple-iterator.h"
55 #include "gimple-ssa.h"
58 #include "tree-phinodes.h"
59 #include "ssa-iterators.h"
60 #include "stringpool.h"
61 #include "tree-ssanames.h"
62 #include "tree-ssa-loop-manip.h"
63 #include "tree-ssa-loop-niter.h"
64 #include "tree-ssa-loop.h"
65 #include "tree-into-ssa.h"
67 #include "tree-pass.h"
68 #include "tree-chrec.h"
69 #include "tree-scalar-evolution.h"
72 #include "tree-inline.h"
74 #include "tree-cfgcleanup.h"
77 /* Specifies types of loops that may be unrolled. */
81 UL_SINGLE_ITER
, /* Only loops that exit immediately in the first
83 UL_NO_GROWTH
, /* Only loops whose unrolling will not cause increase
85 UL_ALL
/* All suitable loops. */
88 /* Adds a canonical induction variable to LOOP iterating NITER times. EXIT
89 is the exit edge whose condition is replaced. */
92 create_canonical_iv (struct loop
*loop
, edge exit
, tree niter
)
97 gimple_stmt_iterator incr_at
;
100 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
102 fprintf (dump_file
, "Added canonical iv to loop %d, ", loop
->num
);
103 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
104 fprintf (dump_file
, " iterations.\n");
107 cond
= last_stmt (exit
->src
);
108 in
= EDGE_SUCC (exit
->src
, 0);
110 in
= EDGE_SUCC (exit
->src
, 1);
112 /* Note that we do not need to worry about overflows, since
113 type of niter is always unsigned and all comparisons are
114 just for equality/nonequality -- i.e. everything works
115 with a modulo arithmetics. */
117 type
= TREE_TYPE (niter
);
118 niter
= fold_build2 (PLUS_EXPR
, type
,
120 build_int_cst (type
, 1));
121 incr_at
= gsi_last_bb (in
->src
);
123 build_int_cst (type
, -1),
125 &incr_at
, false, NULL
, &var
);
127 cmp
= (exit
->flags
& EDGE_TRUE_VALUE
) ? EQ_EXPR
: NE_EXPR
;
128 gimple_cond_set_code (cond
, cmp
);
129 gimple_cond_set_lhs (cond
, var
);
130 gimple_cond_set_rhs (cond
, build_int_cst (type
, 0));
134 /* Describe size of loop as detected by tree_estimate_loop_size. */
137 /* Number of instructions in the loop. */
140 /* Number of instructions that will be likely optimized out in
141 peeled iterations of loop (i.e. computation based on induction
142 variable where induction variable starts at known constant.) */
143 int eliminated_by_peeling
;
145 /* Same statistics for last iteration of loop: it is smaller because
146 instructions after exit are not executed. */
148 int last_iteration_eliminated_by_peeling
;
150 /* If some IV computation will become constant. */
153 /* Number of call stmts that are not a builtin and are pure or const
154 present on the hot path. */
155 int num_pure_calls_on_hot_path
;
156 /* Number of call stmts that are not a builtin and are not pure nor const
157 present on the hot path. */
158 int num_non_pure_calls_on_hot_path
;
159 /* Number of statements other than calls in the loop. */
160 int non_call_stmts_on_hot_path
;
161 /* Number of branches seen on the hot path. */
162 int num_branches_on_hot_path
;
165 /* Return true if OP in STMT will be constant after peeling LOOP. */
168 constant_after_peeling (tree op
, gimple stmt
, struct loop
*loop
)
172 if (is_gimple_min_invariant (op
))
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. */
202 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op
, &iv
, false))
204 if (!is_gimple_min_invariant (iv
.base
))
206 if (!is_gimple_min_invariant (iv
.step
))
211 /* Computes an estimated number of insns in LOOP.
212 EXIT (if non-NULL) is an exite edge that will be eliminated in all but last
213 iteration of the loop.
214 EDGE_TO_CANCEL (if non-NULL) is an non-exit edge eliminated in the last iteration
216 Return results in SIZE, estimate benefits for complete unrolling exiting by EXIT.
217 Stop estimating after UPPER_BOUND is met. Return true in this case. */
220 tree_estimate_loop_size (struct loop
*loop
, edge exit
, edge edge_to_cancel
, struct loop_size
*size
,
223 basic_block
*body
= get_loop_body (loop
);
224 gimple_stmt_iterator gsi
;
227 vec
<basic_block
> path
= get_loop_hot_path (loop
);
230 size
->eliminated_by_peeling
= 0;
231 size
->last_iteration
= 0;
232 size
->last_iteration_eliminated_by_peeling
= 0;
233 size
->num_pure_calls_on_hot_path
= 0;
234 size
->num_non_pure_calls_on_hot_path
= 0;
235 size
->non_call_stmts_on_hot_path
= 0;
236 size
->num_branches_on_hot_path
= 0;
237 size
->constant_iv
= 0;
239 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
240 fprintf (dump_file
, "Estimating sizes for loop %i\n", loop
->num
);
241 for (i
= 0; i
< loop
->num_nodes
; i
++)
243 if (edge_to_cancel
&& body
[i
] != edge_to_cancel
->src
244 && dominated_by_p (CDI_DOMINATORS
, body
[i
], edge_to_cancel
->src
))
248 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
249 fprintf (dump_file
, " BB: %i, after_exit: %i\n", body
[i
]->index
, after_exit
);
251 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
253 gimple stmt
= gsi_stmt (gsi
);
254 int num
= estimate_num_insns (stmt
, &eni_size_weights
);
255 bool likely_eliminated
= false;
256 bool likely_eliminated_last
= false;
257 bool likely_eliminated_peeled
= false;
259 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
261 fprintf (dump_file
, " size: %3i ", num
);
262 print_gimple_stmt (dump_file
, gsi_stmt (gsi
), 0, 0);
265 /* Look for reasons why we might optimize this stmt away. */
267 if (gimple_has_side_effects (stmt
))
269 /* Exit conditional. */
270 else if (exit
&& body
[i
] == exit
->src
271 && stmt
== last_stmt (exit
->src
))
273 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
274 fprintf (dump_file
, " Exit condition will be eliminated "
275 "in peeled copies.\n");
276 likely_eliminated_peeled
= true;
278 else if (edge_to_cancel
&& body
[i
] == edge_to_cancel
->src
279 && stmt
== last_stmt (edge_to_cancel
->src
))
281 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
282 fprintf (dump_file
, " Exit condition will be eliminated "
284 likely_eliminated_last
= true;
286 /* Sets of IV variables */
287 else if (gimple_code (stmt
) == GIMPLE_ASSIGN
288 && constant_after_peeling (gimple_assign_lhs (stmt
), stmt
, loop
))
290 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
291 fprintf (dump_file
, " Induction variable computation will"
292 " be folded away.\n");
293 likely_eliminated
= true;
295 /* Assignments of IV variables. */
296 else if (gimple_code (stmt
) == GIMPLE_ASSIGN
297 && TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
298 && constant_after_peeling (gimple_assign_rhs1 (stmt
), stmt
, loop
)
299 && (gimple_assign_rhs_class (stmt
) != GIMPLE_BINARY_RHS
300 || constant_after_peeling (gimple_assign_rhs2 (stmt
),
303 size
->constant_iv
= true;
304 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
305 fprintf (dump_file
, " Constant expression will be folded away.\n");
306 likely_eliminated
= true;
309 else if ((gimple_code (stmt
) == GIMPLE_COND
310 && constant_after_peeling (gimple_cond_lhs (stmt
), stmt
, loop
)
311 && constant_after_peeling (gimple_cond_rhs (stmt
), stmt
, loop
))
312 || (gimple_code (stmt
) == GIMPLE_SWITCH
313 && constant_after_peeling (gimple_switch_index (stmt
), stmt
, loop
)))
315 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
316 fprintf (dump_file
, " Constant conditional.\n");
317 likely_eliminated
= true;
320 size
->overall
+= num
;
321 if (likely_eliminated
|| likely_eliminated_peeled
)
322 size
->eliminated_by_peeling
+= num
;
325 size
->last_iteration
+= num
;
326 if (likely_eliminated
|| likely_eliminated_last
)
327 size
->last_iteration_eliminated_by_peeling
+= num
;
329 if ((size
->overall
* 3 / 2 - size
->eliminated_by_peeling
330 - size
->last_iteration_eliminated_by_peeling
) > upper_bound
)
338 while (path
.length ())
340 basic_block bb
= path
.pop ();
341 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
343 gimple stmt
= gsi_stmt (gsi
);
344 if (gimple_code (stmt
) == GIMPLE_CALL
)
346 int flags
= gimple_call_flags (stmt
);
347 tree decl
= gimple_call_fndecl (stmt
);
349 if (decl
&& DECL_IS_BUILTIN (decl
)
350 && is_inexpensive_builtin (decl
))
352 else if (flags
& (ECF_PURE
| ECF_CONST
))
353 size
->num_pure_calls_on_hot_path
++;
355 size
->num_non_pure_calls_on_hot_path
++;
356 size
->num_branches_on_hot_path
++;
358 else if (gimple_code (stmt
) != GIMPLE_CALL
359 && gimple_code (stmt
) != GIMPLE_DEBUG
)
360 size
->non_call_stmts_on_hot_path
++;
361 if (((gimple_code (stmt
) == GIMPLE_COND
362 && (!constant_after_peeling (gimple_cond_lhs (stmt
), stmt
, loop
)
363 || constant_after_peeling (gimple_cond_rhs (stmt
), stmt
, loop
)))
364 || (gimple_code (stmt
) == GIMPLE_SWITCH
365 && !constant_after_peeling (gimple_switch_index (stmt
), stmt
, loop
)))
366 && (!exit
|| bb
!= exit
->src
))
367 size
->num_branches_on_hot_path
++;
371 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
372 fprintf (dump_file
, "size: %i-%i, last_iteration: %i-%i\n", size
->overall
,
373 size
->eliminated_by_peeling
, size
->last_iteration
,
374 size
->last_iteration_eliminated_by_peeling
);
380 /* Estimate number of insns of completely unrolled loop.
381 It is (NUNROLL + 1) * size of loop body with taking into account
382 the fact that in last copy everything after exit conditional
383 is dead and that some instructions will be eliminated after
386 Loop body is likely going to simplify further, this is difficult
387 to guess, we just decrease the result by 1/3. */
389 static unsigned HOST_WIDE_INT
390 estimated_unrolled_size (struct loop_size
*size
,
391 unsigned HOST_WIDE_INT nunroll
)
393 HOST_WIDE_INT unr_insns
= ((nunroll
)
394 * (HOST_WIDE_INT
) (size
->overall
395 - size
->eliminated_by_peeling
));
398 unr_insns
+= size
->last_iteration
- size
->last_iteration_eliminated_by_peeling
;
400 unr_insns
= unr_insns
* 2 / 3;
407 /* Loop LOOP is known to not loop. See if there is an edge in the loop
408 body that can be remove to make the loop to always exit and at
409 the same time it does not make any code potentially executed
410 during the last iteration dead.
412 After complette unrolling we still may get rid of the conditional
413 on the exit in the last copy even if we have no idea what it does.
414 This is quite common case for loops of form
420 Here we prove the loop to iterate 5 times but we do not know
421 it from induction variable.
423 For now we handle only simple case where there is exit condition
424 just before the latch block and the latch block contains no statements
425 with side effect that may otherwise terminate the execution of loop
426 (such as by EH or by terminating the program or longjmp).
428 In the general case we may want to cancel the paths leading to statements
429 loop-niter identified as having undefined effect in the last iteration.
430 The other cases are hopefully rare and will be cleaned up later. */
433 loop_edge_to_cancel (struct loop
*loop
)
438 gimple_stmt_iterator gsi
;
440 /* We want only one predecestor of the loop. */
441 if (EDGE_COUNT (loop
->latch
->preds
) > 1)
444 exits
= get_loop_exit_edges (loop
);
446 FOR_EACH_VEC_ELT (exits
, i
, edge_to_cancel
)
448 /* Find the other edge than the loop exit
449 leaving the conditoinal. */
450 if (EDGE_COUNT (edge_to_cancel
->src
->succs
) != 2)
452 if (EDGE_SUCC (edge_to_cancel
->src
, 0) == edge_to_cancel
)
453 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 1);
455 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 0);
457 /* We only can handle conditionals. */
458 if (!(edge_to_cancel
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
461 /* We should never have conditionals in the loop latch. */
462 gcc_assert (edge_to_cancel
->dest
!= loop
->header
);
464 /* Check that it leads to loop latch. */
465 if (edge_to_cancel
->dest
!= loop
->latch
)
470 /* Verify that the code in loop latch does nothing that may end program
471 execution without really reaching the exit. This may include
472 non-pure/const function calls, EH statements, volatile ASMs etc. */
473 for (gsi
= gsi_start_bb (loop
->latch
); !gsi_end_p (gsi
); gsi_next (&gsi
))
474 if (gimple_has_side_effects (gsi_stmt (gsi
)))
476 return edge_to_cancel
;
482 /* Remove all tests for exits that are known to be taken after LOOP was
483 peeled NPEELED times. Put gcc_unreachable before every statement
484 known to not be executed. */
487 remove_exits_and_undefined_stmts (struct loop
*loop
, unsigned int npeeled
)
489 struct nb_iter_bound
*elt
;
490 bool changed
= false;
492 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
494 /* If statement is known to be undefined after peeling, turn it
495 into unreachable (or trap when debugging experience is supposed
498 && wi::ltu_p (elt
->bound
, npeeled
))
500 gimple_stmt_iterator gsi
= gsi_for_stmt (elt
->stmt
);
501 gimple stmt
= gimple_build_call
502 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
), 0);
504 gimple_set_location (stmt
, gimple_location (elt
->stmt
));
505 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
507 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
509 fprintf (dump_file
, "Forced statement unreachable: ");
510 print_gimple_stmt (dump_file
, elt
->stmt
, 0, 0);
513 /* If we know the exit will be taken after peeling, update. */
514 else if (elt
->is_exit
515 && wi::leu_p (elt
->bound
, npeeled
))
517 basic_block bb
= gimple_bb (elt
->stmt
);
518 edge exit_edge
= EDGE_SUCC (bb
, 0);
520 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
522 fprintf (dump_file
, "Forced exit to be taken: ");
523 print_gimple_stmt (dump_file
, elt
->stmt
, 0, 0);
525 if (!loop_exit_edge_p (loop
, exit_edge
))
526 exit_edge
= EDGE_SUCC (bb
, 1);
527 gcc_checking_assert (loop_exit_edge_p (loop
, exit_edge
));
528 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
529 gimple_cond_make_true (elt
->stmt
);
531 gimple_cond_make_false (elt
->stmt
);
532 update_stmt (elt
->stmt
);
539 /* Remove all exits that are known to be never taken because of the loop bound
543 remove_redundant_iv_tests (struct loop
*loop
)
545 struct nb_iter_bound
*elt
;
546 bool changed
= false;
548 if (!loop
->any_upper_bound
)
550 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
552 /* Exit is pointless if it won't be taken before loop reaches
554 if (elt
->is_exit
&& loop
->any_upper_bound
555 && wi::ltu_p (loop
->nb_iterations_upper_bound
, elt
->bound
))
557 basic_block bb
= gimple_bb (elt
->stmt
);
558 edge exit_edge
= EDGE_SUCC (bb
, 0);
559 struct tree_niter_desc niter
;
561 if (!loop_exit_edge_p (loop
, exit_edge
))
562 exit_edge
= EDGE_SUCC (bb
, 1);
564 /* Only when we know the actual number of iterations, not
565 just a bound, we can remove the exit. */
566 if (!number_of_iterations_exit (loop
, exit_edge
,
567 &niter
, false, false)
568 || !integer_onep (niter
.assumptions
)
569 || !integer_zerop (niter
.may_be_zero
)
571 || TREE_CODE (niter
.niter
) != INTEGER_CST
572 || !wi::ltu_p (loop
->nb_iterations_upper_bound
,
573 wi::to_widest (niter
.niter
)))
576 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
578 fprintf (dump_file
, "Removed pointless exit: ");
579 print_gimple_stmt (dump_file
, elt
->stmt
, 0, 0);
581 if (exit_edge
->flags
& EDGE_TRUE_VALUE
)
582 gimple_cond_make_false (elt
->stmt
);
584 gimple_cond_make_true (elt
->stmt
);
585 update_stmt (elt
->stmt
);
592 /* Stores loops that will be unlooped after we process whole loop tree. */
593 static vec
<loop_p
> loops_to_unloop
;
594 static vec
<int> loops_to_unloop_nunroll
;
596 /* Cancel all fully unrolled loops by putting __builtin_unreachable
598 We do it after all unrolling since unlooping moves basic blocks
599 across loop boundaries trashing loop closed SSA form as well
600 as SCEV info needed to be intact during unrolling.
602 IRRED_INVALIDATED is used to bookkeep if information about
603 irreducible regions may become invalid as a result
604 of the transformation.
605 LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case
606 when we need to go into loop closed SSA form. */
609 unloop_loops (bitmap loop_closed_ssa_invalidated
,
610 bool *irred_invalidated
)
612 while (loops_to_unloop
.length ())
614 struct loop
*loop
= loops_to_unloop
.pop ();
615 int n_unroll
= loops_to_unloop_nunroll
.pop ();
616 basic_block latch
= loop
->latch
;
617 edge latch_edge
= loop_latch_edge (loop
);
618 int flags
= latch_edge
->flags
;
619 location_t locus
= latch_edge
->goto_locus
;
621 gimple_stmt_iterator gsi
;
623 remove_exits_and_undefined_stmts (loop
, n_unroll
);
625 /* Unloop destroys the latch edge. */
626 unloop (loop
, irred_invalidated
, loop_closed_ssa_invalidated
);
628 /* Create new basic block for the latch edge destination and wire
630 stmt
= gimple_build_call (builtin_decl_implicit (BUILT_IN_UNREACHABLE
), 0);
631 latch_edge
= make_edge (latch
, create_basic_block (NULL
, NULL
, latch
), flags
);
632 latch_edge
->probability
= 0;
633 latch_edge
->count
= 0;
634 latch_edge
->flags
|= flags
;
635 latch_edge
->goto_locus
= locus
;
637 latch_edge
->dest
->loop_father
= current_loops
->tree_root
;
638 latch_edge
->dest
->count
= 0;
639 latch_edge
->dest
->frequency
= 0;
640 set_immediate_dominator (CDI_DOMINATORS
, latch_edge
->dest
, latch_edge
->src
);
642 gsi
= gsi_start_bb (latch_edge
->dest
);
643 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
645 loops_to_unloop
.release ();
646 loops_to_unloop_nunroll
.release ();
649 /* Tries to unroll LOOP completely, i.e. NITER times.
650 UL determines which loops we are allowed to unroll.
651 EXIT is the exit of the loop that should be eliminated.
652 MAXITER specfy bound on number of iterations, -1 if it is
653 not known or too large for HOST_WIDE_INT. The location
654 LOCUS corresponding to the loop is used when emitting
655 a summary of the unroll to the dump file. */
658 try_unroll_loop_completely (struct loop
*loop
,
659 edge exit
, tree niter
,
660 enum unroll_level ul
,
661 HOST_WIDE_INT maxiter
,
664 unsigned HOST_WIDE_INT n_unroll
= 0, ninsns
, max_unroll
, unr_insns
;
666 struct loop_size size
;
667 bool n_unroll_found
= false;
668 edge edge_to_cancel
= NULL
;
669 int report_flags
= MSG_OPTIMIZED_LOCATIONS
| TDF_RTL
| TDF_DETAILS
;
671 /* See if we proved number of iterations to be low constant.
673 EXIT is an edge that will be removed in all but last iteration of
676 EDGE_TO_CACNEL is an edge that will be removed from the last iteration
677 of the unrolled sequence and is expected to make the final loop not
680 If the number of execution of loop is determined by standard induction
681 variable test, then EXIT and EDGE_TO_CANCEL are the two edges leaving
683 if (tree_fits_uhwi_p (niter
))
685 n_unroll
= tree_to_uhwi (niter
);
686 n_unroll_found
= true;
687 edge_to_cancel
= EDGE_SUCC (exit
->src
, 0);
688 if (edge_to_cancel
== exit
)
689 edge_to_cancel
= EDGE_SUCC (exit
->src
, 1);
691 /* We do not know the number of iterations and thus we can not eliminate
696 /* See if we can improve our estimate by using recorded loop bounds. */
698 && (!n_unroll_found
|| (unsigned HOST_WIDE_INT
)maxiter
< n_unroll
))
701 n_unroll_found
= true;
702 /* Loop terminates before the IV variable test, so we can not
703 remove it in the last iteration. */
704 edge_to_cancel
= NULL
;
710 max_unroll
= PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
);
711 if (n_unroll
> max_unroll
)
715 edge_to_cancel
= loop_edge_to_cancel (loop
);
723 vec
<edge
> to_remove
= vNULL
;
724 if (ul
== UL_SINGLE_ITER
)
727 large
= tree_estimate_loop_size
728 (loop
, exit
, edge_to_cancel
, &size
,
729 PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
));
730 ninsns
= size
.overall
;
733 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
734 fprintf (dump_file
, "Not unrolling loop %d: it is too large.\n",
739 unr_insns
= estimated_unrolled_size (&size
, n_unroll
);
740 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
742 fprintf (dump_file
, " Loop size: %d\n", (int) ninsns
);
743 fprintf (dump_file
, " Estimated size after unrolling: %d\n",
747 /* If the code is going to shrink, we don't need to be extra cautious
748 on guessing if the unrolling is going to be profitable. */
750 /* If there is IV variable that will become constant, we save
751 one instruction in the loop prologue we do not account
753 <= ninsns
+ (size
.constant_iv
!= false))
755 /* We unroll only inner loops, because we do not consider it profitable
756 otheriwse. We still can cancel loopback edge of not rolling loop;
757 this is always a good idea. */
758 else if (ul
== UL_NO_GROWTH
)
760 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
761 fprintf (dump_file
, "Not unrolling loop %d: size would grow.\n",
765 /* Outer loops tend to be less interesting candidates for complette
766 unrolling unless we can do a lot of propagation into the inner loop
767 body. For now we disable outer loop unrolling when the code would
769 else if (loop
->inner
)
771 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
772 fprintf (dump_file
, "Not unrolling loop %d: "
773 "it is not innermost and code would grow.\n",
777 /* If there is call on a hot path through the loop, then
778 there is most probably not much to optimize. */
779 else if (size
.num_non_pure_calls_on_hot_path
)
781 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
782 fprintf (dump_file
, "Not unrolling loop %d: "
783 "contains call and code would grow.\n",
787 /* If there is pure/const call in the function, then we
788 can still optimize the unrolled loop body if it contains
789 some other interesting code than the calls and code
790 storing or cumulating the return value. */
791 else if (size
.num_pure_calls_on_hot_path
792 /* One IV increment, one test, one ivtmp store
793 and one useful stmt. That is about minimal loop
795 && (size
.non_call_stmts_on_hot_path
796 <= 3 + size
.num_pure_calls_on_hot_path
))
798 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
799 fprintf (dump_file
, "Not unrolling loop %d: "
800 "contains just pure calls and code would grow.\n",
804 /* Complette unrolling is major win when control flow is removed and
805 one big basic block is created. If the loop contains control flow
806 the optimization may still be a win because of eliminating the loop
807 overhead but it also may blow the branch predictor tables.
808 Limit number of branches on the hot path through the peeled
810 else if (size
.num_branches_on_hot_path
* (int)n_unroll
811 > PARAM_VALUE (PARAM_MAX_PEEL_BRANCHES
))
813 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
814 fprintf (dump_file
, "Not unrolling loop %d: "
815 " number of branches on hot path in the unrolled sequence"
816 " reach --param max-peel-branches limit.\n",
821 > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
))
823 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
824 fprintf (dump_file
, "Not unrolling loop %d: "
825 "(--param max-completely-peeled-insns limit reached).\n",
829 dump_printf_loc (report_flags
, locus
,
830 "loop turned into non-loop; it never loops.\n");
832 initialize_original_copy_tables ();
833 wont_exit
= sbitmap_alloc (n_unroll
+ 1);
834 bitmap_ones (wont_exit
);
835 bitmap_clear_bit (wont_exit
, 0);
837 if (!gimple_duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
840 DLTHE_FLAG_UPDATE_FREQ
841 | DLTHE_FLAG_COMPLETTE_PEEL
))
843 free_original_copy_tables ();
845 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
846 fprintf (dump_file
, "Failed to duplicate the loop\n");
850 FOR_EACH_VEC_ELT (to_remove
, i
, e
)
852 bool ok
= remove_path (e
);
856 to_remove
.release ();
858 free_original_copy_tables ();
862 /* Remove the conditional from the last copy of the loop. */
865 cond
= last_stmt (edge_to_cancel
->src
);
866 if (edge_to_cancel
->flags
& EDGE_TRUE_VALUE
)
867 gimple_cond_make_false (cond
);
869 gimple_cond_make_true (cond
);
871 /* Do not remove the path. Doing so may remove outer loop
872 and confuse bookkeeping code in tree_unroll_loops_completelly. */
875 /* Store the loop for later unlooping and exit removal. */
876 loops_to_unloop
.safe_push (loop
);
877 loops_to_unloop_nunroll
.safe_push (n_unroll
);
879 if (dump_enabled_p ())
882 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
883 "loop turned into non-loop; it never loops\n");
886 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, locus
,
887 "loop with %d iterations completely unrolled",
888 (int) (n_unroll
+ 1));
890 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
,
891 " (header execution count %d)",
892 (int)loop
->header
->count
);
893 dump_printf (MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
, "\n");
897 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
900 fprintf (dump_file
, "Exit condition of peeled iterations was "
903 fprintf (dump_file
, "Last iteration exit edge was proved true.\n");
905 fprintf (dump_file
, "Latch of last iteration was marked by "
906 "__builtin_unreachable ().\n");
912 /* Return number of instructions after peeling. */
913 static unsigned HOST_WIDE_INT
914 estimated_peeled_sequence_size (struct loop_size
*size
,
915 unsigned HOST_WIDE_INT npeel
)
917 return MAX (npeel
* (HOST_WIDE_INT
) (size
->overall
918 - size
->eliminated_by_peeling
), 1);
921 /* If the loop is expected to iterate N times and is
922 small enough, duplicate the loop body N+1 times before
923 the loop itself. This way the hot path will never
925 Parameters are the same as for try_unroll_loops_completely */
928 try_peel_loop (struct loop
*loop
,
929 edge exit
, tree niter
,
930 HOST_WIDE_INT maxiter
)
933 struct loop_size size
;
937 vec
<edge
> to_remove
= vNULL
;
940 /* If the iteration bound is known and large, then we can safely eliminate
941 the check in peeled copies. */
942 if (TREE_CODE (niter
) != INTEGER_CST
)
945 if (!flag_peel_loops
|| PARAM_VALUE (PARAM_MAX_PEEL_TIMES
) <= 0)
948 /* Peel only innermost loops. */
952 fprintf (dump_file
, "Not peeling: outer loop\n");
956 if (!optimize_loop_for_speed_p (loop
))
959 fprintf (dump_file
, "Not peeling: cold loop\n");
963 /* Check if there is an estimate on the number of iterations. */
964 npeel
= estimated_loop_iterations_int (loop
);
968 fprintf (dump_file
, "Not peeling: number of iterations is not "
972 if (maxiter
>= 0 && maxiter
<= npeel
)
975 fprintf (dump_file
, "Not peeling: upper bound is known so can "
976 "unroll complettely\n");
980 /* We want to peel estimated number of iterations + 1 (so we never
981 enter the loop on quick path). Check against PARAM_MAX_PEEL_TIMES
982 and be sure to avoid overflows. */
983 if (npeel
> PARAM_VALUE (PARAM_MAX_PEEL_TIMES
) - 1)
986 fprintf (dump_file
, "Not peeling: rolls too much "
987 "(%i + 1 > --param max-peel-times)\n", npeel
);
992 /* Check peeled loops size. */
993 tree_estimate_loop_size (loop
, exit
, NULL
, &size
,
994 PARAM_VALUE (PARAM_MAX_PEELED_INSNS
));
995 if ((peeled_size
= estimated_peeled_sequence_size (&size
, npeel
))
996 > PARAM_VALUE (PARAM_MAX_PEELED_INSNS
))
999 fprintf (dump_file
, "Not peeling: peeled sequence size is too large "
1000 "(%i insns > --param max-peel-insns)", peeled_size
);
1004 /* Duplicate possibly eliminating the exits. */
1005 initialize_original_copy_tables ();
1006 wont_exit
= sbitmap_alloc (npeel
+ 1);
1007 bitmap_ones (wont_exit
);
1008 bitmap_clear_bit (wont_exit
, 0);
1009 if (!gimple_duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1012 DLTHE_FLAG_UPDATE_FREQ
1013 | DLTHE_FLAG_COMPLETTE_PEEL
))
1015 free_original_copy_tables ();
1019 FOR_EACH_VEC_ELT (to_remove
, i
, e
)
1021 bool ok
= remove_path (e
);
1025 free_original_copy_tables ();
1026 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1028 fprintf (dump_file
, "Peeled loop %d, %i times.\n",
1031 if (loop
->any_upper_bound
)
1032 loop
->nb_iterations_upper_bound
-= npeel
;
1033 loop
->nb_iterations_estimate
= 0;
1034 /* Make sure to mark loop cold so we do not try to peel it more. */
1035 scale_loop_profile (loop
, 1, 0);
1036 loop
->header
->count
= 0;
1039 /* Adds a canonical induction variable to LOOP if suitable.
1040 CREATE_IV is true if we may create a new iv. UL determines
1041 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
1042 to determine the number of iterations of a loop by direct evaluation.
1043 Returns true if cfg is changed. */
1046 canonicalize_loop_induction_variables (struct loop
*loop
,
1047 bool create_iv
, enum unroll_level ul
,
1052 HOST_WIDE_INT maxiter
;
1053 bool modified
= false;
1054 location_t locus
= UNKNOWN_LOCATION
;
1056 niter
= number_of_latch_executions (loop
);
1057 exit
= single_exit (loop
);
1058 if (TREE_CODE (niter
) == INTEGER_CST
)
1059 locus
= gimple_location (last_stmt (exit
->src
));
1062 /* If the loop has more than one exit, try checking all of them
1063 for # of iterations determinable through scev. */
1065 niter
= find_loop_niter (loop
, &exit
);
1067 /* Finally if everything else fails, try brute force evaluation. */
1069 && (chrec_contains_undetermined (niter
)
1070 || TREE_CODE (niter
) != INTEGER_CST
))
1071 niter
= find_loop_niter_by_eval (loop
, &exit
);
1074 locus
= gimple_location (last_stmt (exit
->src
));
1076 if (TREE_CODE (niter
) != INTEGER_CST
)
1080 /* We work exceptionally hard here to estimate the bound
1081 by find_loop_niter_by_eval. Be sure to keep it for future. */
1082 if (niter
&& TREE_CODE (niter
) == INTEGER_CST
)
1084 record_niter_bound (loop
, wi::to_widest (niter
),
1085 exit
== single_likely_exit (loop
), true);
1088 /* Force re-computation of loop bounds so we can remove redundant exits. */
1089 maxiter
= max_loop_iterations_int (loop
);
1091 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1092 && TREE_CODE (niter
) == INTEGER_CST
)
1094 fprintf (dump_file
, "Loop %d iterates ", loop
->num
);
1095 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1096 fprintf (dump_file
, " times.\n");
1098 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1101 fprintf (dump_file
, "Loop %d iterates at most %i times.\n", loop
->num
,
1105 /* Remove exits that are known to be never taken based on loop bound.
1106 Needs to be called after compilation of max_loop_iterations_int that
1107 populates the loop bounds. */
1108 modified
|= remove_redundant_iv_tests (loop
);
1110 if (try_unroll_loop_completely (loop
, exit
, niter
, ul
, maxiter
, locus
))
1114 && niter
&& !chrec_contains_undetermined (niter
)
1115 && exit
&& just_once_each_iteration_p (loop
, exit
->src
))
1116 create_canonical_iv (loop
, exit
, niter
);
1119 modified
|= try_peel_loop (loop
, exit
, niter
, maxiter
);
1124 /* The main entry point of the pass. Adds canonical induction variables
1125 to the suitable loops. */
1128 canonicalize_induction_variables (void)
1131 bool changed
= false;
1132 bool irred_invalidated
= false;
1133 bitmap loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
1135 free_numbers_of_iterations_estimates ();
1136 estimate_numbers_of_iterations ();
1138 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1140 changed
|= canonicalize_loop_induction_variables (loop
,
1141 true, UL_SINGLE_ITER
,
1144 gcc_assert (!need_ssa_update_p (cfun
));
1146 unloop_loops (loop_closed_ssa_invalidated
, &irred_invalidated
);
1147 if (irred_invalidated
1148 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1149 mark_irreducible_loops ();
1151 /* Clean up the information about numbers of iterations, since brute force
1152 evaluation could reveal new information. */
1155 if (!bitmap_empty_p (loop_closed_ssa_invalidated
))
1157 gcc_checking_assert (loops_state_satisfies_p (LOOP_CLOSED_SSA
));
1158 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1160 BITMAP_FREE (loop_closed_ssa_invalidated
);
1163 return TODO_cleanup_cfg
;
1167 /* Propagate VAL into all uses of SSA_NAME. */
1170 propagate_into_all_uses (tree ssa_name
, tree val
)
1172 imm_use_iterator iter
;
1175 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, ssa_name
)
1177 gimple_stmt_iterator use_stmt_gsi
= gsi_for_stmt (use_stmt
);
1180 FOR_EACH_IMM_USE_ON_STMT (use
, iter
)
1183 if (is_gimple_assign (use_stmt
)
1184 && get_gimple_rhs_class (gimple_assign_rhs_code (use_stmt
))
1185 == GIMPLE_SINGLE_RHS
)
1187 tree rhs
= gimple_assign_rhs1 (use_stmt
);
1189 if (TREE_CODE (rhs
) == ADDR_EXPR
)
1190 recompute_tree_invariant_for_addr_expr (rhs
);
1193 fold_stmt_inplace (&use_stmt_gsi
);
1194 update_stmt (use_stmt
);
1195 maybe_clean_or_replace_eh_stmt (use_stmt
, use_stmt
);
1199 /* Propagate constant SSA_NAMEs defined in basic block BB. */
1202 propagate_constants_for_unrolling (basic_block bb
)
1204 gimple_stmt_iterator gsi
;
1206 /* Look for degenerate PHI nodes with constant argument. */
1207 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); )
1209 gimple phi
= gsi_stmt (gsi
);
1210 tree result
= gimple_phi_result (phi
);
1211 tree arg
= gimple_phi_arg_def (phi
, 0);
1213 if (gimple_phi_num_args (phi
) == 1 && TREE_CODE (arg
) == INTEGER_CST
)
1215 propagate_into_all_uses (result
, arg
);
1216 gsi_remove (&gsi
, true);
1217 release_ssa_name (result
);
1223 /* Look for assignments to SSA names with constant RHS. */
1224 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
1226 gimple stmt
= gsi_stmt (gsi
);
1229 if (is_gimple_assign (stmt
)
1230 && gimple_assign_rhs_code (stmt
) == INTEGER_CST
1231 && (lhs
= gimple_assign_lhs (stmt
), TREE_CODE (lhs
) == SSA_NAME
)
1232 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1234 propagate_into_all_uses (lhs
, gimple_assign_rhs1 (stmt
));
1235 gsi_remove (&gsi
, true);
1236 release_ssa_name (lhs
);
1243 /* Process loops from innermost to outer, stopping at the innermost
1244 loop we unrolled. */
1247 tree_unroll_loops_completely_1 (bool may_increase_size
, bool unroll_outer
,
1248 vec
<loop_p
, va_heap
>& father_stack
,
1251 struct loop
*loop_father
;
1252 bool changed
= false;
1254 enum unroll_level ul
;
1256 /* Process inner loops first. */
1257 for (inner
= loop
->inner
; inner
!= NULL
; inner
= inner
->next
)
1258 changed
|= tree_unroll_loops_completely_1 (may_increase_size
,
1259 unroll_outer
, father_stack
,
1262 /* If we changed an inner loop we cannot process outer loops in this
1263 iteration because SSA form is not up-to-date. Continue with
1264 siblings of outer loops instead. */
1268 /* Don't unroll #pragma omp simd loops until the vectorizer
1269 attempts to vectorize those. */
1270 if (loop
->force_vectorize
)
1273 /* Try to unroll this loop. */
1274 loop_father
= loop_outer (loop
);
1278 if (may_increase_size
&& optimize_loop_nest_for_speed_p (loop
)
1279 /* Unroll outermost loops only if asked to do so or they do
1280 not cause code growth. */
1281 && (unroll_outer
|| loop_outer (loop_father
)))
1286 if (canonicalize_loop_induction_variables
1287 (loop
, false, ul
, !flag_tree_loop_ivcanon
))
1289 /* If we'll continue unrolling, we need to propagate constants
1290 within the new basic blocks to fold away induction variable
1291 computations; otherwise, the size might blow up before the
1292 iteration is complete and the IR eventually cleaned up. */
1293 if (loop_outer (loop_father
) && !loop_father
->aux
)
1295 father_stack
.safe_push (loop_father
);
1296 loop_father
->aux
= loop_father
;
1305 /* Unroll LOOPS completely if they iterate just few times. Unless
1306 MAY_INCREASE_SIZE is true, perform the unrolling only if the
1307 size of the code does not increase. */
1310 tree_unroll_loops_completely (bool may_increase_size
, bool unroll_outer
)
1312 auto_vec
<loop_p
, 16> father_stack
;
1315 bool irred_invalidated
= false;
1320 bitmap loop_closed_ssa_invalidated
= NULL
;
1322 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1323 loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
1325 free_numbers_of_iterations_estimates ();
1326 estimate_numbers_of_iterations ();
1328 changed
= tree_unroll_loops_completely_1 (may_increase_size
,
1329 unroll_outer
, father_stack
,
1330 current_loops
->tree_root
);
1336 /* Be sure to skip unlooped loops while procesing father_stack
1338 FOR_EACH_VEC_ELT (loops_to_unloop
, i
, iter
)
1339 (*iter
)->aux
= NULL
;
1340 FOR_EACH_VEC_ELT (father_stack
, i
, iter
)
1343 unloop_loops (loop_closed_ssa_invalidated
, &irred_invalidated
);
1345 /* We can not use TODO_update_ssa_no_phi because VOPS gets confused. */
1346 if (loop_closed_ssa_invalidated
1347 && !bitmap_empty_p (loop_closed_ssa_invalidated
))
1348 rewrite_into_loop_closed_ssa (loop_closed_ssa_invalidated
,
1351 update_ssa (TODO_update_ssa
);
1353 /* Propagate the constants within the new basic blocks. */
1354 FOR_EACH_VEC_ELT (father_stack
, i
, iter
)
1358 basic_block
*body
= get_loop_body_in_dom_order (*iter
);
1359 for (j
= 0; j
< (*iter
)->num_nodes
; j
++)
1360 propagate_constants_for_unrolling (body
[j
]);
1362 (*iter
)->aux
= NULL
;
1364 father_stack
.truncate (0);
1366 /* This will take care of removing completely unrolled loops
1367 from the loop structures so we can continue unrolling now
1369 if (cleanup_tree_cfg ())
1370 update_ssa (TODO_update_ssa_only_virtuals
);
1372 /* Clean up the information about numbers of iterations, since
1373 complete unrolling might have invalidated it. */
1375 #ifdef ENABLE_CHECKING
1376 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
1377 verify_loop_closed_ssa (true);
1380 if (loop_closed_ssa_invalidated
)
1381 BITMAP_FREE (loop_closed_ssa_invalidated
);
1384 && ++iteration
<= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS
));
1386 father_stack
.release ();
1388 if (irred_invalidated
1389 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1390 mark_irreducible_loops ();
1395 /* Canonical induction variable creation pass. */
1399 const pass_data pass_data_iv_canon
=
1401 GIMPLE_PASS
, /* type */
1402 "ivcanon", /* name */
1403 OPTGROUP_LOOP
, /* optinfo_flags */
1404 TV_TREE_LOOP_IVCANON
, /* tv_id */
1405 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1406 0, /* properties_provided */
1407 0, /* properties_destroyed */
1408 0, /* todo_flags_start */
1409 0, /* todo_flags_finish */
1412 class pass_iv_canon
: public gimple_opt_pass
1415 pass_iv_canon (gcc::context
*ctxt
)
1416 : gimple_opt_pass (pass_data_iv_canon
, ctxt
)
1419 /* opt_pass methods: */
1420 virtual bool gate (function
*) { return flag_tree_loop_ivcanon
!= 0; }
1421 virtual unsigned int execute (function
*fun
);
1423 }; // class pass_iv_canon
1426 pass_iv_canon::execute (function
*fun
)
1428 if (number_of_loops (fun
) <= 1)
1431 return canonicalize_induction_variables ();
1437 make_pass_iv_canon (gcc::context
*ctxt
)
1439 return new pass_iv_canon (ctxt
);
1442 /* Complete unrolling of loops. */
1446 const pass_data pass_data_complete_unroll
=
1448 GIMPLE_PASS
, /* type */
1449 "cunroll", /* name */
1450 OPTGROUP_LOOP
, /* optinfo_flags */
1451 TV_COMPLETE_UNROLL
, /* tv_id */
1452 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1453 0, /* properties_provided */
1454 0, /* properties_destroyed */
1455 0, /* todo_flags_start */
1456 0, /* todo_flags_finish */
1459 class pass_complete_unroll
: public gimple_opt_pass
1462 pass_complete_unroll (gcc::context
*ctxt
)
1463 : gimple_opt_pass (pass_data_complete_unroll
, ctxt
)
1466 /* opt_pass methods: */
1467 virtual unsigned int execute (function
*);
1469 }; // class pass_complete_unroll
1472 pass_complete_unroll::execute (function
*fun
)
1474 if (number_of_loops (fun
) <= 1)
1477 return tree_unroll_loops_completely (flag_unroll_loops
1479 || optimize
>= 3, true);
1485 make_pass_complete_unroll (gcc::context
*ctxt
)
1487 return new pass_complete_unroll (ctxt
);
1490 /* Complete unrolling of inner loops. */
1494 const pass_data pass_data_complete_unrolli
=
1496 GIMPLE_PASS
, /* type */
1497 "cunrolli", /* name */
1498 OPTGROUP_LOOP
, /* optinfo_flags */
1499 TV_COMPLETE_UNROLL
, /* tv_id */
1500 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1501 0, /* properties_provided */
1502 0, /* properties_destroyed */
1503 0, /* todo_flags_start */
1504 0, /* todo_flags_finish */
1507 class pass_complete_unrolli
: public gimple_opt_pass
1510 pass_complete_unrolli (gcc::context
*ctxt
)
1511 : gimple_opt_pass (pass_data_complete_unrolli
, ctxt
)
1514 /* opt_pass methods: */
1515 virtual bool gate (function
*) { return optimize
>= 2; }
1516 virtual unsigned int execute (function
*);
1518 }; // class pass_complete_unrolli
1521 pass_complete_unrolli::execute (function
*fun
)
1525 loop_optimizer_init (LOOPS_NORMAL
1526 | LOOPS_HAVE_RECORDED_EXITS
);
1527 if (number_of_loops (fun
) > 1)
1530 ret
= tree_unroll_loops_completely (optimize
>= 3, false);
1531 free_numbers_of_iterations_estimates ();
1534 loop_optimizer_finalize ();
1542 make_pass_complete_unrolli (gcc::context
*ctxt
)
1544 return new pass_complete_unrolli (ctxt
);