OSDN Git Service

* tree-vrp.c (execute_vrp): Do not pass loops structure through
[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 ();
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 ();
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 ();
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 ();
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 ();
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 ();
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 ();
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 ();
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 (flag_unroll_loops
372                                        || flag_peel_loops
373                                        || optimize >= 3);
374 }
375
376 static bool
377 gate_tree_complete_unroll (void)
378 {
379   return true;
380 }
381
382 struct tree_opt_pass pass_complete_unroll =
383 {
384   "cunroll",                            /* name */
385   gate_tree_complete_unroll,            /* gate */
386   tree_complete_unroll,                 /* execute */
387   NULL,                                 /* sub */
388   NULL,                                 /* next */
389   0,                                    /* static_pass_number */
390   TV_COMPLETE_UNROLL,                   /* tv_id */
391   PROP_cfg | PROP_ssa,                  /* properties_required */
392   0,                                    /* properties_provided */
393   0,                                    /* properties_destroyed */
394   0,                                    /* todo_flags_start */
395   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
396   0                                     /* letter */
397 };
398
399 /* Prefetching.  */
400
401 static unsigned int
402 tree_ssa_loop_prefetch (void)
403 {
404   if (!current_loops)
405     return 0;
406
407   return tree_ssa_prefetch_arrays ();
408 }
409
410 static bool
411 gate_tree_ssa_loop_prefetch (void)
412 {
413   return flag_prefetch_loop_arrays != 0;
414 }
415
416 struct tree_opt_pass pass_loop_prefetch =
417 {
418   "aprefetch",                          /* name */
419   gate_tree_ssa_loop_prefetch,          /* gate */
420   tree_ssa_loop_prefetch,               /* execute */
421   NULL,                                 /* sub */
422   NULL,                                 /* next */
423   0,                                    /* static_pass_number */
424   TV_TREE_PREFETCH,                     /* tv_id */
425   PROP_cfg | PROP_ssa,                  /* properties_required */
426   0,                                    /* properties_provided */
427   0,                                    /* properties_destroyed */
428   0,                                    /* todo_flags_start */
429   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
430   0                                     /* letter */
431 };
432
433 /* Induction variable optimizations.  */
434
435 static unsigned int
436 tree_ssa_loop_ivopts (void)
437 {
438   if (!current_loops)
439     return 0;
440
441   tree_ssa_iv_optimize ();
442   return 0;
443 }
444
445 static bool
446 gate_tree_ssa_loop_ivopts (void)
447 {
448   return flag_ivopts != 0;
449 }
450
451 struct tree_opt_pass pass_iv_optimize =
452 {
453   "ivopts",                             /* name */
454   gate_tree_ssa_loop_ivopts,            /* gate */
455   tree_ssa_loop_ivopts,                 /* execute */
456   NULL,                                 /* sub */
457   NULL,                                 /* next */
458   0,                                    /* static_pass_number */
459   TV_TREE_LOOP_IVOPTS,                  /* tv_id */
460   PROP_cfg | PROP_ssa,                  /* properties_required */
461   0,                                    /* properties_provided */
462   0,                                    /* properties_destroyed */
463   0,                                    /* todo_flags_start */
464   TODO_dump_func
465   | TODO_verify_loops
466   | TODO_update_ssa,                    /* todo_flags_finish */
467   0                                     /* letter */
468 };
469
470 /* Loop optimizer finalization.  */
471
472 static unsigned int
473 tree_ssa_loop_done (void)
474 {
475   if (!current_loops)
476     return 0;
477
478   free_numbers_of_iterations_estimates ();
479   scev_finalize ();
480   loop_optimizer_finalize ();
481   return 0;
482 }
483   
484 struct tree_opt_pass pass_tree_loop_done = 
485 {
486   "loopdone",                           /* name */
487   NULL,                                 /* gate */
488   tree_ssa_loop_done,                   /* execute */
489   NULL,                                 /* sub */
490   NULL,                                 /* next */
491   0,                                    /* static_pass_number */
492   TV_TREE_LOOP_FINI,                    /* tv_id */
493   PROP_cfg,                             /* properties_required */
494   0,                                    /* properties_provided */
495   0,                                    /* properties_destroyed */
496   0,                                    /* todo_flags_start */
497   TODO_cleanup_cfg | TODO_dump_func,    /* todo_flags_finish */
498   0                                     /* letter */
499 };