2012-11-28 Oleg Raikhman <oleg@adapteva.com>
[official-gcc.git] / gcc / loop-init.c
blobf140686ba1168534b3ee8137a0cf3e2cdb4cb8e2
1 /* Loop optimizer initialization routines and RTL loop optimization passes.
2 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "regs.h"
27 #include "obstack.h"
28 #include "basic-block.h"
29 #include "cfgloop.h"
30 #include "tree-pass.h"
31 #include "flags.h"
32 #include "df.h"
33 #include "ggc.h"
36 /* Initialize loop structures. This is used by the tree and RTL loop
37 optimizers. FLAGS specify what properties to compute and/or ensure for
38 loops. */
40 void
41 loop_optimizer_init (unsigned flags)
43 timevar_push (TV_LOOP_INIT);
44 if (!current_loops)
46 struct loops *loops = ggc_alloc_cleared_loops ();
48 gcc_assert (!(cfun->curr_properties & PROP_loops));
50 /* Find the loops. */
52 flow_loops_find (loops);
53 current_loops = loops;
55 else
57 gcc_assert (cfun->curr_properties & PROP_loops);
59 /* Ensure that the dominators are computed, like flow_loops_find does. */
60 calculate_dominance_info (CDI_DOMINATORS);
62 #ifdef ENABLE_CHECKING
63 verify_loop_structure ();
64 #endif
67 if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
69 /* If the loops may have multiple latches, we cannot canonicalize
70 them further (and most of the loop manipulation functions will
71 not work). However, we avoid modifying cfg, which some
72 passes may want. */
73 gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
74 | LOOPS_HAVE_RECORDED_EXITS)) == 0);
75 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
77 else
78 disambiguate_loops_with_multiple_latches ();
80 /* Create pre-headers. */
81 if (flags & LOOPS_HAVE_PREHEADERS)
83 int cp_flags = CP_SIMPLE_PREHEADERS;
85 if (flags & LOOPS_HAVE_FALLTHRU_PREHEADERS)
86 cp_flags |= CP_FALLTHRU_PREHEADERS;
88 create_preheaders (cp_flags);
91 /* Force all latches to have only single successor. */
92 if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
93 force_single_succ_latches ();
95 /* Mark irreducible loops. */
96 if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
97 mark_irreducible_loops ();
99 if (flags & LOOPS_HAVE_RECORDED_EXITS)
100 record_loop_exits ();
102 /* Dump loops. */
103 flow_loops_dump (dump_file, NULL, 1);
105 #ifdef ENABLE_CHECKING
106 verify_loop_structure ();
107 #endif
109 timevar_pop (TV_LOOP_INIT);
112 /* Finalize loop structures. */
114 void
115 loop_optimizer_finalize (void)
117 loop_iterator li;
118 struct loop *loop;
119 basic_block bb;
121 timevar_push (TV_LOOP_FINI);
123 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
124 release_recorded_exits ();
126 /* If we should preserve loop structure, do not free it but clear
127 flags that advanced properties are there as we are not preserving
128 that in full. */
129 if (cfun->curr_properties & PROP_loops)
131 loops_state_clear (LOOP_CLOSED_SSA
132 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
133 | LOOPS_HAVE_PREHEADERS
134 | LOOPS_HAVE_SIMPLE_LATCHES
135 | LOOPS_HAVE_FALLTHRU_PREHEADERS);
136 goto loop_fini_done;
139 gcc_assert (current_loops != NULL);
141 FOR_EACH_LOOP (li, loop, 0)
143 free_simple_loop_desc (loop);
146 /* Clean up. */
147 flow_loops_free (current_loops);
148 ggc_free (current_loops);
149 current_loops = NULL;
151 FOR_ALL_BB (bb)
153 bb->loop_father = NULL;
156 loop_fini_done:
157 timevar_pop (TV_LOOP_FINI);
161 /* Gate for the RTL loop superpass. The actual passes are subpasses.
162 See passes.c for more on that. */
164 static bool
165 gate_handle_loop2 (void)
167 if (optimize > 0
168 && (flag_move_loop_invariants
169 || flag_unswitch_loops
170 || flag_peel_loops
171 || flag_unroll_loops
172 #ifdef HAVE_doloop_end
173 || (flag_branch_on_count_reg && HAVE_doloop_end)
174 #endif
176 return true;
177 else
179 /* No longer preserve loops, remove them now. */
180 cfun->curr_properties &= ~PROP_loops;
181 if (current_loops)
182 loop_optimizer_finalize ();
183 return false;
187 struct rtl_opt_pass pass_loop2 =
190 RTL_PASS,
191 "loop2", /* name */
192 OPTGROUP_LOOP, /* optinfo_flags */
193 gate_handle_loop2, /* gate */
194 NULL, /* execute */
195 NULL, /* sub */
196 NULL, /* next */
197 0, /* static_pass_number */
198 TV_LOOP, /* tv_id */
199 0, /* properties_required */
200 0, /* properties_provided */
201 0, /* properties_destroyed */
202 0, /* todo_flags_start */
203 TODO_ggc_collect /* todo_flags_finish */
208 /* Initialization of the RTL loop passes. */
209 static unsigned int
210 rtl_loop_init (void)
212 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
214 if (dump_file)
216 dump_reg_info (dump_file);
217 dump_flow_info (dump_file, dump_flags);
220 loop_optimizer_init (LOOPS_NORMAL);
221 return 0;
224 struct rtl_opt_pass pass_rtl_loop_init =
227 RTL_PASS,
228 "loop2_init", /* name */
229 OPTGROUP_LOOP, /* optinfo_flags */
230 NULL, /* gate */
231 rtl_loop_init, /* execute */
232 NULL, /* sub */
233 NULL, /* next */
234 0, /* static_pass_number */
235 TV_LOOP, /* tv_id */
236 0, /* properties_required */
237 0, /* properties_provided */
238 0, /* properties_destroyed */
239 0, /* todo_flags_start */
240 TODO_verify_rtl_sharing /* todo_flags_finish */
245 /* Finalization of the RTL loop passes. */
247 static unsigned int
248 rtl_loop_done (void)
250 /* No longer preserve loops, remove them now. */
251 cfun->curr_properties &= ~PROP_loops;
252 loop_optimizer_finalize ();
253 free_dominance_info (CDI_DOMINATORS);
255 cleanup_cfg (0);
256 if (dump_file)
258 dump_reg_info (dump_file);
259 dump_flow_info (dump_file, dump_flags);
262 return 0;
265 struct rtl_opt_pass pass_rtl_loop_done =
268 RTL_PASS,
269 "loop2_done", /* name */
270 OPTGROUP_LOOP, /* optinfo_flags */
271 NULL, /* gate */
272 rtl_loop_done, /* execute */
273 NULL, /* sub */
274 NULL, /* next */
275 0, /* static_pass_number */
276 TV_LOOP, /* tv_id */
277 0, /* properties_required */
278 0, /* properties_provided */
279 PROP_loops, /* properties_destroyed */
280 0, /* todo_flags_start */
281 TODO_verify_flow
282 | TODO_verify_rtl_sharing /* todo_flags_finish */
287 /* Loop invariant code motion. */
288 static bool
289 gate_rtl_move_loop_invariants (void)
291 return flag_move_loop_invariants;
294 static unsigned int
295 rtl_move_loop_invariants (void)
297 if (number_of_loops () > 1)
298 move_loop_invariants ();
299 return 0;
302 struct rtl_opt_pass pass_rtl_move_loop_invariants =
305 RTL_PASS,
306 "loop2_invariant", /* name */
307 OPTGROUP_LOOP, /* optinfo_flags */
308 gate_rtl_move_loop_invariants, /* gate */
309 rtl_move_loop_invariants, /* execute */
310 NULL, /* sub */
311 NULL, /* next */
312 0, /* static_pass_number */
313 TV_LOOP_MOVE_INVARIANTS, /* tv_id */
314 0, /* properties_required */
315 0, /* properties_provided */
316 0, /* properties_destroyed */
317 0, /* todo_flags_start */
318 TODO_df_verify |
319 TODO_df_finish | TODO_verify_rtl_sharing /* todo_flags_finish */
324 /* Loop unswitching for RTL. */
325 static bool
326 gate_rtl_unswitch (void)
328 return flag_unswitch_loops;
331 static unsigned int
332 rtl_unswitch (void)
334 if (number_of_loops () > 1)
335 unswitch_loops ();
336 return 0;
339 struct rtl_opt_pass pass_rtl_unswitch =
342 RTL_PASS,
343 "loop2_unswitch", /* name */
344 OPTGROUP_LOOP, /* optinfo_flags */
345 gate_rtl_unswitch, /* gate */
346 rtl_unswitch, /* execute */
347 NULL, /* sub */
348 NULL, /* next */
349 0, /* static_pass_number */
350 TV_LOOP_UNSWITCH, /* tv_id */
351 0, /* properties_required */
352 0, /* properties_provided */
353 0, /* properties_destroyed */
354 0, /* todo_flags_start */
355 TODO_verify_rtl_sharing, /* todo_flags_finish */
360 /* Loop unswitching for RTL. */
361 static bool
362 gate_rtl_unroll_and_peel_loops (void)
364 return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
367 static unsigned int
368 rtl_unroll_and_peel_loops (void)
370 if (number_of_loops () > 1)
372 int flags = 0;
373 if (dump_file)
374 df_dump (dump_file);
376 if (flag_peel_loops)
377 flags |= UAP_PEEL;
378 if (flag_unroll_loops)
379 flags |= UAP_UNROLL;
380 if (flag_unroll_all_loops)
381 flags |= UAP_UNROLL_ALL;
383 unroll_and_peel_loops (flags);
385 return 0;
388 struct rtl_opt_pass pass_rtl_unroll_and_peel_loops =
391 RTL_PASS,
392 "loop2_unroll", /* name */
393 OPTGROUP_LOOP, /* optinfo_flags */
394 gate_rtl_unroll_and_peel_loops, /* gate */
395 rtl_unroll_and_peel_loops, /* execute */
396 NULL, /* sub */
397 NULL, /* next */
398 0, /* static_pass_number */
399 TV_LOOP_UNROLL, /* tv_id */
400 0, /* properties_required */
401 0, /* properties_provided */
402 0, /* properties_destroyed */
403 0, /* todo_flags_start */
404 TODO_verify_rtl_sharing, /* todo_flags_finish */
409 /* The doloop optimization. */
410 static bool
411 gate_rtl_doloop (void)
413 #ifdef HAVE_doloop_end
414 return (flag_branch_on_count_reg && HAVE_doloop_end);
415 #else
416 return 0;
417 #endif
420 static unsigned int
421 rtl_doloop (void)
423 #ifdef HAVE_doloop_end
424 if (number_of_loops () > 1)
425 doloop_optimize_loops ();
426 #endif
427 return 0;
430 struct rtl_opt_pass pass_rtl_doloop =
433 RTL_PASS,
434 "loop2_doloop", /* name */
435 OPTGROUP_LOOP, /* optinfo_flags */
436 gate_rtl_doloop, /* gate */
437 rtl_doloop, /* execute */
438 NULL, /* sub */
439 NULL, /* next */
440 0, /* static_pass_number */
441 TV_LOOP_DOLOOP, /* tv_id */
442 0, /* properties_required */
443 0, /* properties_provided */
444 0, /* properties_destroyed */
445 0, /* todo_flags_start */
446 TODO_verify_rtl_sharing /* todo_flags_finish */