2013-08-14 Paolo Carlini <paolo.carlini@oracle.com>
[official-gcc.git] / gcc / loop-init.c
blob80c31ef70cd6ccb708a6d429b95deddb656e031a
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
9 version.
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
14 for more details.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "rtl.h"
25 #include "regs.h"
26 #include "obstack.h"
27 #include "basic-block.h"
28 #include "cfgloop.h"
29 #include "tree-pass.h"
30 #include "flags.h"
31 #include "df.h"
32 #include "ggc.h"
33 #include "tree-flow.h"
36 /* Apply FLAGS to the loop state. */
38 static void
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
46 passes may want. */
47 gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
48 | LOOPS_HAVE_RECORDED_EXITS)) == 0);
49 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
51 else
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)
74 record_loop_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
79 loops. */
81 void
82 loop_optimizer_init (unsigned flags)
84 timevar_push (TV_LOOP_INIT);
86 if (!current_loops)
88 gcc_assert (!(cfun->curr_properties & PROP_loops));
90 /* Find the loops. */
91 current_loops = flow_loops_find (NULL);
93 else
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
109 else
110 verify_loop_structure ();
111 #endif
113 /* Clear all flags. */
114 if (recorded_exits)
115 release_recorded_exits ();
116 loops_state_clear (~0U);
119 /* Apply flags to loops. */
120 apply_loop_flags (flags);
122 /* Dump loops. */
123 flow_loops_dump (dump_file, NULL, 1);
125 #ifdef ENABLE_CHECKING
126 verify_loop_structure ();
127 #endif
129 timevar_pop (TV_LOOP_INIT);
132 /* Finalize loop structures. */
134 void
135 loop_optimizer_finalize (void)
137 loop_iterator li;
138 struct loop *loop;
139 basic_block bb;
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
150 that in full. */
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);
159 goto loop_fini_done;
162 gcc_assert (current_loops != NULL);
164 FOR_EACH_LOOP (li, loop, 0)
166 free_simple_loop_desc (loop);
169 /* Clean up. */
170 flow_loops_free (current_loops);
171 ggc_free (current_loops);
172 current_loops = NULL;
174 FOR_ALL_BB (bb)
176 bb->loop_father = NULL;
179 loop_fini_done:
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
192 marked in it.
194 Returns the number of new discovered loops. */
196 unsigned
197 fix_loop_structure (bitmap changed_bbs)
199 basic_block bb;
200 int record_exits = 0;
201 loop_iterator li;
202 struct loop *loop;
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. */
218 if (changed_bbs)
219 FOR_EACH_BB (bb)
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
225 removed later. */
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. */
232 if (loop->header
233 && bb_loop_header_p (loop->header))
234 continue;
236 if (dump_file && (dump_flags & TDF_DETAILS))
237 fprintf (dump_file, "fix_loop_structure: removing loop %d\n",
238 loop->num);
240 while (loop->inner)
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. */
248 loop->header = NULL;
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. */
260 if (changed_bbs)
262 FOR_EACH_BB (bb)
264 if ((void *) (size_t) loop_depth (bb->loop_father) != bb->aux)
265 bitmap_set_bit (changed_bbs, bb->index);
267 bb->aux = NULL;
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 ();
286 #endif
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. */
296 static bool
297 gate_handle_loop2 (void)
299 if (optimize > 0
300 && (flag_move_loop_invariants
301 || flag_unswitch_loops
302 || flag_peel_loops
303 || flag_unroll_loops
304 #ifdef HAVE_doloop_end
305 || (flag_branch_on_count_reg && HAVE_doloop_end)
306 #endif
308 return true;
309 else
311 /* No longer preserve loops, remove them now. */
312 cfun->curr_properties &= ~PROP_loops;
313 if (current_loops)
314 loop_optimizer_finalize ();
315 return false;
319 namespace {
321 const pass_data pass_data_loop2 =
323 RTL_PASS, /* type */
324 "loop2", /* name */
325 OPTGROUP_LOOP, /* optinfo_flags */
326 true, /* has_gate */
327 false, /* has_execute */
328 TV_LOOP, /* tv_id */
329 0, /* properties_required */
330 0, /* properties_provided */
331 0, /* properties_destroyed */
332 0, /* todo_flags_start */
333 0, /* todo_flags_finish */
336 class pass_loop2 : public rtl_opt_pass
338 public:
339 pass_loop2(gcc::context *ctxt)
340 : rtl_opt_pass(pass_data_loop2, ctxt)
343 /* opt_pass methods: */
344 bool gate () { return gate_handle_loop2 (); }
346 }; // class pass_loop2
348 } // anon namespace
350 rtl_opt_pass *
351 make_pass_loop2 (gcc::context *ctxt)
353 return new pass_loop2 (ctxt);
357 /* Initialization of the RTL loop passes. */
358 static unsigned int
359 rtl_loop_init (void)
361 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
363 if (dump_file)
365 dump_reg_info (dump_file);
366 dump_flow_info (dump_file, dump_flags);
369 loop_optimizer_init (LOOPS_NORMAL);
370 return 0;
373 namespace {
375 const pass_data pass_data_rtl_loop_init =
377 RTL_PASS, /* type */
378 "loop2_init", /* name */
379 OPTGROUP_LOOP, /* optinfo_flags */
380 false, /* has_gate */
381 true, /* has_execute */
382 TV_LOOP, /* tv_id */
383 0, /* properties_required */
384 0, /* properties_provided */
385 0, /* properties_destroyed */
386 0, /* todo_flags_start */
387 TODO_verify_rtl_sharing, /* todo_flags_finish */
390 class pass_rtl_loop_init : public rtl_opt_pass
392 public:
393 pass_rtl_loop_init(gcc::context *ctxt)
394 : rtl_opt_pass(pass_data_rtl_loop_init, ctxt)
397 /* opt_pass methods: */
398 unsigned int execute () { return rtl_loop_init (); }
400 }; // class pass_rtl_loop_init
402 } // anon namespace
404 rtl_opt_pass *
405 make_pass_rtl_loop_init (gcc::context *ctxt)
407 return new pass_rtl_loop_init (ctxt);
411 /* Finalization of the RTL loop passes. */
413 static unsigned int
414 rtl_loop_done (void)
416 /* No longer preserve loops, remove them now. */
417 cfun->curr_properties &= ~PROP_loops;
418 loop_optimizer_finalize ();
419 free_dominance_info (CDI_DOMINATORS);
421 cleanup_cfg (0);
422 if (dump_file)
424 dump_reg_info (dump_file);
425 dump_flow_info (dump_file, dump_flags);
428 return 0;
431 namespace {
433 const pass_data pass_data_rtl_loop_done =
435 RTL_PASS, /* type */
436 "loop2_done", /* name */
437 OPTGROUP_LOOP, /* optinfo_flags */
438 false, /* has_gate */
439 true, /* has_execute */
440 TV_LOOP, /* tv_id */
441 0, /* properties_required */
442 0, /* properties_provided */
443 PROP_loops, /* properties_destroyed */
444 0, /* todo_flags_start */
445 ( TODO_verify_flow | TODO_verify_rtl_sharing ), /* todo_flags_finish */
448 class pass_rtl_loop_done : public rtl_opt_pass
450 public:
451 pass_rtl_loop_done(gcc::context *ctxt)
452 : rtl_opt_pass(pass_data_rtl_loop_done, ctxt)
455 /* opt_pass methods: */
456 unsigned int execute () { return rtl_loop_done (); }
458 }; // class pass_rtl_loop_done
460 } // anon namespace
462 rtl_opt_pass *
463 make_pass_rtl_loop_done (gcc::context *ctxt)
465 return new pass_rtl_loop_done (ctxt);
469 /* Loop invariant code motion. */
470 static bool
471 gate_rtl_move_loop_invariants (void)
473 return flag_move_loop_invariants;
476 static unsigned int
477 rtl_move_loop_invariants (void)
479 if (number_of_loops (cfun) > 1)
480 move_loop_invariants ();
481 return 0;
484 namespace {
486 const pass_data pass_data_rtl_move_loop_invariants =
488 RTL_PASS, /* type */
489 "loop2_invariant", /* name */
490 OPTGROUP_LOOP, /* optinfo_flags */
491 true, /* has_gate */
492 true, /* has_execute */
493 TV_LOOP_MOVE_INVARIANTS, /* tv_id */
494 0, /* properties_required */
495 0, /* properties_provided */
496 0, /* properties_destroyed */
497 0, /* todo_flags_start */
498 ( TODO_df_verify | TODO_df_finish
499 | TODO_verify_rtl_sharing ), /* todo_flags_finish */
502 class pass_rtl_move_loop_invariants : public rtl_opt_pass
504 public:
505 pass_rtl_move_loop_invariants(gcc::context *ctxt)
506 : rtl_opt_pass(pass_data_rtl_move_loop_invariants, ctxt)
509 /* opt_pass methods: */
510 bool gate () { return gate_rtl_move_loop_invariants (); }
511 unsigned int execute () { return rtl_move_loop_invariants (); }
513 }; // class pass_rtl_move_loop_invariants
515 } // anon namespace
517 rtl_opt_pass *
518 make_pass_rtl_move_loop_invariants (gcc::context *ctxt)
520 return new pass_rtl_move_loop_invariants (ctxt);
524 /* Loop unswitching for RTL. */
525 static bool
526 gate_rtl_unswitch (void)
528 return flag_unswitch_loops;
531 static unsigned int
532 rtl_unswitch (void)
534 if (number_of_loops (cfun) > 1)
535 unswitch_loops ();
536 return 0;
539 namespace {
541 const pass_data pass_data_rtl_unswitch =
543 RTL_PASS, /* type */
544 "loop2_unswitch", /* name */
545 OPTGROUP_LOOP, /* optinfo_flags */
546 true, /* has_gate */
547 true, /* has_execute */
548 TV_LOOP_UNSWITCH, /* tv_id */
549 0, /* properties_required */
550 0, /* properties_provided */
551 0, /* properties_destroyed */
552 0, /* todo_flags_start */
553 TODO_verify_rtl_sharing, /* todo_flags_finish */
556 class pass_rtl_unswitch : public rtl_opt_pass
558 public:
559 pass_rtl_unswitch(gcc::context *ctxt)
560 : rtl_opt_pass(pass_data_rtl_unswitch, ctxt)
563 /* opt_pass methods: */
564 bool gate () { return gate_rtl_unswitch (); }
565 unsigned int execute () { return rtl_unswitch (); }
567 }; // class pass_rtl_unswitch
569 } // anon namespace
571 rtl_opt_pass *
572 make_pass_rtl_unswitch (gcc::context *ctxt)
574 return new pass_rtl_unswitch (ctxt);
578 /* Loop unswitching for RTL. */
579 static bool
580 gate_rtl_unroll_and_peel_loops (void)
582 return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
585 static unsigned int
586 rtl_unroll_and_peel_loops (void)
588 if (number_of_loops (cfun) > 1)
590 int flags = 0;
591 if (dump_file)
592 df_dump (dump_file);
594 if (flag_peel_loops)
595 flags |= UAP_PEEL;
596 if (flag_unroll_loops)
597 flags |= UAP_UNROLL;
598 if (flag_unroll_all_loops)
599 flags |= UAP_UNROLL_ALL;
601 unroll_and_peel_loops (flags);
603 return 0;
606 namespace {
608 const pass_data pass_data_rtl_unroll_and_peel_loops =
610 RTL_PASS, /* type */
611 "loop2_unroll", /* name */
612 OPTGROUP_LOOP, /* optinfo_flags */
613 true, /* has_gate */
614 true, /* has_execute */
615 TV_LOOP_UNROLL, /* tv_id */
616 0, /* properties_required */
617 0, /* properties_provided */
618 0, /* properties_destroyed */
619 0, /* todo_flags_start */
620 TODO_verify_rtl_sharing, /* todo_flags_finish */
623 class pass_rtl_unroll_and_peel_loops : public rtl_opt_pass
625 public:
626 pass_rtl_unroll_and_peel_loops(gcc::context *ctxt)
627 : rtl_opt_pass(pass_data_rtl_unroll_and_peel_loops, ctxt)
630 /* opt_pass methods: */
631 bool gate () { return gate_rtl_unroll_and_peel_loops (); }
632 unsigned int execute () { return rtl_unroll_and_peel_loops (); }
634 }; // class pass_rtl_unroll_and_peel_loops
636 } // anon namespace
638 rtl_opt_pass *
639 make_pass_rtl_unroll_and_peel_loops (gcc::context *ctxt)
641 return new pass_rtl_unroll_and_peel_loops (ctxt);
645 /* The doloop optimization. */
646 static bool
647 gate_rtl_doloop (void)
649 #ifdef HAVE_doloop_end
650 return (flag_branch_on_count_reg && HAVE_doloop_end);
651 #else
652 return 0;
653 #endif
656 static unsigned int
657 rtl_doloop (void)
659 #ifdef HAVE_doloop_end
660 if (number_of_loops (cfun) > 1)
661 doloop_optimize_loops ();
662 #endif
663 return 0;
666 namespace {
668 const pass_data pass_data_rtl_doloop =
670 RTL_PASS, /* type */
671 "loop2_doloop", /* name */
672 OPTGROUP_LOOP, /* optinfo_flags */
673 true, /* has_gate */
674 true, /* has_execute */
675 TV_LOOP_DOLOOP, /* tv_id */
676 0, /* properties_required */
677 0, /* properties_provided */
678 0, /* properties_destroyed */
679 0, /* todo_flags_start */
680 TODO_verify_rtl_sharing, /* todo_flags_finish */
683 class pass_rtl_doloop : public rtl_opt_pass
685 public:
686 pass_rtl_doloop(gcc::context *ctxt)
687 : rtl_opt_pass(pass_data_rtl_doloop, ctxt)
690 /* opt_pass methods: */
691 bool gate () { return gate_rtl_doloop (); }
692 unsigned int execute () { return rtl_doloop (); }
694 }; // class pass_rtl_doloop
696 } // anon namespace
698 rtl_opt_pass *
699 make_pass_rtl_doloop (gcc::context *ctxt)
701 return new pass_rtl_doloop (ctxt);