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 gcc_assert (cfun
->curr_properties
& PROP_loops
);
96 /* Ensure that the dominators are computed, like flow_loops_find does. */
97 calculate_dominance_info (CDI_DOMINATORS
);
99 #ifdef ENABLE_CHECKING
100 verify_loop_structure ();
103 /* Clear all flags. */
104 loops_state_clear (~0U);
107 /* Apply flags to loops. */
108 apply_loop_flags (flags
);
111 flow_loops_dump (dump_file
, NULL
, 1);
113 #ifdef ENABLE_CHECKING
114 verify_loop_structure ();
117 timevar_pop (TV_LOOP_INIT
);
120 /* Finalize loop structures. */
123 loop_optimizer_finalize (void)
129 timevar_push (TV_LOOP_FINI
);
131 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
132 release_recorded_exits ();
134 /* If we should preserve loop structure, do not free it but clear
135 flags that advanced properties are there as we are not preserving
137 if (cfun
->curr_properties
& PROP_loops
)
139 loops_state_clear (LOOP_CLOSED_SSA
140 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
141 | LOOPS_HAVE_PREHEADERS
142 | LOOPS_HAVE_SIMPLE_LATCHES
143 | LOOPS_HAVE_FALLTHRU_PREHEADERS
);
144 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
148 gcc_assert (current_loops
!= NULL
);
150 FOR_EACH_LOOP (li
, loop
, 0)
152 free_simple_loop_desc (loop
);
156 flow_loops_free (current_loops
);
157 ggc_free (current_loops
);
158 current_loops
= NULL
;
162 bb
->loop_father
= NULL
;
166 timevar_pop (TV_LOOP_FINI
);
169 /* The structure of loops might have changed. Some loops might get removed
170 (and their headers and latches were set to NULL), loop exists might get
171 removed (thus the loop nesting may be wrong), and some blocks and edges
172 were changed (so the information about bb --> loop mapping does not have
173 to be correct). But still for the remaining loops the header dominates
174 the latch, and loops did not get new subloops (new loops might possibly
175 get created, but we are not interested in them). Fix up the mess.
177 If CHANGED_BBS is not NULL, basic blocks whose loop depth has changed are
180 Returns the number of new discovered loops. */
183 fix_loop_structure (bitmap changed_bbs
)
186 int record_exits
= 0;
191 timevar_push (TV_LOOP_INIT
);
193 /* We need exact and fast dominance info to be available. */
194 gcc_assert (dom_info_state (CDI_DOMINATORS
) == DOM_OK
);
196 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
198 release_recorded_exits ();
199 record_exits
= LOOPS_HAVE_RECORDED_EXITS
;
202 /* Remember the depth of the blocks in the loop hierarchy, so that we can
203 recognize blocks whose loop nesting relationship has changed. */
206 bb
->aux
= (void *) (size_t) loop_depth (bb
->loop_father
);
208 /* Remove the dead loops from structures. We start from the innermost
209 loops, so that when we remove the loops, we know that the loops inside
210 are preserved, and do not waste time relinking loops that will be
212 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
214 /* Detect the case that the loop is no longer present even though
215 it wasn't marked for removal.
216 ??? If we do that we can get away with not marking loops for
217 removal at all. And possibly avoid some spurious removals. */
219 && bb_loop_header_p (loop
->header
))
222 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
223 fprintf (dump_file
, "fix_loop_structure: removing loop %d\n",
228 struct loop
*ploop
= loop
->inner
;
229 flow_loop_tree_node_remove (ploop
);
230 flow_loop_tree_node_add (loop_outer (loop
), ploop
);
233 /* Remove the loop and free its data. */
237 /* Remember the number of loops so we can return how many new loops
238 flow_loops_find discovered. */
239 old_nloops
= number_of_loops ();
241 /* Re-compute loop structure in-place. */
242 flow_loops_find (current_loops
);
244 /* Mark the blocks whose loop has changed. */
249 if ((void *) (size_t) loop_depth (bb
->loop_father
) != bb
->aux
)
250 bitmap_set_bit (changed_bbs
, bb
->index
);
256 loops_state_clear (LOOPS_NEED_FIXUP
);
258 /* Apply flags to loops. */
259 apply_loop_flags (current_loops
->state
| record_exits
);
261 #ifdef ENABLE_CHECKING
262 verify_loop_structure ();
265 timevar_pop (TV_LOOP_INIT
);
267 return number_of_loops () - old_nloops
;
270 /* Gate for the RTL loop superpass. The actual passes are subpasses.
271 See passes.c for more on that. */
274 gate_handle_loop2 (void)
277 && (flag_move_loop_invariants
278 || flag_unswitch_loops
281 #ifdef HAVE_doloop_end
282 || (flag_branch_on_count_reg
&& HAVE_doloop_end
)
288 /* No longer preserve loops, remove them now. */
289 cfun
->curr_properties
&= ~PROP_loops
;
291 loop_optimizer_finalize ();
296 struct rtl_opt_pass pass_loop2
=
301 OPTGROUP_LOOP
, /* optinfo_flags */
302 gate_handle_loop2
, /* gate */
306 0, /* static_pass_number */
308 0, /* properties_required */
309 0, /* properties_provided */
310 0, /* properties_destroyed */
311 0, /* todo_flags_start */
312 TODO_ggc_collect
/* todo_flags_finish */
317 /* Initialization of the RTL loop passes. */
321 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT
);
325 dump_reg_info (dump_file
);
326 dump_flow_info (dump_file
, dump_flags
);
329 loop_optimizer_init (LOOPS_NORMAL
);
333 struct rtl_opt_pass pass_rtl_loop_init
=
337 "loop2_init", /* name */
338 OPTGROUP_LOOP
, /* optinfo_flags */
340 rtl_loop_init
, /* execute */
343 0, /* static_pass_number */
345 0, /* properties_required */
346 0, /* properties_provided */
347 0, /* properties_destroyed */
348 0, /* todo_flags_start */
349 TODO_verify_rtl_sharing
/* todo_flags_finish */
354 /* Finalization of the RTL loop passes. */
359 /* No longer preserve loops, remove them now. */
360 cfun
->curr_properties
&= ~PROP_loops
;
361 loop_optimizer_finalize ();
362 free_dominance_info (CDI_DOMINATORS
);
367 dump_reg_info (dump_file
);
368 dump_flow_info (dump_file
, dump_flags
);
374 struct rtl_opt_pass pass_rtl_loop_done
=
378 "loop2_done", /* name */
379 OPTGROUP_LOOP
, /* optinfo_flags */
381 rtl_loop_done
, /* execute */
384 0, /* static_pass_number */
386 0, /* properties_required */
387 0, /* properties_provided */
388 PROP_loops
, /* properties_destroyed */
389 0, /* todo_flags_start */
391 | TODO_verify_rtl_sharing
/* todo_flags_finish */
396 /* Loop invariant code motion. */
398 gate_rtl_move_loop_invariants (void)
400 return flag_move_loop_invariants
;
404 rtl_move_loop_invariants (void)
406 if (number_of_loops () > 1)
407 move_loop_invariants ();
411 struct rtl_opt_pass pass_rtl_move_loop_invariants
=
415 "loop2_invariant", /* name */
416 OPTGROUP_LOOP
, /* optinfo_flags */
417 gate_rtl_move_loop_invariants
, /* gate */
418 rtl_move_loop_invariants
, /* execute */
421 0, /* static_pass_number */
422 TV_LOOP_MOVE_INVARIANTS
, /* tv_id */
423 0, /* properties_required */
424 0, /* properties_provided */
425 0, /* properties_destroyed */
426 0, /* todo_flags_start */
428 TODO_df_finish
| TODO_verify_rtl_sharing
/* todo_flags_finish */
433 /* Loop unswitching for RTL. */
435 gate_rtl_unswitch (void)
437 return flag_unswitch_loops
;
443 if (number_of_loops () > 1)
448 struct rtl_opt_pass pass_rtl_unswitch
=
452 "loop2_unswitch", /* name */
453 OPTGROUP_LOOP
, /* optinfo_flags */
454 gate_rtl_unswitch
, /* gate */
455 rtl_unswitch
, /* execute */
458 0, /* static_pass_number */
459 TV_LOOP_UNSWITCH
, /* tv_id */
460 0, /* properties_required */
461 0, /* properties_provided */
462 0, /* properties_destroyed */
463 0, /* todo_flags_start */
464 TODO_verify_rtl_sharing
, /* todo_flags_finish */
469 /* Loop unswitching for RTL. */
471 gate_rtl_unroll_and_peel_loops (void)
473 return (flag_peel_loops
|| flag_unroll_loops
|| flag_unroll_all_loops
);
477 rtl_unroll_and_peel_loops (void)
479 if (number_of_loops () > 1)
487 if (flag_unroll_loops
)
489 if (flag_unroll_all_loops
)
490 flags
|= UAP_UNROLL_ALL
;
492 unroll_and_peel_loops (flags
);
497 struct rtl_opt_pass pass_rtl_unroll_and_peel_loops
=
501 "loop2_unroll", /* name */
502 OPTGROUP_LOOP
, /* optinfo_flags */
503 gate_rtl_unroll_and_peel_loops
, /* gate */
504 rtl_unroll_and_peel_loops
, /* execute */
507 0, /* static_pass_number */
508 TV_LOOP_UNROLL
, /* tv_id */
509 0, /* properties_required */
510 0, /* properties_provided */
511 0, /* properties_destroyed */
512 0, /* todo_flags_start */
513 TODO_verify_rtl_sharing
, /* todo_flags_finish */
518 /* The doloop optimization. */
520 gate_rtl_doloop (void)
522 #ifdef HAVE_doloop_end
523 return (flag_branch_on_count_reg
&& HAVE_doloop_end
);
532 #ifdef HAVE_doloop_end
533 if (number_of_loops () > 1)
534 doloop_optimize_loops ();
539 struct rtl_opt_pass pass_rtl_doloop
=
543 "loop2_doloop", /* name */
544 OPTGROUP_LOOP
, /* optinfo_flags */
545 gate_rtl_doloop
, /* gate */
546 rtl_doloop
, /* execute */
549 0, /* static_pass_number */
550 TV_LOOP_DOLOOP
, /* tv_id */
551 0, /* properties_required */
552 0, /* properties_provided */
553 0, /* properties_destroyed */
554 0, /* todo_flags_start */
555 TODO_verify_rtl_sharing
/* todo_flags_finish */