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 */