1/* Loop optimizer initialization routines and RTL loop optimization passes.
2   Copyright (C) 2002, 2003, 2004, 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 under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 2, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; 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 "rtl.h"
26#include "hard-reg-set.h"
27#include "obstack.h"
28#include "basic-block.h"
29#include "cfgloop.h"
30#include "cfglayout.h"
31#include "tree-pass.h"
32#include "timevar.h"
33#include "flags.h"
34
35
36/* Initialize loop optimizer.  This is used by the tree and RTL loop
37   optimizers.  FLAGS specify what properties to compute and/or ensure for
38   loops.  */
39
40struct loops *
41loop_optimizer_init (unsigned flags)
42{
43  struct loops *loops = XCNEW (struct loops);
44  edge e;
45  edge_iterator ei;
46  static bool first_time = true;
47
48  if (first_time)
49    {
50      first_time = false;
51      init_set_costs ();
52    }
53
54  /* Avoid annoying special cases of edges going to exit
55     block.  */
56
57  for (ei = ei_start (EXIT_BLOCK_PTR->preds); (e = ei_safe_edge (ei)); )
58    if ((e->flags & EDGE_FALLTHRU) && !single_succ_p (e->src))
59      split_edge (e);
60    else
61      ei_next (&ei);
62
63  /* Find the loops.  */
64
65  if (flow_loops_find (loops) <= 1)
66    {
67      /* No loops.  */
68      flow_loops_free (loops);
69      free (loops);
70
71      return NULL;
72    }
73
74  /* Not going to update these.  */
75  free (loops->cfg.rc_order);
76  loops->cfg.rc_order = NULL;
77  free (loops->cfg.dfs_order);
78  loops->cfg.dfs_order = NULL;
79
80  /* Create pre-headers.  */
81  if (flags & LOOPS_HAVE_PREHEADERS)
82    create_preheaders (loops, CP_SIMPLE_PREHEADERS);
83
84  /* Force all latches to have only single successor.  */
85  if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
86    force_single_succ_latches (loops);
87
88  /* Mark irreducible loops.  */
89  if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
90    mark_irreducible_loops (loops);
91
92  if (flags & LOOPS_HAVE_MARKED_SINGLE_EXITS)
93    mark_single_exit_loops (loops);
94
95  /* Dump loops.  */
96  flow_loops_dump (loops, dump_file, NULL, 1);
97
98#ifdef ENABLE_CHECKING
99  verify_dominators (CDI_DOMINATORS);
100  verify_loop_structure (loops);
101#endif
102
103  return loops;
104}
105
106/* Finalize loop optimizer.  */
107void
108loop_optimizer_finalize (struct loops *loops)
109{
110  unsigned i;
111
112  if (!loops)
113    return;
114
115  for (i = 1; i < loops->num; i++)
116    if (loops->parray[i])
117      free_simple_loop_desc (loops->parray[i]);
118
119  /* Clean up.  */
120  flow_loops_free (loops);
121  free (loops);
122
123  /* Checking.  */
124#ifdef ENABLE_CHECKING
125  verify_flow_info ();
126#endif
127}
128
129
130/* Gate for the RTL loop superpass.  The actual passes are subpasses.
131   See passes.c for more on that.  */
132
133static bool
134gate_handle_loop2 (void)
135{
136  return (optimize > 0
137  	  && (flag_move_loop_invariants
138              || flag_unswitch_loops
139              || flag_peel_loops
140              || flag_unroll_loops
141#ifdef HAVE_doloop_end
142	      || (flag_branch_on_count_reg && HAVE_doloop_end)
143#endif
144	      ));
145}
146
147struct tree_opt_pass pass_loop2 =
148{
149  "loop2",                              /* name */
150  gate_handle_loop2, 		        /* gate */
151  NULL,                                 /* execute */
152  NULL,                                 /* sub */
153  NULL,                                 /* next */
154  0,                                    /* static_pass_number */
155  TV_LOOP,                              /* tv_id */
156  0,                                    /* properties_required */
157  0,                                    /* properties_provided */
158  0,                                    /* properties_destroyed */
159  0,                                    /* todo_flags_start */
160  TODO_dump_func |
161  TODO_ggc_collect,                     /* todo_flags_finish */
162  'L'                                   /* letter */
163};
164
165
166/* Initialization of the RTL loop passes.  */
167static unsigned int
168rtl_loop_init (void)
169{
170  if (dump_file)
171    dump_flow_info (dump_file, dump_flags);
172
173  /* Initialize structures for layout changes.  */
174  cfg_layout_initialize (0);
175
176  current_loops = loop_optimizer_init (LOOPS_NORMAL);
177  return 0;
178}
179
180struct tree_opt_pass pass_rtl_loop_init =
181{
182  "loop2_init",                           /* name */
183  NULL,                                 /* gate */
184  rtl_loop_init,                        /* execute */
185  NULL,                                 /* sub */
186  NULL,                                 /* next */
187  0,                                    /* static_pass_number */
188  TV_LOOP,                              /* tv_id */
189  0,                                    /* properties_required */
190  0,                                    /* properties_provided */
191  0,                                    /* properties_destroyed */
192  0,                                    /* todo_flags_start */
193  TODO_dump_func,                       /* todo_flags_finish */
194  'L'                                   /* letter */
195};
196
197
198/* Finalization of the RTL loop passes.  */
199static unsigned int
200rtl_loop_done (void)
201{
202  basic_block bb;
203
204  if (current_loops)
205    loop_optimizer_finalize (current_loops);
206
207  free_dominance_info (CDI_DOMINATORS);
208
209  /* Finalize layout changes.  */
210  FOR_EACH_BB (bb)
211    if (bb->next_bb != EXIT_BLOCK_PTR)
212      bb->aux = bb->next_bb;
213  cfg_layout_finalize ();
214
215  cleanup_cfg (CLEANUP_EXPENSIVE);
216  delete_trivially_dead_insns (get_insns (), max_reg_num ());
217  reg_scan (get_insns (), max_reg_num ());
218  if (dump_file)
219    dump_flow_info (dump_file, dump_flags);
220
221  current_loops = NULL;
222  return 0;
223}
224
225struct tree_opt_pass pass_rtl_loop_done =
226{
227  "loop2_done",                          /* name */
228  NULL,                                 /* gate */
229  rtl_loop_done,                        /* execute */
230  NULL,                                 /* sub */
231  NULL,                                 /* next */
232  0,                                    /* static_pass_number */
233  TV_LOOP,                              /* tv_id */
234  0,                                    /* properties_required */
235  0,                                    /* properties_provided */
236  0,                                    /* properties_destroyed */
237  0,                                    /* todo_flags_start */
238  TODO_dump_func,                       /* todo_flags_finish */
239  'L'                                   /* letter */
240};
241
242
243/* Loop invariant code motion.  */
244static bool
245gate_rtl_move_loop_invariants (void)
246{
247  return flag_move_loop_invariants;
248}
249
250static unsigned int
251rtl_move_loop_invariants (void)
252{
253  if (current_loops)
254    move_loop_invariants (current_loops);
255  return 0;
256}
257
258struct tree_opt_pass pass_rtl_move_loop_invariants =
259{
260  "loop2_invariant",                     /* name */
261  gate_rtl_move_loop_invariants,        /* gate */
262  rtl_move_loop_invariants,             /* execute */
263  NULL,                                 /* sub */
264  NULL,                                 /* next */
265  0,                                    /* static_pass_number */
266  TV_LOOP,                              /* tv_id */
267  0,                                    /* properties_required */
268  0,                                    /* properties_provided */
269  0,                                    /* properties_destroyed */
270  0,                                    /* todo_flags_start */
271  TODO_dump_func,                       /* todo_flags_finish */
272  'L'                                   /* letter */
273};
274
275
276/* Loop unswitching for RTL.  */
277static bool
278gate_rtl_unswitch (void)
279{
280  return flag_unswitch_loops;
281}
282
283static unsigned int
284rtl_unswitch (void)
285{
286  if (current_loops)
287    unswitch_loops (current_loops);
288  return 0;
289}
290
291struct tree_opt_pass pass_rtl_unswitch =
292{
293  "loop2_unswitch",                      /* name */
294  gate_rtl_unswitch,                    /* gate */
295  rtl_unswitch,                         /* execute */
296  NULL,                                 /* sub */
297  NULL,                                 /* next */
298  0,                                    /* static_pass_number */
299  TV_LOOP,                              /* tv_id */
300  0,                                    /* properties_required */
301  0,                                    /* properties_provided */
302  0,                                    /* properties_destroyed */
303  0,                                    /* todo_flags_start */
304  TODO_dump_func,                       /* todo_flags_finish */
305  'L'                                   /* letter */
306};
307
308
309/* Loop unswitching for RTL.  */
310static bool
311gate_rtl_unroll_and_peel_loops (void)
312{
313  return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
314}
315
316static unsigned int
317rtl_unroll_and_peel_loops (void)
318{
319  if (current_loops)
320    {
321      int flags = 0;
322
323      if (flag_peel_loops)
324	flags |= UAP_PEEL;
325      if (flag_unroll_loops)
326	flags |= UAP_UNROLL;
327      if (flag_unroll_all_loops)
328	flags |= UAP_UNROLL_ALL;
329
330      unroll_and_peel_loops (current_loops, flags);
331    }
332  return 0;
333}
334
335struct tree_opt_pass pass_rtl_unroll_and_peel_loops =
336{
337  "loop2_unroll",                        /* name */
338  gate_rtl_unroll_and_peel_loops,       /* gate */
339  rtl_unroll_and_peel_loops,            /* execute */
340  NULL,                                 /* sub */
341  NULL,                                 /* next */
342  0,                                    /* static_pass_number */
343  TV_LOOP,                              /* tv_id */
344  0,                                    /* properties_required */
345  0,                                    /* properties_provided */
346  0,                                    /* properties_destroyed */
347  0,                                    /* todo_flags_start */
348  TODO_dump_func,                       /* todo_flags_finish */
349  'L'                                   /* letter */
350};
351
352
353/* The doloop optimization.  */
354static bool
355gate_rtl_doloop (void)
356{
357#ifdef HAVE_doloop_end
358  return (flag_branch_on_count_reg && HAVE_doloop_end);
359#else
360  return 0;
361#endif
362}
363
364static unsigned int
365rtl_doloop (void)
366{
367#ifdef HAVE_doloop_end
368  if (current_loops)
369    doloop_optimize_loops (current_loops);
370#endif
371  return 0;
372}
373
374struct tree_opt_pass pass_rtl_doloop =
375{
376  "loop2_doloop",                        /* name */
377  gate_rtl_doloop,                      /* gate */
378  rtl_doloop,                           /* execute */
379  NULL,                                 /* sub */
380  NULL,                                 /* next */
381  0,                                    /* static_pass_number */
382  TV_LOOP,                              /* tv_id */
383  0,                                    /* properties_required */
384  0,                                    /* properties_provided */
385  0,                                    /* properties_destroyed */
386  0,                                    /* todo_flags_start */
387  TODO_dump_func,                       /* todo_flags_finish */
388  'L'                                   /* letter */
389};
390
391