1 /* Loop optimizer initialization routines and RTL loop optimization passes.
2 Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 #include "coretypes.h"
26 #include "hard-reg-set.h"
28 #include "basic-block.h"
30 #include "cfglayout.h"
31 #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 static bool first_time
= true;
54 gcc_assert (!current_loops
);
55 loops
= XCNEW (struct loops
);
57 /* Avoid annoying special cases of edges going to exit
60 for (ei
= ei_start (EXIT_BLOCK_PTR
->preds
); (e
= ei_safe_edge (ei
)); )
61 if ((e
->flags
& EDGE_FALLTHRU
) && !single_succ_p (e
->src
))
68 flow_loops_find (loops
);
69 current_loops
= loops
;
71 if (current_loops
->num
<= 1)
74 loop_optimizer_finalize ();
78 /* Create pre-headers. */
79 if (flags
& LOOPS_HAVE_PREHEADERS
)
80 create_preheaders (current_loops
, CP_SIMPLE_PREHEADERS
);
82 /* Force all latches to have only single successor. */
83 if (flags
& LOOPS_HAVE_SIMPLE_LATCHES
)
84 force_single_succ_latches (current_loops
);
86 /* Mark irreducible loops. */
87 if (flags
& LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
88 mark_irreducible_loops (current_loops
);
90 if (flags
& LOOPS_HAVE_MARKED_SINGLE_EXITS
)
91 mark_single_exit_loops (current_loops
);
94 flow_loops_dump (current_loops
, dump_file
, NULL
, 1);
96 #ifdef ENABLE_CHECKING
97 verify_dominators (CDI_DOMINATORS
);
98 verify_loop_structure (current_loops
);
102 /* Finalize loop structures. */
105 loop_optimizer_finalize (void)
113 for (i
= 1; i
< current_loops
->num
; i
++)
114 if (current_loops
->parray
[i
])
115 free_simple_loop_desc (current_loops
->parray
[i
]);
118 flow_loops_free (current_loops
);
119 free (current_loops
);
120 current_loops
= NULL
;
124 bb
->loop_father
= NULL
;
128 #ifdef ENABLE_CHECKING
134 /* Gate for the RTL loop superpass. The actual passes are subpasses.
135 See passes.c for more on that. */
138 gate_handle_loop2 (void)
141 && (flag_move_loop_invariants
142 || flag_unswitch_loops
145 #ifdef HAVE_doloop_end
146 || (flag_branch_on_count_reg
&& HAVE_doloop_end
)
151 struct tree_opt_pass pass_loop2
=
154 gate_handle_loop2
, /* gate */
158 0, /* static_pass_number */
160 0, /* properties_required */
161 0, /* properties_provided */
162 0, /* properties_destroyed */
163 0, /* todo_flags_start */
165 TODO_ggc_collect
, /* todo_flags_finish */
170 /* Initialization of the RTL loop passes. */
175 dump_flow_info (dump_file
, dump_flags
);
177 /* Initialize structures for layout changes. */
178 cfg_layout_initialize (0);
180 loop_optimizer_init (LOOPS_NORMAL
);
184 struct tree_opt_pass pass_rtl_loop_init
=
186 "loop2_init", /* name */
188 rtl_loop_init
, /* execute */
191 0, /* static_pass_number */
193 0, /* properties_required */
194 0, /* properties_provided */
195 0, /* properties_destroyed */
196 0, /* todo_flags_start */
197 TODO_dump_func
, /* todo_flags_finish */
202 /* Finalization of the RTL loop passes. */
209 loop_optimizer_finalize ();
210 free_dominance_info (CDI_DOMINATORS
);
212 /* Finalize layout changes. */
214 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
215 bb
->aux
= bb
->next_bb
;
216 cfg_layout_finalize ();
218 cleanup_cfg (CLEANUP_EXPENSIVE
);
219 delete_trivially_dead_insns (get_insns (), max_reg_num ());
220 reg_scan (get_insns (), max_reg_num ());
222 dump_flow_info (dump_file
, dump_flags
);
227 struct tree_opt_pass pass_rtl_loop_done
=
229 "loop2_done", /* name */
231 rtl_loop_done
, /* 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_dump_func
, /* todo_flags_finish */
245 /* Loop invariant code motion. */
247 gate_rtl_move_loop_invariants (void)
249 return flag_move_loop_invariants
;
253 rtl_move_loop_invariants (void)
256 move_loop_invariants (current_loops
);
260 struct tree_opt_pass pass_rtl_move_loop_invariants
=
262 "loop2_invariant", /* name */
263 gate_rtl_move_loop_invariants
, /* gate */
264 rtl_move_loop_invariants
, /* execute */
267 0, /* static_pass_number */
269 0, /* properties_required */
270 0, /* properties_provided */
271 0, /* properties_destroyed */
272 0, /* todo_flags_start */
273 TODO_dump_func
, /* todo_flags_finish */
278 /* Loop unswitching for RTL. */
280 gate_rtl_unswitch (void)
282 return flag_unswitch_loops
;
289 unswitch_loops (current_loops
);
293 struct tree_opt_pass pass_rtl_unswitch
=
295 "loop2_unswitch", /* name */
296 gate_rtl_unswitch
, /* gate */
297 rtl_unswitch
, /* execute */
300 0, /* static_pass_number */
302 0, /* properties_required */
303 0, /* properties_provided */
304 0, /* properties_destroyed */
305 0, /* todo_flags_start */
306 TODO_dump_func
, /* todo_flags_finish */
311 /* Loop unswitching for RTL. */
313 gate_rtl_unroll_and_peel_loops (void)
315 return (flag_peel_loops
|| flag_unroll_loops
|| flag_unroll_all_loops
);
319 rtl_unroll_and_peel_loops (void)
327 if (flag_unroll_loops
)
329 if (flag_unroll_all_loops
)
330 flags
|= UAP_UNROLL_ALL
;
332 unroll_and_peel_loops (current_loops
, flags
);
337 struct tree_opt_pass pass_rtl_unroll_and_peel_loops
=
339 "loop2_unroll", /* name */
340 gate_rtl_unroll_and_peel_loops
, /* gate */
341 rtl_unroll_and_peel_loops
, /* execute */
344 0, /* static_pass_number */
346 0, /* properties_required */
347 0, /* properties_provided */
348 0, /* properties_destroyed */
349 0, /* todo_flags_start */
350 TODO_dump_func
, /* todo_flags_finish */
355 /* The doloop optimization. */
357 gate_rtl_doloop (void)
359 #ifdef HAVE_doloop_end
360 return (flag_branch_on_count_reg
&& HAVE_doloop_end
);
369 #ifdef HAVE_doloop_end
371 doloop_optimize_loops (current_loops
);
376 struct tree_opt_pass pass_rtl_doloop
=
378 "loop2_doloop", /* name */
379 gate_rtl_doloop
, /* gate */
380 rtl_doloop
, /* execute */
383 0, /* static_pass_number */
385 0, /* properties_required */
386 0, /* properties_provided */
387 0, /* properties_destroyed */
388 0, /* todo_flags_start */
389 TODO_dump_func
, /* todo_flags_finish */