/* Instruction scheduling pass. This file computes dependencies between
instructions.
- Copyright (C) 1992-2014 Free Software Foundation, Inc.
+ Copyright (C) 1992-2015 Free Software Foundation, Inc.
Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
and currently maintained by, Jim Wilson (wilson@cygnus.com)
#include "tm.h"
#include "diagnostic-core.h"
#include "rtl.h"
+#include "alias.h"
+#include "symtab.h"
#include "tree.h" /* FIXME: Used by call_may_noreturn_p. */
#include "tm_p.h"
#include "hard-reg-set.h"
#include "except.h"
#include "recog.h"
#include "emit-rtl.h"
+#include "dominance.h"
+#include "cfg.h"
+#include "cfgbuild.h"
+#include "predict.h"
+#include "basic-block.h"
#include "sched-int.h"
#include "params.h"
+#include "alloc-pool.h"
#include "cselib.h"
#include "ira.h"
#include "target.h"
}
/* Pool to hold all dependency nodes (dep_node_t). */
-static alloc_pool dn_pool;
+static pool_allocator<_dep_node> *dn_pool;
/* Number of dep_nodes out there. */
static int dn_pool_diff = 0;
static dep_node_t
create_dep_node (void)
{
- dep_node_t n = (dep_node_t) pool_alloc (dn_pool);
+ dep_node_t n = dn_pool->allocate ();
dep_link_t back = DEP_NODE_BACK (n);
dep_link_t forw = DEP_NODE_FORW (n);
--dn_pool_diff;
- pool_free (dn_pool, n);
+ dn_pool->remove (n);
}
/* Pool to hold dependencies lists (deps_list_t). */
-static alloc_pool dl_pool;
+static pool_allocator<_deps_list> *dl_pool;
/* Number of deps_lists out there. */
static int dl_pool_diff = 0;
static deps_list_t
create_deps_list (void)
{
- deps_list_t l = (deps_list_t) pool_alloc (dl_pool);
+ deps_list_t l = dl_pool->allocate ();
DEPS_LIST_FIRST (l) = NULL;
DEPS_LIST_N_LINKS (l) = 0;
--dl_pool_diff;
- pool_free (dl_pool, l);
+ dl_pool->remove (l);
}
/* Return true if there is no dep_nodes and deps_lists out there.
static void add_dependence_list_and_free (struct deps_desc *, rtx_insn *,
rtx_insn_list **, int, enum reg_note,
bool);
-static void delete_all_dependences (rtx);
+static void delete_all_dependences (rtx_insn *);
static void chain_to_prev_insn (rtx_insn *);
static void flush_pending_lists (struct deps_desc *, rtx_insn *, int, int);
static void sched_analyze_2 (struct deps_desc *, rtx, rtx_insn *);
static void sched_analyze_insn (struct deps_desc *, rtx, rtx_insn *);
-static bool sched_has_condition_p (const_rtx);
+static bool sched_has_condition_p (const rtx_insn *);
static int conditions_mutex_p (const_rtx, const_rtx, bool, bool);
static enum DEPS_ADJUST_RESULT maybe_add_or_update_dep_1 (dep_t, bool,
it is set to TRUE when the returned comparison should be reversed
to get the actual condition. */
static rtx
-sched_get_condition_with_rev_uncached (const_rtx insn, bool *rev)
+sched_get_condition_with_rev_uncached (const rtx_insn *insn, bool *rev)
{
rtx pat = PATTERN (insn);
rtx src;
find such a condition. The caller should make a copy of the condition
before using it. */
rtx
-sched_get_reverse_condition_uncached (const_rtx insn)
+sched_get_reverse_condition_uncached (const rtx_insn *insn)
{
bool rev;
rtx cond = sched_get_condition_with_rev_uncached (insn, &rev);
We only do actual work the first time we come here for an insn; the
results are cached in INSN_CACHED_COND and INSN_REVERSE_COND. */
static rtx
-sched_get_condition_with_rev (const_rtx insn, bool *rev)
+sched_get_condition_with_rev (const rtx_insn *insn, bool *rev)
{
bool tmp;
/* True when we can find a condition under which INSN is executed. */
static bool
-sched_has_condition_p (const_rtx insn)
+sched_has_condition_p (const rtx_insn *insn)
{
return !! sched_get_condition_with_rev (insn, NULL);
}
/* Return true if insn1 and insn2 can never depend on one another because
the conditions under which they are executed are mutually exclusive. */
bool
-sched_insns_conditions_mutex_p (const_rtx insn1, const_rtx insn2)
+sched_insns_conditions_mutex_p (const rtx_insn *insn1, const rtx_insn *insn2)
{
rtx cond1, cond2;
bool rev1 = false, rev2 = false;
/* Return true if INSN can potentially be speculated with type DS. */
bool
-sched_insn_is_legitimate_for_speculation_p (const_rtx insn, ds_t ds)
+sched_insn_is_legitimate_for_speculation_p (const rtx_insn *insn, ds_t ds)
{
if (HAS_INTERNAL_DEP (insn))
return false;
if (SCHED_GROUP_P (insn))
return false;
- if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX (insn)))
+ if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX_INSN (insn)))
return false;
if (side_effects_p (PATTERN (insn)))
/* Initialize data for INSN. */
void
-sd_init_insn (rtx insn)
+sd_init_insn (rtx_insn *insn)
{
INSN_HARD_BACK_DEPS (insn) = create_deps_list ();
INSN_SPEC_BACK_DEPS (insn) = create_deps_list ();
/* Free data for INSN. */
void
-sd_finish_insn (rtx insn)
+sd_finish_insn (rtx_insn *insn)
{
/* ??? It would be nice to deallocate dependency caches here. */
switch (ask_dependency_caches (new_dep))
{
case DEP_PRESENT:
+ dep_t present_dep;
+ sd_iterator_def sd_it;
+
+ present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep),
+ DEP_CON (new_dep),
+ resolved_p, &sd_it);
+ DEP_MULTIPLE (present_dep) = 1;
return DEP_PRESENT;
case DEP_CHANGED:
occurrences removed. */
static int
-remove_from_dependence_list (rtx insn, rtx_insn_list **listp)
+remove_from_dependence_list (rtx_insn *insn, rtx_insn_list **listp)
{
int removed = 0;
/* Same as above, but process two lists at once. */
static int
-remove_from_both_dependence_lists (rtx insn,
+remove_from_both_dependence_lists (rtx_insn *insn,
rtx_insn_list **listp,
rtx_expr_list **exprp)
{
/* Clear all dependencies for an insn. */
static void
-delete_all_dependences (rtx insn)
+delete_all_dependences (rtx_insn *insn)
{
sd_iterator_def sd_it;
dep_t dep;
{
unsigned i;
reg_set_iterator rsi;
- rtx list;
struct reg_use_data *use, *use2, *next;
struct deps_reg *reg_last;
reg_last = &deps->reg_last[i];
/* Create the cycle list of uses. */
- for (list = reg_last->uses; list; list = XEXP (list, 1))
+ for (rtx_insn_list *list = reg_last->uses; list; list = list->next ())
{
- use2 = create_insn_reg_use (i, as_a <rtx_insn *> (XEXP (list, 0)));
+ use2 = create_insn_reg_use (i, list->insn ());
next = use->next_regno_use;
use->next_regno_use = use2;
use2->next_regno_use = next;
regno = REGNO (reg);
if (regno < FIRST_PSEUDO_REGISTER)
- mark_insn_hard_regno_birth (insn, regno,
- hard_regno_nregs[regno][GET_MODE (reg)],
+ mark_insn_hard_regno_birth (insn, regno, REG_NREGS (reg),
clobber_p, unused_p);
else
mark_insn_pseudo_birth (insn, regno, clobber_p, unused_p);
regno = REGNO (reg);
if (regno < FIRST_PSEUDO_REGISTER)
- mark_hard_regno_death (regno, hard_regno_nregs[regno][GET_MODE (reg)]);
+ mark_hard_regno_death (regno, REG_NREGS (reg));
else
mark_pseudo_death (regno);
}
/* Set up reg pressure info related to INSN. */
void
-init_insn_reg_pressure_info (rtx insn)
+init_insn_reg_pressure_info (rtx_insn *insn)
{
int i, len;
enum reg_class cl;
CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */
static void
-sched_analyze_reg (struct deps_desc *deps, int regno, enum machine_mode mode,
+sched_analyze_reg (struct deps_desc *deps, int regno, machine_mode mode,
enum rtx_code ref, rtx_insn *insn)
{
/* We could emit new pseudos in renaming. Extend the reg structures. */
if (REG_P (dest))
{
int regno = REGNO (dest);
- enum machine_mode mode = GET_MODE (dest);
+ machine_mode mode = GET_MODE (dest);
sched_analyze_reg (deps, regno, mode, code, insn);
if (sched_deps_info->use_cselib)
{
- enum machine_mode address_mode = get_address_mode (dest);
+ machine_mode address_mode = get_address_mode (dest);
t = shallow_copy_rtx (dest);
cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
/* Pending lists can't get larger with a readonly context. */
if (!deps->readonly
&& ((deps->pending_read_list_length + deps->pending_write_list_length)
- > MAX_PENDING_LIST_LENGTH))
+ >= MAX_PENDING_LIST_LENGTH))
{
/* Flush all pending reads and writes to prevent the pending lists
from getting any larger. Insn scheduling runs too slowly when
}
else
{
- rtx pending, pending_mem;
+ rtx_insn_list *pending;
+ rtx_expr_list *pending_mem;
pending = deps->pending_read_insns;
pending_mem = deps->pending_read_mems;
while (pending)
{
- if (anti_dependence (XEXP (pending_mem, 0), t)
- && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
- note_mem_dep (t, XEXP (pending_mem, 0), as_a <rtx_insn *> (XEXP (pending, 0)),
+ if (anti_dependence (pending_mem->element (), t)
+ && ! sched_insns_conditions_mutex_p (insn, pending->insn ()))
+ note_mem_dep (t, pending_mem->element (), pending->insn (),
DEP_ANTI);
- pending = XEXP (pending, 1);
- pending_mem = XEXP (pending_mem, 1);
+ pending = pending->next ();
+ pending_mem = pending_mem->next ();
}
pending = deps->pending_write_insns;
pending_mem = deps->pending_write_mems;
while (pending)
{
- if (output_dependence (XEXP (pending_mem, 0), t)
- && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
- note_mem_dep (t, XEXP (pending_mem, 0),
- as_a <rtx_insn *> (XEXP (pending, 0)),
+ if (output_dependence (pending_mem->element (), t)
+ && ! sched_insns_conditions_mutex_p (insn, pending->insn ()))
+ note_mem_dep (t, pending_mem->element (),
+ pending->insn (),
DEP_OUTPUT);
- pending = XEXP (pending, 1);
- pending_mem = XEXP (pending_mem, 1);
+ pending = pending->next ();
+ pending_mem = pending_mem-> next ();
}
add_dependence_list (insn, deps->last_pending_memory_flush, 1,
return;
-#ifdef HAVE_cc0
case CC0:
+ if (!HAVE_cc0)
+ gcc_unreachable ();
+
/* User of CC0 depends on immediately preceding insn. */
SCHED_GROUP_P (insn) = 1;
/* Don't move CC0 setter to another block (it can set up the
sched_deps_info->finish_rhs ();
return;
-#endif
case REG:
{
int regno = REGNO (x);
- enum machine_mode mode = GET_MODE (x);
+ machine_mode mode = GET_MODE (x);
sched_analyze_reg (deps, regno, mode, USE, insn);
case MEM:
{
/* Reading memory. */
- rtx u;
- rtx pending, pending_mem;
+ rtx_insn_list *u;
+ rtx_insn_list *pending;
+ rtx_expr_list *pending_mem;
rtx t = x;
if (sched_deps_info->use_cselib)
{
- enum machine_mode address_mode = get_address_mode (t);
+ machine_mode address_mode = get_address_mode (t);
t = shallow_copy_rtx (t);
cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
pending_mem = deps->pending_read_mems;
while (pending)
{
- if (read_dependence (XEXP (pending_mem, 0), t)
+ if (read_dependence (pending_mem->element (), t)
&& ! sched_insns_conditions_mutex_p (insn,
- XEXP (pending, 0)))
- note_mem_dep (t, XEXP (pending_mem, 0),
- as_a <rtx_insn *> (XEXP (pending, 0)),
+ pending->insn ()))
+ note_mem_dep (t, pending_mem->element (),
+ pending->insn (),
DEP_ANTI);
- pending = XEXP (pending, 1);
- pending_mem = XEXP (pending_mem, 1);
+ pending = pending->next ();
+ pending_mem = pending_mem->next ();
}
pending = deps->pending_write_insns;
pending_mem = deps->pending_write_mems;
while (pending)
{
- if (true_dependence (XEXP (pending_mem, 0), VOIDmode, t)
+ if (true_dependence (pending_mem->element (), VOIDmode, t)
&& ! sched_insns_conditions_mutex_p (insn,
- XEXP (pending, 0)))
- note_mem_dep (t, XEXP (pending_mem, 0),
- as_a <rtx_insn *> (XEXP (pending, 0)),
+ pending->insn ()))
+ note_mem_dep (t, pending_mem->element (),
+ pending->insn (),
sched_deps_info->generate_spec_deps
? BEGIN_DATA | DEP_TRUE : DEP_TRUE);
- pending = XEXP (pending, 1);
- pending_mem = XEXP (pending_mem, 1);
+ pending = pending->next ();
+ pending_mem = pending_mem->next ();
}
- for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
- add_dependence (insn, as_a <rtx_insn *> (XEXP (u, 0)),
- REG_DEP_ANTI);
+ for (u = deps->last_pending_memory_flush; u; u = u->next ())
+ add_dependence (insn, u->insn (), REG_DEP_ANTI);
- for (u = deps->pending_jump_insns; u; u = XEXP (u, 1))
+ for (u = deps->pending_jump_insns; u; u = u->next ())
if (deps_may_trap_p (x))
{
if ((sched_deps_info->generate_spec_deps)
ds_t ds = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
MAX_DEP_WEAK);
- note_dep (as_a <rtx_insn *> (XEXP (u, 0)), ds);
+ note_dep (u->insn (), ds);
}
else
- add_dependence (insn, as_a <rtx_insn *> (XEXP (u, 0)),
- REG_DEP_CONTROL);
+ add_dependence (insn, u->insn (), REG_DEP_CONTROL);
}
}
{
if ((deps->pending_read_list_length
+ deps->pending_write_list_length)
- > MAX_PENDING_LIST_LENGTH
+ >= MAX_PENDING_LIST_LENGTH
&& !DEBUG_INSN_P (insn))
flush_pending_lists (deps, insn, true, true);
add_insn_mem_dependence (deps, true, insn, x);
sched_deps_info->finish_rhs ();
}
-/* Try to group two fuseable insns together to prevent scheduler
+/* Try to group two fusible insns together to prevent scheduler
from scheduling them apart. */
static void
prev = prev_nonnote_nondebug_insn (insn);
if (!prev
|| !insn_set
- || !single_set (prev)
- || !modified_in_p (SET_DEST (insn_set), prev))
+ || !single_set (prev))
return;
}
if (JUMP_P (insn))
{
- rtx next;
- next = next_nonnote_nondebug_insn (insn);
+ rtx_insn *next = next_nonnote_nondebug_insn (insn);
if (next && BARRIER_P (next))
reg_pending_barrier = MOVE_BARRIER;
else
{
- rtx pending, pending_mem;
+ rtx_insn_list *pending;
+ rtx_expr_list *pending_mem;
if (sched_deps_info->compute_jump_reg_dependencies)
{
pending_mem = deps->pending_write_mems;
while (pending)
{
- if (! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
- add_dependence (insn, as_a <rtx_insn *> (XEXP (pending, 0)),
+ if (! sched_insns_conditions_mutex_p (insn, pending->insn ()))
+ add_dependence (insn, pending->insn (),
REG_DEP_OUTPUT);
- pending = XEXP (pending, 1);
- pending_mem = XEXP (pending_mem, 1);
+ pending = pending->next ();
+ pending_mem = pending_mem->next ();
}
pending = deps->pending_read_insns;
pending_mem = deps->pending_read_mems;
while (pending)
{
- if (MEM_VOLATILE_P (XEXP (pending_mem, 0))
- && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
- add_dependence (insn, as_a <rtx_insn *> (XEXP (pending, 0)),
+ if (MEM_VOLATILE_P (pending_mem->element ())
+ && ! sched_insns_conditions_mutex_p (insn, pending->insn ()))
+ add_dependence (insn, pending->insn (),
REG_DEP_OUTPUT);
- pending = XEXP (pending, 1);
- pending_mem = XEXP (pending_mem, 1);
+ pending = pending->next ();
+ pending_mem = pending_mem->next ();
}
add_dependence_list (insn, deps->last_pending_memory_flush, 1,
if (DEBUG_INSN_P (insn))
{
rtx_insn *prev = deps->last_debug_insn;
- rtx u;
+ rtx_insn_list *u;
if (!deps->readonly)
deps->last_debug_insn = insn;
REG_DEP_ANTI, false);
if (!sel_sched_p ())
- for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
- add_dependence (insn, as_a <rtx_insn *> (XEXP (u, 0)), REG_DEP_ANTI);
+ for (u = deps->last_pending_memory_flush; u; u = u->next ())
+ add_dependence (insn, u->insn (), REG_DEP_ANTI);
EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
{
{
rtx other = XEXP (list, 0);
if (INSN_CACHED_COND (other) != const_true_rtx
- && refers_to_regno_p (i, i + 1, INSN_CACHED_COND (other), NULL))
+ && refers_to_regno_p (i, INSN_CACHED_COND (other)))
INSN_CACHED_COND (other) = const_true_rtx;
}
}
EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
{
struct deps_reg *reg_last = &deps->reg_last[i];
- if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
- || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
+ if (reg_last->uses_length >= MAX_PENDING_LIST_LENGTH
+ || reg_last->clobbers_length >= MAX_PENDING_LIST_LENGTH)
{
add_dependence_list_and_free (deps, insn, ®_last->sets, 0,
REG_DEP_OUTPUT, false);
/* FIXME: Why can't this function just use flags_from_decl_or_type and
test for ECF_NORETURN? */
static bool
-call_may_noreturn_p (rtx insn)
+call_may_noreturn_p (rtx_insn *insn)
{
rtx call;
instruction of that group. */
static bool
-chain_to_prev_insn_p (rtx insn)
+chain_to_prev_insn_p (rtx_insn *insn)
{
- rtx prev, x;
-
/* INSN forms a group with the previous instruction. */
if (SCHED_GROUP_P (insn))
return true;
part of R, the clobber was added specifically to help us track the
liveness of R. There's no point scheduling the clobber and leaving
INSN behind, especially if we move the clobber to another block. */
- prev = prev_nonnote_nondebug_insn (insn);
+ rtx_insn *prev = prev_nonnote_nondebug_insn (insn);
if (prev
&& INSN_P (prev)
&& BLOCK_FOR_INSN (prev) == BLOCK_FOR_INSN (insn)
&& GET_CODE (PATTERN (prev)) == CLOBBER)
{
- x = XEXP (PATTERN (prev), 0);
+ rtx x = XEXP (PATTERN (prev), 0);
if (set_of (x, insn))
return true;
}
rtx_insn_list *cond_deps = NULL;
t = XEXP (t, 0);
regno = REGNO (t);
- nregs = hard_regno_nregs[regno][GET_MODE (t)];
+ nregs = REG_NREGS (t);
while (nregs-- > 0)
{
struct deps_reg *reg_last = &deps->reg_last[regno + nregs];
&& sel_insn_is_speculation_check (insn)))
{
/* Keep the list a reasonable size. */
- if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
+ if (deps->pending_flush_length++ >= MAX_PENDING_LIST_LENGTH)
flush_pending_lists (deps, insn, true, true);
else
deps->pending_jump_insns
/* Initialize DEPS for the new block beginning with HEAD. */
void
-deps_start_bb (struct deps_desc *deps, rtx head)
+deps_start_bb (struct deps_desc *deps, rtx_insn *head)
{
gcc_assert (!deps->readonly);
hard registers correct. */
if (! reload_completed && !LABEL_P (head))
{
- rtx insn = prev_nonnote_nondebug_insn (head);
+ rtx_insn *insn = prev_nonnote_nondebug_insn (head);
if (insn && CALL_P (insn))
deps->in_post_call_group_p = post_call_initial;
/* Helper for sched_free_deps ().
Delete INSN's (RESOLVED_P) backward dependencies. */
static void
-delete_dep_nodes_in_back_deps (rtx insn, bool resolved_p)
+delete_dep_nodes_in_back_deps (rtx_insn *insn, bool resolved_p)
{
sd_iterator_def sd_it;
dep_t dep;
/* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
deps_lists. */
void
-sched_free_deps (rtx head, rtx tail, bool resolved_p)
+sched_free_deps (rtx_insn *head, rtx_insn *tail, bool resolved_p)
{
- rtx insn;
- rtx next_tail = NEXT_INSN (tail);
+ rtx_insn *insn;
+ rtx_insn *next_tail = NEXT_INSN (tail);
/* We make two passes since some insns may be scheduled before their
dependencies are resolved. */
if (global_p)
{
- dl_pool = create_alloc_pool ("deps_list", sizeof (struct _deps_list),
+ dl_pool = new pool_allocator<_deps_list> ("deps_list",
/* Allocate lists for one block at a time. */
insns_in_block);
- dn_pool = create_alloc_pool ("dep_node", sizeof (struct _dep_node),
+ dn_pool = new pool_allocator<_dep_node> ("dep_node",
/* Allocate nodes for one block at a time.
We assume that average insn has
5 producers. */
sched_deps_finish (void)
{
gcc_assert (deps_pools_are_empty_p ());
- free_alloc_pool_if_empty (&dn_pool);
- free_alloc_pool_if_empty (&dl_pool);
- gcc_assert (dn_pool == NULL && dl_pool == NULL);
+ dn_pool->release_if_empty ();
+ dn_pool = NULL;
+ dl_pool->release_if_empty ();
+ dl_pool = NULL;
h_d_i_d.release ();
cache_size = 0;
if (regs_equal && REGNO (SET_DEST (pat)) == STACK_POINTER_REGNUM)
{
/* Note that the sign has already been reversed for !before_mem. */
-#ifdef STACK_GROWS_DOWNWARD
- return mii->inc_constant > 0;
-#else
- return mii->inc_constant < 0;
-#endif
+ if (STACK_GROWS_DOWNWARD)
+ return mii->inc_constant > 0;
+ else
+ return mii->inc_constant < 0;
}
return true;
}
goto next;
}
- /* The inc instruction could have clobbers, make sure those
- registers are not used in mem insn. */
- FOR_EACH_INSN_DEF (def, mii->inc_insn)
- if (!reg_overlap_mentioned_p (DF_REF_REG (def), mii->mem_reg0))
- {
- df_ref use;
- FOR_EACH_INSN_USE (use, mii->mem_insn)
- if (reg_overlap_mentioned_p (DF_REF_REG (def),
- DF_REF_REG (use)))
- {
- if (sched_verbose >= 5)
- fprintf (sched_dump,
- "inc clobber used in store failure.\n");
- goto next;
- }
- }
-
newaddr = mii->inc_input;
if (mii->mem_index != NULL_RTX)
newaddr = gen_rtx_PLUS (GET_MODE (newaddr), newaddr,