1/* Loop optimizations over tree-ssa.
2   Copyright (C) 2003, 2005 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 2, 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 COPYING.  If not, write to the Free
18Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
1902110-1301, USA.  */
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "tm.h"
25#include "tree.h"
26#include "rtl.h"
27#include "tm_p.h"
28#include "hard-reg-set.h"
29#include "basic-block.h"
30#include "output.h"
31#include "diagnostic.h"
32#include "tree-flow.h"
33#include "tree-dump.h"
34#include "tree-pass.h"
35#include "timevar.h"
36#include "cfgloop.h"
37#include "flags.h"
38#include "tree-inline.h"
39#include "tree-scalar-evolution.h"
40
41/* The loop tree currently optimized.  */
42
43struct loops *current_loops = NULL;
44
45/* Initializes the loop structures.  */
46
47static struct loops *
48tree_loop_optimizer_init (void)
49{
50  struct loops *loops;
51
52  loops = loop_optimizer_init (LOOPS_NORMAL
53			       | LOOPS_HAVE_MARKED_SINGLE_EXITS);
54
55  if (!loops)
56    return NULL;
57
58  rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
59
60  return loops;
61}
62
63/* The loop superpass.  */
64
65static bool
66gate_tree_loop (void)
67{
68  return flag_tree_loop_optimize != 0;
69}
70
71struct tree_opt_pass pass_tree_loop =
72{
73  "loop",				/* name */
74  gate_tree_loop,			/* gate */
75  NULL,					/* execute */
76  NULL,					/* sub */
77  NULL,					/* next */
78  0,					/* static_pass_number */
79  TV_TREE_LOOP,				/* tv_id */
80  PROP_cfg,				/* properties_required */
81  0,					/* properties_provided */
82  0,					/* properties_destroyed */
83  TODO_ggc_collect,			/* todo_flags_start */
84  TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect,	/* todo_flags_finish */
85  0					/* letter */
86};
87
88/* Loop optimizer initialization.  */
89
90static unsigned int
91tree_ssa_loop_init (void)
92{
93  current_loops = tree_loop_optimizer_init ();
94  if (!current_loops)
95    return 0;
96
97  scev_initialize (current_loops);
98  return 0;
99}
100
101struct tree_opt_pass pass_tree_loop_init =
102{
103  "loopinit",				/* name */
104  NULL,					/* gate */
105  tree_ssa_loop_init,			/* execute */
106  NULL,					/* sub */
107  NULL,					/* next */
108  0,					/* static_pass_number */
109  TV_TREE_LOOP_INIT,			/* tv_id */
110  PROP_cfg,				/* properties_required */
111  0,					/* properties_provided */
112  0,					/* properties_destroyed */
113  0,					/* todo_flags_start */
114  TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
115  0					/* letter */
116};
117
118/* Loop invariant motion pass.  */
119
120static unsigned int
121tree_ssa_loop_im (void)
122{
123  if (!current_loops)
124    return 0;
125
126  tree_ssa_lim (current_loops);
127  return 0;
128}
129
130static bool
131gate_tree_ssa_loop_im (void)
132{
133  return flag_tree_loop_im != 0;
134}
135
136struct tree_opt_pass pass_lim =
137{
138  "lim",				/* name */
139  gate_tree_ssa_loop_im,		/* gate */
140  tree_ssa_loop_im,			/* execute */
141  NULL,					/* sub */
142  NULL,					/* next */
143  0,					/* static_pass_number */
144  TV_LIM,				/* tv_id */
145  PROP_cfg,				/* properties_required */
146  0,					/* properties_provided */
147  0,					/* properties_destroyed */
148  0,					/* todo_flags_start */
149  TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
150  0					/* letter */
151};
152
153/* Loop unswitching pass.  */
154
155static unsigned int
156tree_ssa_loop_unswitch (void)
157{
158  if (!current_loops)
159    return 0;
160
161  return tree_ssa_unswitch_loops (current_loops);
162}
163
164static bool
165gate_tree_ssa_loop_unswitch (void)
166{
167  return flag_unswitch_loops != 0;
168}
169
170struct tree_opt_pass pass_tree_unswitch =
171{
172  "unswitch",				/* name */
173  gate_tree_ssa_loop_unswitch,		/* gate */
174  tree_ssa_loop_unswitch,		/* execute */
175  NULL,					/* sub */
176  NULL,					/* next */
177  0,					/* static_pass_number */
178  TV_TREE_LOOP_UNSWITCH,		/* tv_id */
179  PROP_cfg,				/* properties_required */
180  0,					/* properties_provided */
181  0,					/* properties_destroyed */
182  0,					/* todo_flags_start */
183  TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
184  0					/* letter */
185};
186
187/* Loop autovectorization.  */
188
189static unsigned int
190tree_vectorize (void)
191{
192  vectorize_loops (current_loops);
193  return 0;
194}
195
196static bool
197gate_tree_vectorize (void)
198{
199  return flag_tree_vectorize && current_loops;
200}
201
202struct tree_opt_pass pass_vectorize =
203{
204  "vect",                               /* name */
205  gate_tree_vectorize,                  /* gate */
206  tree_vectorize,                       /* execute */
207  NULL,                                 /* sub */
208  NULL,                                 /* next */
209  0,                                    /* static_pass_number */
210  TV_TREE_VECTORIZATION,                /* tv_id */
211  PROP_cfg | PROP_ssa,                  /* properties_required */
212  0,                                    /* properties_provided */
213  0,                                    /* properties_destroyed */
214  TODO_verify_loops,			/* todo_flags_start */
215  TODO_dump_func | TODO_update_ssa,	/* todo_flags_finish */
216  0					/* letter */
217};
218
219/* Loop nest optimizations.  */
220
221static unsigned int
222tree_linear_transform (void)
223{
224  if (!current_loops)
225    return 0;
226
227  linear_transform_loops (current_loops);
228  return 0;
229}
230
231static bool
232gate_tree_linear_transform (void)
233{
234  return flag_tree_loop_linear != 0;
235}
236
237struct tree_opt_pass pass_linear_transform =
238{
239  "ltrans",				/* name */
240  gate_tree_linear_transform,		/* gate */
241  tree_linear_transform,       		/* execute */
242  NULL,					/* sub */
243  NULL,					/* next */
244  0,					/* static_pass_number */
245  TV_TREE_LINEAR_TRANSFORM,  		/* tv_id */
246  PROP_cfg | PROP_ssa,			/* properties_required */
247  0,					/* properties_provided */
248  0,					/* properties_destroyed */
249  0,					/* todo_flags_start */
250  TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
251  0				        /* letter */
252};
253
254/* Canonical induction variable creation pass.  */
255
256static unsigned int
257tree_ssa_loop_ivcanon (void)
258{
259  if (!current_loops)
260    return 0;
261
262  return canonicalize_induction_variables (current_loops);
263}
264
265static bool
266gate_tree_ssa_loop_ivcanon (void)
267{
268  return flag_tree_loop_ivcanon != 0;
269}
270
271struct tree_opt_pass pass_iv_canon =
272{
273  "ivcanon",				/* name */
274  gate_tree_ssa_loop_ivcanon,		/* gate */
275  tree_ssa_loop_ivcanon,	       	/* execute */
276  NULL,					/* sub */
277  NULL,					/* next */
278  0,					/* static_pass_number */
279  TV_TREE_LOOP_IVCANON,	  		/* 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,	/* todo_flags_finish */
285  0					/* letter */
286};
287
288/* Propagation of constants using scev.  */
289
290static bool
291gate_scev_const_prop (void)
292{
293  return true;
294}
295
296struct tree_opt_pass pass_scev_cprop =
297{
298  "sccp",				/* name */
299  gate_scev_const_prop,			/* gate */
300  scev_const_prop,	       		/* execute */
301  NULL,					/* sub */
302  NULL,					/* next */
303  0,					/* static_pass_number */
304  TV_SCEV_CONST,	  		/* tv_id */
305  PROP_cfg | PROP_ssa,			/* properties_required */
306  0,					/* properties_provided */
307  0,					/* properties_destroyed */
308  0,					/* todo_flags_start */
309  TODO_dump_func | TODO_cleanup_cfg
310    | TODO_update_ssa_only_virtuals,
311					/* todo_flags_finish */
312  0					/* letter */
313};
314
315/* Remove empty loops.  */
316
317static unsigned int
318tree_ssa_empty_loop (void)
319{
320  if (!current_loops)
321    return 0;
322
323  return remove_empty_loops (current_loops);
324}
325
326struct tree_opt_pass pass_empty_loop =
327{
328  "empty",				/* name */
329  NULL,					/* gate */
330  tree_ssa_empty_loop,		       	/* execute */
331  NULL,					/* sub */
332  NULL,					/* next */
333  0,					/* static_pass_number */
334  TV_COMPLETE_UNROLL,	  		/* tv_id */
335  PROP_cfg | PROP_ssa,			/* properties_required */
336  0,					/* properties_provided */
337  0,					/* properties_destroyed */
338  0,					/* todo_flags_start */
339  TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
340  0					/* letter */
341};
342
343/* Record bounds on numbers of iterations of loops.  */
344
345static unsigned int
346tree_ssa_loop_bounds (void)
347{
348  if (!current_loops)
349    return 0;
350
351  estimate_numbers_of_iterations (current_loops);
352  scev_reset ();
353  return 0;
354}
355
356struct tree_opt_pass pass_record_bounds =
357{
358  NULL,					/* name */
359  NULL,					/* gate */
360  tree_ssa_loop_bounds,		       	/* execute */
361  NULL,					/* sub */
362  NULL,					/* next */
363  0,					/* static_pass_number */
364  TV_TREE_LOOP_BOUNDS,	  		/* tv_id */
365  PROP_cfg | PROP_ssa,			/* properties_required */
366  0,					/* properties_provided */
367  0,					/* properties_destroyed */
368  0,					/* todo_flags_start */
369  0,			              	/* todo_flags_finish */
370  0					/* letter */
371};
372
373/* Complete unrolling of loops.  */
374
375static unsigned int
376tree_complete_unroll (void)
377{
378  if (!current_loops)
379    return 0;
380
381  return tree_unroll_loops_completely (current_loops,
382				       flag_unroll_loops
383					|| flag_peel_loops
384					|| optimize >= 3);
385}
386
387static bool
388gate_tree_complete_unroll (void)
389{
390  return true;
391}
392
393struct tree_opt_pass pass_complete_unroll =
394{
395  "cunroll",				/* name */
396  gate_tree_complete_unroll,		/* gate */
397  tree_complete_unroll,		       	/* execute */
398  NULL,					/* sub */
399  NULL,					/* next */
400  0,					/* static_pass_number */
401  TV_COMPLETE_UNROLL,	  		/* tv_id */
402  PROP_cfg | PROP_ssa,			/* properties_required */
403  0,					/* properties_provided */
404  0,					/* properties_destroyed */
405  0,					/* todo_flags_start */
406  TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
407  0					/* letter */
408};
409
410/* Prefetching.  */
411
412static unsigned int
413tree_ssa_loop_prefetch (void)
414{
415  if (!current_loops)
416    return 0;
417
418  return tree_ssa_prefetch_arrays (current_loops);
419}
420
421static bool
422gate_tree_ssa_loop_prefetch (void)
423{
424  return flag_prefetch_loop_arrays != 0;
425}
426
427struct tree_opt_pass pass_loop_prefetch =
428{
429  "prefetch",				/* name */
430  gate_tree_ssa_loop_prefetch,		/* gate */
431  tree_ssa_loop_prefetch,	       	/* execute */
432  NULL,					/* sub */
433  NULL,					/* next */
434  0,					/* static_pass_number */
435  TV_TREE_PREFETCH,	  		/* tv_id */
436  PROP_cfg | PROP_ssa,			/* properties_required */
437  0,					/* properties_provided */
438  0,					/* properties_destroyed */
439  0,					/* todo_flags_start */
440  TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
441  0					/* letter */
442};
443
444/* Induction variable optimizations.  */
445
446static unsigned int
447tree_ssa_loop_ivopts (void)
448{
449  if (!current_loops)
450    return 0;
451
452  tree_ssa_iv_optimize (current_loops);
453  return 0;
454}
455
456static bool
457gate_tree_ssa_loop_ivopts (void)
458{
459  return flag_ivopts != 0;
460}
461
462struct tree_opt_pass pass_iv_optimize =
463{
464  "ivopts",				/* name */
465  gate_tree_ssa_loop_ivopts,		/* gate */
466  tree_ssa_loop_ivopts,		       	/* execute */
467  NULL,					/* sub */
468  NULL,					/* next */
469  0,					/* static_pass_number */
470  TV_TREE_LOOP_IVOPTS,	  		/* tv_id */
471  PROP_cfg | PROP_ssa,			/* properties_required */
472  0,					/* properties_provided */
473  0,					/* properties_destroyed */
474  0,					/* todo_flags_start */
475  TODO_dump_func
476  | TODO_verify_loops
477  | TODO_update_ssa,			/* todo_flags_finish */
478  0					/* letter */
479};
480
481/* Loop optimizer finalization.  */
482
483static unsigned int
484tree_ssa_loop_done (void)
485{
486  if (!current_loops)
487    return 0;
488
489  free_numbers_of_iterations_estimates (current_loops);
490  scev_finalize ();
491  loop_optimizer_finalize (current_loops);
492  current_loops = NULL;
493  return 0;
494}
495
496struct tree_opt_pass pass_tree_loop_done =
497{
498  "loopdone",				/* name */
499  NULL,					/* gate */
500  tree_ssa_loop_done,			/* execute */
501  NULL,					/* sub */
502  NULL,					/* next */
503  0,					/* static_pass_number */
504  TV_TREE_LOOP_FINI,			/* tv_id */
505  PROP_cfg,				/* properties_required */
506  0,					/* properties_provided */
507  0,					/* properties_destroyed */
508  0,					/* todo_flags_start */
509  TODO_cleanup_cfg | TODO_dump_func,	/* todo_flags_finish */
510  0					/* letter */
511};
512