OSDN Git Service

* tracer.c (tracer): Don't take FLAGS argument. Assert we are
[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   gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
175   
176   if (dump_file)
177     dump_flow_info (dump_file, dump_flags);
178
179   loop_optimizer_init (LOOPS_NORMAL);
180   return 0;
181 }
182
183 struct tree_opt_pass pass_rtl_loop_init =
184 {
185   "loop2_init",                           /* name */
186   NULL,                                 /* gate */
187   rtl_loop_init,                        /* execute */
188   NULL,                                 /* sub */
189   NULL,                                 /* next */
190   0,                                    /* static_pass_number */
191   TV_LOOP,                              /* tv_id */
192   0,                                    /* properties_required */
193   0,                                    /* properties_provided */
194   0,                                    /* properties_destroyed */
195   0,                                    /* todo_flags_start */
196   TODO_dump_func,                       /* todo_flags_finish */
197   'L'                                   /* letter */
198 };
199
200 \f
201 /* Finalization of the RTL loop passes.  */
202
203 static unsigned int
204 rtl_loop_done (void)
205 {
206   loop_optimizer_finalize ();
207   free_dominance_info (CDI_DOMINATORS);
208
209   cleanup_cfg (CLEANUP_EXPENSIVE);
210   delete_trivially_dead_insns (get_insns (), max_reg_num ());
211   reg_scan (get_insns (), max_reg_num ());
212   if (dump_file)
213     dump_flow_info (dump_file, dump_flags);
214
215   return 0;
216 }
217
218 struct tree_opt_pass pass_rtl_loop_done =
219 {
220   "loop2_done",                          /* name */
221   NULL,                                 /* gate */
222   rtl_loop_done,                        /* execute */
223   NULL,                                 /* sub */
224   NULL,                                 /* next */
225   0,                                    /* static_pass_number */
226   TV_LOOP,                              /* tv_id */
227   0,                                    /* properties_required */
228   0,                                    /* properties_provided */
229   0,                                    /* properties_destroyed */
230   0,                                    /* todo_flags_start */
231   TODO_dump_func,                       /* todo_flags_finish */
232   'L'                                   /* letter */
233 };
234
235 \f
236 /* Loop invariant code motion.  */
237 static bool
238 gate_rtl_move_loop_invariants (void)
239 {
240   return flag_move_loop_invariants;
241 }
242
243 static unsigned int
244 rtl_move_loop_invariants (void)
245 {
246   if (current_loops)
247     move_loop_invariants ();
248   return 0;
249 }
250
251 struct tree_opt_pass pass_rtl_move_loop_invariants =
252 {
253   "loop2_invariant",                     /* name */
254   gate_rtl_move_loop_invariants,        /* gate */
255   rtl_move_loop_invariants,             /* execute */
256   NULL,                                 /* sub */
257   NULL,                                 /* next */
258   0,                                    /* static_pass_number */
259   TV_LOOP,                              /* tv_id */
260   0,                                    /* properties_required */
261   0,                                    /* properties_provided */
262   0,                                    /* properties_destroyed */
263   0,                                    /* todo_flags_start */
264   TODO_dump_func,                       /* todo_flags_finish */
265   'L'                                   /* letter */
266 };
267
268 \f
269 /* Loop unswitching for RTL.  */
270 static bool
271 gate_rtl_unswitch (void)
272 {
273   return flag_unswitch_loops;
274 }
275
276 static unsigned int
277 rtl_unswitch (void)
278 {
279   if (current_loops)
280     unswitch_loops ();
281   return 0;
282 }
283
284 struct tree_opt_pass pass_rtl_unswitch =
285 {
286   "loop2_unswitch",                      /* name */
287   gate_rtl_unswitch,                    /* gate */
288   rtl_unswitch,                         /* execute */
289   NULL,                                 /* sub */
290   NULL,                                 /* next */
291   0,                                    /* static_pass_number */
292   TV_LOOP,                              /* tv_id */
293   0,                                    /* properties_required */
294   0,                                    /* properties_provided */
295   0,                                    /* properties_destroyed */
296   0,                                    /* todo_flags_start */
297   TODO_dump_func,                       /* todo_flags_finish */
298   'L'                                   /* letter */
299 };
300
301 \f
302 /* Loop unswitching for RTL.  */
303 static bool
304 gate_rtl_unroll_and_peel_loops (void)
305 {
306   return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
307 }
308
309 static unsigned int
310 rtl_unroll_and_peel_loops (void)
311 {
312   if (current_loops)
313     {
314       int flags = 0;
315
316       if (flag_peel_loops)
317         flags |= UAP_PEEL;
318       if (flag_unroll_loops)
319         flags |= UAP_UNROLL;
320       if (flag_unroll_all_loops)
321         flags |= UAP_UNROLL_ALL;
322
323       unroll_and_peel_loops (flags);
324     }
325   return 0;
326 }
327
328 struct tree_opt_pass pass_rtl_unroll_and_peel_loops =
329 {
330   "loop2_unroll",                        /* name */
331   gate_rtl_unroll_and_peel_loops,       /* gate */
332   rtl_unroll_and_peel_loops,            /* execute */
333   NULL,                                 /* sub */
334   NULL,                                 /* next */
335   0,                                    /* static_pass_number */
336   TV_LOOP,                              /* tv_id */
337   0,                                    /* properties_required */
338   0,                                    /* properties_provided */
339   0,                                    /* properties_destroyed */
340   0,                                    /* todo_flags_start */
341   TODO_dump_func,                       /* todo_flags_finish */
342   'L'                                   /* letter */
343 };
344
345 \f
346 /* The doloop optimization.  */
347 static bool
348 gate_rtl_doloop (void)
349 {
350 #ifdef HAVE_doloop_end
351   return (flag_branch_on_count_reg && HAVE_doloop_end);
352 #else
353   return 0;
354 #endif
355 }
356
357 static unsigned int
358 rtl_doloop (void)
359 {
360 #ifdef HAVE_doloop_end
361   if (current_loops)
362     doloop_optimize_loops ();
363 #endif
364   return 0;
365 }
366
367 struct tree_opt_pass pass_rtl_doloop =
368 {
369   "loop2_doloop",                        /* name */
370   gate_rtl_doloop,                      /* gate */
371   rtl_doloop,                           /* execute */
372   NULL,                                 /* sub */
373   NULL,                                 /* next */
374   0,                                    /* static_pass_number */
375   TV_LOOP,                              /* tv_id */
376   0,                                    /* properties_required */
377   0,                                    /* properties_provided */
378   0,                                    /* properties_destroyed */
379   0,                                    /* todo_flags_start */
380   TODO_dump_func,                       /* todo_flags_finish */
381   'L'                                   /* letter */
382 };
383