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"
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
42 loop_optimizer_init (unsigned flags
)
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 ();
110 /* Finalize loop structures. */
113 loop_optimizer_finalize (void)
119 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
120 release_recorded_exits ();
122 /* If we should preserve loop structure, do not free it but clear
123 flags that advanced properties are there as we are not preserving
125 if (cfun
->curr_properties
& PROP_loops
)
127 loops_state_clear (LOOP_CLOSED_SSA
128 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
129 | LOOPS_HAVE_PREHEADERS
130 | LOOPS_HAVE_SIMPLE_LATCHES
131 | LOOPS_HAVE_FALLTHRU_PREHEADERS
);
135 gcc_assert (current_loops
!= NULL
);
137 FOR_EACH_LOOP (li
, loop
, 0)
139 free_simple_loop_desc (loop
);
143 flow_loops_free (current_loops
);
144 ggc_free (current_loops
);
145 current_loops
= NULL
;
149 bb
->loop_father
= NULL
;
154 /* Gate for the RTL loop superpass. The actual passes are subpasses.
155 See passes.c for more on that. */
158 gate_handle_loop2 (void)
161 && (flag_move_loop_invariants
162 || flag_unswitch_loops
165 #ifdef HAVE_doloop_end
166 || (flag_branch_on_count_reg
&& HAVE_doloop_end
)
172 /* No longer preserve loops, remove them now. */
173 cfun
->curr_properties
&= ~PROP_loops
;
175 loop_optimizer_finalize ();
180 struct rtl_opt_pass pass_loop2
=
185 gate_handle_loop2
, /* gate */
189 0, /* static_pass_number */
191 0, /* properties_required */
192 0, /* properties_provided */
193 0, /* properties_destroyed */
194 0, /* todo_flags_start */
195 TODO_ggc_collect
/* todo_flags_finish */
200 /* Initialization of the RTL loop passes. */
204 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT
);
208 dump_reg_info (dump_file
);
209 dump_flow_info (dump_file
, dump_flags
);
212 loop_optimizer_init (LOOPS_NORMAL
);
216 struct rtl_opt_pass pass_rtl_loop_init
=
220 "loop2_init", /* name */
222 rtl_loop_init
, /* execute */
225 0, /* static_pass_number */
227 0, /* properties_required */
228 0, /* properties_provided */
229 0, /* properties_destroyed */
230 0, /* todo_flags_start */
231 TODO_verify_rtl_sharing
/* todo_flags_finish */
236 /* Finalization of the RTL loop passes. */
241 /* No longer preserve loops, remove them now. */
242 cfun
->curr_properties
&= ~PROP_loops
;
243 loop_optimizer_finalize ();
244 free_dominance_info (CDI_DOMINATORS
);
249 dump_reg_info (dump_file
);
250 dump_flow_info (dump_file
, dump_flags
);
256 struct rtl_opt_pass pass_rtl_loop_done
=
260 "loop2_done", /* name */
262 rtl_loop_done
, /* execute */
265 0, /* static_pass_number */
267 0, /* properties_required */
268 0, /* properties_provided */
269 PROP_loops
, /* properties_destroyed */
270 0, /* todo_flags_start */
272 | TODO_verify_rtl_sharing
/* todo_flags_finish */
277 /* Loop invariant code motion. */
279 gate_rtl_move_loop_invariants (void)
281 return flag_move_loop_invariants
;
285 rtl_move_loop_invariants (void)
287 if (number_of_loops () > 1)
288 move_loop_invariants ();
292 struct rtl_opt_pass pass_rtl_move_loop_invariants
=
296 "loop2_invariant", /* name */
297 gate_rtl_move_loop_invariants
, /* gate */
298 rtl_move_loop_invariants
, /* execute */
301 0, /* static_pass_number */
302 TV_LOOP_MOVE_INVARIANTS
, /* tv_id */
303 0, /* properties_required */
304 0, /* properties_provided */
305 0, /* properties_destroyed */
306 0, /* todo_flags_start */
308 TODO_df_finish
| TODO_verify_rtl_sharing
/* todo_flags_finish */
313 /* Loop unswitching for RTL. */
315 gate_rtl_unswitch (void)
317 return flag_unswitch_loops
;
323 if (number_of_loops () > 1)
328 struct rtl_opt_pass pass_rtl_unswitch
=
332 "loop2_unswitch", /* name */
333 gate_rtl_unswitch
, /* gate */
334 rtl_unswitch
, /* execute */
337 0, /* static_pass_number */
338 TV_LOOP_UNSWITCH
, /* tv_id */
339 0, /* properties_required */
340 0, /* properties_provided */
341 0, /* properties_destroyed */
342 0, /* todo_flags_start */
343 TODO_verify_rtl_sharing
, /* todo_flags_finish */
348 /* Loop unswitching for RTL. */
350 gate_rtl_unroll_and_peel_loops (void)
352 return (flag_peel_loops
|| flag_unroll_loops
|| flag_unroll_all_loops
);
356 rtl_unroll_and_peel_loops (void)
358 if (number_of_loops () > 1)
366 if (flag_unroll_loops
)
368 if (flag_unroll_all_loops
)
369 flags
|= UAP_UNROLL_ALL
;
371 unroll_and_peel_loops (flags
);
376 struct rtl_opt_pass pass_rtl_unroll_and_peel_loops
=
380 "loop2_unroll", /* name */
381 gate_rtl_unroll_and_peel_loops
, /* gate */
382 rtl_unroll_and_peel_loops
, /* execute */
385 0, /* static_pass_number */
386 TV_LOOP_UNROLL
, /* tv_id */
387 0, /* properties_required */
388 0, /* properties_provided */
389 0, /* properties_destroyed */
390 0, /* todo_flags_start */
391 TODO_verify_rtl_sharing
, /* todo_flags_finish */
396 /* The doloop optimization. */
398 gate_rtl_doloop (void)
400 #ifdef HAVE_doloop_end
401 return (flag_branch_on_count_reg
&& HAVE_doloop_end
);
410 #ifdef HAVE_doloop_end
411 if (number_of_loops () > 1)
412 doloop_optimize_loops ();
417 struct rtl_opt_pass pass_rtl_doloop
=
421 "loop2_doloop", /* name */
422 gate_rtl_doloop
, /* gate */
423 rtl_doloop
, /* execute */
426 0, /* static_pass_number */
427 TV_LOOP_DOLOOP
, /* tv_id */
428 0, /* properties_required */
429 0, /* properties_provided */
430 0, /* properties_destroyed */
431 0, /* todo_flags_start */
432 TODO_verify_rtl_sharing
/* todo_flags_finish */