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 2, 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 COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
34 #include "tree-pass.h"
38 #include "tree-inline.h"
39 #include "tree-scalar-evolution.h"
41 /* Initializes the loop structures. */
44 tree_loop_optimizer_init (void)
46 loop_optimizer_init (LOOPS_NORMAL
47 | LOOPS_HAVE_RECORDED_EXITS);
51 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
54 /* The loop superpass. */
59 return flag_tree_loop_optimize != 0;
62 struct tree_opt_pass pass_tree_loop =
65 gate_tree_loop, /* gate */
69 0, /* static_pass_number */
70 TV_TREE_LOOP, /* tv_id */
71 PROP_cfg, /* properties_required */
72 0, /* properties_provided */
73 0, /* properties_destroyed */
74 TODO_ggc_collect, /* todo_flags_start */
75 TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect, /* todo_flags_finish */
79 /* Loop optimizer initialization. */
82 tree_ssa_loop_init (void)
84 tree_loop_optimizer_init ();
92 struct tree_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)
122 gate_tree_ssa_loop_im (void)
124 return flag_tree_loop_im != 0;
127 struct tree_opt_pass pass_lim =
130 gate_tree_ssa_loop_im, /* gate */
131 tree_ssa_loop_im, /* execute */
134 0, /* static_pass_number */
136 PROP_cfg, /* properties_required */
137 0, /* properties_provided */
138 0, /* properties_destroyed */
139 0, /* todo_flags_start */
140 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */
144 /* Loop unswitching pass. */
147 tree_ssa_loop_unswitch (void)
152 return tree_ssa_unswitch_loops ();
156 gate_tree_ssa_loop_unswitch (void)
158 return flag_unswitch_loops != 0;
161 struct tree_opt_pass pass_tree_unswitch =
163 "unswitch", /* name */
164 gate_tree_ssa_loop_unswitch, /* gate */
165 tree_ssa_loop_unswitch, /* execute */
168 0, /* static_pass_number */
169 TV_TREE_LOOP_UNSWITCH, /* tv_id */
170 PROP_cfg, /* properties_required */
171 0, /* properties_provided */
172 0, /* properties_destroyed */
173 0, /* todo_flags_start */
174 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */
178 /* Loop autovectorization. */
181 tree_vectorize (void)
183 return vectorize_loops ();
187 gate_tree_vectorize (void)
189 return flag_tree_vectorize && current_loops;
192 struct tree_opt_pass pass_vectorize =
195 gate_tree_vectorize, /* gate */
196 tree_vectorize, /* execute */
199 0, /* static_pass_number */
200 TV_TREE_VECTORIZATION, /* tv_id */
201 PROP_cfg | PROP_ssa, /* properties_required */
202 0, /* properties_provided */
203 0, /* properties_destroyed */
204 TODO_verify_loops, /* todo_flags_start */
205 TODO_dump_func | TODO_update_ssa, /* todo_flags_finish */
209 /* Loop nest optimizations. */
212 tree_linear_transform (void)
217 linear_transform_loops ();
222 gate_tree_linear_transform (void)
224 return flag_tree_loop_linear != 0;
227 struct tree_opt_pass pass_linear_transform =
230 gate_tree_linear_transform, /* gate */
231 tree_linear_transform, /* execute */
234 0, /* static_pass_number */
235 TV_TREE_LINEAR_TRANSFORM, /* tv_id */
236 PROP_cfg | PROP_ssa, /* properties_required */
237 0, /* properties_provided */
238 0, /* properties_destroyed */
239 0, /* todo_flags_start */
240 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */
244 /* Check the correctness of the data dependence analyzers. */
247 check_data_deps (void)
252 tree_check_data_deps ();
257 gate_check_data_deps (void)
259 return flag_check_data_deps != 0;
262 struct tree_opt_pass pass_check_data_deps =
265 gate_check_data_deps, /* gate */
266 check_data_deps, /* execute */
269 0, /* static_pass_number */
270 TV_CHECK_DATA_DEPS, /* tv_id */
271 PROP_cfg | PROP_ssa, /* properties_required */
272 0, /* properties_provided */
273 0, /* properties_destroyed */
274 0, /* todo_flags_start */
275 TODO_dump_func, /* todo_flags_finish */
279 /* Canonical induction variable creation pass. */
282 tree_ssa_loop_ivcanon (void)
287 return canonicalize_induction_variables ();
291 gate_tree_ssa_loop_ivcanon (void)
293 return flag_tree_loop_ivcanon != 0;
296 struct tree_opt_pass pass_iv_canon =
298 "ivcanon", /* name */
299 gate_tree_ssa_loop_ivcanon, /* gate */
300 tree_ssa_loop_ivcanon, /* execute */
303 0, /* static_pass_number */
304 TV_TREE_LOOP_IVCANON, /* tv_id */
305 PROP_cfg | PROP_ssa, /* properties_required */
306 0, /* properties_provided */
307 0, /* properties_destroyed */
308 0, /* todo_flags_start */
309 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */
313 /* Propagation of constants using scev. */
316 gate_scev_const_prop (void)
318 return flag_tree_scev_cprop;
321 struct tree_opt_pass pass_scev_cprop =
324 gate_scev_const_prop, /* gate */
325 scev_const_prop, /* execute */
328 0, /* static_pass_number */
329 TV_SCEV_CONST, /* tv_id */
330 PROP_cfg | PROP_ssa, /* properties_required */
331 0, /* properties_provided */
332 0, /* properties_destroyed */
333 0, /* todo_flags_start */
334 TODO_dump_func | TODO_cleanup_cfg
335 | TODO_update_ssa_only_virtuals,
336 /* todo_flags_finish */
340 /* Remove empty loops. */
343 tree_ssa_empty_loop (void)
348 return remove_empty_loops ();
351 struct tree_opt_pass pass_empty_loop =
355 tree_ssa_empty_loop, /* execute */
358 0, /* static_pass_number */
359 TV_COMPLETE_UNROLL, /* tv_id */
360 PROP_cfg | PROP_ssa, /* properties_required */
361 0, /* properties_provided */
362 0, /* properties_destroyed */
363 0, /* todo_flags_start */
364 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */
368 /* Record bounds on numbers of iterations of loops. */
371 tree_ssa_loop_bounds (void)
376 estimate_numbers_of_iterations ();
381 struct tree_opt_pass pass_record_bounds =
385 tree_ssa_loop_bounds, /* execute */
388 0, /* static_pass_number */
389 TV_TREE_LOOP_BOUNDS, /* tv_id */
390 PROP_cfg | PROP_ssa, /* properties_required */
391 0, /* properties_provided */
392 0, /* properties_destroyed */
393 0, /* todo_flags_start */
394 0, /* todo_flags_finish */
398 /* Complete unrolling of loops. */
401 tree_complete_unroll (void)
406 return tree_unroll_loops_completely (flag_unroll_loops
412 gate_tree_complete_unroll (void)
417 struct tree_opt_pass pass_complete_unroll =
419 "cunroll", /* name */
420 gate_tree_complete_unroll, /* gate */
421 tree_complete_unroll, /* execute */
424 0, /* static_pass_number */
425 TV_COMPLETE_UNROLL, /* tv_id */
426 PROP_cfg | PROP_ssa, /* properties_required */
427 0, /* properties_provided */
428 0, /* properties_destroyed */
429 0, /* todo_flags_start */
430 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */
437 tree_ssa_loop_prefetch (void)
442 return tree_ssa_prefetch_arrays ();
446 gate_tree_ssa_loop_prefetch (void)
448 return flag_prefetch_loop_arrays != 0;
451 struct tree_opt_pass pass_loop_prefetch =
453 "aprefetch", /* name */
454 gate_tree_ssa_loop_prefetch, /* gate */
455 tree_ssa_loop_prefetch, /* execute */
458 0, /* static_pass_number */
459 TV_TREE_PREFETCH, /* tv_id */
460 PROP_cfg | PROP_ssa, /* properties_required */
461 0, /* properties_provided */
462 0, /* properties_destroyed */
463 0, /* todo_flags_start */
464 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */
468 /* Induction variable optimizations. */
471 tree_ssa_loop_ivopts (void)
476 tree_ssa_iv_optimize ();
481 gate_tree_ssa_loop_ivopts (void)
483 return flag_ivopts != 0;
486 struct tree_opt_pass pass_iv_optimize =
489 gate_tree_ssa_loop_ivopts, /* gate */
490 tree_ssa_loop_ivopts, /* execute */
493 0, /* static_pass_number */
494 TV_TREE_LOOP_IVOPTS, /* tv_id */
495 PROP_cfg | PROP_ssa, /* properties_required */
496 0, /* properties_provided */
497 0, /* properties_destroyed */
498 0, /* todo_flags_start */
501 | TODO_update_ssa, /* todo_flags_finish */
505 /* Loop optimizer finalization. */
508 tree_ssa_loop_done (void)
513 free_numbers_of_iterations_estimates ();
515 loop_optimizer_finalize ();
519 struct tree_opt_pass pass_tree_loop_done =
521 "loopdone", /* name */
523 tree_ssa_loop_done, /* execute */
526 0, /* static_pass_number */
527 TV_TREE_LOOP_FINI, /* tv_id */
528 PROP_cfg, /* properties_required */
529 0, /* properties_provided */
530 0, /* properties_destroyed */
531 0, /* todo_flags_start */
532 TODO_cleanup_cfg | TODO_dump_func, /* todo_flags_finish */