OSDN Git Service

f7a96fb2aa72389abf427eeb1fedab814c3bf392
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-loop.c
1 /* Loop optimizations over tree-ssa.
2    Copyright (C) 2003, 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
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
9 later version.
10    
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY 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, 59 Temple Place - Suite 330, Boston, MA
19 02111-1307, USA.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "rtl.h"
27 #include "tm_p.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
30 #include "output.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
34 #include "tree-pass.h"
35 #include "timevar.h"
36 #include "cfgloop.h"
37 #include "flags.h"
38 #include "tree-inline.h"
39 #include "tree-scalar-evolution.h"
40
41 /* The loop tree currently optimized.  */
42
43 struct loops *current_loops = NULL;
44
45 /* Initializes the loop structures.  DUMP is the file to that the details
46    about the analysis should be dumped.  */
47
48 static struct loops *
49 tree_loop_optimizer_init (FILE *dump)
50 {
51   struct loops *loops = loop_optimizer_init (dump);
52
53   if (!loops)
54     return NULL;
55
56   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
57
58   return loops;
59 }
60
61 /* The loop superpass.  */
62
63 static bool
64 gate_loop (void)
65 {
66   return flag_tree_loop_optimize != 0;
67 }
68
69 struct tree_opt_pass pass_loop = 
70 {
71   "loop",                               /* name */
72   gate_loop,                            /* gate */
73   NULL,                                 /* execute */
74   NULL,                                 /* sub */
75   NULL,                                 /* next */
76   0,                                    /* static_pass_number */
77   TV_TREE_LOOP,                         /* tv_id */
78   PROP_cfg,                             /* properties_required */
79   0,                                    /* properties_provided */
80   0,                                    /* properties_destroyed */
81   TODO_ggc_collect,                     /* todo_flags_start */
82   TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect,  /* todo_flags_finish */
83   0                                     /* letter */
84 };
85
86 /* Loop optimizer initialization.  */
87
88 static void
89 tree_ssa_loop_init (void)
90 {
91   current_loops = tree_loop_optimizer_init (dump_file);
92   if (!current_loops)
93     return;
94
95   /* Find the loops that are exited just through a single edge.  */
96   mark_single_exit_loops (current_loops);
97
98   scev_initialize (current_loops);
99 }
100   
101 struct tree_opt_pass pass_loop_init = 
102 {
103   "loopinit",                           /* name */
104   NULL,                                 /* gate */
105   tree_ssa_loop_init,                   /* execute */
106   NULL,                                 /* sub */
107   NULL,                                 /* next */
108   0,                                    /* static_pass_number */
109   TV_TREE_LOOP_INIT,                    /* tv_id */
110   PROP_cfg,                             /* properties_required */
111   0,                                    /* properties_provided */
112   0,                                    /* properties_destroyed */
113   0,                                    /* todo_flags_start */
114   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
115   0                                     /* letter */
116 };
117
118 /* Loop invariant motion pass.  */
119
120 static void
121 tree_ssa_loop_im (void)
122 {
123   if (!current_loops)
124     return;
125
126   tree_ssa_lim (current_loops);
127 }
128
129 static bool
130 gate_tree_ssa_loop_im (void)
131 {
132   return flag_tree_loop_im != 0;
133 }
134
135 struct tree_opt_pass pass_lim = 
136 {
137   "lim",                                /* name */
138   gate_tree_ssa_loop_im,                /* gate */
139   tree_ssa_loop_im,                     /* execute */
140   NULL,                                 /* sub */
141   NULL,                                 /* next */
142   0,                                    /* static_pass_number */
143   TV_LIM,                               /* tv_id */
144   PROP_cfg,                             /* properties_required */
145   0,                                    /* properties_provided */
146   0,                                    /* properties_destroyed */
147   0,                                    /* todo_flags_start */
148   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
149   0                                     /* letter */
150 };
151
152 /* Loop unswitching pass.  */
153
154 static void
155 tree_ssa_loop_unswitch (void)
156 {
157   if (!current_loops)
158     return;
159
160   tree_ssa_unswitch_loops (current_loops);
161 }
162
163 static bool
164 gate_tree_ssa_loop_unswitch (void)
165 {
166   return flag_unswitch_loops != 0;
167 }
168
169 struct tree_opt_pass pass_unswitch = 
170 {
171   "unswitch",                           /* name */
172   gate_tree_ssa_loop_unswitch,          /* gate */
173   tree_ssa_loop_unswitch,               /* execute */
174   NULL,                                 /* sub */
175   NULL,                                 /* next */
176   0,                                    /* static_pass_number */
177   TV_TREE_LOOP_UNSWITCH,                /* tv_id */
178   PROP_cfg,                             /* properties_required */
179   0,                                    /* properties_provided */
180   0,                                    /* properties_destroyed */
181   0,                                    /* todo_flags_start */
182   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
183   0                                     /* letter */
184 };
185
186 /* Loop autovectorization.  */
187
188 static void
189 tree_vectorize (void)
190 {
191   if (!current_loops)
192     return;
193
194   vectorize_loops (current_loops);
195 }
196
197 static bool
198 gate_tree_vectorize (void)
199 {
200   return flag_tree_vectorize != 0;
201 }
202
203 struct tree_opt_pass pass_vectorize =
204 {
205   "vect",                               /* name */
206   gate_tree_vectorize,                  /* gate */
207   tree_vectorize,                       /* execute */
208   NULL,                                 /* sub */
209   NULL,                                 /* next */
210   0,                                    /* static_pass_number */
211   TV_TREE_VECTORIZATION,                /* tv_id */
212   PROP_cfg | PROP_ssa,                  /* properties_required */
213   0,                                    /* properties_provided */
214   0,                                    /* properties_destroyed */
215   0,                                    /* todo_flags_start */
216   TODO_dump_func | TODO_update_ssa,     /* todo_flags_finish */
217   0                                     /* letter */
218 };
219
220
221 /* Loop nest optimizations.  */
222
223 static void
224 tree_linear_transform (void)
225 {
226   if (!current_loops)
227     return;
228
229   linear_transform_loops (current_loops);
230 }
231
232 static bool
233 gate_tree_linear_transform (void)
234 {
235   return flag_tree_loop_linear != 0;
236 }
237
238 struct tree_opt_pass pass_linear_transform =
239 {
240   "ltrans",                             /* name */
241   gate_tree_linear_transform,           /* gate */
242   tree_linear_transform,                /* execute */
243   NULL,                                 /* sub */
244   NULL,                                 /* next */
245   0,                                    /* static_pass_number */
246   TV_TREE_LINEAR_TRANSFORM,             /* tv_id */
247   PROP_cfg | PROP_ssa,                  /* properties_required */
248   0,                                    /* properties_provided */
249   0,                                    /* properties_destroyed */
250   0,                                    /* todo_flags_start */
251   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
252   0                                     /* letter */    
253 };
254
255 /* Canonical induction variable creation pass.  */
256
257 static void
258 tree_ssa_loop_ivcanon (void)
259 {
260   if (!current_loops)
261     return;
262
263   canonicalize_induction_variables (current_loops);
264 }
265
266 static bool
267 gate_tree_ssa_loop_ivcanon (void)
268 {
269   return flag_tree_loop_ivcanon != 0;
270 }
271
272 struct tree_opt_pass pass_iv_canon =
273 {
274   "ivcanon",                            /* name */
275   gate_tree_ssa_loop_ivcanon,           /* gate */
276   tree_ssa_loop_ivcanon,                /* execute */
277   NULL,                                 /* sub */
278   NULL,                                 /* next */
279   0,                                    /* static_pass_number */
280   TV_TREE_LOOP_IVCANON,                 /* tv_id */
281   PROP_cfg | PROP_ssa,                  /* properties_required */
282   0,                                    /* properties_provided */
283   0,                                    /* properties_destroyed */
284   0,                                    /* todo_flags_start */
285   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
286   0                                     /* letter */
287 };
288
289 /* Record bounds on numbers of iterations of loops.  */
290
291 static void
292 tree_ssa_loop_bounds (void)
293 {
294   if (!current_loops)
295     return;
296
297   estimate_numbers_of_iterations (current_loops);
298   scev_reset ();
299 }
300
301 struct tree_opt_pass pass_record_bounds =
302 {
303   NULL,                                 /* name */
304   NULL,                                 /* gate */
305   tree_ssa_loop_bounds,                 /* execute */
306   NULL,                                 /* sub */
307   NULL,                                 /* next */
308   0,                                    /* static_pass_number */
309   TV_TREE_LOOP_BOUNDS,                  /* tv_id */
310   PROP_cfg | PROP_ssa,                  /* properties_required */
311   0,                                    /* properties_provided */
312   0,                                    /* properties_destroyed */
313   0,                                    /* todo_flags_start */
314   0,                                    /* todo_flags_finish */
315   0                                     /* letter */
316 };
317
318 /* Complete unrolling of loops.  */
319
320 static void
321 tree_complete_unroll (void)
322 {
323   if (!current_loops)
324     return;
325
326   tree_unroll_loops_completely (current_loops,
327                                 flag_unroll_loops
328                                 || flag_peel_loops
329                                 || optimize >= 3);
330 }
331
332 static bool
333 gate_tree_complete_unroll (void)
334 {
335   return true;
336 }
337
338 struct tree_opt_pass pass_complete_unroll =
339 {
340   "cunroll",                            /* name */
341   gate_tree_complete_unroll,            /* gate */
342   tree_complete_unroll,                 /* execute */
343   NULL,                                 /* sub */
344   NULL,                                 /* next */
345   0,                                    /* static_pass_number */
346   TV_COMPLETE_UNROLL,                   /* tv_id */
347   PROP_cfg | PROP_ssa,                  /* properties_required */
348   0,                                    /* properties_provided */
349   0,                                    /* properties_destroyed */
350   0,                                    /* todo_flags_start */
351   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
352   0                                     /* letter */
353 };
354
355 /* Induction variable optimizations.  */
356
357 static void
358 tree_ssa_loop_ivopts (void)
359 {
360   if (!current_loops)
361     return;
362
363   tree_ssa_iv_optimize (current_loops);
364 }
365
366 static bool
367 gate_tree_ssa_loop_ivopts (void)
368 {
369   return flag_ivopts != 0;
370 }
371
372 struct tree_opt_pass pass_iv_optimize =
373 {
374   "ivopts",                             /* name */
375   gate_tree_ssa_loop_ivopts,            /* gate */
376   tree_ssa_loop_ivopts,                 /* execute */
377   NULL,                                 /* sub */
378   NULL,                                 /* next */
379   0,                                    /* static_pass_number */
380   TV_TREE_LOOP_IVOPTS,                  /* tv_id */
381   PROP_cfg | PROP_ssa,                  /* properties_required */
382   0,                                    /* properties_provided */
383   0,                                    /* properties_destroyed */
384   0,                                    /* todo_flags_start */
385   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
386   0                                     /* letter */
387 };
388
389 /* Loop optimizer finalization.  */
390
391 static void
392 tree_ssa_loop_done (void)
393 {
394   if (!current_loops)
395     return;
396
397   free_numbers_of_iterations_estimates (current_loops);
398   scev_finalize ();
399   loop_optimizer_finalize (current_loops,
400                            (dump_flags & TDF_DETAILS ? dump_file : NULL));
401   current_loops = NULL;
402 }
403   
404 struct tree_opt_pass pass_loop_done = 
405 {
406   "loopdone",                           /* name */
407   NULL,                                 /* gate */
408   tree_ssa_loop_done,                   /* execute */
409   NULL,                                 /* sub */
410   NULL,                                 /* next */
411   0,                                    /* static_pass_number */
412   TV_TREE_LOOP_FINI,                    /* tv_id */
413   PROP_cfg,                             /* properties_required */
414   0,                                    /* properties_provided */
415   0,                                    /* properties_destroyed */
416   0,                                    /* todo_flags_start */
417   TODO_cleanup_cfg | TODO_dump_func,    /* todo_flags_finish */
418   0                                     /* letter */
419 };