\f
#include "config.h"
#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
#include "toplev.h"
#include "rtl.h"
#include "tm_p.h"
#include "sched-int.h"
#include "params.h"
#include "cselib.h"
+#include "df.h"
extern char *reg_known_equiv_p;
extern rtx *reg_known_value;
static regset reg_pending_sets;
static regset reg_pending_clobbers;
static regset reg_pending_uses;
-static bool reg_pending_barrier;
+
+/* 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 enum reg_pending_barrier_mode reg_pending_barrier;
/* To speed up the test for duplicate dependency links we keep a
record of dependencies created by add_dependence when the average
static int deps_may_trap_p PARAMS ((rtx));
static void add_dependence_list PARAMS ((rtx, rtx, enum reg_note));
static void add_dependence_list_and_free PARAMS ((rtx, rtx *, enum reg_note));
-static void remove_dependence PARAMS ((rtx, rtx));
static void set_sched_group_p PARAMS ((rtx));
static void flush_pending_lists PARAMS ((struct deps *, rtx, int, int));
static void sched_analyze_1 PARAMS ((struct deps *, rtx, rtx));
static void sched_analyze_2 PARAMS ((struct deps *, rtx, rtx));
static void sched_analyze_insn PARAMS ((struct deps *, rtx, rtx, rtx));
-static rtx group_leader PARAMS ((rtx));
static rtx get_condition PARAMS ((rtx));
static int conditions_mutex_p PARAMS ((rtx, rtx));
}
\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. */
+ 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. */
-void
+int
add_dependence (insn, elem, dep_type)
rtx insn;
rtx elem;
enum reg_note dep_type;
{
- rtx link, next;
+ rtx link;
int present_p;
rtx cond1, cond2;
/* Don't depend an insn on itself. */
if (insn == elem)
- return;
+ 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 (GET_CODE (elem) == NOTE)
- return;
+ return 0;
/* flow.c doesn't handle conditional lifetimes entirely correctly;
calls mess up the conditional lifetimes. */
/* Make sure second instruction doesn't affect condition of first
instruction if switched. */
&& !modified_in_p (cond2, insn))
- return;
- }
-
- /* If elem is part of a sequence that must be scheduled together, then
- make the dependence point to the last insn of the sequence.
- When HAVE_cc0, it is possible for NOTEs to exist between users and
- setters of the condition codes, so we must skip past notes here.
- Otherwise, NOTEs are impossible here. */
- next = next_nonnote_insn (elem);
- if (next && SCHED_GROUP_P (next)
- && GET_CODE (next) != CODE_LABEL)
- {
- /* Notes will never intervene here though, so don't bother checking
- for them. */
- /* Hah! Wrong. */
- /* We must reject CODE_LABELs, so that we don't get confused by one
- that has LABEL_PRESERVE_P set, which is represented by the same
- bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be
- SCHED_GROUP_P. */
-
- rtx nnext;
- while ((nnext = next_nonnote_insn (next)) != NULL
- && SCHED_GROUP_P (nnext)
- && GET_CODE (nnext) != CODE_LABEL)
- next = nnext;
-
- /* Again, don't depend an insn on itself. */
- if (insn == next)
- return;
-
- /* Make the dependence to NEXT, the last insn of the group, instead
- of the original ELEM. */
- elem = next;
+ return 0;
}
present_p = 1;
elem is a CALL is still required. */
if (GET_CODE (insn) == CALL_INSN
&& (INSN_BB (elem) != INSN_BB (insn)))
- return;
+ return 0;
#endif
/* If we already have a dependency for ELEM, then we do not need to
else
present_p = 0;
if (present_p && (int) dep_type >= (int) present_dep_type)
- return;
+ return 0;
}
#endif
abort ();
}
#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))
INSN_LUID (elem));
}
#endif
- return;
- }
+ return 0;
+ }
/* Might want to check one level of transitivity to save conses. */
link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
SET_BIT (output_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
}
#endif
+ return 1;
}
/* A convenience wrapper to operate on an entire list. */
}
}
-/* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS
- of INSN. Abort if not found. */
-
-static void
-remove_dependence (insn, elem)
- rtx insn;
- rtx elem;
-{
- rtx prev, link, next;
- int found = 0;
-
- for (prev = 0, link = LOG_LINKS (insn); link; link = next)
- {
- next = XEXP (link, 1);
- if (XEXP (link, 0) == elem)
- {
- if (prev)
- XEXP (prev, 1) = next;
- else
- LOG_LINKS (insn) = next;
-
-#ifdef INSN_SCHEDULING
- /* If we are removing a dependency from the LOG_LINKS list,
- make sure to remove it from the cache too. */
- if (true_dependency_cache != NULL)
- {
- if (REG_NOTE_KIND (link) == 0)
- RESET_BIT (true_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem));
- else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
- RESET_BIT (anti_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem));
- else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
- RESET_BIT (output_dependency_cache[INSN_LUID (insn)],
- INSN_LUID (elem));
- }
-#endif
-
- free_INSN_LIST_node (link);
-
- found = 1;
- }
- else
- prev = link;
- }
-
- if (!found)
- abort ();
- return;
-}
-
-/* Return an insn which represents a SCHED_GROUP, which is
- the last insn in the group. */
-
-static rtx
-group_leader (insn)
- rtx insn;
-{
- rtx prev;
-
- do
- {
- prev = insn;
- insn = next_nonnote_insn (insn);
- }
- while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL));
-
- return prev;
-}
-
/* Set SCHED_GROUP_P and care for the rest of the bookkeeping that
goes along with that. */
set_sched_group_p (insn)
rtx insn;
{
- rtx link, prev;
+ rtx prev;
SCHED_GROUP_P (insn) = 1;
- /* There may be a note before this insn now, but all notes will
- be removed before we actually try to schedule the insns, so
- it won't cause a problem later. We must avoid it here though. */
prev = prev_nonnote_insn (insn);
-
- /* Make a copy of all dependencies on the immediately previous insn,
- and add to this insn. This is so that all the dependencies will
- apply to the group. Remove an explicit dependence on this insn
- as SCHED_GROUP_P now represents it. */
-
- if (find_insn_list (prev, LOG_LINKS (insn)))
- remove_dependence (insn, prev);
-
- for (link = LOG_LINKS (prev); link; link = XEXP (link, 1))
- add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link));
+ add_dependence (insn, prev, REG_DEP_ANTI);
}
\f
/* Process an insn's memory dependencies. There are four kinds of
while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
|| GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
{
+ if (GET_CODE (dest) == STRICT_LOW_PART
+ || GET_CODE (dest) == ZERO_EXTRACT
+ || GET_CODE (dest) == SIGN_EXTRACT
+ || read_modify_subreg_p (dest))
+ {
+ /* These both read and modify the result. We must handle
+ them as writes to get proper dependencies for following
+ instructions. We must handle them as reads to get proper
+ dependencies from this to previous instructions.
+ Thus we need to call sched_analyze_2. */
+
+ sched_analyze_2 (deps, XEXP (dest, 0), insn);
+ }
if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
{
/* The second and third arguments are values read by this insn. */
mode. An insn should not be moved across this even if it only uses
pseudo-regs because it might give an incorrectly rounded result. */
if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
- reg_pending_barrier = true;
+ reg_pending_barrier = TRUE_BARRIER;
/* For all ASM_OPERANDS, we must traverse the vector of input operands.
We can not just fall through here since then we would be confused
code = GET_CODE (x);
}
if (code == SET || code == CLOBBER)
- sched_analyze_1 (deps, x, insn);
+ {
+ sched_analyze_1 (deps, x, insn);
+
+ /* Bare clobber insns are used for letting life analysis, reg-stack
+ 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);
+ }
else if (code == PARALLEL)
{
int i;
sched_analyze_2 (deps, XEXP (link, 0), insn);
}
if (find_reg_note (insn, REG_SETJMP, NULL))
- reg_pending_barrier = true;
+ reg_pending_barrier = MOVE_BARRIER;
}
if (GET_CODE (insn) == JUMP_INSN)
rtx next;
next = next_nonnote_insn (insn);
if (next && GET_CODE (next) == BARRIER)
- reg_pending_barrier = true;
+ reg_pending_barrier = TRUE_BARRIER;
else
{
rtx pending, pending_mem;
INIT_REG_SET (&tmp);
(*current_sched_info->compute_jump_reg_dependencies) (insn, &tmp);
- IOR_REG_SET (reg_pending_uses, &tmp);
+ /* Make latency of jump equal to 0 by using anti-dependence. */
+ EXECUTE_IF_SET_IN_REG_SET (&tmp, 0, i,
+ {
+ 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);
+ reg_last->uses_length++;
+ reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
+ });
CLEAR_REG_SET (&tmp);
/* All memory writes and volatile reads must happen before the
|| INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END
|| INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG
|| INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END)
- reg_pending_barrier = true;
+ reg_pending_barrier = MOVE_BARRIER;
link = XEXP (link, 1);
}
where block boundaries fall. This is mighty confusing elsewhere.
Therefore, prevent such an instruction from being moved. */
if (can_throw_internal (insn))
- reg_pending_barrier = true;
+ reg_pending_barrier = MOVE_BARRIER;
/* Add dependencies if a scheduling barrier was found. */
if (reg_pending_barrier)
{
+ /* 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)
{
EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i,
{
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->sets, 0);
- add_dependence_list (insn, reg_last->clobbers, 0);
+ add_dependence_list
+ (insn, reg_last->sets,
+ reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
+ add_dependence_list
+ (insn, reg_last->clobbers,
+ reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
});
}
else
struct deps_reg *reg_last = &deps->reg_last[i];
add_dependence_list_and_free (insn, ®_last->uses,
REG_DEP_ANTI);
- add_dependence_list_and_free (insn, ®_last->sets, 0);
- add_dependence_list_and_free (insn, ®_last->clobbers, 0);
+ add_dependence_list_and_free
+ (insn, ®_last->sets,
+ reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
+ add_dependence_list_and_free
+ (insn, ®_last->clobbers,
+ reg_pending_barrier == TRUE_BARRIER ? 0 : REG_DEP_ANTI);
reg_last->uses_length = 0;
reg_last->clobbers_length = 0;
});
}
flush_pending_lists (deps, insn, true, true);
- reg_pending_barrier = false;
+ reg_pending_barrier = NOT_A_BARRIER;
}
else
{
EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i,
{
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);
if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
|| reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
{
REG_DEP_ANTI);
add_dependence_list_and_free (insn, ®_last->clobbers,
REG_DEP_OUTPUT);
+ reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
reg_last->clobbers_length = 0;
reg_last->uses_length = 0;
}
{
/* This is setjmp. Assume that all registers, not just
hard registers, may be clobbered by this call. */
- reg_pending_barrier = true;
+ reg_pending_barrier = MOVE_BARRIER;
}
else
{
SET_REGNO_REG_SET (reg_pending_sets, i);
SET_REGNO_REG_SET (reg_pending_uses, i);
}
- /* Other call-clobbered hard regs may be clobbered. */
- else if (TEST_HARD_REG_BIT (regs_invalidated_by_call, 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
abort ();
}
\f
+
+/* The following function adds forward dependence (FROM, TO) with
+ given DEP_TYPE. The forward dependence should be not exist before. */
+
+void
+add_forward_dependence (from, to, dep_type)
+ rtx from;
+ rtx to;
+ enum reg_note dep_type;
+{
+ rtx new_link;
+
+#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. */
+ if (GET_CODE (from) == NOTE
+ || INSN_DELETED_P (from)
+ || (forward_dependency_cache != NULL
+ && TEST_BIT (forward_dependency_cache[INSN_LUID (from)],
+ INSN_LUID (to)))
+ || (forward_dependency_cache == NULL
+ && find_insn_list (to, INSN_DEPEND (from))))
+ abort ();
+ if (forward_dependency_cache != NULL)
+ SET_BIT (forward_dependency_cache[INSN_LUID (from)],
+ INSN_LUID (to));
+#endif
+
+ new_link = alloc_INSN_LIST (to, INSN_DEPEND (from));
+
+ PUT_REG_NOTE_KIND (new_link, dep_type);
+
+ INSN_DEPEND (from) = new_link;
+ INSN_DEP_COUNT (to) += 1;
+}
+
/* Examine insns in the range [ HEAD, TAIL ] and Use the backward
dependences from LOG_LINKS to build forward dependences in
INSN_DEPEND. */
{
rtx insn, link;
rtx next_tail;
- enum reg_note dep_type;
next_tail = NEXT_INSN (tail);
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
if (! INSN_P (insn))
continue;
- insn = group_leader (insn);
-
for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
- {
- rtx x = group_leader (XEXP (link, 0));
- rtx new_link;
-
- if (x != XEXP (link, 0))
- continue;
-
-#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. */
- if (GET_CODE (x) == NOTE
- || INSN_DELETED_P (x)
- || (forward_dependency_cache != NULL
- && TEST_BIT (forward_dependency_cache[INSN_LUID (x)],
- INSN_LUID (insn)))
- || (forward_dependency_cache == NULL
- && find_insn_list (insn, INSN_DEPEND (x))))
- abort ();
- if (forward_dependency_cache != NULL)
- SET_BIT (forward_dependency_cache[INSN_LUID (x)],
- INSN_LUID (insn));
-#endif
-
- new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x));
-
- dep_type = REG_NOTE_KIND (link);
- PUT_REG_NOTE_KIND (new_link, dep_type);
-
- INSN_DEPEND (x) = new_link;
- INSN_DEP_COUNT (insn) += 1;
- }
+ add_forward_dependence (XEXP (link, 0), insn, REG_NOTE_KIND (link));
}
}
\f
}
/* If it is profitable to use them, initialize caches for tracking
- dependency informatino. LUID is the number of insns to be scheduled,
+ dependency information. LUID is the number of insns to be scheduled,
it is used in the estimate of profitability. */
void
reg_pending_sets = INITIALIZE_REG_SET (reg_pending_sets_head);
reg_pending_clobbers = INITIALIZE_REG_SET (reg_pending_clobbers_head);
reg_pending_uses = INITIALIZE_REG_SET (reg_pending_uses_head);
- reg_pending_barrier = false;
+ reg_pending_barrier = NOT_A_BARRIER;
}
/* Free everything used by the dependency analysis code. */