1 /* Induction variable canonicalization.
2 Copyright (C) 2004, 2005, 2007, 2008 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)
77 gimple_stmt_iterator incr_at;
80 if (dump_file && (dump_flags & TDF_DETAILS))
82 fprintf (dump_file, "Added canonical iv to loop %d, ", loop->num);
83 print_generic_expr (dump_file, niter, TDF_SLIM);
84 fprintf (dump_file, " iterations.\n");
87 cond = last_stmt (exit->src);
88 in = EDGE_SUCC (exit->src, 0);
90 in = EDGE_SUCC (exit->src, 1);
92 /* Note that we do not need to worry about overflows, since
93 type of niter is always unsigned and all comparisons are
94 just for equality/nonequality -- i.e. everything works
95 with a modulo arithmetics. */
97 type = TREE_TYPE (niter);
98 niter = fold_build2 (PLUS_EXPR, type,
100 build_int_cst (type, 1));
101 incr_at = gsi_last_bb (in->src);
103 build_int_cst (type, -1),
105 &incr_at, false, NULL, &var);
107 cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
108 gimple_cond_set_code (cond, cmp);
109 gimple_cond_set_lhs (cond, var);
110 gimple_cond_set_rhs (cond, build_int_cst (type, 0));
114 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */
117 tree_num_loop_insns (struct loop *loop, eni_weights *weights)
119 basic_block *body = get_loop_body (loop);
120 gimple_stmt_iterator gsi;
121 unsigned size = 1, i;
123 for (i = 0; i < loop->num_nodes; i++)
124 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
125 size += estimate_num_insns (gsi_stmt (gsi), weights);
131 /* Estimate number of insns of completely unrolled loop. We assume
132 that the size of the unrolled loop is decreased in the
133 following way (the numbers of insns are based on what
134 estimate_num_insns returns for appropriate statements):
136 1) exit condition gets removed (2 insns)
137 2) increment of the control variable gets removed (2 insns)
138 3) All remaining statements are likely to get simplified
139 due to constant propagation. Hard to estimate; just
140 as a heuristics we decrease the rest by 1/3.
142 NINSNS is the number of insns in the loop before unrolling.
143 NUNROLL is the number of times the loop is unrolled. */
145 static unsigned HOST_WIDE_INT
146 estimated_unrolled_size (unsigned HOST_WIDE_INT ninsns,
147 unsigned HOST_WIDE_INT nunroll)
149 HOST_WIDE_INT unr_insns = 2 * ((HOST_WIDE_INT) ninsns - 4) / 3;
152 unr_insns *= (nunroll + 1);
157 /* Tries to unroll LOOP completely, i.e. NITER times.
158 UL determines which loops we are allowed to unroll.
159 EXIT is the exit of the loop that should be eliminated. */
162 try_unroll_loop_completely (struct loop *loop,
163 edge exit, tree niter,
164 enum unroll_level ul)
166 unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns;
172 if (!host_integerp (niter, 1))
174 n_unroll = tree_low_cst (niter, 1);
176 max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
177 if (n_unroll > max_unroll)
182 if (ul == UL_SINGLE_ITER)
185 ninsns = tree_num_loop_insns (loop, &eni_size_weights);
187 unr_insns = estimated_unrolled_size (ninsns, n_unroll);
188 if (dump_file && (dump_flags & TDF_DETAILS))
190 fprintf (dump_file, " Loop size: %d\n", (int) ninsns);
191 fprintf (dump_file, " Estimated size after unrolling: %d\n",
195 if (unr_insns > ninsns
197 > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS)))
199 if (dump_file && (dump_flags & TDF_DETAILS))
200 fprintf (dump_file, "Not unrolling loop %d "
201 "(--param max-completely-peeled-insns limit reached).\n",
206 if (ul == UL_NO_GROWTH
207 && unr_insns > ninsns)
209 if (dump_file && (dump_flags & TDF_DETAILS))
210 fprintf (dump_file, "Not unrolling loop %d.\n", loop->num);
220 VEC (edge, heap) *to_remove = NULL;
222 initialize_original_copy_tables ();
223 wont_exit = sbitmap_alloc (n_unroll + 1);
224 sbitmap_ones (wont_exit);
225 RESET_BIT (wont_exit, 0);
227 if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
230 DLTHE_FLAG_UPDATE_FREQ
231 | DLTHE_FLAG_COMPLETTE_PEEL))
233 free_original_copy_tables ();
238 for (i = 0; VEC_iterate (edge, to_remove, i, e); i++)
240 bool ok = remove_path (e);
244 VEC_free (edge, heap, to_remove);
246 free_original_copy_tables ();
249 cond = last_stmt (exit->src);
250 if (exit->flags & EDGE_TRUE_VALUE)
251 gimple_cond_make_true (cond);
253 gimple_cond_make_false (cond);
255 update_ssa (TODO_update_ssa);
257 if (dump_file && (dump_flags & TDF_DETAILS))
258 fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num);
263 /* Adds a canonical induction variable to LOOP if suitable.
264 CREATE_IV is true if we may create a new iv. UL determines
265 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
266 to determine the number of iterations of a loop by direct evaluation.
267 Returns true if cfg is changed. */
270 canonicalize_loop_induction_variables (struct loop *loop,
271 bool create_iv, enum unroll_level ul,
277 niter = number_of_latch_executions (loop);
278 if (TREE_CODE (niter) == INTEGER_CST)
280 exit = single_exit (loop);
281 if (!just_once_each_iteration_p (loop, exit->src))
286 /* If the loop has more than one exit, try checking all of them
287 for # of iterations determinable through scev. */
288 if (!single_exit (loop))
289 niter = find_loop_niter (loop, &exit);
291 /* Finally if everything else fails, try brute force evaluation. */
293 && (chrec_contains_undetermined (niter)
294 || TREE_CODE (niter) != INTEGER_CST))
295 niter = find_loop_niter_by_eval (loop, &exit);
297 if (chrec_contains_undetermined (niter)
298 || TREE_CODE (niter) != INTEGER_CST)
302 if (dump_file && (dump_flags & TDF_DETAILS))
304 fprintf (dump_file, "Loop %d iterates ", loop->num);
305 print_generic_expr (dump_file, niter, TDF_SLIM);
306 fprintf (dump_file, " times.\n");
309 if (try_unroll_loop_completely (loop, exit, niter, ul))
313 create_canonical_iv (loop, exit, niter);
318 /* The main entry point of the pass. Adds canonical induction variables
319 to the suitable loops. */
322 canonicalize_induction_variables (void)
326 bool changed = false;
328 FOR_EACH_LOOP (li, loop, 0)
330 changed |= canonicalize_loop_induction_variables (loop,
331 true, UL_SINGLE_ITER,
335 /* Clean up the information about numbers of iterations, since brute force
336 evaluation could reveal new information. */
340 return TODO_cleanup_cfg;
344 /* Unroll LOOPS completely if they iterate just few times. Unless
345 MAY_INCREASE_SIZE is true, perform the unrolling only if the
346 size of the code does not increase. */
349 tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)
354 enum unroll_level ul;
361 FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
363 if (may_increase_size && optimize_loop_for_speed_p (loop)
364 /* Unroll outermost loops only if asked to do so or they do
365 not cause code growth. */
367 || loop_outer (loop_outer (loop))))
371 changed |= canonicalize_loop_induction_variables
372 (loop, false, ul, !flag_tree_loop_ivcanon);
377 /* This will take care of removing completely unrolled loops
378 from the loop structures so we can continue unrolling now
380 if (cleanup_tree_cfg ())
381 update_ssa (TODO_update_ssa_only_virtuals);
383 /* Clean up the information about numbers of iterations, since
384 complete unrolling might have invalidated it. */
389 && ++iteration <= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS));
394 /* Checks whether LOOP is empty. */
397 empty_loop_p (struct loop *loop)
400 struct tree_niter_desc niter;
402 gimple_stmt_iterator gsi;
405 /* If the loop has multiple exits, it is too hard for us to handle.
406 Similarly, if the exit is not dominating, we cannot determine
407 whether the loop is not infinite. */
408 exit = single_dom_exit (loop);
412 /* The loop must be finite. */
413 if (!number_of_iterations_exit (loop, exit, &niter, false))
416 /* Values of all loop exit phi nodes must be invariants. */
417 for (gsi = gsi_start(phi_nodes (exit->dest)); !gsi_end_p (gsi); gsi_next (&gsi))
419 gimple phi = gsi_stmt (gsi);
422 if (!is_gimple_reg (PHI_RESULT (phi)))
425 def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
427 if (!expr_invariant_in_loop_p (loop, def))
431 /* And there should be no memory modifying or from other reasons
432 unremovable statements. */
433 body = get_loop_body (loop);
434 for (i = 0; i < loop->num_nodes; i++)
436 /* Irreducible region might be infinite. */
437 if (body[i]->flags & BB_IRREDUCIBLE_LOOP)
443 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
445 gimple stmt = gsi_stmt (gsi);
447 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)
448 || gimple_has_volatile_ops (stmt))
454 /* Also, asm statements and calls may have side effects and we
455 cannot change the number of times they are executed. */
456 switch (gimple_code (stmt))
459 if (gimple_has_side_effects (stmt))
467 /* We cannot remove volatile assembler. */
468 if (gimple_asm_volatile_p (stmt))
485 /* Remove LOOP by making it exit in the first iteration. */
488 remove_empty_loop (struct loop *loop)
490 edge exit = single_dom_exit (loop), non_exit;
491 gimple cond_stmt = last_stmt (exit->src);
493 unsigned n_before, freq_in, freq_h;
494 gcov_type exit_count = exit->count;
497 fprintf (dump_file, "Removing empty loop %d\n", loop->num);
499 non_exit = EDGE_SUCC (exit->src, 0);
500 if (non_exit == exit)
501 non_exit = EDGE_SUCC (exit->src, 1);
503 if (exit->flags & EDGE_TRUE_VALUE)
504 gimple_cond_make_true (cond_stmt);
506 gimple_cond_make_false (cond_stmt);
507 update_stmt (cond_stmt);
509 /* Let us set the probabilities of the edges coming from the exit block. */
510 exit->probability = REG_BR_PROB_BASE;
511 non_exit->probability = 0;
514 /* Update frequencies and counts. Everything before
515 the exit needs to be scaled FREQ_IN/FREQ_H times,
516 where FREQ_IN is the frequency of the entry edge
517 and FREQ_H is the frequency of the loop header.
518 Everything after the exit has zero frequency. */
519 freq_h = loop->header->frequency;
520 freq_in = EDGE_FREQUENCY (loop_preheader_edge (loop));
523 body = get_loop_body_in_dom_order (loop);
524 for (n_before = 1; n_before <= loop->num_nodes; n_before++)
525 if (body[n_before - 1] == exit->src)
527 scale_bbs_frequencies_int (body, n_before, freq_in, freq_h);
528 scale_bbs_frequencies_int (body + n_before, loop->num_nodes - n_before,
533 /* Number of executions of exit is not changed, thus we need to restore
534 the original value. */
535 exit->count = exit_count;
538 /* Removes LOOP if it is empty. Returns true if LOOP is removed. CHANGED
539 is set to true if LOOP or any of its subloops is removed. */
542 try_remove_empty_loop (struct loop *loop, bool *changed)
544 bool nonempty_subloop = false;
547 /* First, all subloops must be removed. */
548 for (sub = loop->inner; sub; sub = sub->next)
549 nonempty_subloop |= !try_remove_empty_loop (sub, changed);
551 if (nonempty_subloop || !empty_loop_p (loop))
554 remove_empty_loop (loop);
559 /* Remove the empty loops. */
562 remove_empty_loops (void)
564 bool changed = false;
567 for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
568 try_remove_empty_loop (loop, &changed);
573 return TODO_cleanup_cfg;