1 /* Loop optimizations over tree-ssa.
2 Copyright (C) 2003-2013 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"
27 #include "tree-flow.h"
28 #include "tree-pass.h"
31 #include "tree-inline.h"
32 #include "tree-scalar-evolution.h"
33 #include "diagnostic-core.h"
34 #include "tree-vectorizer.h"
36 /* The loop superpass. */
41 return flag_tree_loop_optimize
!= 0;
44 struct gimple_opt_pass pass_tree_loop
=
49 OPTGROUP_LOOP
, /* optinfo_flags */
50 gate_tree_loop
, /* gate */
54 0, /* static_pass_number */
55 TV_TREE_LOOP
, /* tv_id */
56 PROP_cfg
, /* properties_required */
57 0, /* properties_provided */
58 0, /* properties_destroyed */
59 TODO_ggc_collect
, /* todo_flags_start */
60 TODO_verify_ssa
| TODO_ggc_collect
/* todo_flags_finish */
64 /* Loop optimizer initialization. */
67 tree_ssa_loop_init (void)
69 loop_optimizer_init (LOOPS_NORMAL
70 | LOOPS_HAVE_RECORDED_EXITS
);
71 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
73 /* We might discover new loops, e.g. when turning irreducible
74 regions into reducible. */
77 if (number_of_loops () <= 1)
83 struct gimple_opt_pass pass_tree_loop_init
=
87 "loopinit", /* name */
88 OPTGROUP_LOOP
, /* optinfo_flags */
90 tree_ssa_loop_init
, /* execute */
93 0, /* static_pass_number */
95 PROP_cfg
, /* properties_required */
96 PROP_loops
, /* properties_provided */
97 0, /* properties_destroyed */
98 0, /* todo_flags_start */
99 0 /* todo_flags_finish */
103 /* Loop invariant motion pass. */
106 tree_ssa_loop_im (void)
108 if (number_of_loops () <= 1)
111 return tree_ssa_lim ();
115 gate_tree_ssa_loop_im (void)
117 return flag_tree_loop_im
!= 0;
120 struct gimple_opt_pass pass_lim
=
125 OPTGROUP_LOOP
, /* optinfo_flags */
126 gate_tree_ssa_loop_im
, /* gate */
127 tree_ssa_loop_im
, /* execute */
130 0, /* static_pass_number */
132 PROP_cfg
, /* properties_required */
133 0, /* properties_provided */
134 0, /* properties_destroyed */
135 0, /* todo_flags_start */
136 0 /* todo_flags_finish */
140 /* Loop unswitching pass. */
143 tree_ssa_loop_unswitch (void)
145 if (number_of_loops () <= 1)
148 return tree_ssa_unswitch_loops ();
152 gate_tree_ssa_loop_unswitch (void)
154 return flag_unswitch_loops
!= 0;
157 struct gimple_opt_pass pass_tree_unswitch
=
161 "unswitch", /* name */
162 OPTGROUP_LOOP
, /* optinfo_flags */
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_flags_finish */
177 /* Predictive commoning. */
180 run_tree_predictive_commoning (void)
185 return tree_predictive_commoning ();
189 gate_tree_predictive_commoning (void)
191 return flag_predictive_commoning
!= 0;
194 struct gimple_opt_pass pass_predcom
=
199 OPTGROUP_LOOP
, /* optinfo_flags */
200 gate_tree_predictive_commoning
, /* gate */
201 run_tree_predictive_commoning
, /* execute */
204 0, /* static_pass_number */
205 TV_PREDCOM
, /* tv_id */
206 PROP_cfg
, /* properties_required */
207 0, /* properties_provided */
208 0, /* properties_destroyed */
209 0, /* todo_flags_start */
210 TODO_update_ssa_only_virtuals
/* todo_flags_finish */
214 /* Loop autovectorization. */
217 tree_loop_vectorize (void)
219 if (number_of_loops () <= 1)
222 return vectorize_loops ();
226 gate_tree_loop_vectorize (void)
228 return flag_tree_loop_vectorize
;
231 struct gimple_opt_pass pass_vectorize
=
237 | OPTGROUP_VEC
, /* optinfo_flags */
238 gate_tree_loop_vectorize
, /* gate */
239 tree_loop_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 0, /* todo_flags_start */
249 | TODO_ggc_collect
/* todo_flags_finish */
253 /* GRAPHITE optimizations. */
256 graphite_transforms (void)
261 graphite_transform_loops ();
267 gate_graphite_transforms (void)
269 /* Enable -fgraphite pass if any one of the graphite optimization flags
272 || flag_loop_interchange
273 || flag_loop_strip_mine
274 || flag_graphite_identity
275 || flag_loop_parallelize_all
276 || flag_loop_optimize_isl
)
279 return flag_graphite
!= 0;
282 struct gimple_opt_pass pass_graphite
=
286 "graphite0", /* name */
287 OPTGROUP_LOOP
, /* optinfo_flags */
288 gate_graphite_transforms
, /* gate */
292 0, /* static_pass_number */
293 TV_GRAPHITE
, /* tv_id */
294 PROP_cfg
| PROP_ssa
, /* properties_required */
295 0, /* properties_provided */
296 0, /* properties_destroyed */
297 0, /* todo_flags_start */
298 0 /* todo_flags_finish */
302 struct gimple_opt_pass pass_graphite_transforms
=
306 "graphite", /* name */
307 OPTGROUP_LOOP
, /* optinfo_flags */
308 gate_graphite_transforms
, /* gate */
309 graphite_transforms
, /* execute */
312 0, /* static_pass_number */
313 TV_GRAPHITE_TRANSFORMS
, /* tv_id */
314 PROP_cfg
| PROP_ssa
, /* properties_required */
315 0, /* properties_provided */
316 0, /* properties_destroyed */
317 0, /* todo_flags_start */
318 0 /* todo_flags_finish */
322 /* Check the correctness of the data dependence analyzers. */
325 check_data_deps (void)
327 if (number_of_loops () <= 1)
330 tree_check_data_deps ();
335 gate_check_data_deps (void)
337 return flag_check_data_deps
!= 0;
340 struct gimple_opt_pass pass_check_data_deps
=
345 OPTGROUP_LOOP
, /* optinfo_flags */
346 gate_check_data_deps
, /* gate */
347 check_data_deps
, /* execute */
350 0, /* static_pass_number */
351 TV_CHECK_DATA_DEPS
, /* tv_id */
352 PROP_cfg
| PROP_ssa
, /* properties_required */
353 0, /* properties_provided */
354 0, /* properties_destroyed */
355 0, /* todo_flags_start */
356 0 /* todo_flags_finish */
360 /* Canonical induction variable creation pass. */
363 tree_ssa_loop_ivcanon (void)
365 if (number_of_loops () <= 1)
368 return canonicalize_induction_variables ();
372 gate_tree_ssa_loop_ivcanon (void)
374 return flag_tree_loop_ivcanon
!= 0;
377 struct gimple_opt_pass pass_iv_canon
=
381 "ivcanon", /* name */
382 OPTGROUP_LOOP
, /* optinfo_flags */
383 gate_tree_ssa_loop_ivcanon
, /* gate */
384 tree_ssa_loop_ivcanon
, /* execute */
387 0, /* static_pass_number */
388 TV_TREE_LOOP_IVCANON
, /* tv_id */
389 PROP_cfg
| PROP_ssa
, /* properties_required */
390 0, /* properties_provided */
391 0, /* properties_destroyed */
392 0, /* todo_flags_start */
393 0 /* todo_flags_finish */
397 /* Propagation of constants using scev. */
400 gate_scev_const_prop (void)
402 return flag_tree_scev_cprop
;
405 struct gimple_opt_pass pass_scev_cprop
=
410 OPTGROUP_LOOP
, /* optinfo_flags */
411 gate_scev_const_prop
, /* gate */
412 scev_const_prop
, /* execute */
415 0, /* static_pass_number */
416 TV_SCEV_CONST
, /* tv_id */
417 PROP_cfg
| PROP_ssa
, /* properties_required */
418 0, /* properties_provided */
419 0, /* properties_destroyed */
420 0, /* todo_flags_start */
422 | TODO_update_ssa_only_virtuals
423 /* 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
=
444 "*record_bounds", /* name */
445 OPTGROUP_NONE
, /* optinfo_flags */
447 tree_ssa_loop_bounds
, /* execute */
450 0, /* static_pass_number */
451 TV_TREE_LOOP_BOUNDS
, /* tv_id */
452 PROP_cfg
| PROP_ssa
, /* properties_required */
453 0, /* properties_provided */
454 0, /* properties_destroyed */
455 0, /* todo_flags_start */
456 0 /* todo_flags_finish */
460 /* Complete unrolling of loops. */
463 tree_complete_unroll (void)
465 if (number_of_loops () <= 1)
468 return tree_unroll_loops_completely (flag_unroll_loops
470 || optimize
>= 3, true);
474 gate_tree_complete_unroll (void)
479 struct gimple_opt_pass pass_complete_unroll
=
483 "cunroll", /* name */
484 OPTGROUP_LOOP
, /* optinfo_flags */
485 gate_tree_complete_unroll
, /* gate */
486 tree_complete_unroll
, /* execute */
489 0, /* static_pass_number */
490 TV_COMPLETE_UNROLL
, /* tv_id */
491 PROP_cfg
| PROP_ssa
, /* properties_required */
492 0, /* properties_provided */
493 0, /* properties_destroyed */
494 0, /* todo_flags_start */
495 TODO_ggc_collect
/* todo_flags_finish */
499 /* Complete unrolling of inner loops. */
502 tree_complete_unroll_inner (void)
506 loop_optimizer_init (LOOPS_NORMAL
507 | LOOPS_HAVE_RECORDED_EXITS
);
508 if (number_of_loops () > 1)
511 ret
= tree_unroll_loops_completely (optimize
>= 3, false);
512 free_numbers_of_iterations_estimates ();
515 loop_optimizer_finalize ();
521 gate_tree_complete_unroll_inner (void)
523 return optimize
>= 2;
526 struct gimple_opt_pass pass_complete_unrolli
=
530 "cunrolli", /* name */
531 OPTGROUP_LOOP
, /* optinfo_flags */
532 gate_tree_complete_unroll_inner
, /* gate */
533 tree_complete_unroll_inner
, /* execute */
536 0, /* static_pass_number */
537 TV_COMPLETE_UNROLL
, /* tv_id */
538 PROP_cfg
| PROP_ssa
, /* properties_required */
539 0, /* properties_provided */
540 0, /* properties_destroyed */
541 0, /* todo_flags_start */
543 | TODO_ggc_collect
/* todo_flags_finish */
547 /* Parallelization. */
550 gate_tree_parallelize_loops (void)
552 return flag_tree_parallelize_loops
> 1;
556 tree_parallelize_loops (void)
558 if (number_of_loops () <= 1)
561 if (parallelize_loops ())
562 return TODO_cleanup_cfg
| TODO_rebuild_alias
;
566 struct gimple_opt_pass pass_parallelize_loops
=
570 "parloops", /* name */
571 OPTGROUP_LOOP
, /* optinfo_flags */
572 gate_tree_parallelize_loops
, /* gate */
573 tree_parallelize_loops
, /* execute */
576 0, /* static_pass_number */
577 TV_TREE_PARALLELIZE_LOOPS
, /* tv_id */
578 PROP_cfg
| PROP_ssa
, /* properties_required */
579 0, /* properties_provided */
580 0, /* properties_destroyed */
581 0, /* todo_flags_start */
582 0 /* todo_flags_finish */
589 tree_ssa_loop_prefetch (void)
591 if (number_of_loops () <= 1)
594 return tree_ssa_prefetch_arrays ();
598 gate_tree_ssa_loop_prefetch (void)
600 return flag_prefetch_loop_arrays
> 0;
603 struct gimple_opt_pass pass_loop_prefetch
=
607 "aprefetch", /* name */
608 OPTGROUP_LOOP
, /* optinfo_flags */
609 gate_tree_ssa_loop_prefetch
, /* gate */
610 tree_ssa_loop_prefetch
, /* execute */
613 0, /* static_pass_number */
614 TV_TREE_PREFETCH
, /* tv_id */
615 PROP_cfg
| PROP_ssa
, /* properties_required */
616 0, /* properties_provided */
617 0, /* properties_destroyed */
618 0, /* todo_flags_start */
619 0 /* todo_flags_finish */
623 /* Induction variable optimizations. */
626 tree_ssa_loop_ivopts (void)
628 if (number_of_loops () <= 1)
631 tree_ssa_iv_optimize ();
636 gate_tree_ssa_loop_ivopts (void)
638 return flag_ivopts
!= 0;
641 struct gimple_opt_pass pass_iv_optimize
=
646 OPTGROUP_LOOP
, /* optinfo_flags */
647 gate_tree_ssa_loop_ivopts
, /* gate */
648 tree_ssa_loop_ivopts
, /* execute */
651 0, /* static_pass_number */
652 TV_TREE_LOOP_IVOPTS
, /* tv_id */
653 PROP_cfg
| PROP_ssa
, /* properties_required */
654 0, /* properties_provided */
655 0, /* properties_destroyed */
656 0, /* todo_flags_start */
657 TODO_update_ssa
| TODO_ggc_collect
/* todo_flags_finish */
661 /* Loop optimizer finalization. */
664 tree_ssa_loop_done (void)
666 free_numbers_of_iterations_estimates ();
668 loop_optimizer_finalize ();
672 struct gimple_opt_pass pass_tree_loop_done
=
676 "loopdone", /* name */
677 OPTGROUP_LOOP
, /* optinfo_flags */
679 tree_ssa_loop_done
, /* execute */
682 0, /* static_pass_number */
684 PROP_cfg
, /* properties_required */
685 0, /* properties_provided */
686 0, /* properties_destroyed */
687 0, /* todo_flags_start */
689 | TODO_verify_flow
/* todo_flags_finish */