1 /* Loop optimizations over tree-ssa.
2 Copyright (C) 2003-2013 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/>. */
22 #include "coretypes.h"
26 #include "basic-block.h"
27 #include "tree-flow.h"
28 #include "tree-pass.h"
31 #include "tree-inline.h"
32 #include "tree-scalar-evolution.h"
33 #include "diagnostic-core.h"
34 #include "tree-vectorizer.h"
36 /* The loop superpass. */
41 return flag_tree_loop_optimize != 0;
44 struct gimple_opt_pass pass_tree_loop =
49 OPTGROUP_LOOP, /* optinfo_flags */
50 gate_tree_loop, /* gate */
54 0, /* static_pass_number */
55 TV_TREE_LOOP, /* tv_id */
56 PROP_cfg, /* properties_required */
57 0, /* properties_provided */
58 0, /* properties_destroyed */
59 TODO_ggc_collect, /* todo_flags_start */
60 TODO_verify_ssa | TODO_ggc_collect /* todo_flags_finish */
64 /* Loop optimizer initialization. */
67 tree_ssa_loop_init (void)
69 loop_optimizer_init (LOOPS_NORMAL
70 | LOOPS_HAVE_RECORDED_EXITS);
71 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
73 /* We might discover new loops, e.g. when turning irreducible
74 regions into reducible. */
77 if (number_of_loops () <= 1)
83 struct gimple_opt_pass pass_tree_loop_init =
87 "loopinit", /* name */
88 OPTGROUP_LOOP, /* optinfo_flags */
90 tree_ssa_loop_init, /* execute */
93 0, /* static_pass_number */
95 PROP_cfg, /* properties_required */
96 PROP_loops, /* properties_provided */
97 0, /* properties_destroyed */
98 0, /* todo_flags_start */
99 0 /* todo_flags_finish */
103 /* Loop invariant motion pass. */
106 tree_ssa_loop_im (void)
108 if (number_of_loops () <= 1)
111 return tree_ssa_lim ();
115 gate_tree_ssa_loop_im (void)
117 return flag_tree_loop_im != 0;
120 struct gimple_opt_pass pass_lim =
125 OPTGROUP_LOOP, /* optinfo_flags */
126 gate_tree_ssa_loop_im, /* gate */
127 tree_ssa_loop_im, /* execute */
130 0, /* static_pass_number */
132 PROP_cfg, /* properties_required */
133 0, /* properties_provided */
134 0, /* properties_destroyed */
135 0, /* todo_flags_start */
136 0 /* todo_flags_finish */
140 /* Loop unswitching pass. */
143 tree_ssa_loop_unswitch (void)
145 if (number_of_loops () <= 1)
148 return tree_ssa_unswitch_loops ();
152 gate_tree_ssa_loop_unswitch (void)
154 return flag_unswitch_loops != 0;
157 struct gimple_opt_pass pass_tree_unswitch =
161 "unswitch", /* name */
162 OPTGROUP_LOOP, /* optinfo_flags */
163 gate_tree_ssa_loop_unswitch, /* gate */
164 tree_ssa_loop_unswitch, /* execute */
167 0, /* static_pass_number */
168 TV_TREE_LOOP_UNSWITCH, /* tv_id */
169 PROP_cfg, /* properties_required */
170 0, /* properties_provided */
171 0, /* properties_destroyed */
172 0, /* todo_flags_start */
173 TODO_ggc_collect /* todo_flags_finish */
177 /* Predictive commoning. */
180 run_tree_predictive_commoning (void)
185 return tree_predictive_commoning ();
189 gate_tree_predictive_commoning (void)
191 return flag_predictive_commoning != 0;
194 struct gimple_opt_pass pass_predcom =
199 OPTGROUP_LOOP, /* optinfo_flags */
200 gate_tree_predictive_commoning, /* gate */
201 run_tree_predictive_commoning, /* execute */
204 0, /* static_pass_number */
205 TV_PREDCOM, /* tv_id */
206 PROP_cfg, /* properties_required */
207 0, /* properties_provided */
208 0, /* properties_destroyed */
209 0, /* todo_flags_start */
210 TODO_update_ssa_only_virtuals /* todo_flags_finish */
214 /* Loop autovectorization. */
217 tree_vectorize (void)
219 if (number_of_loops () <= 1)
222 return vectorize_loops ();
226 gate_tree_vectorize (void)
228 return flag_tree_vectorize;
231 struct gimple_opt_pass pass_vectorize =
237 | OPTGROUP_VEC, /* optinfo_flags */
238 gate_tree_vectorize, /* gate */
239 tree_vectorize, /* execute */
242 0, /* static_pass_number */
243 TV_TREE_VECTORIZATION, /* tv_id */
244 PROP_cfg | PROP_ssa, /* properties_required */
245 0, /* properties_provided */
246 0, /* properties_destroyed */
247 0, /* todo_flags_start */
249 | TODO_ggc_collect /* todo_flags_finish */
253 /* GRAPHITE optimizations. */
256 graphite_transforms (void)
261 graphite_transform_loops ();
267 gate_graphite_transforms (void)
269 /* Enable -fgraphite pass if any one of the graphite optimization flags
272 || flag_loop_interchange
273 || flag_loop_strip_mine
274 || flag_graphite_identity
275 || flag_loop_parallelize_all
276 || flag_loop_optimize_isl)
279 return flag_graphite != 0;
282 struct gimple_opt_pass pass_graphite =
286 "graphite0", /* name */
287 OPTGROUP_LOOP, /* optinfo_flags */
288 gate_graphite_transforms, /* gate */
292 0, /* static_pass_number */
293 TV_GRAPHITE, /* tv_id */
294 PROP_cfg | PROP_ssa, /* properties_required */
295 0, /* properties_provided */
296 0, /* properties_destroyed */
297 0, /* todo_flags_start */
298 0 /* todo_flags_finish */
302 struct gimple_opt_pass pass_graphite_transforms =
306 "graphite", /* name */
307 OPTGROUP_LOOP, /* optinfo_flags */
308 gate_graphite_transforms, /* gate */
309 graphite_transforms, /* execute */
312 0, /* static_pass_number */
313 TV_GRAPHITE_TRANSFORMS, /* tv_id */
314 PROP_cfg | PROP_ssa, /* properties_required */
315 0, /* properties_provided */
316 0, /* properties_destroyed */
317 0, /* todo_flags_start */
318 0 /* todo_flags_finish */
322 /* Check the correctness of the data dependence analyzers. */
325 check_data_deps (void)
327 if (number_of_loops () <= 1)
330 tree_check_data_deps ();
335 gate_check_data_deps (void)
337 return flag_check_data_deps != 0;
340 struct gimple_opt_pass pass_check_data_deps =
345 OPTGROUP_LOOP, /* optinfo_flags */
346 gate_check_data_deps, /* gate */
347 check_data_deps, /* execute */
350 0, /* static_pass_number */
351 TV_CHECK_DATA_DEPS, /* tv_id */
352 PROP_cfg | PROP_ssa, /* properties_required */
353 0, /* properties_provided */
354 0, /* properties_destroyed */
355 0, /* todo_flags_start */
356 0 /* todo_flags_finish */
360 /* Canonical induction variable creation pass. */
363 tree_ssa_loop_ivcanon (void)
365 if (number_of_loops () <= 1)
368 return canonicalize_induction_variables ();
372 gate_tree_ssa_loop_ivcanon (void)
374 return flag_tree_loop_ivcanon != 0;
377 struct gimple_opt_pass pass_iv_canon =
381 "ivcanon", /* name */
382 OPTGROUP_LOOP, /* optinfo_flags */
383 gate_tree_ssa_loop_ivcanon, /* gate */
384 tree_ssa_loop_ivcanon, /* execute */
387 0, /* static_pass_number */
388 TV_TREE_LOOP_IVCANON, /* tv_id */
389 PROP_cfg | PROP_ssa, /* properties_required */
390 0, /* properties_provided */
391 0, /* properties_destroyed */
392 0, /* todo_flags_start */
393 0 /* todo_flags_finish */
397 /* Propagation of constants using scev. */
400 gate_scev_const_prop (void)
402 return flag_tree_scev_cprop;
405 struct gimple_opt_pass pass_scev_cprop =
410 OPTGROUP_LOOP, /* optinfo_flags */
411 gate_scev_const_prop, /* gate */
412 scev_const_prop, /* execute */
415 0, /* static_pass_number */
416 TV_SCEV_CONST, /* tv_id */
417 PROP_cfg | PROP_ssa, /* properties_required */
418 0, /* properties_provided */
419 0, /* properties_destroyed */
420 0, /* todo_flags_start */
422 | TODO_update_ssa_only_virtuals
423 /* todo_flags_finish */
427 /* Record bounds on numbers of iterations of loops. */
430 tree_ssa_loop_bounds (void)
432 if (number_of_loops () <= 1)
435 estimate_numbers_of_iterations ();
440 struct gimple_opt_pass pass_record_bounds =
444 "*record_bounds", /* name */
445 OPTGROUP_NONE, /* optinfo_flags */
447 tree_ssa_loop_bounds, /* execute */
450 0, /* static_pass_number */
451 TV_TREE_LOOP_BOUNDS, /* tv_id */
452 PROP_cfg | PROP_ssa, /* properties_required */
453 0, /* properties_provided */
454 0, /* properties_destroyed */
455 0, /* todo_flags_start */
456 0 /* todo_flags_finish */
460 /* Complete unrolling of loops. */
463 tree_complete_unroll (void)
465 if (number_of_loops () <= 1)
468 return tree_unroll_loops_completely (flag_unroll_loops
470 || optimize >= 3, true);
474 gate_tree_complete_unroll (void)
479 struct gimple_opt_pass pass_complete_unroll =
483 "cunroll", /* name */
484 OPTGROUP_LOOP, /* optinfo_flags */
485 gate_tree_complete_unroll, /* gate */
486 tree_complete_unroll, /* execute */
489 0, /* static_pass_number */
490 TV_COMPLETE_UNROLL, /* tv_id */
491 PROP_cfg | PROP_ssa, /* properties_required */
492 0, /* properties_provided */
493 0, /* properties_destroyed */
494 0, /* todo_flags_start */
495 TODO_ggc_collect /* todo_flags_finish */
499 /* Complete unrolling of inner loops. */
502 tree_complete_unroll_inner (void)
506 loop_optimizer_init (LOOPS_NORMAL
507 | LOOPS_HAVE_RECORDED_EXITS);
508 if (number_of_loops () > 1)
511 ret = tree_unroll_loops_completely (optimize >= 3, false);
512 free_numbers_of_iterations_estimates ();
515 loop_optimizer_finalize ();
521 gate_tree_complete_unroll_inner (void)
523 return optimize >= 2;
526 struct gimple_opt_pass pass_complete_unrolli =
530 "cunrolli", /* name */
531 OPTGROUP_LOOP, /* optinfo_flags */
532 gate_tree_complete_unroll_inner, /* gate */
533 tree_complete_unroll_inner, /* execute */
536 0, /* static_pass_number */
537 TV_COMPLETE_UNROLL, /* tv_id */
538 PROP_cfg | PROP_ssa, /* properties_required */
539 0, /* properties_provided */
540 0, /* properties_destroyed */
541 0, /* todo_flags_start */
543 | TODO_ggc_collect /* todo_flags_finish */
547 /* Parallelization. */
550 gate_tree_parallelize_loops (void)
552 return flag_tree_parallelize_loops > 1;
556 tree_parallelize_loops (void)
558 if (number_of_loops () <= 1)
561 if (parallelize_loops ())
562 return TODO_cleanup_cfg | TODO_rebuild_alias;
566 struct gimple_opt_pass pass_parallelize_loops =
570 "parloops", /* name */
571 OPTGROUP_LOOP, /* optinfo_flags */
572 gate_tree_parallelize_loops, /* gate */
573 tree_parallelize_loops, /* execute */
576 0, /* static_pass_number */
577 TV_TREE_PARALLELIZE_LOOPS, /* tv_id */
578 PROP_cfg | PROP_ssa, /* properties_required */
579 0, /* properties_provided */
580 0, /* properties_destroyed */
581 0, /* todo_flags_start */
582 0 /* todo_flags_finish */
589 tree_ssa_loop_prefetch (void)
591 if (number_of_loops () <= 1)
594 return tree_ssa_prefetch_arrays ();
598 gate_tree_ssa_loop_prefetch (void)
600 return flag_prefetch_loop_arrays > 0;
603 struct gimple_opt_pass pass_loop_prefetch =
607 "aprefetch", /* name */
608 OPTGROUP_LOOP, /* optinfo_flags */
609 gate_tree_ssa_loop_prefetch, /* gate */
610 tree_ssa_loop_prefetch, /* execute */
613 0, /* static_pass_number */
614 TV_TREE_PREFETCH, /* tv_id */
615 PROP_cfg | PROP_ssa, /* properties_required */
616 0, /* properties_provided */
617 0, /* properties_destroyed */
618 0, /* todo_flags_start */
619 0 /* todo_flags_finish */
623 /* Induction variable optimizations. */
626 tree_ssa_loop_ivopts (void)
628 if (number_of_loops () <= 1)
631 tree_ssa_iv_optimize ();
636 gate_tree_ssa_loop_ivopts (void)
638 return flag_ivopts != 0;
641 struct gimple_opt_pass pass_iv_optimize =
646 OPTGROUP_LOOP, /* optinfo_flags */
647 gate_tree_ssa_loop_ivopts, /* gate */
648 tree_ssa_loop_ivopts, /* execute */
651 0, /* static_pass_number */
652 TV_TREE_LOOP_IVOPTS, /* tv_id */
653 PROP_cfg | PROP_ssa, /* properties_required */
654 0, /* properties_provided */
655 0, /* properties_destroyed */
656 0, /* todo_flags_start */
657 TODO_update_ssa | TODO_ggc_collect /* todo_flags_finish */
661 /* Loop optimizer finalization. */
664 tree_ssa_loop_done (void)
666 free_numbers_of_iterations_estimates ();
668 loop_optimizer_finalize ();
672 struct gimple_opt_pass pass_tree_loop_done =
676 "loopdone", /* name */
677 OPTGROUP_LOOP, /* optinfo_flags */
679 tree_ssa_loop_done, /* execute */
682 0, /* static_pass_number */
684 PROP_cfg, /* properties_required */
685 0, /* properties_provided */
686 0, /* properties_destroyed */
687 0, /* todo_flags_start */
689 | TODO_verify_flow /* todo_flags_finish */