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