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
)
45 struct loops
*loops
= ggc_alloc_cleared_loops ();
47 gcc_assert (!(cfun
->curr_properties
& PROP_loops
));
51 flow_loops_find (loops
);
52 current_loops
= loops
;
56 gcc_assert (cfun
->curr_properties
& PROP_loops
);
58 /* Ensure that the dominators are computed, like flow_loops_find does. */
59 calculate_dominance_info (CDI_DOMINATORS
);
61 #ifdef ENABLE_CHECKING
62 verify_loop_structure ();
66 if (flags
& LOOPS_MAY_HAVE_MULTIPLE_LATCHES
)
68 /* If the loops may have multiple latches, we cannot canonicalize
69 them further (and most of the loop manipulation functions will
70 not work). However, we avoid modifying cfg, which some
72 gcc_assert ((flags
& ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
73 | LOOPS_HAVE_RECORDED_EXITS
)) == 0);
74 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
77 disambiguate_loops_with_multiple_latches ();
79 /* Create pre-headers. */
80 if (flags
& LOOPS_HAVE_PREHEADERS
)
82 int cp_flags
= CP_SIMPLE_PREHEADERS
;
84 if (flags
& LOOPS_HAVE_FALLTHRU_PREHEADERS
)
85 cp_flags
|= CP_FALLTHRU_PREHEADERS
;
87 create_preheaders (cp_flags
);
90 /* Force all latches to have only single successor. */
91 if (flags
& LOOPS_HAVE_SIMPLE_LATCHES
)
92 force_single_succ_latches ();
94 /* Mark irreducible loops. */
95 if (flags
& LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
96 mark_irreducible_loops ();
98 if (flags
& LOOPS_HAVE_RECORDED_EXITS
)
102 flow_loops_dump (dump_file
, NULL
, 1);
104 #ifdef ENABLE_CHECKING
105 verify_loop_structure ();
109 /* Finalize loop structures. */
112 loop_optimizer_finalize (void)
118 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
119 release_recorded_exits ();
121 /* If we should preserve loop structure, do not free it but clear
122 flags that advanced properties are there as we are not preserving
124 if (cfun
->curr_properties
& PROP_loops
)
126 loops_state_clear (LOOP_CLOSED_SSA
127 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
128 | LOOPS_HAVE_PREHEADERS
129 | LOOPS_HAVE_SIMPLE_LATCHES
130 | LOOPS_HAVE_FALLTHRU_PREHEADERS
);
134 gcc_assert (current_loops
!= NULL
);
136 FOR_EACH_LOOP (li
, loop
, 0)
138 free_simple_loop_desc (loop
);
142 flow_loops_free (current_loops
);
143 ggc_free (current_loops
);
144 current_loops
= NULL
;
148 bb
->loop_father
= NULL
;
153 /* Gate for the RTL loop superpass. The actual passes are subpasses.
154 See passes.c for more on that. */
157 gate_handle_loop2 (void)
160 && (flag_move_loop_invariants
161 || flag_unswitch_loops
164 #ifdef HAVE_doloop_end
165 || (flag_branch_on_count_reg
&& HAVE_doloop_end
)
171 /* No longer preserve loops, remove them now. */
172 cfun
->curr_properties
&= ~PROP_loops
;
174 loop_optimizer_finalize ();
179 struct rtl_opt_pass pass_loop2
=
184 gate_handle_loop2
, /* gate */
188 0, /* static_pass_number */
190 0, /* properties_required */
191 0, /* properties_provided */
192 0, /* properties_destroyed */
193 0, /* todo_flags_start */
194 TODO_ggc_collect
/* todo_flags_finish */
199 /* Initialization of the RTL loop passes. */
203 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT
);
207 dump_reg_info (dump_file
);
208 dump_flow_info (dump_file
, dump_flags
);
211 loop_optimizer_init (LOOPS_NORMAL
);
215 struct rtl_opt_pass pass_rtl_loop_init
=
219 "loop2_init", /* name */
221 rtl_loop_init
, /* execute */
224 0, /* static_pass_number */
226 0, /* properties_required */
227 0, /* properties_provided */
228 0, /* properties_destroyed */
229 0, /* todo_flags_start */
230 TODO_verify_rtl_sharing
/* todo_flags_finish */
235 /* Finalization of the RTL loop passes. */
240 /* No longer preserve loops, remove them now. */
241 cfun
->curr_properties
&= ~PROP_loops
;
242 loop_optimizer_finalize ();
243 free_dominance_info (CDI_DOMINATORS
);
248 dump_reg_info (dump_file
);
249 dump_flow_info (dump_file
, dump_flags
);
255 struct rtl_opt_pass pass_rtl_loop_done
=
259 "loop2_done", /* name */
261 rtl_loop_done
, /* execute */
264 0, /* static_pass_number */
266 0, /* properties_required */
267 0, /* properties_provided */
268 PROP_loops
, /* properties_destroyed */
269 0, /* todo_flags_start */
271 | TODO_verify_rtl_sharing
/* todo_flags_finish */
276 /* Loop invariant code motion. */
278 gate_rtl_move_loop_invariants (void)
280 return flag_move_loop_invariants
;
284 rtl_move_loop_invariants (void)
286 if (number_of_loops () > 1)
287 move_loop_invariants ();
291 struct rtl_opt_pass pass_rtl_move_loop_invariants
=
295 "loop2_invariant", /* name */
296 gate_rtl_move_loop_invariants
, /* gate */
297 rtl_move_loop_invariants
, /* execute */
300 0, /* static_pass_number */
301 TV_LOOP_MOVE_INVARIANTS
, /* tv_id */
302 0, /* properties_required */
303 0, /* properties_provided */
304 0, /* properties_destroyed */
305 0, /* todo_flags_start */
307 TODO_df_finish
| TODO_verify_rtl_sharing
/* todo_flags_finish */
312 /* Loop unswitching for RTL. */
314 gate_rtl_unswitch (void)
316 return flag_unswitch_loops
;
322 if (number_of_loops () > 1)
327 struct rtl_opt_pass pass_rtl_unswitch
=
331 "loop2_unswitch", /* name */
332 gate_rtl_unswitch
, /* gate */
333 rtl_unswitch
, /* execute */
336 0, /* static_pass_number */
337 TV_LOOP_UNSWITCH
, /* tv_id */
338 0, /* properties_required */
339 0, /* properties_provided */
340 0, /* properties_destroyed */
341 0, /* todo_flags_start */
342 TODO_verify_rtl_sharing
, /* todo_flags_finish */
347 /* Loop unswitching for RTL. */
349 gate_rtl_unroll_and_peel_loops (void)
351 return (flag_peel_loops
|| flag_unroll_loops
|| flag_unroll_all_loops
);
355 rtl_unroll_and_peel_loops (void)
357 if (number_of_loops () > 1)
365 if (flag_unroll_loops
)
367 if (flag_unroll_all_loops
)
368 flags
|= UAP_UNROLL_ALL
;
370 unroll_and_peel_loops (flags
);
375 struct rtl_opt_pass pass_rtl_unroll_and_peel_loops
=
379 "loop2_unroll", /* name */
380 gate_rtl_unroll_and_peel_loops
, /* gate */
381 rtl_unroll_and_peel_loops
, /* execute */
384 0, /* static_pass_number */
385 TV_LOOP_UNROLL
, /* tv_id */
386 0, /* properties_required */
387 0, /* properties_provided */
388 0, /* properties_destroyed */
389 0, /* todo_flags_start */
390 TODO_verify_rtl_sharing
, /* todo_flags_finish */
395 /* The doloop optimization. */
397 gate_rtl_doloop (void)
399 #ifdef HAVE_doloop_end
400 return (flag_branch_on_count_reg
&& HAVE_doloop_end
);
409 #ifdef HAVE_doloop_end
410 if (number_of_loops () > 1)
411 doloop_optimize_loops ();
416 struct rtl_opt_pass pass_rtl_doloop
=
420 "loop2_doloop", /* name */
421 gate_rtl_doloop
, /* gate */
422 rtl_doloop
, /* execute */
425 0, /* static_pass_number */
426 TV_LOOP_DOLOOP
, /* tv_id */
427 0, /* properties_required */
428 0, /* properties_provided */
429 0, /* properties_destroyed */
430 0, /* todo_flags_start */
431 TODO_verify_rtl_sharing
/* todo_flags_finish */