1 /* Loop optimizations over tree-ssa.
2 Copyright (C) 2003, 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
27 #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"
36 #include "diagnostic-core.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_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 PROP_loops
, /* properties_provided */
95 0, /* properties_destroyed */
96 0, /* todo_flags_start */
97 0 /* 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 0 /* 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_flags_finish */
173 /* Predictive commoning. */
176 run_tree_predictive_commoning (void)
181 return tree_predictive_commoning ();
185 gate_tree_predictive_commoning (void)
187 return flag_predictive_commoning
!= 0;
190 struct gimple_opt_pass pass_predcom
=
195 gate_tree_predictive_commoning
, /* gate */
196 run_tree_predictive_commoning
, /* execute */
199 0, /* static_pass_number */
200 TV_PREDCOM
, /* tv_id */
201 PROP_cfg
, /* properties_required */
202 0, /* properties_provided */
203 0, /* properties_destroyed */
204 0, /* todo_flags_start */
205 TODO_update_ssa_only_virtuals
/* todo_flags_finish */
209 /* Loop autovectorization. */
212 tree_vectorize (void)
214 if (number_of_loops () <= 1)
217 return vectorize_loops ();
221 gate_tree_vectorize (void)
223 return flag_tree_vectorize
;
226 struct gimple_opt_pass pass_vectorize
=
231 gate_tree_vectorize
, /* gate */
232 tree_vectorize
, /* execute */
235 0, /* static_pass_number */
236 TV_TREE_VECTORIZATION
, /* tv_id */
237 PROP_cfg
| PROP_ssa
, /* properties_required */
238 0, /* properties_provided */
239 0, /* properties_destroyed */
240 0, /* todo_flags_start */
242 | TODO_ggc_collect
/* todo_flags_finish */
246 /* GRAPHITE optimizations. */
249 graphite_transforms (void)
254 graphite_transform_loops ();
260 gate_graphite_transforms (void)
262 /* Enable -fgraphite pass if any one of the graphite optimization flags
265 || flag_loop_interchange
266 || flag_loop_strip_mine
267 || flag_graphite_identity
268 || flag_loop_parallelize_all
)
271 return flag_graphite
!= 0;
274 struct gimple_opt_pass pass_graphite
=
278 "graphite0", /* name */
279 gate_graphite_transforms
, /* gate */
283 0, /* static_pass_number */
284 TV_GRAPHITE
, /* tv_id */
285 PROP_cfg
| PROP_ssa
, /* properties_required */
286 0, /* properties_provided */
287 0, /* properties_destroyed */
288 0, /* todo_flags_start */
289 0 /* todo_flags_finish */
293 struct gimple_opt_pass pass_graphite_transforms
=
297 "graphite", /* name */
298 gate_graphite_transforms
, /* gate */
299 graphite_transforms
, /* execute */
302 0, /* static_pass_number */
303 TV_GRAPHITE_TRANSFORMS
, /* tv_id */
304 PROP_cfg
| PROP_ssa
, /* properties_required */
305 0, /* properties_provided */
306 0, /* properties_destroyed */
307 0, /* todo_flags_start */
308 0 /* todo_flags_finish */
312 /* Check the correctness of the data dependence analyzers. */
315 check_data_deps (void)
317 if (number_of_loops () <= 1)
320 tree_check_data_deps ();
325 gate_check_data_deps (void)
327 return flag_check_data_deps
!= 0;
330 struct gimple_opt_pass pass_check_data_deps
=
335 gate_check_data_deps
, /* gate */
336 check_data_deps
, /* execute */
339 0, /* static_pass_number */
340 TV_CHECK_DATA_DEPS
, /* tv_id */
341 PROP_cfg
| PROP_ssa
, /* properties_required */
342 0, /* properties_provided */
343 0, /* properties_destroyed */
344 0, /* todo_flags_start */
345 0 /* todo_flags_finish */
349 /* Canonical induction variable creation pass. */
352 tree_ssa_loop_ivcanon (void)
354 if (number_of_loops () <= 1)
357 return canonicalize_induction_variables ();
361 gate_tree_ssa_loop_ivcanon (void)
363 return flag_tree_loop_ivcanon
!= 0;
366 struct gimple_opt_pass pass_iv_canon
=
370 "ivcanon", /* name */
371 gate_tree_ssa_loop_ivcanon
, /* gate */
372 tree_ssa_loop_ivcanon
, /* execute */
375 0, /* static_pass_number */
376 TV_TREE_LOOP_IVCANON
, /* tv_id */
377 PROP_cfg
| PROP_ssa
, /* properties_required */
378 0, /* properties_provided */
379 0, /* properties_destroyed */
380 0, /* todo_flags_start */
381 0 /* todo_flags_finish */
385 /* Propagation of constants using scev. */
388 gate_scev_const_prop (void)
390 return flag_tree_scev_cprop
;
393 struct gimple_opt_pass pass_scev_cprop
=
398 gate_scev_const_prop
, /* gate */
399 scev_const_prop
, /* execute */
402 0, /* static_pass_number */
403 TV_SCEV_CONST
, /* tv_id */
404 PROP_cfg
| PROP_ssa
, /* properties_required */
405 0, /* properties_provided */
406 0, /* properties_destroyed */
407 0, /* todo_flags_start */
409 | TODO_update_ssa_only_virtuals
410 /* todo_flags_finish */
414 /* Record bounds on numbers of iterations of loops. */
417 tree_ssa_loop_bounds (void)
419 if (number_of_loops () <= 1)
422 estimate_numbers_of_iterations ();
427 struct gimple_opt_pass pass_record_bounds
=
431 "*record_bounds", /* name */
433 tree_ssa_loop_bounds
, /* execute */
436 0, /* static_pass_number */
437 TV_TREE_LOOP_BOUNDS
, /* tv_id */
438 PROP_cfg
| PROP_ssa
, /* properties_required */
439 0, /* properties_provided */
440 0, /* properties_destroyed */
441 0, /* todo_flags_start */
442 0 /* todo_flags_finish */
446 /* Complete unrolling of loops. */
449 tree_complete_unroll (void)
451 if (number_of_loops () <= 1)
454 return tree_unroll_loops_completely (flag_unroll_loops
456 || optimize
>= 3, true);
460 gate_tree_complete_unroll (void)
465 struct gimple_opt_pass pass_complete_unroll
=
469 "cunroll", /* name */
470 gate_tree_complete_unroll
, /* gate */
471 tree_complete_unroll
, /* execute */
474 0, /* static_pass_number */
475 TV_COMPLETE_UNROLL
, /* tv_id */
476 PROP_cfg
| PROP_ssa
, /* properties_required */
477 0, /* properties_provided */
478 0, /* properties_destroyed */
479 0, /* todo_flags_start */
480 TODO_ggc_collect
/* todo_flags_finish */
484 /* Complete unrolling of inner loops. */
487 tree_complete_unroll_inner (void)
491 loop_optimizer_init (LOOPS_NORMAL
492 | LOOPS_HAVE_RECORDED_EXITS
);
493 if (number_of_loops () > 1)
496 ret
= tree_unroll_loops_completely (optimize
>= 3, false);
497 free_numbers_of_iterations_estimates ();
500 loop_optimizer_finalize ();
506 gate_tree_complete_unroll_inner (void)
508 return optimize
>= 2;
511 struct gimple_opt_pass pass_complete_unrolli
=
515 "cunrolli", /* name */
516 gate_tree_complete_unroll_inner
, /* gate */
517 tree_complete_unroll_inner
, /* execute */
520 0, /* static_pass_number */
521 TV_COMPLETE_UNROLL
, /* tv_id */
522 PROP_cfg
| PROP_ssa
, /* properties_required */
523 0, /* properties_provided */
524 0, /* properties_destroyed */
525 0, /* todo_flags_start */
527 | TODO_ggc_collect
/* todo_flags_finish */
531 /* Parallelization. */
534 gate_tree_parallelize_loops (void)
536 return flag_tree_parallelize_loops
> 1;
540 tree_parallelize_loops (void)
542 if (number_of_loops () <= 1)
545 if (parallelize_loops ())
546 return TODO_cleanup_cfg
| TODO_rebuild_alias
;
550 struct gimple_opt_pass pass_parallelize_loops
=
554 "parloops", /* name */
555 gate_tree_parallelize_loops
, /* gate */
556 tree_parallelize_loops
, /* execute */
559 0, /* static_pass_number */
560 TV_TREE_PARALLELIZE_LOOPS
, /* tv_id */
561 PROP_cfg
| PROP_ssa
, /* properties_required */
562 0, /* properties_provided */
563 0, /* properties_destroyed */
564 0, /* todo_flags_start */
565 0 /* todo_flags_finish */
572 tree_ssa_loop_prefetch (void)
574 if (number_of_loops () <= 1)
577 return tree_ssa_prefetch_arrays ();
581 gate_tree_ssa_loop_prefetch (void)
583 return flag_prefetch_loop_arrays
> 0;
586 struct gimple_opt_pass pass_loop_prefetch
=
590 "aprefetch", /* name */
591 gate_tree_ssa_loop_prefetch
, /* gate */
592 tree_ssa_loop_prefetch
, /* execute */
595 0, /* static_pass_number */
596 TV_TREE_PREFETCH
, /* tv_id */
597 PROP_cfg
| PROP_ssa
, /* properties_required */
598 0, /* properties_provided */
599 0, /* properties_destroyed */
600 0, /* todo_flags_start */
601 0 /* todo_flags_finish */
605 /* Induction variable optimizations. */
608 tree_ssa_loop_ivopts (void)
610 if (number_of_loops () <= 1)
613 tree_ssa_iv_optimize ();
618 gate_tree_ssa_loop_ivopts (void)
620 return flag_ivopts
!= 0;
623 struct gimple_opt_pass pass_iv_optimize
=
628 gate_tree_ssa_loop_ivopts
, /* gate */
629 tree_ssa_loop_ivopts
, /* execute */
632 0, /* static_pass_number */
633 TV_TREE_LOOP_IVOPTS
, /* tv_id */
634 PROP_cfg
| PROP_ssa
, /* properties_required */
635 0, /* properties_provided */
636 0, /* properties_destroyed */
637 0, /* todo_flags_start */
638 TODO_update_ssa
| TODO_ggc_collect
/* todo_flags_finish */
642 /* Loop optimizer finalization. */
645 tree_ssa_loop_done (void)
647 free_numbers_of_iterations_estimates ();
649 loop_optimizer_finalize ();
653 struct gimple_opt_pass pass_tree_loop_done
=
657 "loopdone", /* name */
659 tree_ssa_loop_done
, /* execute */
662 0, /* static_pass_number */
663 TV_TREE_LOOP_FINI
, /* tv_id */
664 PROP_cfg
, /* properties_required */
665 0, /* properties_provided */
666 0, /* properties_destroyed */
667 0, /* todo_flags_start */
669 | TODO_verify_flow
/* todo_flags_finish */