* gcc.dg/compat/struct-layout-1_generate.c (dg_options): New. Moved
[official-gcc.git] / gcc / tree-ssa-loop-ivcanon.c
blobe278c55b08bbd3f0387bf8f03a968f13fd1e9441
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
9 later version.
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
14 for more details.
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
29 to pay up.
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. */
35 #include "config.h"
36 #include "system.h"
37 #include "coretypes.h"
38 #include "tm.h"
39 #include "tree.h"
40 #include "rtl.h"
41 #include "tm_p.h"
42 #include "hard-reg-set.h"
43 #include "basic-block.h"
44 #include "output.h"
45 #include "diagnostic.h"
46 #include "tree-flow.h"
47 #include "tree-dump.h"
48 #include "cfgloop.h"
49 #include "tree-pass.h"
50 #include "ggc.h"
51 #include "tree-chrec.h"
52 #include "tree-scalar-evolution.h"
53 #include "params.h"
54 #include "flags.h"
55 #include "tree-inline.h"
57 /* Specifies types of loops that may be unrolled. */
59 enum unroll_level
61 UL_SINGLE_ITER, /* Only loops that exit immediately in the first
62 iteration. */
63 UL_NO_GROWTH, /* Only loops whose unrolling will not cause increase
64 of code size. */
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. */
71 static void
72 create_canonical_iv (struct loop *loop, edge exit, tree niter)
74 edge in;
75 tree type, var;
76 gimple cond;
77 gimple_stmt_iterator incr_at;
78 enum tree_code cmp;
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);
89 if (in == exit)
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,
99 niter,
100 build_int_cst (type, 1));
101 incr_at = gsi_last_bb (in->src);
102 create_iv (niter,
103 build_int_cst (type, -1),
104 NULL_TREE, loop,
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));
111 update_stmt (cond);
114 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */
116 unsigned
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);
126 free (body);
128 return size;
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;
150 if (unr_insns <= 0)
151 unr_insns = 1;
152 unr_insns *= (nunroll + 1);
154 return unr_insns;
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. */
161 static bool
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;
167 gimple cond;
169 if (loop->inner)
170 return false;
172 if (!host_integerp (niter, 1))
173 return false;
174 n_unroll = tree_low_cst (niter, 1);
176 max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
177 if (n_unroll > max_unroll)
178 return false;
180 if (n_unroll)
182 if (ul == UL_SINGLE_ITER)
183 return false;
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",
192 (int) unr_insns);
195 if (unr_insns > ninsns
196 && (unr_insns
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",
202 loop->num);
203 return false;
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);
211 return false;
215 if (n_unroll)
217 sbitmap wont_exit;
218 edge e;
219 unsigned i;
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),
228 n_unroll, wont_exit,
229 exit, &to_remove,
230 DLTHE_FLAG_UPDATE_FREQ
231 | DLTHE_FLAG_COMPLETTE_PEEL))
233 free_original_copy_tables ();
234 free (wont_exit);
235 return false;
238 for (i = 0; VEC_iterate (edge, to_remove, i, e); i++)
240 bool ok = remove_path (e);
241 gcc_assert (ok);
244 VEC_free (edge, heap, to_remove);
245 free (wont_exit);
246 free_original_copy_tables ();
249 cond = last_stmt (exit->src);
250 if (exit->flags & EDGE_TRUE_VALUE)
251 gimple_cond_make_true (cond);
252 else
253 gimple_cond_make_false (cond);
254 update_stmt (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);
260 return true;
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. */
269 static bool
270 canonicalize_loop_induction_variables (struct loop *loop,
271 bool create_iv, enum unroll_level ul,
272 bool try_eval)
274 edge exit = NULL;
275 tree niter;
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))
282 return false;
284 else
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. */
292 if (try_eval
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)
299 return false;
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))
310 return true;
312 if (create_iv)
313 create_canonical_iv (loop, exit, niter);
315 return false;
318 /* The main entry point of the pass. Adds canonical induction variables
319 to the suitable loops. */
321 unsigned int
322 canonicalize_induction_variables (void)
324 loop_iterator li;
325 struct loop *loop;
326 bool changed = false;
328 FOR_EACH_LOOP (li, loop, 0)
330 changed |= canonicalize_loop_induction_variables (loop,
331 true, UL_SINGLE_ITER,
332 true);
335 /* Clean up the information about numbers of iterations, since brute force
336 evaluation could reveal new information. */
337 scev_reset ();
339 if (changed)
340 return TODO_cleanup_cfg;
341 return 0;
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. */
348 unsigned int
349 tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)
351 loop_iterator li;
352 struct loop *loop;
353 bool changed;
354 enum unroll_level ul;
358 changed = false;
360 FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
362 if (may_increase_size && optimize_loop_for_speed_p (loop)
363 /* Unroll outermost loops only if asked to do so or they do
364 not cause code growth. */
365 && (unroll_outer
366 || loop_outer (loop_outer (loop))))
367 ul = UL_ALL;
368 else
369 ul = UL_NO_GROWTH;
370 changed |= canonicalize_loop_induction_variables
371 (loop, false, ul, !flag_tree_loop_ivcanon);
374 if (changed)
376 /* This will take care of removing completely unrolled loops
377 from the loop structures so we can continue unrolling now
378 innermost loops. */
379 if (cleanup_tree_cfg ())
380 update_ssa (TODO_update_ssa_only_virtuals);
382 /* Clean up the information about numbers of iterations, since
383 complete unrolling might have invalidated it. */
384 scev_reset ();
387 while (changed);
389 return 0;
392 /* Checks whether LOOP is empty. */
394 static bool
395 empty_loop_p (struct loop *loop)
397 edge exit;
398 struct tree_niter_desc niter;
399 basic_block *body;
400 gimple_stmt_iterator gsi;
401 unsigned i;
403 /* If the loop has multiple exits, it is too hard for us to handle.
404 Similarly, if the exit is not dominating, we cannot determine
405 whether the loop is not infinite. */
406 exit = single_dom_exit (loop);
407 if (!exit)
408 return false;
410 /* The loop must be finite. */
411 if (!number_of_iterations_exit (loop, exit, &niter, false))
412 return false;
414 /* Values of all loop exit phi nodes must be invariants. */
415 for (gsi = gsi_start(phi_nodes (exit->dest)); !gsi_end_p (gsi); gsi_next (&gsi))
417 gimple phi = gsi_stmt (gsi);
418 tree def;
420 if (!is_gimple_reg (PHI_RESULT (phi)))
421 continue;
423 def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
425 if (!expr_invariant_in_loop_p (loop, def))
426 return false;
429 /* And there should be no memory modifying or from other reasons
430 unremovable statements. */
431 body = get_loop_body (loop);
432 for (i = 0; i < loop->num_nodes; i++)
434 /* Irreducible region might be infinite. */
435 if (body[i]->flags & BB_IRREDUCIBLE_LOOP)
437 free (body);
438 return false;
441 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
443 gimple stmt = gsi_stmt (gsi);
445 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)
446 || gimple_has_volatile_ops (stmt))
448 free (body);
449 return false;
452 /* Also, asm statements and calls may have side effects and we
453 cannot change the number of times they are executed. */
454 switch (gimple_code (stmt))
456 case GIMPLE_CALL:
457 if (gimple_has_side_effects (stmt))
459 free (body);
460 return false;
462 break;
464 case GIMPLE_ASM:
465 /* We cannot remove volatile assembler. */
466 if (gimple_asm_volatile_p (stmt))
468 free (body);
469 return false;
471 break;
473 default:
474 break;
478 free (body);
480 return true;
483 /* Remove LOOP by making it exit in the first iteration. */
485 static void
486 remove_empty_loop (struct loop *loop)
488 edge exit = single_dom_exit (loop), non_exit;
489 gimple cond_stmt = last_stmt (exit->src);
490 basic_block *body;
491 unsigned n_before, freq_in, freq_h;
492 gcov_type exit_count = exit->count;
494 if (dump_file)
495 fprintf (dump_file, "Removing empty loop %d\n", loop->num);
497 non_exit = EDGE_SUCC (exit->src, 0);
498 if (non_exit == exit)
499 non_exit = EDGE_SUCC (exit->src, 1);
501 if (exit->flags & EDGE_TRUE_VALUE)
502 gimple_cond_make_true (cond_stmt);
503 else
504 gimple_cond_make_false (cond_stmt);
505 update_stmt (cond_stmt);
507 /* Let us set the probabilities of the edges coming from the exit block. */
508 exit->probability = REG_BR_PROB_BASE;
509 non_exit->probability = 0;
510 non_exit->count = 0;
512 /* Update frequencies and counts. Everything before
513 the exit needs to be scaled FREQ_IN/FREQ_H times,
514 where FREQ_IN is the frequency of the entry edge
515 and FREQ_H is the frequency of the loop header.
516 Everything after the exit has zero frequency. */
517 freq_h = loop->header->frequency;
518 freq_in = EDGE_FREQUENCY (loop_preheader_edge (loop));
519 if (freq_h != 0)
521 body = get_loop_body_in_dom_order (loop);
522 for (n_before = 1; n_before <= loop->num_nodes; n_before++)
523 if (body[n_before - 1] == exit->src)
524 break;
525 scale_bbs_frequencies_int (body, n_before, freq_in, freq_h);
526 scale_bbs_frequencies_int (body + n_before, loop->num_nodes - n_before,
527 0, 1);
528 free (body);
531 /* Number of executions of exit is not changed, thus we need to restore
532 the original value. */
533 exit->count = exit_count;
536 /* Removes LOOP if it is empty. Returns true if LOOP is removed. CHANGED
537 is set to true if LOOP or any of its subloops is removed. */
539 static bool
540 try_remove_empty_loop (struct loop *loop, bool *changed)
542 bool nonempty_subloop = false;
543 struct loop *sub;
545 /* First, all subloops must be removed. */
546 for (sub = loop->inner; sub; sub = sub->next)
547 nonempty_subloop |= !try_remove_empty_loop (sub, changed);
549 if (nonempty_subloop || !empty_loop_p (loop))
550 return false;
552 remove_empty_loop (loop);
553 *changed = true;
554 return true;
557 /* Remove the empty loops. */
559 unsigned int
560 remove_empty_loops (void)
562 bool changed = false;
563 struct loop *loop;
565 for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
566 try_remove_empty_loop (loop, &changed);
568 if (changed)
570 scev_reset ();
571 return TODO_cleanup_cfg;
573 return 0;