static sbitmap *forward_dependency_cache;
#endif
+static int deps_may_trap_p PARAMS ((rtx));
static void remove_dependence PARAMS ((rtx, rtx));
static void set_sched_group_p PARAMS ((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
+/* Return nonzero if a load of the memory reference MEM can cause a trap. */
+
+static int
+deps_may_trap_p (mem)
+ rtx mem;
+{
+ rtx addr = XEXP (mem, 0);
+
+ if (REG_P (addr)
+ && REGNO (addr) >= FIRST_PSEUDO_REGISTER
+ && reg_known_value[REGNO (addr)])
+ addr = reg_known_value[REGNO (addr)];
+ return rtx_addr_can_trap_p (addr);
+}
\f
/* Return the INSN_LIST containing INSN in LIST, or NULL
if LIST does not contain INSN. */
return 0;
}
\f
+/* Find the condition under which INSN is executed. */
+
+static rtx
+get_condition (insn)
+ rtx insn;
+{
+ rtx pat = PATTERN (insn);
+ rtx cond;
+
+ if (pat == 0)
+ return 0;
+ if (GET_CODE (pat) == COND_EXEC)
+ return COND_EXEC_TEST (pat);
+ if (GET_CODE (insn) != JUMP_INSN)
+ return 0;
+ if (GET_CODE (pat) != SET || SET_SRC (pat) != pc_rtx)
+ return 0;
+ if (GET_CODE (SET_DEST (pat)) != IF_THEN_ELSE)
+ return 0;
+ pat = SET_DEST (pat);
+ cond = XEXP (pat, 0);
+ if (GET_CODE (XEXP (cond, 1)) == LABEL_REF
+ && XEXP (cond, 2) == pc_rtx)
+ return cond;
+ else if (GET_CODE (XEXP (cond, 2)) == LABEL_REF
+ && XEXP (cond, 1) == pc_rtx)
+ return gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)), GET_MODE (cond),
+ XEXP (cond, 0), XEXP (cond, 1));
+ else
+ return 0;
+}
+
+/* Return nonzero if conditions COND1 and COND2 can never be both true. */
+
+static int
+conditions_mutex_p (cond1, cond2)
+ rtx cond1, cond2;
+{
+ if (GET_RTX_CLASS (GET_CODE (cond1)) == '<'
+ && GET_RTX_CLASS (GET_CODE (cond2)) == '<'
+ && GET_CODE (cond1) == reverse_condition (GET_CODE (cond2))
+ && XEXP (cond1, 0) == XEXP (cond2, 0)
+ && XEXP (cond1, 1) == XEXP (cond2, 1))
+ 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. */
rtx link, next;
int present_p;
enum reg_note present_dep_type;
+ rtx cond1, cond2;
/* Don't depend an insn on itself. */
if (insn == elem)
if (GET_CODE (elem) == NOTE)
return;
+ /* flow.c doesn't handle conditional lifetimes entirely correctly;
+ calls mess up the conditional lifetimes. */
+ if (GET_CODE (insn) != CALL_INSN && GET_CODE (elem) != CALL_INSN)
+ {
+ cond1 = get_condition (insn);
+ cond2 = get_condition (elem);
+ if (cond1 && cond2 && conditions_mutex_p (cond1, cond2))
+ 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
if (dest == 0)
return;
- if (GET_CODE (dest) == PARALLEL
- && GET_MODE (dest) == BLKmode)
+ if (GET_CODE (dest) == PARALLEL)
{
register int i;
+
for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
- sched_analyze_1 (deps, XVECEXP (dest, 0, i), insn);
+ if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
+ sched_analyze_1 (deps,
+ gen_rtx_CLOBBER (VOIDmode,
+ XEXP (XVECEXP (dest, 0, i), 0)),
+ insn);
+
if (GET_CODE (x) == SET)
sched_analyze_2 (deps, SET_SRC (x), insn);
return;
int r = regno + i;
rtx u;
- for (u = deps->reg_last_uses[r]; u; u = XEXP (u, 1))
+ for (u = deps->reg_last[r].uses; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
- for (u = deps->reg_last_sets[r]; u; u = XEXP (u, 1))
+ for (u = deps->reg_last[r].sets; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
/* Clobbers need not be ordered with respect to one
pending clobber. */
if (code == SET)
{
- free_INSN_LIST_list (&deps->reg_last_uses[r]);
- for (u = deps->reg_last_clobbers[r]; u; u = XEXP (u, 1))
+ if (GET_CODE (PATTERN (insn)) != COND_EXEC)
+ free_INSN_LIST_list (&deps->reg_last[r].uses);
+ for (u = deps->reg_last[r].clobbers; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
SET_REGNO_REG_SET (reg_pending_sets, r);
}
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
}
}
+ /* ??? 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)
+ {
+ if (GET_CODE (PATTERN (insn)) != USE
+ && GET_CODE (PATTERN (insn)) != CLOBBER)
+ abort ();
+ }
else
{
rtx u;
- for (u = deps->reg_last_uses[regno]; u; u = XEXP (u, 1))
+ for (u = deps->reg_last[regno].uses; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
- for (u = deps->reg_last_sets[regno]; u; u = XEXP (u, 1))
+ for (u = deps->reg_last[regno].sets; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
if (code == SET)
{
- free_INSN_LIST_list (&deps->reg_last_uses[regno]);
- for (u = deps->reg_last_clobbers[regno]; u; u = XEXP (u, 1))
+ if (GET_CODE (PATTERN (insn)) != COND_EXEC)
+ free_INSN_LIST_list (&deps->reg_last[regno].uses);
+ for (u = deps->reg_last[regno].clobbers; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_OUTPUT);
SET_REGNO_REG_SET (reg_pending_sets, regno);
}
while (--i >= 0)
{
int r = regno + i;
- deps->reg_last_uses[r]
- = alloc_INSN_LIST (insn, deps->reg_last_uses[r]);
+ deps->reg_last[r].uses
+ = alloc_INSN_LIST (insn, deps->reg_last[r].uses);
+ SET_REGNO_REG_SET (&deps->reg_last_in_use, r);
- for (u = deps->reg_last_sets[r]; u; u = XEXP (u, 1))
+ for (u = deps->reg_last[r].sets; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), 0);
/* ??? This should never happen. */
- for (u = deps->reg_last_clobbers[r]; u; u = XEXP (u, 1))
+ for (u = deps->reg_last[r].clobbers; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), 0);
if (call_used_regs[r] || global_regs[r])
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
}
}
+ /* ??? 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)
+ {
+ if (GET_CODE (PATTERN (insn)) != USE
+ && GET_CODE (PATTERN (insn)) != CLOBBER)
+ abort ();
+ }
else
{
- deps->reg_last_uses[regno]
- = alloc_INSN_LIST (insn, deps->reg_last_uses[regno]);
+ deps->reg_last[regno].uses
+ = alloc_INSN_LIST (insn, deps->reg_last[regno].uses);
+ SET_REGNO_REG_SET (&deps->reg_last_in_use, regno);
- for (u = deps->reg_last_sets[regno]; u; u = XEXP (u, 1))
+ for (u = deps->reg_last[regno].sets; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), 0);
/* ??? This should never happen. */
- for (u = deps->reg_last_clobbers[regno]; u; u = XEXP (u, 1))
+ for (u = deps->reg_last[regno].clobbers; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), 0);
/* Pseudos that are REG_EQUIV to something may be replaced
}
for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+ if (GET_CODE (XEXP (u, 0)) != JUMP_INSN
+ || 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. */
pseudo-regs because it might give an incorrectly rounded result. */
if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
{
- int max_reg = max_reg_num ();
- for (i = 0; i < max_reg; i++)
+ for (i = 0; i < deps->max_reg; i++)
{
- for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
- free_INSN_LIST_list (&deps->reg_last_uses[i]);
+ struct deps_reg *reg_last = &deps->reg_last[i];
- for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
+ for (u = reg_last->uses; u; u = XEXP (u, 1))
+ add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+ for (u = reg_last->sets; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), 0);
-
- for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1))
+ for (u = reg_last->clobbers; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), 0);
+
+ if (GET_CODE (PATTERN (insn)) != COND_EXEC)
+ free_INSN_LIST_list (®_last->uses);
}
reg_pending_sets_all = 1;
rtx loop_notes;
{
register RTX_CODE code = GET_CODE (x);
+ int schedule_barrier_found = 0;
rtx link;
- int maxreg = max_reg_num ();
int i;
if (code == COND_EXEC)
sched_analyze_2 (deps, XEXP (link, 0), insn);
}
+ if (GET_CODE (insn) == JUMP_INSN)
+ {
+ rtx next;
+ next = next_nonnote_insn (insn);
+ if (next && GET_CODE (next) == BARRIER)
+ schedule_barrier_found = 1;
+ else
+ {
+ rtx pending, pending_mem, u;
+ regset_head tmp;
+ INIT_REG_SET (&tmp);
+
+ (*current_sched_info->compute_jump_reg_dependencies) (insn, &tmp);
+ EXECUTE_IF_SET_IN_REG_SET (&tmp, 0, i,
+ {
+ struct deps_reg *reg_last = &deps->reg_last[i];
+ for (u = reg_last->sets; u; u = XEXP (u, 1))
+ add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+ reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
+ SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
+ });
+
+ CLEAR_REG_SET (&tmp);
+
+ pending = deps->pending_write_insns;
+ pending_mem = deps->pending_write_mems;
+ while (pending)
+ {
+ add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
+
+ 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);
+ }
+ }
+
/* 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)
{
- int max_reg = max_reg_num ();
- int schedule_barrier_found = 0;
rtx link;
/* Update loop_notes with any notes from this insn. Also determine
if any of the notes on the list correspond to instruction scheduling
- barriers (loop, eh & setjmp notes, but not range notes. */
+ barriers (loop, eh & setjmp notes, but not range notes). */
link = loop_notes;
while (XEXP (link, 1))
{
}
XEXP (link, 1) = REG_NOTES (insn);
REG_NOTES (insn) = loop_notes;
+ }
- /* Add dependencies if a scheduling barrier was found. */
- if (schedule_barrier_found)
- {
- for (i = 0; i < max_reg; i++)
- {
- rtx u;
- for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
- free_INSN_LIST_list (&deps->reg_last_uses[i]);
+ /* 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. */
+ if (flag_non_call_exceptions && can_throw_internal (insn))
+ schedule_barrier_found = 1;
- for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), 0);
+ /* Add dependencies if a scheduling barrier was found. */
+ if (schedule_barrier_found)
+ {
+ rtx u;
- for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1))
- add_dependence (insn, XEXP (u, 0), 0);
- }
- reg_pending_sets_all = 1;
+ for (i = 0; i < deps->max_reg; i++)
+ {
+ struct deps_reg *reg_last = &deps->reg_last[i];
- flush_pending_lists (deps, insn, 0);
+ for (u = reg_last->uses; u; u = XEXP (u, 1))
+ add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
+ for (u = reg_last->sets; u; u = XEXP (u, 1))
+ add_dependence (insn, XEXP (u, 0), 0);
+ for (u = reg_last->clobbers; u; u = XEXP (u, 1))
+ add_dependence (insn, XEXP (u, 0), 0);
+
+ if (GET_CODE (PATTERN (insn)) != COND_EXEC)
+ free_INSN_LIST_list (®_last->uses);
}
+ flush_pending_lists (deps, insn, 0);
+ reg_pending_sets_all = 1;
}
- /* Accumulate clobbers until the next set so that it will be output dependent
- on all of them. At the next set we can clear the clobber list, since
- subsequent sets will be output dependent on it. */
- EXECUTE_IF_SET_IN_REG_SET
- (reg_pending_sets, 0, i,
- {
- free_INSN_LIST_list (&deps->reg_last_sets[i]);
- free_INSN_LIST_list (&deps->reg_last_clobbers[i]);
- deps->reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
- });
- EXECUTE_IF_SET_IN_REG_SET
- (reg_pending_clobbers, 0, i,
- {
- deps->reg_last_clobbers[i]
- = alloc_INSN_LIST (insn, deps->reg_last_clobbers[i]);
- });
- CLEAR_REG_SET (reg_pending_sets);
- CLEAR_REG_SET (reg_pending_clobbers);
-
+ /* Accumulate clobbers until the next set so that it will be output
+ dependent on all of them. At the next set we can clear the clobber
+ list, since subsequent sets will be output dependent on it. */
if (reg_pending_sets_all)
{
- for (i = 0; i < maxreg; i++)
+ reg_pending_sets_all = 0;
+ for (i = 0; i < deps->max_reg; i++)
{
- free_INSN_LIST_list (&deps->reg_last_sets[i]);
- free_INSN_LIST_list (&deps->reg_last_clobbers[i]);
- deps->reg_last_sets[i] = alloc_INSN_LIST (insn, NULL_RTX);
+ struct deps_reg *reg_last = &deps->reg_last[i];
+ if (GET_CODE (PATTERN (insn)) != COND_EXEC)
+ {
+ free_INSN_LIST_list (®_last->sets);
+ free_INSN_LIST_list (®_last->clobbers);
+ }
+ reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
+ SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
}
-
- reg_pending_sets_all = 0;
}
+ else
+ {
+ EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
+ {
+ struct deps_reg *reg_last = &deps->reg_last[i];
+ if (GET_CODE (PATTERN (insn)) != COND_EXEC)
+ {
+ free_INSN_LIST_list (®_last->sets);
+ free_INSN_LIST_list (®_last->clobbers);
+ }
+ reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
+ SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
+ });
+ EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i,
+ {
+ struct deps_reg *reg_last = &deps->reg_last[i];
+ reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
+ SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
+ });
+ }
+ CLEAR_REG_SET (reg_pending_sets);
+ CLEAR_REG_SET (reg_pending_clobbers);
/* 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
if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == NOTE
&& NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
{
- int max_reg = max_reg_num ();
- for (i = 0; i < max_reg; i++)
+ for (i = 0; i < deps->max_reg; i++)
{
- for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
+ struct deps_reg *reg_last = &deps->reg_last[i];
+
+ for (u = reg_last->uses; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
- free_INSN_LIST_list (&deps->reg_last_uses[i]);
-
- for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
+ for (u = reg_last->sets; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), 0);
-
- for (u = deps->reg_last_clobbers[i]; u; u = XEXP (u, 1))
+ for (u = reg_last->clobbers; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), 0);
+
+ free_INSN_LIST_list (®_last->uses);
}
reg_pending_sets_all = 1;
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (call_used_regs[i] || global_regs[i])
{
- for (u = deps->reg_last_uses[i]; u; u = XEXP (u, 1))
+ for (u = deps->reg_last[i].uses; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-
- for (u = deps->reg_last_sets[i]; u; u = XEXP (u, 1))
+ for (u = deps->reg_last[i].sets; u; u = XEXP (u, 1))
add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
SET_REGNO_REG_SET (reg_pending_clobbers, i);
init_deps (deps)
struct deps *deps;
{
- int maxreg = max_reg_num ();
- deps->reg_last_uses = (rtx *) xcalloc (maxreg, sizeof (rtx));
- deps->reg_last_sets = (rtx *) xcalloc (maxreg, sizeof (rtx));
- deps->reg_last_clobbers = (rtx *) xcalloc (maxreg, sizeof (rtx));
+ int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
+
+ deps->max_reg = max_reg;
+ deps->reg_last = (struct deps_reg *)
+ xcalloc (max_reg, sizeof (struct deps_reg));
+ INIT_REG_SET (&deps->reg_last_in_use);
deps->pending_read_insns = 0;
deps->pending_read_mems = 0;
free_deps (deps)
struct deps *deps;
{
- int max_reg = max_reg_num ();
int i;
- /* Note this loop is executed max_reg * nr_regions times. It's first
- implementation accounted for over 90% of the calls to free_INSN_LIST_list.
- The list was empty for the vast majority of those calls. On the PA, not
- calling free_INSN_LIST_list in those cases improves -O2 compile times by
- 3-5% on average. */
- for (i = 0; i < max_reg; ++i)
+ /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
+ times. For a test case with 42000 regs and 8000 small basic blocks,
+ this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */
+ EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i,
{
- if (deps->reg_last_clobbers[i])
- free_INSN_LIST_list (&deps->reg_last_clobbers[i]);
- if (deps->reg_last_sets[i])
- free_INSN_LIST_list (&deps->reg_last_sets[i]);
- if (deps->reg_last_uses[i])
- free_INSN_LIST_list (&deps->reg_last_uses[i]);
- }
+ struct deps_reg *reg_last = &deps->reg_last[i];
+ free_INSN_LIST_list (®_last->uses);
+ free_INSN_LIST_list (®_last->sets);
+ free_INSN_LIST_list (®_last->clobbers);
+ });
+ CLEAR_REG_SET (&deps->reg_last_in_use);
+
+ free (deps->reg_last);
+ deps->reg_last = NULL;
}
/* If it is profitable to use them, initialize caches for tracking