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_loop_parallelize_all)
314 return flag_graphite != 0;
317 struct gimple_opt_pass pass_graphite_transforms =
321 "graphite", /* name */
322 gate_graphite_transforms, /* gate */
323 graphite_transforms, /* execute */
326 0, /* static_pass_number */
327 TV_GRAPHITE_TRANSFORMS, /* tv_id */
328 PROP_cfg | PROP_ssa, /* properties_required */
329 0, /* properties_provided */
330 0, /* properties_destroyed */
331 0, /* todo_flags_start */
332 TODO_verify_loops /* todo_flags_finish */
336 /* Check the correctness of the data dependence analyzers. */
339 check_data_deps (void)
341 if (number_of_loops () <= 1)
344 tree_check_data_deps ();
349 gate_check_data_deps (void)
351 return flag_check_data_deps != 0;
354 struct gimple_opt_pass pass_check_data_deps =
359 gate_check_data_deps, /* gate */
360 check_data_deps, /* execute */
363 0, /* static_pass_number */
364 TV_CHECK_DATA_DEPS, /* tv_id */
365 PROP_cfg | PROP_ssa, /* properties_required */
366 0, /* properties_provided */
367 0, /* properties_destroyed */
368 0, /* todo_flags_start */
369 TODO_dump_func /* todo_flags_finish */
373 /* Canonical induction variable creation pass. */
376 tree_ssa_loop_ivcanon (void)
378 if (number_of_loops () <= 1)
381 return canonicalize_induction_variables ();
385 gate_tree_ssa_loop_ivcanon (void)
387 return flag_tree_loop_ivcanon != 0;
390 struct gimple_opt_pass pass_iv_canon =
394 "ivcanon", /* name */
395 gate_tree_ssa_loop_ivcanon, /* gate */
396 tree_ssa_loop_ivcanon, /* execute */
399 0, /* static_pass_number */
400 TV_TREE_LOOP_IVCANON, /* tv_id */
401 PROP_cfg | PROP_ssa, /* properties_required */
402 0, /* properties_provided */
403 0, /* properties_destroyed */
404 0, /* todo_flags_start */
405 TODO_dump_func | TODO_verify_loops /* todo_flags_finish */
409 /* Propagation of constants using scev. */
412 gate_scev_const_prop (void)
414 return flag_tree_scev_cprop;
417 struct gimple_opt_pass pass_scev_cprop =
422 gate_scev_const_prop, /* gate */
423 scev_const_prop, /* execute */
426 0, /* static_pass_number */
427 TV_SCEV_CONST, /* tv_id */
428 PROP_cfg | PROP_ssa, /* properties_required */
429 0, /* properties_provided */
430 0, /* properties_destroyed */
431 0, /* todo_flags_start */
432 TODO_dump_func | TODO_cleanup_cfg
433 | TODO_update_ssa_only_virtuals
434 /* todo_flags_finish */
438 /* Record bounds on numbers of iterations of loops. */
441 tree_ssa_loop_bounds (void)
443 if (number_of_loops () <= 1)
446 estimate_numbers_of_iterations ();
451 struct gimple_opt_pass pass_record_bounds =
455 "*record_bounds", /* name */
457 tree_ssa_loop_bounds, /* execute */
460 0, /* static_pass_number */
461 TV_TREE_LOOP_BOUNDS, /* tv_id */
462 PROP_cfg | PROP_ssa, /* properties_required */
463 0, /* properties_provided */
464 0, /* properties_destroyed */
465 0, /* todo_flags_start */
466 0 /* todo_flags_finish */
470 /* Complete unrolling of loops. */
473 tree_complete_unroll (void)
475 if (number_of_loops () <= 1)
478 return tree_unroll_loops_completely (flag_unroll_loops
480 || optimize >= 3, true);
484 gate_tree_complete_unroll (void)
489 struct gimple_opt_pass pass_complete_unroll =
493 "cunroll", /* name */
494 gate_tree_complete_unroll, /* gate */
495 tree_complete_unroll, /* execute */
498 0, /* static_pass_number */
499 TV_COMPLETE_UNROLL, /* tv_id */
500 PROP_cfg | PROP_ssa, /* properties_required */
501 0, /* properties_provided */
502 0, /* properties_destroyed */
503 0, /* todo_flags_start */
504 TODO_dump_func | TODO_verify_loops
505 | TODO_ggc_collect /* todo_flags_finish */
509 /* Complete unrolling of inner loops. */
512 tree_complete_unroll_inner (void)
516 loop_optimizer_init (LOOPS_NORMAL
517 | LOOPS_HAVE_RECORDED_EXITS);
518 if (number_of_loops () > 1)
521 ret = tree_unroll_loops_completely (optimize >= 3, false);
522 free_numbers_of_iterations_estimates ();
525 loop_optimizer_finalize ();
531 gate_tree_complete_unroll_inner (void)
533 return optimize >= 2;
536 struct gimple_opt_pass pass_complete_unrolli =
540 "cunrolli", /* name */
541 gate_tree_complete_unroll_inner, /* gate */
542 tree_complete_unroll_inner, /* execute */
545 0, /* static_pass_number */
546 TV_COMPLETE_UNROLL, /* tv_id */
547 PROP_cfg | PROP_ssa, /* properties_required */
548 0, /* properties_provided */
549 0, /* properties_destroyed */
550 0, /* todo_flags_start */
551 TODO_dump_func | TODO_verify_loops
552 | TODO_ggc_collect /* todo_flags_finish */
556 /* Parallelization. */
559 gate_tree_parallelize_loops (void)
561 return flag_tree_parallelize_loops > 1;
565 tree_parallelize_loops (void)
567 if (number_of_loops () <= 1)
570 if (parallelize_loops ())
571 return TODO_cleanup_cfg | TODO_rebuild_alias;
575 struct gimple_opt_pass pass_parallelize_loops =
579 "parloops", /* name */
580 gate_tree_parallelize_loops, /* gate */
581 tree_parallelize_loops, /* execute */
584 0, /* static_pass_number */
585 TV_TREE_PARALLELIZE_LOOPS, /* tv_id */
586 PROP_cfg | PROP_ssa, /* properties_required */
587 0, /* properties_provided */
588 0, /* properties_destroyed */
589 0, /* todo_flags_start */
590 TODO_dump_func | TODO_verify_loops /* todo_flags_finish */
597 tree_ssa_loop_prefetch (void)
599 if (number_of_loops () <= 1)
602 return tree_ssa_prefetch_arrays ();
606 gate_tree_ssa_loop_prefetch (void)
608 return flag_prefetch_loop_arrays != 0;
611 struct gimple_opt_pass pass_loop_prefetch =
615 "aprefetch", /* name */
616 gate_tree_ssa_loop_prefetch, /* gate */
617 tree_ssa_loop_prefetch, /* execute */
620 0, /* static_pass_number */
621 TV_TREE_PREFETCH, /* tv_id */
622 PROP_cfg | PROP_ssa, /* properties_required */
623 0, /* properties_provided */
624 0, /* properties_destroyed */
625 0, /* todo_flags_start */
626 TODO_dump_func | TODO_verify_loops /* todo_flags_finish */
630 /* Induction variable optimizations. */
633 tree_ssa_loop_ivopts (void)
635 if (number_of_loops () <= 1)
638 tree_ssa_iv_optimize ();
643 gate_tree_ssa_loop_ivopts (void)
645 return flag_ivopts != 0;
648 struct gimple_opt_pass pass_iv_optimize =
653 gate_tree_ssa_loop_ivopts, /* gate */
654 tree_ssa_loop_ivopts, /* execute */
657 0, /* static_pass_number */
658 TV_TREE_LOOP_IVOPTS, /* tv_id */
659 PROP_cfg | PROP_ssa, /* properties_required */
660 0, /* properties_provided */
661 0, /* properties_destroyed */
662 0, /* todo_flags_start */
663 TODO_dump_func | TODO_verify_loops
664 | TODO_update_ssa | TODO_ggc_collect /* todo_flags_finish */
668 /* Loop optimizer finalization. */
671 tree_ssa_loop_done (void)
673 free_numbers_of_iterations_estimates ();
675 loop_optimizer_finalize ();
679 struct gimple_opt_pass pass_tree_loop_done =
683 "loopdone", /* name */
685 tree_ssa_loop_done, /* execute */
688 0, /* static_pass_number */
689 TV_TREE_LOOP_FINI, /* tv_id */
690 PROP_cfg, /* properties_required */
691 0, /* properties_provided */
692 0, /* properties_destroyed */
693 0, /* todo_flags_start */
694 TODO_cleanup_cfg | TODO_dump_func /* todo_flags_finish */