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"
29 #include "tree-flow.h"
30 #include "tree-dump.h"
31 #include "tree-pass.h"
35 #include "tree-inline.h"
36 #include "tree-scalar-evolution.h"
37 #include "diagnostic-core.h"
38 #include "tree-vectorizer.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_flags_finish */
102 /* Loop invariant motion pass. */
105 tree_ssa_loop_im (void)
107 if (number_of_loops () <= 1)
110 return tree_ssa_lim ();
114 gate_tree_ssa_loop_im (void)
116 return flag_tree_loop_im
!= 0;
119 struct gimple_opt_pass pass_lim
=
124 gate_tree_ssa_loop_im
, /* gate */
125 tree_ssa_loop_im
, /* execute */
128 0, /* static_pass_number */
130 PROP_cfg
, /* properties_required */
131 0, /* properties_provided */
132 0, /* properties_destroyed */
133 0, /* todo_flags_start */
134 TODO_dump_func
/* todo_flags_finish */
138 /* Loop unswitching pass. */
141 tree_ssa_loop_unswitch (void)
143 if (number_of_loops () <= 1)
146 return tree_ssa_unswitch_loops ();
150 gate_tree_ssa_loop_unswitch (void)
152 return flag_unswitch_loops
!= 0;
155 struct gimple_opt_pass pass_tree_unswitch
=
159 "unswitch", /* name */
160 gate_tree_ssa_loop_unswitch
, /* gate */
161 tree_ssa_loop_unswitch
, /* execute */
164 0, /* static_pass_number */
165 TV_TREE_LOOP_UNSWITCH
, /* tv_id */
166 PROP_cfg
, /* properties_required */
167 0, /* properties_provided */
168 0, /* properties_destroyed */
169 0, /* todo_flags_start */
170 TODO_ggc_collect
| TODO_dump_func
/* todo_flags_finish */
174 /* Predictive commoning. */
177 run_tree_predictive_commoning (void)
182 tree_predictive_commoning ();
187 gate_tree_predictive_commoning (void)
189 return flag_predictive_commoning
!= 0;
192 struct gimple_opt_pass pass_predcom
=
197 gate_tree_predictive_commoning
, /* gate */
198 run_tree_predictive_commoning
, /* execute */
201 0, /* static_pass_number */
202 TV_PREDCOM
, /* tv_id */
203 PROP_cfg
, /* properties_required */
204 0, /* properties_provided */
205 0, /* properties_destroyed */
206 0, /* todo_flags_start */
208 | TODO_update_ssa_only_virtuals
/* todo_flags_finish */
212 /* Loop autovectorization. */
215 tree_vectorize (void)
217 if (number_of_loops () <= 1)
220 return vectorize_loops ();
224 gate_tree_vectorize (void)
226 return flag_tree_vectorize
;
229 struct gimple_opt_pass pass_vectorize
=
234 gate_tree_vectorize
, /* gate */
235 tree_vectorize
, /* execute */
238 0, /* static_pass_number */
239 TV_TREE_VECTORIZATION
, /* tv_id */
240 PROP_cfg
| PROP_ssa
, /* properties_required */
241 0, /* properties_provided */
242 0, /* properties_destroyed */
243 0, /* todo_flags_start */
244 TODO_dump_func
| TODO_update_ssa
245 | TODO_ggc_collect
/* todo_flags_finish */
249 /* Loop nest optimizations. */
252 tree_linear_transform (void)
254 if (number_of_loops () <= 1)
257 linear_transform_loops ();
262 gate_tree_linear_transform (void)
264 return flag_tree_loop_linear
!= 0;
267 struct gimple_opt_pass pass_linear_transform
=
272 gate_tree_linear_transform
, /* gate */
273 tree_linear_transform
, /* execute */
276 0, /* static_pass_number */
277 TV_TREE_LINEAR_TRANSFORM
, /* tv_id */
278 PROP_cfg
| PROP_ssa
, /* properties_required */
279 0, /* properties_provided */
280 0, /* properties_destroyed */
281 0, /* todo_flags_start */
283 | TODO_update_ssa_only_virtuals
284 | TODO_ggc_collect
/* todo_flags_finish */
288 /* GRAPHITE optimizations. */
291 graphite_transforms (void)
296 graphite_transform_loops ();
302 gate_graphite_transforms (void)
304 /* Enable -fgraphite pass if any one of the graphite optimization flags
307 || flag_loop_interchange
308 || flag_loop_strip_mine
309 || flag_graphite_identity
310 || flag_loop_parallelize_all
312 || flag_graphite_opencl
)
315 return flag_graphite
!= 0;
318 struct gimple_opt_pass pass_graphite
=
322 "graphite0", /* name */
323 gate_graphite_transforms
, /* gate */
327 0, /* static_pass_number */
328 TV_GRAPHITE
, /* tv_id */
329 PROP_cfg
| PROP_ssa
, /* properties_required */
330 0, /* properties_provided */
331 0, /* properties_destroyed */
332 0, /* todo_flags_start */
333 0 /* todo_flags_finish */
337 struct gimple_opt_pass pass_graphite_transforms
=
341 "graphite", /* name */
342 gate_graphite_transforms
, /* gate */
343 graphite_transforms
, /* execute */
346 0, /* static_pass_number */
347 TV_GRAPHITE_TRANSFORMS
, /* tv_id */
348 PROP_cfg
| PROP_ssa
, /* properties_required */
349 0, /* properties_provided */
350 0, /* properties_destroyed */
351 0, /* todo_flags_start */
352 0 /* todo_flags_finish */
356 /* Check the correctness of the data dependence analyzers. */
359 check_data_deps (void)
361 if (number_of_loops () <= 1)
364 tree_check_data_deps ();
369 gate_check_data_deps (void)
371 return flag_check_data_deps
!= 0;
374 struct gimple_opt_pass pass_check_data_deps
=
379 gate_check_data_deps
, /* gate */
380 check_data_deps
, /* execute */
383 0, /* static_pass_number */
384 TV_CHECK_DATA_DEPS
, /* tv_id */
385 PROP_cfg
| PROP_ssa
, /* properties_required */
386 0, /* properties_provided */
387 0, /* properties_destroyed */
388 0, /* todo_flags_start */
389 TODO_dump_func
/* todo_flags_finish */
393 /* Canonical induction variable creation pass. */
396 tree_ssa_loop_ivcanon (void)
398 if (number_of_loops () <= 1)
401 return canonicalize_induction_variables ();
405 gate_tree_ssa_loop_ivcanon (void)
407 return flag_tree_loop_ivcanon
!= 0;
410 struct gimple_opt_pass pass_iv_canon
=
414 "ivcanon", /* name */
415 gate_tree_ssa_loop_ivcanon
, /* gate */
416 tree_ssa_loop_ivcanon
, /* execute */
419 0, /* static_pass_number */
420 TV_TREE_LOOP_IVCANON
, /* tv_id */
421 PROP_cfg
| PROP_ssa
, /* properties_required */
422 0, /* properties_provided */
423 0, /* properties_destroyed */
424 0, /* todo_flags_start */
425 TODO_dump_func
/* todo_flags_finish */
429 /* Propagation of constants using scev. */
432 gate_scev_const_prop (void)
434 return flag_tree_scev_cprop
;
437 struct gimple_opt_pass pass_scev_cprop
=
442 gate_scev_const_prop
, /* gate */
443 scev_const_prop
, /* execute */
446 0, /* static_pass_number */
447 TV_SCEV_CONST
, /* tv_id */
448 PROP_cfg
| PROP_ssa
, /* properties_required */
449 0, /* properties_provided */
450 0, /* properties_destroyed */
451 0, /* todo_flags_start */
452 TODO_dump_func
| TODO_cleanup_cfg
453 | TODO_update_ssa_only_virtuals
454 /* todo_flags_finish */
458 /* Record bounds on numbers of iterations of loops. */
461 tree_ssa_loop_bounds (void)
463 if (number_of_loops () <= 1)
466 estimate_numbers_of_iterations (true);
471 struct gimple_opt_pass pass_record_bounds
=
475 "*record_bounds", /* name */
477 tree_ssa_loop_bounds
, /* execute */
480 0, /* static_pass_number */
481 TV_TREE_LOOP_BOUNDS
, /* tv_id */
482 PROP_cfg
| PROP_ssa
, /* properties_required */
483 0, /* properties_provided */
484 0, /* properties_destroyed */
485 0, /* todo_flags_start */
486 0 /* todo_flags_finish */
490 /* Complete unrolling of loops. */
493 tree_complete_unroll (void)
495 if (number_of_loops () <= 1)
498 return tree_unroll_loops_completely (flag_unroll_loops
500 || optimize
>= 3, true);
504 gate_tree_complete_unroll (void)
509 struct gimple_opt_pass pass_complete_unroll
=
513 "cunroll", /* name */
514 gate_tree_complete_unroll
, /* gate */
515 tree_complete_unroll
, /* execute */
518 0, /* static_pass_number */
519 TV_COMPLETE_UNROLL
, /* tv_id */
520 PROP_cfg
| PROP_ssa
, /* properties_required */
521 0, /* properties_provided */
522 0, /* properties_destroyed */
523 0, /* todo_flags_start */
525 | TODO_ggc_collect
/* todo_flags_finish */
529 /* Complete unrolling of inner loops. */
532 tree_complete_unroll_inner (void)
536 loop_optimizer_init (LOOPS_NORMAL
537 | LOOPS_HAVE_RECORDED_EXITS
);
538 if (number_of_loops () > 1)
541 ret
= tree_unroll_loops_completely (optimize
>= 3, false);
542 free_numbers_of_iterations_estimates ();
545 loop_optimizer_finalize ();
551 gate_tree_complete_unroll_inner (void)
553 return optimize
>= 2;
556 struct gimple_opt_pass pass_complete_unrolli
=
560 "cunrolli", /* name */
561 gate_tree_complete_unroll_inner
, /* gate */
562 tree_complete_unroll_inner
, /* execute */
565 0, /* static_pass_number */
566 TV_COMPLETE_UNROLL
, /* tv_id */
567 PROP_cfg
| PROP_ssa
, /* properties_required */
568 0, /* properties_provided */
569 0, /* properties_destroyed */
570 0, /* todo_flags_start */
572 | TODO_ggc_collect
/* todo_flags_finish */
576 /* Parallelization. */
579 gate_tree_parallelize_loops (void)
581 return flag_tree_parallelize_loops
> 1;
585 tree_parallelize_loops (void)
587 if (number_of_loops () <= 1)
590 if (parallelize_loops ())
591 return TODO_cleanup_cfg
| TODO_rebuild_alias
;
595 struct gimple_opt_pass pass_parallelize_loops
=
599 "parloops", /* name */
600 gate_tree_parallelize_loops
, /* gate */
601 tree_parallelize_loops
, /* execute */
604 0, /* static_pass_number */
605 TV_TREE_PARALLELIZE_LOOPS
, /* tv_id */
606 PROP_cfg
| PROP_ssa
, /* properties_required */
607 0, /* properties_provided */
608 0, /* properties_destroyed */
609 0, /* todo_flags_start */
610 TODO_dump_func
/* todo_flags_finish */
617 tree_ssa_loop_prefetch (void)
619 if (number_of_loops () <= 1)
622 return tree_ssa_prefetch_arrays ();
626 gate_tree_ssa_loop_prefetch (void)
628 return flag_prefetch_loop_arrays
> 0;
631 struct gimple_opt_pass pass_loop_prefetch
=
635 "aprefetch", /* name */
636 gate_tree_ssa_loop_prefetch
, /* gate */
637 tree_ssa_loop_prefetch
, /* execute */
640 0, /* static_pass_number */
641 TV_TREE_PREFETCH
, /* tv_id */
642 PROP_cfg
| PROP_ssa
, /* properties_required */
643 0, /* properties_provided */
644 0, /* properties_destroyed */
645 0, /* todo_flags_start */
646 TODO_dump_func
/* todo_flags_finish */
650 /* Induction variable optimizations. */
653 tree_ssa_loop_ivopts (void)
655 if (number_of_loops () <= 1)
658 tree_ssa_iv_optimize ();
663 gate_tree_ssa_loop_ivopts (void)
665 return flag_ivopts
!= 0;
668 struct gimple_opt_pass pass_iv_optimize
=
673 gate_tree_ssa_loop_ivopts
, /* gate */
674 tree_ssa_loop_ivopts
, /* execute */
677 0, /* static_pass_number */
678 TV_TREE_LOOP_IVOPTS
, /* tv_id */
679 PROP_cfg
| PROP_ssa
, /* properties_required */
680 0, /* properties_provided */
681 0, /* properties_destroyed */
682 0, /* todo_flags_start */
683 TODO_dump_func
| TODO_update_ssa
| TODO_ggc_collect
/* todo_flags_finish */
687 /* Loop optimizer finalization. */
690 tree_ssa_loop_done (void)
692 free_numbers_of_iterations_estimates ();
694 loop_optimizer_finalize ();
698 struct gimple_opt_pass pass_tree_loop_done
=
702 "loopdone", /* name */
704 tree_ssa_loop_done
, /* execute */
707 0, /* static_pass_number */
708 TV_TREE_LOOP_FINI
, /* tv_id */
709 PROP_cfg
, /* properties_required */
710 0, /* properties_provided */
711 0, /* properties_destroyed */
712 0, /* todo_flags_start */
713 TODO_cleanup_cfg
| TODO_dump_func
/* todo_flags_finish */