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 /* Initializes the loop structures. */
43 tree_loop_optimizer_init (void)
45 loop_optimizer_init (LOOPS_NORMAL
46 | LOOPS_HAVE_RECORDED_EXITS);
47 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
50 /* The loop superpass. */
55 return flag_tree_loop_optimize != 0;
58 struct gimple_opt_pass pass_tree_loop =
63 gate_tree_loop, /* gate */
67 0, /* static_pass_number */
68 TV_TREE_LOOP, /* tv_id */
69 PROP_cfg, /* properties_required */
70 0, /* properties_provided */
71 0, /* properties_destroyed */
72 TODO_ggc_collect, /* todo_flags_start */
73 TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect /* todo_flags_finish */
77 /* Loop optimizer initialization. */
80 tree_ssa_loop_init (void)
82 tree_loop_optimizer_init ();
83 if (number_of_loops () <= 1)
90 struct gimple_opt_pass pass_tree_loop_init =
94 "loopinit", /* name */
96 tree_ssa_loop_init, /* execute */
99 0, /* static_pass_number */
100 TV_TREE_LOOP_INIT, /* tv_id */
101 PROP_cfg, /* properties_required */
102 0, /* properties_provided */
103 0, /* properties_destroyed */
104 0, /* todo_flags_start */
105 TODO_dump_func | TODO_verify_loops /* todo_flags_finish */
109 /* Loop invariant motion pass. */
112 tree_ssa_loop_im (void)
114 if (number_of_loops () <= 1)
122 gate_tree_ssa_loop_im (void)
124 return flag_tree_loop_im != 0;
127 struct gimple_opt_pass pass_lim =
132 gate_tree_ssa_loop_im, /* gate */
133 tree_ssa_loop_im, /* execute */
136 0, /* static_pass_number */
138 PROP_cfg, /* properties_required */
139 0, /* properties_provided */
140 0, /* properties_destroyed */
141 0, /* todo_flags_start */
142 TODO_dump_func | TODO_verify_loops /* todo_flags_finish */
146 /* Loop unswitching pass. */
149 tree_ssa_loop_unswitch (void)
151 if (number_of_loops () <= 1)
154 return tree_ssa_unswitch_loops ();
158 gate_tree_ssa_loop_unswitch (void)
160 return flag_unswitch_loops != 0;
163 struct gimple_opt_pass pass_tree_unswitch =
167 "unswitch", /* name */
168 gate_tree_ssa_loop_unswitch, /* gate */
169 tree_ssa_loop_unswitch, /* execute */
172 0, /* static_pass_number */
173 TV_TREE_LOOP_UNSWITCH, /* tv_id */
174 PROP_cfg, /* properties_required */
175 0, /* properties_provided */
176 0, /* properties_destroyed */
177 0, /* todo_flags_start */
178 TODO_ggc_collect | TODO_dump_func
179 | TODO_verify_loops /* todo_flags_finish */
183 /* Predictive commoning. */
186 run_tree_predictive_commoning (void)
191 tree_predictive_commoning ();
196 gate_tree_predictive_commoning (void)
198 return flag_predictive_commoning != 0;
201 struct gimple_opt_pass pass_predcom =
206 gate_tree_predictive_commoning, /* gate */
207 run_tree_predictive_commoning, /* execute */
210 0, /* static_pass_number */
211 TV_PREDCOM, /* tv_id */
212 PROP_cfg, /* properties_required */
213 0, /* properties_provided */
214 0, /* properties_destroyed */
215 0, /* todo_flags_start */
216 TODO_dump_func | TODO_verify_loops
217 | TODO_update_ssa_only_virtuals /* todo_flags_finish */
221 /* Loop autovectorization. */
224 tree_vectorize (void)
226 return vectorize_loops ();
230 gate_tree_vectorize (void)
232 return flag_tree_vectorize && number_of_loops () > 1;
235 struct gimple_opt_pass pass_vectorize =
240 gate_tree_vectorize, /* gate */
241 tree_vectorize, /* execute */
244 0, /* static_pass_number */
245 TV_TREE_VECTORIZATION, /* tv_id */
246 PROP_cfg | PROP_ssa, /* properties_required */
247 0, /* properties_provided */
248 0, /* properties_destroyed */
249 TODO_verify_loops, /* todo_flags_start */
250 TODO_dump_func | TODO_update_ssa
251 | TODO_ggc_collect /* todo_flags_finish */
255 /* Loop nest optimizations. */
258 tree_linear_transform (void)
260 if (number_of_loops () <= 1)
263 linear_transform_loops ();
268 gate_tree_linear_transform (void)
270 return flag_tree_loop_linear != 0;
273 struct gimple_opt_pass pass_linear_transform =
278 gate_tree_linear_transform, /* gate */
279 tree_linear_transform, /* execute */
282 0, /* static_pass_number */
283 TV_TREE_LINEAR_TRANSFORM, /* tv_id */
284 PROP_cfg | PROP_ssa, /* properties_required */
285 0, /* properties_provided */
286 0, /* properties_destroyed */
287 0, /* todo_flags_start */
288 TODO_dump_func | TODO_verify_loops
289 | TODO_update_ssa_only_virtuals
290 | TODO_ggc_collect /* todo_flags_finish */
294 /* Check the correctness of the data dependence analyzers. */
297 check_data_deps (void)
299 if (number_of_loops () <= 1)
302 tree_check_data_deps ();
307 gate_check_data_deps (void)
309 return flag_check_data_deps != 0;
312 struct gimple_opt_pass pass_check_data_deps =
317 gate_check_data_deps, /* gate */
318 check_data_deps, /* execute */
321 0, /* static_pass_number */
322 TV_CHECK_DATA_DEPS, /* tv_id */
323 PROP_cfg | PROP_ssa, /* properties_required */
324 0, /* properties_provided */
325 0, /* properties_destroyed */
326 0, /* todo_flags_start */
327 TODO_dump_func /* todo_flags_finish */
331 /* Canonical induction variable creation pass. */
334 tree_ssa_loop_ivcanon (void)
336 if (number_of_loops () <= 1)
339 return canonicalize_induction_variables ();
343 gate_tree_ssa_loop_ivcanon (void)
345 return flag_tree_loop_ivcanon != 0;
348 struct gimple_opt_pass pass_iv_canon =
352 "ivcanon", /* name */
353 gate_tree_ssa_loop_ivcanon, /* gate */
354 tree_ssa_loop_ivcanon, /* execute */
357 0, /* static_pass_number */
358 TV_TREE_LOOP_IVCANON, /* tv_id */
359 PROP_cfg | PROP_ssa, /* properties_required */
360 0, /* properties_provided */
361 0, /* properties_destroyed */
362 0, /* todo_flags_start */
363 TODO_dump_func | TODO_verify_loops /* todo_flags_finish */
367 /* Propagation of constants using scev. */
370 gate_scev_const_prop (void)
372 return flag_tree_scev_cprop;
375 struct gimple_opt_pass pass_scev_cprop =
380 gate_scev_const_prop, /* gate */
381 scev_const_prop, /* execute */
384 0, /* static_pass_number */
385 TV_SCEV_CONST, /* tv_id */
386 PROP_cfg | PROP_ssa, /* properties_required */
387 0, /* properties_provided */
388 0, /* properties_destroyed */
389 0, /* todo_flags_start */
390 TODO_dump_func | TODO_cleanup_cfg
391 | TODO_update_ssa_only_virtuals
392 /* todo_flags_finish */
396 /* Remove empty loops. */
399 tree_ssa_empty_loop (void)
401 if (number_of_loops () <= 1)
404 return remove_empty_loops ();
407 struct gimple_opt_pass pass_empty_loop =
413 tree_ssa_empty_loop, /* execute */
416 0, /* static_pass_number */
417 TV_COMPLETE_UNROLL, /* tv_id */
418 PROP_cfg | PROP_ssa, /* properties_required */
419 0, /* properties_provided */
420 0, /* properties_destroyed */
421 0, /* todo_flags_start */
422 TODO_dump_func | TODO_verify_loops
423 | TODO_ggc_collect /* 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 =
446 tree_ssa_loop_bounds, /* execute */
449 0, /* static_pass_number */
450 TV_TREE_LOOP_BOUNDS, /* tv_id */
451 PROP_cfg | PROP_ssa, /* properties_required */
452 0, /* properties_provided */
453 0, /* properties_destroyed */
454 0, /* todo_flags_start */
455 0 /* todo_flags_finish */
459 /* Complete unrolling of loops. */
462 tree_complete_unroll (void)
464 if (number_of_loops () <= 1)
467 return tree_unroll_loops_completely (flag_unroll_loops
473 gate_tree_complete_unroll (void)
478 struct gimple_opt_pass pass_complete_unroll =
482 "cunroll", /* name */
483 gate_tree_complete_unroll, /* gate */
484 tree_complete_unroll, /* execute */
487 0, /* static_pass_number */
488 TV_COMPLETE_UNROLL, /* tv_id */
489 PROP_cfg | PROP_ssa, /* properties_required */
490 0, /* properties_provided */
491 0, /* properties_destroyed */
492 0, /* todo_flags_start */
493 TODO_dump_func | TODO_verify_loops
494 | TODO_ggc_collect /* todo_flags_finish */
498 /* Parallelization. */
501 gate_tree_parallelize_loops (void)
503 return flag_tree_parallelize_loops > 1;
507 tree_parallelize_loops (void)
509 if (number_of_loops () <= 1)
512 if (parallelize_loops ())
513 return TODO_cleanup_cfg | TODO_rebuild_alias;
517 struct gimple_opt_pass pass_parallelize_loops =
521 "parloops", /* name */
522 gate_tree_parallelize_loops, /* gate */
523 tree_parallelize_loops, /* execute */
526 0, /* static_pass_number */
527 TV_TREE_PARALLELIZE_LOOPS, /* tv_id */
528 PROP_cfg | PROP_ssa, /* properties_required */
529 0, /* properties_provided */
530 0, /* properties_destroyed */
531 0, /* todo_flags_start */
532 TODO_dump_func | TODO_verify_loops /* todo_flags_finish */
539 tree_ssa_loop_prefetch (void)
541 if (number_of_loops () <= 1)
544 return tree_ssa_prefetch_arrays ();
548 gate_tree_ssa_loop_prefetch (void)
550 return flag_prefetch_loop_arrays != 0;
553 struct gimple_opt_pass pass_loop_prefetch =
557 "aprefetch", /* name */
558 gate_tree_ssa_loop_prefetch, /* gate */
559 tree_ssa_loop_prefetch, /* execute */
562 0, /* static_pass_number */
563 TV_TREE_PREFETCH, /* tv_id */
564 PROP_cfg | PROP_ssa, /* properties_required */
565 0, /* properties_provided */
566 0, /* properties_destroyed */
567 0, /* todo_flags_start */
568 TODO_dump_func | TODO_verify_loops /* todo_flags_finish */
572 /* Induction variable optimizations. */
575 tree_ssa_loop_ivopts (void)
577 if (number_of_loops () <= 1)
580 tree_ssa_iv_optimize ();
585 gate_tree_ssa_loop_ivopts (void)
587 return flag_ivopts != 0;
590 struct gimple_opt_pass pass_iv_optimize =
595 gate_tree_ssa_loop_ivopts, /* gate */
596 tree_ssa_loop_ivopts, /* execute */
599 0, /* static_pass_number */
600 TV_TREE_LOOP_IVOPTS, /* tv_id */
601 PROP_cfg | PROP_ssa, /* properties_required */
602 0, /* properties_provided */
603 0, /* properties_destroyed */
604 0, /* todo_flags_start */
605 TODO_dump_func | TODO_verify_loops
606 | TODO_update_ssa | TODO_ggc_collect /* todo_flags_finish */
610 /* Loop optimizer finalization. */
613 tree_ssa_loop_done (void)
615 free_numbers_of_iterations_estimates ();
617 loop_optimizer_finalize ();
621 struct gimple_opt_pass pass_tree_loop_done =
625 "loopdone", /* name */
627 tree_ssa_loop_done, /* execute */
630 0, /* static_pass_number */
631 TV_TREE_LOOP_FINI, /* tv_id */
632 PROP_cfg, /* properties_required */
633 0, /* properties_provided */
634 0, /* properties_destroyed */
635 0, /* todo_flags_start */
636 TODO_cleanup_cfg | TODO_dump_func /* todo_flags_finish */