OSDN Git Service

69d353b7c15997778405d031febe3ebd21414dde
[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, 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 "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 /* Initializes the loop structures.  */
42
43 static void
44 tree_loop_optimizer_init (void)
45 {
46   loop_optimizer_init (LOOPS_NORMAL
47                        | LOOPS_HAVE_MARKED_SINGLE_EXITS);
48   if (!current_loops)
49     return;
50
51   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
52 }
53
54 /* The loop superpass.  */
55
56 static bool
57 gate_tree_loop (void)
58 {
59   return flag_tree_loop_optimize != 0;
60 }
61
62 struct tree_opt_pass pass_tree_loop = 
63 {
64   "loop",                               /* name */
65   gate_tree_loop,                       /* gate */
66   NULL,                                 /* execute */
67   NULL,                                 /* sub */
68   NULL,                                 /* next */
69   0,                                    /* static_pass_number */
70   TV_TREE_LOOP,                         /* tv_id */
71   PROP_cfg,                             /* properties_required */
72   0,                                    /* properties_provided */
73   0,                                    /* properties_destroyed */
74   TODO_ggc_collect,                     /* todo_flags_start */
75   TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect,  /* todo_flags_finish */
76   0                                     /* letter */
77 };
78
79 /* Loop optimizer initialization.  */
80
81 static unsigned int
82 tree_ssa_loop_init (void)
83 {
84   tree_loop_optimizer_init ();
85   if (!current_loops)
86     return 0;
87
88   scev_initialize (current_loops);
89   return 0;
90 }
91   
92 struct tree_opt_pass pass_tree_loop_init = 
93 {
94   "loopinit",                           /* name */
95   NULL,                                 /* gate */
96   tree_ssa_loop_init,                   /* execute */
97   NULL,                                 /* sub */
98   NULL,                                 /* next */
99   0,                                    /* static_pass_number */
100   TV_TREE_LOOP_INIT,                    /* tv_id */
101   PROP_cfg,                             /* properties_required */
102   0,                                    /* properties_provided */
103   0,                                    /* properties_destroyed */
104   0,                                    /* todo_flags_start */
105   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
106   0                                     /* letter */
107 };
108
109 /* Loop invariant motion pass.  */
110
111 static unsigned int
112 tree_ssa_loop_im (void)
113 {
114   if (!current_loops)
115     return 0;
116
117   tree_ssa_lim (current_loops);
118   return 0;
119 }
120
121 static bool
122 gate_tree_ssa_loop_im (void)
123 {
124   return flag_tree_loop_im != 0;
125 }
126
127 struct tree_opt_pass pass_lim = 
128 {
129   "lim",                                /* name */
130   gate_tree_ssa_loop_im,                /* gate */
131   tree_ssa_loop_im,                     /* execute */
132   NULL,                                 /* sub */
133   NULL,                                 /* next */
134   0,                                    /* static_pass_number */
135   TV_LIM,                               /* tv_id */
136   PROP_cfg,                             /* properties_required */
137   0,                                    /* properties_provided */
138   0,                                    /* properties_destroyed */
139   0,                                    /* todo_flags_start */
140   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
141   0                                     /* letter */
142 };
143
144 /* Loop unswitching pass.  */
145
146 static unsigned int
147 tree_ssa_loop_unswitch (void)
148 {
149   if (!current_loops)
150     return 0;
151
152   return tree_ssa_unswitch_loops (current_loops);
153 }
154
155 static bool
156 gate_tree_ssa_loop_unswitch (void)
157 {
158   return flag_unswitch_loops != 0;
159 }
160
161 struct tree_opt_pass pass_tree_unswitch = 
162 {
163   "unswitch",                           /* name */
164   gate_tree_ssa_loop_unswitch,          /* gate */
165   tree_ssa_loop_unswitch,               /* execute */
166   NULL,                                 /* sub */
167   NULL,                                 /* next */
168   0,                                    /* static_pass_number */
169   TV_TREE_LOOP_UNSWITCH,                /* tv_id */
170   PROP_cfg,                             /* properties_required */
171   0,                                    /* properties_provided */
172   0,                                    /* properties_destroyed */
173   0,                                    /* todo_flags_start */
174   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
175   0                                     /* letter */
176 };
177
178 /* Loop autovectorization.  */
179
180 static unsigned int
181 tree_vectorize (void)
182 {
183   return vectorize_loops (current_loops);
184 }
185
186 static bool
187 gate_tree_vectorize (void)
188 {
189   return flag_tree_vectorize && current_loops;
190 }
191
192 struct tree_opt_pass pass_vectorize =
193 {
194   "vect",                               /* name */
195   gate_tree_vectorize,                  /* gate */
196   tree_vectorize,                       /* execute */
197   NULL,                                 /* sub */
198   NULL,                                 /* next */
199   0,                                    /* static_pass_number */
200   TV_TREE_VECTORIZATION,                /* tv_id */
201   PROP_cfg | PROP_ssa,                  /* properties_required */
202   0,                                    /* properties_provided */
203   0,                                    /* properties_destroyed */
204   TODO_verify_loops,                    /* todo_flags_start */
205   TODO_dump_func | TODO_update_ssa,     /* todo_flags_finish */
206   0                                     /* letter */
207 };
208
209 /* Loop nest optimizations.  */
210
211 static unsigned int
212 tree_linear_transform (void)
213 {
214   if (!current_loops)
215     return 0;
216
217   linear_transform_loops (current_loops);
218   return 0;
219 }
220
221 static bool
222 gate_tree_linear_transform (void)
223 {
224   return flag_tree_loop_linear != 0;
225 }
226
227 struct tree_opt_pass pass_linear_transform =
228 {
229   "ltrans",                             /* name */
230   gate_tree_linear_transform,           /* gate */
231   tree_linear_transform,                /* execute */
232   NULL,                                 /* sub */
233   NULL,                                 /* next */
234   0,                                    /* static_pass_number */
235   TV_TREE_LINEAR_TRANSFORM,             /* tv_id */
236   PROP_cfg | PROP_ssa,                  /* properties_required */
237   0,                                    /* properties_provided */
238   0,                                    /* properties_destroyed */
239   0,                                    /* todo_flags_start */
240   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
241   0                                     /* letter */    
242 };
243
244 /* Canonical induction variable creation pass.  */
245
246 static unsigned int
247 tree_ssa_loop_ivcanon (void)
248 {
249   if (!current_loops)
250     return 0;
251
252   return canonicalize_induction_variables (current_loops);
253 }
254
255 static bool
256 gate_tree_ssa_loop_ivcanon (void)
257 {
258   return flag_tree_loop_ivcanon != 0;
259 }
260
261 struct tree_opt_pass pass_iv_canon =
262 {
263   "ivcanon",                            /* name */
264   gate_tree_ssa_loop_ivcanon,           /* gate */
265   tree_ssa_loop_ivcanon,                /* execute */
266   NULL,                                 /* sub */
267   NULL,                                 /* next */
268   0,                                    /* static_pass_number */
269   TV_TREE_LOOP_IVCANON,                 /* tv_id */
270   PROP_cfg | PROP_ssa,                  /* properties_required */
271   0,                                    /* properties_provided */
272   0,                                    /* properties_destroyed */
273   0,                                    /* todo_flags_start */
274   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
275   0                                     /* letter */
276 };
277
278 /* Propagation of constants using scev.  */
279
280 static bool
281 gate_scev_const_prop (void)
282 {
283   return true;
284 }
285
286 struct tree_opt_pass pass_scev_cprop =
287 {
288   "sccp",                               /* name */
289   gate_scev_const_prop,                 /* gate */
290   scev_const_prop,                      /* execute */
291   NULL,                                 /* sub */
292   NULL,                                 /* next */
293   0,                                    /* static_pass_number */
294   TV_SCEV_CONST,                        /* tv_id */
295   PROP_cfg | PROP_ssa,                  /* properties_required */
296   0,                                    /* properties_provided */
297   0,                                    /* properties_destroyed */
298   0,                                    /* todo_flags_start */
299   TODO_dump_func | TODO_cleanup_cfg
300     | TODO_update_ssa_only_virtuals,
301                                         /* todo_flags_finish */
302   0                                     /* letter */
303 };
304
305 /* Remove empty loops.  */
306
307 static unsigned int
308 tree_ssa_empty_loop (void)
309 {
310   if (!current_loops)
311     return 0;
312
313   return remove_empty_loops (current_loops);
314 }
315
316 struct tree_opt_pass pass_empty_loop =
317 {
318   "empty",                              /* name */
319   NULL,                                 /* gate */
320   tree_ssa_empty_loop,                  /* execute */
321   NULL,                                 /* sub */
322   NULL,                                 /* next */
323   0,                                    /* static_pass_number */
324   TV_COMPLETE_UNROLL,                   /* tv_id */
325   PROP_cfg | PROP_ssa,                  /* properties_required */
326   0,                                    /* properties_provided */
327   0,                                    /* properties_destroyed */
328   0,                                    /* todo_flags_start */
329   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
330   0                                     /* letter */
331 };
332
333 /* Record bounds on numbers of iterations of loops.  */
334
335 static unsigned int
336 tree_ssa_loop_bounds (void)
337 {
338   if (!current_loops)
339     return 0;
340
341   estimate_numbers_of_iterations (current_loops);
342   scev_reset ();
343   return 0;
344 }
345
346 struct tree_opt_pass pass_record_bounds =
347 {
348   NULL,                                 /* name */
349   NULL,                                 /* gate */
350   tree_ssa_loop_bounds,                 /* execute */
351   NULL,                                 /* sub */
352   NULL,                                 /* next */
353   0,                                    /* static_pass_number */
354   TV_TREE_LOOP_BOUNDS,                  /* tv_id */
355   PROP_cfg | PROP_ssa,                  /* properties_required */
356   0,                                    /* properties_provided */
357   0,                                    /* properties_destroyed */
358   0,                                    /* todo_flags_start */
359   0,                                    /* todo_flags_finish */
360   0                                     /* letter */
361 };
362
363 /* Complete unrolling of loops.  */
364
365 static unsigned int
366 tree_complete_unroll (void)
367 {
368   if (!current_loops)
369     return 0;
370
371   return tree_unroll_loops_completely (current_loops,
372                                        flag_unroll_loops
373                                         || flag_peel_loops
374                                         || optimize >= 3);
375 }
376
377 static bool
378 gate_tree_complete_unroll (void)
379 {
380   return true;
381 }
382
383 struct tree_opt_pass pass_complete_unroll =
384 {
385   "cunroll",                            /* name */
386   gate_tree_complete_unroll,            /* gate */
387   tree_complete_unroll,                 /* execute */
388   NULL,                                 /* sub */
389   NULL,                                 /* next */
390   0,                                    /* static_pass_number */
391   TV_COMPLETE_UNROLL,                   /* tv_id */
392   PROP_cfg | PROP_ssa,                  /* properties_required */
393   0,                                    /* properties_provided */
394   0,                                    /* properties_destroyed */
395   0,                                    /* todo_flags_start */
396   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
397   0                                     /* letter */
398 };
399
400 /* Prefetching.  */
401
402 static unsigned int
403 tree_ssa_loop_prefetch (void)
404 {
405   if (!current_loops)
406     return 0;
407
408   return tree_ssa_prefetch_arrays (current_loops);
409 }
410
411 static bool
412 gate_tree_ssa_loop_prefetch (void)
413 {
414   return flag_prefetch_loop_arrays != 0;
415 }
416
417 struct tree_opt_pass pass_loop_prefetch =
418 {
419   "aprefetch",                          /* name */
420   gate_tree_ssa_loop_prefetch,          /* gate */
421   tree_ssa_loop_prefetch,               /* execute */
422   NULL,                                 /* sub */
423   NULL,                                 /* next */
424   0,                                    /* static_pass_number */
425   TV_TREE_PREFETCH,                     /* tv_id */
426   PROP_cfg | PROP_ssa,                  /* properties_required */
427   0,                                    /* properties_provided */
428   0,                                    /* properties_destroyed */
429   0,                                    /* todo_flags_start */
430   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
431   0                                     /* letter */
432 };
433
434 /* Induction variable optimizations.  */
435
436 static unsigned int
437 tree_ssa_loop_ivopts (void)
438 {
439   if (!current_loops)
440     return 0;
441
442   tree_ssa_iv_optimize (current_loops);
443   return 0;
444 }
445
446 static bool
447 gate_tree_ssa_loop_ivopts (void)
448 {
449   return flag_ivopts != 0;
450 }
451
452 struct tree_opt_pass pass_iv_optimize =
453 {
454   "ivopts",                             /* name */
455   gate_tree_ssa_loop_ivopts,            /* gate */
456   tree_ssa_loop_ivopts,                 /* execute */
457   NULL,                                 /* sub */
458   NULL,                                 /* next */
459   0,                                    /* static_pass_number */
460   TV_TREE_LOOP_IVOPTS,                  /* tv_id */
461   PROP_cfg | PROP_ssa,                  /* properties_required */
462   0,                                    /* properties_provided */
463   0,                                    /* properties_destroyed */
464   0,                                    /* todo_flags_start */
465   TODO_dump_func
466   | TODO_verify_loops
467   | TODO_update_ssa,                    /* todo_flags_finish */
468   0                                     /* letter */
469 };
470
471 /* Loop optimizer finalization.  */
472
473 static unsigned int
474 tree_ssa_loop_done (void)
475 {
476   if (!current_loops)
477     return 0;
478
479   free_numbers_of_iterations_estimates (current_loops);
480   scev_finalize ();
481   loop_optimizer_finalize ();
482   return 0;
483 }
484   
485 struct tree_opt_pass pass_tree_loop_done = 
486 {
487   "loopdone",                           /* name */
488   NULL,                                 /* gate */
489   tree_ssa_loop_done,                   /* execute */
490   NULL,                                 /* sub */
491   NULL,                                 /* next */
492   0,                                    /* static_pass_number */
493   TV_TREE_LOOP_FINI,                    /* tv_id */
494   PROP_cfg,                             /* properties_required */
495   0,                                    /* properties_provided */
496   0,                                    /* properties_destroyed */
497   0,                                    /* todo_flags_start */
498   TODO_cleanup_cfg | TODO_dump_func,    /* todo_flags_finish */
499   0                                     /* letter */
500 };