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
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
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/>. */
23 #include "coretypes.h"
28 #include "basic-block.h"
30 #include "tree-pass.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
41 loop_optimizer_init (unsigned flags
)
43 timevar_push (TV_LOOP_INIT
);
46 struct loops
*loops
= ggc_alloc_cleared_loops ();
48 gcc_assert (!(cfun
->curr_properties
& PROP_loops
));
52 flow_loops_find (loops
);
53 current_loops
= loops
;
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 ();
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
73 gcc_assert ((flags
& ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
74 | LOOPS_HAVE_RECORDED_EXITS
)) == 0);
75 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
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 ();
103 flow_loops_dump (dump_file
, NULL
, 1);
105 #ifdef ENABLE_CHECKING
106 verify_loop_structure ();
109 timevar_pop (TV_LOOP_INIT
);
112 /* Finalize loop structures. */
115 loop_optimizer_finalize (void)
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
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 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
140 gcc_assert (current_loops
!= NULL
);
142 FOR_EACH_LOOP (li
, loop
, 0)
144 free_simple_loop_desc (loop
);
148 flow_loops_free (current_loops
);
149 ggc_free (current_loops
);
150 current_loops
= NULL
;
154 bb
->loop_father
= NULL
;
158 timevar_pop (TV_LOOP_FINI
);
162 /* Gate for the RTL loop superpass. The actual passes are subpasses.
163 See passes.c for more on that. */
166 gate_handle_loop2 (void)
169 && (flag_move_loop_invariants
170 || flag_unswitch_loops
173 #ifdef HAVE_doloop_end
174 || (flag_branch_on_count_reg
&& HAVE_doloop_end
)
180 /* No longer preserve loops, remove them now. */
181 cfun
->curr_properties
&= ~PROP_loops
;
183 loop_optimizer_finalize ();
188 struct rtl_opt_pass pass_loop2
=
193 OPTGROUP_LOOP
, /* optinfo_flags */
194 gate_handle_loop2
, /* gate */
198 0, /* static_pass_number */
200 0, /* properties_required */
201 0, /* properties_provided */
202 0, /* properties_destroyed */
203 0, /* todo_flags_start */
204 TODO_ggc_collect
/* todo_flags_finish */
209 /* Initialization of the RTL loop passes. */
213 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT
);
217 dump_reg_info (dump_file
);
218 dump_flow_info (dump_file
, dump_flags
);
221 loop_optimizer_init (LOOPS_NORMAL
);
225 struct rtl_opt_pass pass_rtl_loop_init
=
229 "loop2_init", /* name */
230 OPTGROUP_LOOP
, /* optinfo_flags */
232 rtl_loop_init
, /* execute */
235 0, /* static_pass_number */
237 0, /* properties_required */
238 0, /* properties_provided */
239 0, /* properties_destroyed */
240 0, /* todo_flags_start */
241 TODO_verify_rtl_sharing
/* todo_flags_finish */
246 /* Finalization of the RTL loop passes. */
251 /* No longer preserve loops, remove them now. */
252 cfun
->curr_properties
&= ~PROP_loops
;
253 loop_optimizer_finalize ();
254 free_dominance_info (CDI_DOMINATORS
);
259 dump_reg_info (dump_file
);
260 dump_flow_info (dump_file
, dump_flags
);
266 struct rtl_opt_pass pass_rtl_loop_done
=
270 "loop2_done", /* name */
271 OPTGROUP_LOOP
, /* optinfo_flags */
273 rtl_loop_done
, /* execute */
276 0, /* static_pass_number */
278 0, /* properties_required */
279 0, /* properties_provided */
280 PROP_loops
, /* properties_destroyed */
281 0, /* todo_flags_start */
283 | TODO_verify_rtl_sharing
/* todo_flags_finish */
288 /* Loop invariant code motion. */
290 gate_rtl_move_loop_invariants (void)
292 return flag_move_loop_invariants
;
296 rtl_move_loop_invariants (void)
298 if (number_of_loops () > 1)
299 move_loop_invariants ();
303 struct rtl_opt_pass pass_rtl_move_loop_invariants
=
307 "loop2_invariant", /* name */
308 OPTGROUP_LOOP
, /* optinfo_flags */
309 gate_rtl_move_loop_invariants
, /* gate */
310 rtl_move_loop_invariants
, /* execute */
313 0, /* static_pass_number */
314 TV_LOOP_MOVE_INVARIANTS
, /* tv_id */
315 0, /* properties_required */
316 0, /* properties_provided */
317 0, /* properties_destroyed */
318 0, /* todo_flags_start */
320 TODO_df_finish
| TODO_verify_rtl_sharing
/* todo_flags_finish */
325 /* Loop unswitching for RTL. */
327 gate_rtl_unswitch (void)
329 return flag_unswitch_loops
;
335 if (number_of_loops () > 1)
340 struct rtl_opt_pass pass_rtl_unswitch
=
344 "loop2_unswitch", /* name */
345 OPTGROUP_LOOP
, /* optinfo_flags */
346 gate_rtl_unswitch
, /* gate */
347 rtl_unswitch
, /* execute */
350 0, /* static_pass_number */
351 TV_LOOP_UNSWITCH
, /* tv_id */
352 0, /* properties_required */
353 0, /* properties_provided */
354 0, /* properties_destroyed */
355 0, /* todo_flags_start */
356 TODO_verify_rtl_sharing
, /* todo_flags_finish */
361 /* Loop unswitching for RTL. */
363 gate_rtl_unroll_and_peel_loops (void)
365 return (flag_peel_loops
|| flag_unroll_loops
|| flag_unroll_all_loops
);
369 rtl_unroll_and_peel_loops (void)
371 if (number_of_loops () > 1)
379 if (flag_unroll_loops
)
381 if (flag_unroll_all_loops
)
382 flags
|= UAP_UNROLL_ALL
;
384 unroll_and_peel_loops (flags
);
389 struct rtl_opt_pass pass_rtl_unroll_and_peel_loops
=
393 "loop2_unroll", /* name */
394 OPTGROUP_LOOP
, /* optinfo_flags */
395 gate_rtl_unroll_and_peel_loops
, /* gate */
396 rtl_unroll_and_peel_loops
, /* execute */
399 0, /* static_pass_number */
400 TV_LOOP_UNROLL
, /* tv_id */
401 0, /* properties_required */
402 0, /* properties_provided */
403 0, /* properties_destroyed */
404 0, /* todo_flags_start */
405 TODO_verify_rtl_sharing
, /* todo_flags_finish */
410 /* The doloop optimization. */
412 gate_rtl_doloop (void)
414 #ifdef HAVE_doloop_end
415 return (flag_branch_on_count_reg
&& HAVE_doloop_end
);
424 #ifdef HAVE_doloop_end
425 if (number_of_loops () > 1)
426 doloop_optimize_loops ();
431 struct rtl_opt_pass pass_rtl_doloop
=
435 "loop2_doloop", /* name */
436 OPTGROUP_LOOP
, /* optinfo_flags */
437 gate_rtl_doloop
, /* gate */
438 rtl_doloop
, /* execute */
441 0, /* static_pass_number */
442 TV_LOOP_DOLOOP
, /* tv_id */
443 0, /* properties_required */
444 0, /* properties_provided */
445 0, /* properties_destroyed */
446 0, /* todo_flags_start */
447 TODO_verify_rtl_sharing
/* todo_flags_finish */