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