1 /* Induction variable canonicalization.
2 Copyright (C) 2004, 2005, 2007, 2008, 2010
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This pass detects the loops that iterate a constant number of times,
22 adds a canonical induction variable (step -1, tested against 0)
23 and replaces the exit test. This enables the less powerful rtl
24 level analysis to use this information.
26 This might spoil the code in some cases (by increasing register pressure).
27 Note that in the case the new variable is not needed, ivopts will get rid
28 of it, so it might only be a problem when there are no other linear induction
29 variables. In that case the created optimization possibilities are likely
32 Additionally in case we detect that it is beneficial to unroll the
33 loop completely, we do it right here to expose the optimization
34 possibilities to the following passes. */
38 #include "coretypes.h"
42 #include "basic-block.h"
43 #include "gimple-pretty-print.h"
44 #include "tree-flow.h"
46 #include "tree-pass.h"
47 #include "tree-chrec.h"
48 #include "tree-scalar-evolution.h"
51 #include "tree-inline.h"
54 /* Specifies types of loops that may be unrolled. */
58 UL_SINGLE_ITER
, /* Only loops that exit immediately in the first
60 UL_NO_GROWTH
, /* Only loops whose unrolling will not cause increase
62 UL_ALL
/* All suitable loops. */
65 /* Adds a canonical induction variable to LOOP iterating NITER times. EXIT
66 is the exit edge whose condition is replaced. */
69 create_canonical_iv (struct loop
*loop
, edge exit
, tree niter
)
74 gimple_stmt_iterator incr_at
;
77 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
79 fprintf (dump_file
, "Added canonical iv to loop %d, ", loop
->num
);
80 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
81 fprintf (dump_file
, " iterations.\n");
84 cond
= last_stmt (exit
->src
);
85 in
= EDGE_SUCC (exit
->src
, 0);
87 in
= EDGE_SUCC (exit
->src
, 1);
89 /* Note that we do not need to worry about overflows, since
90 type of niter is always unsigned and all comparisons are
91 just for equality/nonequality -- i.e. everything works
92 with a modulo arithmetics. */
94 type
= TREE_TYPE (niter
);
95 niter
= fold_build2 (PLUS_EXPR
, type
,
97 build_int_cst (type
, 1));
98 incr_at
= gsi_last_bb (in
->src
);
100 build_int_cst (type
, -1),
102 &incr_at
, false, NULL
, &var
);
104 cmp
= (exit
->flags
& EDGE_TRUE_VALUE
) ? EQ_EXPR
: NE_EXPR
;
105 gimple_cond_set_code (cond
, cmp
);
106 gimple_cond_set_lhs (cond
, var
);
107 gimple_cond_set_rhs (cond
, build_int_cst (type
, 0));
111 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */
114 tree_num_loop_insns (struct loop
*loop
, eni_weights
*weights
)
116 basic_block
*body
= get_loop_body (loop
);
117 gimple_stmt_iterator gsi
;
118 unsigned size
= 0, i
;
120 for (i
= 0; i
< loop
->num_nodes
; i
++)
121 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
122 size
+= estimate_num_insns (gsi_stmt (gsi
), weights
);
128 /* Describe size of loop as detected by tree_estimate_loop_size. */
131 /* Number of instructions in the loop. */
134 /* Number of instructions that will be likely optimized out in
135 peeled iterations of loop (i.e. computation based on induction
136 variable where induction variable starts at known constant.) */
137 int eliminated_by_peeling
;
139 /* Same statistics for last iteration of loop: it is smaller because
140 instructions after exit are not executed. */
142 int last_iteration_eliminated_by_peeling
;
145 /* Return true if OP in STMT will be constant after peeling LOOP. */
148 constant_after_peeling (tree op
, gimple stmt
, struct loop
*loop
)
152 if (is_gimple_min_invariant (op
))
155 /* We can still fold accesses to constant arrays when index is known. */
156 if (TREE_CODE (op
) != SSA_NAME
)
160 /* First make fast look if we see constant array inside. */
161 while (handled_component_p (base
))
162 base
= TREE_OPERAND (base
, 0);
163 if ((DECL_P (base
) == VAR_DECL
164 && const_value_known_p (base
))
165 || CONSTANT_CLASS_P (base
))
167 /* If so, see if we understand all the indices. */
169 while (handled_component_p (base
))
171 if (TREE_CODE (base
) == ARRAY_REF
172 && !constant_after_peeling (TREE_OPERAND (base
, 1), stmt
, loop
))
174 base
= TREE_OPERAND (base
, 0);
181 /* Induction variables are constants. */
182 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op
, &iv
, false))
184 if (!is_gimple_min_invariant (iv
.base
))
186 if (!is_gimple_min_invariant (iv
.step
))
191 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS.
192 Return results in SIZE, estimate benefits for complete unrolling exiting by EXIT. */
195 tree_estimate_loop_size (struct loop
*loop
, edge exit
, edge edge_to_cancel
, struct loop_size
*size
)
197 basic_block
*body
= get_loop_body (loop
);
198 gimple_stmt_iterator gsi
;
203 size
->eliminated_by_peeling
= 0;
204 size
->last_iteration
= 0;
205 size
->last_iteration_eliminated_by_peeling
= 0;
207 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
208 fprintf (dump_file
, "Estimating sizes for loop %i\n", loop
->num
);
209 for (i
= 0; i
< loop
->num_nodes
; i
++)
211 if (edge_to_cancel
&& body
[i
] != edge_to_cancel
->src
212 && dominated_by_p (CDI_DOMINATORS
, body
[i
], edge_to_cancel
->src
))
216 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
217 fprintf (dump_file
, " BB: %i, after_exit: %i\n", body
[i
]->index
, after_exit
);
219 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
221 gimple stmt
= gsi_stmt (gsi
);
222 int num
= estimate_num_insns (stmt
, &eni_size_weights
);
223 bool likely_eliminated
= false;
225 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
227 fprintf (dump_file
, " size: %3i ", num
);
228 print_gimple_stmt (dump_file
, gsi_stmt (gsi
), 0, 0);
231 /* Look for reasons why we might optimize this stmt away. */
233 /* Exit conditional. */
234 if (exit
&& body
[i
] == exit
->src
&& stmt
== last_stmt (exit
->src
))
236 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
237 fprintf (dump_file
, " Exit condition will be eliminated.\n");
238 likely_eliminated
= true;
240 /* Sets of IV variables */
241 else if (gimple_code (stmt
) == GIMPLE_ASSIGN
242 && constant_after_peeling (gimple_assign_lhs (stmt
), stmt
, loop
))
244 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
245 fprintf (dump_file
, " Induction variable computation will"
246 " be folded away.\n");
247 likely_eliminated
= true;
249 /* Assignments of IV variables. */
250 else if (gimple_code (stmt
) == GIMPLE_ASSIGN
251 && TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
252 && constant_after_peeling (gimple_assign_rhs1 (stmt
), stmt
,loop
)
253 && (gimple_assign_rhs_class (stmt
) != GIMPLE_BINARY_RHS
254 || constant_after_peeling (gimple_assign_rhs2 (stmt
),
257 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
258 fprintf (dump_file
, " Constant expression will be folded away.\n");
259 likely_eliminated
= true;
262 else if (gimple_code (stmt
) == GIMPLE_COND
263 && constant_after_peeling (gimple_cond_lhs (stmt
), stmt
, loop
)
264 && constant_after_peeling (gimple_cond_rhs (stmt
), stmt
, loop
))
266 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
267 fprintf (dump_file
, " Constant conditional.\n");
268 likely_eliminated
= true;
271 size
->overall
+= num
;
272 if (likely_eliminated
)
273 size
->eliminated_by_peeling
+= num
;
276 size
->last_iteration
+= num
;
277 if (likely_eliminated
)
278 size
->last_iteration_eliminated_by_peeling
+= num
;
282 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
283 fprintf (dump_file
, "size: %i-%i, last_iteration: %i-%i\n", size
->overall
,
284 size
->eliminated_by_peeling
, size
->last_iteration
,
285 size
->last_iteration_eliminated_by_peeling
);
290 /* Estimate number of insns of completely unrolled loop.
291 It is (NUNROLL + 1) * size of loop body with taking into account
292 the fact that in last copy everything after exit conditional
293 is dead and that some instructions will be eliminated after
296 Loop body is likely going to simplify futher, this is difficult
297 to guess, we just decrease the result by 1/3. */
299 static unsigned HOST_WIDE_INT
300 estimated_unrolled_size (struct loop_size
*size
,
301 unsigned HOST_WIDE_INT nunroll
)
303 HOST_WIDE_INT unr_insns
= ((nunroll
)
304 * (HOST_WIDE_INT
) (size
->overall
305 - size
->eliminated_by_peeling
));
308 unr_insns
+= size
->last_iteration
- size
->last_iteration_eliminated_by_peeling
;
310 unr_insns
= unr_insns
* 2 / 3;
317 /* Loop LOOP is known to not loop. See if there is an edge in the loop
318 body that can be remove to make the loop to always exit and at
319 the same time it does not make any code potentially executed
320 during the last iteration dead.
322 After complette unrolling we still may get rid of the conditional
323 on the exit in the last copy even if we have no idea what it does.
324 This is quite common case for loops of form
330 Here we prove the loop to iterate 5 times but we do not know
331 it from induction variable.
333 For now we handle only simple case where there is exit condition
334 just before the latch block and the latch block contains no statements
335 with side effect that may otherwise terminate the execution of loop
336 (such as by EH or by terminating the program or longjmp).
338 In the general case we may want to cancel the paths leading to statements
339 loop-niter identified as having undefined effect in the last iteration.
340 The other cases are hopefully rare and will be cleaned up later. */
343 loop_edge_to_cancel (struct loop
*loop
)
345 VEC (edge
, heap
) *exits
;
348 gimple_stmt_iterator gsi
;
350 /* We want only one predecestor of the loop. */
351 if (EDGE_COUNT (loop
->latch
->preds
) > 1)
354 exits
= get_loop_exit_edges (loop
);
356 FOR_EACH_VEC_ELT (edge
, exits
, i
, edge_to_cancel
)
358 /* Find the other edge than the loop exit
359 leaving the conditoinal. */
360 if (EDGE_COUNT (edge_to_cancel
->src
->succs
) != 2)
362 if (EDGE_SUCC (edge_to_cancel
->src
, 0) == edge_to_cancel
)
363 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 1);
365 edge_to_cancel
= EDGE_SUCC (edge_to_cancel
->src
, 0);
367 /* We should never have conditionals in the loop latch. */
368 gcc_assert (edge_to_cancel
->dest
!= loop
->header
);
370 /* Check that it leads to loop latch. */
371 if (edge_to_cancel
->dest
!= loop
->latch
)
374 VEC_free (edge
, heap
, exits
);
376 /* Verify that the code in loop latch does nothing that may end program
377 execution without really reaching the exit. This may include
378 non-pure/const function calls, EH statements, volatile ASMs etc. */
379 for (gsi
= gsi_start_bb (loop
->latch
); !gsi_end_p (gsi
); gsi_next (&gsi
))
380 if (gimple_has_side_effects (gsi_stmt (gsi
)))
382 return edge_to_cancel
;
384 VEC_free (edge
, heap
, exits
);
388 /* Tries to unroll LOOP completely, i.e. NITER times.
389 UL determines which loops we are allowed to unroll.
390 EXIT is the exit of the loop that should be eliminated.
391 IRRED_INVALIDATED is used to bookkeep if information about
392 irreducible regions may become invalid as a result
393 of the transformation.
394 LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case
395 when we need to go into loop closed SSA form. */
398 try_unroll_loop_completely (struct loop
*loop
,
399 edge exit
, tree niter
,
400 enum unroll_level ul
,
401 bool *irred_invalidated
,
402 bitmap loop_closed_ssa_invalidated
)
404 unsigned HOST_WIDE_INT n_unroll
, ninsns
, max_unroll
, unr_insns
;
406 struct loop_size size
;
407 bool n_unroll_found
= false;
408 HOST_WIDE_INT maxiter
;
414 gimple_stmt_iterator gsi
;
415 edge edge_to_cancel
= NULL
;
418 /* See if we proved number of iterations to be low constant.
420 EXIT is an edge that will be removed in all but last iteration of
423 EDGE_TO_CACNEL is an edge that will be removed from the last iteration
424 of the unrolled sequence and is expected to make the final loop not
427 If the number of execution of loop is determined by standard induction
428 variable test, then EXIT and EDGE_TO_CANCEL are the two edges leaving
430 if (host_integerp (niter
, 1))
432 n_unroll
= tree_low_cst (niter
, 1);
433 n_unroll_found
= true;
434 edge_to_cancel
= EDGE_SUCC (exit
->src
, 0);
435 if (edge_to_cancel
== exit
)
436 edge_to_cancel
= EDGE_SUCC (exit
->src
, 1);
438 /* We do not know the number of iterations and thus we can not eliminate
443 /* See if we can improve our estimate by using recorded loop bounds. */
444 maxiter
= max_loop_iterations_int (loop
);
446 && (!n_unroll_found
|| (unsigned HOST_WIDE_INT
)maxiter
< n_unroll
))
449 n_unroll_found
= true;
450 /* Loop terminates before the IV variable test, so we can not
451 remove it in the last iteration. */
452 edge_to_cancel
= NULL
;
458 max_unroll
= PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
);
459 if (n_unroll
> max_unroll
)
463 edge_to_cancel
= loop_edge_to_cancel (loop
);
470 VEC (edge
, heap
) *to_remove
= NULL
;
471 if (ul
== UL_SINGLE_ITER
)
474 tree_estimate_loop_size (loop
, exit
, edge_to_cancel
, &size
);
475 ninsns
= size
.overall
;
477 unr_insns
= estimated_unrolled_size (&size
, n_unroll
);
478 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
480 fprintf (dump_file
, " Loop size: %d\n", (int) ninsns
);
481 fprintf (dump_file
, " Estimated size after unrolling: %d\n",
485 /* We unroll only inner loops, because we do not consider it profitable
486 otheriwse. We still can cancel loopback edge of not rolling loop;
487 this is always a good idea. */
488 if (loop
->inner
&& unr_insns
> ninsns
)
490 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
491 fprintf (dump_file
, "Not unrolling loop %d:"
492 "it is not innermost and code would grow.\n",
497 if (unr_insns
> ninsns
499 > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
)))
501 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
502 fprintf (dump_file
, "Not unrolling loop %d "
503 "(--param max-completely-peeled-insns limit reached).\n",
508 if (ul
== UL_NO_GROWTH
509 && unr_insns
> ninsns
)
511 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
512 fprintf (dump_file
, "Not unrolling loop %d: size would grow.\n",
517 initialize_original_copy_tables ();
518 wont_exit
= sbitmap_alloc (n_unroll
+ 1);
519 sbitmap_ones (wont_exit
);
520 RESET_BIT (wont_exit
, 0);
522 if (!gimple_duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
525 DLTHE_FLAG_UPDATE_FREQ
526 | DLTHE_FLAG_COMPLETTE_PEEL
))
528 free_original_copy_tables ();
533 FOR_EACH_VEC_ELT (edge
, to_remove
, i
, e
)
535 bool ok
= remove_path (e
);
539 VEC_free (edge
, heap
, to_remove
);
541 free_original_copy_tables ();
544 /* Remove the conditional from the last copy of the loop. */
547 cond
= last_stmt (edge_to_cancel
->src
);
548 if (edge_to_cancel
->flags
& EDGE_TRUE_VALUE
)
549 gimple_cond_make_false (cond
);
551 gimple_cond_make_true (cond
);
553 /* Do not remove the path. Doing so may remove outer loop
554 and confuse bookkeeping code in tree_unroll_loops_completelly. */
556 /* We did not manage to cancel the loop.
557 The loop latch remains reachable even if it will never be reached
558 at runtime. We must redirect it to somewhere, so create basic
559 block containg __builtin_unreachable call for this reason. */
563 latch_edge
= loop_latch_edge (loop
);
564 flags
= latch_edge
->flags
;
565 locus
= latch_edge
->goto_locus
;
567 /* Unloop destroys the latch edge. */
568 unloop (loop
, irred_invalidated
, loop_closed_ssa_invalidated
);
570 /* Create new basic block for the latch edge destination and wire
572 stmt
= gimple_build_call (builtin_decl_implicit (BUILT_IN_UNREACHABLE
), 0);
573 latch_edge
= make_edge (latch
, create_basic_block (NULL
, NULL
, latch
), flags
);
574 latch_edge
->probability
= 0;
575 latch_edge
->count
= 0;
576 latch_edge
->flags
|= flags
;
577 latch_edge
->goto_locus
= locus
;
579 latch_edge
->dest
->loop_father
= current_loops
->tree_root
;
580 latch_edge
->dest
->count
= 0;
581 latch_edge
->dest
->frequency
= 0;
582 set_immediate_dominator (CDI_DOMINATORS
, latch_edge
->dest
, latch_edge
->src
);
584 gsi
= gsi_start_bb (latch_edge
->dest
);
585 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
588 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
591 fprintf (dump_file
, "Turned loop %d to non-loop; it never loops.\n",
594 fprintf (dump_file
, "Unrolled loop %d completely "
595 "(duplicated %i times).\n", num
, (int)n_unroll
);
597 fprintf (dump_file
, "Exit condition of peeled iterations was "
600 fprintf (dump_file
, "Last iteration exit edge was proved true.\n");
602 fprintf (dump_file
, "Latch of last iteration was marked by "
603 "__builtin_unreachable ().\n");
609 /* Adds a canonical induction variable to LOOP if suitable.
610 CREATE_IV is true if we may create a new iv. UL determines
611 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
612 to determine the number of iterations of a loop by direct evaluation.
613 Returns true if cfg is changed.
615 IRRED_INVALIDATED is used to keep if irreducible reginos needs to be recomputed. */
618 canonicalize_loop_induction_variables (struct loop
*loop
,
619 bool create_iv
, enum unroll_level ul
,
621 bool *irred_invalidated
,
622 bitmap loop_closed_ssa_invalidated
)
627 niter
= number_of_latch_executions (loop
);
628 if (TREE_CODE (niter
) == INTEGER_CST
)
630 exit
= single_exit (loop
);
631 if (!just_once_each_iteration_p (loop
, exit
->src
))
636 /* If the loop has more than one exit, try checking all of them
637 for # of iterations determinable through scev. */
638 if (!single_exit (loop
))
639 niter
= find_loop_niter (loop
, &exit
);
641 /* Finally if everything else fails, try brute force evaluation. */
643 && (chrec_contains_undetermined (niter
)
644 || TREE_CODE (niter
) != INTEGER_CST
))
645 niter
= find_loop_niter_by_eval (loop
, &exit
);
647 if (TREE_CODE (niter
) != INTEGER_CST
)
651 /* We work exceptionally hard here to estimate the bound
652 by find_loop_niter_by_eval. Be sure to keep it for future. */
653 if (niter
&& TREE_CODE (niter
) == INTEGER_CST
)
654 record_niter_bound (loop
, tree_to_double_int (niter
), false, true);
656 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
657 && TREE_CODE (niter
) == INTEGER_CST
)
659 fprintf (dump_file
, "Loop %d iterates ", loop
->num
);
660 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
661 fprintf (dump_file
, " times.\n");
663 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
664 && max_loop_iterations_int (loop
) >= 0)
666 fprintf (dump_file
, "Loop %d iterates at most %i times.\n", loop
->num
,
667 (int)max_loop_iterations_int (loop
));
670 if (try_unroll_loop_completely (loop
, exit
, niter
, ul
, irred_invalidated
,
671 loop_closed_ssa_invalidated
))
675 && niter
&& !chrec_contains_undetermined (niter
))
676 create_canonical_iv (loop
, exit
, niter
);
681 /* The main entry point of the pass. Adds canonical induction variables
682 to the suitable loops. */
685 canonicalize_induction_variables (void)
689 bool changed
= false;
690 bool irred_invalidated
= false;
691 bitmap loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
693 FOR_EACH_LOOP (li
, loop
, 0)
695 changed
|= canonicalize_loop_induction_variables (loop
,
696 true, UL_SINGLE_ITER
,
699 loop_closed_ssa_invalidated
);
701 gcc_assert (!need_ssa_update_p (cfun
));
703 if (irred_invalidated
704 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
705 mark_irreducible_loops ();
707 /* Clean up the information about numbers of iterations, since brute force
708 evaluation could reveal new information. */
711 if (!bitmap_empty_p (loop_closed_ssa_invalidated
))
713 gcc_checking_assert (loops_state_satisfies_p (LOOP_CLOSED_SSA
));
714 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
716 BITMAP_FREE (loop_closed_ssa_invalidated
);
719 return TODO_cleanup_cfg
;
723 /* Propagate VAL into all uses of SSA_NAME. */
726 propagate_into_all_uses (tree ssa_name
, tree val
)
728 imm_use_iterator iter
;
731 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, ssa_name
)
733 gimple_stmt_iterator use_stmt_gsi
= gsi_for_stmt (use_stmt
);
736 FOR_EACH_IMM_USE_ON_STMT (use
, iter
)
739 if (is_gimple_assign (use_stmt
)
740 && get_gimple_rhs_class (gimple_assign_rhs_code (use_stmt
))
741 == GIMPLE_SINGLE_RHS
)
743 tree rhs
= gimple_assign_rhs1 (use_stmt
);
745 if (TREE_CODE (rhs
) == ADDR_EXPR
)
746 recompute_tree_invariant_for_addr_expr (rhs
);
749 fold_stmt_inplace (&use_stmt_gsi
);
750 update_stmt (use_stmt
);
751 maybe_clean_or_replace_eh_stmt (use_stmt
, use_stmt
);
755 /* Propagate constant SSA_NAMEs defined in basic block BB. */
758 propagate_constants_for_unrolling (basic_block bb
)
760 gimple_stmt_iterator gsi
;
762 /* Look for degenerate PHI nodes with constant argument. */
763 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); )
765 gimple phi
= gsi_stmt (gsi
);
766 tree result
= gimple_phi_result (phi
);
767 tree arg
= gimple_phi_arg_def (phi
, 0);
769 if (gimple_phi_num_args (phi
) == 1 && TREE_CODE (arg
) == INTEGER_CST
)
771 propagate_into_all_uses (result
, arg
);
772 gsi_remove (&gsi
, true);
773 release_ssa_name (result
);
779 /* Look for assignments to SSA names with constant RHS. */
780 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
782 gimple stmt
= gsi_stmt (gsi
);
785 if (is_gimple_assign (stmt
)
786 && (lhs
= gimple_assign_lhs (stmt
), TREE_CODE (lhs
) == SSA_NAME
)
787 && gimple_assign_rhs_code (stmt
) == INTEGER_CST
)
789 propagate_into_all_uses (lhs
, gimple_assign_rhs1 (stmt
));
790 gsi_remove (&gsi
, true);
791 release_ssa_name (lhs
);
798 /* Unroll LOOPS completely if they iterate just few times. Unless
799 MAY_INCREASE_SIZE is true, perform the unrolling only if the
800 size of the code does not increase. */
803 tree_unroll_loops_completely (bool may_increase_size
, bool unroll_outer
)
805 VEC(loop_p
,stack
) *father_stack
= VEC_alloc (loop_p
, stack
, 16);
809 enum unroll_level ul
;
811 bool irred_invalidated
= false;
816 bitmap loop_closed_ssa_invalidated
= NULL
;
818 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
819 loop_closed_ssa_invalidated
= BITMAP_ALLOC (NULL
);
821 FOR_EACH_LOOP (li
, loop
, 0)
823 struct loop
*loop_father
= loop_outer (loop
);
825 if (may_increase_size
&& optimize_loop_for_speed_p (loop
)
826 /* Unroll outermost loops only if asked to do so or they do
827 not cause code growth. */
828 && (unroll_outer
|| loop_outer (loop_father
)))
833 if (canonicalize_loop_induction_variables
834 (loop
, false, ul
, !flag_tree_loop_ivcanon
,
835 &irred_invalidated
, loop_closed_ssa_invalidated
))
838 /* If we'll continue unrolling, we need to propagate constants
839 within the new basic blocks to fold away induction variable
840 computations; otherwise, the size might blow up before the
841 iteration is complete and the IR eventually cleaned up. */
842 if (loop_outer (loop_father
) && !loop_father
->aux
)
844 VEC_safe_push (loop_p
, stack
, father_stack
, loop_father
);
845 loop_father
->aux
= loop_father
;
855 /* We can not use TODO_update_ssa_no_phi because VOPS gets confused. */
857 if (loop_closed_ssa_invalidated
858 && !bitmap_empty_p (loop_closed_ssa_invalidated
))
859 rewrite_into_loop_closed_ssa (loop_closed_ssa_invalidated
,
862 update_ssa (TODO_update_ssa
);
864 /* Propagate the constants within the new basic blocks. */
865 FOR_EACH_VEC_ELT (loop_p
, father_stack
, i
, iter
)
868 basic_block
*body
= get_loop_body_in_dom_order (*iter
);
869 for (j
= 0; j
< (*iter
)->num_nodes
; j
++)
870 propagate_constants_for_unrolling (body
[j
]);
874 VEC_truncate (loop_p
, father_stack
, 0);
876 /* This will take care of removing completely unrolled loops
877 from the loop structures so we can continue unrolling now
879 if (cleanup_tree_cfg ())
880 update_ssa (TODO_update_ssa_only_virtuals
);
882 /* Clean up the information about numbers of iterations, since
883 complete unrolling might have invalidated it. */
885 #ifdef ENABLE_CHECKING
886 if (loops_state_satisfies_p (LOOP_CLOSED_SSA
))
887 verify_loop_closed_ssa (true);
890 if (loop_closed_ssa_invalidated
)
891 BITMAP_FREE (loop_closed_ssa_invalidated
);
894 && ++iteration
<= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS
));
896 VEC_free (loop_p
, stack
, father_stack
);
898 if (irred_invalidated
899 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
900 mark_irreducible_loops ();