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 optimizer. 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 struct loops *loops = XCNEW (struct loops);
46 static bool first_time = true;
54 /* Avoid annoying special cases of edges going to exit
57 for (ei = ei_start (EXIT_BLOCK_PTR->preds); (e = ei_safe_edge (ei)); )
58 if ((e->flags & EDGE_FALLTHRU) && !single_succ_p (e->src))
65 if (flow_loops_find (loops) <= 1)
68 flow_loops_free (loops);
74 /* Not going to update these. */
75 free (loops->cfg.rc_order);
76 loops->cfg.rc_order = NULL;
77 free (loops->cfg.dfs_order);
78 loops->cfg.dfs_order = NULL;
80 /* Create pre-headers. */
81 if (flags & LOOPS_HAVE_PREHEADERS)
82 create_preheaders (loops, CP_SIMPLE_PREHEADERS);
84 /* Force all latches to have only single successor. */
85 if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
86 force_single_succ_latches (loops);
88 /* Mark irreducible loops. */
89 if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
90 mark_irreducible_loops (loops);
92 if (flags & LOOPS_HAVE_MARKED_SINGLE_EXITS)
93 mark_single_exit_loops (loops);
96 flow_loops_dump (loops, dump_file, NULL, 1);
98 #ifdef ENABLE_CHECKING
99 verify_dominators (CDI_DOMINATORS);
100 verify_loop_structure (loops);
106 /* Finalize loop optimizer. */
108 loop_optimizer_finalize (struct loops *loops)
115 for (i = 1; i < loops->num; i++)
116 if (loops->parray[i])
117 free_simple_loop_desc (loops->parray[i]);
120 flow_loops_free (loops);
124 #ifdef ENABLE_CHECKING
130 /* Gate for the RTL loop superpass. The actual passes are subpasses.
131 See passes.c for more on that. */
134 gate_handle_loop2 (void)
137 && (flag_move_loop_invariants
138 || flag_unswitch_loops
141 #ifdef HAVE_doloop_end
142 || (flag_branch_on_count_reg && HAVE_doloop_end)
147 struct tree_opt_pass pass_loop2 =
150 gate_handle_loop2, /* gate */
154 0, /* static_pass_number */
156 0, /* properties_required */
157 0, /* properties_provided */
158 0, /* properties_destroyed */
159 0, /* todo_flags_start */
161 TODO_ggc_collect, /* todo_flags_finish */
166 /* Initialization of the RTL loop passes. */
171 dump_flow_info (dump_file, dump_flags);
173 /* Initialize structures for layout changes. */
174 cfg_layout_initialize (0);
176 current_loops = loop_optimizer_init (LOOPS_NORMAL);
179 struct tree_opt_pass pass_rtl_loop_init =
181 "loop2_init", /* name */
183 rtl_loop_init, /* execute */
186 0, /* static_pass_number */
188 0, /* properties_required */
189 0, /* properties_provided */
190 0, /* properties_destroyed */
191 0, /* todo_flags_start */
192 TODO_dump_func, /* todo_flags_finish */
197 /* Finalization of the RTL loop passes. */
204 loop_optimizer_finalize (current_loops);
206 free_dominance_info (CDI_DOMINATORS);
208 /* Finalize layout changes. */
210 if (bb->next_bb != EXIT_BLOCK_PTR)
211 bb->aux = bb->next_bb;
212 cfg_layout_finalize ();
214 cleanup_cfg (CLEANUP_EXPENSIVE);
215 delete_trivially_dead_insns (get_insns (), max_reg_num ());
216 reg_scan (get_insns (), max_reg_num ());
218 dump_flow_info (dump_file, dump_flags);
220 current_loops = NULL;
223 struct tree_opt_pass pass_rtl_loop_done =
225 "loop2_done", /* name */
227 rtl_loop_done, /* execute */
230 0, /* static_pass_number */
232 0, /* properties_required */
233 0, /* properties_provided */
234 0, /* properties_destroyed */
235 0, /* todo_flags_start */
236 TODO_dump_func, /* todo_flags_finish */
241 /* Loop invariant code motion. */
243 gate_rtl_move_loop_invariants (void)
245 return flag_move_loop_invariants;
249 rtl_move_loop_invariants (void)
252 move_loop_invariants (current_loops);
255 struct tree_opt_pass pass_rtl_move_loop_invariants =
257 "loop2_invariant", /* name */
258 gate_rtl_move_loop_invariants, /* gate */
259 rtl_move_loop_invariants, /* execute */
262 0, /* static_pass_number */
264 0, /* properties_required */
265 0, /* properties_provided */
266 0, /* properties_destroyed */
267 0, /* todo_flags_start */
268 TODO_dump_func, /* todo_flags_finish */
273 /* Loop unswitching for RTL. */
275 gate_rtl_unswitch (void)
277 return flag_unswitch_loops;
284 unswitch_loops (current_loops);
287 struct tree_opt_pass pass_rtl_unswitch =
289 "loop2_unswitch", /* name */
290 gate_rtl_unswitch, /* gate */
291 rtl_unswitch, /* execute */
294 0, /* static_pass_number */
296 0, /* properties_required */
297 0, /* properties_provided */
298 0, /* properties_destroyed */
299 0, /* todo_flags_start */
300 TODO_dump_func, /* todo_flags_finish */
305 /* Loop unswitching for RTL. */
307 gate_rtl_unroll_and_peel_loops (void)
309 return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
313 rtl_unroll_and_peel_loops (void)
321 if (flag_unroll_loops)
323 if (flag_unroll_all_loops)
324 flags |= UAP_UNROLL_ALL;
326 unroll_and_peel_loops (current_loops, flags);
330 struct tree_opt_pass pass_rtl_unroll_and_peel_loops =
332 "loop2_unroll", /* name */
333 gate_rtl_unroll_and_peel_loops, /* gate */
334 rtl_unroll_and_peel_loops, /* execute */
337 0, /* static_pass_number */
339 0, /* properties_required */
340 0, /* properties_provided */
341 0, /* properties_destroyed */
342 0, /* todo_flags_start */
343 TODO_dump_func, /* todo_flags_finish */
348 /* The doloop optimization. */
350 gate_rtl_doloop (void)
352 #ifdef HAVE_doloop_end
353 return (flag_branch_on_count_reg && HAVE_doloop_end);
362 #ifdef HAVE_doloop_end
364 doloop_optimize_loops (current_loops);
368 struct tree_opt_pass pass_rtl_doloop =
370 "loop2_doloop", /* name */
371 gate_rtl_doloop, /* gate */
372 rtl_doloop, /* execute */
375 0, /* static_pass_number */
377 0, /* properties_required */
378 0, /* properties_provided */
379 0, /* properties_destroyed */
380 0, /* todo_flags_start */
381 TODO_dump_func, /* todo_flags_finish */