1 /* Induction variable canonicalization.
2 Copyright (C) 2004, 2005, 2007 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
31 Additionally in case we detect that it is beneficial to unroll the
32 loop completely, we do it right here to expose the optimization
33 possibilities to the following passes. */
37 #include "coretypes.h"
42 #include "hard-reg-set.h"
43 #include "basic-block.h"
45 #include "diagnostic.h"
46 #include "tree-flow.h"
47 #include "tree-dump.h"
49 #include "tree-pass.h"
51 #include "tree-chrec.h"
52 #include "tree-scalar-evolution.h"
55 #include "tree-inline.h"
57 /* Specifies types of loops that may be unrolled. */
61 UL_SINGLE_ITER
, /* Only loops that exit immediately in the first
63 UL_NO_GROWTH
, /* Only loops whose unrolling will not cause increase
65 UL_ALL
/* All suitable loops. */
68 /* Adds a canonical induction variable to LOOP iterating NITER times. EXIT
69 is the exit edge whose condition is replaced. */
72 create_canonical_iv (struct loop
*loop
, edge exit
, tree niter
)
76 block_stmt_iterator incr_at
;
79 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
81 fprintf (dump_file
, "Added canonical iv to loop %d, ", loop
->num
);
82 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
83 fprintf (dump_file
, " iterations.\n");
86 cond
= last_stmt (exit
->src
);
87 in
= EDGE_SUCC (exit
->src
, 0);
89 in
= EDGE_SUCC (exit
->src
, 1);
91 /* Note that we do not need to worry about overflows, since
92 type of niter is always unsigned and all comparisons are
93 just for equality/nonequality -- i.e. everything works
94 with a modulo arithmetics. */
96 type
= TREE_TYPE (niter
);
97 niter
= fold_build2 (PLUS_EXPR
, type
,
99 build_int_cst (type
, 1));
100 incr_at
= bsi_last (in
->src
);
102 build_int_cst (type
, -1),
104 &incr_at
, false, NULL
, &var
);
106 cmp
= (exit
->flags
& EDGE_TRUE_VALUE
) ? EQ_EXPR
: NE_EXPR
;
107 COND_EXPR_COND (cond
) = build2 (cmp
, boolean_type_node
,
109 build_int_cst (type
, 0));
113 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */
116 tree_num_loop_insns (struct loop
*loop
, eni_weights
*weights
)
118 basic_block
*body
= get_loop_body (loop
);
119 block_stmt_iterator bsi
;
120 unsigned size
= 1, i
;
122 for (i
= 0; i
< loop
->num_nodes
; i
++)
123 for (bsi
= bsi_start (body
[i
]); !bsi_end_p (bsi
); bsi_next (&bsi
))
124 size
+= estimate_num_insns (bsi_stmt (bsi
), weights
);
130 /* Estimate number of insns of completely unrolled loop. We assume
131 that the size of the unrolled loop is decreased in the
132 following way (the numbers of insns are based on what
133 estimate_num_insns returns for appropriate statements):
135 1) exit condition gets removed (2 insns)
136 2) increment of the control variable gets removed (2 insns)
137 3) All remaining statements are likely to get simplified
138 due to constant propagation. Hard to estimate; just
139 as a heuristics we decrease the rest by 1/3.
141 NINSNS is the number of insns in the loop before unrolling.
142 NUNROLL is the number of times the loop is unrolled. */
144 static unsigned HOST_WIDE_INT
145 estimated_unrolled_size (unsigned HOST_WIDE_INT ninsns
,
146 unsigned HOST_WIDE_INT nunroll
)
148 HOST_WIDE_INT unr_insns
= 2 * ((HOST_WIDE_INT
) ninsns
- 4) / 3;
151 unr_insns
*= (nunroll
+ 1);
156 /* Tries to unroll LOOP completely, i.e. NITER times.
157 UL determines which loops we are allowed to unroll.
158 EXIT is the exit of the loop that should be eliminated. */
161 try_unroll_loop_completely (struct loop
*loop
,
162 edge exit
, tree niter
,
163 enum unroll_level ul
)
165 unsigned HOST_WIDE_INT n_unroll
, ninsns
, max_unroll
, unr_insns
;
171 if (!host_integerp (niter
, 1))
173 n_unroll
= tree_low_cst (niter
, 1);
175 max_unroll
= PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
);
176 if (n_unroll
> max_unroll
)
181 if (ul
== UL_SINGLE_ITER
)
184 ninsns
= tree_num_loop_insns (loop
, &eni_size_weights
);
186 if (n_unroll
* ninsns
187 > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
))
190 unr_insns
= estimated_unrolled_size (ninsns
, n_unroll
);
191 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
193 fprintf (dump_file
, " Loop size: %d\n", (int) ninsns
);
194 fprintf (dump_file
, " Estimated size after unrolling: %d\n",
198 if (ul
== UL_NO_GROWTH
199 && unr_insns
> ninsns
)
201 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
202 fprintf (dump_file
, "Not unrolling loop %d.\n", loop
->num
);
212 VEC (edge
, heap
) *to_remove
= NULL
;
214 initialize_original_copy_tables ();
215 wont_exit
= sbitmap_alloc (n_unroll
+ 1);
216 sbitmap_ones (wont_exit
);
217 RESET_BIT (wont_exit
, 0);
219 if (!tree_duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
222 DLTHE_FLAG_UPDATE_FREQ
223 | DLTHE_FLAG_COMPLETTE_PEEL
))
225 free_original_copy_tables ();
230 for (i
= 0; VEC_iterate (edge
, to_remove
, i
, e
); i
++)
232 bool ok
= remove_path (e
);
236 VEC_free (edge
, heap
, to_remove
);
238 free_original_copy_tables ();
241 cond
= last_stmt (exit
->src
);
242 COND_EXPR_COND (cond
) = (exit
->flags
& EDGE_TRUE_VALUE
) ? boolean_true_node
243 : boolean_false_node
;
245 update_ssa (TODO_update_ssa
);
247 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
248 fprintf (dump_file
, "Unrolled loop %d completely.\n", loop
->num
);
253 /* Adds a canonical induction variable to LOOP if suitable.
254 CREATE_IV is true if we may create a new iv. UL determines
255 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
256 to determine the number of iterations of a loop by direct evaluation.
257 Returns true if cfg is changed. */
260 canonicalize_loop_induction_variables (struct loop
*loop
,
261 bool create_iv
, enum unroll_level ul
,
267 niter
= number_of_latch_executions (loop
);
268 if (TREE_CODE (niter
) == INTEGER_CST
)
270 exit
= single_exit (loop
);
271 if (!just_once_each_iteration_p (loop
, exit
->src
))
276 /* If the loop has more than one exit, try checking all of them
277 for # of iterations determinable through scev. */
278 if (!single_exit (loop
))
279 niter
= find_loop_niter (loop
, &exit
);
281 /* Finally if everything else fails, try brute force evaluation. */
283 && (chrec_contains_undetermined (niter
)
284 || TREE_CODE (niter
) != INTEGER_CST
))
285 niter
= find_loop_niter_by_eval (loop
, &exit
);
287 if (chrec_contains_undetermined (niter
)
288 || TREE_CODE (niter
) != INTEGER_CST
)
292 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
294 fprintf (dump_file
, "Loop %d iterates ", loop
->num
);
295 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
296 fprintf (dump_file
, " times.\n");
299 if (try_unroll_loop_completely (loop
, exit
, niter
, ul
))
303 create_canonical_iv (loop
, exit
, niter
);
308 /* The main entry point of the pass. Adds canonical induction variables
309 to the suitable loops. */
312 canonicalize_induction_variables (void)
316 bool changed
= false;
318 FOR_EACH_LOOP (li
, loop
, 0)
320 changed
|= canonicalize_loop_induction_variables (loop
,
321 true, UL_SINGLE_ITER
,
325 /* Clean up the information about numbers of iterations, since brute force
326 evaluation could reveal new information. */
330 return TODO_cleanup_cfg
;
334 /* Unroll LOOPS completely if they iterate just few times. Unless
335 MAY_INCREASE_SIZE is true, perform the unrolling only if the
336 size of the code does not increase. */
339 tree_unroll_loops_completely (bool may_increase_size
, bool unroll_outer
)
344 enum unroll_level ul
;
350 FOR_EACH_LOOP (li
, loop
, LI_ONLY_INNERMOST
)
352 if (may_increase_size
&& maybe_hot_bb_p (loop
->header
)
353 /* Unroll outermost loops only if asked to do so or they do
354 not cause code growth. */
356 || loop_outer (loop_outer (loop
))))
360 changed
|= canonicalize_loop_induction_variables
361 (loop
, false, ul
, !flag_tree_loop_ivcanon
);
366 /* This will take care of removing completely unrolled loops
367 from the loop structures so we can continue unrolling now
369 if (cleanup_tree_cfg ())
370 update_ssa (TODO_update_ssa_only_virtuals
);
372 /* Clean up the information about numbers of iterations, since
373 complete unrolling might have invalidated it. */
382 /* Checks whether LOOP is empty. */
385 empty_loop_p (struct loop
*loop
)
388 struct tree_niter_desc niter
;
391 block_stmt_iterator bsi
;
395 /* If the loop has multiple exits, it is too hard for us to handle.
396 Similarly, if the exit is not dominating, we cannot determine
397 whether the loop is not infinite. */
398 exit
= single_dom_exit (loop
);
402 /* The loop must be finite. */
403 if (!number_of_iterations_exit (loop
, exit
, &niter
, false))
406 /* Values of all loop exit phi nodes must be invariants. */
407 for (phi
= phi_nodes (exit
->dest
); phi
; phi
= PHI_CHAIN (phi
))
409 if (!is_gimple_reg (PHI_RESULT (phi
)))
412 def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
414 if (!expr_invariant_in_loop_p (loop
, def
))
418 /* And there should be no memory modifying or from other reasons
419 unremovable statements. */
420 body
= get_loop_body (loop
);
421 for (i
= 0; i
< loop
->num_nodes
; i
++)
423 /* Irreducible region might be infinite. */
424 if (body
[i
]->flags
& BB_IRREDUCIBLE_LOOP
)
430 for (bsi
= bsi_start (body
[i
]); !bsi_end_p (bsi
); bsi_next (&bsi
))
432 stmt
= bsi_stmt (bsi
);
433 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_VIRTUAL_DEFS
)
434 || stmt_ann (stmt
)->has_volatile_ops
)
440 /* Also, asm statements and calls may have side effects and we
441 cannot change the number of times they are executed. */
442 switch (TREE_CODE (stmt
))
445 case GIMPLE_MODIFY_STMT
:
446 stmt
= get_call_expr_in (stmt
);
451 if (TREE_SIDE_EFFECTS (stmt
))
459 /* We cannot remove volatile assembler. */
460 if (ASM_VOLATILE_P (stmt
))
477 /* Remove LOOP by making it exit in the first iteration. */
480 remove_empty_loop (struct loop
*loop
)
482 edge exit
= single_dom_exit (loop
), non_exit
;
483 tree cond_stmt
= last_stmt (exit
->src
);
486 unsigned n_before
, freq_in
, freq_h
;
487 gcov_type exit_count
= exit
->count
;
490 fprintf (dump_file
, "Removing empty loop %d\n", loop
->num
);
492 non_exit
= EDGE_SUCC (exit
->src
, 0);
493 if (non_exit
== exit
)
494 non_exit
= EDGE_SUCC (exit
->src
, 1);
496 if (exit
->flags
& EDGE_TRUE_VALUE
)
497 do_exit
= boolean_true_node
;
499 do_exit
= boolean_false_node
;
501 COND_EXPR_COND (cond_stmt
) = do_exit
;
502 update_stmt (cond_stmt
);
504 /* Let us set the probabilities of the edges coming from the exit block. */
505 exit
->probability
= REG_BR_PROB_BASE
;
506 non_exit
->probability
= 0;
509 /* Update frequencies and counts. Everything before
510 the exit needs to be scaled FREQ_IN/FREQ_H times,
511 where FREQ_IN is the frequency of the entry edge
512 and FREQ_H is the frequency of the loop header.
513 Everything after the exit has zero frequency. */
514 freq_h
= loop
->header
->frequency
;
515 freq_in
= EDGE_FREQUENCY (loop_preheader_edge (loop
));
518 body
= get_loop_body_in_dom_order (loop
);
519 for (n_before
= 1; n_before
<= loop
->num_nodes
; n_before
++)
520 if (body
[n_before
- 1] == exit
->src
)
522 scale_bbs_frequencies_int (body
, n_before
, freq_in
, freq_h
);
523 scale_bbs_frequencies_int (body
+ n_before
, loop
->num_nodes
- n_before
,
528 /* Number of executions of exit is not changed, thus we need to restore
529 the original value. */
530 exit
->count
= exit_count
;
533 /* Removes LOOP if it is empty. Returns true if LOOP is removed. CHANGED
534 is set to true if LOOP or any of its subloops is removed. */
537 try_remove_empty_loop (struct loop
*loop
, bool *changed
)
539 bool nonempty_subloop
= false;
542 /* First, all subloops must be removed. */
543 for (sub
= loop
->inner
; sub
; sub
= sub
->next
)
544 nonempty_subloop
|= !try_remove_empty_loop (sub
, changed
);
546 if (nonempty_subloop
|| !empty_loop_p (loop
))
549 remove_empty_loop (loop
);
554 /* Remove the empty loops. */
557 remove_empty_loops (void)
559 bool changed
= false;
562 for (loop
= current_loops
->tree_root
->inner
; loop
; loop
= loop
->next
)
563 try_remove_empty_loop (loop
, &changed
);
568 return TODO_cleanup_cfg
;