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;
189 unsigned old_nloops
, i
;
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. */
235 flow_loop_tree_node_remove (loop
);
238 /* Remember the number of loops so we can return how many new loops
239 flow_loops_find discovered. */
240 old_nloops
= number_of_loops ();
242 /* Re-compute loop structure in-place. */
243 flow_loops_find (current_loops
);
245 /* Mark the blocks whose loop has changed. */
250 if ((void *) (size_t) loop_depth (bb
->loop_father
) != bb
->aux
)
251 bitmap_set_bit (changed_bbs
, bb
->index
);
257 /* Finally free deleted loops. */
258 FOR_EACH_VEC_ELT (*get_loops (), i
, loop
)
259 if (loop
&& loop
->header
== NULL
)
261 (*get_loops ())[i
] = NULL
;
262 flow_loop_free (loop
);
265 loops_state_clear (LOOPS_NEED_FIXUP
);
267 /* Apply flags to loops. */
268 apply_loop_flags (current_loops
->state
| record_exits
);
270 #ifdef ENABLE_CHECKING
271 verify_loop_structure ();
274 timevar_pop (TV_LOOP_INIT
);
276 return number_of_loops () - old_nloops
;
279 /* Gate for the RTL loop superpass. The actual passes are subpasses.
280 See passes.c for more on that. */
283 gate_handle_loop2 (void)
286 && (flag_move_loop_invariants
287 || flag_unswitch_loops
290 #ifdef HAVE_doloop_end
291 || (flag_branch_on_count_reg
&& HAVE_doloop_end
)
297 /* No longer preserve loops, remove them now. */
298 cfun
->curr_properties
&= ~PROP_loops
;
300 loop_optimizer_finalize ();
305 struct rtl_opt_pass pass_loop2
=
310 OPTGROUP_LOOP
, /* optinfo_flags */
311 gate_handle_loop2
, /* gate */
315 0, /* static_pass_number */
317 0, /* properties_required */
318 0, /* properties_provided */
319 0, /* properties_destroyed */
320 0, /* todo_flags_start */
321 0 /* todo_flags_finish */
326 /* Initialization of the RTL loop passes. */
330 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT
);
334 dump_reg_info (dump_file
);
335 dump_flow_info (dump_file
, dump_flags
);
338 loop_optimizer_init (LOOPS_NORMAL
);
342 struct rtl_opt_pass pass_rtl_loop_init
=
346 "loop2_init", /* name */
347 OPTGROUP_LOOP
, /* optinfo_flags */
349 rtl_loop_init
, /* execute */
352 0, /* static_pass_number */
354 0, /* properties_required */
355 0, /* properties_provided */
356 0, /* properties_destroyed */
357 0, /* todo_flags_start */
358 TODO_verify_rtl_sharing
/* todo_flags_finish */
363 /* Finalization of the RTL loop passes. */
368 /* No longer preserve loops, remove them now. */
369 cfun
->curr_properties
&= ~PROP_loops
;
370 loop_optimizer_finalize ();
371 free_dominance_info (CDI_DOMINATORS
);
376 dump_reg_info (dump_file
);
377 dump_flow_info (dump_file
, dump_flags
);
383 struct rtl_opt_pass pass_rtl_loop_done
=
387 "loop2_done", /* name */
388 OPTGROUP_LOOP
, /* optinfo_flags */
390 rtl_loop_done
, /* execute */
393 0, /* static_pass_number */
395 0, /* properties_required */
396 0, /* properties_provided */
397 PROP_loops
, /* properties_destroyed */
398 0, /* todo_flags_start */
400 | TODO_verify_rtl_sharing
/* todo_flags_finish */
405 /* Loop invariant code motion. */
407 gate_rtl_move_loop_invariants (void)
409 return flag_move_loop_invariants
;
413 rtl_move_loop_invariants (void)
415 if (number_of_loops () > 1)
416 move_loop_invariants ();
420 struct rtl_opt_pass pass_rtl_move_loop_invariants
=
424 "loop2_invariant", /* name */
425 OPTGROUP_LOOP
, /* optinfo_flags */
426 gate_rtl_move_loop_invariants
, /* gate */
427 rtl_move_loop_invariants
, /* execute */
430 0, /* static_pass_number */
431 TV_LOOP_MOVE_INVARIANTS
, /* tv_id */
432 0, /* properties_required */
433 0, /* properties_provided */
434 0, /* properties_destroyed */
435 0, /* todo_flags_start */
437 TODO_df_finish
| TODO_verify_rtl_sharing
438 | TODO_do_not_ggc_collect
/* todo_flags_finish */
443 /* Loop unswitching for RTL. */
445 gate_rtl_unswitch (void)
447 return flag_unswitch_loops
;
453 if (number_of_loops () > 1)
458 struct rtl_opt_pass pass_rtl_unswitch
=
462 "loop2_unswitch", /* name */
463 OPTGROUP_LOOP
, /* optinfo_flags */
464 gate_rtl_unswitch
, /* gate */
465 rtl_unswitch
, /* execute */
468 0, /* static_pass_number */
469 TV_LOOP_UNSWITCH
, /* tv_id */
470 0, /* properties_required */
471 0, /* properties_provided */
472 0, /* properties_destroyed */
473 0, /* todo_flags_start */
474 TODO_verify_rtl_sharing
475 | TODO_do_not_ggc_collect
/* todo_flags_finish */
480 /* Loop unswitching for RTL. */
482 gate_rtl_unroll_and_peel_loops (void)
484 return (flag_peel_loops
|| flag_unroll_loops
|| flag_unroll_all_loops
);
488 rtl_unroll_and_peel_loops (void)
490 if (number_of_loops () > 1)
498 if (flag_unroll_loops
)
500 if (flag_unroll_all_loops
)
501 flags
|= UAP_UNROLL_ALL
;
503 unroll_and_peel_loops (flags
);
508 struct rtl_opt_pass pass_rtl_unroll_and_peel_loops
=
512 "loop2_unroll", /* name */
513 OPTGROUP_LOOP
, /* optinfo_flags */
514 gate_rtl_unroll_and_peel_loops
, /* gate */
515 rtl_unroll_and_peel_loops
, /* execute */
518 0, /* static_pass_number */
519 TV_LOOP_UNROLL
, /* tv_id */
520 0, /* properties_required */
521 0, /* properties_provided */
522 0, /* properties_destroyed */
523 0, /* todo_flags_start */
524 TODO_verify_rtl_sharing
525 | TODO_do_not_ggc_collect
/* todo_flags_finish */
530 /* The doloop optimization. */
532 gate_rtl_doloop (void)
534 #ifdef HAVE_doloop_end
535 return (flag_branch_on_count_reg
&& HAVE_doloop_end
);
544 #ifdef HAVE_doloop_end
545 if (number_of_loops () > 1)
546 doloop_optimize_loops ();
551 struct rtl_opt_pass pass_rtl_doloop
=
555 "loop2_doloop", /* name */
556 OPTGROUP_LOOP
, /* optinfo_flags */
557 gate_rtl_doloop
, /* gate */
558 rtl_doloop
, /* execute */
561 0, /* static_pass_number */
562 TV_LOOP_DOLOOP
, /* tv_id */
563 0, /* properties_required */
564 0, /* properties_provided */
565 0, /* properties_destroyed */
566 0, /* todo_flags_start */
567 TODO_verify_rtl_sharing
568 | TODO_do_not_ggc_collect
/* todo_flags_finish */