/* Loop optimizer initialization routines and RTL loop optimization passes.
- Copyright (C) 2002-2013 Free Software Foundation, Inc.
+ Copyright (C) 2002-2020 Free Software Foundation, Inc.
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
+#include "backend.h"
+#include "target.h"
#include "rtl.h"
#include "tree.h"
+#include "cfghooks.h"
+#include "df.h"
#include "regs.h"
-#include "obstack.h"
-#include "basic-block.h"
+#include "cfgcleanup.h"
#include "cfgloop.h"
#include "tree-pass.h"
-#include "flags.h"
-#include "df.h"
-#include "ggc.h"
#include "tree-ssa-loop-niter.h"
+#include "loop-unroll.h"
+#include "tree-scalar-evolution.h"
\f
/* Apply FLAGS to the loop state. */
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 (loops_state_satisfies_p (LOOPS_NEED_FIXUP))
- {
- loops_state_clear (~0U);
- fix_loop_structure (NULL);
- }
-
-#ifdef ENABLE_CHECKING
- else
- verify_loop_structure ();
-#endif
+ if (!needs_fixup)
+ checking_verify_loop_structure ();
/* Clear all flags. */
if (recorded_exits)
- release_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. */
/* Dump loops. */
flow_loops_dump (dump_file, NULL, 1);
-#ifdef ENABLE_CHECKING
- verify_loop_structure ();
-#endif
+ checking_verify_loop_structure ();
timevar_pop (TV_LOOP_INIT);
}
/* Finalize loop structures. */
void
-loop_optimizer_finalize (void)
+loop_optimizer_finalize (struct function *fn)
{
- struct loop *loop;
+ class loop *loop;
basic_block bb;
timevar_push (TV_LOOP_FINI);
- if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
- release_recorded_exits ();
+ if (loops_state_satisfies_p (fn, LOOPS_HAVE_RECORDED_EXITS))
+ release_recorded_exits (fn);
- free_numbers_of_iterations_estimates ();
+ 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 (cfun->curr_properties & PROP_loops)
+ if (fn->curr_properties & PROP_loops)
{
- loops_state_clear (LOOP_CLOSED_SSA
+ 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 (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
+ loops_state_set (fn, LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
goto loop_fini_done;
}
- gcc_assert (current_loops != NULL);
-
- FOR_EACH_LOOP (loop, 0)
+ FOR_EACH_LOOP_FN (fn, loop, 0)
free_simple_loop_desc (loop);
/* Clean up. */
- flow_loops_free (current_loops);
- ggc_free (current_loops);
- current_loops = NULL;
+ flow_loops_free (loops_for_fn (fn));
+ ggc_free (loops_for_fn (fn));
+ set_loops_for_fn (fn, NULL);
- FOR_ALL_BB (bb)
+ FOR_ALL_BB_FN (bb, fn)
{
bb->loop_father = NULL;
}
{
basic_block bb;
int record_exits = 0;
- struct loop *loop;
+ class loop *loop;
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 ();
+ 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 (bb)
+ 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
while (loop->inner)
{
- struct loop *ploop = 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);
}
/* Mark the blocks whose loop has changed. */
if (changed_bbs)
{
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
if ((void *) (size_t) loop_depth (bb->loop_father) != bb->aux)
bitmap_set_bit (changed_bbs, bb->index);
}
/* Finally free deleted loops. */
+ bool any_deleted = false;
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);
-#ifdef ENABLE_CHECKING
- verify_loop_structure ();
-#endif
+ checking_verify_loop_structure ();
timevar_pop (TV_LOOP_INIT);
return number_of_loops (cfun) - old_nloops;
}
\f
-/* Gate for the RTL loop superpass. The actual passes are subpasses.
- See passes.c for more on that. */
-
-static bool
-gate_handle_loop2 (void)
-{
- if (optimize > 0
- && (flag_move_loop_invariants
- || flag_unswitch_loops
- || flag_peel_loops
- || flag_unroll_loops
-#ifdef HAVE_doloop_end
- || (flag_branch_on_count_reg && HAVE_doloop_end)
-#endif
- ))
- return true;
- else
- {
- /* No longer preserve loops, remove them now. */
- cfun->curr_properties &= ~PROP_loops;
- if (current_loops)
- loop_optimizer_finalize ();
- return false;
- }
-}
+/* The RTL loop superpass. The actual passes are subpasses. See passes.c for
+ more on that. */
namespace {
RTL_PASS, /* type */
"loop2", /* name */
OPTGROUP_LOOP, /* optinfo_flags */
- true, /* has_gate */
- false, /* has_execute */
TV_LOOP, /* tv_id */
0, /* properties_required */
0, /* properties_provided */
{}
/* opt_pass methods: */
- bool gate () { return gate_handle_loop2 (); }
+ 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 *
dump_flow_info (dump_file, dump_flags);
}
- loop_optimizer_init (LOOPS_NORMAL);
+ loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
return 0;
}
RTL_PASS, /* type */
"loop2_init", /* name */
OPTGROUP_LOOP, /* optinfo_flags */
- false, /* has_gate */
- true, /* has_execute */
TV_LOOP, /* tv_id */
0, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_verify_rtl_sharing, /* todo_flags_finish */
+ 0, /* todo_flags_finish */
};
class pass_rtl_loop_init : public rtl_opt_pass
{}
/* opt_pass methods: */
- unsigned int execute () { return rtl_loop_init (); }
+ virtual unsigned int execute (function *) { return rtl_loop_init (); }
}; // class pass_rtl_loop_init
\f
/* Finalization of the RTL loop passes. */
-static unsigned int
-rtl_loop_done (void)
-{
- /* No longer preserve loops, remove them now. */
- cfun->curr_properties &= ~PROP_loops;
- loop_optimizer_finalize ();
- free_dominance_info (CDI_DOMINATORS);
-
- cleanup_cfg (CLEANUP_EXPENSIVE);
- if (dump_file)
- {
- dump_reg_info (dump_file);
- dump_flow_info (dump_file, dump_flags);
- }
-
- return 0;
-}
-
namespace {
const pass_data pass_data_rtl_loop_done =
RTL_PASS, /* type */
"loop2_done", /* name */
OPTGROUP_LOOP, /* optinfo_flags */
- false, /* has_gate */
- true, /* has_execute */
TV_LOOP, /* tv_id */
0, /* properties_required */
0, /* properties_provided */
PROP_loops, /* properties_destroyed */
0, /* todo_flags_start */
- ( TODO_verify_flow | TODO_verify_rtl_sharing ), /* todo_flags_finish */
+ 0, /* todo_flags_finish */
};
class pass_rtl_loop_done : public rtl_opt_pass
{}
/* opt_pass methods: */
- unsigned int execute () { return rtl_loop_done (); }
+ 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 *
\f
/* Loop invariant code motion. */
-static bool
-gate_rtl_move_loop_invariants (void)
-{
- return flag_move_loop_invariants;
-}
-
-static unsigned int
-rtl_move_loop_invariants (void)
-{
- if (number_of_loops (cfun) > 1)
- move_loop_invariants ();
- return 0;
-}
namespace {
RTL_PASS, /* type */
"loop2_invariant", /* name */
OPTGROUP_LOOP, /* optinfo_flags */
- true, /* has_gate */
- true, /* has_execute */
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_verify_rtl_sharing ), /* todo_flags_finish */
+ ( TODO_df_verify | TODO_df_finish ), /* todo_flags_finish */
};
class pass_rtl_move_loop_invariants : public rtl_opt_pass
{}
/* opt_pass methods: */
- bool gate () { return gate_rtl_move_loop_invariants (); }
- unsigned int execute () { return rtl_move_loop_invariants (); }
+ 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
}
\f
-/* Loop unswitching for RTL. */
-static bool
-gate_rtl_unswitch (void)
-{
- return flag_unswitch_loops;
-}
-
-static unsigned int
-rtl_unswitch (void)
-{
- if (number_of_loops (cfun) > 1)
- unswitch_loops ();
- return 0;
-}
-
namespace {
-const pass_data pass_data_rtl_unswitch =
+const pass_data pass_data_rtl_unroll_loops =
{
RTL_PASS, /* type */
- "loop2_unswitch", /* name */
+ "loop2_unroll", /* name */
OPTGROUP_LOOP, /* optinfo_flags */
- true, /* has_gate */
- true, /* has_execute */
- TV_LOOP_UNSWITCH, /* tv_id */
+ TV_LOOP_UNROLL, /* tv_id */
0, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_verify_rtl_sharing, /* todo_flags_finish */
+ 0, /* todo_flags_finish */
};
-class pass_rtl_unswitch : public rtl_opt_pass
+class pass_rtl_unroll_loops : public rtl_opt_pass
{
public:
- pass_rtl_unswitch (gcc::context *ctxt)
- : rtl_opt_pass (pass_data_rtl_unswitch, ctxt)
+ pass_rtl_unroll_loops (gcc::context *ctxt)
+ : rtl_opt_pass (pass_data_rtl_unroll_loops, ctxt)
{}
/* opt_pass methods: */
- bool gate () { return gate_rtl_unswitch (); }
- unsigned int execute () { return rtl_unswitch (); }
-
-}; // class pass_rtl_unswitch
-
-} // anon namespace
+ virtual bool gate (function *)
+ {
+ return (flag_unroll_loops || flag_unroll_all_loops || cfun->has_unroll);
+ }
-rtl_opt_pass *
-make_pass_rtl_unswitch (gcc::context *ctxt)
-{
- return new pass_rtl_unswitch (ctxt);
-}
+ virtual unsigned int execute (function *);
-\f
-/* Loop unswitching for RTL. */
-static bool
-gate_rtl_unroll_and_peel_loops (void)
-{
- return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
-}
+}; // class pass_rtl_unroll_loops
-static unsigned int
-rtl_unroll_and_peel_loops (void)
+unsigned int
+pass_rtl_unroll_loops::execute (function *fun)
{
- if (number_of_loops (cfun) > 1)
+ if (number_of_loops (fun) > 1)
{
int flags = 0;
if (dump_file)
df_dump (dump_file);
- if (flag_peel_loops)
- flags |= UAP_PEEL;
if (flag_unroll_loops)
flags |= UAP_UNROLL;
if (flag_unroll_all_loops)
flags |= UAP_UNROLL_ALL;
- unroll_and_peel_loops (flags);
+ unroll_loops (flags);
}
return 0;
}
-namespace {
-
-const pass_data pass_data_rtl_unroll_and_peel_loops =
-{
- RTL_PASS, /* type */
- "loop2_unroll", /* name */
- OPTGROUP_LOOP, /* optinfo_flags */
- true, /* has_gate */
- true, /* has_execute */
- TV_LOOP_UNROLL, /* tv_id */
- 0, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_verify_rtl_sharing, /* todo_flags_finish */
-};
-
-class pass_rtl_unroll_and_peel_loops : public rtl_opt_pass
-{
-public:
- pass_rtl_unroll_and_peel_loops (gcc::context *ctxt)
- : rtl_opt_pass (pass_data_rtl_unroll_and_peel_loops, ctxt)
- {}
-
- /* opt_pass methods: */
- bool gate () { return gate_rtl_unroll_and_peel_loops (); }
- unsigned int execute () { return rtl_unroll_and_peel_loops (); }
-
-}; // class pass_rtl_unroll_and_peel_loops
-
} // anon namespace
rtl_opt_pass *
-make_pass_rtl_unroll_and_peel_loops (gcc::context *ctxt)
+make_pass_rtl_unroll_loops (gcc::context *ctxt)
{
- return new pass_rtl_unroll_and_peel_loops (ctxt);
+ return new pass_rtl_unroll_loops (ctxt);
}
\f
-/* The doloop optimization. */
-static bool
-gate_rtl_doloop (void)
-{
-#ifdef HAVE_doloop_end
- return (flag_branch_on_count_reg && HAVE_doloop_end);
-#else
- return 0;
-#endif
-}
-
-static unsigned int
-rtl_doloop (void)
-{
-#ifdef HAVE_doloop_end
- if (number_of_loops (cfun) > 1)
- doloop_optimize_loops ();
-#endif
- return 0;
-}
-
namespace {
const pass_data pass_data_rtl_doloop =
RTL_PASS, /* type */
"loop2_doloop", /* name */
OPTGROUP_LOOP, /* optinfo_flags */
- true, /* has_gate */
- true, /* has_execute */
TV_LOOP_DOLOOP, /* tv_id */
0, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_verify_rtl_sharing, /* todo_flags_finish */
+ 0, /* todo_flags_finish */
};
class pass_rtl_doloop : public rtl_opt_pass
{}
/* opt_pass methods: */
- bool gate () { return gate_rtl_doloop (); }
- unsigned int execute () { return rtl_doloop (); }
+ 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 *