OSDN Git Service

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