1 /* Loop optimizer initialization routines and RTL loop optimization passes.
2 Copyright (C) 2002-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
27 #include "basic-block.h"
29 #include "tree-pass.h"
35 /* Apply FLAGS to the loop state. */
38 apply_loop_flags (unsigned flags
)
40 if (flags
& LOOPS_MAY_HAVE_MULTIPLE_LATCHES
)
42 /* If the loops may have multiple latches, we cannot canonicalize
43 them further (and most of the loop manipulation functions will
44 not work). However, we avoid modifying cfg, which some
46 gcc_assert ((flags
& ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
47 | LOOPS_HAVE_RECORDED_EXITS
)) == 0);
48 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
51 disambiguate_loops_with_multiple_latches ();
53 /* Create pre-headers. */
54 if (flags
& LOOPS_HAVE_PREHEADERS
)
56 int cp_flags
= CP_SIMPLE_PREHEADERS
;
58 if (flags
& LOOPS_HAVE_FALLTHRU_PREHEADERS
)
59 cp_flags
|= CP_FALLTHRU_PREHEADERS
;
61 create_preheaders (cp_flags
);
64 /* Force all latches to have only single successor. */
65 if (flags
& LOOPS_HAVE_SIMPLE_LATCHES
)
66 force_single_succ_latches ();
68 /* Mark irreducible loops. */
69 if (flags
& LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
70 mark_irreducible_loops ();
72 if (flags
& LOOPS_HAVE_RECORDED_EXITS
)
76 /* Initialize loop structures. This is used by the tree and RTL loop
77 optimizers. FLAGS specify what properties to compute and/or ensure for
81 loop_optimizer_init (unsigned flags
)
83 timevar_push (TV_LOOP_INIT
);
87 gcc_assert (!(cfun
->curr_properties
& PROP_loops
));
90 current_loops
= flow_loops_find (NULL
);
94 bool recorded_exits
= loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
);
96 gcc_assert (cfun
->curr_properties
& PROP_loops
);
98 /* Ensure that the dominators are computed, like flow_loops_find does. */
99 calculate_dominance_info (CDI_DOMINATORS
);
101 if (loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
103 loops_state_clear (~0U);
104 fix_loop_structure (NULL
);
107 #ifdef ENABLE_CHECKING
109 verify_loop_structure ();
112 /* Clear all flags. */
114 release_recorded_exits ();
115 loops_state_clear (~0U);
118 /* Apply flags to loops. */
119 apply_loop_flags (flags
);
122 flow_loops_dump (dump_file
, NULL
, 1);
124 #ifdef ENABLE_CHECKING
125 verify_loop_structure ();
128 timevar_pop (TV_LOOP_INIT
);
131 /* Finalize loop structures. */
134 loop_optimizer_finalize (void)
140 timevar_push (TV_LOOP_FINI
);
142 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
143 release_recorded_exits ();
145 /* If we should preserve loop structure, do not free it but clear
146 flags that advanced properties are there as we are not preserving
148 if (cfun
->curr_properties
& PROP_loops
)
150 loops_state_clear (LOOP_CLOSED_SSA
151 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
152 | LOOPS_HAVE_PREHEADERS
153 | LOOPS_HAVE_SIMPLE_LATCHES
154 | LOOPS_HAVE_FALLTHRU_PREHEADERS
);
155 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
159 gcc_assert (current_loops
!= NULL
);
161 FOR_EACH_LOOP (li
, loop
, 0)
163 free_simple_loop_desc (loop
);
167 flow_loops_free (current_loops
);
168 ggc_free (current_loops
);
169 current_loops
= NULL
;
173 bb
->loop_father
= NULL
;
177 timevar_pop (TV_LOOP_FINI
);
180 /* The structure of loops might have changed. Some loops might get removed
181 (and their headers and latches were set to NULL), loop exists might get
182 removed (thus the loop nesting may be wrong), and some blocks and edges
183 were changed (so the information about bb --> loop mapping does not have
184 to be correct). But still for the remaining loops the header dominates
185 the latch, and loops did not get new subloops (new loops might possibly
186 get created, but we are not interested in them). Fix up the mess.
188 If CHANGED_BBS is not NULL, basic blocks whose loop depth has changed are
191 Returns the number of new discovered loops. */
194 fix_loop_structure (bitmap changed_bbs
)
197 int record_exits
= 0;
200 unsigned old_nloops
, i
;
202 timevar_push (TV_LOOP_INIT
);
204 /* We need exact and fast dominance info to be available. */
205 gcc_assert (dom_info_state (CDI_DOMINATORS
) == DOM_OK
);
207 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
209 release_recorded_exits ();
210 record_exits
= LOOPS_HAVE_RECORDED_EXITS
;
213 /* Remember the depth of the blocks in the loop hierarchy, so that we can
214 recognize blocks whose loop nesting relationship has changed. */
217 bb
->aux
= (void *) (size_t) loop_depth (bb
->loop_father
);
219 /* Remove the dead loops from structures. We start from the innermost
220 loops, so that when we remove the loops, we know that the loops inside
221 are preserved, and do not waste time relinking loops that will be
223 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
225 /* Detect the case that the loop is no longer present even though
226 it wasn't marked for removal.
227 ??? If we do that we can get away with not marking loops for
228 removal at all. And possibly avoid some spurious removals. */
230 && bb_loop_header_p (loop
->header
))
233 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
234 fprintf (dump_file
, "fix_loop_structure: removing loop %d\n",
239 struct loop
*ploop
= loop
->inner
;
240 flow_loop_tree_node_remove (ploop
);
241 flow_loop_tree_node_add (loop_outer (loop
), ploop
);
244 /* Remove the loop. */
246 flow_loop_tree_node_remove (loop
);
249 /* Remember the number of loops so we can return how many new loops
250 flow_loops_find discovered. */
251 old_nloops
= number_of_loops ();
253 /* Re-compute loop structure in-place. */
254 flow_loops_find (current_loops
);
256 /* Mark the blocks whose loop has changed. */
261 if ((void *) (size_t) loop_depth (bb
->loop_father
) != bb
->aux
)
262 bitmap_set_bit (changed_bbs
, bb
->index
);
268 /* Finally free deleted loops. */
269 FOR_EACH_VEC_ELT (*get_loops (), i
, loop
)
270 if (loop
&& loop
->header
== NULL
)
272 (*get_loops ())[i
] = NULL
;
273 flow_loop_free (loop
);
276 loops_state_clear (LOOPS_NEED_FIXUP
);
278 /* Apply flags to loops. */
279 apply_loop_flags (current_loops
->state
| record_exits
);
281 #ifdef ENABLE_CHECKING
282 verify_loop_structure ();
285 timevar_pop (TV_LOOP_INIT
);
287 return number_of_loops () - old_nloops
;
290 /* Gate for the RTL loop superpass. The actual passes are subpasses.
291 See passes.c for more on that. */
294 gate_handle_loop2 (void)
297 && (flag_move_loop_invariants
298 || flag_unswitch_loops
301 #ifdef HAVE_doloop_end
302 || (flag_branch_on_count_reg
&& HAVE_doloop_end
)
308 /* No longer preserve loops, remove them now. */
309 cfun
->curr_properties
&= ~PROP_loops
;
311 loop_optimizer_finalize ();
316 struct rtl_opt_pass pass_loop2
=
321 OPTGROUP_LOOP
, /* optinfo_flags */
322 gate_handle_loop2
, /* gate */
326 0, /* static_pass_number */
328 0, /* properties_required */
329 0, /* properties_provided */
330 0, /* properties_destroyed */
331 0, /* todo_flags_start */
332 0 /* todo_flags_finish */
337 /* Initialization of the RTL loop passes. */
341 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT
);
345 dump_reg_info (dump_file
);
346 dump_flow_info (dump_file
, dump_flags
);
349 loop_optimizer_init (LOOPS_NORMAL
);
353 struct rtl_opt_pass pass_rtl_loop_init
=
357 "loop2_init", /* name */
358 OPTGROUP_LOOP
, /* optinfo_flags */
360 rtl_loop_init
, /* execute */
363 0, /* static_pass_number */
365 0, /* properties_required */
366 0, /* properties_provided */
367 0, /* properties_destroyed */
368 0, /* todo_flags_start */
369 TODO_verify_rtl_sharing
/* todo_flags_finish */
374 /* Finalization of the RTL loop passes. */
379 /* No longer preserve loops, remove them now. */
380 cfun
->curr_properties
&= ~PROP_loops
;
381 loop_optimizer_finalize ();
382 free_dominance_info (CDI_DOMINATORS
);
387 dump_reg_info (dump_file
);
388 dump_flow_info (dump_file
, dump_flags
);
394 struct rtl_opt_pass pass_rtl_loop_done
=
398 "loop2_done", /* name */
399 OPTGROUP_LOOP
, /* optinfo_flags */
401 rtl_loop_done
, /* execute */
404 0, /* static_pass_number */
406 0, /* properties_required */
407 0, /* properties_provided */
408 PROP_loops
, /* properties_destroyed */
409 0, /* todo_flags_start */
411 | TODO_verify_rtl_sharing
/* todo_flags_finish */
416 /* Loop invariant code motion. */
418 gate_rtl_move_loop_invariants (void)
420 return flag_move_loop_invariants
;
424 rtl_move_loop_invariants (void)
426 if (number_of_loops () > 1)
427 move_loop_invariants ();
431 struct rtl_opt_pass pass_rtl_move_loop_invariants
=
435 "loop2_invariant", /* name */
436 OPTGROUP_LOOP
, /* optinfo_flags */
437 gate_rtl_move_loop_invariants
, /* gate */
438 rtl_move_loop_invariants
, /* execute */
441 0, /* static_pass_number */
442 TV_LOOP_MOVE_INVARIANTS
, /* tv_id */
443 0, /* properties_required */
444 0, /* properties_provided */
445 0, /* properties_destroyed */
446 0, /* todo_flags_start */
448 TODO_df_finish
| TODO_verify_rtl_sharing
/* todo_flags_finish */
453 /* Loop unswitching for RTL. */
455 gate_rtl_unswitch (void)
457 return flag_unswitch_loops
;
463 if (number_of_loops () > 1)
468 struct rtl_opt_pass pass_rtl_unswitch
=
472 "loop2_unswitch", /* name */
473 OPTGROUP_LOOP
, /* optinfo_flags */
474 gate_rtl_unswitch
, /* gate */
475 rtl_unswitch
, /* execute */
478 0, /* static_pass_number */
479 TV_LOOP_UNSWITCH
, /* tv_id */
480 0, /* properties_required */
481 0, /* properties_provided */
482 0, /* properties_destroyed */
483 0, /* todo_flags_start */
484 TODO_verify_rtl_sharing
, /* todo_flags_finish */
489 /* Loop unswitching for RTL. */
491 gate_rtl_unroll_and_peel_loops (void)
493 return (flag_peel_loops
|| flag_unroll_loops
|| flag_unroll_all_loops
);
497 rtl_unroll_and_peel_loops (void)
499 if (number_of_loops () > 1)
507 if (flag_unroll_loops
)
509 if (flag_unroll_all_loops
)
510 flags
|= UAP_UNROLL_ALL
;
512 unroll_and_peel_loops (flags
);
517 struct rtl_opt_pass pass_rtl_unroll_and_peel_loops
=
521 "loop2_unroll", /* name */
522 OPTGROUP_LOOP
, /* optinfo_flags */
523 gate_rtl_unroll_and_peel_loops
, /* gate */
524 rtl_unroll_and_peel_loops
, /* execute */
527 0, /* static_pass_number */
528 TV_LOOP_UNROLL
, /* tv_id */
529 0, /* properties_required */
530 0, /* properties_provided */
531 0, /* properties_destroyed */
532 0, /* todo_flags_start */
533 TODO_verify_rtl_sharing
, /* todo_flags_finish */
538 /* The doloop optimization. */
540 gate_rtl_doloop (void)
542 #ifdef HAVE_doloop_end
543 return (flag_branch_on_count_reg
&& HAVE_doloop_end
);
552 #ifdef HAVE_doloop_end
553 if (number_of_loops () > 1)
554 doloop_optimize_loops ();
559 struct rtl_opt_pass pass_rtl_doloop
=
563 "loop2_doloop", /* name */
564 OPTGROUP_LOOP
, /* optinfo_flags */
565 gate_rtl_doloop
, /* gate */
566 rtl_doloop
, /* execute */
569 0, /* static_pass_number */
570 TV_LOOP_DOLOOP
, /* tv_id */
571 0, /* properties_required */
572 0, /* properties_provided */
573 0, /* properties_destroyed */
574 0, /* todo_flags_start */
575 TODO_verify_rtl_sharing
/* todo_flags_finish */