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