1 /* Loop optimizations over tree-ssa.
2    Copyright (C) 2003, 2005, 2006, 2007, 2008, 2009, 2010
3    Free Software Foundation, Inc.
4 
5 This file is part of GCC.
6 
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
10 later version.
11 
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16 
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20 
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "tm_p.h"
27 #include "basic-block.h"
28 #include "output.h"
29 #include "tree-flow.h"
30 #include "tree-dump.h"
31 #include "tree-pass.h"
32 #include "timevar.h"
33 #include "cfgloop.h"
34 #include "flags.h"
35 #include "tree-inline.h"
36 #include "tree-scalar-evolution.h"
37 #include "diagnostic-core.h"
38 #include "tree-vectorizer.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_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   0             			/* 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   return tree_ssa_lim ();
111 }
112 
113 static bool
114 gate_tree_ssa_loop_im (void)
115 {
116   return flag_tree_loop_im != 0;
117 }
118 
119 struct gimple_opt_pass pass_lim =
120 {
121  {
122   GIMPLE_PASS,
123   "lim",				/* name */
124   gate_tree_ssa_loop_im,		/* gate */
125   tree_ssa_loop_im,			/* execute */
126   NULL,					/* sub */
127   NULL,					/* next */
128   0,					/* static_pass_number */
129   TV_LIM,				/* tv_id */
130   PROP_cfg,				/* properties_required */
131   0,					/* properties_provided */
132   0,					/* properties_destroyed */
133   0,					/* todo_flags_start */
134   0             			/* todo_flags_finish */
135  }
136 };
137 
138 /* Loop unswitching pass.  */
139 
140 static unsigned int
141 tree_ssa_loop_unswitch (void)
142 {
143   if (number_of_loops () <= 1)
144     return 0;
145 
146   return tree_ssa_unswitch_loops ();
147 }
148 
149 static bool
150 gate_tree_ssa_loop_unswitch (void)
151 {
152   return flag_unswitch_loops != 0;
153 }
154 
155 struct gimple_opt_pass pass_tree_unswitch =
156 {
157  {
158   GIMPLE_PASS,
159   "unswitch",				/* name */
160   gate_tree_ssa_loop_unswitch,		/* gate */
161   tree_ssa_loop_unswitch,		/* execute */
162   NULL,					/* sub */
163   NULL,					/* next */
164   0,					/* static_pass_number */
165   TV_TREE_LOOP_UNSWITCH,		/* tv_id */
166   PROP_cfg,				/* properties_required */
167   0,					/* properties_provided */
168   0,					/* properties_destroyed */
169   0,					/* todo_flags_start */
170   TODO_ggc_collect                  	/* todo_flags_finish */
171  }
172 };
173 
174 /* Predictive commoning.  */
175 
176 static unsigned
177 run_tree_predictive_commoning (void)
178 {
179   if (!current_loops)
180     return 0;
181 
182   return tree_predictive_commoning ();
183 }
184 
185 static bool
186 gate_tree_predictive_commoning (void)
187 {
188   return flag_predictive_commoning != 0;
189 }
190 
191 struct gimple_opt_pass pass_predcom =
192 {
193  {
194   GIMPLE_PASS,
195   "pcom",				/* name */
196   gate_tree_predictive_commoning,	/* gate */
197   run_tree_predictive_commoning,	/* execute */
198   NULL,					/* sub */
199   NULL,					/* next */
200   0,					/* static_pass_number */
201   TV_PREDCOM,				/* tv_id */
202   PROP_cfg,				/* properties_required */
203   0,					/* properties_provided */
204   0,					/* properties_destroyed */
205   0,					/* todo_flags_start */
206   TODO_update_ssa_only_virtuals 	/* todo_flags_finish */
207  }
208 };
209 
210 /* Loop autovectorization.  */
211 
212 static unsigned int
213 tree_vectorize (void)
214 {
215   if (number_of_loops () <= 1)
216     return 0;
217 
218   return vectorize_loops ();
219 }
220 
221 static bool
222 gate_tree_vectorize (void)
223 {
224   return flag_tree_vectorize;
225 }
226 
227 struct gimple_opt_pass pass_vectorize =
228 {
229  {
230   GIMPLE_PASS,
231   "vect",                               /* name */
232   gate_tree_vectorize,                  /* gate */
233   tree_vectorize,                       /* execute */
234   NULL,                                 /* sub */
235   NULL,                                 /* next */
236   0,                                    /* static_pass_number */
237   TV_TREE_VECTORIZATION,                /* tv_id */
238   PROP_cfg | PROP_ssa,                  /* properties_required */
239   0,                                    /* properties_provided */
240   0,                                    /* properties_destroyed */
241   0,					/* todo_flags_start */
242   TODO_update_ssa
243     | TODO_ggc_collect			/* todo_flags_finish */
244  }
245 };
246 
247 /* GRAPHITE optimizations.  */
248 
249 static unsigned int
250 graphite_transforms (void)
251 {
252   if (!current_loops)
253     return 0;
254 
255   graphite_transform_loops ();
256 
257   return 0;
258 }
259 
260 static bool
261 gate_graphite_transforms (void)
262 {
263   /* Enable -fgraphite pass if any one of the graphite optimization flags
264      is turned on.  */
265   if (flag_loop_block
266       || flag_loop_interchange
267       || flag_loop_strip_mine
268       || flag_graphite_identity
269       || flag_loop_parallelize_all
270       || flag_loop_flatten)
271     flag_graphite = 1;
272 
273   return flag_graphite != 0;
274 }
275 
276 struct gimple_opt_pass pass_graphite =
277 {
278  {
279   GIMPLE_PASS,
280   "graphite0",				/* name */
281   gate_graphite_transforms,		/* gate */
282   NULL,					/* execute */
283   NULL,					/* sub */
284   NULL,					/* next */
285   0,					/* static_pass_number */
286   TV_GRAPHITE,				/* tv_id */
287   PROP_cfg | PROP_ssa,			/* properties_required */
288   0,					/* properties_provided */
289   0,					/* properties_destroyed */
290   0,					/* todo_flags_start */
291   0					/* todo_flags_finish */
292  }
293 };
294 
295 struct gimple_opt_pass pass_graphite_transforms =
296 {
297  {
298   GIMPLE_PASS,
299   "graphite",				/* name */
300   gate_graphite_transforms,		/* gate */
301   graphite_transforms,       		/* execute */
302   NULL,					/* sub */
303   NULL,					/* next */
304   0,					/* static_pass_number */
305   TV_GRAPHITE_TRANSFORMS,  		/* tv_id */
306   PROP_cfg | PROP_ssa,			/* properties_required */
307   0,					/* properties_provided */
308   0,					/* properties_destroyed */
309   0,					/* todo_flags_start */
310   0             			/* todo_flags_finish */
311  }
312 };
313 
314 /* Check the correctness of the data dependence analyzers.  */
315 
316 static unsigned int
317 check_data_deps (void)
318 {
319   if (number_of_loops () <= 1)
320     return 0;
321 
322   tree_check_data_deps ();
323   return 0;
324 }
325 
326 static bool
327 gate_check_data_deps (void)
328 {
329   return flag_check_data_deps != 0;
330 }
331 
332 struct gimple_opt_pass pass_check_data_deps =
333 {
334  {
335   GIMPLE_PASS,
336   "ckdd",				/* name */
337   gate_check_data_deps,	        	/* gate */
338   check_data_deps,       		/* execute */
339   NULL,					/* sub */
340   NULL,					/* next */
341   0,					/* static_pass_number */
342   TV_CHECK_DATA_DEPS,  	        	/* tv_id */
343   PROP_cfg | PROP_ssa,			/* properties_required */
344   0,					/* properties_provided */
345   0,					/* properties_destroyed */
346   0,					/* todo_flags_start */
347   0                             	/* todo_flags_finish */
348  }
349 };
350 
351 /* Canonical induction variable creation pass.  */
352 
353 static unsigned int
354 tree_ssa_loop_ivcanon (void)
355 {
356   if (number_of_loops () <= 1)
357     return 0;
358 
359   return canonicalize_induction_variables ();
360 }
361 
362 static bool
363 gate_tree_ssa_loop_ivcanon (void)
364 {
365   return flag_tree_loop_ivcanon != 0;
366 }
367 
368 struct gimple_opt_pass pass_iv_canon =
369 {
370  {
371   GIMPLE_PASS,
372   "ivcanon",				/* name */
373   gate_tree_ssa_loop_ivcanon,		/* gate */
374   tree_ssa_loop_ivcanon,	       	/* execute */
375   NULL,					/* sub */
376   NULL,					/* next */
377   0,					/* static_pass_number */
378   TV_TREE_LOOP_IVCANON,	  		/* tv_id */
379   PROP_cfg | PROP_ssa,			/* properties_required */
380   0,					/* properties_provided */
381   0,					/* properties_destroyed */
382   0,					/* todo_flags_start */
383   0             			/* todo_flags_finish */
384  }
385 };
386 
387 /* Propagation of constants using scev.  */
388 
389 static bool
390 gate_scev_const_prop (void)
391 {
392   return flag_tree_scev_cprop;
393 }
394 
395 struct gimple_opt_pass pass_scev_cprop =
396 {
397  {
398   GIMPLE_PASS,
399   "sccp",				/* name */
400   gate_scev_const_prop,			/* gate */
401   scev_const_prop,	       		/* execute */
402   NULL,					/* sub */
403   NULL,					/* next */
404   0,					/* static_pass_number */
405   TV_SCEV_CONST,	  		/* tv_id */
406   PROP_cfg | PROP_ssa,			/* properties_required */
407   0,					/* properties_provided */
408   0,					/* properties_destroyed */
409   0,					/* todo_flags_start */
410   TODO_cleanup_cfg
411     | TODO_update_ssa_only_virtuals
412 					/* todo_flags_finish */
413  }
414 };
415 
416 /* Record bounds on numbers of iterations of loops.  */
417 
418 static unsigned int
419 tree_ssa_loop_bounds (void)
420 {
421   if (number_of_loops () <= 1)
422     return 0;
423 
424   estimate_numbers_of_iterations (true);
425   scev_reset ();
426   return 0;
427 }
428 
429 struct gimple_opt_pass pass_record_bounds =
430 {
431  {
432   GIMPLE_PASS,
433   "*record_bounds",			/* name */
434   NULL,					/* gate */
435   tree_ssa_loop_bounds,		       	/* execute */
436   NULL,					/* sub */
437   NULL,					/* next */
438   0,					/* static_pass_number */
439   TV_TREE_LOOP_BOUNDS,	  		/* tv_id */
440   PROP_cfg | PROP_ssa,			/* properties_required */
441   0,					/* properties_provided */
442   0,					/* properties_destroyed */
443   0,					/* todo_flags_start */
444   0			              	/* todo_flags_finish */
445  }
446 };
447 
448 /* Complete unrolling of loops.  */
449 
450 static unsigned int
451 tree_complete_unroll (void)
452 {
453   if (number_of_loops () <= 1)
454     return 0;
455 
456   return tree_unroll_loops_completely (flag_unroll_loops
457 				       || flag_peel_loops
458 				       || optimize >= 3, true);
459 }
460 
461 static bool
462 gate_tree_complete_unroll (void)
463 {
464   return true;
465 }
466 
467 struct gimple_opt_pass pass_complete_unroll =
468 {
469  {
470   GIMPLE_PASS,
471   "cunroll",				/* name */
472   gate_tree_complete_unroll,		/* gate */
473   tree_complete_unroll,		       	/* execute */
474   NULL,					/* sub */
475   NULL,					/* next */
476   0,					/* static_pass_number */
477   TV_COMPLETE_UNROLL,	  		/* tv_id */
478   PROP_cfg | PROP_ssa,			/* properties_required */
479   0,					/* properties_provided */
480   0,					/* properties_destroyed */
481   0,					/* todo_flags_start */
482   TODO_ggc_collect			/* todo_flags_finish */
483  }
484 };
485 
486 /* Complete unrolling of inner loops.  */
487 
488 static unsigned int
489 tree_complete_unroll_inner (void)
490 {
491   unsigned ret = 0;
492 
493   loop_optimizer_init (LOOPS_NORMAL
494 		       | LOOPS_HAVE_RECORDED_EXITS);
495   if (number_of_loops () > 1)
496     {
497       scev_initialize ();
498       ret = tree_unroll_loops_completely (optimize >= 3, false);
499       free_numbers_of_iterations_estimates ();
500       scev_finalize ();
501     }
502   loop_optimizer_finalize ();
503 
504   return ret;
505 }
506 
507 static bool
508 gate_tree_complete_unroll_inner (void)
509 {
510   return optimize >= 2;
511 }
512 
513 struct gimple_opt_pass pass_complete_unrolli =
514 {
515  {
516   GIMPLE_PASS,
517   "cunrolli",				/* name */
518   gate_tree_complete_unroll_inner,	/* gate */
519   tree_complete_unroll_inner,	       	/* execute */
520   NULL,					/* sub */
521   NULL,					/* next */
522   0,					/* static_pass_number */
523   TV_COMPLETE_UNROLL,	  		/* tv_id */
524   PROP_cfg | PROP_ssa,			/* properties_required */
525   0,					/* properties_provided */
526   0,					/* properties_destroyed */
527   0,					/* todo_flags_start */
528   TODO_verify_flow
529     | TODO_ggc_collect 			/* todo_flags_finish */
530  }
531 };
532 
533 /* Parallelization.  */
534 
535 static bool
536 gate_tree_parallelize_loops (void)
537 {
538   return flag_tree_parallelize_loops > 1;
539 }
540 
541 static unsigned
542 tree_parallelize_loops (void)
543 {
544   if (number_of_loops () <= 1)
545     return 0;
546 
547   if (parallelize_loops ())
548     return TODO_cleanup_cfg | TODO_rebuild_alias;
549   return 0;
550 }
551 
552 struct gimple_opt_pass pass_parallelize_loops =
553 {
554  {
555   GIMPLE_PASS,
556   "parloops",				/* name */
557   gate_tree_parallelize_loops,		/* gate */
558   tree_parallelize_loops,      		/* execute */
559   NULL,					/* sub */
560   NULL,					/* next */
561   0,					/* static_pass_number */
562   TV_TREE_PARALLELIZE_LOOPS,  		/* tv_id */
563   PROP_cfg | PROP_ssa,			/* properties_required */
564   0,					/* properties_provided */
565   0,					/* properties_destroyed */
566   0,					/* todo_flags_start */
567   0             			/* todo_flags_finish */
568  }
569 };
570 
571 /* Prefetching.  */
572 
573 static unsigned int
574 tree_ssa_loop_prefetch (void)
575 {
576   if (number_of_loops () <= 1)
577     return 0;
578 
579   return tree_ssa_prefetch_arrays ();
580 }
581 
582 static bool
583 gate_tree_ssa_loop_prefetch (void)
584 {
585   return flag_prefetch_loop_arrays > 0;
586 }
587 
588 struct gimple_opt_pass pass_loop_prefetch =
589 {
590  {
591   GIMPLE_PASS,
592   "aprefetch",				/* name */
593   gate_tree_ssa_loop_prefetch,		/* gate */
594   tree_ssa_loop_prefetch,	       	/* execute */
595   NULL,					/* sub */
596   NULL,					/* next */
597   0,					/* static_pass_number */
598   TV_TREE_PREFETCH,	  		/* tv_id */
599   PROP_cfg | PROP_ssa,			/* properties_required */
600   0,					/* properties_provided */
601   0,					/* properties_destroyed */
602   0,					/* todo_flags_start */
603   0             			/* todo_flags_finish */
604  }
605 };
606 
607 /* Induction variable optimizations.  */
608 
609 static unsigned int
610 tree_ssa_loop_ivopts (void)
611 {
612   if (number_of_loops () <= 1)
613     return 0;
614 
615   tree_ssa_iv_optimize ();
616   return 0;
617 }
618 
619 static bool
620 gate_tree_ssa_loop_ivopts (void)
621 {
622   return flag_ivopts != 0;
623 }
624 
625 struct gimple_opt_pass pass_iv_optimize =
626 {
627  {
628   GIMPLE_PASS,
629   "ivopts",				/* name */
630   gate_tree_ssa_loop_ivopts,		/* gate */
631   tree_ssa_loop_ivopts,		       	/* execute */
632   NULL,					/* sub */
633   NULL,					/* next */
634   0,					/* static_pass_number */
635   TV_TREE_LOOP_IVOPTS,	  		/* tv_id */
636   PROP_cfg | PROP_ssa,			/* properties_required */
637   0,					/* properties_provided */
638   0,					/* properties_destroyed */
639   0,					/* todo_flags_start */
640   TODO_update_ssa | TODO_ggc_collect	/* todo_flags_finish */
641  }
642 };
643 
644 /* Loop optimizer finalization.  */
645 
646 static unsigned int
647 tree_ssa_loop_done (void)
648 {
649   free_numbers_of_iterations_estimates ();
650   scev_finalize ();
651   loop_optimizer_finalize ();
652   return 0;
653 }
654 
655 struct gimple_opt_pass pass_tree_loop_done =
656 {
657  {
658   GIMPLE_PASS,
659   "loopdone",				/* name */
660   NULL,					/* gate */
661   tree_ssa_loop_done,			/* execute */
662   NULL,					/* sub */
663   NULL,					/* next */
664   0,					/* static_pass_number */
665   TV_TREE_LOOP_FINI,			/* tv_id */
666   PROP_cfg,				/* properties_required */
667   0,					/* properties_provided */
668   0,					/* properties_destroyed */
669   0,					/* todo_flags_start */
670   TODO_cleanup_cfg
671     | TODO_verify_flow			/* todo_flags_finish */
672  }
673 };
674