PR sanitizer/65400
[official-gcc.git] / gcc / loop-init.c
blobc13d360fb5a3bc2a87e77f15434375099db97d8b
1 /* Loop optimizer initialization routines and RTL loop optimization passes.
2 Copyright (C) 2002-2015 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 "hash-set.h"
26 #include "machmode.h"
27 #include "vec.h"
28 #include "double-int.h"
29 #include "input.h"
30 #include "alias.h"
31 #include "symtab.h"
32 #include "wide-int.h"
33 #include "inchash.h"
34 #include "tree.h"
35 #include "regs.h"
36 #include "obstack.h"
37 #include "predict.h"
38 #include "hard-reg-set.h"
39 #include "input.h"
40 #include "function.h"
41 #include "dominance.h"
42 #include "cfg.h"
43 #include "cfgcleanup.h"
44 #include "basic-block.h"
45 #include "cfgloop.h"
46 #include "tree-pass.h"
47 #include "flags.h"
48 #include "df.h"
49 #include "ggc.h"
50 #include "tree-ssa-loop-niter.h"
51 #include "loop-unroll.h"
54 /* Apply FLAGS to the loop state. */
56 static void
57 apply_loop_flags (unsigned flags)
59 if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
61 /* If the loops may have multiple latches, we cannot canonicalize
62 them further (and most of the loop manipulation functions will
63 not work). However, we avoid modifying cfg, which some
64 passes may want. */
65 gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
66 | LOOPS_HAVE_RECORDED_EXITS)) == 0);
67 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
69 else
70 disambiguate_loops_with_multiple_latches ();
72 /* Create pre-headers. */
73 if (flags & LOOPS_HAVE_PREHEADERS)
75 int cp_flags = CP_SIMPLE_PREHEADERS;
77 if (flags & LOOPS_HAVE_FALLTHRU_PREHEADERS)
78 cp_flags |= CP_FALLTHRU_PREHEADERS;
80 create_preheaders (cp_flags);
83 /* Force all latches to have only single successor. */
84 if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
85 force_single_succ_latches ();
87 /* Mark irreducible loops. */
88 if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
89 mark_irreducible_loops ();
91 if (flags & LOOPS_HAVE_RECORDED_EXITS)
92 record_loop_exits ();
95 /* Initialize loop structures. This is used by the tree and RTL loop
96 optimizers. FLAGS specify what properties to compute and/or ensure for
97 loops. */
99 void
100 loop_optimizer_init (unsigned flags)
102 timevar_push (TV_LOOP_INIT);
104 if (!current_loops)
106 gcc_assert (!(cfun->curr_properties & PROP_loops));
108 /* Find the loops. */
109 current_loops = flow_loops_find (NULL);
111 else
113 bool recorded_exits = loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS);
114 bool needs_fixup = loops_state_satisfies_p (LOOPS_NEED_FIXUP);
116 gcc_assert (cfun->curr_properties & PROP_loops);
118 /* Ensure that the dominators are computed, like flow_loops_find does. */
119 calculate_dominance_info (CDI_DOMINATORS);
121 #ifdef ENABLE_CHECKING
122 if (!needs_fixup)
123 verify_loop_structure ();
124 #endif
126 /* Clear all flags. */
127 if (recorded_exits)
128 release_recorded_exits ();
129 loops_state_clear (~0U);
131 if (needs_fixup)
133 /* Apply LOOPS_MAY_HAVE_MULTIPLE_LATCHES early as fix_loop_structure
134 re-applies flags. */
135 loops_state_set (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
136 fix_loop_structure (NULL);
140 /* Apply flags to loops. */
141 apply_loop_flags (flags);
143 /* Dump loops. */
144 flow_loops_dump (dump_file, NULL, 1);
146 #ifdef ENABLE_CHECKING
147 verify_loop_structure ();
148 #endif
150 timevar_pop (TV_LOOP_INIT);
153 /* Finalize loop structures. */
155 void
156 loop_optimizer_finalize (void)
158 struct loop *loop;
159 basic_block bb;
161 timevar_push (TV_LOOP_FINI);
163 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
164 release_recorded_exits ();
166 free_numbers_of_iterations_estimates ();
168 /* If we should preserve loop structure, do not free it but clear
169 flags that advanced properties are there as we are not preserving
170 that in full. */
171 if (cfun->curr_properties & PROP_loops)
173 loops_state_clear (LOOP_CLOSED_SSA
174 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
175 | LOOPS_HAVE_PREHEADERS
176 | LOOPS_HAVE_SIMPLE_LATCHES
177 | LOOPS_HAVE_FALLTHRU_PREHEADERS);
178 loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
179 goto loop_fini_done;
182 gcc_assert (current_loops != NULL);
184 FOR_EACH_LOOP (loop, 0)
185 free_simple_loop_desc (loop);
187 /* Clean up. */
188 flow_loops_free (current_loops);
189 ggc_free (current_loops);
190 current_loops = NULL;
192 FOR_ALL_BB_FN (bb, cfun)
194 bb->loop_father = NULL;
197 loop_fini_done:
198 timevar_pop (TV_LOOP_FINI);
201 /* The structure of loops might have changed. Some loops might get removed
202 (and their headers and latches were set to NULL), loop exists might get
203 removed (thus the loop nesting may be wrong), and some blocks and edges
204 were changed (so the information about bb --> loop mapping does not have
205 to be correct). But still for the remaining loops the header dominates
206 the latch, and loops did not get new subloops (new loops might possibly
207 get created, but we are not interested in them). Fix up the mess.
209 If CHANGED_BBS is not NULL, basic blocks whose loop depth has changed are
210 marked in it.
212 Returns the number of new discovered loops. */
214 unsigned
215 fix_loop_structure (bitmap changed_bbs)
217 basic_block bb;
218 int record_exits = 0;
219 struct loop *loop;
220 unsigned old_nloops, i;
222 timevar_push (TV_LOOP_INIT);
224 /* We need exact and fast dominance info to be available. */
225 gcc_assert (dom_info_state (CDI_DOMINATORS) == DOM_OK);
227 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
229 release_recorded_exits ();
230 record_exits = LOOPS_HAVE_RECORDED_EXITS;
233 /* Remember the depth of the blocks in the loop hierarchy, so that we can
234 recognize blocks whose loop nesting relationship has changed. */
235 if (changed_bbs)
236 FOR_EACH_BB_FN (bb, cfun)
237 bb->aux = (void *) (size_t) loop_depth (bb->loop_father);
239 /* Remove the dead loops from structures. We start from the innermost
240 loops, so that when we remove the loops, we know that the loops inside
241 are preserved, and do not waste time relinking loops that will be
242 removed later. */
243 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
245 /* Detect the case that the loop is no longer present even though
246 it wasn't marked for removal.
247 ??? If we do that we can get away with not marking loops for
248 removal at all. And possibly avoid some spurious removals. */
249 if (loop->header
250 && bb_loop_header_p (loop->header))
251 continue;
253 if (dump_file && (dump_flags & TDF_DETAILS))
254 fprintf (dump_file, "fix_loop_structure: removing loop %d\n",
255 loop->num);
257 while (loop->inner)
259 struct loop *ploop = loop->inner;
260 flow_loop_tree_node_remove (ploop);
261 flow_loop_tree_node_add (loop_outer (loop), ploop);
264 /* Remove the loop. */
265 if (loop->header)
266 loop->former_header = loop->header;
267 else
268 gcc_assert (loop->former_header != NULL);
269 loop->header = NULL;
270 flow_loop_tree_node_remove (loop);
273 /* Remember the number of loops so we can return how many new loops
274 flow_loops_find discovered. */
275 old_nloops = number_of_loops (cfun);
277 /* Re-compute loop structure in-place. */
278 flow_loops_find (current_loops);
280 /* Mark the blocks whose loop has changed. */
281 if (changed_bbs)
283 FOR_EACH_BB_FN (bb, cfun)
285 if ((void *) (size_t) loop_depth (bb->loop_father) != bb->aux)
286 bitmap_set_bit (changed_bbs, bb->index);
288 bb->aux = NULL;
292 /* Finally free deleted loops. */
293 FOR_EACH_VEC_ELT (*get_loops (cfun), i, loop)
294 if (loop && loop->header == NULL)
296 if (dump_file
297 && ((unsigned) loop->former_header->index
298 < basic_block_info_for_fn (cfun)->length ()))
300 basic_block former_header
301 = BASIC_BLOCK_FOR_FN (cfun, loop->former_header->index);
302 /* If the old header still exists we want to check if the
303 original loop is re-discovered or the old header is now
304 part of a newly discovered loop.
305 In both cases we should have avoided removing the loop. */
306 if (former_header == loop->former_header)
308 if (former_header->loop_father->header == former_header)
309 fprintf (dump_file, "fix_loop_structure: rediscovered "
310 "removed loop %d as loop %d with old header %d\n",
311 loop->num, former_header->loop_father->num,
312 former_header->index);
313 else if ((unsigned) former_header->loop_father->num
314 >= old_nloops)
315 fprintf (dump_file, "fix_loop_structure: header %d of "
316 "removed loop %d is part of the newly "
317 "discovered loop %d with header %d\n",
318 former_header->index, loop->num,
319 former_header->loop_father->num,
320 former_header->loop_father->header->index);
323 (*get_loops (cfun))[i] = NULL;
324 flow_loop_free (loop);
327 loops_state_clear (LOOPS_NEED_FIXUP);
329 /* Apply flags to loops. */
330 apply_loop_flags (current_loops->state | record_exits);
332 #ifdef ENABLE_CHECKING
333 verify_loop_structure ();
334 #endif
336 timevar_pop (TV_LOOP_INIT);
338 return number_of_loops (cfun) - old_nloops;
341 /* The RTL loop superpass. The actual passes are subpasses. See passes.c for
342 more on that. */
344 namespace {
346 const pass_data pass_data_loop2 =
348 RTL_PASS, /* type */
349 "loop2", /* name */
350 OPTGROUP_LOOP, /* optinfo_flags */
351 TV_LOOP, /* tv_id */
352 0, /* properties_required */
353 0, /* properties_provided */
354 0, /* properties_destroyed */
355 0, /* todo_flags_start */
356 0, /* todo_flags_finish */
359 class pass_loop2 : public rtl_opt_pass
361 public:
362 pass_loop2 (gcc::context *ctxt)
363 : rtl_opt_pass (pass_data_loop2, ctxt)
366 /* opt_pass methods: */
367 virtual bool gate (function *);
369 }; // class pass_loop2
371 bool
372 pass_loop2::gate (function *fun)
374 if (optimize > 0
375 && (flag_move_loop_invariants
376 || flag_unswitch_loops
377 || flag_unroll_loops
378 #ifdef HAVE_doloop_end
379 || (flag_branch_on_count_reg && HAVE_doloop_end)
380 #endif
382 return true;
383 else
385 /* No longer preserve loops, remove them now. */
386 fun->curr_properties &= ~PROP_loops;
387 if (current_loops)
388 loop_optimizer_finalize ();
389 return false;
393 } // anon namespace
395 rtl_opt_pass *
396 make_pass_loop2 (gcc::context *ctxt)
398 return new pass_loop2 (ctxt);
402 /* Initialization of the RTL loop passes. */
403 static unsigned int
404 rtl_loop_init (void)
406 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
408 if (dump_file)
410 dump_reg_info (dump_file);
411 dump_flow_info (dump_file, dump_flags);
414 loop_optimizer_init (LOOPS_NORMAL);
415 return 0;
418 namespace {
420 const pass_data pass_data_rtl_loop_init =
422 RTL_PASS, /* type */
423 "loop2_init", /* name */
424 OPTGROUP_LOOP, /* optinfo_flags */
425 TV_LOOP, /* tv_id */
426 0, /* properties_required */
427 0, /* properties_provided */
428 0, /* properties_destroyed */
429 0, /* todo_flags_start */
430 0, /* todo_flags_finish */
433 class pass_rtl_loop_init : public rtl_opt_pass
435 public:
436 pass_rtl_loop_init (gcc::context *ctxt)
437 : rtl_opt_pass (pass_data_rtl_loop_init, ctxt)
440 /* opt_pass methods: */
441 virtual unsigned int execute (function *) { return rtl_loop_init (); }
443 }; // class pass_rtl_loop_init
445 } // anon namespace
447 rtl_opt_pass *
448 make_pass_rtl_loop_init (gcc::context *ctxt)
450 return new pass_rtl_loop_init (ctxt);
454 /* Finalization of the RTL loop passes. */
456 namespace {
458 const pass_data pass_data_rtl_loop_done =
460 RTL_PASS, /* type */
461 "loop2_done", /* name */
462 OPTGROUP_LOOP, /* optinfo_flags */
463 TV_LOOP, /* tv_id */
464 0, /* properties_required */
465 0, /* properties_provided */
466 PROP_loops, /* properties_destroyed */
467 0, /* todo_flags_start */
468 0, /* todo_flags_finish */
471 class pass_rtl_loop_done : public rtl_opt_pass
473 public:
474 pass_rtl_loop_done (gcc::context *ctxt)
475 : rtl_opt_pass (pass_data_rtl_loop_done, ctxt)
478 /* opt_pass methods: */
479 virtual unsigned int execute (function *);
481 }; // class pass_rtl_loop_done
483 unsigned int
484 pass_rtl_loop_done::execute (function *fun)
486 /* No longer preserve loops, remove them now. */
487 fun->curr_properties &= ~PROP_loops;
488 loop_optimizer_finalize ();
489 free_dominance_info (CDI_DOMINATORS);
491 cleanup_cfg (0);
492 if (dump_file)
494 dump_reg_info (dump_file);
495 dump_flow_info (dump_file, dump_flags);
498 return 0;
501 } // anon namespace
503 rtl_opt_pass *
504 make_pass_rtl_loop_done (gcc::context *ctxt)
506 return new pass_rtl_loop_done (ctxt);
510 /* Loop invariant code motion. */
512 namespace {
514 const pass_data pass_data_rtl_move_loop_invariants =
516 RTL_PASS, /* type */
517 "loop2_invariant", /* name */
518 OPTGROUP_LOOP, /* optinfo_flags */
519 TV_LOOP_MOVE_INVARIANTS, /* tv_id */
520 0, /* properties_required */
521 0, /* properties_provided */
522 0, /* properties_destroyed */
523 0, /* todo_flags_start */
524 ( TODO_df_verify | TODO_df_finish ), /* todo_flags_finish */
527 class pass_rtl_move_loop_invariants : public rtl_opt_pass
529 public:
530 pass_rtl_move_loop_invariants (gcc::context *ctxt)
531 : rtl_opt_pass (pass_data_rtl_move_loop_invariants, ctxt)
534 /* opt_pass methods: */
535 virtual bool gate (function *) { return flag_move_loop_invariants; }
536 virtual unsigned int execute (function *fun)
538 if (number_of_loops (fun) > 1)
539 move_loop_invariants ();
540 return 0;
543 }; // class pass_rtl_move_loop_invariants
545 } // anon namespace
547 rtl_opt_pass *
548 make_pass_rtl_move_loop_invariants (gcc::context *ctxt)
550 return new pass_rtl_move_loop_invariants (ctxt);
554 namespace {
556 const pass_data pass_data_rtl_unroll_loops =
558 RTL_PASS, /* type */
559 "loop2_unroll", /* name */
560 OPTGROUP_LOOP, /* optinfo_flags */
561 TV_LOOP_UNROLL, /* tv_id */
562 0, /* properties_required */
563 0, /* properties_provided */
564 0, /* properties_destroyed */
565 0, /* todo_flags_start */
566 0, /* todo_flags_finish */
569 class pass_rtl_unroll_loops : public rtl_opt_pass
571 public:
572 pass_rtl_unroll_loops (gcc::context *ctxt)
573 : rtl_opt_pass (pass_data_rtl_unroll_loops, ctxt)
576 /* opt_pass methods: */
577 virtual bool gate (function *)
579 return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
582 virtual unsigned int execute (function *);
584 }; // class pass_rtl_unroll_loops
586 unsigned int
587 pass_rtl_unroll_loops::execute (function *fun)
589 if (number_of_loops (fun) > 1)
591 int flags = 0;
592 if (dump_file)
593 df_dump (dump_file);
595 if (flag_unroll_loops)
596 flags |= UAP_UNROLL;
597 if (flag_unroll_all_loops)
598 flags |= UAP_UNROLL_ALL;
600 unroll_loops (flags);
602 return 0;
605 } // anon namespace
607 rtl_opt_pass *
608 make_pass_rtl_unroll_loops (gcc::context *ctxt)
610 return new pass_rtl_unroll_loops (ctxt);
614 namespace {
616 const pass_data pass_data_rtl_doloop =
618 RTL_PASS, /* type */
619 "loop2_doloop", /* name */
620 OPTGROUP_LOOP, /* optinfo_flags */
621 TV_LOOP_DOLOOP, /* tv_id */
622 0, /* properties_required */
623 0, /* properties_provided */
624 0, /* properties_destroyed */
625 0, /* todo_flags_start */
626 0, /* todo_flags_finish */
629 class pass_rtl_doloop : public rtl_opt_pass
631 public:
632 pass_rtl_doloop (gcc::context *ctxt)
633 : rtl_opt_pass (pass_data_rtl_doloop, ctxt)
636 /* opt_pass methods: */
637 virtual bool gate (function *);
638 virtual unsigned int execute (function *);
640 }; // class pass_rtl_doloop
642 bool
643 pass_rtl_doloop::gate (function *)
645 #ifdef HAVE_doloop_end
646 return (flag_branch_on_count_reg && HAVE_doloop_end);
647 #else
648 return false;
649 #endif
652 unsigned int
653 pass_rtl_doloop::execute (function *fun ATTRIBUTE_UNUSED)
655 #ifdef HAVE_doloop_end
656 if (number_of_loops (fun) > 1)
657 doloop_optimize_loops ();
658 #endif
659 return 0;
662 } // anon namespace
664 rtl_opt_pass *
665 make_pass_rtl_doloop (gcc::context *ctxt)
667 return new pass_rtl_doloop (ctxt);