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"
26 #include "basic-block.h"
28 #include "tree-flow.h"
29 #include "tree-dump.h"
30 #include "tree-pass.h"
34 #include "tree-inline.h"
35 #include "tree-scalar-evolution.h"
37 #include "tree-vectorizer.h"
39 /* The loop superpass. */
44 return flag_tree_loop_optimize != 0;
47 struct gimple_opt_pass pass_tree_loop =
52 gate_tree_loop, /* gate */
56 0, /* static_pass_number */
57 TV_TREE_LOOP, /* tv_id */
58 PROP_cfg, /* properties_required */
59 0, /* properties_provided */
60 0, /* properties_destroyed */
61 TODO_ggc_collect, /* todo_flags_start */
62 TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect /* todo_flags_finish */
66 /* Loop optimizer initialization. */
69 tree_ssa_loop_init (void)
71 loop_optimizer_init (LOOPS_NORMAL
72 | LOOPS_HAVE_RECORDED_EXITS);
73 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
75 if (number_of_loops () <= 1)
82 struct gimple_opt_pass pass_tree_loop_init =
86 "loopinit", /* name */
88 tree_ssa_loop_init, /* execute */
91 0, /* static_pass_number */
92 TV_TREE_LOOP_INIT, /* tv_id */
93 PROP_cfg, /* properties_required */
94 0, /* properties_provided */
95 0, /* properties_destroyed */
96 0, /* todo_flags_start */
97 TODO_dump_func /* todo_flags_finish */
101 /* Loop invariant motion pass. */
104 tree_ssa_loop_im (void)
106 if (number_of_loops () <= 1)
109 return tree_ssa_lim ();
113 gate_tree_ssa_loop_im (void)
115 return flag_tree_loop_im != 0;
118 struct gimple_opt_pass pass_lim =
123 gate_tree_ssa_loop_im, /* gate */
124 tree_ssa_loop_im, /* execute */
127 0, /* static_pass_number */
129 PROP_cfg, /* properties_required */
130 0, /* properties_provided */
131 0, /* properties_destroyed */
132 0, /* todo_flags_start */
133 TODO_dump_func /* todo_flags_finish */
137 /* Loop unswitching pass. */
140 tree_ssa_loop_unswitch (void)
142 if (number_of_loops () <= 1)
145 return tree_ssa_unswitch_loops ();
149 gate_tree_ssa_loop_unswitch (void)
151 return flag_unswitch_loops != 0;
154 struct gimple_opt_pass pass_tree_unswitch =
158 "unswitch", /* name */
159 gate_tree_ssa_loop_unswitch, /* gate */
160 tree_ssa_loop_unswitch, /* execute */
163 0, /* static_pass_number */
164 TV_TREE_LOOP_UNSWITCH, /* tv_id */
165 PROP_cfg, /* properties_required */
166 0, /* properties_provided */
167 0, /* properties_destroyed */
168 0, /* todo_flags_start */
169 TODO_ggc_collect | TODO_dump_func /* todo_flags_finish */
173 /* Predictive commoning. */
176 run_tree_predictive_commoning (void)
181 tree_predictive_commoning ();
186 gate_tree_predictive_commoning (void)
188 return flag_predictive_commoning != 0;
191 struct gimple_opt_pass pass_predcom =
196 gate_tree_predictive_commoning, /* gate */
197 run_tree_predictive_commoning, /* execute */
200 0, /* static_pass_number */
201 TV_PREDCOM, /* tv_id */
202 PROP_cfg, /* properties_required */
203 0, /* properties_provided */
204 0, /* properties_destroyed */
205 0, /* todo_flags_start */
207 | TODO_update_ssa_only_virtuals /* todo_flags_finish */
211 /* Loop autovectorization. */
214 tree_vectorize (void)
216 if (number_of_loops () <= 1)
219 return vectorize_loops ();
223 gate_tree_vectorize (void)
225 return flag_tree_vectorize;
228 struct gimple_opt_pass pass_vectorize =
233 gate_tree_vectorize, /* gate */
234 tree_vectorize, /* execute */
237 0, /* static_pass_number */
238 TV_TREE_VECTORIZATION, /* tv_id */
239 PROP_cfg | PROP_ssa, /* properties_required */
240 0, /* properties_provided */
241 0, /* properties_destroyed */
242 0, /* todo_flags_start */
243 TODO_dump_func | TODO_update_ssa
244 | TODO_ggc_collect /* todo_flags_finish */
248 /* Loop nest optimizations. */
251 tree_linear_transform (void)
253 if (number_of_loops () <= 1)
256 linear_transform_loops ();
261 gate_tree_linear_transform (void)
263 return flag_tree_loop_linear != 0;
266 struct gimple_opt_pass pass_linear_transform =
271 gate_tree_linear_transform, /* gate */
272 tree_linear_transform, /* execute */
275 0, /* static_pass_number */
276 TV_TREE_LINEAR_TRANSFORM, /* tv_id */
277 PROP_cfg | PROP_ssa, /* properties_required */
278 0, /* properties_provided */
279 0, /* properties_destroyed */
280 0, /* todo_flags_start */
282 | TODO_update_ssa_only_virtuals
283 | TODO_ggc_collect /* todo_flags_finish */
287 /* GRAPHITE optimizations. */
290 graphite_transforms (void)
295 graphite_transform_loops ();
301 gate_graphite_transforms (void)
303 /* Enable -fgraphite pass if any one of the graphite optimization flags
305 if (flag_loop_block || flag_loop_interchange || flag_loop_strip_mine
306 || flag_graphite_identity || flag_loop_parallelize_all)
309 return flag_graphite != 0;
312 struct gimple_opt_pass pass_graphite_transforms =
316 "graphite", /* name */
317 gate_graphite_transforms, /* gate */
318 graphite_transforms, /* execute */
321 0, /* static_pass_number */
322 TV_GRAPHITE_TRANSFORMS, /* tv_id */
323 PROP_cfg | PROP_ssa, /* properties_required */
324 0, /* properties_provided */
325 0, /* properties_destroyed */
326 0, /* todo_flags_start */
327 0 /* todo_flags_finish */
331 /* Check the correctness of the data dependence analyzers. */
334 check_data_deps (void)
336 if (number_of_loops () <= 1)
339 tree_check_data_deps ();
344 gate_check_data_deps (void)
346 return flag_check_data_deps != 0;
349 struct gimple_opt_pass pass_check_data_deps =
354 gate_check_data_deps, /* gate */
355 check_data_deps, /* execute */
358 0, /* static_pass_number */
359 TV_CHECK_DATA_DEPS, /* tv_id */
360 PROP_cfg | PROP_ssa, /* properties_required */
361 0, /* properties_provided */
362 0, /* properties_destroyed */
363 0, /* todo_flags_start */
364 TODO_dump_func /* todo_flags_finish */
368 /* Canonical induction variable creation pass. */
371 tree_ssa_loop_ivcanon (void)
373 if (number_of_loops () <= 1)
376 return canonicalize_induction_variables ();
380 gate_tree_ssa_loop_ivcanon (void)
382 return flag_tree_loop_ivcanon != 0;
385 struct gimple_opt_pass pass_iv_canon =
389 "ivcanon", /* name */
390 gate_tree_ssa_loop_ivcanon, /* gate */
391 tree_ssa_loop_ivcanon, /* execute */
394 0, /* static_pass_number */
395 TV_TREE_LOOP_IVCANON, /* tv_id */
396 PROP_cfg | PROP_ssa, /* properties_required */
397 0, /* properties_provided */
398 0, /* properties_destroyed */
399 0, /* todo_flags_start */
400 TODO_dump_func /* todo_flags_finish */
404 /* Propagation of constants using scev. */
407 gate_scev_const_prop (void)
409 return flag_tree_scev_cprop;
412 struct gimple_opt_pass pass_scev_cprop =
417 gate_scev_const_prop, /* gate */
418 scev_const_prop, /* execute */
421 0, /* static_pass_number */
422 TV_SCEV_CONST, /* tv_id */
423 PROP_cfg | PROP_ssa, /* properties_required */
424 0, /* properties_provided */
425 0, /* properties_destroyed */
426 0, /* todo_flags_start */
427 TODO_dump_func | TODO_cleanup_cfg
428 | TODO_update_ssa_only_virtuals
429 /* todo_flags_finish */
433 /* Record bounds on numbers of iterations of loops. */
436 tree_ssa_loop_bounds (void)
438 if (number_of_loops () <= 1)
441 estimate_numbers_of_iterations ();
446 struct gimple_opt_pass pass_record_bounds =
450 "*record_bounds", /* name */
452 tree_ssa_loop_bounds, /* execute */
455 0, /* static_pass_number */
456 TV_TREE_LOOP_BOUNDS, /* tv_id */
457 PROP_cfg | PROP_ssa, /* properties_required */
458 0, /* properties_provided */
459 0, /* properties_destroyed */
460 0, /* todo_flags_start */
461 0 /* todo_flags_finish */
465 /* Complete unrolling of loops. */
468 tree_complete_unroll (void)
470 if (number_of_loops () <= 1)
473 return tree_unroll_loops_completely (flag_unroll_loops
475 || optimize >= 3, true);
479 gate_tree_complete_unroll (void)
484 struct gimple_opt_pass pass_complete_unroll =
488 "cunroll", /* name */
489 gate_tree_complete_unroll, /* gate */
490 tree_complete_unroll, /* execute */
493 0, /* static_pass_number */
494 TV_COMPLETE_UNROLL, /* tv_id */
495 PROP_cfg | PROP_ssa, /* properties_required */
496 0, /* properties_provided */
497 0, /* properties_destroyed */
498 0, /* todo_flags_start */
500 | TODO_ggc_collect /* todo_flags_finish */
504 /* Complete unrolling of inner loops. */
507 tree_complete_unroll_inner (void)
511 loop_optimizer_init (LOOPS_NORMAL
512 | LOOPS_HAVE_RECORDED_EXITS);
513 if (number_of_loops () > 1)
516 ret = tree_unroll_loops_completely (optimize >= 3, false);
517 free_numbers_of_iterations_estimates ();
520 loop_optimizer_finalize ();
526 gate_tree_complete_unroll_inner (void)
528 return optimize >= 2;
531 struct gimple_opt_pass pass_complete_unrolli =
535 "cunrolli", /* name */
536 gate_tree_complete_unroll_inner, /* gate */
537 tree_complete_unroll_inner, /* execute */
540 0, /* static_pass_number */
541 TV_COMPLETE_UNROLL, /* tv_id */
542 PROP_cfg | PROP_ssa, /* properties_required */
543 0, /* properties_provided */
544 0, /* properties_destroyed */
545 0, /* todo_flags_start */
547 | TODO_ggc_collect /* todo_flags_finish */
551 /* Parallelization. */
554 gate_tree_parallelize_loops (void)
556 return flag_tree_parallelize_loops > 1;
560 tree_parallelize_loops (void)
562 if (number_of_loops () <= 1)
565 if (parallelize_loops ())
566 return TODO_cleanup_cfg | TODO_rebuild_alias;
570 struct gimple_opt_pass pass_parallelize_loops =
574 "parloops", /* name */
575 gate_tree_parallelize_loops, /* gate */
576 tree_parallelize_loops, /* execute */
579 0, /* static_pass_number */
580 TV_TREE_PARALLELIZE_LOOPS, /* tv_id */
581 PROP_cfg | PROP_ssa, /* properties_required */
582 0, /* properties_provided */
583 0, /* properties_destroyed */
584 0, /* todo_flags_start */
585 TODO_dump_func /* todo_flags_finish */
592 tree_ssa_loop_prefetch (void)
594 if (number_of_loops () <= 1)
597 return tree_ssa_prefetch_arrays ();
601 gate_tree_ssa_loop_prefetch (void)
603 return flag_prefetch_loop_arrays > 0;
606 struct gimple_opt_pass pass_loop_prefetch =
610 "aprefetch", /* name */
611 gate_tree_ssa_loop_prefetch, /* gate */
612 tree_ssa_loop_prefetch, /* execute */
615 0, /* static_pass_number */
616 TV_TREE_PREFETCH, /* tv_id */
617 PROP_cfg | PROP_ssa, /* properties_required */
618 0, /* properties_provided */
619 0, /* properties_destroyed */
620 0, /* todo_flags_start */
621 TODO_dump_func /* todo_flags_finish */
625 /* Induction variable optimizations. */
628 tree_ssa_loop_ivopts (void)
630 if (number_of_loops () <= 1)
633 tree_ssa_iv_optimize ();
638 gate_tree_ssa_loop_ivopts (void)
640 return flag_ivopts != 0;
643 struct gimple_opt_pass pass_iv_optimize =
648 gate_tree_ssa_loop_ivopts, /* gate */
649 tree_ssa_loop_ivopts, /* execute */
652 0, /* static_pass_number */
653 TV_TREE_LOOP_IVOPTS, /* tv_id */
654 PROP_cfg | PROP_ssa, /* properties_required */
655 0, /* properties_provided */
656 0, /* properties_destroyed */
657 0, /* todo_flags_start */
658 TODO_dump_func | TODO_update_ssa | TODO_ggc_collect /* todo_flags_finish */
662 /* Loop optimizer finalization. */
665 tree_ssa_loop_done (void)
667 free_numbers_of_iterations_estimates ();
669 loop_optimizer_finalize ();
673 struct gimple_opt_pass pass_tree_loop_done =
677 "loopdone", /* name */
679 tree_ssa_loop_done, /* execute */
682 0, /* static_pass_number */
683 TV_TREE_LOOP_FINI, /* tv_id */
684 PROP_cfg, /* properties_required */
685 0, /* properties_provided */
686 0, /* properties_destroyed */
687 0, /* todo_flags_start */
688 TODO_cleanup_cfg | TODO_dump_func /* todo_flags_finish */