OSDN Git Service

3e6d3428b897cb2c4c06f5631c443444113722a3
[pf3gnuchains/gcc-fork.git] / gcc / loop-init.c
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 \f
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
38    loops.  */
39
40 void
41 loop_optimizer_init (unsigned flags)
42 {
43   struct loops *loops;
44
45   gcc_assert (!current_loops);
46   loops = XCNEW (struct loops);
47
48   /* Find the loops.  */
49
50   flow_loops_find (loops);
51   current_loops = loops;
52
53   if (number_of_loops () <= 1)
54     {
55       /* No loops (the 1 returned by number_of_loops corresponds to the fake
56          loop that we put as a root of the loop tree).  */
57       loop_optimizer_finalize ();
58       return;
59     }
60
61   if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
62     {
63       /* If the loops may have multiple latches, we cannot canonicalize
64          them further (and most of the loop manipulation functions will
65          not work).  However, we avoid modifying cfg, which some
66          passes may want.  */
67       gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
68                              | LOOPS_HAVE_RECORDED_EXITS)) == 0);
69       current_loops->state = LOOPS_MAY_HAVE_MULTIPLE_LATCHES;
70     }
71   else
72     disambiguate_loops_with_multiple_latches ();
73
74   /* Create pre-headers.  */
75   if (flags & LOOPS_HAVE_PREHEADERS)
76     create_preheaders (CP_SIMPLE_PREHEADERS);
77
78   /* Force all latches to have only single successor.  */
79   if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
80     force_single_succ_latches ();
81
82   /* Mark irreducible loops.  */
83   if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
84     mark_irreducible_loops ();
85
86   if (flags & LOOPS_HAVE_RECORDED_EXITS)
87     record_loop_exits ();
88
89   /* Dump loops.  */
90   flow_loops_dump (dump_file, NULL, 1);
91
92 #ifdef ENABLE_CHECKING
93   verify_dominators (CDI_DOMINATORS);
94   verify_loop_structure ();
95 #endif
96 }
97
98 /* Finalize loop structures.  */
99
100 void
101 loop_optimizer_finalize (void)
102 {
103   loop_iterator li;
104   struct loop *loop;
105   basic_block bb;
106
107   if (!current_loops)
108     return;
109
110   FOR_EACH_LOOP (li, loop, 0)
111     {
112       free_simple_loop_desc (loop);
113     }
114
115   /* Clean up.  */
116   if (current_loops->state & LOOPS_HAVE_RECORDED_EXITS)
117     release_recorded_exits ();
118   flow_loops_free (current_loops);
119   free (current_loops);
120   current_loops = NULL;
121
122   FOR_ALL_BB (bb)
123     {
124       bb->loop_father = NULL;
125     }
126
127   /* Checking.  */
128 #ifdef ENABLE_CHECKING
129   verify_flow_info ();
130 #endif
131 }
132
133 \f
134 /* Gate for the RTL loop superpass.  The actual passes are subpasses.
135    See passes.c for more on that.  */
136
137 static bool
138 gate_handle_loop2 (void)
139 {
140   return (optimize > 0
141           && (flag_move_loop_invariants
142               || flag_unswitch_loops
143               || flag_peel_loops
144               || flag_unroll_loops
145 #ifdef HAVE_doloop_end
146               || (flag_branch_on_count_reg && HAVE_doloop_end)
147 #endif
148               ));
149 }
150
151 struct tree_opt_pass pass_loop2 =
152 {
153   "loop2",                              /* name */
154   gate_handle_loop2,                    /* gate */
155   NULL,                                 /* execute */
156   NULL,                                 /* sub */
157   NULL,                                 /* next */
158   0,                                    /* static_pass_number */
159   TV_LOOP,                              /* tv_id */
160   0,                                    /* properties_required */
161   0,                                    /* properties_provided */
162   0,                                    /* properties_destroyed */
163   0,                                    /* todo_flags_start */
164   TODO_dump_func |
165   TODO_ggc_collect,                     /* todo_flags_finish */
166   'L'                                   /* letter */
167 };
168
169 \f
170 /* Initialization of the RTL loop passes.  */
171 static unsigned int
172 rtl_loop_init (void)
173 {
174   if (dump_file)
175     dump_flow_info (dump_file, dump_flags);
176
177   /* Initialize structures for layout changes.  */
178   cfg_layout_initialize (0);
179
180   loop_optimizer_init (LOOPS_NORMAL);
181   return 0;
182 }
183
184 struct tree_opt_pass pass_rtl_loop_init =
185 {
186   "loop2_init",                           /* name */
187   NULL,                                 /* gate */
188   rtl_loop_init,                        /* execute */
189   NULL,                                 /* sub */
190   NULL,                                 /* next */
191   0,                                    /* static_pass_number */
192   TV_LOOP,                              /* tv_id */
193   0,                                    /* properties_required */
194   0,                                    /* properties_provided */
195   0,                                    /* properties_destroyed */
196   0,                                    /* todo_flags_start */
197   TODO_dump_func,                       /* todo_flags_finish */
198   'L'                                   /* letter */
199 };
200
201 \f
202 /* Finalization of the RTL loop passes.  */
203
204 static unsigned int
205 rtl_loop_done (void)
206 {
207   basic_block bb;
208
209   loop_optimizer_finalize ();
210   free_dominance_info (CDI_DOMINATORS);
211
212   /* Finalize layout changes.  */
213   FOR_EACH_BB (bb)
214     if (bb->next_bb != EXIT_BLOCK_PTR)
215       bb->aux = bb->next_bb;
216   cfg_layout_finalize ();
217
218   cleanup_cfg (CLEANUP_EXPENSIVE);
219   delete_trivially_dead_insns (get_insns (), max_reg_num ());
220   reg_scan (get_insns (), max_reg_num ());
221   if (dump_file)
222     dump_flow_info (dump_file, dump_flags);
223
224   return 0;
225 }
226
227 struct tree_opt_pass pass_rtl_loop_done =
228 {
229   "loop2_done",                          /* name */
230   NULL,                                 /* gate */
231   rtl_loop_done,                        /* execute */
232   NULL,                                 /* sub */
233   NULL,                                 /* next */
234   0,                                    /* static_pass_number */
235   TV_LOOP,                              /* tv_id */
236   0,                                    /* properties_required */
237   0,                                    /* properties_provided */
238   0,                                    /* properties_destroyed */
239   0,                                    /* todo_flags_start */
240   TODO_dump_func,                       /* todo_flags_finish */
241   'L'                                   /* letter */
242 };
243
244 \f
245 /* Loop invariant code motion.  */
246 static bool
247 gate_rtl_move_loop_invariants (void)
248 {
249   return flag_move_loop_invariants;
250 }
251
252 static unsigned int
253 rtl_move_loop_invariants (void)
254 {
255   if (current_loops)
256     move_loop_invariants ();
257   return 0;
258 }
259
260 struct tree_opt_pass pass_rtl_move_loop_invariants =
261 {
262   "loop2_invariant",                     /* name */
263   gate_rtl_move_loop_invariants,        /* gate */
264   rtl_move_loop_invariants,             /* execute */
265   NULL,                                 /* sub */
266   NULL,                                 /* next */
267   0,                                    /* static_pass_number */
268   TV_LOOP,                              /* tv_id */
269   0,                                    /* properties_required */
270   0,                                    /* properties_provided */
271   0,                                    /* properties_destroyed */
272   0,                                    /* todo_flags_start */
273   TODO_dump_func,                       /* todo_flags_finish */
274   'L'                                   /* letter */
275 };
276
277 \f
278 /* Loop unswitching for RTL.  */
279 static bool
280 gate_rtl_unswitch (void)
281 {
282   return flag_unswitch_loops;
283 }
284
285 static unsigned int
286 rtl_unswitch (void)
287 {
288   if (current_loops)
289     unswitch_loops ();
290   return 0;
291 }
292
293 struct tree_opt_pass pass_rtl_unswitch =
294 {
295   "loop2_unswitch",                      /* name */
296   gate_rtl_unswitch,                    /* gate */
297   rtl_unswitch,                         /* execute */
298   NULL,                                 /* sub */
299   NULL,                                 /* next */
300   0,                                    /* static_pass_number */
301   TV_LOOP,                              /* tv_id */
302   0,                                    /* properties_required */
303   0,                                    /* properties_provided */
304   0,                                    /* properties_destroyed */
305   0,                                    /* todo_flags_start */
306   TODO_dump_func,                       /* todo_flags_finish */
307   'L'                                   /* letter */
308 };
309
310 \f
311 /* Loop unswitching for RTL.  */
312 static bool
313 gate_rtl_unroll_and_peel_loops (void)
314 {
315   return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
316 }
317
318 static unsigned int
319 rtl_unroll_and_peel_loops (void)
320 {
321   if (current_loops)
322     {
323       int flags = 0;
324
325       if (flag_peel_loops)
326         flags |= UAP_PEEL;
327       if (flag_unroll_loops)
328         flags |= UAP_UNROLL;
329       if (flag_unroll_all_loops)
330         flags |= UAP_UNROLL_ALL;
331
332       unroll_and_peel_loops (flags);
333     }
334   return 0;
335 }
336
337 struct tree_opt_pass pass_rtl_unroll_and_peel_loops =
338 {
339   "loop2_unroll",                        /* name */
340   gate_rtl_unroll_and_peel_loops,       /* gate */
341   rtl_unroll_and_peel_loops,            /* execute */
342   NULL,                                 /* sub */
343   NULL,                                 /* next */
344   0,                                    /* static_pass_number */
345   TV_LOOP,                              /* tv_id */
346   0,                                    /* properties_required */
347   0,                                    /* properties_provided */
348   0,                                    /* properties_destroyed */
349   0,                                    /* todo_flags_start */
350   TODO_dump_func,                       /* todo_flags_finish */
351   'L'                                   /* letter */
352 };
353
354 \f
355 /* The doloop optimization.  */
356 static bool
357 gate_rtl_doloop (void)
358 {
359 #ifdef HAVE_doloop_end
360   return (flag_branch_on_count_reg && HAVE_doloop_end);
361 #else
362   return 0;
363 #endif
364 }
365
366 static unsigned int
367 rtl_doloop (void)
368 {
369 #ifdef HAVE_doloop_end
370   if (current_loops)
371     doloop_optimize_loops ();
372 #endif
373   return 0;
374 }
375
376 struct tree_opt_pass pass_rtl_doloop =
377 {
378   "loop2_doloop",                        /* name */
379   gate_rtl_doloop,                      /* gate */
380   rtl_doloop,                           /* execute */
381   NULL,                                 /* sub */
382   NULL,                                 /* next */
383   0,                                    /* static_pass_number */
384   TV_LOOP,                              /* tv_id */
385   0,                                    /* properties_required */
386   0,                                    /* properties_provided */
387   0,                                    /* properties_destroyed */
388   0,                                    /* todo_flags_start */
389   TODO_dump_func,                       /* todo_flags_finish */
390   'L'                                   /* letter */
391 };
392