Daily bump.
[official-gcc.git] / gcc / loop-init.c
blob57f9768b37722f69b5ebc1a6e553f228947c069b
1 /* Loop optimizer initialization routines and RTL loop optimization passes.
2 Copyright (C) 2002, 2003, 2004, 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 under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "rtl.h"
25 #include "hard-reg-set.h"
26 #include "obstack.h"
27 #include "basic-block.h"
28 #include "cfgloop.h"
29 #include "cfglayout.h"
30 #include "tree-pass.h"
31 #include "timevar.h"
32 #include "flags.h"
33 #include "df.h"
34 #include "ggc.h"
37 /* Initialize loop structures. This is used by the tree and RTL loop
38 optimizers. FLAGS specify what properties to compute and/or ensure for
39 loops. */
41 void
42 loop_optimizer_init (unsigned flags)
44 struct loops *loops;
46 gcc_assert (!current_loops);
47 loops = GGC_CNEW (struct loops);
49 /* Find the loops. */
51 flow_loops_find (loops);
52 current_loops = loops;
54 if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
56 /* If the loops may have multiple latches, we cannot canonicalize
57 them further (and most of the loop manipulation functions will
58 not work). However, we avoid modifying cfg, which some
59 passes may want. */
60 gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
61 | LOOPS_HAVE_RECORDED_EXITS)) == 0);
62 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
64 else
65 disambiguate_loops_with_multiple_latches ();
67 /* Create pre-headers. */
68 if (flags & LOOPS_HAVE_PREHEADERS)
69 create_preheaders (CP_SIMPLE_PREHEADERS);
71 /* Force all latches to have only single successor. */
72 if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
73 force_single_succ_latches ();
75 /* Mark irreducible loops. */
76 if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
77 mark_irreducible_loops ();
79 if (flags & LOOPS_HAVE_RECORDED_EXITS)
80 record_loop_exits ();
82 /* Dump loops. */
83 flow_loops_dump (dump_file, NULL, 1);
85 #ifdef ENABLE_CHECKING
86 verify_dominators (CDI_DOMINATORS);
87 verify_loop_structure ();
88 #endif
91 /* Finalize loop structures. */
93 void
94 loop_optimizer_finalize (void)
96 loop_iterator li;
97 struct loop *loop;
98 basic_block bb;
100 gcc_assert (current_loops != NULL);
102 FOR_EACH_LOOP (li, loop, 0)
104 free_simple_loop_desc (loop);
107 /* Clean up. */
108 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
109 release_recorded_exits ();
110 flow_loops_free (current_loops);
111 ggc_free (current_loops);
112 current_loops = NULL;
114 FOR_ALL_BB (bb)
116 bb->loop_father = NULL;
119 /* Checking. */
120 #ifdef ENABLE_CHECKING
121 verify_flow_info ();
122 #endif
126 /* Gate for the RTL loop superpass. The actual passes are subpasses.
127 See passes.c for more on that. */
129 static bool
130 gate_handle_loop2 (void)
132 return (optimize > 0
133 && (flag_move_loop_invariants
134 || flag_unswitch_loops
135 || flag_peel_loops
136 || flag_unroll_loops
137 #ifdef HAVE_doloop_end
138 || (flag_branch_on_count_reg && HAVE_doloop_end)
139 #endif
143 struct tree_opt_pass pass_loop2 =
145 "loop2", /* name */
146 gate_handle_loop2, /* gate */
147 NULL, /* execute */
148 NULL, /* sub */
149 NULL, /* next */
150 0, /* static_pass_number */
151 TV_LOOP, /* tv_id */
152 0, /* properties_required */
153 0, /* properties_provided */
154 0, /* properties_destroyed */
155 0, /* todo_flags_start */
156 TODO_dump_func |
157 TODO_ggc_collect, /* todo_flags_finish */
158 'L' /* letter */
162 /* Initialization of the RTL loop passes. */
163 static unsigned int
164 rtl_loop_init (void)
166 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
168 if (dump_file)
169 dump_flow_info (dump_file, dump_flags);
171 loop_optimizer_init (LOOPS_NORMAL);
172 return 0;
175 struct tree_opt_pass pass_rtl_loop_init =
177 "loop2_init", /* name */
178 NULL, /* gate */
179 rtl_loop_init, /* execute */
180 NULL, /* sub */
181 NULL, /* next */
182 0, /* static_pass_number */
183 TV_LOOP, /* tv_id */
184 0, /* properties_required */
185 0, /* properties_provided */
186 0, /* properties_destroyed */
187 0, /* todo_flags_start */
188 TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */
189 'L' /* letter */
193 /* Finalization of the RTL loop passes. */
195 static unsigned int
196 rtl_loop_done (void)
198 loop_optimizer_finalize ();
199 free_dominance_info (CDI_DOMINATORS);
201 cleanup_cfg (0);
202 if (dump_file)
203 dump_flow_info (dump_file, dump_flags);
205 return 0;
208 struct tree_opt_pass pass_rtl_loop_done =
210 "loop2_done", /* name */
211 NULL, /* gate */
212 rtl_loop_done, /* execute */
213 NULL, /* sub */
214 NULL, /* next */
215 0, /* static_pass_number */
216 TV_LOOP, /* tv_id */
217 0, /* properties_required */
218 0, /* properties_provided */
219 0, /* properties_destroyed */
220 0, /* todo_flags_start */
221 TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */
222 'L' /* letter */
226 /* Loop invariant code motion. */
227 static bool
228 gate_rtl_move_loop_invariants (void)
230 return flag_move_loop_invariants;
233 static unsigned int
234 rtl_move_loop_invariants (void)
236 if (number_of_loops () > 1)
237 move_loop_invariants ();
238 return 0;
241 struct tree_opt_pass pass_rtl_move_loop_invariants =
243 "loop2_invariant", /* name */
244 gate_rtl_move_loop_invariants, /* gate */
245 rtl_move_loop_invariants, /* execute */
246 NULL, /* sub */
247 NULL, /* next */
248 0, /* static_pass_number */
249 TV_LOOP, /* tv_id */
250 0, /* properties_required */
251 0, /* properties_provided */
252 0, /* properties_destroyed */
253 0, /* todo_flags_start */
254 TODO_df_verify |
255 TODO_df_finish | TODO_verify_rtl_sharing |
256 TODO_dump_func, /* todo_flags_finish */
257 'L' /* letter */
261 /* Loop unswitching for RTL. */
262 static bool
263 gate_rtl_unswitch (void)
265 return flag_unswitch_loops;
268 static unsigned int
269 rtl_unswitch (void)
271 if (number_of_loops () > 1)
272 unswitch_loops ();
273 return 0;
276 struct tree_opt_pass pass_rtl_unswitch =
278 "loop2_unswitch", /* name */
279 gate_rtl_unswitch, /* gate */
280 rtl_unswitch, /* execute */
281 NULL, /* sub */
282 NULL, /* next */
283 0, /* static_pass_number */
284 TV_LOOP, /* tv_id */
285 0, /* properties_required */
286 0, /* properties_provided */
287 0, /* properties_destroyed */
288 0, /* todo_flags_start */
289 TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */
290 'L' /* letter */
294 /* Loop unswitching for RTL. */
295 static bool
296 gate_rtl_unroll_and_peel_loops (void)
298 return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
301 static unsigned int
302 rtl_unroll_and_peel_loops (void)
304 if (number_of_loops () > 1)
306 int flags = 0;
307 if (dump_file)
308 df_dump (dump_file);
310 if (flag_peel_loops)
311 flags |= UAP_PEEL;
312 if (flag_unroll_loops)
313 flags |= UAP_UNROLL;
314 if (flag_unroll_all_loops)
315 flags |= UAP_UNROLL_ALL;
317 unroll_and_peel_loops (flags);
319 return 0;
322 struct tree_opt_pass pass_rtl_unroll_and_peel_loops =
324 "loop2_unroll", /* name */
325 gate_rtl_unroll_and_peel_loops, /* gate */
326 rtl_unroll_and_peel_loops, /* execute */
327 NULL, /* sub */
328 NULL, /* next */
329 0, /* static_pass_number */
330 TV_LOOP, /* tv_id */
331 0, /* properties_required */
332 0, /* properties_provided */
333 0, /* properties_destroyed */
334 0, /* todo_flags_start */
335 TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */
336 'L' /* letter */
340 /* The doloop optimization. */
341 static bool
342 gate_rtl_doloop (void)
344 #ifdef HAVE_doloop_end
345 return (flag_branch_on_count_reg && HAVE_doloop_end);
346 #else
347 return 0;
348 #endif
351 static unsigned int
352 rtl_doloop (void)
354 #ifdef HAVE_doloop_end
355 if (number_of_loops () > 1)
356 doloop_optimize_loops ();
357 #endif
358 return 0;
361 struct tree_opt_pass pass_rtl_doloop =
363 "loop2_doloop", /* name */
364 gate_rtl_doloop, /* gate */
365 rtl_doloop, /* execute */
366 NULL, /* sub */
367 NULL, /* next */
368 0, /* static_pass_number */
369 TV_LOOP, /* tv_id */
370 0, /* properties_required */
371 0, /* properties_provided */
372 0, /* properties_destroyed */
373 0, /* todo_flags_start */
374 TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */
375 'L' /* letter */