1/* Loop optimizer initialization routines and RTL loop optimization passes.
2   Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008
3   Free Software Foundation, Inc.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3.  If not see
19<http://www.gnu.org/licenses/>.  */
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#include "df.h"
35#include "ggc.h"
36
37
38/* Initialize loop structures.  This is used by the tree and RTL loop
39   optimizers.  FLAGS specify what properties to compute and/or ensure for
40   loops.  */
41
42void
43loop_optimizer_init (unsigned flags)
44{
45  struct loops *loops;
46
47  gcc_assert (!current_loops);
48  loops = GGC_CNEW (struct loops);
49
50  /* Find the loops.  */
51
52  flow_loops_find (loops);
53  current_loops = loops;
54
55  if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
56    {
57      /* If the loops may have multiple latches, we cannot canonicalize
58	 them further (and most of the loop manipulation functions will
59	 not work).  However, we avoid modifying cfg, which some
60	 passes may want.  */
61      gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
62			     | LOOPS_HAVE_RECORDED_EXITS)) == 0);
63      loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
64    }
65  else
66    disambiguate_loops_with_multiple_latches ();
67
68  /* Create pre-headers.  */
69  if (flags & LOOPS_HAVE_PREHEADERS)
70    {
71      int cp_flags = CP_SIMPLE_PREHEADERS;
72
73      if (flags & LOOPS_HAVE_FALLTHRU_PREHEADERS)
74        cp_flags |= CP_FALLTHRU_PREHEADERS;
75
76      create_preheaders (cp_flags);
77    }
78
79  /* Force all latches to have only single successor.  */
80  if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
81    force_single_succ_latches ();
82
83  /* Mark irreducible loops.  */
84  if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
85    mark_irreducible_loops ();
86
87  if (flags & LOOPS_HAVE_RECORDED_EXITS)
88    record_loop_exits ();
89
90  /* Dump loops.  */
91  flow_loops_dump (dump_file, NULL, 1);
92
93#ifdef ENABLE_CHECKING
94  verify_dominators (CDI_DOMINATORS);
95  verify_loop_structure ();
96#endif
97}
98
99/* Finalize loop structures.  */
100
101void
102loop_optimizer_finalize (void)
103{
104  loop_iterator li;
105  struct loop *loop;
106  basic_block bb;
107
108  gcc_assert (current_loops != NULL);
109
110  FOR_EACH_LOOP (li, loop, 0)
111    {
112      free_simple_loop_desc (loop);
113    }
114
115  /* Clean up.  */
116  if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
117    release_recorded_exits ();
118  flow_loops_free (current_loops);
119  ggc_free (current_loops);
120  current_loops = NULL;
121
122  FOR_ALL_BB (bb)
123    {
124      bb->loop_father = NULL;
125    }
126
127  /* Checking.  */
128#ifdef ENABLE_CHECKING
129  /* FIXME: no point to verify flow info after bundling on ia64.  Use this
130     hack for achieving this.  */
131  if (!reload_completed)
132    verify_flow_info ();
133#endif
134}
135
136
137/* Gate for the RTL loop superpass.  The actual passes are subpasses.
138   See passes.c for more on that.  */
139
140static bool
141gate_handle_loop2 (void)
142{
143  return (optimize > 0
144  	  && (flag_move_loop_invariants
145              || flag_unswitch_loops
146              || flag_peel_loops
147              || flag_unroll_loops
148#ifdef HAVE_doloop_end
149	      || (flag_branch_on_count_reg && HAVE_doloop_end)
150#endif
151	      ));
152}
153
154struct rtl_opt_pass pass_loop2 =
155{
156 {
157  RTL_PASS,
158  "loop2",                              /* name */
159  gate_handle_loop2, 		        /* gate */
160  NULL,                                 /* execute */
161  NULL,                                 /* sub */
162  NULL,                                 /* next */
163  0,                                    /* static_pass_number */
164  TV_LOOP,                              /* tv_id */
165  0,                                    /* properties_required */
166  0,                                    /* properties_provided */
167  0,                                    /* properties_destroyed */
168  0,                                    /* todo_flags_start */
169  TODO_dump_func |
170  TODO_ggc_collect                      /* todo_flags_finish */
171 }
172};
173
174
175/* Initialization of the RTL loop passes.  */
176static unsigned int
177rtl_loop_init (void)
178{
179  gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
180
181  if (dump_file)
182    dump_flow_info (dump_file, dump_flags);
183
184  loop_optimizer_init (LOOPS_NORMAL);
185  return 0;
186}
187
188struct rtl_opt_pass pass_rtl_loop_init =
189{
190 {
191  RTL_PASS,
192  "loop2_init",                           /* name */
193  NULL,                                 /* gate */
194  rtl_loop_init,                        /* execute */
195  NULL,                                 /* sub */
196  NULL,                                 /* next */
197  0,                                    /* static_pass_number */
198  TV_LOOP,                              /* tv_id */
199  0,                                    /* properties_required */
200  0,                                    /* properties_provided */
201  0,                                    /* properties_destroyed */
202  0,                                    /* todo_flags_start */
203  TODO_dump_func | TODO_verify_rtl_sharing /* todo_flags_finish */
204 }
205};
206
207
208/* Finalization of the RTL loop passes.  */
209
210static unsigned int
211rtl_loop_done (void)
212{
213  loop_optimizer_finalize ();
214  free_dominance_info (CDI_DOMINATORS);
215
216  cleanup_cfg (0);
217  if (dump_file)
218    dump_flow_info (dump_file, dump_flags);
219
220  return 0;
221}
222
223struct rtl_opt_pass pass_rtl_loop_done =
224{
225 {
226  RTL_PASS,
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_verify_rtl_sharing /* todo_flags_finish */
239 }
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 (number_of_loops () > 1)
254    move_loop_invariants ();
255  return 0;
256}
257
258struct rtl_opt_pass pass_rtl_move_loop_invariants =
259{
260 {
261  RTL_PASS,
262  "loop2_invariant",                    /* name */
263  gate_rtl_move_loop_invariants,        /* gate */
264  rtl_move_loop_invariants,             /* execute */
265  NULL,                                 /* sub */
266  NULL,                                 /* next */
267  0,                                    /* static_pass_number */
268  TV_LOOP_MOVE_INVARIANTS,              /* tv_id */
269  0,                                    /* properties_required */
270  0,                                    /* properties_provided */
271  0,                                    /* properties_destroyed */
272  0,                                    /* todo_flags_start */
273  TODO_df_verify |
274  TODO_df_finish | TODO_verify_rtl_sharing |
275  TODO_dump_func                        /* todo_flags_finish */
276 }
277};
278
279
280/* Loop unswitching for RTL.  */
281static bool
282gate_rtl_unswitch (void)
283{
284  return flag_unswitch_loops;
285}
286
287static unsigned int
288rtl_unswitch (void)
289{
290  if (number_of_loops () > 1)
291    unswitch_loops ();
292  return 0;
293}
294
295struct rtl_opt_pass pass_rtl_unswitch =
296{
297 {
298  RTL_PASS,
299  "loop2_unswitch",                      /* name */
300  gate_rtl_unswitch,                    /* gate */
301  rtl_unswitch,                         /* execute */
302  NULL,                                 /* sub */
303  NULL,                                 /* next */
304  0,                                    /* static_pass_number */
305  TV_LOOP_UNSWITCH,                     /* tv_id */
306  0,                                    /* properties_required */
307  0,                                    /* properties_provided */
308  0,                                    /* properties_destroyed */
309  0,                                    /* todo_flags_start */
310  TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */
311 }
312};
313
314
315/* Loop unswitching for RTL.  */
316static bool
317gate_rtl_unroll_and_peel_loops (void)
318{
319  return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
320}
321
322static unsigned int
323rtl_unroll_and_peel_loops (void)
324{
325  if (number_of_loops () > 1)
326    {
327      int flags = 0;
328      if (dump_file)
329	df_dump (dump_file);
330
331      if (flag_peel_loops)
332	flags |= UAP_PEEL;
333      if (flag_unroll_loops)
334	flags |= UAP_UNROLL;
335      if (flag_unroll_all_loops)
336	flags |= UAP_UNROLL_ALL;
337
338      unroll_and_peel_loops (flags);
339    }
340  return 0;
341}
342
343struct rtl_opt_pass pass_rtl_unroll_and_peel_loops =
344{
345 {
346  RTL_PASS,
347  "loop2_unroll",                        /* name */
348  gate_rtl_unroll_and_peel_loops,       /* gate */
349  rtl_unroll_and_peel_loops,            /* execute */
350  NULL,                                 /* sub */
351  NULL,                                 /* next */
352  0,                                    /* static_pass_number */
353  TV_LOOP_UNROLL,                       /* tv_id */
354  0,                                    /* properties_required */
355  0,                                    /* properties_provided */
356  0,                                    /* properties_destroyed */
357  0,                                    /* todo_flags_start */
358  TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */
359 }
360};
361
362
363/* The doloop optimization.  */
364static bool
365gate_rtl_doloop (void)
366{
367#ifdef HAVE_doloop_end
368  return (flag_branch_on_count_reg && HAVE_doloop_end);
369#else
370  return 0;
371#endif
372}
373
374static unsigned int
375rtl_doloop (void)
376{
377#ifdef HAVE_doloop_end
378  if (number_of_loops () > 1)
379    doloop_optimize_loops ();
380#endif
381  return 0;
382}
383
384struct rtl_opt_pass pass_rtl_doloop =
385{
386 {
387  RTL_PASS,
388  "loop2_doloop",                        /* name */
389  gate_rtl_doloop,                      /* gate */
390  rtl_doloop,                           /* execute */
391  NULL,                                 /* sub */
392  NULL,                                 /* next */
393  0,                                    /* static_pass_number */
394  TV_LOOP_DOLOOP,                       /* tv_id */
395  0,                                    /* properties_required */
396  0,                                    /* properties_provided */
397  0,                                    /* properties_destroyed */
398  0,                                    /* todo_flags_start */
399  TODO_dump_func | TODO_verify_rtl_sharing /* todo_flags_finish */
400 }
401};
402
403