OSDN Git Service

51fc07c558ae042eb5411c31d14d67235c8e3b74
[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 = 1;
310
311   return flag_graphite != 0;
312 }
313
314 struct gimple_opt_pass pass_graphite_transforms =
315 {
316  {
317   GIMPLE_PASS,
318   "graphite",                           /* name */
319   gate_graphite_transforms,             /* gate */
320   graphite_transforms,                  /* execute */
321   NULL,                                 /* sub */
322   NULL,                                 /* next */
323   0,                                    /* static_pass_number */
324   TV_GRAPHITE_TRANSFORMS,               /* tv_id */
325   PROP_cfg | PROP_ssa,                  /* properties_required */
326   0,                                    /* properties_provided */
327   0,                                    /* properties_destroyed */
328   0,                                    /* todo_flags_start */
329   TODO_verify_loops                     /* todo_flags_finish */
330  }
331 };
332
333 /* Check the correctness of the data dependence analyzers.  */
334
335 static unsigned int
336 check_data_deps (void)
337 {
338   if (number_of_loops () <= 1)
339     return 0;
340
341   tree_check_data_deps ();
342   return 0;
343 }
344
345 static bool
346 gate_check_data_deps (void)
347 {
348   return flag_check_data_deps != 0;
349 }
350
351 struct gimple_opt_pass pass_check_data_deps =
352 {
353  {
354   GIMPLE_PASS,
355   "ckdd",                               /* name */
356   gate_check_data_deps,                 /* gate */
357   check_data_deps,                      /* execute */
358   NULL,                                 /* sub */
359   NULL,                                 /* next */
360   0,                                    /* static_pass_number */
361   TV_CHECK_DATA_DEPS,                   /* tv_id */
362   PROP_cfg | PROP_ssa,                  /* properties_required */
363   0,                                    /* properties_provided */
364   0,                                    /* properties_destroyed */
365   0,                                    /* todo_flags_start */
366   TODO_dump_func                        /* todo_flags_finish */
367  }
368 };
369
370 /* Canonical induction variable creation pass.  */
371
372 static unsigned int
373 tree_ssa_loop_ivcanon (void)
374 {
375   if (number_of_loops () <= 1)
376     return 0;
377
378   return canonicalize_induction_variables ();
379 }
380
381 static bool
382 gate_tree_ssa_loop_ivcanon (void)
383 {
384   return flag_tree_loop_ivcanon != 0;
385 }
386
387 struct gimple_opt_pass pass_iv_canon =
388 {
389  {
390   GIMPLE_PASS,
391   "ivcanon",                            /* name */
392   gate_tree_ssa_loop_ivcanon,           /* gate */
393   tree_ssa_loop_ivcanon,                /* execute */
394   NULL,                                 /* sub */
395   NULL,                                 /* next */
396   0,                                    /* static_pass_number */
397   TV_TREE_LOOP_IVCANON,                 /* tv_id */
398   PROP_cfg | PROP_ssa,                  /* properties_required */
399   0,                                    /* properties_provided */
400   0,                                    /* properties_destroyed */
401   0,                                    /* todo_flags_start */
402   TODO_dump_func | TODO_verify_loops    /* todo_flags_finish */
403  }
404 };
405
406 /* Propagation of constants using scev.  */
407
408 static bool
409 gate_scev_const_prop (void)
410 {
411   return flag_tree_scev_cprop;
412 }
413
414 struct gimple_opt_pass pass_scev_cprop =
415 {
416  {
417   GIMPLE_PASS,
418   "sccp",                               /* name */
419   gate_scev_const_prop,                 /* gate */
420   scev_const_prop,                      /* execute */
421   NULL,                                 /* sub */
422   NULL,                                 /* next */
423   0,                                    /* static_pass_number */
424   TV_SCEV_CONST,                        /* 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_cleanup_cfg
430     | TODO_update_ssa_only_virtuals
431                                         /* todo_flags_finish */
432  }
433 };
434
435 /* Remove empty loops.  */
436
437 static unsigned int
438 tree_ssa_empty_loop (void)
439 {
440   if (number_of_loops () <= 1)
441     return 0;
442
443   return remove_empty_loops ();
444 }
445
446 struct gimple_opt_pass pass_empty_loop =
447 {
448  {
449   GIMPLE_PASS,
450   "empty",                              /* name */
451   NULL,                                 /* gate */
452   tree_ssa_empty_loop,                  /* execute */
453   NULL,                                 /* sub */
454   NULL,                                 /* next */
455   0,                                    /* static_pass_number */
456   TV_COMPLETE_UNROLL,                   /* tv_id */
457   PROP_cfg | PROP_ssa,                  /* properties_required */
458   0,                                    /* properties_provided */
459   0,                                    /* properties_destroyed */
460   0,                                    /* todo_flags_start */
461   TODO_dump_func | TODO_verify_loops 
462     | TODO_ggc_collect                  /* todo_flags_finish */
463  }
464 };
465
466 /* Record bounds on numbers of iterations of loops.  */
467
468 static unsigned int
469 tree_ssa_loop_bounds (void)
470 {
471   if (number_of_loops () <= 1)
472     return 0;
473
474   estimate_numbers_of_iterations ();
475   scev_reset ();
476   return 0;
477 }
478
479 struct gimple_opt_pass pass_record_bounds =
480 {
481  {
482   GIMPLE_PASS,
483   NULL,                                 /* name */
484   NULL,                                 /* gate */
485   tree_ssa_loop_bounds,                 /* execute */
486   NULL,                                 /* sub */
487   NULL,                                 /* next */
488   0,                                    /* static_pass_number */
489   TV_TREE_LOOP_BOUNDS,                  /* tv_id */
490   PROP_cfg | PROP_ssa,                  /* properties_required */
491   0,                                    /* properties_provided */
492   0,                                    /* properties_destroyed */
493   0,                                    /* todo_flags_start */
494   0                                     /* todo_flags_finish */
495  }
496 };
497
498 /* Complete unrolling of loops.  */
499
500 static unsigned int
501 tree_complete_unroll (void)
502 {
503   if (number_of_loops () <= 1)
504     return 0;
505
506   return tree_unroll_loops_completely (flag_unroll_loops
507                                        || flag_peel_loops
508                                        || optimize >= 3, true);
509 }
510
511 static bool
512 gate_tree_complete_unroll (void)
513 {
514   return true;
515 }
516
517 struct gimple_opt_pass pass_complete_unroll =
518 {
519  {
520   GIMPLE_PASS,
521   "cunroll",                            /* name */
522   gate_tree_complete_unroll,            /* gate */
523   tree_complete_unroll,                 /* execute */
524   NULL,                                 /* sub */
525   NULL,                                 /* next */
526   0,                                    /* static_pass_number */
527   TV_COMPLETE_UNROLL,                   /* tv_id */
528   PROP_cfg | PROP_ssa,                  /* properties_required */
529   0,                                    /* properties_provided */
530   0,                                    /* properties_destroyed */
531   0,                                    /* todo_flags_start */
532   TODO_dump_func | TODO_verify_loops
533     | TODO_ggc_collect                  /* todo_flags_finish */
534  }
535 };
536
537 /* Complete unrolling of inner loops.  */
538
539 static unsigned int
540 tree_complete_unroll_inner (void)
541 {
542   unsigned ret = 0;
543
544   loop_optimizer_init (LOOPS_NORMAL
545                        | LOOPS_HAVE_RECORDED_EXITS);
546   if (number_of_loops () > 1)
547     {
548       scev_initialize ();
549       ret = tree_unroll_loops_completely (optimize >= 3, false);
550       free_numbers_of_iterations_estimates ();
551       scev_finalize ();
552     }
553   loop_optimizer_finalize ();
554
555   return ret;
556 }
557
558 static bool
559 gate_tree_complete_unroll_inner (void)
560 {
561   return optimize >= 2;
562 }
563
564 struct gimple_opt_pass pass_complete_unrolli =
565 {
566  {
567   GIMPLE_PASS,
568   "cunrolli",                           /* name */
569   gate_tree_complete_unroll_inner,      /* gate */
570   tree_complete_unroll_inner,           /* execute */
571   NULL,                                 /* sub */
572   NULL,                                 /* next */
573   0,                                    /* static_pass_number */
574   TV_COMPLETE_UNROLL,                   /* tv_id */
575   PROP_cfg | PROP_ssa,                  /* properties_required */
576   0,                                    /* properties_provided */
577   0,                                    /* properties_destroyed */
578   0,                                    /* todo_flags_start */
579   TODO_dump_func | TODO_verify_loops
580     | TODO_ggc_collect                  /* todo_flags_finish */
581  }
582 };
583
584 /* Parallelization.  */
585
586 static bool
587 gate_tree_parallelize_loops (void)
588 {
589   return flag_tree_parallelize_loops > 1;
590 }
591
592 static unsigned
593 tree_parallelize_loops (void)
594 {
595   if (number_of_loops () <= 1)
596     return 0;
597
598   if (parallelize_loops ())
599     return TODO_cleanup_cfg | TODO_rebuild_alias;
600   return 0;
601 }
602
603 struct gimple_opt_pass pass_parallelize_loops =
604 {
605  {
606   GIMPLE_PASS,
607   "parloops",                           /* name */
608   gate_tree_parallelize_loops,          /* gate */
609   tree_parallelize_loops,               /* execute */
610   NULL,                                 /* sub */
611   NULL,                                 /* next */
612   0,                                    /* static_pass_number */
613   TV_TREE_PARALLELIZE_LOOPS,            /* tv_id */
614   PROP_cfg | PROP_ssa,                  /* properties_required */
615   0,                                    /* properties_provided */
616   0,                                    /* properties_destroyed */
617   0,                                    /* todo_flags_start */
618   TODO_dump_func | TODO_verify_loops    /* todo_flags_finish */
619  }
620 };
621
622 /* Prefetching.  */
623
624 static unsigned int
625 tree_ssa_loop_prefetch (void)
626 {
627   if (number_of_loops () <= 1)
628     return 0;
629
630   return tree_ssa_prefetch_arrays ();
631 }
632
633 static bool
634 gate_tree_ssa_loop_prefetch (void)
635 {
636   return flag_prefetch_loop_arrays != 0;
637 }
638
639 struct gimple_opt_pass pass_loop_prefetch =
640 {
641  {
642   GIMPLE_PASS,
643   "aprefetch",                          /* name */
644   gate_tree_ssa_loop_prefetch,          /* gate */
645   tree_ssa_loop_prefetch,               /* execute */
646   NULL,                                 /* sub */
647   NULL,                                 /* next */
648   0,                                    /* static_pass_number */
649   TV_TREE_PREFETCH,                     /* tv_id */
650   PROP_cfg | PROP_ssa,                  /* properties_required */
651   0,                                    /* properties_provided */
652   0,                                    /* properties_destroyed */
653   0,                                    /* todo_flags_start */
654   TODO_dump_func | TODO_verify_loops    /* todo_flags_finish */
655  }
656 };
657
658 /* Induction variable optimizations.  */
659
660 static unsigned int
661 tree_ssa_loop_ivopts (void)
662 {
663   if (number_of_loops () <= 1)
664     return 0;
665
666   tree_ssa_iv_optimize ();
667   return 0;
668 }
669
670 static bool
671 gate_tree_ssa_loop_ivopts (void)
672 {
673   return flag_ivopts != 0;
674 }
675
676 struct gimple_opt_pass pass_iv_optimize =
677 {
678  {
679   GIMPLE_PASS,
680   "ivopts",                             /* name */
681   gate_tree_ssa_loop_ivopts,            /* gate */
682   tree_ssa_loop_ivopts,                 /* execute */
683   NULL,                                 /* sub */
684   NULL,                                 /* next */
685   0,                                    /* static_pass_number */
686   TV_TREE_LOOP_IVOPTS,                  /* tv_id */
687   PROP_cfg | PROP_ssa,                  /* properties_required */
688   0,                                    /* properties_provided */
689   0,                                    /* properties_destroyed */
690   0,                                    /* todo_flags_start */
691   TODO_dump_func | TODO_verify_loops
692   | TODO_update_ssa | TODO_ggc_collect  /* todo_flags_finish */
693  }
694 };
695
696 /* Loop optimizer finalization.  */
697
698 static unsigned int
699 tree_ssa_loop_done (void)
700 {
701   free_numbers_of_iterations_estimates ();
702   scev_finalize ();
703   loop_optimizer_finalize ();
704   return 0;
705 }
706   
707 struct gimple_opt_pass pass_tree_loop_done = 
708 {
709  {
710   GIMPLE_PASS,
711   "loopdone",                           /* name */
712   NULL,                                 /* gate */
713   tree_ssa_loop_done,                   /* execute */
714   NULL,                                 /* sub */
715   NULL,                                 /* next */
716   0,                                    /* static_pass_number */
717   TV_TREE_LOOP_FINI,                    /* tv_id */
718   PROP_cfg,                             /* properties_required */
719   0,                                    /* properties_provided */
720   0,                                    /* properties_destroyed */
721   0,                                    /* todo_flags_start */
722   TODO_cleanup_cfg | TODO_dump_func     /* todo_flags_finish */
723  }
724 };