1 /* Loop optimizations over tree-ssa.
2 Copyright (C) 2003, 2005 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, 59 Temple Place - Suite 330, 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 /* The loop tree currently optimized. */
43 struct loops *current_loops;
45 /* Initializes the loop structures. DUMP is the file to that the details
46 about the analysis should be dumped. */
49 tree_loop_optimizer_init (FILE *dump)
51 struct loops *loops = loop_optimizer_init (dump);
56 update_ssa (TODO_update_ssa);
57 rewrite_into_loop_closed_ssa (NULL);
62 /* The loop superpass. */
67 return flag_tree_loop_optimize != 0;
70 struct tree_opt_pass pass_loop =
77 0, /* static_pass_number */
78 TV_TREE_LOOP, /* tv_id */
79 PROP_cfg, /* properties_required */
80 0, /* properties_provided */
81 0, /* properties_destroyed */
82 TODO_ggc_collect, /* todo_flags_start */
83 TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect, /* todo_flags_finish */
87 /* Loop optimizer initialization. */
90 tree_ssa_loop_init (void)
92 current_loops = tree_loop_optimizer_init (dump_file);
96 /* Find the loops that are exited just through a single edge. */
97 mark_single_exit_loops (current_loops);
99 scev_initialize (current_loops);
102 struct tree_opt_pass pass_loop_init =
104 "loopinit", /* name */
106 tree_ssa_loop_init, /* execute */
109 0, /* static_pass_number */
110 TV_TREE_LOOP_INIT, /* tv_id */
111 PROP_cfg, /* properties_required */
112 0, /* properties_provided */
113 0, /* properties_destroyed */
114 0, /* todo_flags_start */
115 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */
119 /* Loop invariant motion pass. */
122 tree_ssa_loop_im (void)
127 tree_ssa_lim (current_loops);
131 gate_tree_ssa_loop_im (void)
133 return flag_tree_loop_im != 0;
136 struct tree_opt_pass pass_lim =
139 gate_tree_ssa_loop_im, /* gate */
140 tree_ssa_loop_im, /* execute */
143 0, /* static_pass_number */
145 PROP_cfg, /* properties_required */
146 0, /* properties_provided */
147 0, /* properties_destroyed */
148 0, /* todo_flags_start */
149 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */
153 /* Loop unswitching pass. */
156 tree_ssa_loop_unswitch (void)
161 tree_ssa_unswitch_loops (current_loops);
165 gate_tree_ssa_loop_unswitch (void)
167 return flag_unswitch_loops != 0;
170 struct tree_opt_pass pass_unswitch =
172 "unswitch", /* name */
173 gate_tree_ssa_loop_unswitch, /* gate */
174 tree_ssa_loop_unswitch, /* execute */
177 0, /* static_pass_number */
178 TV_TREE_LOOP_UNSWITCH, /* tv_id */
179 PROP_cfg, /* properties_required */
180 0, /* properties_provided */
181 0, /* properties_destroyed */
182 0, /* todo_flags_start */
183 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */
187 /* Loop autovectorization. */
190 tree_vectorize (void)
195 vectorize_loops (current_loops);
199 gate_tree_vectorize (void)
201 return flag_tree_vectorize != 0;
204 struct tree_opt_pass pass_vectorize =
207 gate_tree_vectorize, /* gate */
208 tree_vectorize, /* execute */
211 0, /* static_pass_number */
212 TV_TREE_VECTORIZATION, /* tv_id */
213 PROP_cfg | PROP_ssa, /* properties_required */
214 0, /* properties_provided */
215 0, /* properties_destroyed */
216 0, /* todo_flags_start */
217 TODO_dump_func | TODO_update_ssa, /* todo_flags_finish */
222 /* Loop nest optimizations. */
225 tree_linear_transform (void)
230 linear_transform_loops (current_loops);
234 gate_tree_linear_transform (void)
236 return flag_tree_loop_linear != 0;
239 struct tree_opt_pass pass_linear_transform =
242 gate_tree_linear_transform, /* gate */
243 tree_linear_transform, /* execute */
246 0, /* static_pass_number */
247 TV_TREE_LINEAR_TRANSFORM, /* tv_id */
248 PROP_cfg | PROP_ssa, /* properties_required */
249 0, /* properties_provided */
250 0, /* properties_destroyed */
251 0, /* todo_flags_start */
252 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */
256 /* Canonical induction variable creation pass. */
259 tree_ssa_loop_ivcanon (void)
264 canonicalize_induction_variables (current_loops);
268 gate_tree_ssa_loop_ivcanon (void)
270 return flag_tree_loop_ivcanon != 0;
273 struct tree_opt_pass pass_iv_canon =
275 "ivcanon", /* name */
276 gate_tree_ssa_loop_ivcanon, /* gate */
277 tree_ssa_loop_ivcanon, /* execute */
280 0, /* static_pass_number */
281 TV_TREE_LOOP_IVCANON, /* tv_id */
282 PROP_cfg | PROP_ssa, /* properties_required */
283 0, /* properties_provided */
284 0, /* properties_destroyed */
285 0, /* todo_flags_start */
286 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */
290 /* Record bounds on numbers of iterations of loops. */
293 tree_ssa_loop_bounds (void)
298 estimate_numbers_of_iterations (current_loops);
302 struct tree_opt_pass pass_record_bounds =
306 tree_ssa_loop_bounds, /* execute */
309 0, /* static_pass_number */
310 TV_TREE_LOOP_BOUNDS, /* tv_id */
311 PROP_cfg | PROP_ssa, /* properties_required */
312 0, /* properties_provided */
313 0, /* properties_destroyed */
314 0, /* todo_flags_start */
315 0, /* todo_flags_finish */
319 /* Complete unrolling of loops. */
322 tree_complete_unroll (void)
327 tree_unroll_loops_completely (current_loops);
331 gate_tree_complete_unroll (void)
333 return flag_peel_loops || flag_unroll_loops;
336 struct tree_opt_pass pass_complete_unroll =
338 "cunroll", /* name */
339 gate_tree_complete_unroll, /* gate */
340 tree_complete_unroll, /* execute */
343 0, /* static_pass_number */
344 TV_COMPLETE_UNROLL, /* tv_id */
345 PROP_cfg | PROP_ssa, /* properties_required */
346 0, /* properties_provided */
347 0, /* properties_destroyed */
348 0, /* todo_flags_start */
349 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */
353 /* Induction variable optimizations. */
356 tree_ssa_loop_ivopts (void)
361 tree_ssa_iv_optimize (current_loops);
365 gate_tree_ssa_loop_ivopts (void)
367 return flag_ivopts != 0;
370 struct tree_opt_pass pass_iv_optimize =
373 gate_tree_ssa_loop_ivopts, /* gate */
374 tree_ssa_loop_ivopts, /* execute */
377 0, /* static_pass_number */
378 TV_TREE_LOOP_IVOPTS, /* tv_id */
379 PROP_cfg | PROP_ssa, /* properties_required */
380 0, /* properties_provided */
381 0, /* properties_destroyed */
382 0, /* todo_flags_start */
383 TODO_dump_func | TODO_verify_loops, /* todo_flags_finish */
387 /* Loop optimizer finalization. */
390 tree_ssa_loop_done (void)
395 free_numbers_of_iterations_estimates (current_loops);
397 loop_optimizer_finalize (current_loops,
398 (dump_flags & TDF_DETAILS ? dump_file : NULL));
399 current_loops = NULL;
402 struct tree_opt_pass pass_loop_done =
404 "loopdone", /* name */
406 tree_ssa_loop_done, /* execute */
409 0, /* static_pass_number */
410 TV_TREE_LOOP_FINI, /* tv_id */
411 PROP_cfg, /* properties_required */
412 0, /* properties_provided */
413 0, /* properties_destroyed */
414 0, /* todo_flags_start */
415 TODO_cleanup_cfg | TODO_dump_func, /* todo_flags_finish */