1 /* Loop optimizations over tree-ssa.
2 Copyright (C) 2003, 2005, 2006, 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/>. */
22 #include "coretypes.h"
27 #include "hard-reg-set.h"
28 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #include "tree-dump.h"
33 #include "tree-pass.h"
37 #include "tree-inline.h"
38 #include "tree-scalar-evolution.h"
40 #include "tree-vectorizer.h"
42 /* The loop superpass. */
47 return flag_tree_loop_optimize != 0;
50 struct gimple_opt_pass pass_tree_loop =
55 gate_tree_loop, /* gate */
59 0, /* static_pass_number */
60 TV_TREE_LOOP, /* tv_id */
61 PROP_cfg, /* properties_required */
62 0, /* properties_provided */
63 0, /* properties_destroyed */
64 TODO_ggc_collect, /* todo_flags_start */
65 TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect /* todo_flags_finish */
69 /* Loop optimizer initialization. */
72 tree_ssa_loop_init (void)
74 loop_optimizer_init (LOOPS_NORMAL
75 | LOOPS_HAVE_RECORDED_EXITS);
76 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
78 if (number_of_loops () <= 1)
85 struct gimple_opt_pass pass_tree_loop_init =
89 "loopinit", /* name */
91 tree_ssa_loop_init, /* execute */
94 0, /* static_pass_number */
95 TV_TREE_LOOP_INIT, /* tv_id */
96 PROP_cfg, /* properties_required */
97 0, /* properties_provided */
98 0, /* properties_destroyed */
99 0, /* todo_flags_start */
100 TODO_dump_func | TODO_verify_loops /* todo_flags_finish */
104 /* Loop invariant motion pass. */
107 tree_ssa_loop_im (void)
109 if (number_of_loops () <= 1)
117 gate_tree_ssa_loop_im (void)
119 return flag_tree_loop_im != 0;
122 struct gimple_opt_pass pass_lim =
127 gate_tree_ssa_loop_im, /* gate */
128 tree_ssa_loop_im, /* execute */
131 0, /* static_pass_number */
133 PROP_cfg, /* properties_required */
134 0, /* properties_provided */
135 0, /* properties_destroyed */
136 0, /* todo_flags_start */
137 TODO_dump_func | TODO_verify_loops /* todo_flags_finish */
141 /* Loop unswitching pass. */
144 tree_ssa_loop_unswitch (void)
146 if (number_of_loops () <= 1)
149 return tree_ssa_unswitch_loops ();
153 gate_tree_ssa_loop_unswitch (void)
155 return flag_unswitch_loops != 0;
158 struct gimple_opt_pass pass_tree_unswitch =
162 "unswitch", /* name */
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_dump_func
174 | TODO_verify_loops /* todo_flags_finish */
178 /* Predictive commoning. */
181 run_tree_predictive_commoning (void)
186 tree_predictive_commoning ();
191 gate_tree_predictive_commoning (void)
193 return flag_predictive_commoning != 0;
196 struct gimple_opt_pass pass_predcom =
201 gate_tree_predictive_commoning, /* gate */
202 run_tree_predictive_commoning, /* execute */
205 0, /* static_pass_number */
206 TV_PREDCOM, /* tv_id */
207 PROP_cfg, /* properties_required */
208 0, /* properties_provided */
209 0, /* properties_destroyed */
210 0, /* todo_flags_start */
211 TODO_dump_func | TODO_verify_loops
212 | TODO_update_ssa_only_virtuals /* todo_flags_finish */
216 /* Loop autovectorization. */
219 tree_vectorize (void)
221 if (number_of_loops () <= 1)
224 return vectorize_loops ();
228 gate_tree_vectorize (void)
230 return flag_tree_vectorize;
233 struct gimple_opt_pass pass_vectorize =
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 TODO_verify_loops, /* todo_flags_start */
248 TODO_dump_func | TODO_update_ssa
249 | TODO_ggc_collect /* todo_flags_finish */
253 /* Loop nest optimizations. */
256 tree_linear_transform (void)
258 if (number_of_loops () <= 1)
261 linear_transform_loops ();
266 gate_tree_linear_transform (void)
268 return flag_tree_loop_linear != 0;
271 struct gimple_opt_pass pass_linear_transform =
276 gate_tree_linear_transform, /* gate */
277 tree_linear_transform, /* execute */
280 0, /* static_pass_number */
281 TV_TREE_LINEAR_TRANSFORM, /* tv_id */
282 PROP_cfg | PROP_ssa, /* properties_required */
283 0, /* properties_provided */
284 0, /* properties_destroyed */
285 0, /* todo_flags_start */
286 TODO_dump_func | TODO_verify_loops
287 | TODO_update_ssa_only_virtuals
288 | TODO_ggc_collect /* todo_flags_finish */
292 /* GRAPHITE optimizations. */
295 graphite_transforms (void)
300 graphite_transform_loops ();
306 gate_graphite_transforms (void)
308 /* Enable -fgraphite pass if any one of the graphite optimization flags
310 if (flag_loop_block || flag_loop_interchange || flag_loop_strip_mine
311 || flag_graphite_identity || flag_graphite_force_parallel)
315 sorry ("loop blocking not implemented");
317 return flag_graphite != 0;
320 struct gimple_opt_pass pass_graphite_transforms =
324 "graphite", /* name */
325 gate_graphite_transforms, /* gate */
326 graphite_transforms, /* execute */
329 0, /* static_pass_number */
330 TV_GRAPHITE_TRANSFORMS, /* tv_id */
331 PROP_cfg | PROP_ssa, /* properties_required */
332 0, /* properties_provided */
333 0, /* properties_destroyed */
334 0, /* todo_flags_start */
335 TODO_verify_loops /* todo_flags_finish */
339 /* Check the correctness of the data dependence analyzers. */
342 check_data_deps (void)
344 if (number_of_loops () <= 1)
347 tree_check_data_deps ();
352 gate_check_data_deps (void)
354 return flag_check_data_deps != 0;
357 struct gimple_opt_pass pass_check_data_deps =
362 gate_check_data_deps, /* gate */
363 check_data_deps, /* execute */
366 0, /* static_pass_number */
367 TV_CHECK_DATA_DEPS, /* tv_id */
368 PROP_cfg | PROP_ssa, /* properties_required */
369 0, /* properties_provided */
370 0, /* properties_destroyed */
371 0, /* todo_flags_start */
372 TODO_dump_func /* todo_flags_finish */
376 /* Canonical induction variable creation pass. */
379 tree_ssa_loop_ivcanon (void)
381 if (number_of_loops () <= 1)
384 return canonicalize_induction_variables ();
388 gate_tree_ssa_loop_ivcanon (void)
390 return flag_tree_loop_ivcanon != 0;
393 struct gimple_opt_pass pass_iv_canon =
397 "ivcanon", /* name */
398 gate_tree_ssa_loop_ivcanon, /* gate */
399 tree_ssa_loop_ivcanon, /* execute */
402 0, /* static_pass_number */
403 TV_TREE_LOOP_IVCANON, /* tv_id */
404 PROP_cfg | PROP_ssa, /* properties_required */
405 0, /* properties_provided */
406 0, /* properties_destroyed */
407 0, /* todo_flags_start */
408 TODO_dump_func | TODO_verify_loops /* todo_flags_finish */
412 /* Propagation of constants using scev. */
415 gate_scev_const_prop (void)
417 return flag_tree_scev_cprop;
420 struct gimple_opt_pass pass_scev_cprop =
425 gate_scev_const_prop, /* gate */
426 scev_const_prop, /* execute */
429 0, /* static_pass_number */
430 TV_SCEV_CONST, /* tv_id */
431 PROP_cfg | PROP_ssa, /* properties_required */
432 0, /* properties_provided */
433 0, /* properties_destroyed */
434 0, /* todo_flags_start */
435 TODO_dump_func | TODO_cleanup_cfg
436 | TODO_update_ssa_only_virtuals
437 /* todo_flags_finish */
441 /* Record bounds on numbers of iterations of loops. */
444 tree_ssa_loop_bounds (void)
446 if (number_of_loops () <= 1)
449 estimate_numbers_of_iterations ();
454 struct gimple_opt_pass pass_record_bounds =
460 tree_ssa_loop_bounds, /* execute */
463 0, /* static_pass_number */
464 TV_TREE_LOOP_BOUNDS, /* tv_id */
465 PROP_cfg | PROP_ssa, /* properties_required */
466 0, /* properties_provided */
467 0, /* properties_destroyed */
468 0, /* todo_flags_start */
469 0 /* todo_flags_finish */
473 /* Complete unrolling of loops. */
476 tree_complete_unroll (void)
478 if (number_of_loops () <= 1)
481 return tree_unroll_loops_completely (flag_unroll_loops
483 || optimize >= 3, true);
487 gate_tree_complete_unroll (void)
492 struct gimple_opt_pass pass_complete_unroll =
496 "cunroll", /* name */
497 gate_tree_complete_unroll, /* gate */
498 tree_complete_unroll, /* execute */
501 0, /* static_pass_number */
502 TV_COMPLETE_UNROLL, /* tv_id */
503 PROP_cfg | PROP_ssa, /* properties_required */
504 0, /* properties_provided */
505 0, /* properties_destroyed */
506 0, /* todo_flags_start */
507 TODO_dump_func | TODO_verify_loops
508 | TODO_ggc_collect /* todo_flags_finish */
512 /* Complete unrolling of inner loops. */
515 tree_complete_unroll_inner (void)
519 loop_optimizer_init (LOOPS_NORMAL
520 | LOOPS_HAVE_RECORDED_EXITS);
521 if (number_of_loops () > 1)
524 ret = tree_unroll_loops_completely (optimize >= 3, false);
525 free_numbers_of_iterations_estimates ();
528 loop_optimizer_finalize ();
534 gate_tree_complete_unroll_inner (void)
536 return optimize >= 2;
539 struct gimple_opt_pass pass_complete_unrolli =
543 "cunrolli", /* name */
544 gate_tree_complete_unroll_inner, /* gate */
545 tree_complete_unroll_inner, /* execute */
548 0, /* static_pass_number */
549 TV_COMPLETE_UNROLL, /* tv_id */
550 PROP_cfg | PROP_ssa, /* properties_required */
551 0, /* properties_provided */
552 0, /* properties_destroyed */
553 0, /* todo_flags_start */
554 TODO_dump_func | TODO_verify_loops
555 | TODO_ggc_collect /* todo_flags_finish */
559 /* Parallelization. */
562 gate_tree_parallelize_loops (void)
564 return flag_tree_parallelize_loops > 1;
568 tree_parallelize_loops (void)
570 if (number_of_loops () <= 1)
573 if (parallelize_loops ())
574 return TODO_cleanup_cfg | TODO_rebuild_alias;
578 struct gimple_opt_pass pass_parallelize_loops =
582 "parloops", /* name */
583 gate_tree_parallelize_loops, /* gate */
584 tree_parallelize_loops, /* execute */
587 0, /* static_pass_number */
588 TV_TREE_PARALLELIZE_LOOPS, /* tv_id */
589 PROP_cfg | PROP_ssa, /* properties_required */
590 0, /* properties_provided */
591 0, /* properties_destroyed */
592 0, /* todo_flags_start */
593 TODO_dump_func | TODO_verify_loops /* todo_flags_finish */
600 tree_ssa_loop_prefetch (void)
602 if (number_of_loops () <= 1)
605 return tree_ssa_prefetch_arrays ();
609 gate_tree_ssa_loop_prefetch (void)
611 return flag_prefetch_loop_arrays != 0;
614 struct gimple_opt_pass pass_loop_prefetch =
618 "aprefetch", /* name */
619 gate_tree_ssa_loop_prefetch, /* gate */
620 tree_ssa_loop_prefetch, /* execute */
623 0, /* static_pass_number */
624 TV_TREE_PREFETCH, /* tv_id */
625 PROP_cfg | PROP_ssa, /* properties_required */
626 0, /* properties_provided */
627 0, /* properties_destroyed */
628 0, /* todo_flags_start */
629 TODO_dump_func | TODO_verify_loops /* todo_flags_finish */
633 /* Induction variable optimizations. */
636 tree_ssa_loop_ivopts (void)
638 if (number_of_loops () <= 1)
641 tree_ssa_iv_optimize ();
646 gate_tree_ssa_loop_ivopts (void)
648 return flag_ivopts != 0;
651 struct gimple_opt_pass pass_iv_optimize =
656 gate_tree_ssa_loop_ivopts, /* gate */
657 tree_ssa_loop_ivopts, /* execute */
660 0, /* static_pass_number */
661 TV_TREE_LOOP_IVOPTS, /* tv_id */
662 PROP_cfg | PROP_ssa, /* properties_required */
663 0, /* properties_provided */
664 0, /* properties_destroyed */
665 0, /* todo_flags_start */
666 TODO_dump_func | TODO_verify_loops
667 | TODO_update_ssa | TODO_ggc_collect /* todo_flags_finish */
671 /* Loop optimizer finalization. */
674 tree_ssa_loop_done (void)
676 free_numbers_of_iterations_estimates ();
678 loop_optimizer_finalize ();
682 struct gimple_opt_pass pass_tree_loop_done =
686 "loopdone", /* name */
688 tree_ssa_loop_done, /* execute */
691 0, /* static_pass_number */
692 TV_TREE_LOOP_FINI, /* tv_id */
693 PROP_cfg, /* properties_required */
694 0, /* properties_provided */
695 0, /* properties_destroyed */
696 0, /* todo_flags_start */
697 TODO_cleanup_cfg | TODO_dump_func /* todo_flags_finish */