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)
136 return (optimize
> 0 && flag_loop_optimize2
137 && (flag_move_loop_invariants
138 || flag_unswitch_loops
141 || flag_branch_on_count_reg
));
144 struct tree_opt_pass pass_loop2
=
147 gate_handle_loop2
, /* gate */
151 0, /* static_pass_number */
153 0, /* properties_required */
154 0, /* properties_provided */
155 0, /* properties_destroyed */
156 0, /* todo_flags_start */
158 TODO_ggc_collect
, /* todo_flags_finish */
163 /* Initialization of the RTL loop passes. */
168 dump_flow_info (dump_file
);
170 /* Initialize structures for layout changes. */
171 cfg_layout_initialize (0);
173 current_loops
= loop_optimizer_init (LOOPS_NORMAL
);
176 struct tree_opt_pass pass_rtl_loop_init
=
178 "loop2_init", /* name */
180 rtl_loop_init
, /* execute */
183 0, /* static_pass_number */
185 0, /* properties_required */
186 0, /* properties_provided */
187 0, /* properties_destroyed */
188 0, /* todo_flags_start */
189 TODO_dump_func
, /* todo_flags_finish */
194 /* Finalization of the RTL loop passes. */
201 loop_optimizer_finalize (current_loops
);
203 free_dominance_info (CDI_DOMINATORS
);
205 /* Finalize layout changes. */
207 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
208 bb
->aux
= bb
->next_bb
;
209 cfg_layout_finalize ();
211 cleanup_cfg (CLEANUP_EXPENSIVE
);
212 delete_trivially_dead_insns (get_insns (), max_reg_num ());
213 reg_scan (get_insns (), max_reg_num ());
215 dump_flow_info (dump_file
);
217 current_loops
= NULL
;
220 struct tree_opt_pass pass_rtl_loop_done
=
222 "loop2_done", /* name */
224 rtl_loop_done
, /* execute */
227 0, /* static_pass_number */
229 0, /* properties_required */
230 0, /* properties_provided */
231 0, /* properties_destroyed */
232 0, /* todo_flags_start */
233 TODO_dump_func
, /* todo_flags_finish */
238 /* Loop invariant code motion. */
240 gate_rtl_move_loop_invariants (void)
242 return flag_move_loop_invariants
;
246 rtl_move_loop_invariants (void)
249 move_loop_invariants (current_loops
);
252 struct tree_opt_pass pass_rtl_move_loop_invariants
=
254 "loop2_invariant", /* name */
255 gate_rtl_move_loop_invariants
, /* gate */
256 rtl_move_loop_invariants
, /* execute */
259 0, /* static_pass_number */
261 0, /* properties_required */
262 0, /* properties_provided */
263 0, /* properties_destroyed */
264 0, /* todo_flags_start */
265 TODO_dump_func
, /* todo_flags_finish */
270 /* Loop unswitching for RTL. */
272 gate_rtl_unswitch (void)
274 return flag_unswitch_loops
;
281 unswitch_loops (current_loops
);
284 struct tree_opt_pass pass_rtl_unswitch
=
286 "loop2_unswitch", /* name */
287 gate_rtl_unswitch
, /* gate */
288 rtl_unswitch
, /* execute */
291 0, /* static_pass_number */
293 0, /* properties_required */
294 0, /* properties_provided */
295 0, /* properties_destroyed */
296 0, /* todo_flags_start */
297 TODO_dump_func
, /* todo_flags_finish */
302 /* Loop unswitching for RTL. */
304 gate_rtl_unroll_and_peel_loops (void)
306 return (flag_peel_loops
|| flag_unroll_loops
|| flag_unroll_all_loops
);
310 rtl_unroll_and_peel_loops (void)
318 if (flag_unroll_loops
)
320 if (flag_unroll_all_loops
)
321 flags
|= UAP_UNROLL_ALL
;
323 unroll_and_peel_loops (current_loops
, flags
);
327 struct tree_opt_pass pass_rtl_unroll_and_peel_loops
=
329 "loop2_unroll", /* name */
330 gate_rtl_unroll_and_peel_loops
, /* gate */
331 rtl_unroll_and_peel_loops
, /* execute */
334 0, /* static_pass_number */
336 0, /* properties_required */
337 0, /* properties_provided */
338 0, /* properties_destroyed */
339 0, /* todo_flags_start */
340 TODO_dump_func
, /* todo_flags_finish */
345 /* The doloop optimization. */
347 gate_rtl_doloop (void)
349 #ifdef HAVE_doloop_end
350 return (flag_branch_on_count_reg
&& HAVE_doloop_end
);
359 #ifdef HAVE_doloop_end
361 doloop_optimize_loops (current_loops
);
365 struct tree_opt_pass pass_rtl_doloop
=
367 "loop2_doloop", /* name */
368 gate_rtl_doloop
, /* gate */
369 rtl_doloop
, /* execute */
372 0, /* static_pass_number */
374 0, /* properties_required */
375 0, /* properties_provided */
376 0, /* properties_destroyed */
377 0, /* todo_flags_start */
378 TODO_dump_func
, /* todo_flags_finish */