1 /* Loop optimizer initialization routines and RTL loop optimization passes.
2 Copyright (C) 2002-2014 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"
28 #include "basic-block.h"
30 #include "tree-pass.h"
34 #include "tree-ssa-loop-niter.h"
37 /* Apply FLAGS to the loop state. */
40 apply_loop_flags (unsigned flags
)
42 if (flags
& LOOPS_MAY_HAVE_MULTIPLE_LATCHES
)
44 /* If the loops may have multiple latches, we cannot canonicalize
45 them further (and most of the loop manipulation functions will
46 not work). However, we avoid modifying cfg, which some
48 gcc_assert ((flags
& ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
49 | LOOPS_HAVE_RECORDED_EXITS
)) == 0);
50 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
53 disambiguate_loops_with_multiple_latches ();
55 /* Create pre-headers. */
56 if (flags
& LOOPS_HAVE_PREHEADERS
)
58 int cp_flags
= CP_SIMPLE_PREHEADERS
;
60 if (flags
& LOOPS_HAVE_FALLTHRU_PREHEADERS
)
61 cp_flags
|= CP_FALLTHRU_PREHEADERS
;
63 create_preheaders (cp_flags
);
66 /* Force all latches to have only single successor. */
67 if (flags
& LOOPS_HAVE_SIMPLE_LATCHES
)
68 force_single_succ_latches ();
70 /* Mark irreducible loops. */
71 if (flags
& LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
72 mark_irreducible_loops ();
74 if (flags
& LOOPS_HAVE_RECORDED_EXITS
)
78 /* Initialize loop structures. This is used by the tree and RTL loop
79 optimizers. FLAGS specify what properties to compute and/or ensure for
83 loop_optimizer_init (unsigned flags
)
85 timevar_push (TV_LOOP_INIT
);
89 gcc_assert (!(cfun
->curr_properties
& PROP_loops
));
92 current_loops
= flow_loops_find (NULL
);
96 bool recorded_exits
= loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
);
97 bool needs_fixup
= loops_state_satisfies_p (LOOPS_NEED_FIXUP
);
99 gcc_assert (cfun
->curr_properties
& PROP_loops
);
101 /* Ensure that the dominators are computed, like flow_loops_find does. */
102 calculate_dominance_info (CDI_DOMINATORS
);
104 #ifdef ENABLE_CHECKING
106 verify_loop_structure ();
109 /* Clear all flags. */
111 release_recorded_exits ();
112 loops_state_clear (~0U);
116 /* Apply LOOPS_MAY_HAVE_MULTIPLE_LATCHES early as fix_loop_structure
118 loops_state_set (flags
& LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
119 fix_loop_structure (NULL
);
123 /* Apply flags to loops. */
124 apply_loop_flags (flags
);
127 flow_loops_dump (dump_file
, NULL
, 1);
129 #ifdef ENABLE_CHECKING
130 verify_loop_structure ();
133 timevar_pop (TV_LOOP_INIT
);
136 /* Finalize loop structures. */
139 loop_optimizer_finalize (void)
144 timevar_push (TV_LOOP_FINI
);
146 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
147 release_recorded_exits ();
149 free_numbers_of_iterations_estimates ();
151 /* If we should preserve loop structure, do not free it but clear
152 flags that advanced properties are there as we are not preserving
154 if (cfun
->curr_properties
& PROP_loops
)
156 loops_state_clear (LOOP_CLOSED_SSA
157 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
158 | LOOPS_HAVE_PREHEADERS
159 | LOOPS_HAVE_SIMPLE_LATCHES
160 | LOOPS_HAVE_FALLTHRU_PREHEADERS
);
161 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
);
165 gcc_assert (current_loops
!= NULL
);
167 FOR_EACH_LOOP (loop
, 0)
168 free_simple_loop_desc (loop
);
171 flow_loops_free (current_loops
);
172 ggc_free (current_loops
);
173 current_loops
= NULL
;
175 FOR_ALL_BB_FN (bb
, cfun
)
177 bb
->loop_father
= NULL
;
181 timevar_pop (TV_LOOP_FINI
);
184 /* The structure of loops might have changed. Some loops might get removed
185 (and their headers and latches were set to NULL), loop exists might get
186 removed (thus the loop nesting may be wrong), and some blocks and edges
187 were changed (so the information about bb --> loop mapping does not have
188 to be correct). But still for the remaining loops the header dominates
189 the latch, and loops did not get new subloops (new loops might possibly
190 get created, but we are not interested in them). Fix up the mess.
192 If CHANGED_BBS is not NULL, basic blocks whose loop depth has changed are
195 Returns the number of new discovered loops. */
198 fix_loop_structure (bitmap changed_bbs
)
201 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. */
219 FOR_EACH_BB_FN (bb
, cfun
)
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 (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 loop
->former_header
= loop
->header
;
251 gcc_assert (loop
->former_header
!= NULL
);
253 flow_loop_tree_node_remove (loop
);
256 /* Remember the number of loops so we can return how many new loops
257 flow_loops_find discovered. */
258 old_nloops
= number_of_loops (cfun
);
260 /* Re-compute loop structure in-place. */
261 flow_loops_find (current_loops
);
263 /* Mark the blocks whose loop has changed. */
266 FOR_EACH_BB_FN (bb
, cfun
)
268 if ((void *) (size_t) loop_depth (bb
->loop_father
) != bb
->aux
)
269 bitmap_set_bit (changed_bbs
, bb
->index
);
275 /* Finally free deleted loops. */
276 FOR_EACH_VEC_ELT (*get_loops (cfun
), i
, loop
)
277 if (loop
&& loop
->header
== NULL
)
280 && ((unsigned) loop
->former_header
->index
281 < basic_block_info_for_fn (cfun
)->length ()))
283 basic_block former_header
284 = BASIC_BLOCK_FOR_FN (cfun
, loop
->former_header
->index
);
285 /* If the old header still exists we want to check if the
286 original loop is re-discovered or the old header is now
287 part of a newly discovered loop.
288 In both cases we should have avoided removing the loop. */
289 if (former_header
== loop
->former_header
)
291 if (former_header
->loop_father
->header
== former_header
)
292 fprintf (dump_file
, "fix_loop_structure: rediscovered "
293 "removed loop %d as loop %d with old header %d\n",
294 loop
->num
, former_header
->loop_father
->num
,
295 former_header
->index
);
296 else if ((unsigned) former_header
->loop_father
->num
298 fprintf (dump_file
, "fix_loop_structure: header %d of "
299 "removed loop %d is part of the newly "
300 "discovered loop %d with header %d\n",
301 former_header
->index
, loop
->num
,
302 former_header
->loop_father
->num
,
303 former_header
->loop_father
->header
->index
);
306 (*get_loops (cfun
))[i
] = NULL
;
307 flow_loop_free (loop
);
310 loops_state_clear (LOOPS_NEED_FIXUP
);
312 /* Apply flags to loops. */
313 apply_loop_flags (current_loops
->state
| record_exits
);
315 #ifdef ENABLE_CHECKING
316 verify_loop_structure ();
319 timevar_pop (TV_LOOP_INIT
);
321 return number_of_loops (cfun
) - old_nloops
;
324 /* Gate for the RTL loop superpass. The actual passes are subpasses.
325 See passes.c for more on that. */
328 gate_handle_loop2 (void)
331 && (flag_move_loop_invariants
332 || flag_unswitch_loops
335 #ifdef HAVE_doloop_end
336 || (flag_branch_on_count_reg
&& HAVE_doloop_end
)
342 /* No longer preserve loops, remove them now. */
343 cfun
->curr_properties
&= ~PROP_loops
;
345 loop_optimizer_finalize ();
352 const pass_data pass_data_loop2
=
356 OPTGROUP_LOOP
, /* optinfo_flags */
358 false, /* has_execute */
360 0, /* properties_required */
361 0, /* properties_provided */
362 0, /* properties_destroyed */
363 0, /* todo_flags_start */
364 0, /* todo_flags_finish */
367 class pass_loop2
: public rtl_opt_pass
370 pass_loop2 (gcc::context
*ctxt
)
371 : rtl_opt_pass (pass_data_loop2
, ctxt
)
374 /* opt_pass methods: */
375 bool gate () { return gate_handle_loop2 (); }
377 }; // class pass_loop2
382 make_pass_loop2 (gcc::context
*ctxt
)
384 return new pass_loop2 (ctxt
);
388 /* Initialization of the RTL loop passes. */
392 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT
);
396 dump_reg_info (dump_file
);
397 dump_flow_info (dump_file
, dump_flags
);
400 loop_optimizer_init (LOOPS_NORMAL
);
406 const pass_data pass_data_rtl_loop_init
=
409 "loop2_init", /* name */
410 OPTGROUP_LOOP
, /* optinfo_flags */
411 false, /* has_gate */
412 true, /* has_execute */
414 0, /* properties_required */
415 0, /* properties_provided */
416 0, /* properties_destroyed */
417 0, /* todo_flags_start */
418 TODO_verify_rtl_sharing
, /* todo_flags_finish */
421 class pass_rtl_loop_init
: public rtl_opt_pass
424 pass_rtl_loop_init (gcc::context
*ctxt
)
425 : rtl_opt_pass (pass_data_rtl_loop_init
, ctxt
)
428 /* opt_pass methods: */
429 unsigned int execute () { return rtl_loop_init (); }
431 }; // class pass_rtl_loop_init
436 make_pass_rtl_loop_init (gcc::context
*ctxt
)
438 return new pass_rtl_loop_init (ctxt
);
442 /* Finalization of the RTL loop passes. */
447 /* No longer preserve loops, remove them now. */
448 cfun
->curr_properties
&= ~PROP_loops
;
449 loop_optimizer_finalize ();
450 free_dominance_info (CDI_DOMINATORS
);
455 dump_reg_info (dump_file
);
456 dump_flow_info (dump_file
, dump_flags
);
464 const pass_data pass_data_rtl_loop_done
=
467 "loop2_done", /* name */
468 OPTGROUP_LOOP
, /* optinfo_flags */
469 false, /* has_gate */
470 true, /* has_execute */
472 0, /* properties_required */
473 0, /* properties_provided */
474 PROP_loops
, /* properties_destroyed */
475 0, /* todo_flags_start */
476 ( TODO_verify_flow
| TODO_verify_rtl_sharing
), /* todo_flags_finish */
479 class pass_rtl_loop_done
: public rtl_opt_pass
482 pass_rtl_loop_done (gcc::context
*ctxt
)
483 : rtl_opt_pass (pass_data_rtl_loop_done
, ctxt
)
486 /* opt_pass methods: */
487 unsigned int execute () { return rtl_loop_done (); }
489 }; // class pass_rtl_loop_done
494 make_pass_rtl_loop_done (gcc::context
*ctxt
)
496 return new pass_rtl_loop_done (ctxt
);
500 /* Loop invariant code motion. */
502 gate_rtl_move_loop_invariants (void)
504 return flag_move_loop_invariants
;
508 rtl_move_loop_invariants (void)
510 if (number_of_loops (cfun
) > 1)
511 move_loop_invariants ();
517 const pass_data pass_data_rtl_move_loop_invariants
=
520 "loop2_invariant", /* name */
521 OPTGROUP_LOOP
, /* optinfo_flags */
523 true, /* has_execute */
524 TV_LOOP_MOVE_INVARIANTS
, /* tv_id */
525 0, /* properties_required */
526 0, /* properties_provided */
527 0, /* properties_destroyed */
528 0, /* todo_flags_start */
529 ( TODO_df_verify
| TODO_df_finish
530 | TODO_verify_rtl_sharing
), /* todo_flags_finish */
533 class pass_rtl_move_loop_invariants
: public rtl_opt_pass
536 pass_rtl_move_loop_invariants (gcc::context
*ctxt
)
537 : rtl_opt_pass (pass_data_rtl_move_loop_invariants
, ctxt
)
540 /* opt_pass methods: */
541 bool gate () { return gate_rtl_move_loop_invariants (); }
542 unsigned int execute () { return rtl_move_loop_invariants (); }
544 }; // class pass_rtl_move_loop_invariants
549 make_pass_rtl_move_loop_invariants (gcc::context
*ctxt
)
551 return new pass_rtl_move_loop_invariants (ctxt
);
555 /* Loop unswitching for RTL. */
557 gate_rtl_unswitch (void)
559 return flag_unswitch_loops
;
565 if (number_of_loops (cfun
) > 1)
572 const pass_data pass_data_rtl_unswitch
=
575 "loop2_unswitch", /* name */
576 OPTGROUP_LOOP
, /* optinfo_flags */
578 true, /* has_execute */
579 TV_LOOP_UNSWITCH
, /* tv_id */
580 0, /* properties_required */
581 0, /* properties_provided */
582 0, /* properties_destroyed */
583 0, /* todo_flags_start */
584 TODO_verify_rtl_sharing
, /* todo_flags_finish */
587 class pass_rtl_unswitch
: public rtl_opt_pass
590 pass_rtl_unswitch (gcc::context
*ctxt
)
591 : rtl_opt_pass (pass_data_rtl_unswitch
, ctxt
)
594 /* opt_pass methods: */
595 bool gate () { return gate_rtl_unswitch (); }
596 unsigned int execute () { return rtl_unswitch (); }
598 }; // class pass_rtl_unswitch
603 make_pass_rtl_unswitch (gcc::context
*ctxt
)
605 return new pass_rtl_unswitch (ctxt
);
609 /* Loop unswitching for RTL. */
611 gate_rtl_unroll_and_peel_loops (void)
613 return (flag_peel_loops
|| flag_unroll_loops
|| flag_unroll_all_loops
);
617 rtl_unroll_and_peel_loops (void)
619 if (number_of_loops (cfun
) > 1)
627 if (flag_unroll_loops
)
629 if (flag_unroll_all_loops
)
630 flags
|= UAP_UNROLL_ALL
;
632 unroll_and_peel_loops (flags
);
639 const pass_data pass_data_rtl_unroll_and_peel_loops
=
642 "loop2_unroll", /* name */
643 OPTGROUP_LOOP
, /* optinfo_flags */
645 true, /* has_execute */
646 TV_LOOP_UNROLL
, /* tv_id */
647 0, /* properties_required */
648 0, /* properties_provided */
649 0, /* properties_destroyed */
650 0, /* todo_flags_start */
651 TODO_verify_rtl_sharing
, /* todo_flags_finish */
654 class pass_rtl_unroll_and_peel_loops
: public rtl_opt_pass
657 pass_rtl_unroll_and_peel_loops (gcc::context
*ctxt
)
658 : rtl_opt_pass (pass_data_rtl_unroll_and_peel_loops
, ctxt
)
661 /* opt_pass methods: */
662 bool gate () { return gate_rtl_unroll_and_peel_loops (); }
663 unsigned int execute () { return rtl_unroll_and_peel_loops (); }
665 }; // class pass_rtl_unroll_and_peel_loops
670 make_pass_rtl_unroll_and_peel_loops (gcc::context
*ctxt
)
672 return new pass_rtl_unroll_and_peel_loops (ctxt
);
676 /* The doloop optimization. */
678 gate_rtl_doloop (void)
680 #ifdef HAVE_doloop_end
681 return (flag_branch_on_count_reg
&& HAVE_doloop_end
);
690 #ifdef HAVE_doloop_end
691 if (number_of_loops (cfun
) > 1)
692 doloop_optimize_loops ();
699 const pass_data pass_data_rtl_doloop
=
702 "loop2_doloop", /* name */
703 OPTGROUP_LOOP
, /* optinfo_flags */
705 true, /* has_execute */
706 TV_LOOP_DOLOOP
, /* tv_id */
707 0, /* properties_required */
708 0, /* properties_provided */
709 0, /* properties_destroyed */
710 0, /* todo_flags_start */
711 TODO_verify_rtl_sharing
, /* todo_flags_finish */
714 class pass_rtl_doloop
: public rtl_opt_pass
717 pass_rtl_doloop (gcc::context
*ctxt
)
718 : rtl_opt_pass (pass_data_rtl_doloop
, ctxt
)
721 /* opt_pass methods: */
722 bool gate () { return gate_rtl_doloop (); }
723 unsigned int execute () { return rtl_doloop (); }
725 }; // class pass_rtl_doloop
730 make_pass_rtl_doloop (gcc::context
*ctxt
)
732 return new pass_rtl_doloop (ctxt
);