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"
33 #include "tree-flow.h"
36 /* Apply FLAGS to the loop state. */
39 apply_loop_flags (unsigned flags
)
41 if (flags
& LOOPS_MAY_HAVE_MULTIPLE_LATCHES
)
43 /* If the loops may have multiple latches, we cannot canonicalize
44 them further (and most of the loop manipulation functions will
45 not work). However, we avoid modifying cfg, which some
47 gcc_assert ((flags
& ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
48 | LOOPS_HAVE_RECORDED_EXITS
)) == 0);
49 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
52 disambiguate_loops_with_multiple_latches ();
54 /* Create pre-headers. */
55 if (flags
& LOOPS_HAVE_PREHEADERS
)
57 int cp_flags
= CP_SIMPLE_PREHEADERS
;
59 if (flags
& LOOPS_HAVE_FALLTHRU_PREHEADERS
)
60 cp_flags
|= CP_FALLTHRU_PREHEADERS
;
62 create_preheaders (cp_flags
);
65 /* Force all latches to have only single successor. */
66 if (flags
& LOOPS_HAVE_SIMPLE_LATCHES
)
67 force_single_succ_latches ();
69 /* Mark irreducible loops. */
70 if (flags
& LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
71 mark_irreducible_loops ();
73 if (flags
& LOOPS_HAVE_RECORDED_EXITS
)
77 /* Initialize loop structures. This is used by the tree and RTL loop
78 optimizers. FLAGS specify what properties to compute and/or ensure for
82 loop_optimizer_init (unsigned flags
)
84 timevar_push (TV_LOOP_INIT
);
88 gcc_assert (!(cfun
->curr_properties
& PROP_loops
));
91 current_loops
= flow_loops_find (NULL
);
95 bool recorded_exits
= loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
);
97 gcc_assert (cfun
->curr_properties
& PROP_loops
);
99 /* Ensure that the dominators are computed, like flow_loops_find does. */
100 calculate_dominance_info (CDI_DOMINATORS
);
102 if (loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
104 loops_state_clear (~0U);
105 fix_loop_structure (NULL
);
108 #ifdef ENABLE_CHECKING
110 verify_loop_structure ();
113 /* Clear all flags. */
115 release_recorded_exits ();
116 loops_state_clear (~0U);
119 /* Apply flags to loops. */
120 apply_loop_flags (flags
);
123 flow_loops_dump (dump_file
, NULL
, 1);
125 #ifdef ENABLE_CHECKING
126 verify_loop_structure ();
129 timevar_pop (TV_LOOP_INIT
);
132 /* Finalize loop structures. */
135 loop_optimizer_finalize (void)
141 timevar_push (TV_LOOP_FINI
);
143 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
144 release_recorded_exits ();
146 free_numbers_of_iterations_estimates ();
148 /* If we should preserve loop structure, do not free it but clear
149 flags that advanced properties are there as we are not preserving
151 if (cfun
->curr_properties
& PROP_loops
)
153 loops_state_clear (LOOP_CLOSED_SSA
154 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
155 | LOOPS_HAVE_PREHEADERS
156 | LOOPS_HAVE_SIMPLE_LATCHES
157 | LOOPS_HAVE_FALLTHRU_PREHEADERS
);
158 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
162 gcc_assert (current_loops
!= NULL
);
164 FOR_EACH_LOOP (li
, loop
, 0)
166 free_simple_loop_desc (loop
);
170 flow_loops_free (current_loops
);
171 ggc_free (current_loops
);
172 current_loops
= NULL
;
176 bb
->loop_father
= NULL
;
180 timevar_pop (TV_LOOP_FINI
);
183 /* The structure of loops might have changed. Some loops might get removed
184 (and their headers and latches were set to NULL), loop exists might get
185 removed (thus the loop nesting may be wrong), and some blocks and edges
186 were changed (so the information about bb --> loop mapping does not have
187 to be correct). But still for the remaining loops the header dominates
188 the latch, and loops did not get new subloops (new loops might possibly
189 get created, but we are not interested in them). Fix up the mess.
191 If CHANGED_BBS is not NULL, basic blocks whose loop depth has changed are
194 Returns the number of new discovered loops. */
197 fix_loop_structure (bitmap changed_bbs
)
200 int record_exits
= 0;
203 unsigned old_nloops
, i
;
205 timevar_push (TV_LOOP_INIT
);
207 /* We need exact and fast dominance info to be available. */
208 gcc_assert (dom_info_state (CDI_DOMINATORS
) == DOM_OK
);
210 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
212 release_recorded_exits ();
213 record_exits
= LOOPS_HAVE_RECORDED_EXITS
;
216 /* Remember the depth of the blocks in the loop hierarchy, so that we can
217 recognize blocks whose loop nesting relationship has changed. */
220 bb
->aux
= (void *) (size_t) loop_depth (bb
->loop_father
);
222 /* Remove the dead loops from structures. We start from the innermost
223 loops, so that when we remove the loops, we know that the loops inside
224 are preserved, and do not waste time relinking loops that will be
226 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
228 /* Detect the case that the loop is no longer present even though
229 it wasn't marked for removal.
230 ??? If we do that we can get away with not marking loops for
231 removal at all. And possibly avoid some spurious removals. */
233 && bb_loop_header_p (loop
->header
))
236 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
237 fprintf (dump_file
, "fix_loop_structure: removing loop %d\n",
242 struct loop
*ploop
= loop
->inner
;
243 flow_loop_tree_node_remove (ploop
);
244 flow_loop_tree_node_add (loop_outer (loop
), ploop
);
247 /* Remove the loop. */
249 flow_loop_tree_node_remove (loop
);
252 /* Remember the number of loops so we can return how many new loops
253 flow_loops_find discovered. */
254 old_nloops
= number_of_loops (cfun
);
256 /* Re-compute loop structure in-place. */
257 flow_loops_find (current_loops
);
259 /* Mark the blocks whose loop has changed. */
264 if ((void *) (size_t) loop_depth (bb
->loop_father
) != bb
->aux
)
265 bitmap_set_bit (changed_bbs
, bb
->index
);
271 /* Finally free deleted loops. */
272 FOR_EACH_VEC_ELT (*get_loops (cfun
), i
, loop
)
273 if (loop
&& loop
->header
== NULL
)
275 (*get_loops (cfun
))[i
] = NULL
;
276 flow_loop_free (loop
);
279 loops_state_clear (LOOPS_NEED_FIXUP
);
281 /* Apply flags to loops. */
282 apply_loop_flags (current_loops
->state
| record_exits
);
284 #ifdef ENABLE_CHECKING
285 verify_loop_structure ();
288 timevar_pop (TV_LOOP_INIT
);
290 return number_of_loops (cfun
) - old_nloops
;
293 /* Gate for the RTL loop superpass. The actual passes are subpasses.
294 See passes.c for more on that. */
297 gate_handle_loop2 (void)
300 && (flag_move_loop_invariants
301 || flag_unswitch_loops
304 #ifdef HAVE_doloop_end
305 || (flag_branch_on_count_reg
&& HAVE_doloop_end
)
311 /* No longer preserve loops, remove them now. */
312 cfun
->curr_properties
&= ~PROP_loops
;
314 loop_optimizer_finalize ();
319 struct rtl_opt_pass pass_loop2
=
324 OPTGROUP_LOOP
, /* optinfo_flags */
325 gate_handle_loop2
, /* gate */
329 0, /* static_pass_number */
331 0, /* properties_required */
332 0, /* properties_provided */
333 0, /* properties_destroyed */
334 0, /* todo_flags_start */
335 0 /* todo_flags_finish */
340 /* Initialization of the RTL loop passes. */
344 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT
);
348 dump_reg_info (dump_file
);
349 dump_flow_info (dump_file
, dump_flags
);
352 loop_optimizer_init (LOOPS_NORMAL
);
356 struct rtl_opt_pass pass_rtl_loop_init
=
360 "loop2_init", /* name */
361 OPTGROUP_LOOP
, /* optinfo_flags */
363 rtl_loop_init
, /* execute */
366 0, /* static_pass_number */
368 0, /* properties_required */
369 0, /* properties_provided */
370 0, /* properties_destroyed */
371 0, /* todo_flags_start */
372 TODO_verify_rtl_sharing
/* todo_flags_finish */
377 /* Finalization of the RTL loop passes. */
382 /* No longer preserve loops, remove them now. */
383 cfun
->curr_properties
&= ~PROP_loops
;
384 loop_optimizer_finalize ();
385 free_dominance_info (CDI_DOMINATORS
);
390 dump_reg_info (dump_file
);
391 dump_flow_info (dump_file
, dump_flags
);
397 struct rtl_opt_pass pass_rtl_loop_done
=
401 "loop2_done", /* name */
402 OPTGROUP_LOOP
, /* optinfo_flags */
404 rtl_loop_done
, /* execute */
407 0, /* static_pass_number */
409 0, /* properties_required */
410 0, /* properties_provided */
411 PROP_loops
, /* properties_destroyed */
412 0, /* todo_flags_start */
414 | TODO_verify_rtl_sharing
/* todo_flags_finish */
419 /* Loop invariant code motion. */
421 gate_rtl_move_loop_invariants (void)
423 return flag_move_loop_invariants
;
427 rtl_move_loop_invariants (void)
429 if (number_of_loops (cfun
) > 1)
430 move_loop_invariants ();
434 struct rtl_opt_pass pass_rtl_move_loop_invariants
=
438 "loop2_invariant", /* name */
439 OPTGROUP_LOOP
, /* optinfo_flags */
440 gate_rtl_move_loop_invariants
, /* gate */
441 rtl_move_loop_invariants
, /* execute */
444 0, /* static_pass_number */
445 TV_LOOP_MOVE_INVARIANTS
, /* tv_id */
446 0, /* properties_required */
447 0, /* properties_provided */
448 0, /* properties_destroyed */
449 0, /* todo_flags_start */
451 TODO_df_finish
| TODO_verify_rtl_sharing
/* todo_flags_finish */
456 /* Loop unswitching for RTL. */
458 gate_rtl_unswitch (void)
460 return flag_unswitch_loops
;
466 if (number_of_loops (cfun
) > 1)
471 struct rtl_opt_pass pass_rtl_unswitch
=
475 "loop2_unswitch", /* name */
476 OPTGROUP_LOOP
, /* optinfo_flags */
477 gate_rtl_unswitch
, /* gate */
478 rtl_unswitch
, /* execute */
481 0, /* static_pass_number */
482 TV_LOOP_UNSWITCH
, /* tv_id */
483 0, /* properties_required */
484 0, /* properties_provided */
485 0, /* properties_destroyed */
486 0, /* todo_flags_start */
487 TODO_verify_rtl_sharing
, /* todo_flags_finish */
492 /* Loop unswitching for RTL. */
494 gate_rtl_unroll_and_peel_loops (void)
496 return (flag_peel_loops
|| flag_unroll_loops
|| flag_unroll_all_loops
);
500 rtl_unroll_and_peel_loops (void)
502 if (number_of_loops (cfun
) > 1)
510 if (flag_unroll_loops
)
512 if (flag_unroll_all_loops
)
513 flags
|= UAP_UNROLL_ALL
;
515 unroll_and_peel_loops (flags
);
520 struct rtl_opt_pass pass_rtl_unroll_and_peel_loops
=
524 "loop2_unroll", /* name */
525 OPTGROUP_LOOP
, /* optinfo_flags */
526 gate_rtl_unroll_and_peel_loops
, /* gate */
527 rtl_unroll_and_peel_loops
, /* execute */
530 0, /* static_pass_number */
531 TV_LOOP_UNROLL
, /* tv_id */
532 0, /* properties_required */
533 0, /* properties_provided */
534 0, /* properties_destroyed */
535 0, /* todo_flags_start */
536 TODO_verify_rtl_sharing
, /* todo_flags_finish */
541 /* The doloop optimization. */
543 gate_rtl_doloop (void)
545 #ifdef HAVE_doloop_end
546 return (flag_branch_on_count_reg
&& HAVE_doloop_end
);
555 #ifdef HAVE_doloop_end
556 if (number_of_loops (cfun
) > 1)
557 doloop_optimize_loops ();
562 struct rtl_opt_pass pass_rtl_doloop
=
566 "loop2_doloop", /* name */
567 OPTGROUP_LOOP
, /* optinfo_flags */
568 gate_rtl_doloop
, /* gate */
569 rtl_doloop
, /* execute */
572 0, /* static_pass_number */
573 TV_LOOP_DOLOOP
, /* tv_id */
574 0, /* properties_required */
575 0, /* properties_provided */
576 0, /* properties_destroyed */
577 0, /* todo_flags_start */
578 TODO_verify_rtl_sharing
/* todo_flags_finish */