/* Instruction scheduling pass. This file computes dependencies between
instructions.
Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
- 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
+ 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
+ 2011, 2012
Free Software Foundation, Inc.
Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
and currently maintained by, Jim Wilson (wilson@cygnus.com)
#include "system.h"
#include "coretypes.h"
#include "tm.h"
-#include "toplev.h"
+#include "diagnostic-core.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
#include "insn-config.h"
#include "insn-attr.h"
#include "except.h"
-#include "toplev.h"
#include "recog.h"
#include "sched-int.h"
#include "params.h"
#include "cselib.h"
+#include "ira.h"
+#include "target.h"
+
+#ifdef INSN_SCHEDULING
#ifdef ENABLE_CHECKING
#define CHECK (true)
#define CHECK (false)
#endif
+/* Holds current parameters for the dependency analyzer. */
+struct sched_deps_info_def *sched_deps_info;
+
+/* The data is specific to the Haifa scheduler. */
+VEC(haifa_deps_insn_data_def, heap) *h_d_i_d = NULL;
+
/* Return the major type present in the DS. */
enum reg_note
ds_to_dk (ds_t ds)
if (ds & DEP_OUTPUT)
return REG_DEP_OUTPUT;
+ if (ds & DEP_CONTROL)
+ return REG_DEP_CONTROL;
+
gcc_assert (ds & DEP_ANTI);
return REG_DEP_ANTI;
case REG_DEP_OUTPUT:
return DEP_OUTPUT;
+ case REG_DEP_CONTROL:
+ return DEP_CONTROL;
+
default:
gcc_assert (dk == REG_DEP_ANTI);
return DEP_ANTI;
/* Functions to operate with dependence information container - dep_t. */
/* Init DEP with the arguments. */
-static void
-init_dep_1 (dep_t dep, rtx pro, rtx con, enum reg_note kind, ds_t ds)
+void
+init_dep_1 (dep_t dep, rtx pro, rtx con, enum reg_note type, ds_t ds)
{
DEP_PRO (dep) = pro;
DEP_CON (dep) = con;
- DEP_KIND (dep) = kind;
+ DEP_TYPE (dep) = type;
DEP_STATUS (dep) = ds;
+ DEP_COST (dep) = UNKNOWN_DEP_COST;
}
/* Init DEP with the arguments.
{
ds_t ds;
- if ((current_sched_info->flags & USE_DEPS_LIST) != 0)
+ if ((current_sched_info->flags & USE_DEPS_LIST))
ds = dk_to_ds (kind);
else
- ds = -1;
+ ds = 0;
init_dep_1 (dep, pro, con, kind, ds);
}
memcpy (to, from, sizeof (*to));
}
-/* Functions to operate with a single link from the dependencies lists -
- dep_link_t. */
+static void dump_ds (FILE *, ds_t);
-/* Return true if dep_link L is consistent. */
-static bool
-dep_link_consistent_p (dep_link_t l)
+/* Define flags for dump_dep (). */
+
+/* Dump producer of the dependence. */
+#define DUMP_DEP_PRO (2)
+
+/* Dump consumer of the dependence. */
+#define DUMP_DEP_CON (4)
+
+/* Dump type of the dependence. */
+#define DUMP_DEP_TYPE (8)
+
+/* Dump status of the dependence. */
+#define DUMP_DEP_STATUS (16)
+
+/* Dump all information about the dependence. */
+#define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE \
+ |DUMP_DEP_STATUS)
+
+/* Dump DEP to DUMP.
+ FLAGS is a bit mask specifying what information about DEP needs
+ to be printed.
+ If FLAGS has the very first bit set, then dump all information about DEP
+ and propagate this bit into the callee dump functions. */
+static void
+dump_dep (FILE *dump, dep_t dep, int flags)
{
- dep_link_t next = DEP_LINK_NEXT (l);
+ if (flags & 1)
+ flags |= DUMP_DEP_ALL;
+
+ fprintf (dump, "<");
+
+ if (flags & DUMP_DEP_PRO)
+ fprintf (dump, "%d; ", INSN_UID (DEP_PRO (dep)));
+
+ if (flags & DUMP_DEP_CON)
+ fprintf (dump, "%d; ", INSN_UID (DEP_CON (dep)));
+
+ if (flags & DUMP_DEP_TYPE)
+ {
+ char t;
+ enum reg_note type = DEP_TYPE (dep);
+
+ switch (type)
+ {
+ case REG_DEP_TRUE:
+ t = 't';
+ break;
+
+ case REG_DEP_OUTPUT:
+ t = 'o';
+ break;
+
+ case REG_DEP_CONTROL:
+ t = 'c';
+ break;
+
+ case REG_DEP_ANTI:
+ t = 'a';
+ break;
+
+ default:
+ gcc_unreachable ();
+ break;
+ }
+
+ fprintf (dump, "%c; ", t);
+ }
+
+ if (flags & DUMP_DEP_STATUS)
+ {
+ if (current_sched_info->flags & USE_DEPS_LIST)
+ dump_ds (dump, DEP_STATUS (dep));
+ }
+
+ fprintf (dump, ">");
+}
+
+/* Default flags for dump_dep (). */
+static int dump_dep_flags = (DUMP_DEP_PRO | DUMP_DEP_CON);
+
+/* Dump all fields of DEP to STDERR. */
+void
+sd_debug_dep (dep_t dep)
+{
+ dump_dep (stderr, dep, 1);
+ fprintf (stderr, "\n");
+}
+
+/* Determine whether DEP is a dependency link of a non-debug insn on a
+ debug insn. */
- return (next == NULL
- || &DEP_LINK_NEXT (l) == DEP_LINK_PREV_NEXTP (next));
+static inline bool
+depl_on_debug_p (dep_link_t dep)
+{
+ return (DEBUG_INSN_P (DEP_LINK_PRO (dep))
+ && !DEBUG_INSN_P (DEP_LINK_CON (dep)));
}
+/* Functions to operate with a single link from the dependencies lists -
+ dep_link_t. */
+
/* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by
PREV_NEXT_P. */
static void
add_to_deps_list (dep_link_t link, deps_list_t l)
{
attach_dep_link (link, &DEPS_LIST_FIRST (l));
+
+ /* Don't count debug deps. */
+ if (!depl_on_debug_p (link))
+ ++DEPS_LIST_N_LINKS (l);
}
/* Detach dep_link L from the list. */
if (next != NULL)
DEP_LINK_PREV_NEXTP (next) = prev_nextp;
- /* Though this is property is not used anywhere but in the assert in
- attach_dep_link (), this can prevent latent errors. */
DEP_LINK_PREV_NEXTP (l) = NULL;
DEP_LINK_NEXT (l) = NULL;
}
-/* Move LINK from whatever list it is now to L. */
-void
-move_dep_link (dep_link_t link, deps_list_t l)
+/* Remove link LINK from list LIST. */
+static void
+remove_from_deps_list (dep_link_t link, deps_list_t list)
{
detach_dep_link (link);
- add_to_deps_list (link, l);
-}
-
-/* Check L's and its successors' consistency.
- This is, potentially, an expensive check, hence it should be guarded by
- ENABLE_CHECKING at all times. */
-static bool
-dep_links_consistent_p (dep_link_t l)
-{
- while (l != NULL)
- {
- if (dep_link_consistent_p (l))
- l = DEP_LINK_NEXT (l);
- else
- return false;
- }
- return true;
+ /* Don't count debug deps. */
+ if (!depl_on_debug_p (link))
+ --DEPS_LIST_N_LINKS (list);
}
-/* Dump dep_nodes starting from l. */
+/* Move link LINK from list FROM to list TO. */
static void
-dump_dep_links (FILE *dump, dep_link_t l)
+move_dep_link (dep_link_t link, deps_list_t from, deps_list_t to)
{
- while (l != NULL)
- {
- dep_t d = DEP_LINK_DEP (l);
-
- fprintf (dump, "%d%c>%d ", INSN_UID (DEP_PRO (d)),
- dep_link_consistent_p (l) ? '-' : '!', INSN_UID (DEP_CON (d)));
-
- l = DEP_LINK_NEXT (l);
- }
-
- fprintf (dump, "\n");
+ remove_from_deps_list (link, from);
+ add_to_deps_list (link, to);
}
-/* Dump dep_nodes starting from L to stderr. */
-void
-debug_dep_links (dep_link_t l)
+/* Return true of LINK is not attached to any list. */
+static bool
+dep_link_is_detached_p (dep_link_t link)
{
- dump_dep_links (stderr, l);
+ return DEP_LINK_PREV_NEXTP (link) == NULL;
}
-/* Obstack to allocate dep_nodes and deps_lists on. */
-static struct obstack deps_obstack;
+/* Pool to hold all dependency nodes (dep_node_t). */
+static alloc_pool dn_pool;
-/* Obstack to hold forward dependencies lists (deps_list_t). */
-static struct obstack *dl_obstack = &deps_obstack;
+/* Number of dep_nodes out there. */
+static int dn_pool_diff = 0;
-/* Obstack to hold all dependency nodes (dep_node_t). */
-static struct obstack *dn_obstack = &deps_obstack;
+/* Create a dep_node. */
+static dep_node_t
+create_dep_node (void)
+{
+ dep_node_t n = (dep_node_t) pool_alloc (dn_pool);
+ dep_link_t back = DEP_NODE_BACK (n);
+ dep_link_t forw = DEP_NODE_FORW (n);
-/* Functions to operate with dependences lists - deps_list_t. */
+ DEP_LINK_NODE (back) = n;
+ DEP_LINK_NEXT (back) = NULL;
+ DEP_LINK_PREV_NEXTP (back) = NULL;
-/* Allocate deps_list.
+ DEP_LINK_NODE (forw) = n;
+ DEP_LINK_NEXT (forw) = NULL;
+ DEP_LINK_PREV_NEXTP (forw) = NULL;
- If ON_OBSTACK_P is true, allocate the list on the obstack. This is done for
- INSN_FORW_DEPS lists because they should live till the end of scheduling.
+ ++dn_pool_diff;
- INSN_BACK_DEPS and INSN_RESOLVED_BACK_DEPS lists are allocated on the free
- store and are being freed in haifa-sched.c: schedule_insn (). */
-static deps_list_t
-alloc_deps_list (bool on_obstack_p)
-{
- if (on_obstack_p)
- return obstack_alloc (dl_obstack, sizeof (struct _deps_list));
- else
- return xmalloc (sizeof (struct _deps_list));
+ return n;
}
-/* Initialize deps_list L. */
+/* Delete dep_node N. N must not be connected to any deps_list. */
static void
-init_deps_list (deps_list_t l)
+delete_dep_node (dep_node_t n)
{
- DEPS_LIST_FIRST (l) = NULL;
-}
+ gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n))
+ && dep_link_is_detached_p (DEP_NODE_FORW (n)));
-/* Create (allocate and init) deps_list.
- The meaning of ON_OBSTACK_P is the same as in alloc_deps_list (). */
-deps_list_t
-create_deps_list (bool on_obstack_p)
-{
- deps_list_t l = alloc_deps_list (on_obstack_p);
+ --dn_pool_diff;
- init_deps_list (l);
- return l;
+ pool_free (dn_pool, n);
}
-/* Free dep_data_nodes that present in L. */
-static void
-clear_deps_list (deps_list_t l)
-{
- /* All dep_nodes are allocated on the dn_obstack. They'll be freed with
- the obstack. */
-
- DEPS_LIST_FIRST (l) = NULL;
-}
+/* Pool to hold dependencies lists (deps_list_t). */
+static alloc_pool dl_pool;
-/* Free deps_list L. */
-void
-free_deps_list (deps_list_t l)
-{
- gcc_assert (deps_list_empty_p (l));
- free (l);
-}
+/* Number of deps_lists out there. */
+static int dl_pool_diff = 0;
-/* Delete (clear and free) deps_list L. */
-void
-delete_deps_list (deps_list_t l)
-{
- clear_deps_list (l);
- free_deps_list (l);
-}
+/* Functions to operate with dependences lists - deps_list_t. */
-/* Return true if L is empty. */
-bool
+/* Return true if list L is empty. */
+static bool
deps_list_empty_p (deps_list_t l)
{
- return DEPS_LIST_FIRST (l) == NULL;
+ return DEPS_LIST_N_LINKS (l) == 0;
}
-/* Check L's consistency.
- This is, potentially, an expensive check, hence it should be guarded by
- ENABLE_CHECKING at all times. */
-static bool
-deps_list_consistent_p (deps_list_t l)
+/* Create a new deps_list. */
+static deps_list_t
+create_deps_list (void)
{
- dep_link_t first = DEPS_LIST_FIRST (l);
+ deps_list_t l = (deps_list_t) pool_alloc (dl_pool);
- return (first == NULL
- || (&DEPS_LIST_FIRST (l) == DEP_LINK_PREV_NEXTP (first)
- && dep_links_consistent_p (first)));
-}
-
-/* Dump L to F. */
-static void
-dump_deps_list (FILE *f, deps_list_t l)
-{
- dump_dep_links (f, DEPS_LIST_FIRST (l));
-}
+ DEPS_LIST_FIRST (l) = NULL;
+ DEPS_LIST_N_LINKS (l) = 0;
-/* Dump L to STDERR. */
-void
-debug_deps_list (deps_list_t l)
-{
- dump_deps_list (stderr, l);
+ ++dl_pool_diff;
+ return l;
}
-/* Add a dependency described by DEP to the list L.
- L should be either INSN_BACK_DEPS or INSN_RESOLVED_BACK_DEPS. */
-void
-add_back_dep_to_deps_list (deps_list_t l, dep_t dep_from)
+/* Free deps_list L. */
+static void
+free_deps_list (deps_list_t l)
{
- dep_node_t n = (dep_node_t) obstack_alloc (dn_obstack,
- sizeof (*n));
- dep_t dep_to = DEP_NODE_DEP (n);
- dep_link_t back = DEP_NODE_BACK (n);
- dep_link_t forw = DEP_NODE_FORW (n);
-
- copy_dep (dep_to, dep_from);
-
- DEP_LINK_NODE (back) = n;
- DEP_LINK_NODE (forw) = n;
+ gcc_assert (deps_list_empty_p (l));
- /* There is no particular need to initialize these four fields except to make
- assert in attach_dep_link () happy. */
- DEP_LINK_NEXT (back) = NULL;
- DEP_LINK_PREV_NEXTP (back) = NULL;
- DEP_LINK_NEXT (forw) = NULL;
- DEP_LINK_PREV_NEXTP (forw) = NULL;
+ --dl_pool_diff;
- add_to_deps_list (back, l);
+ pool_free (dl_pool, l);
}
-/* Find the dep_link with producer PRO in deps_list L. */
-dep_link_t
-find_link_by_pro_in_deps_list (deps_list_t l, rtx pro)
+/* Return true if there is no dep_nodes and deps_lists out there.
+ After the region is scheduled all the dependency nodes and lists
+ should [generally] be returned to pool. */
+bool
+deps_pools_are_empty_p (void)
{
- dep_link_t link;
-
- FOR_EACH_DEP_LINK (link, l)
- if (DEP_LINK_PRO (link) == pro)
- return link;
-
- return NULL;
+ return dn_pool_diff == 0 && dl_pool_diff == 0;
}
-/* Find the dep_link with consumer CON in deps_list L. */
-dep_link_t
-find_link_by_con_in_deps_list (deps_list_t l, rtx con)
+/* Remove all elements from L. */
+static void
+clear_deps_list (deps_list_t l)
{
- dep_link_t link;
+ do
+ {
+ dep_link_t link = DEPS_LIST_FIRST (l);
- FOR_EACH_DEP_LINK (link, l)
- if (DEP_LINK_CON (link) == con)
- return link;
+ if (link == NULL)
+ break;
- return NULL;
+ remove_from_deps_list (link, l);
+ }
+ while (1);
}
-/* Make a copy of FROM in TO with substituting consumer with CON.
- TO and FROM should be RESOLVED_BACK_DEPS lists. */
-void
-copy_deps_list_change_con (deps_list_t to, deps_list_t from, rtx con)
+/* Decide whether a dependency should be treated as a hard or a speculative
+ dependency. */
+static bool
+dep_spec_p (dep_t dep)
{
- dep_link_t l;
-
- gcc_assert (deps_list_empty_p (to));
-
- FOR_EACH_DEP_LINK (l, from)
+ if (current_sched_info->flags & DO_SPECULATION)
{
- add_back_dep_to_deps_list (to, DEP_LINK_DEP (l));
- DEP_LINK_CON (DEPS_LIST_FIRST (to)) = con;
+ if (DEP_STATUS (dep) & SPECULATIVE)
+ return true;
+ }
+ if (current_sched_info->flags & DO_PREDICATION)
+ {
+ if (DEP_TYPE (dep) == REG_DEP_CONTROL)
+ return true;
}
+ return false;
}
static regset reg_pending_sets;
static regset reg_pending_clobbers;
static regset reg_pending_uses;
-
-/* The following enumeration values tell us what dependencies we
- should use to implement the barrier. We use true-dependencies for
- TRUE_BARRIER and anti-dependencies for MOVE_BARRIER. */
-enum reg_pending_barrier_mode
-{
- NOT_A_BARRIER = 0,
- MOVE_BARRIER,
- TRUE_BARRIER
-};
-
+static regset reg_pending_control_uses;
static enum reg_pending_barrier_mode reg_pending_barrier;
+/* Hard registers implicitly clobbered or used (or may be implicitly
+ clobbered or used) by the currently analyzed insn. For example,
+ insn in its constraint has one register class. Even if there is
+ currently no hard register in the insn, the particular hard
+ register will be in the insn after reload pass because the
+ constraint requires it. */
+static HARD_REG_SET implicit_reg_pending_clobbers;
+static HARD_REG_SET implicit_reg_pending_uses;
+
/* To speed up the test for duplicate dependency links we keep a
record of dependencies created by add_dependence when the average
number of instructions in a basic block is very large.
has enough entries to represent a dependency on any other insn in
the insn chain. All bitmap for true dependencies cache is
allocated then the rest two ones are also allocated. */
-static bitmap_head *true_dependency_cache;
-static bitmap_head *output_dependency_cache;
-static bitmap_head *anti_dependency_cache;
-static bitmap_head *spec_dependency_cache;
+static bitmap_head *true_dependency_cache = NULL;
+static bitmap_head *output_dependency_cache = NULL;
+static bitmap_head *anti_dependency_cache = NULL;
+static bitmap_head *control_dependency_cache = NULL;
+static bitmap_head *spec_dependency_cache = NULL;
static int cache_size;
-/* To speed up checking consistency of formed forward insn
- dependencies we use the following cache. Another possible solution
- could be switching off checking duplication of insns in forward
- dependencies. */
-#ifdef ENABLE_CHECKING
-static bitmap_head *forward_dependency_cache;
-#endif
-
-static int deps_may_trap_p (rtx);
+static int deps_may_trap_p (const_rtx);
+static void add_dependence_1 (rtx, rtx, enum reg_note);
static void add_dependence_list (rtx, rtx, int, enum reg_note);
-static void add_dependence_list_and_free (rtx, rtx *, int, enum reg_note);
+static void add_dependence_list_and_free (struct deps_desc *, rtx,
+ rtx *, int, enum reg_note);
static void delete_all_dependences (rtx);
static void fixup_sched_groups (rtx);
-static void flush_pending_lists (struct deps *, rtx, int, int);
-static void sched_analyze_1 (struct deps *, rtx, rtx);
-static void sched_analyze_2 (struct deps *, rtx, rtx);
-static void sched_analyze_insn (struct deps *, rtx, rtx);
+static void flush_pending_lists (struct deps_desc *, rtx, int, int);
+static void sched_analyze_1 (struct deps_desc *, rtx, rtx);
+static void sched_analyze_2 (struct deps_desc *, rtx, rtx);
+static void sched_analyze_insn (struct deps_desc *, rtx, rtx);
-static rtx sched_get_condition (rtx);
-static int conditions_mutex_p (rtx, rtx);
+static bool sched_has_condition_p (const_rtx);
+static int conditions_mutex_p (const_rtx, const_rtx, bool, bool);
-static enum DEPS_ADJUST_RESULT maybe_add_or_update_back_dep_1 (rtx, rtx,
- enum reg_note, ds_t, rtx, rtx, dep_link_t **);
-static enum DEPS_ADJUST_RESULT add_or_update_back_dep_1 (rtx, rtx,
- enum reg_note, ds_t, rtx, rtx, dep_link_t **);
-static void add_back_dep (rtx, rtx, enum reg_note, ds_t);
+static enum DEPS_ADJUST_RESULT maybe_add_or_update_dep_1 (dep_t, bool,
+ rtx, rtx);
+static enum DEPS_ADJUST_RESULT add_or_update_dep_1 (dep_t, bool, rtx, rtx);
-static void adjust_add_sorted_back_dep (rtx, dep_link_t, dep_link_t *);
-static void adjust_back_add_forw_dep (rtx, dep_link_t *);
-static void delete_forw_dep (dep_link_t);
-static dw_t estimate_dep_weak (rtx, rtx);
-#ifdef INSN_SCHEDULING
#ifdef ENABLE_CHECKING
-static void check_dep_status (enum reg_note, ds_t, bool);
-#endif
+static void check_dep (dep_t, bool);
#endif
\f
/* Return nonzero if a load of the memory reference MEM can cause a trap. */
static int
-deps_may_trap_p (rtx mem)
+deps_may_trap_p (const_rtx mem)
{
- rtx addr = XEXP (mem, 0);
+ const_rtx addr = XEXP (mem, 0);
if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER)
{
- rtx t = get_reg_known_value (REGNO (addr));
+ const_rtx t = get_reg_known_value (REGNO (addr));
if (t)
addr = t;
}
return rtx_addr_can_trap_p (addr);
}
\f
-/* Find the condition under which INSN is executed. */
+/* Find the condition under which INSN is executed. If REV is not NULL,
+ it is set to TRUE when the returned comparison should be reversed
+ to get the actual condition. */
static rtx
-sched_get_condition (rtx insn)
+sched_get_condition_with_rev_uncached (const_rtx insn, bool *rev)
{
rtx pat = PATTERN (insn);
rtx src;
- if (pat == 0)
- return 0;
+ if (rev)
+ *rev = false;
if (GET_CODE (pat) == COND_EXEC)
return COND_EXEC_TEST (pat);
if (revcode == UNKNOWN)
return 0;
- return gen_rtx_fmt_ee (revcode, GET_MODE (cond), XEXP (cond, 0),
- XEXP (cond, 1));
+
+ if (rev)
+ *rev = true;
+ return cond;
}
return 0;
}
+/* Return the condition under which INSN does not execute (i.e. the
+ not-taken condition for a conditional branch), or NULL if we cannot
+ 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)
+{
+ bool rev;
+ rtx cond = sched_get_condition_with_rev_uncached (insn, &rev);
+ if (cond == NULL_RTX)
+ return cond;
+ if (!rev)
+ {
+ enum rtx_code revcode = reversed_comparison_code (cond, insn);
+ cond = gen_rtx_fmt_ee (revcode, GET_MODE (cond),
+ XEXP (cond, 0),
+ XEXP (cond, 1));
+ }
+ return cond;
+}
+
+/* Caching variant of sched_get_condition_with_rev_uncached.
+ 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)
+{
+ bool tmp;
+
+ if (INSN_LUID (insn) == 0)
+ return sched_get_condition_with_rev_uncached (insn, rev);
+
+ if (INSN_CACHED_COND (insn) == const_true_rtx)
+ return NULL_RTX;
+
+ if (INSN_CACHED_COND (insn) != NULL_RTX)
+ {
+ if (rev)
+ *rev = INSN_REVERSE_COND (insn);
+ return INSN_CACHED_COND (insn);
+ }
+
+ INSN_CACHED_COND (insn) = sched_get_condition_with_rev_uncached (insn, &tmp);
+ INSN_REVERSE_COND (insn) = tmp;
+
+ if (INSN_CACHED_COND (insn) == NULL_RTX)
+ {
+ INSN_CACHED_COND (insn) = const_true_rtx;
+ return NULL_RTX;
+ }
+
+ if (rev)
+ *rev = INSN_REVERSE_COND (insn);
+ return INSN_CACHED_COND (insn);
+}
+
+/* True when we can find a condition under which INSN is executed. */
+static bool
+sched_has_condition_p (const_rtx insn)
+{
+ return !! sched_get_condition_with_rev (insn, NULL);
+}
+
\f
-/* Return nonzero if conditions COND1 and COND2 can never be both true. */
+/* Return nonzero if conditions COND1 and COND2 can never be both true. */
static int
-conditions_mutex_p (rtx cond1, rtx cond2)
+conditions_mutex_p (const_rtx cond1, const_rtx cond2, bool rev1, bool rev2)
{
if (COMPARISON_P (cond1)
&& COMPARISON_P (cond2)
- && GET_CODE (cond1) == reversed_comparison_code (cond2, NULL)
- && XEXP (cond1, 0) == XEXP (cond2, 0)
+ && GET_CODE (cond1) ==
+ (rev1==rev2
+ ? reversed_comparison_code (cond2, NULL)
+ : GET_CODE (cond2))
+ && rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
&& XEXP (cond1, 1) == XEXP (cond2, 1))
return 1;
return 0;
/* 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 (rtx insn1, rtx insn2)
+sched_insns_conditions_mutex_p (const_rtx insn1, const_rtx insn2)
{
rtx cond1, cond2;
+ bool rev1 = false, rev2 = false;
/* df doesn't handle conditional lifetimes entirely correctly;
calls mess up the conditional lifetimes. */
if (!CALL_P (insn1) && !CALL_P (insn2))
{
- cond1 = sched_get_condition (insn1);
- cond2 = sched_get_condition (insn2);
+ cond1 = sched_get_condition_with_rev (insn1, &rev1);
+ cond2 = sched_get_condition_with_rev (insn2, &rev2);
if (cond1 && cond2
- && conditions_mutex_p (cond1, cond2)
+ && conditions_mutex_p (cond1, cond2, rev1, rev2)
/* Make sure first instruction doesn't affect condition of second
instruction if switched. */
&& !modified_in_p (cond1, insn2)
return false;
}
\f
-/* Add ELEM wrapped in an dep_link with reg note kind DEP_TYPE to the
- INSN_BACK_DEPS (INSN), if it is not already there. DEP_TYPE indicates the
- type of dependence that this link represents. DS, if nonzero,
- indicates speculations, through which this dependence can be overcome.
- MEM1 and MEM2, if non-null, corresponds to memory locations in case of
- data speculation. The function returns a value indicating if an old entry
- has been changed or a new entry has been added to insn's backward deps.
- In case of changed entry CHANGED_LINKPP sets to its address.
- See also the definition of enum DEPS_ADJUST_RESULT in sched-int.h.
- Actual manipulation of dependence data structures is performed in
- add_or_update_back_dep_1. */
-static enum DEPS_ADJUST_RESULT
-maybe_add_or_update_back_dep_1 (rtx insn, rtx elem, enum reg_note dep_type,
- ds_t ds, rtx mem1, rtx mem2,
- dep_link_t **changed_linkpp)
+/* 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)
{
- gcc_assert (INSN_P (insn) && INSN_P (elem));
+ if (HAS_INTERNAL_DEP (insn))
+ return false;
- /* Don't depend an insn on itself. */
- if (insn == elem)
+ if (!NONJUMP_INSN_P (insn))
+ return false;
+
+ if (SCHED_GROUP_P (insn))
+ return false;
+
+ if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX (insn)))
+ return false;
+
+ if (side_effects_p (PATTERN (insn)))
+ return false;
+
+ if (ds & BE_IN_SPEC)
+ /* The following instructions, which depend on a speculatively scheduled
+ instruction, cannot be speculatively scheduled along. */
{
-#ifdef INSN_SCHEDULING
- if (current_sched_info->flags & DO_SPECULATION)
- /* INSN has an internal dependence, which we can't overcome. */
- HAS_INTERNAL_DEP (insn) = 1;
-#endif
- return 0;
+ if (may_trap_or_fault_p (PATTERN (insn)))
+ /* If instruction might fault, it cannot be speculatively scheduled.
+ For control speculation it's obvious why and for data speculation
+ it's because the insn might get wrong input if speculation
+ wasn't successful. */
+ return false;
+
+ if ((ds & BE_IN_DATA)
+ && sched_has_condition_p (insn))
+ /* If this is a predicated instruction, then it cannot be
+ speculatively scheduled. See PR35659. */
+ return false;
}
- return add_or_update_back_dep_1 (insn, elem, dep_type,
- ds, mem1, mem2, changed_linkpp);
+ return true;
}
-/* This function has the same meaning of parameters and return values
- as maybe_add_or_update_back_dep_1. The only difference between these
- two functions is that INSN and ELEM are guaranteed not to be the same
- in this one. */
-static enum DEPS_ADJUST_RESULT
-add_or_update_back_dep_1 (rtx insn, rtx elem, enum reg_note dep_type,
- ds_t ds ATTRIBUTE_UNUSED,
- rtx mem1 ATTRIBUTE_UNUSED, rtx mem2 ATTRIBUTE_UNUSED,
- dep_link_t **changed_linkpp ATTRIBUTE_UNUSED)
+/* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR,
+ initialize RESOLVED_P_PTR with true if that list consists of resolved deps,
+ and remove the type of returned [through LIST_PTR] list from TYPES_PTR.
+ This function is used to switch sd_iterator to the next list.
+ !!! For internal use only. Might consider moving it to sched-int.h. */
+void
+sd_next_list (const_rtx insn, sd_list_types_def *types_ptr,
+ deps_list_t *list_ptr, bool *resolved_p_ptr)
{
- bool maybe_present_p = true, present_p = false;
+ sd_list_types_def types = *types_ptr;
- gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
-
-#ifdef INSN_SCHEDULING
+ if (types & SD_LIST_HARD_BACK)
+ {
+ *list_ptr = INSN_HARD_BACK_DEPS (insn);
+ *resolved_p_ptr = false;
+ *types_ptr = types & ~SD_LIST_HARD_BACK;
+ }
+ else if (types & SD_LIST_SPEC_BACK)
+ {
+ *list_ptr = INSN_SPEC_BACK_DEPS (insn);
+ *resolved_p_ptr = false;
+ *types_ptr = types & ~SD_LIST_SPEC_BACK;
+ }
+ else if (types & SD_LIST_FORW)
+ {
+ *list_ptr = INSN_FORW_DEPS (insn);
+ *resolved_p_ptr = false;
+ *types_ptr = types & ~SD_LIST_FORW;
+ }
+ else if (types & SD_LIST_RES_BACK)
+ {
+ *list_ptr = INSN_RESOLVED_BACK_DEPS (insn);
+ *resolved_p_ptr = true;
+ *types_ptr = types & ~SD_LIST_RES_BACK;
+ }
+ else if (types & SD_LIST_RES_FORW)
+ {
+ *list_ptr = INSN_RESOLVED_FORW_DEPS (insn);
+ *resolved_p_ptr = true;
+ *types_ptr = types & ~SD_LIST_RES_FORW;
+ }
+ else
+ {
+ *list_ptr = NULL;
+ *resolved_p_ptr = false;
+ *types_ptr = SD_LIST_NONE;
+ }
+}
-#ifdef ENABLE_CHECKING
- check_dep_status (dep_type, ds, mem1 != NULL);
-#endif
+/* Return the summary size of INSN's lists defined by LIST_TYPES. */
+int
+sd_lists_size (const_rtx insn, sd_list_types_def list_types)
+{
+ int size = 0;
- /* If we already have a dependency for ELEM, then we do not need to
- do anything. Avoiding the list walk below can cut compile times
- dramatically for some code. */
- if (true_dependency_cache != NULL)
+ while (list_types != SD_LIST_NONE)
{
- enum reg_note present_dep_type;
-
- gcc_assert (output_dependency_cache);
- gcc_assert (anti_dependency_cache);
- if (!(current_sched_info->flags & USE_DEPS_LIST))
- {
- if (bitmap_bit_p (&true_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem)))
- present_dep_type = REG_DEP_TRUE;
- else if (bitmap_bit_p (&output_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem)))
- present_dep_type = REG_DEP_OUTPUT;
- else if (bitmap_bit_p (&anti_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem)))
- present_dep_type = REG_DEP_ANTI;
- else
- maybe_present_p = false;
+ deps_list_t list;
+ bool resolved_p;
- if (maybe_present_p)
- {
- if ((int) dep_type >= (int) present_dep_type)
- return DEP_PRESENT;
-
- present_p = true;
- }
- }
- else
- {
- ds_t present_dep_types = 0;
-
- if (bitmap_bit_p (&true_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem)))
- present_dep_types |= DEP_TRUE;
- if (bitmap_bit_p (&output_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem)))
- present_dep_types |= DEP_OUTPUT;
- if (bitmap_bit_p (&anti_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem)))
- present_dep_types |= DEP_ANTI;
-
- if (present_dep_types)
- {
- if (!(current_sched_info->flags & DO_SPECULATION)
- || !bitmap_bit_p (&spec_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem)))
- {
- if ((present_dep_types | (ds & DEP_TYPES))
- == present_dep_types)
- /* We already have all these bits. */
- return DEP_PRESENT;
- }
- else
- {
- /* Only true dependencies can be data speculative and
- only anti dependencies can be control speculative. */
- gcc_assert ((present_dep_types & (DEP_TRUE | DEP_ANTI))
- == present_dep_types);
-
- /* if (additional dep is SPECULATIVE) then
- we should update DEP_STATUS
- else
- we should reset existing dep to non-speculative. */
- }
-
- present_p = true;
- }
- else
- maybe_present_p = false;
- }
+ sd_next_list (insn, &list_types, &list, &resolved_p);
+ if (list)
+ size += DEPS_LIST_N_LINKS (list);
}
-#endif
- /* Check that we don't already have this dependence. */
- if (maybe_present_p)
- {
- dep_link_t *linkp;
+ return size;
+}
- for (linkp = &DEPS_LIST_FIRST (INSN_BACK_DEPS (insn));
- *linkp != NULL;
- linkp = &DEP_LINK_NEXT (*linkp))
- {
- dep_t link = DEP_LINK_DEP (*linkp);
+/* Return true if INSN's lists defined by LIST_TYPES are all empty. */
- gcc_assert (true_dependency_cache == 0 || present_p);
-
- if (DEP_PRO (link) == elem)
- {
- enum DEPS_ADJUST_RESULT changed_p = DEP_PRESENT;
+bool
+sd_lists_empty_p (const_rtx insn, sd_list_types_def list_types)
+{
+ while (list_types != SD_LIST_NONE)
+ {
+ deps_list_t list;
+ bool resolved_p;
-#ifdef INSN_SCHEDULING
- if (current_sched_info->flags & USE_DEPS_LIST)
- {
- ds_t new_status = ds | DEP_STATUS (link);
+ sd_next_list (insn, &list_types, &list, &resolved_p);
+ if (!deps_list_empty_p (list))
+ return false;
+ }
+
+ return true;
+}
+
+/* Initialize data for INSN. */
+void
+sd_init_insn (rtx insn)
+{
+ INSN_HARD_BACK_DEPS (insn) = create_deps_list ();
+ INSN_SPEC_BACK_DEPS (insn) = create_deps_list ();
+ INSN_RESOLVED_BACK_DEPS (insn) = create_deps_list ();
+ INSN_FORW_DEPS (insn) = create_deps_list ();
+ INSN_RESOLVED_FORW_DEPS (insn) = create_deps_list ();
+
+ /* ??? It would be nice to allocate dependency caches here. */
+}
+
+/* Free data for INSN. */
+void
+sd_finish_insn (rtx insn)
+{
+ /* ??? It would be nice to deallocate dependency caches here. */
+
+ free_deps_list (INSN_HARD_BACK_DEPS (insn));
+ INSN_HARD_BACK_DEPS (insn) = NULL;
+
+ free_deps_list (INSN_SPEC_BACK_DEPS (insn));
+ INSN_SPEC_BACK_DEPS (insn) = NULL;
+
+ free_deps_list (INSN_RESOLVED_BACK_DEPS (insn));
+ INSN_RESOLVED_BACK_DEPS (insn) = NULL;
+
+ free_deps_list (INSN_FORW_DEPS (insn));
+ INSN_FORW_DEPS (insn) = NULL;
+
+ free_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
+ INSN_RESOLVED_FORW_DEPS (insn) = NULL;
+}
+
+/* Find a dependency between producer PRO and consumer CON.
+ Search through resolved dependency lists if RESOLVED_P is true.
+ If no such dependency is found return NULL,
+ otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull]
+ with an iterator pointing to it. */
+static dep_t
+sd_find_dep_between_no_cache (rtx pro, rtx con, bool resolved_p,
+ sd_iterator_def *sd_it_ptr)
+{
+ sd_list_types_def pro_list_type;
+ sd_list_types_def con_list_type;
+ sd_iterator_def sd_it;
+ dep_t dep;
+ bool found_p = false;
+
+ if (resolved_p)
+ {
+ pro_list_type = SD_LIST_RES_FORW;
+ con_list_type = SD_LIST_RES_BACK;
+ }
+ else
+ {
+ pro_list_type = SD_LIST_FORW;
+ con_list_type = SD_LIST_BACK;
+ }
+
+ /* Walk through either back list of INSN or forw list of ELEM
+ depending on which one is shorter. */
+ if (sd_lists_size (con, con_list_type) < sd_lists_size (pro, pro_list_type))
+ {
+ /* Find the dep_link with producer PRO in consumer's back_deps. */
+ FOR_EACH_DEP (con, con_list_type, sd_it, dep)
+ if (DEP_PRO (dep) == pro)
+ {
+ found_p = true;
+ break;
+ }
+ }
+ else
+ {
+ /* Find the dep_link with consumer CON in producer's forw_deps. */
+ FOR_EACH_DEP (pro, pro_list_type, sd_it, dep)
+ if (DEP_CON (dep) == con)
+ {
+ found_p = true;
+ break;
+ }
+ }
+
+ if (found_p)
+ {
+ if (sd_it_ptr != NULL)
+ *sd_it_ptr = sd_it;
+
+ return dep;
+ }
+
+ return NULL;
+}
+
+/* Find a dependency between producer PRO and consumer CON.
+ Use dependency [if available] to check if dependency is present at all.
+ Search through resolved dependency lists if RESOLVED_P is true.
+ If the dependency or NULL if none found. */
+dep_t
+sd_find_dep_between (rtx pro, rtx con, bool resolved_p)
+{
+ if (true_dependency_cache != NULL)
+ /* Avoiding the list walk below can cut compile times dramatically
+ for some code. */
+ {
+ int elem_luid = INSN_LUID (pro);
+ int insn_luid = INSN_LUID (con);
+
+ if (!bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid)
+ && !bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid)
+ && !bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid)
+ && !bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
+ return NULL;
+ }
+
+ return sd_find_dep_between_no_cache (pro, con, resolved_p, NULL);
+}
+
+/* Add or update a dependence described by DEP.
+ MEM1 and MEM2, if non-null, correspond to memory locations in case of
+ data speculation.
+
+ The function returns a value indicating if an old entry has been changed
+ or a new entry has been added to insn's backward deps.
+
+ This function merely checks if producer and consumer is the same insn
+ and doesn't create a dep in this case. Actual manipulation of
+ dependence data structures is performed in add_or_update_dep_1. */
+static enum DEPS_ADJUST_RESULT
+maybe_add_or_update_dep_1 (dep_t dep, bool resolved_p, rtx mem1, rtx mem2)
+{
+ rtx elem = DEP_PRO (dep);
+ rtx insn = DEP_CON (dep);
+
+ gcc_assert (INSN_P (insn) && INSN_P (elem));
+
+ /* Don't depend an insn on itself. */
+ if (insn == elem)
+ {
+ if (sched_deps_info->generate_spec_deps)
+ /* INSN has an internal dependence, which we can't overcome. */
+ HAS_INTERNAL_DEP (insn) = 1;
+
+ return DEP_NODEP;
+ }
+
+ return add_or_update_dep_1 (dep, resolved_p, mem1, mem2);
+}
+
+/* Ask dependency caches what needs to be done for dependence DEP.
+ Return DEP_CREATED if new dependence should be created and there is no
+ need to try to find one searching the dependencies lists.
+ Return DEP_PRESENT if there already is a dependence described by DEP and
+ hence nothing is to be done.
+ Return DEP_CHANGED if there already is a dependence, but it should be
+ updated to incorporate additional information from DEP. */
+static enum DEPS_ADJUST_RESULT
+ask_dependency_caches (dep_t dep)
+{
+ int elem_luid = INSN_LUID (DEP_PRO (dep));
+ int insn_luid = INSN_LUID (DEP_CON (dep));
+
+ gcc_assert (true_dependency_cache != NULL
+ && output_dependency_cache != NULL
+ && anti_dependency_cache != NULL
+ && control_dependency_cache != NULL);
+
+ if (!(current_sched_info->flags & USE_DEPS_LIST))
+ {
+ enum reg_note present_dep_type;
+
+ if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
+ present_dep_type = REG_DEP_TRUE;
+ else if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
+ present_dep_type = REG_DEP_OUTPUT;
+ else if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
+ present_dep_type = REG_DEP_ANTI;
+ else if (bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
+ present_dep_type = REG_DEP_CONTROL;
+ else
+ /* There is no existing dep so it should be created. */
+ return DEP_CREATED;
+
+ if ((int) DEP_TYPE (dep) >= (int) present_dep_type)
+ /* DEP does not add anything to the existing dependence. */
+ return DEP_PRESENT;
+ }
+ else
+ {
+ ds_t present_dep_types = 0;
+
+ if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid))
+ present_dep_types |= DEP_TRUE;
+ if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid))
+ present_dep_types |= DEP_OUTPUT;
+ if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
+ present_dep_types |= DEP_ANTI;
+ if (bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
+ present_dep_types |= DEP_CONTROL;
+
+ if (present_dep_types == 0)
+ /* There is no existing dep so it should be created. */
+ return DEP_CREATED;
+
+ if (!(current_sched_info->flags & DO_SPECULATION)
+ || !bitmap_bit_p (&spec_dependency_cache[insn_luid], elem_luid))
+ {
+ if ((present_dep_types | (DEP_STATUS (dep) & DEP_TYPES))
+ == present_dep_types)
+ /* DEP does not add anything to the existing dependence. */
+ return DEP_PRESENT;
+ }
+ else
+ {
+ /* Only true dependencies can be data speculative and
+ only anti dependencies can be control speculative. */
+ gcc_assert ((present_dep_types & (DEP_TRUE | DEP_ANTI))
+ == present_dep_types);
+
+ /* if (DEP is SPECULATIVE) then
+ ..we should update DEP_STATUS
+ else
+ ..we should reset existing dep to non-speculative. */
+ }
+ }
+
+ return DEP_CHANGED;
+}
+
+/* Set dependency caches according to DEP. */
+static void
+set_dependency_caches (dep_t dep)
+{
+ int elem_luid = INSN_LUID (DEP_PRO (dep));
+ int insn_luid = INSN_LUID (DEP_CON (dep));
+
+ if (!(current_sched_info->flags & USE_DEPS_LIST))
+ {
+ switch (DEP_TYPE (dep))
+ {
+ case REG_DEP_TRUE:
+ bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
+ break;
+
+ case REG_DEP_OUTPUT:
+ bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
+ break;
+
+ case REG_DEP_ANTI:
+ bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
+ break;
+
+ case REG_DEP_CONTROL:
+ bitmap_set_bit (&control_dependency_cache[insn_luid], elem_luid);
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+ }
+ else
+ {
+ ds_t ds = DEP_STATUS (dep);
+
+ if (ds & DEP_TRUE)
+ bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid);
+ if (ds & DEP_OUTPUT)
+ bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
+ if (ds & DEP_ANTI)
+ bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
+ if (ds & DEP_CONTROL)
+ bitmap_set_bit (&control_dependency_cache[insn_luid], elem_luid);
+
+ if (ds & SPECULATIVE)
+ {
+ gcc_assert (current_sched_info->flags & DO_SPECULATION);
+ bitmap_set_bit (&spec_dependency_cache[insn_luid], elem_luid);
+ }
+ }
+}
+
+/* Type of dependence DEP have changed from OLD_TYPE. Update dependency
+ caches accordingly. */
+static void
+update_dependency_caches (dep_t dep, enum reg_note old_type)
+{
+ int elem_luid = INSN_LUID (DEP_PRO (dep));
+ int insn_luid = INSN_LUID (DEP_CON (dep));
+
+ /* Clear corresponding cache entry because type of the link
+ may have changed. Keep them if we use_deps_list. */
+ if (!(current_sched_info->flags & USE_DEPS_LIST))
+ {
+ switch (old_type)
+ {
+ case REG_DEP_OUTPUT:
+ bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
+ break;
+
+ case REG_DEP_ANTI:
+ bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
+ break;
+
+ case REG_DEP_CONTROL:
+ bitmap_clear_bit (&control_dependency_cache[insn_luid], elem_luid);
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+ }
+
+ set_dependency_caches (dep);
+}
+
+/* Convert a dependence pointed to by SD_IT to be non-speculative. */
+static void
+change_spec_dep_to_hard (sd_iterator_def sd_it)
+{
+ dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
+ dep_link_t link = DEP_NODE_BACK (node);
+ dep_t dep = DEP_NODE_DEP (node);
+ rtx elem = DEP_PRO (dep);
+ rtx insn = DEP_CON (dep);
+
+ move_dep_link (link, INSN_SPEC_BACK_DEPS (insn), INSN_HARD_BACK_DEPS (insn));
+
+ DEP_STATUS (dep) &= ~SPECULATIVE;
+
+ if (true_dependency_cache != NULL)
+ /* Clear the cache entry. */
+ bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
+ INSN_LUID (elem));
+}
+
+/* Update DEP to incorporate information from NEW_DEP.
+ SD_IT points to DEP in case it should be moved to another list.
+ MEM1 and MEM2, if nonnull, correspond to memory locations in case if
+ data-speculative dependence should be updated. */
+static enum DEPS_ADJUST_RESULT
+update_dep (dep_t dep, dep_t new_dep,
+ sd_iterator_def sd_it ATTRIBUTE_UNUSED,
+ rtx mem1 ATTRIBUTE_UNUSED,
+ rtx mem2 ATTRIBUTE_UNUSED)
+{
+ enum DEPS_ADJUST_RESULT res = DEP_PRESENT;
+ enum reg_note old_type = DEP_TYPE (dep);
+ bool was_spec = dep_spec_p (dep);
+
+ /* If this is a more restrictive type of dependence than the
+ existing one, then change the existing dependence to this
+ type. */
+ if ((int) DEP_TYPE (new_dep) < (int) old_type)
+ {
+ DEP_TYPE (dep) = DEP_TYPE (new_dep);
+ res = DEP_CHANGED;
+ }
+
+ if (current_sched_info->flags & USE_DEPS_LIST)
+ /* Update DEP_STATUS. */
+ {
+ ds_t dep_status = DEP_STATUS (dep);
+ ds_t ds = DEP_STATUS (new_dep);
+ ds_t new_status = ds | dep_status;
+
+ if (new_status & SPECULATIVE)
+ {
+ /* Either existing dep or a dep we're adding or both are
+ speculative. */
+ if (!(ds & SPECULATIVE)
+ || !(dep_status & SPECULATIVE))
+ /* The new dep can't be speculative. */
+ new_status &= ~SPECULATIVE;
+ else
+ {
+ /* Both are speculative. Merge probabilities. */
+ if (mem1 != NULL)
+ {
+ dw_t dw;
+
+ dw = estimate_dep_weak (mem1, mem2);
+ ds = set_dep_weak (ds, BEGIN_DATA, dw);
+ }
+
+ new_status = ds_merge (dep_status, ds);
+ }
+ }
+
+ ds = new_status;
+
+ if (dep_status != ds)
+ {
+ DEP_STATUS (dep) = ds;
+ res = DEP_CHANGED;
+ }
+ }
+
+ if (was_spec && !dep_spec_p (dep))
+ /* The old dep was speculative, but now it isn't. */
+ change_spec_dep_to_hard (sd_it);
+
+ if (true_dependency_cache != NULL
+ && res == DEP_CHANGED)
+ update_dependency_caches (dep, old_type);
+
+ return res;
+}
+
+/* Add or update a dependence described by DEP.
+ MEM1 and MEM2, if non-null, correspond to memory locations in case of
+ data speculation.
+
+ The function returns a value indicating if an old entry has been changed
+ or a new entry has been added to insn's backward deps or nothing has
+ been updated at all. */
+static enum DEPS_ADJUST_RESULT
+add_or_update_dep_1 (dep_t new_dep, bool resolved_p,
+ rtx mem1 ATTRIBUTE_UNUSED, rtx mem2 ATTRIBUTE_UNUSED)
+{
+ bool maybe_present_p = true;
+ bool present_p = false;
+
+ gcc_assert (INSN_P (DEP_PRO (new_dep)) && INSN_P (DEP_CON (new_dep))
+ && DEP_PRO (new_dep) != DEP_CON (new_dep));
+
+#ifdef ENABLE_CHECKING
+ check_dep (new_dep, mem1 != NULL);
+#endif
+
+ if (true_dependency_cache != NULL)
+ {
+ switch (ask_dependency_caches (new_dep))
+ {
+ case DEP_PRESENT:
+ return DEP_PRESENT;
+
+ case DEP_CHANGED:
+ maybe_present_p = true;
+ present_p = true;
+ break;
+
+ case DEP_CREATED:
+ maybe_present_p = false;
+ present_p = false;
+ break;
+
+ default:
+ gcc_unreachable ();
+ break;
+ }
+ }
+
+ /* Check that we don't already have this dependence. */
+ if (maybe_present_p)
+ {
+ dep_t present_dep;
+ sd_iterator_def sd_it;
+
+ gcc_assert (true_dependency_cache == NULL || present_p);
+
+ present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep),
+ DEP_CON (new_dep),
+ resolved_p, &sd_it);
+
+ if (present_dep != NULL)
+ /* We found an existing dependency between ELEM and INSN. */
+ return update_dep (present_dep, new_dep, sd_it, mem1, mem2);
+ else
+ /* We didn't find a dep, it shouldn't present in the cache. */
+ gcc_assert (!present_p);
+ }
+
+ /* Might want to check one level of transitivity to save conses.
+ This check should be done in maybe_add_or_update_dep_1.
+ Since we made it to add_or_update_dep_1, we must create
+ (or update) a link. */
+
+ if (mem1 != NULL_RTX)
+ {
+ gcc_assert (sched_deps_info->generate_spec_deps);
+ DEP_STATUS (new_dep) = set_dep_weak (DEP_STATUS (new_dep), BEGIN_DATA,
+ estimate_dep_weak (mem1, mem2));
+ }
+
+ sd_add_dep (new_dep, resolved_p);
+
+ return DEP_CREATED;
+}
+
+/* Initialize BACK_LIST_PTR with consumer's backward list and
+ FORW_LIST_PTR with producer's forward list. If RESOLVED_P is true
+ initialize with lists that hold resolved deps. */
+static void
+get_back_and_forw_lists (dep_t dep, bool resolved_p,
+ deps_list_t *back_list_ptr,
+ deps_list_t *forw_list_ptr)
+{
+ rtx con = DEP_CON (dep);
+
+ if (!resolved_p)
+ {
+ if (dep_spec_p (dep))
+ *back_list_ptr = INSN_SPEC_BACK_DEPS (con);
+ else
+ *back_list_ptr = INSN_HARD_BACK_DEPS (con);
+
+ *forw_list_ptr = INSN_FORW_DEPS (DEP_PRO (dep));
+ }
+ else
+ {
+ *back_list_ptr = INSN_RESOLVED_BACK_DEPS (con);
+ *forw_list_ptr = INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep));
+ }
+}
+
+/* Add dependence described by DEP.
+ If RESOLVED_P is true treat the dependence as a resolved one. */
+void
+sd_add_dep (dep_t dep, bool resolved_p)
+{
+ dep_node_t n = create_dep_node ();
+ deps_list_t con_back_deps;
+ deps_list_t pro_forw_deps;
+ rtx elem = DEP_PRO (dep);
+ rtx insn = DEP_CON (dep);
+
+ gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
+
+ if ((current_sched_info->flags & DO_SPECULATION) == 0
+ || !sched_insn_is_legitimate_for_speculation_p (insn, DEP_STATUS (dep)))
+ DEP_STATUS (dep) &= ~SPECULATIVE;
+
+ copy_dep (DEP_NODE_DEP (n), dep);
+
+ get_back_and_forw_lists (dep, resolved_p, &con_back_deps, &pro_forw_deps);
+
+ add_to_deps_list (DEP_NODE_BACK (n), con_back_deps);
+
+#ifdef ENABLE_CHECKING
+ check_dep (dep, false);
+#endif
+
+ add_to_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
+
+ /* If we are adding a dependency to INSN's LOG_LINKs, then note that
+ in the bitmap caches of dependency information. */
+ if (true_dependency_cache != NULL)
+ set_dependency_caches (dep);
+}
+
+/* Add or update backward dependence between INSN and ELEM
+ with given type DEP_TYPE and dep_status DS.
+ This function is a convenience wrapper. */
+enum DEPS_ADJUST_RESULT
+sd_add_or_update_dep (dep_t dep, bool resolved_p)
+{
+ return add_or_update_dep_1 (dep, resolved_p, NULL_RTX, NULL_RTX);
+}
+
+/* Resolved dependence pointed to by SD_IT.
+ SD_IT will advance to the next element. */
+void
+sd_resolve_dep (sd_iterator_def sd_it)
+{
+ dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
+ dep_t dep = DEP_NODE_DEP (node);
+ rtx pro = DEP_PRO (dep);
+ rtx con = DEP_CON (dep);
+
+ if (dep_spec_p (dep))
+ move_dep_link (DEP_NODE_BACK (node), INSN_SPEC_BACK_DEPS (con),
+ INSN_RESOLVED_BACK_DEPS (con));
+ else
+ move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con),
+ INSN_RESOLVED_BACK_DEPS (con));
+
+ move_dep_link (DEP_NODE_FORW (node), INSN_FORW_DEPS (pro),
+ INSN_RESOLVED_FORW_DEPS (pro));
+}
+
+/* Perform the inverse operation of sd_resolve_dep. Restore the dependence
+ pointed to by SD_IT to unresolved state. */
+void
+sd_unresolve_dep (sd_iterator_def sd_it)
+{
+ dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
+ dep_t dep = DEP_NODE_DEP (node);
+ rtx pro = DEP_PRO (dep);
+ rtx con = DEP_CON (dep);
+
+ if (dep_spec_p (dep))
+ move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con),
+ INSN_SPEC_BACK_DEPS (con));
+ else
+ move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con),
+ INSN_HARD_BACK_DEPS (con));
+
+ move_dep_link (DEP_NODE_FORW (node), INSN_RESOLVED_FORW_DEPS (pro),
+ INSN_FORW_DEPS (pro));
+}
+
+/* Make TO depend on all the FROM's producers.
+ If RESOLVED_P is true add dependencies to the resolved lists. */
+void
+sd_copy_back_deps (rtx to, rtx from, bool resolved_p)
+{
+ sd_list_types_def list_type;
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ list_type = resolved_p ? SD_LIST_RES_BACK : SD_LIST_BACK;
+
+ FOR_EACH_DEP (from, list_type, sd_it, dep)
+ {
+ dep_def _new_dep, *new_dep = &_new_dep;
+
+ copy_dep (new_dep, dep);
+ DEP_CON (new_dep) = to;
+ sd_add_dep (new_dep, resolved_p);
+ }
+}
+
+/* Remove a dependency referred to by SD_IT.
+ SD_IT will point to the next dependence after removal. */
+void
+sd_delete_dep (sd_iterator_def sd_it)
+{
+ dep_node_t n = DEP_LINK_NODE (*sd_it.linkp);
+ dep_t dep = DEP_NODE_DEP (n);
+ rtx pro = DEP_PRO (dep);
+ rtx con = DEP_CON (dep);
+ deps_list_t con_back_deps;
+ deps_list_t pro_forw_deps;
+
+ if (true_dependency_cache != NULL)
+ {
+ int elem_luid = INSN_LUID (pro);
+ int insn_luid = INSN_LUID (con);
+
+ bitmap_clear_bit (&true_dependency_cache[insn_luid], elem_luid);
+ bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
+ bitmap_clear_bit (&control_dependency_cache[insn_luid], elem_luid);
+ bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
+
+ if (current_sched_info->flags & DO_SPECULATION)
+ bitmap_clear_bit (&spec_dependency_cache[insn_luid], elem_luid);
+ }
+
+ get_back_and_forw_lists (dep, sd_it.resolved_p,
+ &con_back_deps, &pro_forw_deps);
+
+ remove_from_deps_list (DEP_NODE_BACK (n), con_back_deps);
+ remove_from_deps_list (DEP_NODE_FORW (n), pro_forw_deps);
+
+ delete_dep_node (n);
+}
+
+/* Dump size of the lists. */
+#define DUMP_LISTS_SIZE (2)
+
+/* Dump dependencies of the lists. */
+#define DUMP_LISTS_DEPS (4)
+
+/* Dump all information about the lists. */
+#define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS)
+
+/* Dump deps_lists of INSN specified by TYPES to DUMP.
+ FLAGS is a bit mask specifying what information about the lists needs
+ to be printed.
+ If FLAGS has the very first bit set, then dump all information about
+ the lists and propagate this bit into the callee dump functions. */
+static void
+dump_lists (FILE *dump, rtx insn, sd_list_types_def types, int flags)
+{
+ sd_iterator_def sd_it;
+ dep_t dep;
+ int all;
+
+ all = (flags & 1);
- if (new_status & SPECULATIVE)
- {
- if (!(ds & SPECULATIVE)
- || !(DEP_STATUS (link) & SPECULATIVE))
- /* Then this dep can't be speculative. */
- {
- new_status &= ~SPECULATIVE;
- if (true_dependency_cache
- && (DEP_STATUS (link) & SPECULATIVE))
- bitmap_clear_bit (&spec_dependency_cache
- [INSN_LUID (insn)],
- INSN_LUID (elem));
- }
- else
- {
- /* Both are speculative. Merging probabilities. */
- if (mem1)
- {
- dw_t dw;
-
- dw = estimate_dep_weak (mem1, mem2);
- ds = set_dep_weak (ds, BEGIN_DATA, dw);
- }
-
- new_status = ds_merge (DEP_STATUS (link), ds);
- }
- }
+ if (all)
+ flags |= DUMP_LISTS_ALL;
+
+ fprintf (dump, "[");
+
+ if (flags & DUMP_LISTS_SIZE)
+ fprintf (dump, "%d; ", sd_lists_size (insn, types));
+
+ if (flags & DUMP_LISTS_DEPS)
+ {
+ FOR_EACH_DEP (insn, types, sd_it, dep)
+ {
+ dump_dep (dump, dep, dump_dep_flags | all);
+ fprintf (dump, " ");
+ }
+ }
+}
+
+/* Dump all information about deps_lists of INSN specified by TYPES
+ to STDERR. */
+void
+sd_debug_lists (rtx insn, sd_list_types_def types)
+{
+ dump_lists (stderr, insn, types, 1);
+ fprintf (stderr, "\n");
+}
+
+/* A wrapper around add_dependence_1, to add a dependence of CON on
+ PRO, with type DEP_TYPE. This function implements special handling
+ for REG_DEP_CONTROL dependencies. For these, we optionally promote
+ the type to REG_DEP_ANTI if we can determine that predication is
+ impossible; otherwise we add additional true dependencies on the
+ INSN_COND_DEPS list of the jump (which PRO must be). */
+void
+add_dependence (rtx con, rtx pro, enum reg_note dep_type)
+{
+ if (dep_type == REG_DEP_CONTROL
+ && !(current_sched_info->flags & DO_PREDICATION))
+ dep_type = REG_DEP_ANTI;
+
+ /* A REG_DEP_CONTROL dependence may be eliminated through predication,
+ so we must also make the insn dependent on the setter of the
+ condition. */
+ if (dep_type == REG_DEP_CONTROL)
+ {
+ rtx real_pro = pro;
+ rtx other = real_insn_for_shadow (real_pro);
+ rtx cond;
+
+ if (other != NULL_RTX)
+ real_pro = other;
+ cond = sched_get_reverse_condition_uncached (real_pro);
+ /* Verify that the insn does not use a different value in
+ the condition register than the one that was present at
+ the jump. */
+ if (cond == NULL_RTX)
+ dep_type = REG_DEP_ANTI;
+ else if (INSN_CACHED_COND (real_pro) == const_true_rtx)
+ {
+ HARD_REG_SET uses;
+ CLEAR_HARD_REG_SET (uses);
+ note_uses (&PATTERN (con), record_hard_reg_uses, &uses);
+ if (TEST_HARD_REG_BIT (uses, REGNO (XEXP (cond, 0))))
+ dep_type = REG_DEP_ANTI;
+ }
+ if (dep_type == REG_DEP_CONTROL)
+ {
+ if (sched_verbose >= 5)
+ fprintf (sched_dump, "making DEP_CONTROL for %d\n",
+ INSN_UID (real_pro));
+ add_dependence_list (con, INSN_COND_DEPS (real_pro), 0,
+ REG_DEP_TRUE);
+ }
+ }
+
+ add_dependence_1 (con, pro, dep_type);
+}
+
+/* A convenience wrapper to operate on an entire list. */
+
+static void
+add_dependence_list (rtx insn, rtx list, int uncond, enum reg_note dep_type)
+{
+ for (; list; list = XEXP (list, 1))
+ {
+ if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
+ add_dependence (insn, XEXP (list, 0), dep_type);
+ }
+}
+
+/* Similar, but free *LISTP at the same time, when the context
+ is not readonly. */
+
+static void
+add_dependence_list_and_free (struct deps_desc *deps, rtx insn, rtx *listp,
+ int uncond, enum reg_note dep_type)
+{
+ rtx list, next;
+
+ /* We don't want to short-circuit dependencies involving debug
+ insns, because they may cause actual dependencies to be
+ disregarded. */
+ if (deps->readonly || DEBUG_INSN_P (insn))
+ {
+ add_dependence_list (insn, *listp, uncond, dep_type);
+ return;
+ }
+
+ for (list = *listp, *listp = NULL; list ; list = next)
+ {
+ next = XEXP (list, 1);
+ if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
+ add_dependence (insn, XEXP (list, 0), dep_type);
+ free_INSN_LIST_node (list);
+ }
+}
+
+/* Remove all occurences of INSN from LIST. Return the number of
+ occurences removed. */
+
+static int
+remove_from_dependence_list (rtx insn, rtx* listp)
+{
+ int removed = 0;
+
+ while (*listp)
+ {
+ if (XEXP (*listp, 0) == insn)
+ {
+ remove_free_INSN_LIST_node (listp);
+ removed++;
+ continue;
+ }
+
+ listp = &XEXP (*listp, 1);
+ }
+
+ return removed;
+}
+
+/* Same as above, but process two lists at once. */
+static int
+remove_from_both_dependence_lists (rtx insn, rtx *listp, rtx *exprp)
+{
+ int removed = 0;
+
+ while (*listp)
+ {
+ if (XEXP (*listp, 0) == insn)
+ {
+ remove_free_INSN_LIST_node (listp);
+ remove_free_EXPR_LIST_node (exprp);
+ removed++;
+ continue;
+ }
+
+ listp = &XEXP (*listp, 1);
+ exprp = &XEXP (*exprp, 1);
+ }
+
+ return removed;
+}
+
+/* Clear all dependencies for an insn. */
+static void
+delete_all_dependences (rtx insn)
+{
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ /* The below cycle can be optimized to clear the caches and back_deps
+ in one call but that would provoke duplication of code from
+ delete_dep (). */
+
+ for (sd_it = sd_iterator_start (insn, SD_LIST_BACK);
+ sd_iterator_cond (&sd_it, &dep);)
+ sd_delete_dep (sd_it);
+}
+
+/* All insns in a scheduling group except the first should only have
+ dependencies on the previous insn in the group. So we find the
+ first instruction in the scheduling group by walking the dependence
+ chains backwards. Then we add the dependencies for the group to
+ the previous nonnote insn. */
+
+static void
+fixup_sched_groups (rtx insn)
+{
+ sd_iterator_def sd_it;
+ dep_t dep;
+ rtx prev_nonnote;
+
+ FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
+ {
+ rtx i = insn;
+ rtx pro = DEP_PRO (dep);
+
+ do
+ {
+ i = prev_nonnote_insn (i);
+
+ if (pro == i)
+ goto next_link;
+ } while (SCHED_GROUP_P (i) || DEBUG_INSN_P (i));
+
+ if (! sched_insns_conditions_mutex_p (i, pro))
+ add_dependence (i, pro, DEP_TYPE (dep));
+ next_link:;
+ }
+
+ delete_all_dependences (insn);
+
+ prev_nonnote = prev_nonnote_nondebug_insn (insn);
+ if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
+ && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
+ add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
+}
+\f
+/* Process an insn's memory dependencies. There are four kinds of
+ dependencies:
+
+ (0) read dependence: read follows read
+ (1) true dependence: read follows write
+ (2) output dependence: write follows write
+ (3) anti dependence: write follows read
+
+ We are careful to build only dependencies which actually exist, and
+ use transitivity to avoid building too many links. */
+
+/* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
+ The MEM is a memory reference contained within INSN, which we are saving
+ so that we can do memory aliasing on it. */
+
+static void
+add_insn_mem_dependence (struct deps_desc *deps, bool read_p,
+ rtx insn, rtx mem)
+{
+ rtx *insn_list;
+ rtx *mem_list;
+ rtx link;
+
+ gcc_assert (!deps->readonly);
+ if (read_p)
+ {
+ insn_list = &deps->pending_read_insns;
+ mem_list = &deps->pending_read_mems;
+ if (!DEBUG_INSN_P (insn))
+ deps->pending_read_list_length++;
+ }
+ else
+ {
+ insn_list = &deps->pending_write_insns;
+ mem_list = &deps->pending_write_mems;
+ deps->pending_write_list_length++;
+ }
+
+ link = alloc_INSN_LIST (insn, *insn_list);
+ *insn_list = link;
+
+ if (sched_deps_info->use_cselib)
+ {
+ mem = shallow_copy_rtx (mem);
+ XEXP (mem, 0) = cselib_subst_to_values_from_insn (XEXP (mem, 0),
+ GET_MODE (mem), insn);
+ }
+ link = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
+ *mem_list = link;
+}
+
+/* Make a dependency between every memory reference on the pending lists
+ and INSN, thus flushing the pending lists. FOR_READ is true if emitting
+ dependencies for a read operation, similarly with FOR_WRITE. */
+
+static void
+flush_pending_lists (struct deps_desc *deps, rtx insn, int for_read,
+ int for_write)
+{
+ if (for_write)
+ {
+ add_dependence_list_and_free (deps, insn, &deps->pending_read_insns,
+ 1, REG_DEP_ANTI);
+ if (!deps->readonly)
+ {
+ free_EXPR_LIST_list (&deps->pending_read_mems);
+ deps->pending_read_list_length = 0;
+ }
+ }
+
+ add_dependence_list_and_free (deps, insn, &deps->pending_write_insns, 1,
+ for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
+
+ add_dependence_list_and_free (deps, insn,
+ &deps->last_pending_memory_flush, 1,
+ for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
+
+ add_dependence_list_and_free (deps, insn, &deps->pending_jump_insns, 1,
+ REG_DEP_ANTI);
+
+ if (!deps->readonly)
+ {
+ free_EXPR_LIST_list (&deps->pending_write_mems);
+ deps->pending_write_list_length = 0;
+
+ deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
+ deps->pending_flush_length = 1;
+ }
+}
+\f
+/* Instruction which dependencies we are analyzing. */
+static rtx cur_insn = NULL_RTX;
+
+/* Implement hooks for haifa scheduler. */
+
+static void
+haifa_start_insn (rtx insn)
+{
+ gcc_assert (insn && !cur_insn);
+
+ cur_insn = insn;
+}
+
+static void
+haifa_finish_insn (void)
+{
+ cur_insn = NULL;
+}
+
+void
+haifa_note_reg_set (int regno)
+{
+ SET_REGNO_REG_SET (reg_pending_sets, regno);
+}
+
+void
+haifa_note_reg_clobber (int regno)
+{
+ SET_REGNO_REG_SET (reg_pending_clobbers, regno);
+}
+
+void
+haifa_note_reg_use (int regno)
+{
+ SET_REGNO_REG_SET (reg_pending_uses, regno);
+}
+
+static void
+haifa_note_mem_dep (rtx mem, rtx pending_mem, rtx pending_insn, ds_t ds)
+{
+ if (!(ds & SPECULATIVE))
+ {
+ mem = NULL_RTX;
+ pending_mem = NULL_RTX;
+ }
+ else
+ gcc_assert (ds & BEGIN_DATA);
+
+ {
+ dep_def _dep, *dep = &_dep;
+
+ init_dep_1 (dep, pending_insn, cur_insn, ds_to_dt (ds),
+ current_sched_info->flags & USE_DEPS_LIST ? ds : 0);
+ maybe_add_or_update_dep_1 (dep, false, pending_mem, mem);
+ }
+
+}
+
+static void
+haifa_note_dep (rtx elem, ds_t ds)
+{
+ dep_def _dep;
+ dep_t dep = &_dep;
+
+ init_dep (dep, elem, cur_insn, ds_to_dt (ds));
+ maybe_add_or_update_dep_1 (dep, false, NULL_RTX, NULL_RTX);
+}
+
+static void
+note_reg_use (int r)
+{
+ if (sched_deps_info->note_reg_use)
+ sched_deps_info->note_reg_use (r);
+}
+
+static void
+note_reg_set (int r)
+{
+ if (sched_deps_info->note_reg_set)
+ sched_deps_info->note_reg_set (r);
+}
+
+static void
+note_reg_clobber (int r)
+{
+ if (sched_deps_info->note_reg_clobber)
+ sched_deps_info->note_reg_clobber (r);
+}
+
+static void
+note_mem_dep (rtx m1, rtx m2, rtx e, ds_t ds)
+{
+ if (sched_deps_info->note_mem_dep)
+ sched_deps_info->note_mem_dep (m1, m2, e, ds);
+}
+
+static void
+note_dep (rtx e, ds_t ds)
+{
+ if (sched_deps_info->note_dep)
+ sched_deps_info->note_dep (e, ds);
+}
+
+/* Return corresponding to DS reg_note. */
+enum reg_note
+ds_to_dt (ds_t ds)
+{
+ if (ds & DEP_TRUE)
+ return REG_DEP_TRUE;
+ else if (ds & DEP_OUTPUT)
+ return REG_DEP_OUTPUT;
+ else if (ds & DEP_ANTI)
+ return REG_DEP_ANTI;
+ else
+ {
+ gcc_assert (ds & DEP_CONTROL);
+ return REG_DEP_CONTROL;
+ }
+}
+
+\f
+
+/* Functions for computation of info needed for register pressure
+ sensitive insn scheduling. */
- ds = new_status;
- }
- /* Clear corresponding cache entry because type of the link
- may have changed. Keep them if we use_deps_list. */
- if (true_dependency_cache != NULL
- && !(current_sched_info->flags & USE_DEPS_LIST))
- {
- enum reg_note kind = DEP_KIND (link);
+/* Allocate and return reg_use_data structure for REGNO and INSN. */
+static struct reg_use_data *
+create_insn_reg_use (int regno, rtx insn)
+{
+ struct reg_use_data *use;
+
+ use = (struct reg_use_data *) xmalloc (sizeof (struct reg_use_data));
+ use->regno = regno;
+ use->insn = insn;
+ use->next_insn_use = INSN_REG_USE_LIST (insn);
+ INSN_REG_USE_LIST (insn) = use;
+ return use;
+}
- switch (kind)
- {
- case REG_DEP_OUTPUT:
- bitmap_clear_bit (&output_dependency_cache
- [INSN_LUID (insn)], INSN_LUID (elem));
- break;
- case REG_DEP_ANTI:
- bitmap_clear_bit (&anti_dependency_cache
- [INSN_LUID (insn)], INSN_LUID (elem));
- break;
- default:
- gcc_unreachable ();
- }
- }
+/* Allocate and return reg_set_data structure for REGNO and INSN. */
+static struct reg_set_data *
+create_insn_reg_set (int regno, rtx insn)
+{
+ struct reg_set_data *set;
+
+ set = (struct reg_set_data *) xmalloc (sizeof (struct reg_set_data));
+ set->regno = regno;
+ set->insn = insn;
+ set->next_insn_set = INSN_REG_SET_LIST (insn);
+ INSN_REG_SET_LIST (insn) = set;
+ return set;
+}
- if ((current_sched_info->flags & USE_DEPS_LIST)
- && DEP_STATUS (link) != ds)
- {
- DEP_STATUS (link) = ds;
- changed_p = DEP_CHANGED;
- }
-#endif
+/* Set up insn register uses for INSN and dependency context DEPS. */
+static void
+setup_insn_reg_uses (struct deps_desc *deps, rtx insn)
+{
+ unsigned i;
+ reg_set_iterator rsi;
+ rtx list;
+ struct reg_use_data *use, *use2, *next;
+ struct deps_reg *reg_last;
- /* If this is a more restrictive type of dependence than the
- existing one, then change the existing dependence to this
- type. */
- if ((int) dep_type < (int) DEP_KIND (link))
- {
- DEP_KIND (link) = dep_type;
- changed_p = DEP_CHANGED;
- }
+ EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
+ {
+ if (i < FIRST_PSEUDO_REGISTER
+ && TEST_HARD_REG_BIT (ira_no_alloc_regs, i))
+ continue;
-#ifdef INSN_SCHEDULING
- /* If we are adding a dependency to INSN's LOG_LINKs, then
- note that in the bitmap caches of dependency information. */
- if (true_dependency_cache != NULL)
- {
- if (!(current_sched_info->flags & USE_DEPS_LIST))
- {
- if (DEP_KIND (link) == REG_DEP_TRUE)
- bitmap_set_bit (&true_dependency_cache
- [INSN_LUID (insn)], INSN_LUID (elem));
- else if (DEP_KIND (link) == REG_DEP_OUTPUT)
- bitmap_set_bit (&output_dependency_cache
- [INSN_LUID (insn)], INSN_LUID (elem));
- else if (DEP_KIND (link) == REG_DEP_ANTI)
- bitmap_set_bit (&anti_dependency_cache
- [INSN_LUID (insn)], INSN_LUID (elem));
- }
- else
- {
- if (ds & DEP_TRUE)
- bitmap_set_bit (&true_dependency_cache
- [INSN_LUID (insn)], INSN_LUID (elem));
- if (ds & DEP_OUTPUT)
- bitmap_set_bit (&output_dependency_cache
- [INSN_LUID (insn)], INSN_LUID (elem));
- if (ds & DEP_ANTI)
- bitmap_set_bit (&anti_dependency_cache
- [INSN_LUID (insn)], INSN_LUID (elem));
- /* Note, that dep can become speculative only
- at the moment of creation. Thus, we don't need to
- check for it here. */
- }
- }
-
- if (changed_linkpp && changed_p == DEP_CHANGED)
- *changed_linkpp = linkp;
-#endif
- return changed_p;
- }
- }
- /* We didn't find a dep. It shouldn't be present in the cache. */
- gcc_assert (!present_p);
- }
+ if (find_regno_note (insn, REG_DEAD, i) == NULL_RTX
+ && ! REGNO_REG_SET_P (reg_pending_sets, i)
+ && ! REGNO_REG_SET_P (reg_pending_clobbers, i))
+ /* Ignore use which is not dying. */
+ continue;
- /* Might want to check one level of transitivity to save conses.
- This check should be done in maybe_add_or_update_back_dep_1.
- Since we made it to add_or_update_back_dep_1, we must create
- (or update) a link. */
+ use = create_insn_reg_use (i, insn);
+ use->next_regno_use = use;
+ reg_last = &deps->reg_last[i];
- if (mem1)
- {
- gcc_assert (current_sched_info->flags & DO_SPECULATION);
- ds = set_dep_weak (ds, BEGIN_DATA, estimate_dep_weak (mem1, mem2));
+ /* Create the cycle list of uses. */
+ for (list = reg_last->uses; list; list = XEXP (list, 1))
+ {
+ use2 = create_insn_reg_use (i, XEXP (list, 0));
+ next = use->next_regno_use;
+ use->next_regno_use = use2;
+ use2->next_regno_use = next;
+ }
}
-
- add_back_dep (insn, elem, dep_type, ds);
-
- return DEP_CREATED;
}
-/* This function creates a link between INSN and ELEM under any
- conditions. DS describes speculative status of the link. */
-static void
-add_back_dep (rtx insn, rtx elem, enum reg_note dep_type, ds_t ds)
+/* Register pressure info for the currently processed insn. */
+static struct reg_pressure_data reg_pressure_info[N_REG_CLASSES];
+
+/* Return TRUE if INSN has the use structure for REGNO. */
+static bool
+insn_use_p (rtx insn, int regno)
{
- struct _dep _dep, *dep = &_dep;
+ struct reg_use_data *use;
- gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
+ for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
+ if (use->regno == regno)
+ return true;
+ return false;
+}
- if (current_sched_info->flags & USE_DEPS_LIST)
- init_dep_1 (dep, elem, insn, dep_type, ds);
- else
- init_dep_1 (dep, elem, insn, dep_type, -1);
+/* Update the register pressure info after birth of pseudo register REGNO
+ in INSN. Arguments CLOBBER_P and UNUSED_P say correspondingly that
+ the register is in clobber or unused after the insn. */
+static void
+mark_insn_pseudo_birth (rtx insn, int regno, bool clobber_p, bool unused_p)
+{
+ int incr, new_incr;
+ enum reg_class cl;
- add_back_dep_to_deps_list (INSN_BACK_DEPS (insn), dep);
+ gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
+ cl = sched_regno_pressure_class[regno];
+ if (cl != NO_REGS)
+ {
+ incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
+ if (clobber_p)
+ {
+ new_incr = reg_pressure_info[cl].clobber_increase + incr;
+ reg_pressure_info[cl].clobber_increase = new_incr;
+ }
+ else if (unused_p)
+ {
+ new_incr = reg_pressure_info[cl].unused_set_increase + incr;
+ reg_pressure_info[cl].unused_set_increase = new_incr;
+ }
+ else
+ {
+ new_incr = reg_pressure_info[cl].set_increase + incr;
+ reg_pressure_info[cl].set_increase = new_incr;
+ if (! insn_use_p (insn, regno))
+ reg_pressure_info[cl].change += incr;
+ create_insn_reg_set (regno, insn);
+ }
+ gcc_assert (new_incr < (1 << INCREASE_BITS));
+ }
+}
-#ifdef INSN_SCHEDULING
-#ifdef ENABLE_CHECKING
- check_dep_status (dep_type, ds, false);
-#endif
+/* Like mark_insn_pseudo_regno_birth except that NREGS saying how many
+ hard registers involved in the birth. */
+static void
+mark_insn_hard_regno_birth (rtx insn, int regno, int nregs,
+ bool clobber_p, bool unused_p)
+{
+ enum reg_class cl;
+ int new_incr, last = regno + nregs;
- /* If we are adding a dependency to INSN's LOG_LINKs, then note that
- in the bitmap caches of dependency information. */
- if (true_dependency_cache != NULL)
+ while (regno < last)
{
- if (!(current_sched_info->flags & USE_DEPS_LIST))
- {
- if (dep_type == REG_DEP_TRUE)
- bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem));
- else if (dep_type == REG_DEP_OUTPUT)
- bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem));
- else if (dep_type == REG_DEP_ANTI)
- bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem));
- }
- else
- {
- if (ds & DEP_TRUE)
- bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem));
- if (ds & DEP_OUTPUT)
- bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem));
- if (ds & DEP_ANTI)
- bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem));
- if (ds & SPECULATIVE)
+ gcc_assert (regno < FIRST_PSEUDO_REGISTER);
+ if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
+ {
+ cl = sched_regno_pressure_class[regno];
+ if (cl != NO_REGS)
{
- gcc_assert (current_sched_info->flags & DO_SPECULATION);
- bitmap_set_bit (&spec_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem));
+ if (clobber_p)
+ {
+ new_incr = reg_pressure_info[cl].clobber_increase + 1;
+ reg_pressure_info[cl].clobber_increase = new_incr;
+ }
+ else if (unused_p)
+ {
+ new_incr = reg_pressure_info[cl].unused_set_increase + 1;
+ reg_pressure_info[cl].unused_set_increase = new_incr;
+ }
+ else
+ {
+ new_incr = reg_pressure_info[cl].set_increase + 1;
+ reg_pressure_info[cl].set_increase = new_incr;
+ if (! insn_use_p (insn, regno))
+ reg_pressure_info[cl].change += 1;
+ create_insn_reg_set (regno, insn);
+ }
+ gcc_assert (new_incr < (1 << INCREASE_BITS));
}
- }
+ }
+ regno++;
}
-#endif
}
-/* A convenience wrapper to operate on an entire list. */
+/* Update the register pressure info after birth of pseudo or hard
+ register REG in INSN. Arguments CLOBBER_P and UNUSED_P say
+ correspondingly that the register is in clobber or unused after the
+ insn. */
+static void
+mark_insn_reg_birth (rtx insn, rtx reg, bool clobber_p, bool unused_p)
+{
+ int regno;
+
+ if (GET_CODE (reg) == SUBREG)
+ reg = SUBREG_REG (reg);
+
+ if (! REG_P (reg))
+ return;
+
+ regno = REGNO (reg);
+ if (regno < FIRST_PSEUDO_REGISTER)
+ mark_insn_hard_regno_birth (insn, regno,
+ hard_regno_nregs[regno][GET_MODE (reg)],
+ clobber_p, unused_p);
+ else
+ mark_insn_pseudo_birth (insn, regno, clobber_p, unused_p);
+}
+/* Update the register pressure info after death of pseudo register
+ REGNO. */
static void
-add_dependence_list (rtx insn, rtx list, int uncond, enum reg_note dep_type)
+mark_pseudo_death (int regno)
{
- for (; list; list = XEXP (list, 1))
+ int incr;
+ enum reg_class cl;
+
+ gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
+ cl = sched_regno_pressure_class[regno];
+ if (cl != NO_REGS)
{
- if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
- add_dependence (insn, XEXP (list, 0), dep_type);
+ incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)];
+ reg_pressure_info[cl].change -= incr;
}
}
-/* Similar, but free *LISTP at the same time. */
-
+/* Like mark_pseudo_death except that NREGS saying how many hard
+ registers involved in the death. */
static void
-add_dependence_list_and_free (rtx insn, rtx *listp, int uncond,
- enum reg_note dep_type)
+mark_hard_regno_death (int regno, int nregs)
{
- rtx list, next;
- for (list = *listp, *listp = NULL; list ; list = next)
+ enum reg_class cl;
+ int last = regno + nregs;
+
+ while (regno < last)
{
- next = XEXP (list, 1);
- if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
- add_dependence (insn, XEXP (list, 0), dep_type);
- free_INSN_LIST_node (list);
+ gcc_assert (regno < FIRST_PSEUDO_REGISTER);
+ if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
+ {
+ cl = sched_regno_pressure_class[regno];
+ if (cl != NO_REGS)
+ reg_pressure_info[cl].change -= 1;
+ }
+ regno++;
}
}
-/* Clear all dependencies for an insn. */
-
+/* Update the register pressure info after death of pseudo or hard
+ register REG. */
static void
-delete_all_dependences (rtx insn)
+mark_reg_death (rtx reg)
{
- /* Clear caches, if they exist, as well as free the dependence. */
+ int regno;
-#ifdef INSN_SCHEDULING
- if (true_dependency_cache != NULL)
- {
- bitmap_clear (&true_dependency_cache[INSN_LUID (insn)]);
- bitmap_clear (&output_dependency_cache[INSN_LUID (insn)]);
- bitmap_clear (&anti_dependency_cache[INSN_LUID (insn)]);
- /* We don't have to clear forward_dependency_cache here,
- because it is formed later. */
- if (current_sched_info->flags & DO_SPECULATION)
- bitmap_clear (&spec_dependency_cache[INSN_LUID (insn)]);
- }
-#endif
+ if (GET_CODE (reg) == SUBREG)
+ reg = SUBREG_REG (reg);
+
+ if (! REG_P (reg))
+ return;
- clear_deps_list (INSN_BACK_DEPS (insn));
+ regno = REGNO (reg);
+ if (regno < FIRST_PSEUDO_REGISTER)
+ mark_hard_regno_death (regno, hard_regno_nregs[regno][GET_MODE (reg)]);
+ else
+ mark_pseudo_death (regno);
}
-/* All insns in a scheduling group except the first should only have
- dependencies on the previous insn in the group. So we find the
- first instruction in the scheduling group by walking the dependence
- chains backwards. Then we add the dependencies for the group to
- the previous nonnote insn. */
+/* Process SETTER of REG. DATA is an insn containing the setter. */
+static void
+mark_insn_reg_store (rtx reg, const_rtx setter, void *data)
+{
+ if (setter != NULL_RTX && GET_CODE (setter) != SET)
+ return;
+ mark_insn_reg_birth
+ ((rtx) data, reg, false,
+ find_reg_note ((const_rtx) data, REG_UNUSED, reg) != NULL_RTX);
+}
+/* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs. */
static void
-fixup_sched_groups (rtx insn)
+mark_insn_reg_clobber (rtx reg, const_rtx setter, void *data)
{
- dep_link_t link;
- rtx prev_nonnote;
+ if (GET_CODE (setter) == CLOBBER)
+ mark_insn_reg_birth ((rtx) data, reg, true, false);
+}
- FOR_EACH_DEP_LINK (link, INSN_BACK_DEPS (insn))
- {
- rtx i = insn;
- dep_t dep = DEP_LINK_DEP (link);
- rtx pro = DEP_PRO (dep);
+/* Set up reg pressure info related to INSN. */
+void
+init_insn_reg_pressure_info (rtx insn)
+{
+ int i, len;
+ enum reg_class cl;
+ static struct reg_pressure_data *pressure_info;
+ rtx link;
- do
- {
- i = prev_nonnote_insn (i);
+ gcc_assert (sched_pressure_p);
- if (pro == i)
- goto next_link;
- } while (SCHED_GROUP_P (i));
+ if (! INSN_P (insn))
+ return;
- if (! sched_insns_conditions_mutex_p (i, pro))
- add_dependence (i, pro, DEP_KIND (dep));
- next_link:;
+ for (i = 0; i < ira_pressure_classes_num; i++)
+ {
+ cl = ira_pressure_classes[i];
+ reg_pressure_info[cl].clobber_increase = 0;
+ reg_pressure_info[cl].set_increase = 0;
+ reg_pressure_info[cl].unused_set_increase = 0;
+ reg_pressure_info[cl].change = 0;
}
- delete_all_dependences (insn);
+ note_stores (PATTERN (insn), mark_insn_reg_clobber, insn);
- prev_nonnote = prev_nonnote_insn (insn);
- if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
- && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
- add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
+ note_stores (PATTERN (insn), mark_insn_reg_store, insn);
+
+#ifdef AUTO_INC_DEC
+ for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
+ if (REG_NOTE_KIND (link) == REG_INC)
+ mark_insn_reg_store (XEXP (link, 0), NULL_RTX, insn);
+#endif
+
+ for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
+ if (REG_NOTE_KIND (link) == REG_DEAD)
+ mark_reg_death (XEXP (link, 0));
+
+ len = sizeof (struct reg_pressure_data) * ira_pressure_classes_num;
+ pressure_info
+ = INSN_REG_PRESSURE (insn) = (struct reg_pressure_data *) xmalloc (len);
+ INSN_MAX_REG_PRESSURE (insn) = (int *) xcalloc (ira_pressure_classes_num
+ * sizeof (int), 1);
+ for (i = 0; i < ira_pressure_classes_num; i++)
+ {
+ cl = ira_pressure_classes[i];
+ pressure_info[i].clobber_increase
+ = reg_pressure_info[cl].clobber_increase;
+ pressure_info[i].set_increase = reg_pressure_info[cl].set_increase;
+ pressure_info[i].unused_set_increase
+ = reg_pressure_info[cl].unused_set_increase;
+ pressure_info[i].change = reg_pressure_info[cl].change;
+ }
}
-\f
-/* Process an insn's memory dependencies. There are four kinds of
- dependencies:
- (0) read dependence: read follows read
- (1) true dependence: read follows write
- (2) output dependence: write follows write
- (3) anti dependence: write follows read
- We are careful to build only dependencies which actually exist, and
- use transitivity to avoid building too many links. */
+\f
-/* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
- The MEM is a memory reference contained within INSN, which we are saving
- so that we can do memory aliasing on it. */
+/* Internal variable for sched_analyze_[12] () functions.
+ If it is nonzero, this means that sched_analyze_[12] looks
+ at the most toplevel SET. */
+static bool can_start_lhs_rhs_p;
+/* Extend reg info for the deps context DEPS given that
+ we have just generated a register numbered REGNO. */
static void
-add_insn_mem_dependence (struct deps *deps, bool read_p,
- rtx insn, rtx mem)
+extend_deps_reg_info (struct deps_desc *deps, int regno)
{
- rtx *insn_list;
- rtx *mem_list;
- rtx link;
+ int max_regno = regno + 1;
- if (read_p)
- {
- insn_list = &deps->pending_read_insns;
- mem_list = &deps->pending_read_mems;
- deps->pending_read_list_length++;
- }
- else
+ gcc_assert (!reload_completed);
+
+ /* In a readonly context, it would not hurt to extend info,
+ but it should not be needed. */
+ if (reload_completed && deps->readonly)
{
- insn_list = &deps->pending_write_insns;
- mem_list = &deps->pending_write_mems;
- deps->pending_write_list_length++;
+ deps->max_reg = max_regno;
+ return;
}
- link = alloc_INSN_LIST (insn, *insn_list);
- *insn_list = link;
-
- if (current_sched_info->use_cselib)
+ if (max_regno > deps->max_reg)
{
- mem = shallow_copy_rtx (mem);
- XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0));
+ deps->reg_last = XRESIZEVEC (struct deps_reg, deps->reg_last,
+ max_regno);
+ memset (&deps->reg_last[deps->max_reg],
+ 0, (max_regno - deps->max_reg)
+ * sizeof (struct deps_reg));
+ deps->max_reg = max_regno;
}
- link = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
- *mem_list = link;
}
-/* Make a dependency between every memory reference on the pending lists
- and INSN, thus flushing the pending lists. FOR_READ is true if emitting
- dependencies for a read operation, similarly with FOR_WRITE. */
-
-static void
-flush_pending_lists (struct deps *deps, rtx insn, int for_read,
- int for_write)
+/* Extends REG_INFO_P if needed. */
+void
+maybe_extend_reg_info_p (void)
{
- if (for_write)
+ /* Extend REG_INFO_P, if needed. */
+ if ((unsigned int)max_regno - 1 >= reg_info_p_size)
{
- add_dependence_list_and_free (insn, &deps->pending_read_insns, 1,
- REG_DEP_ANTI);
- free_EXPR_LIST_list (&deps->pending_read_mems);
- deps->pending_read_list_length = 0;
- }
+ size_t new_reg_info_p_size = max_regno + 128;
- add_dependence_list_and_free (insn, &deps->pending_write_insns, 1,
- for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
- free_EXPR_LIST_list (&deps->pending_write_mems);
- deps->pending_write_list_length = 0;
+ gcc_assert (!reload_completed && sel_sched_p ());
- add_dependence_list_and_free (insn, &deps->last_pending_memory_flush, 1,
- for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
- deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
- deps->pending_flush_length = 1;
+ reg_info_p = (struct reg_info_t *) xrecalloc (reg_info_p,
+ new_reg_info_p_size,
+ reg_info_p_size,
+ sizeof (*reg_info_p));
+ reg_info_p_size = new_reg_info_p_size;
+ }
}
-\f
+
/* Analyze a single reference to register (reg:MODE REGNO) in INSN.
The type of the reference is specified by REF and can be SET,
CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */
static void
-sched_analyze_reg (struct deps *deps, int regno, enum machine_mode mode,
+sched_analyze_reg (struct deps_desc *deps, int regno, enum machine_mode mode,
enum rtx_code ref, rtx insn)
{
+ /* We could emit new pseudos in renaming. Extend the reg structures. */
+ if (!reload_completed && sel_sched_p ()
+ && (regno >= max_reg_num () - 1 || regno >= deps->max_reg))
+ extend_deps_reg_info (deps, regno);
+
+ maybe_extend_reg_info_p ();
+
/* A hard reg in a wide mode may really be multiple registers.
If so, mark all of them just like the first. */
if (regno < FIRST_PSEUDO_REGISTER)
if (ref == SET)
{
while (--i >= 0)
- SET_REGNO_REG_SET (reg_pending_sets, regno + i);
+ note_reg_set (regno + i);
}
else if (ref == USE)
{
while (--i >= 0)
- SET_REGNO_REG_SET (reg_pending_uses, regno + i);
+ note_reg_use (regno + i);
}
else
{
while (--i >= 0)
- SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
+ note_reg_clobber (regno + i);
}
}
else
{
if (ref == SET)
- SET_REGNO_REG_SET (reg_pending_sets, regno);
+ note_reg_set (regno);
else if (ref == USE)
- SET_REGNO_REG_SET (reg_pending_uses, regno);
+ note_reg_use (regno);
else
- SET_REGNO_REG_SET (reg_pending_clobbers, regno);
+ note_reg_clobber (regno);
/* Pseudos that are REG_EQUIV to something may be replaced
by that during reloading. We need only add dependencies for
already cross one. */
if (REG_N_CALLS_CROSSED (regno) == 0)
{
- if (ref == USE)
+ if (!deps->readonly && ref == USE && !DEBUG_INSN_P (insn))
deps->sched_before_next_call
= alloc_INSN_LIST (insn, deps->sched_before_next_call);
else
destination of X, and reads of everything mentioned. */
static void
-sched_analyze_1 (struct deps *deps, rtx x, rtx insn)
+sched_analyze_1 (struct deps_desc *deps, rtx x, rtx insn)
{
rtx dest = XEXP (x, 0);
enum rtx_code code = GET_CODE (x);
+ bool cslr_p = can_start_lhs_rhs_p;
+
+ can_start_lhs_rhs_p = false;
+ gcc_assert (dest);
if (dest == 0)
return;
+ if (cslr_p && sched_deps_info->start_lhs)
+ sched_deps_info->start_lhs (dest);
+
if (GET_CODE (dest) == PARALLEL)
{
int i;
XEXP (XVECEXP (dest, 0, i), 0)),
insn);
- if (GET_CODE (x) == SET)
- sched_analyze_2 (deps, SET_SRC (x), insn);
+ if (cslr_p && sched_deps_info->finish_lhs)
+ sched_deps_info->finish_lhs ();
+
+ if (code == SET)
+ {
+ can_start_lhs_rhs_p = cslr_p;
+
+ sched_analyze_2 (deps, SET_SRC (x), insn);
+
+ can_start_lhs_rhs_p = false;
+ }
+
return;
}
/* Avoid analyzing the same register twice. */
if (regno != FIRST_STACK_REG)
sched_analyze_reg (deps, FIRST_STACK_REG, mode, code, insn);
- sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
+
+ add_to_hard_reg_set (&implicit_reg_pending_uses, mode,
+ FIRST_STACK_REG);
}
#endif
}
/* Writing memory. */
rtx t = dest;
- if (current_sched_info->use_cselib)
+ if (sched_deps_info->use_cselib)
{
+ enum machine_mode address_mode
+ = targetm.addr_space.address_mode (MEM_ADDR_SPACE (dest));
+
t = shallow_copy_rtx (dest);
- cselib_lookup (XEXP (t, 0), Pmode, 1);
- XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
+ cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
+ GET_MODE (t), insn);
+ XEXP (t, 0)
+ = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t),
+ insn);
}
t = canon_rtx (t);
- if ((deps->pending_read_list_length + deps->pending_write_list_length)
- > MAX_PENDING_LIST_LENGTH)
+ /* 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))
{
/* Flush all pending reads and writes to prevent the pending lists
from getting any larger. Insn scheduling runs too slowly when
{
if (anti_dependence (XEXP (pending_mem, 0), t)
&& ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
- add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
+ note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
+ DEP_ANTI);
pending = XEXP (pending, 1);
pending_mem = XEXP (pending_mem, 1);
{
if (output_dependence (XEXP (pending_mem, 0), t)
&& ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
- add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
+ note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
+ DEP_OUTPUT);
pending = XEXP (pending, 1);
pending_mem = XEXP (pending_mem, 1);
add_dependence_list (insn, deps->last_pending_memory_flush, 1,
REG_DEP_ANTI);
+ add_dependence_list (insn, deps->pending_jump_insns, 1,
+ REG_DEP_CONTROL);
- add_insn_mem_dependence (deps, false, insn, dest);
+ if (!deps->readonly)
+ add_insn_mem_dependence (deps, false, insn, dest);
}
sched_analyze_2 (deps, XEXP (dest, 0), insn);
}
+ if (cslr_p && sched_deps_info->finish_lhs)
+ sched_deps_info->finish_lhs ();
+
/* Analyze reads. */
if (GET_CODE (x) == SET)
- sched_analyze_2 (deps, SET_SRC (x), insn);
+ {
+ can_start_lhs_rhs_p = cslr_p;
+
+ sched_analyze_2 (deps, SET_SRC (x), insn);
+
+ can_start_lhs_rhs_p = false;
+ }
}
/* Analyze the uses of memory and registers in rtx X in INSN. */
-
static void
-sched_analyze_2 (struct deps *deps, rtx x, rtx insn)
+sched_analyze_2 (struct deps_desc *deps, rtx x, rtx insn)
{
int i;
int j;
enum rtx_code code;
const char *fmt;
+ bool cslr_p = can_start_lhs_rhs_p;
+ can_start_lhs_rhs_p = false;
+
+ gcc_assert (x);
if (x == 0)
return;
+ if (cslr_p && sched_deps_info->start_rhs)
+ sched_deps_info->start_rhs (x);
+
code = GET_CODE (x);
switch (code)
{
case CONST_INT:
case CONST_DOUBLE:
+ case CONST_FIXED:
case CONST_VECTOR:
case SYMBOL_REF:
case CONST:
case LABEL_REF:
- /* Ignore constants. Note that we must handle CONST_DOUBLE here
- because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
- this does not mean that this insn is using cc0. */
+ /* Ignore constants. */
+ if (cslr_p && sched_deps_info->finish_rhs)
+ sched_deps_info->finish_rhs ();
+
return;
#ifdef HAVE_cc0
/* Don't move CC0 setter to another block (it can set up the
same flag for previous CC0 users which is safe). */
CANT_MOVE (prev_nonnote_insn (insn)) = 1;
+
+ if (cslr_p && sched_deps_info->finish_rhs)
+ sched_deps_info->finish_rhs ();
+
return;
#endif
sched_analyze_reg (deps, FIRST_STACK_REG, mode, SET, insn);
}
#endif
+
+ if (cslr_p && sched_deps_info->finish_rhs)
+ sched_deps_info->finish_rhs ();
+
return;
}
rtx pending, pending_mem;
rtx t = x;
- if (current_sched_info->use_cselib)
- {
- t = shallow_copy_rtx (t);
- cselib_lookup (XEXP (t, 0), Pmode, 1);
- XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
- }
- t = canon_rtx (t);
- pending = deps->pending_read_insns;
- pending_mem = deps->pending_read_mems;
- while (pending)
+ if (sched_deps_info->use_cselib)
{
- if (read_dependence (XEXP (pending_mem, 0), t)
- && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
- add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
+ enum machine_mode address_mode
+ = targetm.addr_space.address_mode (MEM_ADDR_SPACE (t));
- pending = XEXP (pending, 1);
- pending_mem = XEXP (pending_mem, 1);
+ t = shallow_copy_rtx (t);
+ cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1,
+ GET_MODE (t), insn);
+ XEXP (t, 0)
+ = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t),
+ insn);
}
- pending = deps->pending_write_insns;
- pending_mem = deps->pending_write_mems;
- while (pending)
+ if (!DEBUG_INSN_P (insn))
{
- if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
- t, rtx_varies_p)
- && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
- {
- if (current_sched_info->flags & DO_SPECULATION)
- maybe_add_or_update_back_dep_1 (insn, XEXP (pending, 0),
- REG_DEP_TRUE,
- BEGIN_DATA | DEP_TRUE,
- XEXP (pending_mem, 0), t, 0);
- else
- add_dependence (insn, XEXP (pending, 0), REG_DEP_TRUE);
- }
-
- pending = XEXP (pending, 1);
- pending_mem = XEXP (pending_mem, 1);
+ t = canon_rtx (t);
+ pending = deps->pending_read_insns;
+ pending_mem = deps->pending_read_mems;
+ while (pending)
+ {
+ if (read_dependence (XEXP (pending_mem, 0), t)
+ && ! sched_insns_conditions_mutex_p (insn,
+ XEXP (pending, 0)))
+ note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
+ DEP_ANTI);
+
+ pending = XEXP (pending, 1);
+ pending_mem = XEXP (pending_mem, 1);
+ }
+
+ pending = deps->pending_write_insns;
+ pending_mem = deps->pending_write_mems;
+ while (pending)
+ {
+ if (true_dependence (XEXP (pending_mem, 0), VOIDmode, t)
+ && ! sched_insns_conditions_mutex_p (insn,
+ XEXP (pending, 0)))
+ note_mem_dep (t, XEXP (pending_mem, 0), XEXP (pending, 0),
+ sched_deps_info->generate_spec_deps
+ ? BEGIN_DATA | DEP_TRUE : DEP_TRUE);
+
+ pending = XEXP (pending, 1);
+ pending_mem = XEXP (pending_mem, 1);
+ }
+
+ for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
+ add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+
+ for (u = deps->pending_jump_insns; u; u = XEXP (u, 1))
+ if (deps_may_trap_p (x))
+ {
+ if ((sched_deps_info->generate_spec_deps)
+ && sel_sched_p () && (spec_info->mask & BEGIN_CONTROL))
+ {
+ ds_t ds = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
+ MAX_DEP_WEAK);
+
+ note_dep (XEXP (u, 0), ds);
+ }
+ else
+ add_dependence (insn, XEXP (u, 0), REG_DEP_CONTROL);
+ }
}
- for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
- if (! JUMP_P (XEXP (u, 0)) || deps_may_trap_p (x))
- add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-
/* Always add these dependencies to pending_reads, since
this insn may be followed by a write. */
- add_insn_mem_dependence (deps, true, insn, x);
+ if (!deps->readonly)
+ add_insn_mem_dependence (deps, true, insn, x);
- /* Take advantage of tail recursion here. */
sched_analyze_2 (deps, XEXP (x, 0), insn);
+
+ if (cslr_p && sched_deps_info->finish_rhs)
+ sched_deps_info->finish_rhs ();
+
return;
}
flush_pending_lists (deps, insn, true, false);
break;
+ case PREFETCH:
+ if (PREFETCH_SCHEDULE_BARRIER_P (x))
+ reg_pending_barrier = TRUE_BARRIER;
+ break;
+
+ case UNSPEC_VOLATILE:
+ flush_pending_lists (deps, insn, true, true);
+ /* FALLTHRU */
+
case ASM_OPERANDS:
case ASM_INPUT:
- case UNSPEC_VOLATILE:
{
/* Traditional and volatile asm instructions must be considered to use
and clobber all hard registers, all pseudo-registers and all of
{
for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
+
+ if (cslr_p && sched_deps_info->finish_rhs)
+ sched_deps_info->finish_rhs ();
+
return;
}
break;
to get the proper antecedent for the read. */
sched_analyze_2 (deps, XEXP (x, 0), insn);
sched_analyze_1 (deps, x, insn);
+
+ if (cslr_p && sched_deps_info->finish_rhs)
+ sched_deps_info->finish_rhs ();
+
return;
case POST_MODIFY:
sched_analyze_2 (deps, XEXP (x, 0), insn);
sched_analyze_2 (deps, XEXP (x, 1), insn);
sched_analyze_1 (deps, x, insn);
+
+ if (cslr_p && sched_deps_info->finish_rhs)
+ sched_deps_info->finish_rhs ();
+
return;
default:
for (j = 0; j < XVECLEN (x, i); j++)
sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
}
+
+ if (cslr_p && sched_deps_info->finish_rhs)
+ sched_deps_info->finish_rhs ();
}
/* Analyze an INSN with pattern X to find all dependencies. */
-
static void
-sched_analyze_insn (struct deps *deps, rtx x, rtx insn)
+sched_analyze_insn (struct deps_desc *deps, rtx x, rtx insn)
{
RTX_CODE code = GET_CODE (x);
rtx link;
unsigned i;
reg_set_iterator rsi;
+ if (! reload_completed)
+ {
+ HARD_REG_SET temp;
+
+ extract_insn (insn);
+ preprocess_constraints ();
+ ira_implicitly_set_insn_hard_regs (&temp);
+ AND_COMPL_HARD_REG_SET (temp, ira_no_alloc_regs);
+ IOR_HARD_REG_SET (implicit_reg_pending_clobbers, temp);
+ }
+
+ can_start_lhs_rhs_p = (NONJUMP_INSN_P (insn)
+ && code == SET);
+
+ if (may_trap_p (x))
+ /* Avoid moving trapping instructions accross function calls that might
+ not always return. */
+ add_dependence_list (insn, deps->last_function_call_may_noreturn,
+ 1, REG_DEP_ANTI);
+
+ /* We must avoid creating a situation in which two successors of the
+ current block have different unwind info after scheduling. If at any
+ point the two paths re-join this leads to incorrect unwind info. */
+ /* ??? There are certain situations involving a forced frame pointer in
+ which, with extra effort, we could fix up the unwind info at a later
+ CFG join. However, it seems better to notice these cases earlier
+ during prologue generation and avoid marking the frame pointer setup
+ as frame-related at all. */
+ if (RTX_FRAME_RELATED_P (insn))
+ {
+ /* Make sure prologue insn is scheduled before next jump. */
+ deps->sched_before_next_jump
+ = alloc_INSN_LIST (insn, deps->sched_before_next_jump);
+
+ /* Make sure epilogue insn is scheduled after preceding jumps. */
+ add_dependence_list (insn, deps->pending_jump_insns, 1, REG_DEP_ANTI);
+ }
+
if (code == COND_EXEC)
{
sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
and others know that a value is dead. Depend on the last call
instruction so that reg-stack won't get confused. */
if (code == CLOBBER)
- add_dependence_list (insn, deps->last_function_call, 1, REG_DEP_OUTPUT);
+ add_dependence_list (insn, deps->last_function_call, 1,
+ REG_DEP_OUTPUT);
}
else if (code == PARALLEL)
{
else
sched_analyze_2 (deps, XEXP (link, 0), insn);
}
- if (find_reg_note (insn, REG_SETJMP, NULL))
+ /* Don't schedule anything after a tail call, tail call needs
+ to use at least all call-saved registers. */
+ if (SIBLING_CALL_P (insn))
+ reg_pending_barrier = TRUE_BARRIER;
+ else if (find_reg_note (insn, REG_SETJMP, NULL))
reg_pending_barrier = MOVE_BARRIER;
}
if (JUMP_P (insn))
{
rtx next;
- next = next_nonnote_insn (insn);
+ next = next_nonnote_nondebug_insn (insn);
if (next && BARRIER_P (next))
- reg_pending_barrier = TRUE_BARRIER;
+ reg_pending_barrier = MOVE_BARRIER;
else
{
rtx pending, pending_mem;
- regset_head tmp_uses, tmp_sets;
- INIT_REG_SET (&tmp_uses);
- INIT_REG_SET (&tmp_sets);
-
- (*current_sched_info->compute_jump_reg_dependencies)
- (insn, &deps->reg_conditional_sets, &tmp_uses, &tmp_sets);
- /* Make latency of jump equal to 0 by using anti-dependence. */
- EXECUTE_IF_SET_IN_REG_SET (&tmp_uses, 0, i, rsi)
- {
- struct deps_reg *reg_last = &deps->reg_last[i];
- add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI);
- add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI);
- reg_last->uses_length++;
- reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
- }
- IOR_REG_SET (reg_pending_sets, &tmp_sets);
- CLEAR_REG_SET (&tmp_uses);
- CLEAR_REG_SET (&tmp_sets);
+ if (sched_deps_info->compute_jump_reg_dependencies)
+ {
+ (*sched_deps_info->compute_jump_reg_dependencies)
+ (insn, reg_pending_control_uses);
+
+ /* Make latency of jump equal to 0 by using anti-dependence. */
+ EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
+ {
+ struct deps_reg *reg_last = &deps->reg_last[i];
+ add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI);
+ add_dependence_list (insn, reg_last->implicit_sets,
+ 0, REG_DEP_ANTI);
+ add_dependence_list (insn, reg_last->clobbers, 0,
+ REG_DEP_ANTI);
+ }
+ }
/* All memory writes and volatile reads must happen before the
jump. Non-volatile reads must happen before the jump iff
add_dependence_list (insn, deps->last_pending_memory_flush, 1,
REG_DEP_ANTI);
+ add_dependence_list (insn, deps->pending_jump_insns, 1,
+ REG_DEP_ANTI);
}
}
|| (NONJUMP_INSN_P (insn) && control_flow_insn_p (insn)))
reg_pending_barrier = MOVE_BARRIER;
- /* Add dependencies if a scheduling barrier was found. */
- if (reg_pending_barrier)
+ if (sched_pressure_p)
{
- /* In the case of barrier the most added dependencies are not
- real, so we use anti-dependence here. */
- if (sched_get_condition (insn))
+ setup_insn_reg_uses (deps, insn);
+ init_insn_reg_pressure_info (insn);
+ }
+
+ /* Add register dependencies for insn. */
+ if (DEBUG_INSN_P (insn))
+ {
+ rtx prev = deps->last_debug_insn;
+ rtx u;
+
+ if (!deps->readonly)
+ deps->last_debug_insn = insn;
+
+ if (prev)
+ add_dependence (insn, prev, REG_DEP_ANTI);
+
+ add_dependence_list (insn, deps->last_function_call, 1,
+ REG_DEP_ANTI);
+
+ for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
+ if (!sel_sched_p ())
+ add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+
+ EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
{
- EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
- {
- struct deps_reg *reg_last = &deps->reg_last[i];
- add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
- add_dependence_list
- (insn, reg_last->sets, 0,
- reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
- add_dependence_list
- (insn, reg_last->clobbers, 0,
- reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
- }
+ struct deps_reg *reg_last = &deps->reg_last[i];
+ add_dependence_list (insn, reg_last->sets, 1, REG_DEP_ANTI);
+ /* There's no point in making REG_DEP_CONTROL dependencies for
+ debug insns. */
+ add_dependence_list (insn, reg_last->clobbers, 1, REG_DEP_ANTI);
+
+ if (!deps->readonly)
+ reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
}
- else
+ CLEAR_REG_SET (reg_pending_uses);
+
+ /* Quite often, a debug insn will refer to stuff in the
+ previous instruction, but the reason we want this
+ dependency here is to make sure the scheduler doesn't
+ gratuitously move a debug insn ahead. This could dirty
+ DF flags and cause additional analysis that wouldn't have
+ occurred in compilation without debug insns, and such
+ additional analysis can modify the generated code. */
+ prev = PREV_INSN (insn);
+
+ if (prev && NONDEBUG_INSN_P (prev))
+ add_dependence (insn, prev, REG_DEP_ANTI);
+ }
+ else
+ {
+ regset_head set_or_clobbered;
+
+ EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
{
- EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
+ struct deps_reg *reg_last = &deps->reg_last[i];
+ add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
+ add_dependence_list (insn, reg_last->implicit_sets, 0, REG_DEP_ANTI);
+ add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
+
+ if (!deps->readonly)
{
- struct deps_reg *reg_last = &deps->reg_last[i];
- add_dependence_list_and_free (insn, ®_last->uses, 0,
- REG_DEP_ANTI);
- add_dependence_list_and_free
- (insn, ®_last->sets, 0,
- reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
- add_dependence_list_and_free
- (insn, ®_last->clobbers, 0,
- reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
- reg_last->uses_length = 0;
- reg_last->clobbers_length = 0;
+ reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
+ reg_last->uses_length++;
}
}
- for (i = 0; i < (unsigned)deps->max_reg; i++)
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i))
+ {
+ struct deps_reg *reg_last = &deps->reg_last[i];
+ add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
+ add_dependence_list (insn, reg_last->implicit_sets, 0,
+ REG_DEP_ANTI);
+ add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
+
+ if (!deps->readonly)
+ {
+ reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
+ reg_last->uses_length++;
+ }
+ }
+
+ if (targetm.sched.exposed_pipeline)
{
- struct deps_reg *reg_last = &deps->reg_last[i];
- reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
- SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
+ INIT_REG_SET (&set_or_clobbered);
+ bitmap_ior (&set_or_clobbered, reg_pending_clobbers,
+ reg_pending_sets);
+ EXECUTE_IF_SET_IN_REG_SET (&set_or_clobbered, 0, i, rsi)
+ {
+ struct deps_reg *reg_last = &deps->reg_last[i];
+ rtx list;
+ for (list = reg_last->uses; list; list = XEXP (list, 1))
+ {
+ 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))
+ INSN_CACHED_COND (other) = const_true_rtx;
+ }
+ }
}
- flush_pending_lists (deps, insn, true, true);
- CLEAR_REG_SET (&deps->reg_conditional_sets);
- reg_pending_barrier = NOT_A_BARRIER;
- }
- else
- {
/* If the current insn is conditional, we can't free any
of the lists. */
- if (sched_get_condition (insn))
+ if (sched_has_condition_p (insn))
{
- EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
- {
- struct deps_reg *reg_last = &deps->reg_last[i];
- add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
- add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
- reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
- reg_last->uses_length++;
- }
EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
{
struct deps_reg *reg_last = &deps->reg_last[i];
add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
+ add_dependence_list (insn, reg_last->implicit_sets, 0,
+ REG_DEP_ANTI);
add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
- reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
- reg_last->clobbers_length++;
+ add_dependence_list (insn, reg_last->control_uses, 0,
+ REG_DEP_CONTROL);
+
+ if (!deps->readonly)
+ {
+ reg_last->clobbers
+ = alloc_INSN_LIST (insn, reg_last->clobbers);
+ reg_last->clobbers_length++;
+ }
}
EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
{
struct deps_reg *reg_last = &deps->reg_last[i];
add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
+ add_dependence_list (insn, reg_last->implicit_sets, 0,
+ REG_DEP_ANTI);
add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT);
add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
- reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
- SET_REGNO_REG_SET (&deps->reg_conditional_sets, i);
+ add_dependence_list (insn, reg_last->control_uses, 0,
+ REG_DEP_CONTROL);
+
+ if (!deps->readonly)
+ reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
}
}
else
{
- EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
- {
- struct deps_reg *reg_last = &deps->reg_last[i];
- add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
- add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
- reg_last->uses_length++;
- reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
- }
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)
{
- add_dependence_list_and_free (insn, ®_last->sets, 0,
- REG_DEP_OUTPUT);
- add_dependence_list_and_free (insn, ®_last->uses, 0,
- REG_DEP_ANTI);
- add_dependence_list_and_free (insn, ®_last->clobbers, 0,
+ add_dependence_list_and_free (deps, insn, ®_last->sets, 0,
REG_DEP_OUTPUT);
- reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
- reg_last->clobbers_length = 0;
- reg_last->uses_length = 0;
+ add_dependence_list_and_free (deps, insn,
+ ®_last->implicit_sets, 0,
+ REG_DEP_ANTI);
+ add_dependence_list_and_free (deps, insn, ®_last->uses, 0,
+ REG_DEP_ANTI);
+ add_dependence_list_and_free (deps, insn,
+ ®_last->control_uses, 0,
+ REG_DEP_ANTI);
+ add_dependence_list_and_free
+ (deps, insn, ®_last->clobbers, 0, REG_DEP_OUTPUT);
+
+ if (!deps->readonly)
+ {
+ reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
+ reg_last->clobbers_length = 0;
+ reg_last->uses_length = 0;
+ }
}
else
{
add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
+ add_dependence_list (insn, reg_last->implicit_sets, 0,
+ REG_DEP_ANTI);
add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
+ add_dependence_list (insn, reg_last->control_uses, 0,
+ REG_DEP_CONTROL);
+ }
+
+ if (!deps->readonly)
+ {
+ reg_last->clobbers_length++;
+ reg_last->clobbers
+ = alloc_INSN_LIST (insn, reg_last->clobbers);
}
- reg_last->clobbers_length++;
- reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
}
EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
{
struct deps_reg *reg_last = &deps->reg_last[i];
- add_dependence_list_and_free (insn, ®_last->sets, 0,
+
+ add_dependence_list_and_free (deps, insn, ®_last->sets, 0,
REG_DEP_OUTPUT);
- add_dependence_list_and_free (insn, ®_last->clobbers, 0,
+ add_dependence_list_and_free (deps, insn,
+ ®_last->implicit_sets,
+ 0, REG_DEP_ANTI);
+ add_dependence_list_and_free (deps, insn, ®_last->clobbers, 0,
REG_DEP_OUTPUT);
- add_dependence_list_and_free (insn, ®_last->uses, 0,
+ add_dependence_list_and_free (deps, insn, ®_last->uses, 0,
REG_DEP_ANTI);
- reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
- reg_last->uses_length = 0;
- reg_last->clobbers_length = 0;
- CLEAR_REGNO_REG_SET (&deps->reg_conditional_sets, i);
+ add_dependence_list (insn, reg_last->control_uses, 0,
+ REG_DEP_CONTROL);
+
+ if (!deps->readonly)
+ {
+ reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
+ reg_last->uses_length = 0;
+ reg_last->clobbers_length = 0;
+ }
+ }
+ }
+ if (!deps->readonly)
+ {
+ EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
+ {
+ struct deps_reg *reg_last = &deps->reg_last[i];
+ reg_last->control_uses
+ = alloc_INSN_LIST (insn, reg_last->control_uses);
}
}
+ }
+
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
+ {
+ struct deps_reg *reg_last = &deps->reg_last[i];
+ add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI);
+ add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI);
+ add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
+ add_dependence_list (insn, reg_last->control_uses, 0, REG_DEP_ANTI);
+
+ if (!deps->readonly)
+ reg_last->implicit_sets
+ = alloc_INSN_LIST (insn, reg_last->implicit_sets);
+ }
+ if (!deps->readonly)
+ {
IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i)
+ || TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i))
+ SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
+
+ /* Set up the pending barrier found. */
+ deps->last_reg_pending_barrier = reg_pending_barrier;
}
+
CLEAR_REG_SET (reg_pending_uses);
CLEAR_REG_SET (reg_pending_clobbers);
CLEAR_REG_SET (reg_pending_sets);
+ CLEAR_REG_SET (reg_pending_control_uses);
+ CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
+ CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
- /* If we are currently in a libcall scheduling group, then mark the
- current insn as being in a scheduling group and that it can not
- be moved into a different basic block. */
-
- if (deps->libcall_block_tail_insn)
+ /* Add dependencies if a scheduling barrier was found. */
+ if (reg_pending_barrier)
{
- SCHED_GROUP_P (insn) = 1;
- CANT_MOVE (insn) = 1;
+ /* In the case of barrier the most added dependencies are not
+ real, so we use anti-dependence here. */
+ if (sched_has_condition_p (insn))
+ {
+ EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
+ {
+ struct deps_reg *reg_last = &deps->reg_last[i];
+ add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
+ add_dependence_list (insn, reg_last->sets, 0,
+ reg_pending_barrier == TRUE_BARRIER
+ ? REG_DEP_TRUE : REG_DEP_ANTI);
+ add_dependence_list (insn, reg_last->implicit_sets, 0,
+ REG_DEP_ANTI);
+ add_dependence_list (insn, reg_last->clobbers, 0,
+ reg_pending_barrier == TRUE_BARRIER
+ ? REG_DEP_TRUE : REG_DEP_ANTI);
+ }
+ }
+ else
+ {
+ EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
+ {
+ struct deps_reg *reg_last = &deps->reg_last[i];
+ add_dependence_list_and_free (deps, insn, ®_last->uses, 0,
+ REG_DEP_ANTI);
+ add_dependence_list_and_free (deps, insn,
+ ®_last->control_uses, 0,
+ REG_DEP_CONTROL);
+ add_dependence_list_and_free (deps, insn, ®_last->sets, 0,
+ reg_pending_barrier == TRUE_BARRIER
+ ? REG_DEP_TRUE : REG_DEP_ANTI);
+ add_dependence_list_and_free (deps, insn,
+ ®_last->implicit_sets, 0,
+ REG_DEP_ANTI);
+ add_dependence_list_and_free (deps, insn, ®_last->clobbers, 0,
+ reg_pending_barrier == TRUE_BARRIER
+ ? REG_DEP_TRUE : REG_DEP_ANTI);
+
+ if (!deps->readonly)
+ {
+ reg_last->uses_length = 0;
+ reg_last->clobbers_length = 0;
+ }
+ }
+ }
+
+ if (!deps->readonly)
+ for (i = 0; i < (unsigned)deps->max_reg; i++)
+ {
+ struct deps_reg *reg_last = &deps->reg_last[i];
+ reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
+ SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
+ }
+
+ /* Flush pending lists on jumps, but not on speculative checks. */
+ if (JUMP_P (insn) && !(sel_sched_p ()
+ && sel_insn_is_speculation_check (insn)))
+ flush_pending_lists (deps, insn, true, true);
+
+ reg_pending_barrier = NOT_A_BARRIER;
}
/* If a post-call group is still open, see if it should remain so.
This insn must be a simple move of a hard reg to a pseudo or
vice-versa.
- We must avoid moving these insns for correctness on
- SMALL_REGISTER_CLASS machines, and for special registers like
+ We must avoid moving these insns for correctness on targets
+ with small register classes, and for special registers like
PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all
hard regs for all targets. */
int src_regno, dest_regno;
if (set == NULL)
- goto end_call_group;
+ {
+ if (DEBUG_INSN_P (insn))
+ /* We don't want to mark debug insns as part of the same
+ sched group. We know they really aren't, but if we use
+ debug insns to tell that a call group is over, we'll
+ get different code if debug insns are not there and
+ instructions that follow seem like they should be part
+ of the call group.
+
+ Also, if we did, fixup_sched_groups() would move the
+ deps of the debug insn to the call insn, modifying
+ non-debug post-dependency counts of the debug insn
+ dependencies and otherwise messing with the scheduling
+ order.
+
+ Instead, let such debug insns be scheduled freely, but
+ keep the call group open in case there are insns that
+ should be part of it afterwards. Since we grant debug
+ insns higher priority than even sched group insns, it
+ will all turn out all right. */
+ goto debug_dont_end_call_group;
+ else
+ goto end_call_group;
+ }
tmp = SET_DEST (set);
if (GET_CODE (tmp) == SUBREG)
if (src_regno < FIRST_PSEUDO_REGISTER
|| dest_regno < FIRST_PSEUDO_REGISTER)
{
- if (deps->in_post_call_group_p == post_call_initial)
+ if (!deps->readonly
+ && deps->in_post_call_group_p == post_call_initial)
deps->in_post_call_group_p = post_call;
- SCHED_GROUP_P (insn) = 1;
- CANT_MOVE (insn) = 1;
+ if (!sel_sched_p () || sched_emulate_haifa_p)
+ {
+ SCHED_GROUP_P (insn) = 1;
+ CANT_MOVE (insn) = 1;
+ }
}
else
{
end_call_group:
- deps->in_post_call_group_p = not_post_call;
+ if (!deps->readonly)
+ deps->in_post_call_group_p = not_post_call;
}
}
- /* Fixup the dependencies in the sched group. */
- if (SCHED_GROUP_P (insn))
- fixup_sched_groups (insn);
+ debug_dont_end_call_group:
+ if ((current_sched_info->flags & DO_SPECULATION)
+ && !sched_insn_is_legitimate_for_speculation_p (insn, 0))
+ /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot
+ be speculated. */
+ {
+ if (sel_sched_p ())
+ sel_mark_hard_insn (insn);
+ else
+ {
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
+ sd_iterator_cond (&sd_it, &dep);)
+ change_spec_dep_to_hard (sd_it);
+ }
+ }
}
-/* Analyze every insn between HEAD and TAIL inclusive, creating backward
- dependencies for each insn. */
+/* Return TRUE if INSN might not always return normally (e.g. call exit,
+ longjmp, loop forever, ...). */
+static bool
+call_may_noreturn_p (rtx insn)
+{
+ rtx call;
+
+ /* const or pure calls that aren't looping will always return. */
+ if (RTL_CONST_OR_PURE_CALL_P (insn)
+ && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn))
+ return false;
+
+ call = PATTERN (insn);
+ if (GET_CODE (call) == PARALLEL)
+ call = XVECEXP (call, 0, 0);
+ if (GET_CODE (call) == SET)
+ call = SET_SRC (call);
+ if (GET_CODE (call) == CALL
+ && MEM_P (XEXP (call, 0))
+ && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
+ {
+ rtx symbol = XEXP (XEXP (call, 0), 0);
+ if (SYMBOL_REF_DECL (symbol)
+ && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
+ {
+ if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
+ == BUILT_IN_NORMAL)
+ switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol)))
+ {
+ case BUILT_IN_BCMP:
+ case BUILT_IN_BCOPY:
+ case BUILT_IN_BZERO:
+ case BUILT_IN_INDEX:
+ case BUILT_IN_MEMCHR:
+ case BUILT_IN_MEMCMP:
+ case BUILT_IN_MEMCPY:
+ case BUILT_IN_MEMMOVE:
+ case BUILT_IN_MEMPCPY:
+ case BUILT_IN_MEMSET:
+ case BUILT_IN_RINDEX:
+ case BUILT_IN_STPCPY:
+ case BUILT_IN_STPNCPY:
+ case BUILT_IN_STRCAT:
+ case BUILT_IN_STRCHR:
+ case BUILT_IN_STRCMP:
+ case BUILT_IN_STRCPY:
+ case BUILT_IN_STRCSPN:
+ case BUILT_IN_STRLEN:
+ case BUILT_IN_STRNCAT:
+ case BUILT_IN_STRNCMP:
+ case BUILT_IN_STRNCPY:
+ case BUILT_IN_STRPBRK:
+ case BUILT_IN_STRRCHR:
+ case BUILT_IN_STRSPN:
+ case BUILT_IN_STRSTR:
+ /* Assume certain string/memory builtins always return. */
+ return false;
+ default:
+ break;
+ }
+ }
+ }
+ /* For all other calls assume that they might not always return. */
+ return true;
+}
+
+/* Analyze INSN with DEPS as a context. */
void
-sched_analyze (struct deps *deps, rtx head, rtx tail)
+deps_analyze_insn (struct deps_desc *deps, rtx insn)
{
- rtx insn;
+ if (sched_deps_info->start_insn)
+ sched_deps_info->start_insn (insn);
- if (current_sched_info->use_cselib)
- cselib_init (true);
+ /* Record the condition for this insn. */
+ if (NONDEBUG_INSN_P (insn))
+ {
+ rtx t;
+ sched_get_condition_with_rev (insn, NULL);
+ t = INSN_CACHED_COND (insn);
+ INSN_COND_DEPS (insn) = NULL_RTX;
+ if (reload_completed
+ && (current_sched_info->flags & DO_PREDICATION)
+ && COMPARISON_P (t)
+ && REG_P (XEXP (t, 0))
+ && CONSTANT_P (XEXP (t, 1)))
+ {
+ unsigned int regno;
+ int nregs;
+ t = XEXP (t, 0);
+ regno = REGNO (t);
+ nregs = hard_regno_nregs[regno][GET_MODE (t)];
+ t = NULL_RTX;
+ while (nregs-- > 0)
+ {
+ struct deps_reg *reg_last = &deps->reg_last[regno + nregs];
+ t = concat_INSN_LIST (reg_last->sets, t);
+ t = concat_INSN_LIST (reg_last->clobbers, t);
+ t = concat_INSN_LIST (reg_last->implicit_sets, t);
+ }
+ INSN_COND_DEPS (insn) = t;
+ }
+ }
- /* Before reload, if the previous block ended in a call, show that
- we are inside a post-call group, so as to keep the lifetimes of
- hard registers correct. */
- if (! reload_completed && !LABEL_P (head))
+ if (JUMP_P (insn))
{
- insn = prev_nonnote_insn (head);
- if (insn && CALL_P (insn))
- deps->in_post_call_group_p = post_call_initial;
+ /* Make each JUMP_INSN (but not a speculative check)
+ a scheduling barrier for memory references. */
+ if (!deps->readonly
+ && !(sel_sched_p ()
+ && sel_insn_is_speculation_check (insn)))
+ {
+ /* Keep the list a reasonable size. */
+ if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
+ flush_pending_lists (deps, insn, true, true);
+ else
+ deps->pending_jump_insns
+ = alloc_INSN_LIST (insn, deps->pending_jump_insns);
+ }
+
+ /* For each insn which shouldn't cross a jump, add a dependence. */
+ add_dependence_list_and_free (deps, insn,
+ &deps->sched_before_next_jump, 1,
+ REG_DEP_ANTI);
+
+ sched_analyze_insn (deps, PATTERN (insn), insn);
}
- for (insn = head;; insn = NEXT_INSN (insn))
+ else if (NONJUMP_INSN_P (insn) || DEBUG_INSN_P (insn))
{
- rtx link, end_seq, r0, set;
+ sched_analyze_insn (deps, PATTERN (insn), insn);
+ }
+ else if (CALL_P (insn))
+ {
+ int i;
- if (INSN_P (insn))
- {
- /* These two lists will be freed in schedule_insn (). */
- INSN_BACK_DEPS (insn) = create_deps_list (false);
- INSN_RESOLVED_BACK_DEPS (insn) = create_deps_list (false);
+ CANT_MOVE (insn) = 1;
- /* This one should be allocated on the obstack because it should live
- till the scheduling ends. */
- INSN_FORW_DEPS (insn) = create_deps_list (true);
- }
+ if (find_reg_note (insn, REG_SETJMP, NULL))
+ {
+ /* This is setjmp. Assume that all registers, not just
+ hard registers, may be clobbered by this call. */
+ reg_pending_barrier = MOVE_BARRIER;
+ }
+ else
+ {
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ /* A call may read and modify global register variables. */
+ if (global_regs[i])
+ {
+ SET_REGNO_REG_SET (reg_pending_sets, i);
+ SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
+ }
+ /* Other call-clobbered hard regs may be clobbered.
+ Since we only have a choice between 'might be clobbered'
+ and 'definitely not clobbered', we must include all
+ partly call-clobbered registers here. */
+ else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
+ || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
+ SET_REGNO_REG_SET (reg_pending_clobbers, i);
+ /* We don't know what set of fixed registers might be used
+ by the function, but it is certain that the stack pointer
+ is among them, but be conservative. */
+ else if (fixed_regs[i])
+ SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
+ /* The frame pointer is normally not used by the function
+ itself, but by the debugger. */
+ /* ??? MIPS o32 is an exception. It uses the frame pointer
+ in the macro expansion of jal but does not represent this
+ fact in the call_insn rtl. */
+ else if (i == FRAME_POINTER_REGNUM
+ || (i == HARD_FRAME_POINTER_REGNUM
+ && (! reload_completed || frame_pointer_needed)))
+ SET_HARD_REG_BIT (implicit_reg_pending_uses, i);
+ }
- if (NONJUMP_INSN_P (insn) || JUMP_P (insn))
- {
- /* Make each JUMP_INSN a scheduling barrier for memory
- references. */
- if (JUMP_P (insn))
- {
- /* Keep the list a reasonable size. */
- if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
- flush_pending_lists (deps, insn, true, true);
- else
- deps->last_pending_memory_flush
- = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
- }
- sched_analyze_insn (deps, PATTERN (insn), insn);
- }
- else if (CALL_P (insn))
- {
- int i;
+ /* For each insn which shouldn't cross a call, add a dependence
+ between that insn and this call insn. */
+ add_dependence_list_and_free (deps, insn,
+ &deps->sched_before_next_call, 1,
+ REG_DEP_ANTI);
- CANT_MOVE (insn) = 1;
+ sched_analyze_insn (deps, PATTERN (insn), insn);
- if (find_reg_note (insn, REG_SETJMP, NULL))
- {
- /* This is setjmp. Assume that all registers, not just
- hard registers, may be clobbered by this call. */
- reg_pending_barrier = MOVE_BARRIER;
- }
- else
+ /* If CALL would be in a sched group, then this will violate
+ convention that sched group insns have dependencies only on the
+ previous instruction.
+
+ Of course one can say: "Hey! What about head of the sched group?"
+ And I will answer: "Basic principles (one dep per insn) are always
+ the same." */
+ gcc_assert (!SCHED_GROUP_P (insn));
+
+ /* In the absence of interprocedural alias analysis, we must flush
+ all pending reads and writes, and start new dependencies starting
+ from here. But only flush writes for constant calls (which may
+ be passed a pointer to something we haven't written yet). */
+ flush_pending_lists (deps, insn, true, ! RTL_CONST_OR_PURE_CALL_P (insn));
+
+ if (!deps->readonly)
+ {
+ /* Remember the last function call for limiting lifetimes. */
+ free_INSN_LIST_list (&deps->last_function_call);
+ deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
+
+ if (call_may_noreturn_p (insn))
{
- for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
- /* A call may read and modify global register variables. */
- if (global_regs[i])
- {
- SET_REGNO_REG_SET (reg_pending_sets, i);
- SET_REGNO_REG_SET (reg_pending_uses, i);
- }
- /* Other call-clobbered hard regs may be clobbered.
- Since we only have a choice between 'might be clobbered'
- and 'definitely not clobbered', we must include all
- partly call-clobbered registers here. */
- else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
- || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
- SET_REGNO_REG_SET (reg_pending_clobbers, i);
- /* We don't know what set of fixed registers might be used
- by the function, but it is certain that the stack pointer
- is among them, but be conservative. */
- else if (fixed_regs[i])
- SET_REGNO_REG_SET (reg_pending_uses, i);
- /* The frame pointer is normally not used by the function
- itself, but by the debugger. */
- /* ??? MIPS o32 is an exception. It uses the frame pointer
- in the macro expansion of jal but does not represent this
- fact in the call_insn rtl. */
- else if (i == FRAME_POINTER_REGNUM
- || (i == HARD_FRAME_POINTER_REGNUM
- && (! reload_completed || frame_pointer_needed)))
- SET_REGNO_REG_SET (reg_pending_uses, i);
+ /* Remember the last function call that might not always return
+ normally for limiting moves of trapping insns. */
+ free_INSN_LIST_list (&deps->last_function_call_may_noreturn);
+ deps->last_function_call_may_noreturn
+ = alloc_INSN_LIST (insn, NULL_RTX);
}
- /* For each insn which shouldn't cross a call, add a dependence
- between that insn and this call insn. */
- add_dependence_list_and_free (insn, &deps->sched_before_next_call, 1,
- REG_DEP_ANTI);
+ /* Before reload, begin a post-call group, so as to keep the
+ lifetimes of hard registers correct. */
+ if (! reload_completed)
+ deps->in_post_call_group_p = post_call;
+ }
+ }
+
+ if (sched_deps_info->use_cselib)
+ cselib_process_insn (insn);
+
+ /* EH_REGION insn notes can not appear until well after we complete
+ scheduling. */
+ if (NOTE_P (insn))
+ gcc_assert (NOTE_KIND (insn) != NOTE_INSN_EH_REGION_BEG
+ && NOTE_KIND (insn) != NOTE_INSN_EH_REGION_END);
+
+ if (sched_deps_info->finish_insn)
+ sched_deps_info->finish_insn ();
+
+ /* Fixup the dependencies in the sched group. */
+ if ((NONJUMP_INSN_P (insn) || JUMP_P (insn))
+ && SCHED_GROUP_P (insn) && !sel_sched_p ())
+ fixup_sched_groups (insn);
+}
+
+/* Initialize DEPS for the new block beginning with HEAD. */
+void
+deps_start_bb (struct deps_desc *deps, rtx head)
+{
+ gcc_assert (!deps->readonly);
+
+ /* Before reload, if the previous block ended in a call, show that
+ we are inside a post-call group, so as to keep the lifetimes of
+ hard registers correct. */
+ if (! reload_completed && !LABEL_P (head))
+ {
+ rtx insn = prev_nonnote_nondebug_insn (head);
+
+ if (insn && CALL_P (insn))
+ deps->in_post_call_group_p = post_call_initial;
+ }
+}
+
+/* Analyze every insn between HEAD and TAIL inclusive, creating backward
+ dependencies for each insn. */
+void
+sched_analyze (struct deps_desc *deps, rtx head, rtx tail)
+{
+ rtx insn;
- sched_analyze_insn (deps, PATTERN (insn), insn);
+ if (sched_deps_info->use_cselib)
+ cselib_init (CSELIB_RECORD_MEMORY);
- /* In the absence of interprocedural alias analysis, we must flush
- all pending reads and writes, and start new dependencies starting
- from here. But only flush writes for constant calls (which may
- be passed a pointer to something we haven't written yet). */
- flush_pending_lists (deps, insn, true, !CONST_OR_PURE_CALL_P (insn));
+ deps_start_bb (deps, head);
- /* Remember the last function call for limiting lifetimes. */
- free_INSN_LIST_list (&deps->last_function_call);
- deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
+ for (insn = head;; insn = NEXT_INSN (insn))
+ {
- /* Before reload, begin a post-call group, so as to keep the
- lifetimes of hard registers correct. */
- if (! reload_completed)
- deps->in_post_call_group_p = post_call;
+ if (INSN_P (insn))
+ {
+ /* And initialize deps_lists. */
+ sd_init_insn (insn);
}
- /* EH_REGION insn notes can not appear until well after we complete
- scheduling. */
- if (NOTE_P (insn))
- gcc_assert (NOTE_KIND (insn) != NOTE_INSN_EH_REGION_BEG
- && NOTE_KIND (insn) != NOTE_INSN_EH_REGION_END);
-
- if (current_sched_info->use_cselib)
- cselib_process_insn (insn);
-
- /* Now that we have completed handling INSN, check and see if it is
- a CLOBBER beginning a libcall block. If it is, record the
- end of the libcall sequence.
-
- We want to schedule libcall blocks as a unit before reload. While
- this restricts scheduling, it preserves the meaning of a libcall
- block.
-
- As a side effect, we may get better code due to decreased register
- pressure as well as less chance of a foreign insn appearing in
- a libcall block. */
- if (!reload_completed
- /* Note we may have nested libcall sequences. We only care about
- the outermost libcall sequence. */
- && deps->libcall_block_tail_insn == 0
- /* The sequence must start with a clobber of a register. */
- && NONJUMP_INSN_P (insn)
- && GET_CODE (PATTERN (insn)) == CLOBBER
- && (r0 = XEXP (PATTERN (insn), 0), REG_P (r0))
- && REG_P (XEXP (PATTERN (insn), 0))
- /* The CLOBBER must also have a REG_LIBCALL note attached. */
- && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
- && (end_seq = XEXP (link, 0)) != 0
- /* The insn referenced by the REG_LIBCALL note must be a
- simple nop copy with the same destination as the register
- mentioned in the clobber. */
- && (set = single_set (end_seq)) != 0
- && SET_DEST (set) == r0 && SET_SRC (set) == r0
- /* And finally the insn referenced by the REG_LIBCALL must
- also contain a REG_EQUAL note and a REG_RETVAL note. */
- && find_reg_note (end_seq, REG_EQUAL, NULL_RTX) != 0
- && find_reg_note (end_seq, REG_RETVAL, NULL_RTX) != 0)
- deps->libcall_block_tail_insn = XEXP (link, 0);
-
- /* If we have reached the end of a libcall block, then close the
- block. */
- if (deps->libcall_block_tail_insn == insn)
- deps->libcall_block_tail_insn = 0;
+ deps_analyze_insn (deps, insn);
if (insn == tail)
{
- if (current_sched_info->use_cselib)
+ if (sched_deps_info->use_cselib)
cselib_finish ();
return;
}
}
gcc_unreachable ();
}
-\f
-/* The following function adds forward dependence (FROM, TO) with
- given DEP_TYPE. The forward dependence should be not exist before. */
-
-void
-add_forw_dep (dep_link_t link)
+/* 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)
{
- dep_t dep = DEP_LINK_DEP (link);
- rtx to = DEP_CON (dep);
- rtx from = DEP_PRO (dep);
+ sd_iterator_def sd_it;
+ dep_t dep;
+ sd_list_types_def types;
-#ifdef ENABLE_CHECKING
- /* If add_dependence is working properly there should never
- be notes, deleted insns or duplicates in the backward
- links. Thus we need not check for them here.
-
- However, if we have enabled checking we might as well go
- ahead and verify that add_dependence worked properly. */
- gcc_assert (INSN_P (from));
- gcc_assert (!INSN_DELETED_P (from));
- if (true_dependency_cache)
+ if (resolved_p)
+ types = SD_LIST_RES_BACK;
+ else
+ types = SD_LIST_BACK;
+
+ for (sd_it = sd_iterator_start (insn, types);
+ sd_iterator_cond (&sd_it, &dep);)
{
- gcc_assert (!bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
- INSN_LUID (to)));
- bitmap_set_bit (&forward_dependency_cache[INSN_LUID (from)],
- INSN_LUID (to));
+ dep_link_t link = *sd_it.linkp;
+ dep_node_t node = DEP_LINK_NODE (link);
+ deps_list_t back_list;
+ deps_list_t forw_list;
+
+ get_back_and_forw_lists (dep, resolved_p, &back_list, &forw_list);
+ remove_from_deps_list (link, back_list);
+ delete_dep_node (node);
}
-
- gcc_assert (find_link_by_con_in_deps_list (INSN_FORW_DEPS (from), to)
- == NULL);
-#endif
-
- add_to_deps_list (DEP_NODE_FORW (DEP_LINK_NODE (link)),
- INSN_FORW_DEPS (from));
-
- INSN_DEP_COUNT (to) += 1;
}
-/* Examine insns in the range [ HEAD, TAIL ] and Use the backward
- dependences from INSN_BACK_DEPS list to build forward dependences in
- INSN_FORW_DEPS. */
-
+/* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with
+ deps_lists. */
void
-compute_forward_dependences (rtx head, rtx tail)
+sched_free_deps (rtx head, rtx tail, bool resolved_p)
{
rtx insn;
- rtx next_tail;
+ rtx next_tail = NEXT_INSN (tail);
- next_tail = NEXT_INSN (tail);
+ /* We make two passes since some insns may be scheduled before their
+ dependencies are resolved. */
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
- {
- dep_link_t link;
-
- if (! INSN_P (insn))
- continue;
-
- if (current_sched_info->flags & DO_SPECULATION)
- {
- /* We will add links, preserving order, from INSN_BACK_DEPS to
- NEW. */
- dep_link_t new = NULL;
-
- link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn));
-
- while (link != NULL)
- {
- dep_link_t next = DEP_LINK_NEXT (link);
-
- detach_dep_link (link);
- adjust_add_sorted_back_dep (insn, link, &new);
-
- link = next;
- }
-
- /* Attach NEW to be the list of backward dependencies. */
- if (new != NULL)
- {
- DEP_LINK_PREV_NEXTP (new)
- = &DEPS_LIST_FIRST (INSN_BACK_DEPS (insn));
-
- DEPS_LIST_FIRST (INSN_BACK_DEPS (insn)) = new;
- }
- }
+ if (INSN_P (insn) && INSN_LUID (insn) > 0)
+ {
+ /* Clear forward deps and leave the dep_nodes to the
+ corresponding back_deps list. */
+ if (resolved_p)
+ clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
+ else
+ clear_deps_list (INSN_FORW_DEPS (insn));
+ }
+ for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
+ if (INSN_P (insn) && INSN_LUID (insn) > 0)
+ {
+ /* Clear resolved back deps together with its dep_nodes. */
+ delete_dep_nodes_in_back_deps (insn, resolved_p);
- FOR_EACH_DEP_LINK (link, INSN_BACK_DEPS (insn))
- add_forw_dep (link);
- }
+ sd_finish_insn (insn);
+ }
}
\f
/* Initialize variables for region data dependence analysis.
- n_bbs is the number of region blocks. */
+ When LAZY_REG_LAST is true, do not allocate reg_last array
+ of struct deps_desc immediately. */
void
-init_deps (struct deps *deps)
+init_deps (struct deps_desc *deps, bool lazy_reg_last)
{
int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
deps->max_reg = max_reg;
- deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
+ if (lazy_reg_last)
+ deps->reg_last = NULL;
+ else
+ deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
INIT_REG_SET (&deps->reg_last_in_use);
- INIT_REG_SET (&deps->reg_conditional_sets);
deps->pending_read_insns = 0;
deps->pending_read_mems = 0;
deps->pending_write_insns = 0;
deps->pending_write_mems = 0;
+ deps->pending_jump_insns = 0;
deps->pending_read_list_length = 0;
deps->pending_write_list_length = 0;
deps->pending_flush_length = 0;
deps->last_pending_memory_flush = 0;
deps->last_function_call = 0;
+ deps->last_function_call_may_noreturn = 0;
deps->sched_before_next_call = 0;
+ deps->sched_before_next_jump = 0;
deps->in_post_call_group_p = not_post_call;
- deps->libcall_block_tail_insn = 0;
+ deps->last_debug_insn = 0;
+ deps->last_reg_pending_barrier = NOT_A_BARRIER;
+ deps->readonly = 0;
+}
+
+/* Init only reg_last field of DEPS, which was not allocated before as
+ we inited DEPS lazily. */
+void
+init_deps_reg_last (struct deps_desc *deps)
+{
+ gcc_assert (deps && deps->max_reg > 0);
+ gcc_assert (deps->reg_last == NULL);
+
+ deps->reg_last = XCNEWVEC (struct deps_reg, deps->max_reg);
}
+
/* Free insn lists found in DEPS. */
void
-free_deps (struct deps *deps)
+free_deps (struct deps_desc *deps)
{
unsigned i;
reg_set_iterator rsi;
+ /* We set max_reg to 0 when this context was already freed. */
+ if (deps->max_reg == 0)
+ {
+ gcc_assert (deps->reg_last == NULL);
+ return;
+ }
+ deps->max_reg = 0;
+
free_INSN_LIST_list (&deps->pending_read_insns);
free_EXPR_LIST_list (&deps->pending_read_mems);
free_INSN_LIST_list (&deps->pending_write_insns);
free_INSN_LIST_list (®_last->uses);
if (reg_last->sets)
free_INSN_LIST_list (®_last->sets);
+ if (reg_last->implicit_sets)
+ free_INSN_LIST_list (®_last->implicit_sets);
+ if (reg_last->control_uses)
+ free_INSN_LIST_list (®_last->control_uses);
if (reg_last->clobbers)
free_INSN_LIST_list (®_last->clobbers);
}
CLEAR_REG_SET (&deps->reg_last_in_use);
- CLEAR_REG_SET (&deps->reg_conditional_sets);
+ /* As we initialize reg_last lazily, it is possible that we didn't allocate
+ it at all. */
free (deps->reg_last);
+ deps->reg_last = NULL;
+
+ deps = NULL;
+}
+
+/* Remove INSN from dependence contexts DEPS. */
+void
+remove_from_deps (struct deps_desc *deps, rtx insn)
+{
+ int removed;
+ unsigned i;
+ reg_set_iterator rsi;
+
+ removed = remove_from_both_dependence_lists (insn, &deps->pending_read_insns,
+ &deps->pending_read_mems);
+ if (!DEBUG_INSN_P (insn))
+ deps->pending_read_list_length -= removed;
+ removed = remove_from_both_dependence_lists (insn, &deps->pending_write_insns,
+ &deps->pending_write_mems);
+ deps->pending_write_list_length -= removed;
+
+ removed = remove_from_dependence_list (insn, &deps->pending_jump_insns);
+ deps->pending_flush_length -= removed;
+ removed = remove_from_dependence_list (insn, &deps->last_pending_memory_flush);
+ deps->pending_flush_length -= removed;
+
+ EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
+ {
+ struct deps_reg *reg_last = &deps->reg_last[i];
+ if (reg_last->uses)
+ remove_from_dependence_list (insn, ®_last->uses);
+ if (reg_last->sets)
+ remove_from_dependence_list (insn, ®_last->sets);
+ if (reg_last->implicit_sets)
+ remove_from_dependence_list (insn, ®_last->implicit_sets);
+ if (reg_last->clobbers)
+ remove_from_dependence_list (insn, ®_last->clobbers);
+ if (!reg_last->uses && !reg_last->sets && !reg_last->implicit_sets
+ && !reg_last->clobbers)
+ CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, i);
+ }
+
+ if (CALL_P (insn))
+ {
+ remove_from_dependence_list (insn, &deps->last_function_call);
+ remove_from_dependence_list (insn,
+ &deps->last_function_call_may_noreturn);
+ }
+ remove_from_dependence_list (insn, &deps->sched_before_next_call);
}
-/* If it is profitable to use them, initialize caches for tracking
- dependency information. LUID is the number of insns to be scheduled,
- it is used in the estimate of profitability. */
+/* Init deps data vector. */
+static void
+init_deps_data_vector (void)
+{
+ int reserve = (sched_max_luid + 1
+ - VEC_length (haifa_deps_insn_data_def, h_d_i_d));
+ if (reserve > 0
+ && ! VEC_space (haifa_deps_insn_data_def, h_d_i_d, reserve))
+ VEC_safe_grow_cleared (haifa_deps_insn_data_def, heap, h_d_i_d,
+ 3 * sched_max_luid / 2);
+}
+/* If it is profitable to use them, initialize or extend (depending on
+ GLOBAL_P) dependency data. */
void
-init_dependency_caches (int luid)
+sched_deps_init (bool global_p)
{
- /* ?!? We could save some memory by computing a per-region luid mapping
- which could reduce both the number of vectors in the cache and the size
- of each vector. Instead we just avoid the cache entirely unless the
- average number of instructions in a basic block is very high. See
- the comment before the declaration of true_dependency_cache for
- what we consider "very high". */
- if (luid / n_basic_blocks > 100 * 5)
+ /* Average number of insns in the basic block.
+ '+ 1' is used to make it nonzero. */
+ int insns_in_block = sched_max_luid / n_basic_blocks + 1;
+
+ init_deps_data_vector ();
+
+ /* We use another caching mechanism for selective scheduling, so
+ we don't use this one. */
+ if (!sel_sched_p () && global_p && insns_in_block > 100 * 5)
{
+ /* ?!? We could save some memory by computing a per-region luid mapping
+ which could reduce both the number of vectors in the cache and the
+ size of each vector. Instead we just avoid the cache entirely unless
+ the average number of instructions in a basic block is very high. See
+ the comment before the declaration of true_dependency_cache for
+ what we consider "very high". */
cache_size = 0;
- extend_dependency_caches (luid, true);
+ extend_dependency_caches (sched_max_luid, true);
}
- /* Lifetime of this obstack is whole function scheduling (not single region
- scheduling) because some dependencies can be manually generated for
- outside regions. See dont_calc_deps in sched-{rgn, ebb}.c .
-
- Possible solution would be to have two obstacks:
- * the big one for regular dependencies with region scheduling lifetime,
- * and the small one for manually generated dependencies with function
- scheduling lifetime. */
- gcc_obstack_init (&deps_obstack);
+ if (global_p)
+ {
+ dl_pool = create_alloc_pool ("deps_list", sizeof (struct _deps_list),
+ /* Allocate lists for one block at a time. */
+ insns_in_block);
+ dn_pool = create_alloc_pool ("dep_node", sizeof (struct _dep_node),
+ /* Allocate nodes for one block at a time.
+ We assume that average insn has
+ 5 producers. */
+ 5 * insns_in_block);
+ }
}
+
/* Create or extend (depending on CREATE_P) dependency caches to
size N. */
void
output_dependency_cache, luid);
anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
luid);
-#ifdef ENABLE_CHECKING
- forward_dependency_cache = XRESIZEVEC (bitmap_head,
- forward_dependency_cache, luid);
-#endif
+ control_dependency_cache = XRESIZEVEC (bitmap_head, control_dependency_cache,
+ luid);
+
if (current_sched_info->flags & DO_SPECULATION)
spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
luid);
bitmap_initialize (&true_dependency_cache[i], 0);
bitmap_initialize (&output_dependency_cache[i], 0);
bitmap_initialize (&anti_dependency_cache[i], 0);
-#ifdef ENABLE_CHECKING
- bitmap_initialize (&forward_dependency_cache[i], 0);
-#endif
+ bitmap_initialize (&control_dependency_cache[i], 0);
+
if (current_sched_info->flags & DO_SPECULATION)
bitmap_initialize (&spec_dependency_cache[i], 0);
}
}
}
-/* Free the caches allocated in init_dependency_caches. */
-
+/* Finalize dependency information for the whole function. */
void
-free_dependency_caches (void)
+sched_deps_finish (void)
{
- obstack_free (&deps_obstack, NULL);
+ 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);
+
+ VEC_free (haifa_deps_insn_data_def, heap, h_d_i_d);
+ cache_size = 0;
if (true_dependency_cache)
{
bitmap_clear (&true_dependency_cache[i]);
bitmap_clear (&output_dependency_cache[i]);
bitmap_clear (&anti_dependency_cache[i]);
-#ifdef ENABLE_CHECKING
- bitmap_clear (&forward_dependency_cache[i]);
-#endif
- if (current_sched_info->flags & DO_SPECULATION)
+ bitmap_clear (&control_dependency_cache[i]);
+
+ if (sched_deps_info->generate_spec_deps)
bitmap_clear (&spec_dependency_cache[i]);
}
free (true_dependency_cache);
output_dependency_cache = NULL;
free (anti_dependency_cache);
anti_dependency_cache = NULL;
-#ifdef ENABLE_CHECKING
- free (forward_dependency_cache);
- forward_dependency_cache = NULL;
-#endif
- if (current_sched_info->flags & DO_SPECULATION)
+ free (control_dependency_cache);
+ control_dependency_cache = NULL;
+
+ if (sched_deps_info->generate_spec_deps)
{
free (spec_dependency_cache);
spec_dependency_cache = NULL;
}
+
}
}
void
init_deps_global (void)
{
+ CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
+ CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
reg_pending_sets = ALLOC_REG_SET (®_obstack);
reg_pending_clobbers = ALLOC_REG_SET (®_obstack);
reg_pending_uses = ALLOC_REG_SET (®_obstack);
+ reg_pending_control_uses = ALLOC_REG_SET (®_obstack);
reg_pending_barrier = NOT_A_BARRIER;
+
+ if (!sel_sched_p () || sched_emulate_haifa_p)
+ {
+ sched_deps_info->start_insn = haifa_start_insn;
+ sched_deps_info->finish_insn = haifa_finish_insn;
+
+ sched_deps_info->note_reg_set = haifa_note_reg_set;
+ sched_deps_info->note_reg_clobber = haifa_note_reg_clobber;
+ sched_deps_info->note_reg_use = haifa_note_reg_use;
+
+ sched_deps_info->note_mem_dep = haifa_note_mem_dep;
+ sched_deps_info->note_dep = haifa_note_dep;
+ }
}
/* Free everything used by the dependency analysis code. */
FREE_REG_SET (reg_pending_sets);
FREE_REG_SET (reg_pending_clobbers);
FREE_REG_SET (reg_pending_uses);
-}
-
-/* Insert LINK into the dependence chain pointed to by LINKP and
- maintain the sort order. */
-static void
-adjust_add_sorted_back_dep (rtx insn, dep_link_t link, dep_link_t *linkp)
-{
- gcc_assert (current_sched_info->flags & DO_SPECULATION);
-
- /* If the insn cannot move speculatively, but the link is speculative,
- make it hard dependence. */
- if (HAS_INTERNAL_DEP (insn)
- && (DEP_LINK_STATUS (link) & SPECULATIVE))
- {
- DEP_LINK_STATUS (link) &= ~SPECULATIVE;
-
- if (true_dependency_cache)
- bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (DEP_LINK_PRO (link)));
- }
-
- /* Non-speculative links go at the head of deps_list, followed by
- speculative links. */
- if (DEP_LINK_STATUS (link) & SPECULATIVE)
- while (*linkp && !(DEP_LINK_STATUS (*linkp) & SPECULATIVE))
- linkp = &DEP_LINK_NEXT (*linkp);
-
- attach_dep_link (link, linkp);
-
- if (CHECK)
- gcc_assert (deps_list_consistent_p (INSN_BACK_DEPS (insn)));
-}
-
-/* Move the dependence pointed to by LINKP to the back dependencies
- of INSN, and also add this dependence to the forward ones. All dep_links,
- except one pointed to by LINKP, must be sorted. */
-static void
-adjust_back_add_forw_dep (rtx insn, dep_link_t *linkp)
-{
- dep_link_t link;
-
- gcc_assert (current_sched_info->flags & DO_SPECULATION);
-
- link = *linkp;
- detach_dep_link (link);
-
- adjust_add_sorted_back_dep (insn, link,
- &DEPS_LIST_FIRST (INSN_BACK_DEPS (insn)));
- add_forw_dep (link);
-}
-
-/* Remove forward dependence described by L. */
-static void
-delete_forw_dep (dep_link_t l)
-{
- gcc_assert (current_sched_info->flags & DO_SPECULATION);
-
-#ifdef ENABLE_CHECKING
- if (true_dependency_cache)
- bitmap_clear_bit (&forward_dependency_cache[INSN_LUID (DEP_LINK_PRO (l))],
- INSN_LUID (DEP_LINK_CON (l)));
-#endif
-
- detach_dep_link (l);
-
- INSN_DEP_COUNT (DEP_LINK_CON (l))--;
+ FREE_REG_SET (reg_pending_control_uses);
}
/* Estimate the weakness of dependence between MEM1 and MEM2. */
-static dw_t
+dw_t
estimate_dep_weak (rtx mem1, rtx mem2)
{
rtx r1, r2;
/* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
This function can handle same INSN and ELEM (INSN == ELEM).
It is a convenience wrapper. */
-void
-add_dependence (rtx insn, rtx elem, enum reg_note dep_type)
+static void
+add_dependence_1 (rtx insn, rtx elem, enum reg_note dep_type)
{
ds_t ds;
-
+ bool internal;
+
if (dep_type == REG_DEP_TRUE)
ds = DEP_TRUE;
else if (dep_type == REG_DEP_OUTPUT)
ds = DEP_OUTPUT;
- else if (dep_type == REG_DEP_ANTI)
- ds = DEP_ANTI;
+ else if (dep_type == REG_DEP_CONTROL)
+ ds = DEP_CONTROL;
else
- gcc_unreachable ();
-
- maybe_add_or_update_back_dep_1 (insn, elem, dep_type, ds, 0, 0, 0);
-}
-
-/* Add or update backward dependence between INSN and ELEM
- with given type DEP_TYPE and dep_status DS.
- This function is a convenience wrapper. */
-enum DEPS_ADJUST_RESULT
-add_or_update_back_dep (rtx insn, rtx elem, enum reg_note dep_type, ds_t ds)
-{
- return add_or_update_back_dep_1 (insn, elem, dep_type, ds, 0, 0, 0);
-}
-
-/* Add or update both backward and forward dependencies between INSN and ELEM
- with given type DEP_TYPE and dep_status DS. */
-void
-add_or_update_back_forw_dep (rtx insn, rtx elem, enum reg_note dep_type,
- ds_t ds)
-{
- enum DEPS_ADJUST_RESULT res;
- dep_link_t *linkp;
-
- res = add_or_update_back_dep_1 (insn, elem, dep_type, ds, 0, 0, &linkp);
-
- if (res == DEP_CHANGED || res == DEP_CREATED)
{
- if (res == DEP_CHANGED)
- delete_forw_dep (DEP_NODE_FORW (DEP_LINK_NODE (*linkp)));
- else if (res == DEP_CREATED)
- linkp = &DEPS_LIST_FIRST (INSN_BACK_DEPS (insn));
-
- adjust_back_add_forw_dep (insn, linkp);
+ gcc_assert (dep_type == REG_DEP_ANTI);
+ ds = DEP_ANTI;
}
-}
-
-/* Add both backward and forward dependencies between INSN and ELEM
- with given type DEP_TYPE and dep_status DS. */
-void
-add_back_forw_dep (rtx insn, rtx elem, enum reg_note dep_type, ds_t ds)
-{
- add_back_dep (insn, elem, dep_type, ds);
- adjust_back_add_forw_dep (insn, &DEPS_LIST_FIRST (INSN_BACK_DEPS (insn)));
-
- if (CHECK)
- gcc_assert (deps_list_consistent_p (INSN_BACK_DEPS (insn)));
-}
-
-/* Remove a dependency referred to by L. */
-void
-delete_back_forw_dep (dep_link_t l)
-{
- dep_node_t n = DEP_LINK_NODE (l);
-
- gcc_assert (current_sched_info->flags & DO_SPECULATION);
-
- if (true_dependency_cache != NULL)
- {
- dep_t dep = DEP_NODE_DEP (n);
- int elem_luid = INSN_LUID (DEP_PRO (dep));
- int insn_luid = INSN_LUID (DEP_CON (dep));
- bitmap_clear_bit (&true_dependency_cache[insn_luid], elem_luid);
- bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
- bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
- bitmap_clear_bit (&spec_dependency_cache[insn_luid], elem_luid);
- }
+ /* When add_dependence is called from inside sched-deps.c, we expect
+ cur_insn to be non-null. */
+ internal = cur_insn != NULL;
+ if (internal)
+ gcc_assert (insn == cur_insn);
+ else
+ cur_insn = insn;
- delete_forw_dep (DEP_NODE_FORW (n));
- detach_dep_link (DEP_NODE_BACK (n));
+ note_dep (elem, ds);
+ if (!internal)
+ cur_insn = NULL;
}
/* Return weakness of speculative type TYPE in the dep_status DS. */
dw_t
-get_dep_weak (ds_t ds, ds_t type)
+get_dep_weak_1 (ds_t ds, ds_t type)
{
ds = ds & type;
+
switch (type)
{
case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
default: gcc_unreachable ();
}
- gcc_assert (MIN_DEP_WEAK <= ds && ds <= MAX_DEP_WEAK);
return (dw_t) ds;
}
+dw_t
+get_dep_weak (ds_t ds, ds_t type)
+{
+ dw_t dw = get_dep_weak_1 (ds, type);
+
+ gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
+ return dw;
+}
+
/* Return the dep_status, which has the same parameters as DS, except for
speculative type TYPE, that will have weakness DW. */
ds_t
return ds;
}
-/* Return the join of two dep_statuses DS1 and DS2. */
-ds_t
-ds_merge (ds_t ds1, ds_t ds2)
+/* Return the join of two dep_statuses DS1 and DS2.
+ If MAX_P is true then choose the greater probability,
+ otherwise multiply probabilities.
+ This function assumes that both DS1 and DS2 contain speculative bits. */
+static ds_t
+ds_merge_1 (ds_t ds1, ds_t ds2, bool max_p)
{
ds_t ds, t;
ds |= ds2 & t;
else if ((ds1 & t) && (ds2 & t))
{
+ dw_t dw1 = get_dep_weak (ds1, t);
+ dw_t dw2 = get_dep_weak (ds2, t);
ds_t dw;
- dw = ((ds_t) get_dep_weak (ds1, t)) * ((ds_t) get_dep_weak (ds2, t));
- dw /= MAX_DEP_WEAK;
- if (dw < MIN_DEP_WEAK)
- dw = MIN_DEP_WEAK;
+ if (!max_p)
+ {
+ dw = ((ds_t) dw1) * ((ds_t) dw2);
+ dw /= MAX_DEP_WEAK;
+ if (dw < MIN_DEP_WEAK)
+ dw = MIN_DEP_WEAK;
+ }
+ else
+ {
+ if (dw1 >= dw2)
+ dw = dw1;
+ else
+ dw = dw2;
+ }
ds = set_dep_weak (ds, t, (dw_t) dw);
}
return ds;
}
-#ifdef INSN_SCHEDULING
+/* Return the join of two dep_statuses DS1 and DS2.
+ This function assumes that both DS1 and DS2 contain speculative bits. */
+ds_t
+ds_merge (ds_t ds1, ds_t ds2)
+{
+ return ds_merge_1 (ds1, ds2, false);
+}
+
+/* Return the join of two dep_statuses DS1 and DS2. */
+ds_t
+ds_full_merge (ds_t ds, ds_t ds2, rtx mem1, rtx mem2)
+{
+ ds_t new_status = ds | ds2;
+
+ if (new_status & SPECULATIVE)
+ {
+ if ((ds && !(ds & SPECULATIVE))
+ || (ds2 && !(ds2 & SPECULATIVE)))
+ /* Then this dep can't be speculative. */
+ new_status &= ~SPECULATIVE;
+ else
+ {
+ /* Both are speculative. Merging probabilities. */
+ if (mem1)
+ {
+ dw_t dw;
+
+ dw = estimate_dep_weak (mem1, mem2);
+ ds = set_dep_weak (ds, BEGIN_DATA, dw);
+ }
+
+ if (!ds)
+ new_status = ds2;
+ else if (!ds2)
+ new_status = ds;
+ else
+ new_status = ds_merge (ds2, ds);
+ }
+ }
+
+ return new_status;
+}
+
+/* Return the join of DS1 and DS2. Use maximum instead of multiplying
+ probabilities. */
+ds_t
+ds_max_merge (ds_t ds1, ds_t ds2)
+{
+ if (ds1 == 0 && ds2 == 0)
+ return 0;
+
+ if (ds1 == 0 && ds2 != 0)
+ return ds2;
+
+ if (ds1 != 0 && ds2 == 0)
+ return ds1;
+
+ return ds_merge_1 (ds1, ds2, true);
+}
+
+/* Return the probability of speculation success for the speculation
+ status DS. */
+dw_t
+ds_weak (ds_t ds)
+{
+ ds_t res = 1, dt;
+ int n = 0;
+
+ dt = FIRST_SPEC_TYPE;
+ do
+ {
+ if (ds & dt)
+ {
+ res *= (ds_t) get_dep_weak (ds, dt);
+ n++;
+ }
+
+ if (dt == LAST_SPEC_TYPE)
+ break;
+ dt <<= SPEC_TYPE_SHIFT;
+ }
+ while (1);
+
+ gcc_assert (n);
+ while (--n)
+ res /= MAX_DEP_WEAK;
+
+ if (res < MIN_DEP_WEAK)
+ res = MIN_DEP_WEAK;
+
+ gcc_assert (res <= MAX_DEP_WEAK);
+
+ return (dw_t) res;
+}
+
+/* Return a dep status that contains all speculation types of DS. */
+ds_t
+ds_get_speculation_types (ds_t ds)
+{
+ if (ds & BEGIN_DATA)
+ ds |= BEGIN_DATA;
+ if (ds & BE_IN_DATA)
+ ds |= BE_IN_DATA;
+ if (ds & BEGIN_CONTROL)
+ ds |= BEGIN_CONTROL;
+ if (ds & BE_IN_CONTROL)
+ ds |= BE_IN_CONTROL;
+
+ return ds & SPECULATIVE;
+}
+
+/* Return a dep status that contains maximal weakness for each speculation
+ type present in DS. */
+ds_t
+ds_get_max_dep_weak (ds_t ds)
+{
+ if (ds & BEGIN_DATA)
+ ds = set_dep_weak (ds, BEGIN_DATA, MAX_DEP_WEAK);
+ if (ds & BE_IN_DATA)
+ ds = set_dep_weak (ds, BE_IN_DATA, MAX_DEP_WEAK);
+ if (ds & BEGIN_CONTROL)
+ ds = set_dep_weak (ds, BEGIN_CONTROL, MAX_DEP_WEAK);
+ if (ds & BE_IN_CONTROL)
+ ds = set_dep_weak (ds, BE_IN_CONTROL, MAX_DEP_WEAK);
+
+ return ds;
+}
+
+/* Dump information about the dependence status S. */
+static void
+dump_ds (FILE *f, ds_t s)
+{
+ fprintf (f, "{");
+
+ if (s & BEGIN_DATA)
+ fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak_1 (s, BEGIN_DATA));
+ if (s & BE_IN_DATA)
+ fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak_1 (s, BE_IN_DATA));
+ if (s & BEGIN_CONTROL)
+ fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s, BEGIN_CONTROL));
+ if (s & BE_IN_CONTROL)
+ fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s, BE_IN_CONTROL));
+
+ if (s & HARD_DEP)
+ fprintf (f, "HARD_DEP; ");
+
+ if (s & DEP_TRUE)
+ fprintf (f, "DEP_TRUE; ");
+ if (s & DEP_OUTPUT)
+ fprintf (f, "DEP_OUTPUT; ");
+ if (s & DEP_ANTI)
+ fprintf (f, "DEP_ANTI; ");
+ if (s & DEP_CONTROL)
+ fprintf (f, "DEP_CONTROL; ");
+
+ fprintf (f, "}");
+}
+
+DEBUG_FUNCTION void
+debug_ds (ds_t s)
+{
+ dump_ds (stderr, s);
+ fprintf (stderr, "\n");
+}
+
#ifdef ENABLE_CHECKING
/* Verify that dependence type and status are consistent.
If RELAXED_P is true, then skip dep_weakness checks. */
static void
-check_dep_status (enum reg_note dt, ds_t ds, bool relaxed_p)
+check_dep (dep_t dep, bool relaxed_p)
{
+ enum reg_note dt = DEP_TYPE (dep);
+ ds_t ds = DEP_STATUS (dep);
+
+ gcc_assert (DEP_PRO (dep) != DEP_CON (dep));
+
+ if (!(current_sched_info->flags & USE_DEPS_LIST))
+ {
+ gcc_assert (ds == 0);
+ return;
+ }
+
/* Check that dependence type contains the same bits as the status. */
if (dt == REG_DEP_TRUE)
gcc_assert (ds & DEP_TRUE);
else if (dt == REG_DEP_OUTPUT)
gcc_assert ((ds & DEP_OUTPUT)
- && !(ds & DEP_TRUE));
- else
- gcc_assert ((dt == REG_DEP_ANTI)
- && (ds & DEP_ANTI)
+ && !(ds & DEP_TRUE));
+ else if (dt == REG_DEP_ANTI)
+ gcc_assert ((ds & DEP_ANTI)
&& !(ds & (DEP_OUTPUT | DEP_TRUE)));
+ else
+ gcc_assert (dt == REG_DEP_CONTROL
+ && (ds & DEP_CONTROL)
+ && !(ds & (DEP_OUTPUT | DEP_ANTI | DEP_TRUE)));
/* HARD_DEP can not appear in dep_status of a link. */
- gcc_assert (!(ds & HARD_DEP));
+ gcc_assert (!(ds & HARD_DEP));
/* Check that dependence status is set correctly when speculation is not
supported. */
- if (!(current_sched_info->flags & DO_SPECULATION))
+ if (!sched_deps_info->generate_spec_deps)
gcc_assert (!(ds & SPECULATIVE));
else if (ds & SPECULATIVE)
{
/* Subsequent speculations should resolve true dependencies. */
gcc_assert ((ds & DEP_TYPES) == DEP_TRUE);
}
-
- /* Check that true and anti dependencies can't have other speculative
+
+ /* Check that true and anti dependencies can't have other speculative
statuses. */
if (ds & DEP_TRUE)
gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC));
gcc_assert (ds & BEGIN_CONTROL);
}
}
-#endif
-#endif
+#endif /* ENABLE_CHECKING */
+
+#endif /* INSN_SCHEDULING */