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.  DUMP is the file to that the details
46   about the analysis should be dumped.  */
47
48static struct loops *
49tree_loop_optimizer_init (FILE *dump)
50{
51  struct loops *loops = loop_optimizer_init (dump);
52
53  if (!loops)
54    return NULL;
55
56  rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
57
58  return loops;
59}
60
61/* The loop superpass.  */
62
63static bool
64gate_tree_loop (void)
65{
66  return flag_tree_loop_optimize != 0;
67}
68
69struct tree_opt_pass pass_tree_loop =
70{
71  "loop",				/* name */
72  gate_tree_loop,			/* gate */
73  NULL,					/* execute */
74  NULL,					/* sub */
75  NULL,					/* next */
76  0,					/* static_pass_number */
77  TV_TREE_LOOP,				/* tv_id */
78  PROP_cfg,				/* properties_required */
79  0,					/* properties_provided */
80  0,					/* properties_destroyed */
81  TODO_ggc_collect,			/* todo_flags_start */
82  TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect,	/* todo_flags_finish */
83  0					/* letter */
84};
85
86/* Loop optimizer initialization.  */
87
88static void
89tree_ssa_loop_init (void)
90{
91  current_loops = tree_loop_optimizer_init (dump_file);
92  if (!current_loops)
93    return;
94
95  /* Find the loops that are exited just through a single edge.  */
96  mark_single_exit_loops (current_loops);
97
98  scev_initialize (current_loops);
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 void
121tree_ssa_loop_im (void)
122{
123  if (!current_loops)
124    return;
125
126  tree_ssa_lim (current_loops);
127}
128
129static bool
130gate_tree_ssa_loop_im (void)
131{
132  return flag_tree_loop_im != 0;
133}
134
135struct tree_opt_pass pass_lim =
136{
137  "lim",				/* name */
138  gate_tree_ssa_loop_im,		/* gate */
139  tree_ssa_loop_im,			/* execute */
140  NULL,					/* sub */
141  NULL,					/* next */
142  0,					/* static_pass_number */
143  TV_LIM,				/* tv_id */
144  PROP_cfg,				/* properties_required */
145  0,					/* properties_provided */
146  0,					/* properties_destroyed */
147  0,					/* todo_flags_start */
148  TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
149  0					/* letter */
150};
151
152/* Loop unswitching pass.  */
153
154static void
155tree_ssa_loop_unswitch (void)
156{
157  if (!current_loops)
158    return;
159
160  tree_ssa_unswitch_loops (current_loops);
161}
162
163static bool
164gate_tree_ssa_loop_unswitch (void)
165{
166  return flag_unswitch_loops != 0;
167}
168
169struct tree_opt_pass pass_tree_unswitch =
170{
171  "unswitch",				/* name */
172  gate_tree_ssa_loop_unswitch,		/* gate */
173  tree_ssa_loop_unswitch,		/* execute */
174  NULL,					/* sub */
175  NULL,					/* next */
176  0,					/* static_pass_number */
177  TV_TREE_LOOP_UNSWITCH,		/* tv_id */
178  PROP_cfg,				/* properties_required */
179  0,					/* properties_provided */
180  0,					/* properties_destroyed */
181  0,					/* todo_flags_start */
182  TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
183  0					/* letter */
184};
185
186/* Loop autovectorization.  */
187
188static void
189tree_vectorize (void)
190{
191  vectorize_loops (current_loops);
192}
193
194static bool
195gate_tree_vectorize (void)
196{
197  return flag_tree_vectorize && current_loops;
198}
199
200struct tree_opt_pass pass_vectorize =
201{
202  "vect",                               /* name */
203  gate_tree_vectorize,                  /* gate */
204  tree_vectorize,                       /* execute */
205  NULL,                                 /* sub */
206  NULL,                                 /* next */
207  0,                                    /* static_pass_number */
208  TV_TREE_VECTORIZATION,                /* tv_id */
209  PROP_cfg | PROP_ssa,                  /* properties_required */
210  0,                                    /* properties_provided */
211  0,                                    /* properties_destroyed */
212  TODO_verify_loops,			/* todo_flags_start */
213  TODO_dump_func | TODO_update_ssa,	/* todo_flags_finish */
214  0					/* letter */
215};
216
217/* Loop nest optimizations.  */
218
219static void
220tree_linear_transform (void)
221{
222  if (!current_loops)
223    return;
224
225  linear_transform_loops (current_loops);
226}
227
228static bool
229gate_tree_linear_transform (void)
230{
231  return flag_tree_loop_linear != 0;
232}
233
234struct tree_opt_pass pass_linear_transform =
235{
236  "ltrans",				/* name */
237  gate_tree_linear_transform,		/* gate */
238  tree_linear_transform,       		/* execute */
239  NULL,					/* sub */
240  NULL,					/* next */
241  0,					/* static_pass_number */
242  TV_TREE_LINEAR_TRANSFORM,  		/* 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_verify_loops,	/* todo_flags_finish */
248  0				        /* letter */
249};
250
251/* Canonical induction variable creation pass.  */
252
253static void
254tree_ssa_loop_ivcanon (void)
255{
256  if (!current_loops)
257    return;
258
259  canonicalize_induction_variables (current_loops);
260}
261
262static bool
263gate_tree_ssa_loop_ivcanon (void)
264{
265  return flag_tree_loop_ivcanon != 0;
266}
267
268struct tree_opt_pass pass_iv_canon =
269{
270  "ivcanon",				/* name */
271  gate_tree_ssa_loop_ivcanon,		/* gate */
272  tree_ssa_loop_ivcanon,	       	/* execute */
273  NULL,					/* sub */
274  NULL,					/* next */
275  0,					/* static_pass_number */
276  TV_TREE_LOOP_IVCANON,	  		/* tv_id */
277  PROP_cfg | PROP_ssa,			/* properties_required */
278  0,					/* properties_provided */
279  0,					/* properties_destroyed */
280  0,					/* todo_flags_start */
281  TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
282  0					/* letter */
283};
284
285/* Propagation of constants using scev.  */
286
287static bool
288gate_scev_const_prop (void)
289{
290  return true;
291}
292
293struct tree_opt_pass pass_scev_cprop =
294{
295  "sccp",				/* name */
296  gate_scev_const_prop,			/* gate */
297  scev_const_prop,	       		/* execute */
298  NULL,					/* sub */
299  NULL,					/* next */
300  0,					/* static_pass_number */
301  TV_SCEV_CONST,	  		/* tv_id */
302  PROP_cfg | PROP_ssa,			/* properties_required */
303  0,					/* properties_provided */
304  0,					/* properties_destroyed */
305  0,					/* todo_flags_start */
306  TODO_dump_func | TODO_cleanup_cfg
307    | TODO_update_ssa_only_virtuals,
308					/* todo_flags_finish */
309  0					/* letter */
310};
311
312/* Remove empty loops.  */
313
314static void
315tree_ssa_empty_loop (void)
316{
317  if (!current_loops)
318    return;
319
320  remove_empty_loops (current_loops);
321}
322
323struct tree_opt_pass pass_empty_loop =
324{
325  "empty",				/* name */
326  NULL,					/* gate */
327  tree_ssa_empty_loop,		       	/* execute */
328  NULL,					/* sub */
329  NULL,					/* next */
330  0,					/* static_pass_number */
331  TV_COMPLETE_UNROLL,	  		/* tv_id */
332  PROP_cfg | PROP_ssa,			/* properties_required */
333  0,					/* properties_provided */
334  0,					/* properties_destroyed */
335  0,					/* todo_flags_start */
336  TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
337  0					/* letter */
338};
339
340/* Record bounds on numbers of iterations of loops.  */
341
342static void
343tree_ssa_loop_bounds (void)
344{
345  if (!current_loops)
346    return;
347
348  estimate_numbers_of_iterations (current_loops);
349  scev_reset ();
350}
351
352struct tree_opt_pass pass_record_bounds =
353{
354  NULL,					/* name */
355  NULL,					/* gate */
356  tree_ssa_loop_bounds,		       	/* execute */
357  NULL,					/* sub */
358  NULL,					/* next */
359  0,					/* static_pass_number */
360  TV_TREE_LOOP_BOUNDS,	  		/* tv_id */
361  PROP_cfg | PROP_ssa,			/* properties_required */
362  0,					/* properties_provided */
363  0,					/* properties_destroyed */
364  0,					/* todo_flags_start */
365  0,			              	/* todo_flags_finish */
366  0					/* letter */
367};
368
369/* Complete unrolling of loops.  */
370
371static void
372tree_complete_unroll (void)
373{
374  if (!current_loops)
375    return;
376
377  tree_unroll_loops_completely (current_loops,
378				flag_unroll_loops
379				|| flag_peel_loops
380				|| optimize >= 3);
381}
382
383static bool
384gate_tree_complete_unroll (void)
385{
386  return true;
387}
388
389struct tree_opt_pass pass_complete_unroll =
390{
391  "cunroll",				/* name */
392  gate_tree_complete_unroll,		/* gate */
393  tree_complete_unroll,		       	/* execute */
394  NULL,					/* sub */
395  NULL,					/* next */
396  0,					/* static_pass_number */
397  TV_COMPLETE_UNROLL,	  		/* 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  0					/* letter */
404};
405
406/* Induction variable optimizations.  */
407
408static void
409tree_ssa_loop_ivopts (void)
410{
411  if (!current_loops)
412    return;
413
414  tree_ssa_iv_optimize (current_loops);
415}
416
417static bool
418gate_tree_ssa_loop_ivopts (void)
419{
420  return flag_ivopts != 0;
421}
422
423struct tree_opt_pass pass_iv_optimize =
424{
425  "ivopts",				/* name */
426  gate_tree_ssa_loop_ivopts,		/* gate */
427  tree_ssa_loop_ivopts,		       	/* execute */
428  NULL,					/* sub */
429  NULL,					/* next */
430  0,					/* static_pass_number */
431  TV_TREE_LOOP_IVOPTS,	  		/* tv_id */
432  PROP_cfg | PROP_ssa,			/* properties_required */
433  0,					/* properties_provided */
434  0,					/* properties_destroyed */
435  0,					/* todo_flags_start */
436  TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
437  0					/* letter */
438};
439
440/* Loop optimizer finalization.  */
441
442static void
443tree_ssa_loop_done (void)
444{
445  if (!current_loops)
446    return;
447
448  free_numbers_of_iterations_estimates (current_loops);
449  scev_finalize ();
450  loop_optimizer_finalize (current_loops,
451			   (dump_flags & TDF_DETAILS ? dump_file : NULL));
452  current_loops = NULL;
453}
454
455struct tree_opt_pass pass_tree_loop_done =
456{
457  "loopdone",				/* name */
458  NULL,					/* gate */
459  tree_ssa_loop_done,			/* execute */
460  NULL,					/* sub */
461  NULL,					/* next */
462  0,					/* static_pass_number */
463  TV_TREE_LOOP_FINI,			/* tv_id */
464  PROP_cfg,				/* properties_required */
465  0,					/* properties_provided */
466  0,					/* properties_destroyed */
467  0,					/* todo_flags_start */
468  TODO_cleanup_cfg | TODO_dump_func,	/* todo_flags_finish */
469  0					/* letter */
470};
471