aboutsummaryrefslogtreecommitdiff
path: root/gcc/loop-init.cc
diff options
context:
space:
mode:
Diffstat (limited to 'gcc/loop-init.cc')
-rw-r--r--gcc/loop-init.cc653
1 files changed, 653 insertions, 0 deletions
diff --git a/gcc/loop-init.cc b/gcc/loop-init.cc
new file mode 100644
index 0000000..db386e0
--- /dev/null
+++ b/gcc/loop-init.cc
@@ -0,0 +1,653 @@
+/* Loop optimizer initialization routines and RTL loop optimization passes.
+ Copyright (C) 2002-2022 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "target.h"
+#include "rtl.h"
+#include "tree.h"
+#include "cfghooks.h"
+#include "df.h"
+#include "regs.h"
+#include "cfgcleanup.h"
+#include "cfgloop.h"
+#include "tree-pass.h"
+#include "tree-ssa-loop-niter.h"
+#include "loop-unroll.h"
+#include "tree-scalar-evolution.h"
+#include "tree-cfgcleanup.h"
+
+
+/* Apply FLAGS to the loop state. */
+
+static void
+apply_loop_flags (unsigned flags)
+{
+ if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
+ {
+ /* If the loops may have multiple latches, we cannot canonicalize
+ them further (and most of the loop manipulation functions will
+ not work). However, we avoid modifying cfg, which some
+ passes may want. */
+ gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
+ | LOOPS_HAVE_RECORDED_EXITS
+ | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)) == 0);
+ loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
+ }
+ else
+ disambiguate_loops_with_multiple_latches ();
+
+ /* Create pre-headers. */
+ if (flags & LOOPS_HAVE_PREHEADERS)
+ {
+ int cp_flags = CP_SIMPLE_PREHEADERS;
+
+ if (flags & LOOPS_HAVE_FALLTHRU_PREHEADERS)
+ cp_flags |= CP_FALLTHRU_PREHEADERS;
+
+ create_preheaders (cp_flags);
+ }
+
+ /* Force all latches to have only single successor. */
+ if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
+ force_single_succ_latches ();
+
+ /* Mark irreducible loops. */
+ if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
+ mark_irreducible_loops ();
+
+ if (flags & LOOPS_HAVE_RECORDED_EXITS)
+ record_loop_exits ();
+}
+
+/* Initialize loop structures. This is used by the tree and RTL loop
+ optimizers. FLAGS specify what properties to compute and/or ensure for
+ loops. */
+
+void
+loop_optimizer_init (unsigned flags)
+{
+ timevar_push (TV_LOOP_INIT);
+
+ if (!current_loops)
+ {
+ gcc_assert (!(cfun->curr_properties & PROP_loops));
+
+ /* Find the loops. */
+ current_loops = flow_loops_find (NULL);
+ }
+ else
+ {
+ bool recorded_exits = loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS);
+ bool needs_fixup = loops_state_satisfies_p (LOOPS_NEED_FIXUP);
+
+ gcc_assert (cfun->curr_properties & PROP_loops);
+
+ /* Ensure that the dominators are computed, like flow_loops_find does. */
+ calculate_dominance_info (CDI_DOMINATORS);
+
+ if (!needs_fixup)
+ checking_verify_loop_structure ();
+
+ /* Clear all flags. */
+ if (recorded_exits)
+ release_recorded_exits (cfun);
+ loops_state_clear (~0U);
+
+ if (needs_fixup)
+ {
+ /* Apply LOOPS_MAY_HAVE_MULTIPLE_LATCHES early as fix_loop_structure
+ re-applies flags. */
+ loops_state_set (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
+ fix_loop_structure (NULL);
+ }
+ }
+
+ /* Apply flags to loops. */
+ apply_loop_flags (flags);
+
+ /* Dump loops. */
+ flow_loops_dump (dump_file, NULL, 1);
+
+ checking_verify_loop_structure ();
+
+ timevar_pop (TV_LOOP_INIT);
+}
+
+/* Finalize loop structures. */
+
+void
+loop_optimizer_finalize (struct function *fn, bool clean_loop_closed_phi)
+{
+ basic_block bb;
+
+ timevar_push (TV_LOOP_FINI);
+
+ if (clean_loop_closed_phi && loops_state_satisfies_p (fn, LOOP_CLOSED_SSA))
+ {
+ clean_up_loop_closed_phi (fn);
+ loops_state_clear (fn, LOOP_CLOSED_SSA);
+ }
+
+ if (loops_state_satisfies_p (fn, LOOPS_HAVE_RECORDED_EXITS))
+ release_recorded_exits (fn);
+
+ free_numbers_of_iterations_estimates (fn);
+
+ /* If we should preserve loop structure, do not free it but clear
+ flags that advanced properties are there as we are not preserving
+ that in full. */
+ if (fn->curr_properties & PROP_loops)
+ {
+ loops_state_clear (fn, LOOP_CLOSED_SSA
+ | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
+ | LOOPS_HAVE_PREHEADERS
+ | LOOPS_HAVE_SIMPLE_LATCHES
+ | LOOPS_HAVE_FALLTHRU_PREHEADERS);
+ loops_state_set (fn, LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
+ goto loop_fini_done;
+ }
+
+ for (auto loop : loops_list (fn, 0))
+ free_simple_loop_desc (loop);
+
+ /* Clean up. */
+ flow_loops_free (loops_for_fn (fn));
+ ggc_free (loops_for_fn (fn));
+ set_loops_for_fn (fn, NULL);
+
+ FOR_ALL_BB_FN (bb, fn)
+ {
+ bb->loop_father = NULL;
+ }
+
+loop_fini_done:
+ timevar_pop (TV_LOOP_FINI);
+}
+
+/* The structure of loops might have changed. Some loops might get removed
+ (and their headers and latches were set to NULL), loop exists might get
+ removed (thus the loop nesting may be wrong), and some blocks and edges
+ were changed (so the information about bb --> loop mapping does not have
+ to be correct). But still for the remaining loops the header dominates
+ the latch, and loops did not get new subloops (new loops might possibly
+ get created, but we are not interested in them). Fix up the mess.
+
+ If CHANGED_BBS is not NULL, basic blocks whose loop depth has changed are
+ marked in it.
+
+ Returns the number of new discovered loops. */
+
+unsigned
+fix_loop_structure (bitmap changed_bbs)
+{
+ basic_block bb;
+ int record_exits = 0;
+ unsigned old_nloops, i;
+
+ timevar_push (TV_LOOP_INIT);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "fix_loop_structure: fixing up loops for function\n");
+
+ /* We need exact and fast dominance info to be available. */
+ gcc_assert (dom_info_state (CDI_DOMINATORS) == DOM_OK);
+
+ if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
+ {
+ release_recorded_exits (cfun);
+ record_exits = LOOPS_HAVE_RECORDED_EXITS;
+ }
+
+ /* Remember the depth of the blocks in the loop hierarchy, so that we can
+ recognize blocks whose loop nesting relationship has changed. */
+ if (changed_bbs)
+ FOR_EACH_BB_FN (bb, cfun)
+ bb->aux = (void *) (size_t) loop_depth (bb->loop_father);
+
+ /* Remove the dead loops from structures. We start from the innermost
+ loops, so that when we remove the loops, we know that the loops inside
+ are preserved, and do not waste time relinking loops that will be
+ removed later. */
+ for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
+ {
+ /* Detect the case that the loop is no longer present even though
+ it wasn't marked for removal.
+ ??? If we do that we can get away with not marking loops for
+ removal at all. And possibly avoid some spurious removals. */
+ if (loop->header
+ && bb_loop_header_p (loop->header))
+ continue;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "fix_loop_structure: removing loop %d\n",
+ loop->num);
+
+ while (loop->inner)
+ {
+ class loop *ploop = loop->inner;
+ flow_loop_tree_node_remove (ploop);
+ flow_loop_tree_node_add (loop_outer (loop), ploop);
+ }
+
+ /* Remove the loop. */
+ if (loop->header)
+ loop->former_header = loop->header;
+ else
+ gcc_assert (loop->former_header != NULL);
+ loop->header = NULL;
+ flow_loop_tree_node_remove (loop);
+ }
+
+ /* Remember the number of loops so we can return how many new loops
+ flow_loops_find discovered. */
+ old_nloops = number_of_loops (cfun);
+
+ /* Re-compute loop structure in-place. */
+ flow_loops_find (current_loops);
+
+ /* Mark the blocks whose loop has changed. */
+ if (changed_bbs)
+ {
+ FOR_EACH_BB_FN (bb, cfun)
+ {
+ if ((void *) (size_t) loop_depth (bb->loop_father) != bb->aux)
+ bitmap_set_bit (changed_bbs, bb->index);
+
+ bb->aux = NULL;
+ }
+ }
+
+ /* Finally free deleted loops. */
+ bool any_deleted = false;
+ class loop *loop;
+ FOR_EACH_VEC_ELT (*get_loops (cfun), i, loop)
+ if (loop && loop->header == NULL)
+ {
+ if (dump_file
+ && ((unsigned) loop->former_header->index
+ < basic_block_info_for_fn (cfun)->length ()))
+ {
+ basic_block former_header
+ = BASIC_BLOCK_FOR_FN (cfun, loop->former_header->index);
+ /* If the old header still exists we want to check if the
+ original loop is re-discovered or the old header is now
+ part of a newly discovered loop.
+ In both cases we should have avoided removing the loop. */
+ if (former_header == loop->former_header)
+ {
+ if (former_header->loop_father->header == former_header)
+ fprintf (dump_file, "fix_loop_structure: rediscovered "
+ "removed loop %d as loop %d with old header %d\n",
+ loop->num, former_header->loop_father->num,
+ former_header->index);
+ else if ((unsigned) former_header->loop_father->num
+ >= old_nloops)
+ fprintf (dump_file, "fix_loop_structure: header %d of "
+ "removed loop %d is part of the newly "
+ "discovered loop %d with header %d\n",
+ former_header->index, loop->num,
+ former_header->loop_father->num,
+ former_header->loop_father->header->index);
+ }
+ }
+ (*get_loops (cfun))[i] = NULL;
+ flow_loop_free (loop);
+ any_deleted = true;
+ }
+
+ /* If we deleted loops then the cached scalar evolutions refering to
+ those loops become invalid. */
+ if (any_deleted && scev_initialized_p ())
+ scev_reset_htab ();
+
+ loops_state_clear (LOOPS_NEED_FIXUP);
+
+ /* Apply flags to loops. */
+ apply_loop_flags (current_loops->state | record_exits);
+
+ checking_verify_loop_structure ();
+
+ timevar_pop (TV_LOOP_INIT);
+
+ return number_of_loops (cfun) - old_nloops;
+}
+
+/* The RTL loop superpass. The actual passes are subpasses. See passes.c for
+ more on that. */
+
+namespace {
+
+const pass_data pass_data_loop2 =
+{
+ RTL_PASS, /* type */
+ "loop2", /* name */
+ OPTGROUP_LOOP, /* optinfo_flags */
+ TV_LOOP, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
+};
+
+class pass_loop2 : public rtl_opt_pass
+{
+public:
+ pass_loop2 (gcc::context *ctxt)
+ : rtl_opt_pass (pass_data_loop2, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *);
+
+}; // class pass_loop2
+
+bool
+pass_loop2::gate (function *fun)
+{
+ if (optimize > 0
+ && (flag_move_loop_invariants
+ || flag_unswitch_loops
+ || flag_unroll_loops
+ || (flag_branch_on_count_reg && targetm.have_doloop_end ())
+ || cfun->has_unroll))
+ return true;
+ else
+ {
+ /* No longer preserve loops, remove them now. */
+ fun->curr_properties &= ~PROP_loops;
+ if (current_loops)
+ loop_optimizer_finalize ();
+ return false;
+ }
+}
+
+} // anon namespace
+
+rtl_opt_pass *
+make_pass_loop2 (gcc::context *ctxt)
+{
+ return new pass_loop2 (ctxt);
+}
+
+
+/* Initialization of the RTL loop passes. */
+static unsigned int
+rtl_loop_init (void)
+{
+ gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
+
+ if (dump_file)
+ {
+ dump_reg_info (dump_file);
+ dump_flow_info (dump_file, dump_flags);
+ }
+
+ loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
+ return 0;
+}
+
+namespace {
+
+const pass_data pass_data_rtl_loop_init =
+{
+ RTL_PASS, /* type */
+ "loop2_init", /* name */
+ OPTGROUP_LOOP, /* optinfo_flags */
+ TV_LOOP, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
+};
+
+class pass_rtl_loop_init : public rtl_opt_pass
+{
+public:
+ pass_rtl_loop_init (gcc::context *ctxt)
+ : rtl_opt_pass (pass_data_rtl_loop_init, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual unsigned int execute (function *) { return rtl_loop_init (); }
+
+}; // class pass_rtl_loop_init
+
+} // anon namespace
+
+rtl_opt_pass *
+make_pass_rtl_loop_init (gcc::context *ctxt)
+{
+ return new pass_rtl_loop_init (ctxt);
+}
+
+
+/* Finalization of the RTL loop passes. */
+
+namespace {
+
+const pass_data pass_data_rtl_loop_done =
+{
+ RTL_PASS, /* type */
+ "loop2_done", /* name */
+ OPTGROUP_LOOP, /* optinfo_flags */
+ TV_LOOP, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ PROP_loops, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
+};
+
+class pass_rtl_loop_done : public rtl_opt_pass
+{
+public:
+ pass_rtl_loop_done (gcc::context *ctxt)
+ : rtl_opt_pass (pass_data_rtl_loop_done, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual unsigned int execute (function *);
+
+}; // class pass_rtl_loop_done
+
+unsigned int
+pass_rtl_loop_done::execute (function *fun)
+{
+ /* No longer preserve loops, remove them now. */
+ fun->curr_properties &= ~PROP_loops;
+ loop_optimizer_finalize ();
+ free_dominance_info (CDI_DOMINATORS);
+
+ cleanup_cfg (0);
+ if (dump_file)
+ {
+ dump_reg_info (dump_file);
+ dump_flow_info (dump_file, dump_flags);
+ }
+
+ return 0;
+}
+
+} // anon namespace
+
+rtl_opt_pass *
+make_pass_rtl_loop_done (gcc::context *ctxt)
+{
+ return new pass_rtl_loop_done (ctxt);
+}
+
+
+/* Loop invariant code motion. */
+
+namespace {
+
+const pass_data pass_data_rtl_move_loop_invariants =
+{
+ RTL_PASS, /* type */
+ "loop2_invariant", /* name */
+ OPTGROUP_LOOP, /* optinfo_flags */
+ TV_LOOP_MOVE_INVARIANTS, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ ( TODO_df_verify | TODO_df_finish ), /* todo_flags_finish */
+};
+
+class pass_rtl_move_loop_invariants : public rtl_opt_pass
+{
+public:
+ pass_rtl_move_loop_invariants (gcc::context *ctxt)
+ : rtl_opt_pass (pass_data_rtl_move_loop_invariants, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *) { return flag_move_loop_invariants; }
+ virtual unsigned int execute (function *fun)
+ {
+ if (number_of_loops (fun) > 1)
+ move_loop_invariants ();
+ return 0;
+ }
+
+}; // class pass_rtl_move_loop_invariants
+
+} // anon namespace
+
+rtl_opt_pass *
+make_pass_rtl_move_loop_invariants (gcc::context *ctxt)
+{
+ return new pass_rtl_move_loop_invariants (ctxt);
+}
+
+
+namespace {
+
+const pass_data pass_data_rtl_unroll_loops =
+{
+ RTL_PASS, /* type */
+ "loop2_unroll", /* name */
+ OPTGROUP_LOOP, /* optinfo_flags */
+ TV_LOOP_UNROLL, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
+};
+
+class pass_rtl_unroll_loops : public rtl_opt_pass
+{
+public:
+ pass_rtl_unroll_loops (gcc::context *ctxt)
+ : rtl_opt_pass (pass_data_rtl_unroll_loops, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *)
+ {
+ return (flag_unroll_loops || flag_unroll_all_loops || cfun->has_unroll);
+ }
+
+ virtual unsigned int execute (function *);
+
+}; // class pass_rtl_unroll_loops
+
+unsigned int
+pass_rtl_unroll_loops::execute (function *fun)
+{
+ if (number_of_loops (fun) > 1)
+ {
+ int flags = 0;
+ if (dump_file)
+ df_dump (dump_file);
+
+ if (flag_unroll_loops)
+ flags |= UAP_UNROLL;
+ if (flag_unroll_all_loops)
+ flags |= UAP_UNROLL_ALL;
+
+ unroll_loops (flags);
+ }
+ return 0;
+}
+
+} // anon namespace
+
+rtl_opt_pass *
+make_pass_rtl_unroll_loops (gcc::context *ctxt)
+{
+ return new pass_rtl_unroll_loops (ctxt);
+}
+
+
+namespace {
+
+const pass_data pass_data_rtl_doloop =
+{
+ RTL_PASS, /* type */
+ "loop2_doloop", /* name */
+ OPTGROUP_LOOP, /* optinfo_flags */
+ TV_LOOP_DOLOOP, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
+};
+
+class pass_rtl_doloop : public rtl_opt_pass
+{
+public:
+ pass_rtl_doloop (gcc::context *ctxt)
+ : rtl_opt_pass (pass_data_rtl_doloop, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *);
+ virtual unsigned int execute (function *);
+
+}; // class pass_rtl_doloop
+
+bool
+pass_rtl_doloop::gate (function *)
+{
+ return (flag_branch_on_count_reg && targetm.have_doloop_end ());
+}
+
+unsigned int
+pass_rtl_doloop::execute (function *fun)
+{
+ if (number_of_loops (fun) > 1)
+ doloop_optimize_loops ();
+ return 0;
+}
+
+} // anon namespace
+
+rtl_opt_pass *
+make_pass_rtl_doloop (gcc::context *ctxt)
+{
+ return new pass_rtl_doloop (ctxt);
+}