1 /* Loop optimizer initialization routines and RTL loop optimization passes.
2 Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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
9 version.
10
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
14 for more details.
15
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
19 02110-1301, USA. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "hard-reg-set.h"
27 #include "obstack.h"
28 #include "basic-block.h"
29 #include "cfgloop.h"
30 #include "cfglayout.h"
31 #include "tree-pass.h"
32 #include "timevar.h"
33 #include "flags.h"
34
35
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
38 loops. */
39
40 struct loops *
loop_optimizer_init(unsigned flags)41 loop_optimizer_init (unsigned flags)
42 {
43 struct loops *loops = XCNEW (struct loops);
44 edge e;
45 edge_iterator ei;
46 static bool first_time = true;
47
48 if (first_time)
49 {
50 first_time = false;
51 init_set_costs ();
52 }
53
54 /* Avoid annoying special cases of edges going to exit
55 block. */
56
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))
59 split_edge (e);
60 else
61 ei_next (&ei);
62
63 /* Find the loops. */
64
65 if (flow_loops_find (loops) <= 1)
66 {
67 /* No loops. */
68 flow_loops_free (loops);
69 free (loops);
70
71 return NULL;
72 }
73
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;
79
80 /* Create pre-headers. */
81 if (flags & LOOPS_HAVE_PREHEADERS)
82 create_preheaders (loops, CP_SIMPLE_PREHEADERS);
83
84 /* Force all latches to have only single successor. */
85 if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
86 force_single_succ_latches (loops);
87
88 /* Mark irreducible loops. */
89 if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
90 mark_irreducible_loops (loops);
91
92 if (flags & LOOPS_HAVE_MARKED_SINGLE_EXITS)
93 mark_single_exit_loops (loops);
94
95 /* Dump loops. */
96 flow_loops_dump (loops, dump_file, NULL, 1);
97
98 #ifdef ENABLE_CHECKING
99 verify_dominators (CDI_DOMINATORS);
100 verify_loop_structure (loops);
101 #endif
102
103 return loops;
104 }
105
106 /* Finalize loop optimizer. */
107 void
loop_optimizer_finalize(struct loops * loops)108 loop_optimizer_finalize (struct loops *loops)
109 {
110 unsigned i;
111
112 if (!loops)
113 return;
114
115 for (i = 1; i < loops->num; i++)
116 if (loops->parray[i])
117 free_simple_loop_desc (loops->parray[i]);
118
119 /* Clean up. */
120 flow_loops_free (loops);
121 free (loops);
122
123 /* Checking. */
124 #ifdef ENABLE_CHECKING
125 verify_flow_info ();
126 #endif
127 }
128
129
130 /* Gate for the RTL loop superpass. The actual passes are subpasses.
131 See passes.c for more on that. */
132
133 static bool
gate_handle_loop2(void)134 gate_handle_loop2 (void)
135 {
136 return (optimize > 0
137 && (flag_move_loop_invariants
138 || flag_unswitch_loops
139 || flag_peel_loops
140 || flag_unroll_loops
141 #ifdef HAVE_doloop_end
142 || (flag_branch_on_count_reg && HAVE_doloop_end)
143 #endif
144 ));
145 }
146
147 struct tree_opt_pass pass_loop2 =
148 {
149 "loop2", /* name */
150 gate_handle_loop2, /* gate */
151 NULL, /* execute */
152 NULL, /* sub */
153 NULL, /* next */
154 0, /* static_pass_number */
155 TV_LOOP, /* tv_id */
156 0, /* properties_required */
157 0, /* properties_provided */
158 0, /* properties_destroyed */
159 0, /* todo_flags_start */
160 TODO_dump_func |
161 TODO_ggc_collect, /* todo_flags_finish */
162 'L' /* letter */
163 };
164
165
166 /* Initialization of the RTL loop passes. */
167 static unsigned int
rtl_loop_init(void)168 rtl_loop_init (void)
169 {
170 if (dump_file)
171 dump_flow_info (dump_file, dump_flags);
172
173 /* Initialize structures for layout changes. */
174 cfg_layout_initialize (0);
175
176 current_loops = loop_optimizer_init (LOOPS_NORMAL);
177 return 0;
178 }
179
180 struct tree_opt_pass pass_rtl_loop_init =
181 {
182 "loop2_init", /* name */
183 NULL, /* gate */
184 rtl_loop_init, /* execute */
185 NULL, /* sub */
186 NULL, /* next */
187 0, /* static_pass_number */
188 TV_LOOP, /* tv_id */
189 0, /* properties_required */
190 0, /* properties_provided */
191 0, /* properties_destroyed */
192 0, /* todo_flags_start */
193 TODO_dump_func, /* todo_flags_finish */
194 'L' /* letter */
195 };
196
197
198 /* Finalization of the RTL loop passes. */
199 static unsigned int
rtl_loop_done(void)200 rtl_loop_done (void)
201 {
202 basic_block bb;
203
204 if (current_loops)
205 loop_optimizer_finalize (current_loops);
206
207 free_dominance_info (CDI_DOMINATORS);
208
209 /* Finalize layout changes. */
210 FOR_EACH_BB (bb)
211 if (bb->next_bb != EXIT_BLOCK_PTR)
212 bb->aux = bb->next_bb;
213 cfg_layout_finalize ();
214
215 cleanup_cfg (CLEANUP_EXPENSIVE);
216 delete_trivially_dead_insns (get_insns (), max_reg_num ());
217 reg_scan (get_insns (), max_reg_num ());
218 if (dump_file)
219 dump_flow_info (dump_file, dump_flags);
220
221 current_loops = NULL;
222 return 0;
223 }
224
225 struct tree_opt_pass pass_rtl_loop_done =
226 {
227 "loop2_done", /* name */
228 NULL, /* gate */
229 rtl_loop_done, /* execute */
230 NULL, /* sub */
231 NULL, /* next */
232 0, /* static_pass_number */
233 TV_LOOP, /* tv_id */
234 0, /* properties_required */
235 0, /* properties_provided */
236 0, /* properties_destroyed */
237 0, /* todo_flags_start */
238 TODO_dump_func, /* todo_flags_finish */
239 'L' /* letter */
240 };
241
242
243 /* Loop invariant code motion. */
244 static bool
gate_rtl_move_loop_invariants(void)245 gate_rtl_move_loop_invariants (void)
246 {
247 return flag_move_loop_invariants;
248 }
249
250 static unsigned int
rtl_move_loop_invariants(void)251 rtl_move_loop_invariants (void)
252 {
253 if (current_loops)
254 move_loop_invariants (current_loops);
255 return 0;
256 }
257
258 struct tree_opt_pass pass_rtl_move_loop_invariants =
259 {
260 "loop2_invariant", /* name */
261 gate_rtl_move_loop_invariants, /* gate */
262 rtl_move_loop_invariants, /* execute */
263 NULL, /* sub */
264 NULL, /* next */
265 0, /* static_pass_number */
266 TV_LOOP, /* tv_id */
267 0, /* properties_required */
268 0, /* properties_provided */
269 0, /* properties_destroyed */
270 0, /* todo_flags_start */
271 TODO_dump_func, /* todo_flags_finish */
272 'L' /* letter */
273 };
274
275
276 /* Loop unswitching for RTL. */
277 static bool
gate_rtl_unswitch(void)278 gate_rtl_unswitch (void)
279 {
280 return flag_unswitch_loops;
281 }
282
283 static unsigned int
rtl_unswitch(void)284 rtl_unswitch (void)
285 {
286 if (current_loops)
287 unswitch_loops (current_loops);
288 return 0;
289 }
290
291 struct tree_opt_pass pass_rtl_unswitch =
292 {
293 "loop2_unswitch", /* name */
294 gate_rtl_unswitch, /* gate */
295 rtl_unswitch, /* execute */
296 NULL, /* sub */
297 NULL, /* next */
298 0, /* static_pass_number */
299 TV_LOOP, /* tv_id */
300 0, /* properties_required */
301 0, /* properties_provided */
302 0, /* properties_destroyed */
303 0, /* todo_flags_start */
304 TODO_dump_func, /* todo_flags_finish */
305 'L' /* letter */
306 };
307
308
309 /* Loop unswitching for RTL. */
310 static bool
gate_rtl_unroll_and_peel_loops(void)311 gate_rtl_unroll_and_peel_loops (void)
312 {
313 return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
314 }
315
316 static unsigned int
rtl_unroll_and_peel_loops(void)317 rtl_unroll_and_peel_loops (void)
318 {
319 if (current_loops)
320 {
321 int flags = 0;
322
323 if (flag_peel_loops)
324 flags |= UAP_PEEL;
325 if (flag_unroll_loops)
326 flags |= UAP_UNROLL;
327 if (flag_unroll_all_loops)
328 flags |= UAP_UNROLL_ALL;
329
330 unroll_and_peel_loops (current_loops, flags);
331 }
332 return 0;
333 }
334
335 struct tree_opt_pass pass_rtl_unroll_and_peel_loops =
336 {
337 "loop2_unroll", /* name */
338 gate_rtl_unroll_and_peel_loops, /* gate */
339 rtl_unroll_and_peel_loops, /* execute */
340 NULL, /* sub */
341 NULL, /* next */
342 0, /* static_pass_number */
343 TV_LOOP, /* tv_id */
344 0, /* properties_required */
345 0, /* properties_provided */
346 0, /* properties_destroyed */
347 0, /* todo_flags_start */
348 TODO_dump_func, /* todo_flags_finish */
349 'L' /* letter */
350 };
351
352
353 /* The doloop optimization. */
354 static bool
gate_rtl_doloop(void)355 gate_rtl_doloop (void)
356 {
357 #ifdef HAVE_doloop_end
358 return (flag_branch_on_count_reg && HAVE_doloop_end);
359 #else
360 return 0;
361 #endif
362 }
363
364 static unsigned int
rtl_doloop(void)365 rtl_doloop (void)
366 {
367 #ifdef HAVE_doloop_end
368 if (current_loops)
369 doloop_optimize_loops (current_loops);
370 #endif
371 return 0;
372 }
373
374 struct tree_opt_pass pass_rtl_doloop =
375 {
376 "loop2_doloop", /* name */
377 gate_rtl_doloop, /* gate */
378 rtl_doloop, /* execute */
379 NULL, /* sub */
380 NULL, /* next */
381 0, /* static_pass_number */
382 TV_LOOP, /* tv_id */
383 0, /* properties_required */
384 0, /* properties_provided */
385 0, /* properties_destroyed */
386 0, /* todo_flags_start */
387 TODO_dump_func, /* todo_flags_finish */
388 'L' /* letter */
389 };
390
391