OSDN Git Service

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