OSDN Git Service

2ea58f690430adf85f6d8fe2d580ad7a0d3f2e07
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-loop.c
1 /* Loop optimizations over tree-ssa.
2    Copyright (C) 2003, 2005, 2006, 2007 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 3, 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 COPYING3.  If not see
18 <http://www.gnu.org/licenses/>.  */
19
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "tree.h"
25 #include "rtl.h"
26 #include "tm_p.h"
27 #include "hard-reg-set.h"
28 #include "basic-block.h"
29 #include "output.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #include "tree-dump.h"
33 #include "tree-pass.h"
34 #include "timevar.h"
35 #include "cfgloop.h"
36 #include "flags.h"
37 #include "tree-inline.h"
38 #include "tree-scalar-evolution.h"
39
40 /* The loop superpass.  */
41
42 static bool
43 gate_tree_loop (void)
44 {
45   return flag_tree_loop_optimize != 0;
46 }
47
48 struct gimple_opt_pass pass_tree_loop = 
49 {
50  {
51   GIMPLE_PASS,
52   "loop",                               /* name */
53   gate_tree_loop,                       /* gate */
54   NULL,                                 /* execute */
55   NULL,                                 /* sub */
56   NULL,                                 /* next */
57   0,                                    /* static_pass_number */
58   TV_TREE_LOOP,                         /* tv_id */
59   PROP_cfg,                             /* properties_required */
60   0,                                    /* properties_provided */
61   0,                                    /* properties_destroyed */
62   TODO_ggc_collect,                     /* todo_flags_start */
63   TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect   /* todo_flags_finish */
64  }
65 };
66
67 /* Loop optimizer initialization.  */
68
69 static unsigned int
70 tree_ssa_loop_init (void)
71 {
72   loop_optimizer_init (LOOPS_NORMAL
73                        | LOOPS_HAVE_RECORDED_EXITS);
74   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
75
76   if (number_of_loops () <= 1)
77     return 0;
78
79   scev_initialize ();
80   return 0;
81 }
82   
83 struct gimple_opt_pass pass_tree_loop_init = 
84 {
85  {
86   GIMPLE_PASS,
87   "loopinit",                           /* name */
88   NULL,                                 /* gate */
89   tree_ssa_loop_init,                   /* execute */
90   NULL,                                 /* sub */
91   NULL,                                 /* next */
92   0,                                    /* static_pass_number */
93   TV_TREE_LOOP_INIT,                    /* tv_id */
94   PROP_cfg,                             /* properties_required */
95   0,                                    /* properties_provided */
96   0,                                    /* properties_destroyed */
97   0,                                    /* todo_flags_start */
98   TODO_dump_func | TODO_verify_loops    /* todo_flags_finish */
99  }
100 };
101
102 /* Loop invariant motion pass.  */
103
104 static unsigned int
105 tree_ssa_loop_im (void)
106 {
107   if (number_of_loops () <= 1)
108     return 0;
109
110   tree_ssa_lim ();
111   return 0;
112 }
113
114 static bool
115 gate_tree_ssa_loop_im (void)
116 {
117   return flag_tree_loop_im != 0;
118 }
119
120 struct gimple_opt_pass pass_lim = 
121 {
122  {
123   GIMPLE_PASS,
124   "lim",                                /* name */
125   gate_tree_ssa_loop_im,                /* gate */
126   tree_ssa_loop_im,                     /* execute */
127   NULL,                                 /* sub */
128   NULL,                                 /* next */
129   0,                                    /* static_pass_number */
130   TV_LIM,                               /* tv_id */
131   PROP_cfg,                             /* properties_required */
132   0,                                    /* properties_provided */
133   0,                                    /* properties_destroyed */
134   0,                                    /* todo_flags_start */
135   TODO_dump_func | TODO_verify_loops    /* todo_flags_finish */
136  }
137 };
138
139 /* Loop unswitching pass.  */
140
141 static unsigned int
142 tree_ssa_loop_unswitch (void)
143 {
144   if (number_of_loops () <= 1)
145     return 0;
146
147   return tree_ssa_unswitch_loops ();
148 }
149
150 static bool
151 gate_tree_ssa_loop_unswitch (void)
152 {
153   return flag_unswitch_loops != 0;
154 }
155
156 struct gimple_opt_pass pass_tree_unswitch = 
157 {
158  {
159   GIMPLE_PASS,
160   "unswitch",                           /* name */
161   gate_tree_ssa_loop_unswitch,          /* gate */
162   tree_ssa_loop_unswitch,               /* execute */
163   NULL,                                 /* sub */
164   NULL,                                 /* next */
165   0,                                    /* static_pass_number */
166   TV_TREE_LOOP_UNSWITCH,                /* tv_id */
167   PROP_cfg,                             /* properties_required */
168   0,                                    /* properties_provided */
169   0,                                    /* properties_destroyed */
170   0,                                    /* todo_flags_start */
171   TODO_ggc_collect | TODO_dump_func
172     | TODO_verify_loops                 /* todo_flags_finish */
173  }
174 };
175
176 /* Predictive commoning.  */
177
178 static unsigned
179 run_tree_predictive_commoning (void)
180 {
181   if (!current_loops)
182     return 0;
183
184   tree_predictive_commoning ();
185   return 0;
186 }
187
188 static bool
189 gate_tree_predictive_commoning (void)
190 {
191   return flag_predictive_commoning != 0;
192 }
193
194 struct gimple_opt_pass pass_predcom = 
195 {
196  {
197   GIMPLE_PASS,
198   "pcom",                               /* name */
199   gate_tree_predictive_commoning,       /* gate */
200   run_tree_predictive_commoning,        /* execute */
201   NULL,                                 /* sub */
202   NULL,                                 /* next */
203   0,                                    /* static_pass_number */
204   TV_PREDCOM,                           /* tv_id */
205   PROP_cfg,                             /* properties_required */
206   0,                                    /* properties_provided */
207   0,                                    /* properties_destroyed */
208   0,                                    /* todo_flags_start */
209   TODO_dump_func | TODO_verify_loops
210     | TODO_update_ssa_only_virtuals     /* todo_flags_finish */
211  }
212 };
213
214 /* Loop autovectorization.  */
215
216 static unsigned int
217 tree_vectorize (void)
218 {
219   if (number_of_loops () <= 1)
220     return 0;
221
222   return vectorize_loops ();
223 }
224
225 static bool
226 gate_tree_vectorize (void)
227 {
228   return flag_tree_vectorize;
229 }
230
231 struct gimple_opt_pass pass_vectorize =
232 {
233  {
234   GIMPLE_PASS,
235   "vect",                               /* name */
236   gate_tree_vectorize,                  /* gate */
237   tree_vectorize,                       /* execute */
238   NULL,                                 /* sub */
239   NULL,                                 /* next */
240   0,                                    /* static_pass_number */
241   TV_TREE_VECTORIZATION,                /* tv_id */
242   PROP_cfg | PROP_ssa,                  /* properties_required */
243   0,                                    /* properties_provided */
244   0,                                    /* properties_destroyed */
245   TODO_verify_loops,                    /* todo_flags_start */
246   TODO_dump_func | TODO_update_ssa
247     | TODO_ggc_collect                  /* todo_flags_finish */
248  }
249 };
250
251 /* Loop nest optimizations.  */
252
253 static unsigned int
254 tree_linear_transform (void)
255 {
256   if (number_of_loops () <= 1)
257     return 0;
258
259   linear_transform_loops ();
260   return 0;
261 }
262
263 static bool
264 gate_tree_linear_transform (void)
265 {
266   return flag_tree_loop_linear != 0;
267 }
268
269 struct gimple_opt_pass pass_linear_transform =
270 {
271  {
272   GIMPLE_PASS,
273   "ltrans",                             /* name */
274   gate_tree_linear_transform,           /* gate */
275   tree_linear_transform,                /* execute */
276   NULL,                                 /* sub */
277   NULL,                                 /* next */
278   0,                                    /* static_pass_number */
279   TV_TREE_LINEAR_TRANSFORM,             /* 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
285     | TODO_update_ssa_only_virtuals
286     | TODO_ggc_collect                  /* todo_flags_finish */
287  }
288 };
289
290 /* GRAPHITE optimizations.  */
291
292 static unsigned int
293 graphite_transforms (void)
294 {
295   if (!current_loops)
296     return 0;
297
298   graphite_transform_loops ();
299
300   return 0;
301 }
302
303 static bool
304 gate_graphite_transforms (void)
305 {
306   /* Enable -fgraphite pass if any one of the graphite optimization flags 
307      is turned on.  */
308   if (flag_loop_block || flag_loop_interchange || flag_loop_strip_mine
309       || flag_graphite_identity)
310     flag_graphite = 1;
311
312   return flag_graphite != 0;
313 }
314
315 struct gimple_opt_pass pass_graphite_transforms =
316 {
317  {
318   GIMPLE_PASS,
319   "graphite",                           /* name */
320   gate_graphite_transforms,             /* gate */
321   graphite_transforms,                  /* execute */
322   NULL,                                 /* sub */
323   NULL,                                 /* next */
324   0,                                    /* static_pass_number */
325   TV_GRAPHITE_TRANSFORMS,               /* tv_id */
326   PROP_cfg | PROP_ssa,                  /* properties_required */
327   0,                                    /* properties_provided */
328   0,                                    /* properties_destroyed */
329   0,                                    /* todo_flags_start */
330   TODO_verify_loops                     /* todo_flags_finish */
331  }
332 };
333
334 /* Check the correctness of the data dependence analyzers.  */
335
336 static unsigned int
337 check_data_deps (void)
338 {
339   if (number_of_loops () <= 1)
340     return 0;
341
342   tree_check_data_deps ();
343   return 0;
344 }
345
346 static bool
347 gate_check_data_deps (void)
348 {
349   return flag_check_data_deps != 0;
350 }
351
352 struct gimple_opt_pass pass_check_data_deps =
353 {
354  {
355   GIMPLE_PASS,
356   "ckdd",                               /* name */
357   gate_check_data_deps,                 /* gate */
358   check_data_deps,                      /* execute */
359   NULL,                                 /* sub */
360   NULL,                                 /* next */
361   0,                                    /* static_pass_number */
362   TV_CHECK_DATA_DEPS,                   /* tv_id */
363   PROP_cfg | PROP_ssa,                  /* properties_required */
364   0,                                    /* properties_provided */
365   0,                                    /* properties_destroyed */
366   0,                                    /* todo_flags_start */
367   TODO_dump_func                        /* todo_flags_finish */
368  }
369 };
370
371 /* Canonical induction variable creation pass.  */
372
373 static unsigned int
374 tree_ssa_loop_ivcanon (void)
375 {
376   if (number_of_loops () <= 1)
377     return 0;
378
379   return canonicalize_induction_variables ();
380 }
381
382 static bool
383 gate_tree_ssa_loop_ivcanon (void)
384 {
385   return flag_tree_loop_ivcanon != 0;
386 }
387
388 struct gimple_opt_pass pass_iv_canon =
389 {
390  {
391   GIMPLE_PASS,
392   "ivcanon",                            /* name */
393   gate_tree_ssa_loop_ivcanon,           /* gate */
394   tree_ssa_loop_ivcanon,                /* execute */
395   NULL,                                 /* sub */
396   NULL,                                 /* next */
397   0,                                    /* static_pass_number */
398   TV_TREE_LOOP_IVCANON,                 /* tv_id */
399   PROP_cfg | PROP_ssa,                  /* properties_required */
400   0,                                    /* properties_provided */
401   0,                                    /* properties_destroyed */
402   0,                                    /* todo_flags_start */
403   TODO_dump_func | TODO_verify_loops    /* todo_flags_finish */
404  }
405 };
406
407 /* Propagation of constants using scev.  */
408
409 static bool
410 gate_scev_const_prop (void)
411 {
412   return flag_tree_scev_cprop;
413 }
414
415 struct gimple_opt_pass pass_scev_cprop =
416 {
417  {
418   GIMPLE_PASS,
419   "sccp",                               /* name */
420   gate_scev_const_prop,                 /* gate */
421   scev_const_prop,                      /* execute */
422   NULL,                                 /* sub */
423   NULL,                                 /* next */
424   0,                                    /* static_pass_number */
425   TV_SCEV_CONST,                        /* 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_cleanup_cfg
431     | TODO_update_ssa_only_virtuals
432                                         /* todo_flags_finish */
433  }
434 };
435
436 /* Remove empty loops.  */
437
438 static unsigned int
439 tree_ssa_empty_loop (void)
440 {
441   if (number_of_loops () <= 1)
442     return 0;
443
444   return remove_empty_loops ();
445 }
446
447 struct gimple_opt_pass pass_empty_loop =
448 {
449  {
450   GIMPLE_PASS,
451   "empty",                              /* name */
452   NULL,                                 /* gate */
453   tree_ssa_empty_loop,                  /* execute */
454   NULL,                                 /* sub */
455   NULL,                                 /* next */
456   0,                                    /* static_pass_number */
457   TV_COMPLETE_UNROLL,                   /* tv_id */
458   PROP_cfg | PROP_ssa,                  /* properties_required */
459   0,                                    /* properties_provided */
460   0,                                    /* properties_destroyed */
461   0,                                    /* todo_flags_start */
462   TODO_dump_func | TODO_verify_loops 
463     | TODO_ggc_collect                  /* todo_flags_finish */
464  }
465 };
466
467 /* Record bounds on numbers of iterations of loops.  */
468
469 static unsigned int
470 tree_ssa_loop_bounds (void)
471 {
472   if (number_of_loops () <= 1)
473     return 0;
474
475   estimate_numbers_of_iterations ();
476   scev_reset ();
477   return 0;
478 }
479
480 struct gimple_opt_pass pass_record_bounds =
481 {
482  {
483   GIMPLE_PASS,
484   NULL,                                 /* name */
485   NULL,                                 /* gate */
486   tree_ssa_loop_bounds,                 /* execute */
487   NULL,                                 /* sub */
488   NULL,                                 /* next */
489   0,                                    /* static_pass_number */
490   TV_TREE_LOOP_BOUNDS,                  /* tv_id */
491   PROP_cfg | PROP_ssa,                  /* properties_required */
492   0,                                    /* properties_provided */
493   0,                                    /* properties_destroyed */
494   0,                                    /* todo_flags_start */
495   0                                     /* todo_flags_finish */
496  }
497 };
498
499 /* Complete unrolling of loops.  */
500
501 static unsigned int
502 tree_complete_unroll (void)
503 {
504   if (number_of_loops () <= 1)
505     return 0;
506
507   return tree_unroll_loops_completely (flag_unroll_loops
508                                        || flag_peel_loops
509                                        || optimize >= 3, true);
510 }
511
512 static bool
513 gate_tree_complete_unroll (void)
514 {
515   return true;
516 }
517
518 struct gimple_opt_pass pass_complete_unroll =
519 {
520  {
521   GIMPLE_PASS,
522   "cunroll",                            /* name */
523   gate_tree_complete_unroll,            /* gate */
524   tree_complete_unroll,                 /* execute */
525   NULL,                                 /* sub */
526   NULL,                                 /* next */
527   0,                                    /* static_pass_number */
528   TV_COMPLETE_UNROLL,                   /* tv_id */
529   PROP_cfg | PROP_ssa,                  /* properties_required */
530   0,                                    /* properties_provided */
531   0,                                    /* properties_destroyed */
532   0,                                    /* todo_flags_start */
533   TODO_dump_func | TODO_verify_loops
534     | TODO_ggc_collect                  /* todo_flags_finish */
535  }
536 };
537
538 /* Complete unrolling of inner loops.  */
539
540 static unsigned int
541 tree_complete_unroll_inner (void)
542 {
543   unsigned ret = 0;
544
545   loop_optimizer_init (LOOPS_NORMAL
546                        | LOOPS_HAVE_RECORDED_EXITS);
547   if (number_of_loops () > 1)
548     {
549       scev_initialize ();
550       ret = tree_unroll_loops_completely (optimize >= 3, false);
551       free_numbers_of_iterations_estimates ();
552       scev_finalize ();
553     }
554   loop_optimizer_finalize ();
555
556   return ret;
557 }
558
559 static bool
560 gate_tree_complete_unroll_inner (void)
561 {
562   return optimize >= 2;
563 }
564
565 struct gimple_opt_pass pass_complete_unrolli =
566 {
567  {
568   GIMPLE_PASS,
569   "cunrolli",                           /* name */
570   gate_tree_complete_unroll_inner,      /* gate */
571   tree_complete_unroll_inner,           /* execute */
572   NULL,                                 /* sub */
573   NULL,                                 /* next */
574   0,                                    /* static_pass_number */
575   TV_COMPLETE_UNROLL,                   /* tv_id */
576   PROP_cfg | PROP_ssa,                  /* properties_required */
577   0,                                    /* properties_provided */
578   0,                                    /* properties_destroyed */
579   0,                                    /* todo_flags_start */
580   TODO_dump_func | TODO_verify_loops
581     | TODO_ggc_collect                  /* todo_flags_finish */
582  }
583 };
584
585 /* Parallelization.  */
586
587 static bool
588 gate_tree_parallelize_loops (void)
589 {
590   return flag_tree_parallelize_loops > 1;
591 }
592
593 static unsigned
594 tree_parallelize_loops (void)
595 {
596   if (number_of_loops () <= 1)
597     return 0;
598
599   if (parallelize_loops ())
600     return TODO_cleanup_cfg | TODO_rebuild_alias;
601   return 0;
602 }
603
604 struct gimple_opt_pass pass_parallelize_loops =
605 {
606  {
607   GIMPLE_PASS,
608   "parloops",                           /* name */
609   gate_tree_parallelize_loops,          /* gate */
610   tree_parallelize_loops,               /* execute */
611   NULL,                                 /* sub */
612   NULL,                                 /* next */
613   0,                                    /* static_pass_number */
614   TV_TREE_PARALLELIZE_LOOPS,            /* tv_id */
615   PROP_cfg | PROP_ssa,                  /* properties_required */
616   0,                                    /* properties_provided */
617   0,                                    /* properties_destroyed */
618   0,                                    /* todo_flags_start */
619   TODO_dump_func | TODO_verify_loops    /* todo_flags_finish */
620  }
621 };
622
623 /* Prefetching.  */
624
625 static unsigned int
626 tree_ssa_loop_prefetch (void)
627 {
628   if (number_of_loops () <= 1)
629     return 0;
630
631   return tree_ssa_prefetch_arrays ();
632 }
633
634 static bool
635 gate_tree_ssa_loop_prefetch (void)
636 {
637   return flag_prefetch_loop_arrays != 0;
638 }
639
640 struct gimple_opt_pass pass_loop_prefetch =
641 {
642  {
643   GIMPLE_PASS,
644   "aprefetch",                          /* name */
645   gate_tree_ssa_loop_prefetch,          /* gate */
646   tree_ssa_loop_prefetch,               /* execute */
647   NULL,                                 /* sub */
648   NULL,                                 /* next */
649   0,                                    /* static_pass_number */
650   TV_TREE_PREFETCH,                     /* tv_id */
651   PROP_cfg | PROP_ssa,                  /* properties_required */
652   0,                                    /* properties_provided */
653   0,                                    /* properties_destroyed */
654   0,                                    /* todo_flags_start */
655   TODO_dump_func | TODO_verify_loops    /* todo_flags_finish */
656  }
657 };
658
659 /* Induction variable optimizations.  */
660
661 static unsigned int
662 tree_ssa_loop_ivopts (void)
663 {
664   if (number_of_loops () <= 1)
665     return 0;
666
667   tree_ssa_iv_optimize ();
668   return 0;
669 }
670
671 static bool
672 gate_tree_ssa_loop_ivopts (void)
673 {
674   return flag_ivopts != 0;
675 }
676
677 struct gimple_opt_pass pass_iv_optimize =
678 {
679  {
680   GIMPLE_PASS,
681   "ivopts",                             /* name */
682   gate_tree_ssa_loop_ivopts,            /* gate */
683   tree_ssa_loop_ivopts,                 /* execute */
684   NULL,                                 /* sub */
685   NULL,                                 /* next */
686   0,                                    /* static_pass_number */
687   TV_TREE_LOOP_IVOPTS,                  /* tv_id */
688   PROP_cfg | PROP_ssa,                  /* properties_required */
689   0,                                    /* properties_provided */
690   0,                                    /* properties_destroyed */
691   0,                                    /* todo_flags_start */
692   TODO_dump_func | TODO_verify_loops
693   | TODO_update_ssa | TODO_ggc_collect  /* todo_flags_finish */
694  }
695 };
696
697 /* Loop optimizer finalization.  */
698
699 static unsigned int
700 tree_ssa_loop_done (void)
701 {
702   free_numbers_of_iterations_estimates ();
703   scev_finalize ();
704   loop_optimizer_finalize ();
705   return 0;
706 }
707   
708 struct gimple_opt_pass pass_tree_loop_done = 
709 {
710  {
711   GIMPLE_PASS,
712   "loopdone",                           /* name */
713   NULL,                                 /* gate */
714   tree_ssa_loop_done,                   /* execute */
715   NULL,                                 /* sub */
716   NULL,                                 /* next */
717   0,                                    /* static_pass_number */
718   TV_TREE_LOOP_FINI,                    /* tv_id */
719   PROP_cfg,                             /* properties_required */
720   0,                                    /* properties_provided */
721   0,                                    /* properties_destroyed */
722   0,                                    /* todo_flags_start */
723   TODO_cleanup_cfg | TODO_dump_func     /* todo_flags_finish */
724  }
725 };