1 /* Loop optimizations over tree-ssa.
2 Copyright (C) 2003, 2005, 2006, 2007 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 /* The loop superpass. */
45 return flag_tree_loop_optimize != 0;
48 struct gimple_opt_pass pass_tree_loop =
53 gate_tree_loop, /* gate */
57 0, /* static_pass_number */
58 TV_TREE_LOOP, /* tv_id */
59 PROP_cfg, /* properties_required */
60 0, /* properties_provided */
61 0, /* properties_destroyed */
62 TODO_ggc_collect, /* todo_flags_start */
63 TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect /* todo_flags_finish */
67 /* Loop optimizer initialization. */
70 tree_ssa_loop_init (void)
72 loop_optimizer_init (LOOPS_NORMAL
73 | LOOPS_HAVE_RECORDED_EXITS);
74 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
76 if (number_of_loops () <= 1)
83 struct gimple_opt_pass pass_tree_loop_init =
87 "loopinit", /* name */
89 tree_ssa_loop_init, /* execute */
92 0, /* static_pass_number */
93 TV_TREE_LOOP_INIT, /* tv_id */
94 PROP_cfg, /* properties_required */
95 0, /* properties_provided */
96 0, /* properties_destroyed */
97 0, /* todo_flags_start */
98 TODO_dump_func | TODO_verify_loops /* todo_flags_finish */
102 /* Loop invariant motion pass. */
105 tree_ssa_loop_im (void)
107 if (number_of_loops () <= 1)
115 gate_tree_ssa_loop_im (void)
117 return flag_tree_loop_im != 0;
120 struct gimple_opt_pass pass_lim =
125 gate_tree_ssa_loop_im, /* gate */
126 tree_ssa_loop_im, /* execute */
129 0, /* static_pass_number */
131 PROP_cfg, /* properties_required */
132 0, /* properties_provided */
133 0, /* properties_destroyed */
134 0, /* todo_flags_start */
135 TODO_dump_func | TODO_verify_loops /* todo_flags_finish */
139 /* Loop unswitching pass. */
142 tree_ssa_loop_unswitch (void)
144 if (number_of_loops () <= 1)
147 return tree_ssa_unswitch_loops ();
151 gate_tree_ssa_loop_unswitch (void)
153 return flag_unswitch_loops != 0;
156 struct gimple_opt_pass pass_tree_unswitch =
160 "unswitch", /* name */
161 gate_tree_ssa_loop_unswitch, /* gate */
162 tree_ssa_loop_unswitch, /* execute */
165 0, /* static_pass_number */
166 TV_TREE_LOOP_UNSWITCH, /* tv_id */
167 PROP_cfg, /* properties_required */
168 0, /* properties_provided */
169 0, /* properties_destroyed */
170 0, /* todo_flags_start */
171 TODO_ggc_collect | TODO_dump_func
172 | TODO_verify_loops /* todo_flags_finish */
176 /* Predictive commoning. */
179 run_tree_predictive_commoning (void)
184 tree_predictive_commoning ();
189 gate_tree_predictive_commoning (void)
191 return flag_predictive_commoning != 0;
194 struct gimple_opt_pass pass_predcom =
199 gate_tree_predictive_commoning, /* gate */
200 run_tree_predictive_commoning, /* execute */
203 0, /* static_pass_number */
204 TV_PREDCOM, /* tv_id */
205 PROP_cfg, /* properties_required */
206 0, /* properties_provided */
207 0, /* properties_destroyed */
208 0, /* todo_flags_start */
209 TODO_dump_func | TODO_verify_loops
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 =
236 gate_tree_vectorize, /* gate */
237 tree_vectorize, /* execute */
240 0, /* static_pass_number */
241 TV_TREE_VECTORIZATION, /* tv_id */
242 PROP_cfg | PROP_ssa, /* properties_required */
243 0, /* properties_provided */
244 0, /* properties_destroyed */
245 TODO_verify_loops, /* todo_flags_start */
246 TODO_dump_func | TODO_update_ssa
247 | TODO_ggc_collect /* todo_flags_finish */
251 /* Loop nest optimizations. */
254 tree_linear_transform (void)
256 if (number_of_loops () <= 1)
259 linear_transform_loops ();
264 gate_tree_linear_transform (void)
266 return flag_tree_loop_linear != 0;
269 struct gimple_opt_pass pass_linear_transform =
274 gate_tree_linear_transform, /* gate */
275 tree_linear_transform, /* execute */
278 0, /* static_pass_number */
279 TV_TREE_LINEAR_TRANSFORM, /* tv_id */
280 PROP_cfg | PROP_ssa, /* properties_required */
281 0, /* properties_provided */
282 0, /* properties_destroyed */
283 0, /* todo_flags_start */
284 TODO_dump_func | TODO_verify_loops
285 | TODO_update_ssa_only_virtuals
286 | TODO_ggc_collect /* todo_flags_finish */
290 /* Check the correctness of the data dependence analyzers. */
293 check_data_deps (void)
295 if (number_of_loops () <= 1)
298 tree_check_data_deps ();
303 gate_check_data_deps (void)
305 return flag_check_data_deps != 0;
308 struct gimple_opt_pass pass_check_data_deps =
313 gate_check_data_deps, /* gate */
314 check_data_deps, /* execute */
317 0, /* static_pass_number */
318 TV_CHECK_DATA_DEPS, /* tv_id */
319 PROP_cfg | PROP_ssa, /* properties_required */
320 0, /* properties_provided */
321 0, /* properties_destroyed */
322 0, /* todo_flags_start */
323 TODO_dump_func /* todo_flags_finish */
327 /* Canonical induction variable creation pass. */
330 tree_ssa_loop_ivcanon (void)
332 if (number_of_loops () <= 1)
335 return canonicalize_induction_variables ();
339 gate_tree_ssa_loop_ivcanon (void)
341 return flag_tree_loop_ivcanon != 0;
344 struct gimple_opt_pass pass_iv_canon =
348 "ivcanon", /* name */
349 gate_tree_ssa_loop_ivcanon, /* gate */
350 tree_ssa_loop_ivcanon, /* execute */
353 0, /* static_pass_number */
354 TV_TREE_LOOP_IVCANON, /* tv_id */
355 PROP_cfg | PROP_ssa, /* properties_required */
356 0, /* properties_provided */
357 0, /* properties_destroyed */
358 0, /* todo_flags_start */
359 TODO_dump_func | TODO_verify_loops /* todo_flags_finish */
363 /* Propagation of constants using scev. */
366 gate_scev_const_prop (void)
368 return flag_tree_scev_cprop;
371 struct gimple_opt_pass pass_scev_cprop =
376 gate_scev_const_prop, /* gate */
377 scev_const_prop, /* execute */
380 0, /* static_pass_number */
381 TV_SCEV_CONST, /* tv_id */
382 PROP_cfg | PROP_ssa, /* properties_required */
383 0, /* properties_provided */
384 0, /* properties_destroyed */
385 0, /* todo_flags_start */
386 TODO_dump_func | TODO_cleanup_cfg
387 | TODO_update_ssa_only_virtuals
388 /* todo_flags_finish */
392 /* Remove empty loops. */
395 tree_ssa_empty_loop (void)
397 if (number_of_loops () <= 1)
400 return remove_empty_loops ();
403 struct gimple_opt_pass pass_empty_loop =
409 tree_ssa_empty_loop, /* execute */
412 0, /* static_pass_number */
413 TV_COMPLETE_UNROLL, /* tv_id */
414 PROP_cfg | PROP_ssa, /* properties_required */
415 0, /* properties_provided */
416 0, /* properties_destroyed */
417 0, /* todo_flags_start */
418 TODO_dump_func | TODO_verify_loops
419 | TODO_ggc_collect /* todo_flags_finish */
423 /* Record bounds on numbers of iterations of loops. */
426 tree_ssa_loop_bounds (void)
428 if (number_of_loops () <= 1)
431 estimate_numbers_of_iterations ();
436 struct gimple_opt_pass pass_record_bounds =
442 tree_ssa_loop_bounds, /* execute */
445 0, /* static_pass_number */
446 TV_TREE_LOOP_BOUNDS, /* tv_id */
447 PROP_cfg | PROP_ssa, /* properties_required */
448 0, /* properties_provided */
449 0, /* properties_destroyed */
450 0, /* todo_flags_start */
451 0 /* todo_flags_finish */
455 /* Complete unrolling of loops. */
458 tree_complete_unroll (void)
460 if (number_of_loops () <= 1)
463 return tree_unroll_loops_completely (flag_unroll_loops
465 || optimize >= 3, true);
469 gate_tree_complete_unroll (void)
474 struct gimple_opt_pass pass_complete_unroll =
478 "cunroll", /* name */
479 gate_tree_complete_unroll, /* gate */
480 tree_complete_unroll, /* execute */
483 0, /* static_pass_number */
484 TV_COMPLETE_UNROLL, /* tv_id */
485 PROP_cfg | PROP_ssa, /* properties_required */
486 0, /* properties_provided */
487 0, /* properties_destroyed */
488 0, /* todo_flags_start */
489 TODO_dump_func | TODO_verify_loops
490 | TODO_ggc_collect /* todo_flags_finish */
494 /* Complete unrolling of inner loops. */
497 tree_complete_unroll_inner (void)
501 loop_optimizer_init (LOOPS_NORMAL
502 | LOOPS_HAVE_RECORDED_EXITS);
503 if (number_of_loops () > 1)
506 ret = tree_unroll_loops_completely (optimize >= 3, false);
507 free_numbers_of_iterations_estimates ();
510 loop_optimizer_finalize ();
516 gate_tree_complete_unroll_inner (void)
518 return optimize >= 2;
521 struct gimple_opt_pass pass_complete_unrolli =
525 "cunrolli", /* name */
526 gate_tree_complete_unroll_inner, /* gate */
527 tree_complete_unroll_inner, /* execute */
530 0, /* static_pass_number */
531 TV_COMPLETE_UNROLL, /* tv_id */
532 PROP_cfg | PROP_ssa, /* properties_required */
533 0, /* properties_provided */
534 0, /* properties_destroyed */
535 0, /* todo_flags_start */
536 TODO_dump_func | TODO_verify_loops
537 | TODO_ggc_collect /* todo_flags_finish */
541 /* Parallelization. */
544 gate_tree_parallelize_loops (void)
546 return flag_tree_parallelize_loops > 1;
550 tree_parallelize_loops (void)
552 if (number_of_loops () <= 1)
555 if (parallelize_loops ())
556 return TODO_cleanup_cfg | TODO_rebuild_alias;
560 struct gimple_opt_pass pass_parallelize_loops =
564 "parloops", /* name */
565 gate_tree_parallelize_loops, /* gate */
566 tree_parallelize_loops, /* execute */
569 0, /* static_pass_number */
570 TV_TREE_PARALLELIZE_LOOPS, /* tv_id */
571 PROP_cfg | PROP_ssa, /* properties_required */
572 0, /* properties_provided */
573 0, /* properties_destroyed */
574 0, /* todo_flags_start */
575 TODO_dump_func | TODO_verify_loops /* todo_flags_finish */
582 tree_ssa_loop_prefetch (void)
584 if (number_of_loops () <= 1)
587 return tree_ssa_prefetch_arrays ();
591 gate_tree_ssa_loop_prefetch (void)
593 return flag_prefetch_loop_arrays != 0;
596 struct gimple_opt_pass pass_loop_prefetch =
600 "aprefetch", /* name */
601 gate_tree_ssa_loop_prefetch, /* gate */
602 tree_ssa_loop_prefetch, /* execute */
605 0, /* static_pass_number */
606 TV_TREE_PREFETCH, /* tv_id */
607 PROP_cfg | PROP_ssa, /* properties_required */
608 0, /* properties_provided */
609 0, /* properties_destroyed */
610 0, /* todo_flags_start */
611 TODO_dump_func | TODO_verify_loops /* todo_flags_finish */
615 /* Induction variable optimizations. */
618 tree_ssa_loop_ivopts (void)
620 if (number_of_loops () <= 1)
623 tree_ssa_iv_optimize ();
628 gate_tree_ssa_loop_ivopts (void)
630 return flag_ivopts != 0;
633 struct gimple_opt_pass pass_iv_optimize =
638 gate_tree_ssa_loop_ivopts, /* gate */
639 tree_ssa_loop_ivopts, /* execute */
642 0, /* static_pass_number */
643 TV_TREE_LOOP_IVOPTS, /* tv_id */
644 PROP_cfg | PROP_ssa, /* properties_required */
645 0, /* properties_provided */
646 0, /* properties_destroyed */
647 0, /* todo_flags_start */
648 TODO_dump_func | TODO_verify_loops
649 | TODO_update_ssa | TODO_ggc_collect /* todo_flags_finish */
653 /* Loop optimizer finalization. */
656 tree_ssa_loop_done (void)
658 free_numbers_of_iterations_estimates ();
660 loop_optimizer_finalize ();
664 struct gimple_opt_pass pass_tree_loop_done =
668 "loopdone", /* name */
670 tree_ssa_loop_done, /* execute */
673 0, /* static_pass_number */
674 TV_TREE_LOOP_FINI, /* tv_id */
675 PROP_cfg, /* properties_required */
676 0, /* properties_provided */
677 0, /* properties_destroyed */
678 0, /* todo_flags_start */
679 TODO_cleanup_cfg | TODO_dump_func /* todo_flags_finish */