1 /* Loop optimizations over tree-ssa.
2 Copyright (C) 2003 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 /* Creation of preheaders may create redundant phi nodes if the loop is
57 entered by more than one edge, but the initial value of the induction
58 variable is the same on all of them. */
59 kill_redundant_phi_nodes ();
60 rewrite_into_ssa (false);
61 bitmap_clear (vars_to_rename
);
63 rewrite_into_loop_closed_ssa ();
64 #ifdef ENABLE_CHECKING
65 verify_loop_closed_ssa ();
71 /* The loop superpass. */
76 return flag_tree_loop_optimize
!= 0;
79 struct tree_opt_pass pass_loop
=
86 0, /* static_pass_number */
87 TV_TREE_LOOP
, /* tv_id */
88 PROP_cfg
, /* properties_required */
89 0, /* properties_provided */
90 0, /* properties_destroyed */
91 TODO_ggc_collect
, /* todo_flags_start */
92 TODO_dump_func
| TODO_verify_ssa
| TODO_ggc_collect
, /* todo_flags_finish */
96 /* Loop optimizer initialization. */
99 tree_ssa_loop_init (void)
101 current_loops
= tree_loop_optimizer_init (dump_file
);
105 /* Find the loops that are exited just through a single edge. */
106 mark_single_exit_loops (current_loops
);
108 scev_initialize (current_loops
);
111 struct tree_opt_pass pass_loop_init
=
113 "loopinit", /* name */
115 tree_ssa_loop_init
, /* execute */
118 0, /* static_pass_number */
120 PROP_cfg
, /* properties_required */
121 0, /* properties_provided */
122 0, /* properties_destroyed */
123 0, /* todo_flags_start */
124 TODO_dump_func
, /* todo_flags_finish */
128 /* Loop invariant motion pass. */
131 tree_ssa_loop_im (void)
136 tree_ssa_lim (current_loops
);
140 gate_tree_ssa_loop_im (void)
142 return flag_tree_loop_im
!= 0;
145 struct tree_opt_pass pass_lim
=
148 gate_tree_ssa_loop_im
, /* gate */
149 tree_ssa_loop_im
, /* execute */
152 0, /* static_pass_number */
154 PROP_cfg
, /* properties_required */
155 0, /* properties_provided */
156 0, /* properties_destroyed */
157 0, /* todo_flags_start */
158 TODO_dump_func
, /* todo_flags_finish */
162 /* Loop autovectorization. */
165 tree_vectorize (void)
170 bitmap_clear (vars_to_rename
);
171 vectorize_loops (current_loops
);
175 gate_tree_vectorize (void)
177 return flag_tree_vectorize
!= 0;
180 struct tree_opt_pass pass_vectorize
=
183 gate_tree_vectorize
, /* gate */
184 tree_vectorize
, /* execute */
187 0, /* static_pass_number */
188 TV_TREE_VECTORIZATION
, /* tv_id */
189 PROP_cfg
| PROP_ssa
, /* properties_required */
190 0, /* properties_provided */
191 0, /* properties_destroyed */
192 0, /* todo_flags_start */
193 TODO_dump_func
, /* todo_flags_finish */
198 /* Loop nest optimizations. */
201 tree_linear_transform (void)
206 linear_transform_loops (current_loops
);
210 gate_tree_linear_transform (void)
212 return flag_tree_loop_linear
!= 0;
215 struct tree_opt_pass pass_linear_transform
=
218 gate_tree_linear_transform
, /* gate */
219 tree_linear_transform
, /* execute */
222 0, /* static_pass_number */
223 TV_TREE_LINEAR_TRANSFORM
, /* tv_id */
224 PROP_cfg
| PROP_ssa
, /* properties_required */
225 0, /* properties_provided */
226 0, /* properties_destroyed */
227 0, /* todo_flags_start */
228 TODO_dump_func
, /* todo_flags_finish */
232 /* Canonical induction variable creation pass. */
235 tree_ssa_loop_ivcanon (void)
240 canonicalize_induction_variables (current_loops
);
244 gate_tree_ssa_loop_ivcanon (void)
246 return flag_tree_loop_ivcanon
!= 0;
249 struct tree_opt_pass pass_iv_canon
=
251 "ivcanon", /* name */
252 gate_tree_ssa_loop_ivcanon
, /* gate */
253 tree_ssa_loop_ivcanon
, /* execute */
256 0, /* static_pass_number */
257 TV_TREE_LOOP_IVCANON
, /* tv_id */
258 PROP_cfg
| PROP_ssa
, /* properties_required */
259 0, /* properties_provided */
260 0, /* properties_destroyed */
261 0, /* todo_flags_start */
262 TODO_dump_func
, /* todo_flags_finish */
266 /* Complete unrolling of loops. */
269 tree_complete_unroll (void)
274 tree_unroll_loops_completely (current_loops
);
278 gate_tree_complete_unroll (void)
280 return flag_unroll_loops
!= 0;
283 struct tree_opt_pass pass_complete_unroll
=
285 "cunroll", /* name */
286 gate_tree_complete_unroll
, /* gate */
287 tree_complete_unroll
, /* execute */
290 0, /* static_pass_number */
291 TV_COMPLETE_UNROLL
, /* tv_id */
292 PROP_cfg
| PROP_ssa
, /* properties_required */
293 0, /* properties_provided */
294 0, /* properties_destroyed */
295 0, /* todo_flags_start */
296 TODO_dump_func
, /* todo_flags_finish */
300 /* Induction variable optimizations. */
303 tree_ssa_loop_ivopts (void)
308 tree_ssa_iv_optimize (current_loops
);
312 gate_tree_ssa_loop_ivopts (void)
314 return flag_ivopts
!= 0;
317 struct tree_opt_pass pass_iv_optimize
=
320 gate_tree_ssa_loop_ivopts
, /* gate */
321 tree_ssa_loop_ivopts
, /* execute */
324 0, /* static_pass_number */
325 TV_TREE_LOOP_IVOPTS
, /* tv_id */
326 PROP_cfg
| PROP_ssa
, /* properties_required */
327 0, /* properties_provided */
328 0, /* properties_destroyed */
329 0, /* todo_flags_start */
330 TODO_dump_func
, /* todo_flags_finish */
334 /* Loop optimizer finalization. */
337 tree_ssa_loop_done (void)
342 #ifdef ENABLE_CHECKING
343 verify_loop_closed_ssa ();
346 free_numbers_of_iterations_estimates (current_loops
);
348 loop_optimizer_finalize (current_loops
,
349 (dump_flags
& TDF_DETAILS
? dump_file
: NULL
));
350 current_loops
= NULL
;
354 struct tree_opt_pass pass_loop_done
=
356 "loopdone", /* name */
358 tree_ssa_loop_done
, /* execute */
361 0, /* static_pass_number */
363 PROP_cfg
, /* properties_required */
364 0, /* properties_provided */
365 0, /* properties_destroyed */
366 0, /* todo_flags_start */
367 TODO_dump_func
, /* todo_flags_finish */