/* 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 Free Software Foundation, Inc.
+ 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
+ Free Software Foundation, Inc.
Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
and currently maintained by, Jim Wilson (wilson@cygnus.com)
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
\f
#include "config.h"
#include "system.h"
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 *anti_dependency_cache;
static bitmap_head *output_dependency_cache;
+static bitmap_head *anti_dependency_cache;
+static bitmap_head *spec_dependency_cache;
static int cache_size;
/* To speed up checking consistency of formed forward insn
#endif
static int deps_may_trap_p (rtx);
-static void add_dependence_list (rtx, rtx, enum reg_note);
-static void add_dependence_list_and_free (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 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, rtx);
+static void sched_analyze_insn (struct deps *, rtx, rtx);
static rtx sched_get_condition (rtx);
static int conditions_mutex_p (rtx, rtx);
+
+static enum DEPS_ADJUST_RESULT maybe_add_or_update_back_dep_1 (rtx, rtx,
+ enum reg_note, ds_t, rtx, rtx, rtx **);
+static enum DEPS_ADJUST_RESULT add_or_update_back_dep_1 (rtx, rtx,
+ enum reg_note, ds_t, rtx, rtx, rtx **);
+static void add_back_dep (rtx, rtx, enum reg_note, ds_t);
+
+static void adjust_add_sorted_back_dep (rtx, rtx, rtx *);
+static void adjust_back_add_forw_dep (rtx, rtx *);
+static void delete_forw_dep (rtx, rtx);
+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
+#endif
\f
/* Return nonzero if a load of the memory reference MEM can cause a trap. */
return 0;
src = SET_SRC (pc_set (insn));
-#if 0
- /* The previous code here was completely invalid and could never extract
- the condition from a jump. This code does the correct thing, but that
- triggers latent bugs later in the scheduler on ports with conditional
- execution. So this is disabled for now. */
+
if (XEXP (src, 2) == pc_rtx)
return XEXP (src, 0);
else if (XEXP (src, 1) == pc_rtx)
return gen_rtx_fmt_ee (revcode, GET_MODE (cond), XEXP (cond, 0),
XEXP (cond, 1));
}
-#endif
return 0;
}
+\f
/* Return nonzero if conditions COND1 and COND2 can never be both true. */
static int
return 1;
return 0;
}
-\f
-/* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
- LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the
- type of dependence that this link represents. The function returns
- nonzero if a new entry has been added to insn's LOG_LINK. */
-int
-add_dependence (rtx insn, rtx elem, enum reg_note dep_type)
+/* 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)
{
- rtx link;
- int present_p;
rtx cond1, cond2;
- /* Don't depend an insn on itself. */
- if (insn == elem)
- return 0;
-
- /* We can get a dependency on deleted insns due to optimizations in
- the register allocation and reloading or due to splitting. Any
- such dependency is useless and can be ignored. */
- if (NOTE_P (elem))
- return 0;
-
/* flow.c doesn't handle conditional lifetimes entirely correctly;
calls mess up the conditional lifetimes. */
- /* ??? add_dependence is the wrong place to be eliding dependencies,
- as that forgets that the condition expressions themselves may
- be dependent. */
- if (!CALL_P (insn) && !CALL_P (elem))
+ if (!CALL_P (insn1) && !CALL_P (insn2))
{
- cond1 = sched_get_condition (insn);
- cond2 = sched_get_condition (elem);
+ cond1 = sched_get_condition (insn1);
+ cond2 = sched_get_condition (insn2);
if (cond1 && cond2
&& conditions_mutex_p (cond1, cond2)
/* Make sure first instruction doesn't affect condition of second
instruction if switched. */
- && !modified_in_p (cond1, elem)
+ && !modified_in_p (cond1, insn2)
/* Make sure second instruction doesn't affect condition of first
instruction if switched. */
- && !modified_in_p (cond2, insn))
- return 0;
+ && !modified_in_p (cond2, insn1))
+ return true;
}
+ return false;
+}
+\f
+/* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
+ LOG_LINKS of 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 LOG_LINK.
+ 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,
+ rtx **changed_linkpp)
+{
+ gcc_assert (INSN_P (insn) && INSN_P (elem));
- present_p = 1;
+ /* Don't depend an insn on itself. */
+ if (insn == elem)
+ {
#ifdef INSN_SCHEDULING
- /* ??? No good way to tell from here whether we're doing interblock
- scheduling. Possibly add another callback. */
-#if 0
- /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
- No need for interblock dependences with calls, since
- calls are not moved between blocks. Note: the edge where
- elem is a CALL is still required. */
- if (CALL_P (insn)
- && (INSN_BB (elem) != INSN_BB (insn)))
- return 0;
+ 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;
+ }
+
+ return add_or_update_back_dep_1 (insn, elem, dep_type,
+ ds, mem1, mem2, changed_linkpp);
+}
+
+/* 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,
+ rtx **changed_linkpp ATTRIBUTE_UNUSED)
+{
+ bool maybe_present_p = true, present_p = false;
+
+ gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
+
+#ifdef INSN_SCHEDULING
+
+#ifdef ENABLE_CHECKING
+ check_dep_status (dep_type, ds, mem1 != NULL);
#endif
/* If we already have a dependency for ELEM, then we do not need to
dramatically for some code. */
if (true_dependency_cache != NULL)
{
- enum reg_note present_dep_type = 0;
-
- gcc_assert (anti_dependency_cache);
+ enum reg_note present_dep_type;
+
gcc_assert (output_dependency_cache);
- if (bitmap_bit_p (&true_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem)))
- /* Do nothing (present_set_type is already 0). */
- ;
- else if (bitmap_bit_p (&anti_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem)))
- present_dep_type = REG_DEP_ANTI;
- else if (bitmap_bit_p (&output_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem)))
- present_dep_type = REG_DEP_OUTPUT;
+ 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;
+
+ if (maybe_present_p)
+ {
+ if ((int) dep_type >= (int) present_dep_type)
+ return DEP_PRESENT;
+
+ present_p = true;
+ }
+ }
else
- present_p = 0;
- if (present_p && (int) dep_type >= (int) present_dep_type)
- return 0;
+ {
+ 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;
+ }
}
#endif
/* Check that we don't already have this dependence. */
- if (present_p)
- for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
- if (XEXP (link, 0) == elem)
- {
+ if (maybe_present_p)
+ {
+ rtx *linkp;
+
+ for (linkp = &LOG_LINKS (insn); *linkp; linkp = &XEXP (*linkp, 1))
+ {
+ rtx link = *linkp;
+
+ gcc_assert (true_dependency_cache == 0 || present_p);
+
+ if (XEXP (link, 0) == elem)
+ {
+ enum DEPS_ADJUST_RESULT changed_p = DEP_PRESENT;
+
#ifdef INSN_SCHEDULING
- /* Clear corresponding cache entry because type of the link
- may be changed. */
- if (true_dependency_cache != NULL)
- {
- enum reg_note kind = REG_NOTE_KIND (link);
- switch (kind)
+ if (current_sched_info->flags & USE_DEPS_LIST)
+ {
+ ds_t new_status = ds | DEP_STATUS (link);
+
+ 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);
+ }
+ }
+
+ 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 = REG_NOTE_KIND (link);
+
+ 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 ();
+ }
+ }
+
+ if ((current_sched_info->flags & USE_DEPS_LIST)
+ && DEP_STATUS (link) != ds)
{
- case REG_DEP_ANTI:
- bitmap_clear_bit (&anti_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem));
- break;
- case REG_DEP_OUTPUT:
- gcc_assert (output_dependency_cache);
- bitmap_clear_bit (&output_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem));
- break;
- default:
- gcc_unreachable ();
+ DEP_STATUS (link) = ds;
+ changed_p = DEP_CHANGED;
}
- }
#endif
- /* 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) REG_NOTE_KIND (link))
- PUT_REG_NOTE_KIND (link, dep_type);
+ /* 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) REG_NOTE_KIND (link))
+ {
+ PUT_REG_NOTE_KIND (link, dep_type);
+ changed_p = DEP_CHANGED;
+ }
#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 ((int) REG_NOTE_KIND (link) == 0)
- bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem));
- else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
- bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem));
- else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
- bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem));
- }
+ /* 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 (REG_NOTE_KIND (link) == REG_DEP_TRUE)
+ bitmap_set_bit (&true_dependency_cache
+ [INSN_LUID (insn)], INSN_LUID (elem));
+ else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
+ bitmap_set_bit (&output_dependency_cache
+ [INSN_LUID (insn)], INSN_LUID (elem));
+ else if (REG_NOTE_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 0;
- }
- /* Might want to check one level of transitivity to save conses. */
+ return changed_p;
+ }
+ }
+ /* We didn't find a dep. It shouldn't be present in the cache. */
+ gcc_assert (!present_p);
+ }
- link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
- LOG_LINKS (insn) = link;
+ /* 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. */
- /* Insn dependency, not data dependency. */
- PUT_REG_NOTE_KIND (link, dep_type);
+ if (mem1)
+ {
+ gcc_assert (current_sched_info->flags & DO_SPECULATION);
+ ds = set_dep_weak (ds, BEGIN_DATA, estimate_dep_weak (mem1, mem2));
+ }
+
+ 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)
+{
+ gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
+ if (current_sched_info->flags & USE_DEPS_LIST)
+ LOG_LINKS (insn) = alloc_DEPS_LIST (elem, LOG_LINKS (insn), ds);
+ else
+ LOG_LINKS (insn) = alloc_INSN_LIST (elem, LOG_LINKS (insn));
+
+ /* Insn dependency, not data dependency. */
+ PUT_REG_NOTE_KIND (LOG_LINKS (insn), dep_type);
+
#ifdef INSN_SCHEDULING
+#ifdef ENABLE_CHECKING
+ check_dep_status (dep_type, ds, false);
+#endif
+
/* 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 ((int) dep_type == 0)
- bitmap_set_bit (&true_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 (dep_type == REG_DEP_OUTPUT)
- bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
+ 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 (current_sched_info->flags & DO_SPECULATION);
+ bitmap_set_bit (&spec_dependency_cache[INSN_LUID (insn)],
+ INSN_LUID (elem));
+ }
+ }
}
#endif
- return 1;
}
/* A convenience wrapper to operate on an entire list. */
static void
-add_dependence_list (rtx insn, rtx list, enum reg_note dep_type)
+add_dependence_list (rtx insn, rtx list, int uncond, enum reg_note dep_type)
{
for (; list; list = XEXP (list, 1))
- add_dependence (insn, XEXP (list, 0), dep_type);
+ {
+ 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. */
static void
-add_dependence_list_and_free (rtx insn, rtx *listp, enum reg_note dep_type)
+add_dependence_list_and_free (rtx insn, rtx *listp, int uncond,
+ enum reg_note dep_type)
{
rtx list, next;
for (list = *listp, *listp = NULL; list ; list = next)
{
next = XEXP (list, 1);
- add_dependence (insn, XEXP (list, 0), dep_type);
+ if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
+ add_dependence (insn, XEXP (list, 0), dep_type);
free_INSN_LIST_node (list);
}
}
if (true_dependency_cache != NULL)
{
bitmap_clear (&true_dependency_cache[INSN_LUID (insn)]);
- bitmap_clear (&anti_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
- free_INSN_LIST_list (&LOG_LINKS (insn));
+ if (!(current_sched_info->flags & USE_DEPS_LIST))
+ /* In this case LOG_LINKS are formed from the DEPS_LISTs,
+ not the INSN_LISTs. */
+ free_INSN_LIST_list (&LOG_LINKS (insn));
+ else
+ free_DEPS_LIST_list (&LOG_LINKS (insn));
}
/* All insns in a scheduling group except the first should only have
static void
fixup_sched_groups (rtx insn)
{
- rtx link;
+ rtx link, prev_nonnote;
for (link = LOG_LINKS (insn); link ; link = XEXP (link, 1))
{
if (XEXP (link, 0) == i)
goto next_link;
} while (SCHED_GROUP_P (i));
- add_dependence (i, XEXP (link, 0), REG_NOTE_KIND (link));
+ if (! sched_insns_conditions_mutex_p (i, XEXP (link, 0)))
+ add_dependence (i, XEXP (link, 0), REG_NOTE_KIND (link));
next_link:;
}
delete_all_dependences (insn);
- if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote_insn (insn)))
- add_dependence (insn, prev_nonnote_insn (insn), REG_DEP_ANTI);
+ 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);
}
\f
/* Process an insn's memory dependencies. There are four kinds of
(0) read dependence: read follows read
(1) true dependence: read follows write
- (2) anti dependence: write follows read
- (3) output dependence: write 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. */
{
if (for_write)
{
- add_dependence_list_and_free (insn, &deps->pending_read_insns,
+ add_dependence_list_and_free (insn, &deps->pending_read_insns, 1,
REG_DEP_ANTI);
free_EXPR_LIST_list (&deps->pending_read_mems);
}
- add_dependence_list_and_free (insn, &deps->pending_write_insns,
+ 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_lists_length = 0;
- add_dependence_list_and_free (insn, &deps->last_pending_memory_flush,
+ 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;
}
\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,
+ enum rtx_code ref, rtx insn)
+{
+ /* 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)
+ {
+ int i = hard_regno_nregs[regno][mode];
+ if (ref == SET)
+ {
+ while (--i >= 0)
+ SET_REGNO_REG_SET (reg_pending_sets, regno + i);
+ }
+ else if (ref == USE)
+ {
+ while (--i >= 0)
+ SET_REGNO_REG_SET (reg_pending_uses, regno + i);
+ }
+ else
+ {
+ while (--i >= 0)
+ SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
+ }
+ }
+
+ /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
+ it does not reload. Ignore these as they have served their
+ purpose already. */
+ else if (regno >= deps->max_reg)
+ {
+ enum rtx_code code = GET_CODE (PATTERN (insn));
+ gcc_assert (code == USE || code == CLOBBER);
+ }
+
+ else
+ {
+ if (ref == SET)
+ SET_REGNO_REG_SET (reg_pending_sets, regno);
+ else if (ref == USE)
+ SET_REGNO_REG_SET (reg_pending_uses, regno);
+ else
+ SET_REGNO_REG_SET (reg_pending_clobbers, regno);
+
+ /* Pseudos that are REG_EQUIV to something may be replaced
+ by that during reloading. We need only add dependencies for
+ the address in the REG_EQUIV note. */
+ if (!reload_completed && get_reg_known_equiv_p (regno))
+ {
+ rtx t = get_reg_known_value (regno);
+ if (MEM_P (t))
+ sched_analyze_2 (deps, XEXP (t, 0), insn);
+ }
+
+ /* Don't let it cross a call after scheduling if it doesn't
+ already cross one. */
+ if (REG_N_CALLS_CROSSED (regno) == 0)
+ {
+ if (ref == USE)
+ deps->sched_before_next_call
+ = alloc_INSN_LIST (insn, deps->sched_before_next_call);
+ else
+ add_dependence_list (insn, deps->last_function_call, 1,
+ REG_DEP_ANTI);
+ }
+ }
+}
+
/* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
rtx, X, creating all dependencies generated by the write to the
destination of X, and reads of everything mentioned. */
static void
sched_analyze_1 (struct deps *deps, rtx x, rtx insn)
{
- int regno;
rtx dest = XEXP (x, 0);
enum rtx_code code = GET_CODE (x);
{
if (GET_CODE (dest) == STRICT_LOW_PART
|| GET_CODE (dest) == ZERO_EXTRACT
- || read_modify_subreg_p (dest))
+ || df_read_modify_subreg_p (dest))
{
/* These both read and modify the result. We must handle
them as writes to get proper dependencies for following
if (REG_P (dest))
{
- regno = REGNO (dest);
+ int regno = REGNO (dest);
+ enum machine_mode mode = GET_MODE (dest);
- /* 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)
- {
- int i = hard_regno_nregs[regno][GET_MODE (dest)];
- if (code == SET)
- {
- while (--i >= 0)
- SET_REGNO_REG_SET (reg_pending_sets, regno + i);
- }
- else
- {
- while (--i >= 0)
- SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
- }
- }
- /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
- it does not reload. Ignore these as they have served their
- purpose already. */
- else if (regno >= deps->max_reg)
- {
- gcc_assert (GET_CODE (PATTERN (insn)) == USE
- || GET_CODE (PATTERN (insn)) == CLOBBER);
- }
- else
- {
- if (code == SET)
- SET_REGNO_REG_SET (reg_pending_sets, regno);
- else
- SET_REGNO_REG_SET (reg_pending_clobbers, regno);
+ sched_analyze_reg (deps, regno, mode, code, insn);
- /* Pseudos that are REG_EQUIV to something may be replaced
- by that during reloading. We need only add dependencies for
- the address in the REG_EQUIV note. */
- if (!reload_completed && get_reg_known_equiv_p (regno))
- {
- rtx t = get_reg_known_value (regno);
- if (MEM_P (t))
- sched_analyze_2 (deps, XEXP (t, 0), insn);
- }
-
- /* Don't let it cross a call after scheduling if it doesn't
- already cross one. */
- if (REG_N_CALLS_CROSSED (regno) == 0)
- add_dependence_list (insn, deps->last_function_call, REG_DEP_ANTI);
+#ifdef STACK_REGS
+ /* Treat all writes to a stack register as modifying the TOS. */
+ if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
+ {
+ /* 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);
}
+#endif
}
else if (MEM_P (dest))
{
pending_mem = deps->pending_read_mems;
while (pending)
{
- if (anti_dependence (XEXP (pending_mem, 0), t))
+ 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);
pending = XEXP (pending, 1);
pending_mem = deps->pending_write_mems;
while (pending)
{
- if (output_dependence (XEXP (pending_mem, 0), t))
+ 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);
pending = XEXP (pending, 1);
pending_mem = XEXP (pending_mem, 1);
}
- add_dependence_list (insn, deps->last_pending_memory_flush,
+ add_dependence_list (insn, deps->last_pending_memory_flush, 1,
REG_DEP_ANTI);
add_insn_mem_dependence (deps, &deps->pending_write_insns,
case REG:
{
int regno = REGNO (x);
- if (regno < FIRST_PSEUDO_REGISTER)
- {
- int i = hard_regno_nregs[regno][GET_MODE (x)];
- while (--i >= 0)
- SET_REGNO_REG_SET (reg_pending_uses, regno + i);
- }
- /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
- it does not reload. Ignore these as they have served their
- purpose already. */
- else if (regno >= deps->max_reg)
- {
- gcc_assert (GET_CODE (PATTERN (insn)) == USE
- || GET_CODE (PATTERN (insn)) == CLOBBER);
- }
- else
- {
- SET_REGNO_REG_SET (reg_pending_uses, regno);
-
- /* Pseudos that are REG_EQUIV to something may be replaced
- by that during reloading. We need only add dependencies for
- the address in the REG_EQUIV note. */
- if (!reload_completed && get_reg_known_equiv_p (regno))
- {
- rtx t = get_reg_known_value (regno);
- if (MEM_P (t))
- sched_analyze_2 (deps, XEXP (t, 0), insn);
- }
-
- /* If the register does not already cross any calls, then add this
- insn to the sched_before_next_call list so that it will still
- not cross calls after scheduling. */
- if (REG_N_CALLS_CROSSED (regno) == 0)
- deps->sched_before_next_call
- = alloc_INSN_LIST (insn, deps->sched_before_next_call);
- }
+ enum machine_mode mode = GET_MODE (x);
+
+ sched_analyze_reg (deps, regno, mode, USE, insn);
+
+#ifdef STACK_REGS
+ /* Treat all reads of a stack register as modifying the TOS. */
+ if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
+ {
+ /* Avoid analyzing the same register twice. */
+ if (regno != FIRST_STACK_REG)
+ sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
+ sched_analyze_reg (deps, FIRST_STACK_REG, mode, SET, insn);
+ }
+#endif
return;
}
pending_mem = deps->pending_read_mems;
while (pending)
{
- if (read_dependence (XEXP (pending_mem, 0), t))
+ 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);
pending = XEXP (pending, 1);
while (pending)
{
if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
- t, rtx_varies_p))
- add_dependence (insn, XEXP (pending, 0), 0);
+ 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);
}
for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
- if (!JUMP_P (XEXP (u, 0))
- || deps_may_trap_p (x))
+ 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
/* Analyze an INSN with pattern X to find all dependencies. */
static void
-sched_analyze_insn (struct deps *deps, rtx x, rtx insn, rtx loop_notes)
+sched_analyze_insn (struct deps *deps, rtx x, rtx insn)
{
RTX_CODE code = GET_CODE (x);
rtx link;
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, REG_DEP_OUTPUT);
+ add_dependence_list (insn, deps->last_function_call, 1, REG_DEP_OUTPUT);
}
else if (code == PARALLEL)
{
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, REG_DEP_ANTI);
- add_dependence_list (insn, reg_last->clobbers, REG_DEP_ANTI);
+ 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);
}
pending_mem = deps->pending_write_mems;
while (pending)
{
- add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
+ if (! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
+ add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
pending = XEXP (pending, 1);
pending_mem = XEXP (pending_mem, 1);
}
pending_mem = deps->pending_read_mems;
while (pending)
{
- if (MEM_VOLATILE_P (XEXP (pending_mem, 0)))
+ if (MEM_VOLATILE_P (XEXP (pending_mem, 0))
+ && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
pending = XEXP (pending, 1);
pending_mem = XEXP (pending_mem, 1);
}
- add_dependence_list (insn, deps->last_pending_memory_flush,
+ add_dependence_list (insn, deps->last_pending_memory_flush, 1,
REG_DEP_ANTI);
}
}
- /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
- block, then we must be sure that no instructions are scheduled across it.
- Otherwise, the reg_n_refs info (which depends on loop_depth) would
- become incorrect. */
- if (loop_notes)
- {
- rtx link;
-
- /* Update loop_notes with any notes from this insn. */
- link = loop_notes;
- while (XEXP (link, 1))
- {
- gcc_assert (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG
- || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END);
-
- reg_pending_barrier = MOVE_BARRIER;
- link = XEXP (link, 1);
- }
- XEXP (link, 1) = REG_NOTES (insn);
- REG_NOTES (insn) = loop_notes;
- }
-
/* If this instruction can throw an exception, then moving it changes
where block boundaries fall. This is mighty confusing elsewhere.
Therefore, prevent such an instruction from being moved. */
{
/* In the case of barrier the most added dependencies are not
real, so we use anti-dependence here. */
- if (GET_CODE (PATTERN (insn)) == COND_EXEC)
+ if (sched_get_condition (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, REG_DEP_ANTI);
+ add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
add_dependence_list
- (insn, reg_last->sets,
- reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
+ (insn, reg_last->sets, 0,
+ reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
add_dependence_list
- (insn, reg_last->clobbers,
- reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
+ (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 (insn, ®_last->uses,
+ add_dependence_list_and_free (insn, ®_last->uses, 0,
REG_DEP_ANTI);
add_dependence_list_and_free
- (insn, ®_last->sets,
- reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
+ (insn, ®_last->sets, 0,
+ reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
add_dependence_list_and_free
- (insn, ®_last->clobbers,
- reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
+ (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;
}
{
/* If the current insn is conditional, we can't free any
of the lists. */
- if (GET_CODE (PATTERN (insn)) == COND_EXEC)
+ if (sched_get_condition (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);
- add_dependence_list (insn, reg_last->clobbers, 0);
+ 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, REG_DEP_OUTPUT);
- add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
+ add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
+ 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++;
}
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, REG_DEP_OUTPUT);
- add_dependence_list (insn, reg_last->clobbers, REG_DEP_OUTPUT);
- add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
+ add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
+ 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);
}
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);
- add_dependence_list (insn, reg_last->clobbers, 0);
+ 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);
}
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,
+ add_dependence_list_and_free (insn, ®_last->sets, 0,
REG_DEP_OUTPUT);
- add_dependence_list_and_free (insn, ®_last->uses,
+ add_dependence_list_and_free (insn, ®_last->uses, 0,
REG_DEP_ANTI);
- add_dependence_list_and_free (insn, ®_last->clobbers,
+ add_dependence_list_and_free (insn, ®_last->clobbers, 0,
REG_DEP_OUTPUT);
reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
reg_last->clobbers_length = 0;
}
else
{
- add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
- add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
+ add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
+ add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
}
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,
+ add_dependence_list_and_free (insn, ®_last->sets, 0,
REG_DEP_OUTPUT);
- add_dependence_list_and_free (insn, ®_last->clobbers,
+ add_dependence_list_and_free (insn, ®_last->clobbers, 0,
REG_DEP_OUTPUT);
- add_dependence_list_and_free (insn, ®_last->uses,
+ add_dependence_list_and_free (insn, ®_last->uses, 0,
REG_DEP_ANTI);
reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
reg_last->uses_length = 0;
sched_analyze (struct deps *deps, rtx head, rtx tail)
{
rtx insn;
- rtx loop_notes = 0;
if (current_sched_info->use_cselib)
cselib_init (true);
deps->last_pending_memory_flush
= alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
}
- sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
- loop_notes = 0;
+ sched_analyze_insn (deps, PATTERN (insn), insn);
}
else if (CALL_P (insn))
{
/* 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,
+ add_dependence_list_and_free (insn, &deps->sched_before_next_call, 1,
REG_DEP_ANTI);
- sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
- loop_notes = 0;
+ sched_analyze_insn (deps, PATTERN (insn), insn);
/* In the absence of interprocedural alias analysis, we must flush
all pending reads and writes, and start new dependencies starting
gcc_assert (NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END);
- /* See comments on reemit_notes as to why we do this.
- ??? Actually, the reemit_notes just say what is done, not why. */
-
- if (NOTE_P (insn)
- && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
- || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END))
- {
- loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
- GEN_INT (NOTE_LINE_NUMBER (insn)),
- loop_notes);
- CONST_OR_PURE_CALL_P (loop_notes) = CONST_OR_PURE_CALL_P (insn);
- }
-
if (current_sched_info->use_cselib)
cselib_process_insn (insn);
given DEP_TYPE. The forward dependence should be not exist before. */
void
-add_forward_dependence (rtx from, rtx to, enum reg_note dep_type)
+add_forw_dep (rtx to, rtx link)
{
- rtx new_link;
+ rtx new_link, from;
+
+ from = XEXP (link, 0);
#ifdef ENABLE_CHECKING
/* If add_dependence is working properly there should never
However, if we have enabled checking we might as well go
ahead and verify that add_dependence worked properly. */
- gcc_assert (!NOTE_P (from));
+ gcc_assert (INSN_P (from));
gcc_assert (!INSN_DELETED_P (from));
- if (forward_dependency_cache)
- gcc_assert (!bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
- INSN_LUID (to)));
+ if (true_dependency_cache)
+ {
+ 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));
+ }
else
gcc_assert (!find_insn_list (to, INSN_DEPEND (from)));
-
- /* ??? If bitmap_bit_p is a predicate, what is this supposed to do? */
- if (forward_dependency_cache != NULL)
- bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
- INSN_LUID (to));
#endif
- new_link = alloc_INSN_LIST (to, INSN_DEPEND (from));
+ if (!(current_sched_info->flags & USE_DEPS_LIST))
+ new_link = alloc_INSN_LIST (to, INSN_DEPEND (from));
+ else
+ new_link = alloc_DEPS_LIST (to, INSN_DEPEND (from), DEP_STATUS (link));
- PUT_REG_NOTE_KIND (new_link, dep_type);
+ PUT_REG_NOTE_KIND (new_link, REG_NOTE_KIND (link));
INSN_DEPEND (from) = new_link;
INSN_DEP_COUNT (to) += 1;
void
compute_forward_dependences (rtx head, rtx tail)
{
- rtx insn, link;
+ rtx insn;
rtx next_tail;
next_tail = NEXT_INSN (tail);
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
{
+ rtx link;
+
if (! INSN_P (insn))
continue;
+
+ if (current_sched_info->flags & DO_SPECULATION)
+ {
+ rtx new = 0, link, next;
+
+ for (link = LOG_LINKS (insn); link; link = next)
+ {
+ next = XEXP (link, 1);
+ adjust_add_sorted_back_dep (insn, link, &new);
+ }
+
+ LOG_LINKS (insn) = new;
+ }
for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
- add_forward_dependence (XEXP (link, 0), insn, REG_NOTE_KIND (link));
+ add_forw_dep (insn, link);
}
}
\f
int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
deps->max_reg = max_reg;
- deps->reg_last = xcalloc (max_reg, sizeof (struct deps_reg));
+ deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
INIT_REG_SET (&deps->reg_last_in_use);
INIT_REG_SET (&deps->reg_conditional_sets);
what we consider "very high". */
if (luid / n_basic_blocks > 100 * 5)
{
- int i;
- true_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
- anti_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
- output_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
+ cache_size = 0;
+ extend_dependency_caches (luid, true);
+ }
+}
+
+/* Create or extend (depending on CREATE_P) dependency caches to
+ size N. */
+void
+extend_dependency_caches (int n, bool create_p)
+{
+ if (create_p || true_dependency_cache)
+ {
+ int i, luid = cache_size + n;
+
+ true_dependency_cache = XRESIZEVEC (bitmap_head, true_dependency_cache,
+ luid);
+ output_dependency_cache = XRESIZEVEC (bitmap_head,
+ output_dependency_cache, luid);
+ anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
+ luid);
#ifdef ENABLE_CHECKING
- forward_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
+ forward_dependency_cache = XRESIZEVEC (bitmap_head,
+ forward_dependency_cache, luid);
#endif
- for (i = 0; i < luid; i++)
+ if (current_sched_info->flags & DO_SPECULATION)
+ spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
+ luid);
+
+ for (i = cache_size; i < luid; i++)
{
bitmap_initialize (&true_dependency_cache[i], 0);
- bitmap_initialize (&anti_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
+ if (current_sched_info->flags & DO_SPECULATION)
+ bitmap_initialize (&spec_dependency_cache[i], 0);
}
cache_size = luid;
}
for (i = 0; i < cache_size; i++)
{
bitmap_clear (&true_dependency_cache[i]);
- bitmap_clear (&anti_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 (&spec_dependency_cache[i]);
}
free (true_dependency_cache);
true_dependency_cache = NULL;
- free (anti_dependency_cache);
- anti_dependency_cache = NULL;
free (output_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 (spec_dependency_cache);
+ spec_dependency_cache = NULL;
+ }
}
}
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, rtx link, rtx *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_STATUS (link) & SPECULATIVE))
+ {
+ DEP_STATUS (link) &= ~SPECULATIVE;
+
+ if (true_dependency_cache)
+ bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
+ INSN_LUID (XEXP (link, 0)));
+ }
+
+ /* Non-speculative links go at the head of LOG_LINKS, followed by
+ speculative links. */
+ if (DEP_STATUS (link) & SPECULATIVE)
+ while (*linkp && !(DEP_STATUS (*linkp) & SPECULATIVE))
+ linkp = &XEXP (*linkp, 1);
+
+ XEXP (link, 1) = *linkp;
+ *linkp = link;
+}
+
+/* Move the dependence pointed to by LINKP to the back dependencies
+ of INSN, and also add this dependence to the forward ones. All LOG_LINKS,
+ except one pointed to by LINKP, must be sorted. */
+static void
+adjust_back_add_forw_dep (rtx insn, rtx *linkp)
+{
+ rtx link;
+
+ gcc_assert (current_sched_info->flags & DO_SPECULATION);
+
+ link = *linkp;
+ *linkp = XEXP (*linkp, 1);
+
+ adjust_add_sorted_back_dep (insn, link, &LOG_LINKS (insn));
+ add_forw_dep (insn, link);
+}
+
+/* Remove forward dependence ELEM from the DEPS_LIST of INSN. */
+static void
+delete_forw_dep (rtx insn, rtx elem)
+{
+ gcc_assert (current_sched_info->flags & DO_SPECULATION);
+
+#ifdef ENABLE_CHECKING
+ if (true_dependency_cache)
+ bitmap_clear_bit (&forward_dependency_cache[INSN_LUID (elem)],
+ INSN_LUID (insn));
+#endif
+
+ remove_free_DEPS_LIST_elem (insn, &INSN_DEPEND (elem));
+ INSN_DEP_COUNT (insn)--;
+}
+
+/* Estimate the weakness of dependence between MEM1 and MEM2. */
+static dw_t
+estimate_dep_weak (rtx mem1, rtx mem2)
+{
+ rtx r1, r2;
+
+ if (mem1 == mem2)
+ /* MEMs are the same - don't speculate. */
+ return MIN_DEP_WEAK;
+
+ r1 = XEXP (mem1, 0);
+ r2 = XEXP (mem2, 0);
+
+ if (r1 == r2
+ || (REG_P (r1) && REG_P (r2)
+ && REGNO (r1) == REGNO (r2)))
+ /* Again, MEMs are the same. */
+ return MIN_DEP_WEAK;
+ else if ((REG_P (r1) && !REG_P (r2))
+ || (!REG_P (r1) && REG_P (r2)))
+ /* Different addressing modes - reason to be more speculative,
+ than usual. */
+ return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2;
+ else
+ /* We can't say anything about the dependence. */
+ return UNCERTAIN_DEP_WEAK;
+}
+
+/* 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)
+{
+ ds_t ds;
+
+ 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
+ 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;
+ rtx *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 (insn, elem);
+ else if (res == DEP_CREATED)
+ linkp = &LOG_LINKS (insn);
+
+ adjust_back_add_forw_dep (insn, linkp);
+ }
+}
+
+/* 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, &LOG_LINKS (insn));
+}
+
+/* Remove both backward and forward dependencies between INSN and ELEM. */
+void
+delete_back_forw_dep (rtx insn, rtx elem)
+{
+ gcc_assert (current_sched_info->flags & DO_SPECULATION);
+
+ if (true_dependency_cache != NULL)
+ {
+ bitmap_clear_bit (&true_dependency_cache[INSN_LUID (insn)],
+ INSN_LUID (elem));
+ bitmap_clear_bit (&anti_dependency_cache[INSN_LUID (insn)],
+ INSN_LUID (elem));
+ bitmap_clear_bit (&output_dependency_cache[INSN_LUID (insn)],
+ INSN_LUID (elem));
+ bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
+ INSN_LUID (elem));
+ }
+
+ remove_free_DEPS_LIST_elem (elem, &LOG_LINKS (insn));
+ delete_forw_dep (insn, elem);
+}
+
+/* Return weakness of speculative type TYPE in the dep_status DS. */
+dw_t
+get_dep_weak (ds_t ds, ds_t type)
+{
+ ds = ds & type;
+ switch (type)
+ {
+ case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
+ case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break;
+ case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break;
+ case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break;
+ default: gcc_unreachable ();
+ }
+
+ gcc_assert (MIN_DEP_WEAK <= ds && ds <= MAX_DEP_WEAK);
+ return (dw_t) ds;
+}
+
+/* Return the dep_status, which has the same parameters as DS, except for
+ speculative type TYPE, that will have weakness DW. */
+ds_t
+set_dep_weak (ds_t ds, ds_t type, dw_t dw)
+{
+ gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
+
+ ds &= ~type;
+ switch (type)
+ {
+ case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break;
+ case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break;
+ case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break;
+ case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break;
+ default: gcc_unreachable ();
+ }
+ return ds;
+}
+
+/* Return the join of two dep_statuses DS1 and DS2. */
+ds_t
+ds_merge (ds_t ds1, ds_t ds2)
+{
+ ds_t ds, t;
+
+ gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE));
+
+ ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES);
+
+ t = FIRST_SPEC_TYPE;
+ do
+ {
+ if ((ds1 & t) && !(ds2 & t))
+ ds |= ds1 & t;
+ else if (!(ds1 & t) && (ds2 & t))
+ ds |= ds2 & t;
+ else if ((ds1 & t) && (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;
+
+ ds = set_dep_weak (ds, t, (dw_t) dw);
+ }
+
+ if (t == LAST_SPEC_TYPE)
+ break;
+ t <<= SPEC_TYPE_SHIFT;
+ }
+ while (1);
+
+ return ds;
+}
+
+#ifdef INSN_SCHEDULING
+#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 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_OUTPUT | DEP_TRUE)));
+
+ /* HARD_DEP can not appear in dep_status of a link. */
+ gcc_assert (!(ds & HARD_DEP));
+
+ /* Check that dependence status is set correctly when speculation is not
+ supported. */
+ if (!(current_sched_info->flags & DO_SPECULATION))
+ gcc_assert (!(ds & SPECULATIVE));
+ else if (ds & SPECULATIVE)
+ {
+ if (!relaxed_p)
+ {
+ ds_t type = FIRST_SPEC_TYPE;
+
+ /* Check that dependence weakness is in proper range. */
+ do
+ {
+ if (ds & type)
+ get_dep_weak (ds, type);
+
+ if (type == LAST_SPEC_TYPE)
+ break;
+ type <<= SPEC_TYPE_SHIFT;
+ }
+ while (1);
+ }
+
+ if (ds & BEGIN_SPEC)
+ {
+ /* Only true dependence can be data speculative. */
+ if (ds & BEGIN_DATA)
+ gcc_assert (ds & DEP_TRUE);
+
+ /* Control dependencies in the insn scheduler are represented by
+ anti-dependencies, therefore only anti dependence can be
+ control speculative. */
+ if (ds & BEGIN_CONTROL)
+ gcc_assert (ds & DEP_ANTI);
+ }
+ else
+ {
+ /* Subsequent speculations should resolve true dependencies. */
+ gcc_assert ((ds & DEP_TYPES) == DEP_TRUE);
+ }
+
+ /* Check that true and anti dependencies can't have other speculative
+ statuses. */
+ if (ds & DEP_TRUE)
+ gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC));
+ /* An output dependence can't be speculative at all. */
+ gcc_assert (!(ds & DEP_OUTPUT));
+ if (ds & DEP_ANTI)
+ gcc_assert (ds & BEGIN_CONTROL);
+ }
+}
+#endif
+#endif
OSDN Git Service
