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
);
139 gcc_assert (current_loops
!= NULL
);
141 FOR_EACH_LOOP (li
, loop
, 0)
143 free_simple_loop_desc (loop
);
147 flow_loops_free (current_loops
);
148 ggc_free (current_loops
);
149 current_loops
= NULL
;
153 bb
->loop_father
= NULL
;
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. */
165 gate_handle_loop2 (void)
168 && (flag_move_loop_invariants
169 || flag_unswitch_loops
172 #ifdef HAVE_doloop_end
173 || (flag_branch_on_count_reg
&& HAVE_doloop_end
)
179 /* No longer preserve loops, remove them now. */
180 cfun
->curr_properties
&= ~PROP_loops
;
182 loop_optimizer_finalize ();
187 struct rtl_opt_pass pass_loop2
=
192 OPTGROUP_LOOP
, /* optinfo_flags */
193 gate_handle_loop2
, /* gate */
197 0, /* static_pass_number */
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. */
212 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT
);
216 dump_reg_info (dump_file
);
217 dump_flow_info (dump_file
, dump_flags
);
220 loop_optimizer_init (LOOPS_NORMAL
);
224 struct rtl_opt_pass pass_rtl_loop_init
=
228 "loop2_init", /* name */
229 OPTGROUP_LOOP
, /* optinfo_flags */
231 rtl_loop_init
, /* execute */
234 0, /* static_pass_number */
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. */
250 /* No longer preserve loops, remove them now. */
251 cfun
->curr_properties
&= ~PROP_loops
;
252 loop_optimizer_finalize ();
253 free_dominance_info (CDI_DOMINATORS
);
258 dump_reg_info (dump_file
);
259 dump_flow_info (dump_file
, dump_flags
);
265 struct rtl_opt_pass pass_rtl_loop_done
=
269 "loop2_done", /* name */
270 OPTGROUP_LOOP
, /* optinfo_flags */
272 rtl_loop_done
, /* execute */
275 0, /* static_pass_number */
277 0, /* properties_required */
278 0, /* properties_provided */
279 PROP_loops
, /* properties_destroyed */
280 0, /* todo_flags_start */
282 | TODO_verify_rtl_sharing
/* todo_flags_finish */
287 /* Loop invariant code motion. */
289 gate_rtl_move_loop_invariants (void)
291 return flag_move_loop_invariants
;
295 rtl_move_loop_invariants (void)
297 if (number_of_loops () > 1)
298 move_loop_invariants ();
302 struct rtl_opt_pass pass_rtl_move_loop_invariants
=
306 "loop2_invariant", /* name */
307 OPTGROUP_LOOP
, /* optinfo_flags */
308 gate_rtl_move_loop_invariants
, /* gate */
309 rtl_move_loop_invariants
, /* execute */
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 */
319 TODO_df_finish
| TODO_verify_rtl_sharing
/* todo_flags_finish */
324 /* Loop unswitching for RTL. */
326 gate_rtl_unswitch (void)
328 return flag_unswitch_loops
;
334 if (number_of_loops () > 1)
339 struct rtl_opt_pass pass_rtl_unswitch
=
343 "loop2_unswitch", /* name */
344 OPTGROUP_LOOP
, /* optinfo_flags */
345 gate_rtl_unswitch
, /* gate */
346 rtl_unswitch
, /* execute */
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. */
362 gate_rtl_unroll_and_peel_loops (void)
364 return (flag_peel_loops
|| flag_unroll_loops
|| flag_unroll_all_loops
);
368 rtl_unroll_and_peel_loops (void)
370 if (number_of_loops () > 1)
378 if (flag_unroll_loops
)
380 if (flag_unroll_all_loops
)
381 flags
|= UAP_UNROLL_ALL
;
383 unroll_and_peel_loops (flags
);
388 struct rtl_opt_pass pass_rtl_unroll_and_peel_loops
=
392 "loop2_unroll", /* name */
393 OPTGROUP_LOOP
, /* optinfo_flags */
394 gate_rtl_unroll_and_peel_loops
, /* gate */
395 rtl_unroll_and_peel_loops
, /* execute */
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. */
411 gate_rtl_doloop (void)
413 #ifdef HAVE_doloop_end
414 return (flag_branch_on_count_reg
&& HAVE_doloop_end
);
423 #ifdef HAVE_doloop_end
424 if (number_of_loops () > 1)
425 doloop_optimize_loops ();
430 struct rtl_opt_pass pass_rtl_doloop
=
434 "loop2_doloop", /* name */
435 OPTGROUP_LOOP
, /* optinfo_flags */
436 gate_rtl_doloop
, /* gate */
437 rtl_doloop
, /* execute */
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 */