/* Perform instruction reorganizations for delay slot filling.
- Copyright (C) 1992, 1993, 1994, 1995 Free Software Foundation, Inc.
+ Copyright (C) 1992, 93, 94, 95, 96, 1997 Free Software Foundation, Inc.
Contributed by Richard Kenner (kenner@vlsi1.ultra.nyu.edu).
Hacked by Michael Tiemann (tiemann@cygnus.com).
#include "obstack.h"
#include "insn-attr.h"
+/* Import list of registers used as spill regs from reload. */
+extern HARD_REG_SET used_spill_regs;
+
+/* Import highest label used in function at end of reload. */
+extern int max_label_num_after_reload;
+
+
#ifdef DELAY_SLOTS
#define obstack_chunk_alloc xmalloc
struct resources
{
char memory; /* Insn sets or needs a memory location. */
- char unch_memory; /* Insn sets of needs a "unchanging" MEM. */
- char volatil; /* Insn sets or needs a volatile memory loc. */
+ char unch_memory; /* Insn sets of needs a "unchanging" MEM. */
+ char volatil; /* Insn sets or needs a volatile memory loc. */
char cc; /* Insn sets or needs the condition codes. */
HARD_REG_SET regs; /* Which registers are set or needed. */
};
static void update_block PROTO((rtx, rtx));
static int reorg_redirect_jump PROTO((rtx, rtx));
static void update_reg_dead_notes PROTO((rtx, rtx));
+static void fix_reg_dead_note PROTO((rtx, rtx));
static void update_reg_unused_notes PROTO((rtx, rtx));
static void update_live_status PROTO((rtx, rtx));
static rtx next_insn_no_annul PROTO((rtx));
case UNSPEC_VOLATILE:
case ASM_INPUT:
+ case TRAP_IF:
/* Traditional asm's are always volatile. */
res->volatil = 1;
return;
rtx next = NEXT_INSN (x);
int i;
- /* If we are part of a delay slot sequence, point at the SEQUENCE. */
+ /* If we are part of a delay slot sequence, point at the SEQUENCE. */
if (NEXT_INSN (insn) != x)
{
next = NEXT_INSN (NEXT_INSN (insn));
}
}
- /* ... fall through to other INSN processing ... */
+ /* ... fall through to other INSN processing ... */
case INSN:
case JUMP_INSN:
end_of_function_label = gen_label_rtx ();
LABEL_NUSES (end_of_function_label) = 0;
- /* Put the label before an USE insns that may proceed the RETURN insn. */
+ /* Put the label before an USE insns that may proceed the RETURN insn. */
while (GET_CODE (temp) == USE)
temp = PREV_INSN (temp);
register rtx li;
int had_barrier = 0;
- /* Allocate the the rtvec to hold the insns and the SEQUENCE. */
+ /* Allocate the the rtvec to hold the insns and the SEQUENCE. */
rtvec seqv = rtvec_alloc (length + 1);
rtx seq = gen_rtx (SEQUENCE, VOIDmode, seqv);
rtx seq_insn = make_insn_raw (seq);
rtx first = get_insns ();
rtx last = get_last_insn ();
- /* Make a copy of the insn having delay slots. */
+ /* Make a copy of the insn having delay slots. */
rtx delay_insn = copy_rtx (insn);
/* If INSN is followed by a BARRIER, delete the BARRIER since it will only
Non conditional branches return no direction information and
are predicted as very likely taken. */
+
static int
get_jump_flags (insn, label)
rtx insn, label;
}
/* Look at the relative rarities of the fallthrough and destination. If
- they differ, we can predict the branch that way. */
+ they differ, we can predict the branch that way. */
switch (rare_fallthrough - rare_dest)
{
}
}
+/* Called when an insn redundant with start_insn is deleted. If there
+ is a REG_DEAD note for the target of start_insn between start_insn
+ and stop_insn, then the REG_DEAD note needs to be deleted since the
+ value no longer dies there.
+
+ If the REG_DEAD note isn't deleted, then mark_target_live_regs may be
+ confused into thinking the register is dead. */
+
+static void
+fix_reg_dead_note (start_insn, stop_insn)
+ rtx start_insn, stop_insn;
+{
+ rtx p, link, next;
+
+ for (p = next_nonnote_insn (start_insn); p != stop_insn;
+ p = next_nonnote_insn (p))
+ for (link = REG_NOTES (p); link; link = next)
+ {
+ next = XEXP (link, 1);
+
+ if (REG_NOTE_KIND (link) != REG_DEAD
+ || GET_CODE (XEXP (link, 0)) != REG)
+ continue;
+
+ if (reg_set_p (XEXP (link, 0), PATTERN (start_insn)))
+ {
+ remove_note (p, link);
+ return;
+ }
+ }
+}
+
/* Delete any REG_UNUSED notes that exist on INSN but not on REDUNDANT_INSN.
This handles the case of udivmodXi4 instructions which optimize their
return insn;
}
\f
+/* A subroutine of mark_target_live_regs. Search forward from TARGET
+ looking for registers that are set before they are used. These are dead.
+ Stop after passing a few conditional jumps, and/or a small
+ number of unconditional branches. */
+
+static rtx
+find_dead_or_set_registers (target, res, jump_target, jump_count, set, needed)
+ rtx target;
+ struct resources *res;
+ rtx *jump_target;
+ int jump_count;
+ struct resources set, needed;
+{
+ HARD_REG_SET scratch;
+ rtx insn, next;
+ rtx jump_insn = 0;
+ int i;
+
+ for (insn = target; insn; insn = next)
+ {
+ rtx this_jump_insn = insn;
+
+ next = NEXT_INSN (insn);
+ switch (GET_CODE (insn))
+ {
+ case CODE_LABEL:
+ /* After a label, any pending dead registers that weren't yet
+ used can be made dead. */
+ AND_COMPL_HARD_REG_SET (pending_dead_regs, needed.regs);
+ AND_COMPL_HARD_REG_SET (res->regs, pending_dead_regs);
+ CLEAR_HARD_REG_SET (pending_dead_regs);
+
+ if (CODE_LABEL_NUMBER (insn) < max_label_num_after_reload)
+ {
+ /* All spill registers are dead at a label, so kill all of the
+ ones that aren't needed also. */
+ COPY_HARD_REG_SET (scratch, used_spill_regs);
+ AND_COMPL_HARD_REG_SET (scratch, needed.regs);
+ AND_COMPL_HARD_REG_SET (res->regs, scratch);
+ }
+ continue;
+
+ case BARRIER:
+ case NOTE:
+ continue;
+
+ case INSN:
+ if (GET_CODE (PATTERN (insn)) == USE)
+ {
+ /* If INSN is a USE made by update_block, we care about the
+ underlying insn. Any registers set by the underlying insn
+ are live since the insn is being done somewhere else. */
+ if (GET_RTX_CLASS (GET_CODE (XEXP (PATTERN (insn), 0))) == 'i')
+ mark_set_resources (XEXP (PATTERN (insn), 0), res, 0, 1);
+
+ /* All other USE insns are to be ignored. */
+ continue;
+ }
+ else if (GET_CODE (PATTERN (insn)) == CLOBBER)
+ continue;
+ else if (GET_CODE (PATTERN (insn)) == SEQUENCE)
+ {
+ /* An unconditional jump can be used to fill the delay slot
+ of a call, so search for a JUMP_INSN in any position. */
+ for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
+ {
+ this_jump_insn = XVECEXP (PATTERN (insn), 0, i);
+ if (GET_CODE (this_jump_insn) == JUMP_INSN)
+ break;
+ }
+ }
+ }
+
+ if (GET_CODE (this_jump_insn) == JUMP_INSN)
+ {
+ if (jump_count++ < 10)
+ {
+ if (simplejump_p (this_jump_insn)
+ || GET_CODE (PATTERN (this_jump_insn)) == RETURN)
+ {
+ next = JUMP_LABEL (this_jump_insn);
+ if (jump_insn == 0)
+ {
+ jump_insn = insn;
+ if (jump_target)
+ *jump_target = JUMP_LABEL (this_jump_insn);
+ }
+ }
+ else if (condjump_p (this_jump_insn)
+ || condjump_in_parallel_p (this_jump_insn))
+ {
+ struct resources target_set, target_res;
+ struct resources fallthrough_res;
+
+ /* We can handle conditional branches here by following
+ both paths, and then IOR the results of the two paths
+ together, which will give us registers that are dead
+ on both paths. Since this is expensive, we give it
+ a much higher cost than unconditional branches. The
+ cost was chosen so that we will follow at most 1
+ conditional branch. */
+
+ jump_count += 4;
+ if (jump_count >= 10)
+ break;
+
+ mark_referenced_resources (insn, &needed, 1);
+
+ /* For an annulled branch, mark_set_resources ignores slots
+ filled by instructions from the target. This is correct
+ if the branch is not taken. Since we are following both
+ paths from the branch, we must also compute correct info
+ if the branch is taken. We do this by inverting all of
+ the INSN_FROM_TARGET_P bits, calling mark_set_resources,
+ and then inverting the INSN_FROM_TARGET_P bits again. */
+
+ if (GET_CODE (PATTERN (insn)) == SEQUENCE
+ && INSN_ANNULLED_BRANCH_P (this_jump_insn))
+ {
+ for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++)
+ INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i))
+ = ! INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i));
+
+ target_set = set;
+ mark_set_resources (insn, &target_set, 0, 1);
+
+ for (i = 1; i < XVECLEN (PATTERN (insn), 0); i++)
+ INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i))
+ = ! INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i));
+
+ mark_set_resources (insn, &set, 0, 1);
+ }
+ else
+ {
+ mark_set_resources (insn, &set, 0, 1);
+ target_set = set;
+ }
+
+ target_res = *res;
+ COPY_HARD_REG_SET (scratch, target_set.regs);
+ AND_COMPL_HARD_REG_SET (scratch, needed.regs);
+ AND_COMPL_HARD_REG_SET (target_res.regs, scratch);
+
+ fallthrough_res = *res;
+ COPY_HARD_REG_SET (scratch, set.regs);
+ AND_COMPL_HARD_REG_SET (scratch, needed.regs);
+ AND_COMPL_HARD_REG_SET (fallthrough_res.regs, scratch);
+
+ find_dead_or_set_registers (JUMP_LABEL (this_jump_insn),
+ &target_res, 0, jump_count,
+ target_set, needed);
+ find_dead_or_set_registers (next,
+ &fallthrough_res, 0, jump_count,
+ set, needed);
+ IOR_HARD_REG_SET (fallthrough_res.regs, target_res.regs);
+ AND_HARD_REG_SET (res->regs, fallthrough_res.regs);
+ break;
+ }
+ else
+ break;
+ }
+ else
+ {
+ /* Don't try this optimization if we expired our jump count
+ above, since that would mean there may be an infinite loop
+ in the function being compiled. */
+ jump_insn = 0;
+ break;
+ }
+ }
+
+ mark_referenced_resources (insn, &needed, 1);
+ mark_set_resources (insn, &set, 0, 1);
+
+ COPY_HARD_REG_SET (scratch, set.regs);
+ AND_COMPL_HARD_REG_SET (scratch, needed.regs);
+ AND_COMPL_HARD_REG_SET (res->regs, scratch);
+ }
+
+ return jump_insn;
+}
+
/* Set the resources that are live at TARGET.
If TARGET is zero, we refer to the end of the current function and can
in use. This should happen only extremely rarely. */
SET_HARD_REG_SET (res->regs);
- /* Now step forward from TARGET looking for registers that are set before
- they are used. These are dead. If we pass a label, any pending dead
- registers that weren't yet used can be made dead. Stop when we pass a
- conditional JUMP_INSN; follow the first few unconditional branches. */
-
CLEAR_RESOURCE (&set);
CLEAR_RESOURCE (&needed);
- for (insn = target; insn; insn = next)
- {
- rtx this_jump_insn = insn;
-
- next = NEXT_INSN (insn);
- switch (GET_CODE (insn))
- {
- case CODE_LABEL:
- AND_COMPL_HARD_REG_SET (pending_dead_regs, needed.regs);
- AND_COMPL_HARD_REG_SET (res->regs, pending_dead_regs);
- CLEAR_HARD_REG_SET (pending_dead_regs);
- continue;
-
- case BARRIER:
- case NOTE:
- continue;
-
- case INSN:
- if (GET_CODE (PATTERN (insn)) == USE)
- {
- /* If INSN is a USE made by update_block, we care about the
- underlying insn. Any registers set by the underlying insn
- are live since the insn is being done somewhere else. */
- if (GET_RTX_CLASS (GET_CODE (XEXP (PATTERN (insn), 0))) == 'i')
- mark_set_resources (XEXP (PATTERN (insn), 0), res, 0, 1);
-
- /* All other USE insns are to be ignored. */
- continue;
- }
- else if (GET_CODE (PATTERN (insn)) == CLOBBER)
- continue;
- else if (GET_CODE (PATTERN (insn)) == SEQUENCE)
- {
- /* An unconditional jump can be used to fill the delay slot
- of a call, so search for a JUMP_INSN in any position. */
- for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
- {
- this_jump_insn = XVECEXP (PATTERN (insn), 0, i);
- if (GET_CODE (this_jump_insn) == JUMP_INSN)
- break;
- }
- }
- }
-
- if (GET_CODE (this_jump_insn) == JUMP_INSN)
- {
- if (jump_count++ < 10
- && (simplejump_p (this_jump_insn)
- || GET_CODE (PATTERN (this_jump_insn)) == RETURN))
- {
- next = next_active_insn (JUMP_LABEL (this_jump_insn));
- if (jump_insn == 0)
- {
- jump_insn = insn;
- jump_target = JUMP_LABEL (this_jump_insn);
- }
- }
- else
- break;
- }
-
- mark_referenced_resources (insn, &needed, 1);
- mark_set_resources (insn, &set, 0, 1);
-
- COPY_HARD_REG_SET (scratch, set.regs);
- AND_COMPL_HARD_REG_SET (scratch, needed.regs);
- AND_COMPL_HARD_REG_SET (res->regs, scratch);
- }
+ jump_insn = find_dead_or_set_registers (target, res, &jump_target, 0,
+ set, needed);
/* If we hit an unconditional branch, we have another way of finding out
what is live: we can see what is live at the branch target and include
anything used but not set before the branch. The only things that are
- live are those that are live using the above test and the test below.
-
- Don't try this if we expired our jump count above, since that would
- mean there may be an infinite loop in the function being compiled. */
+ live are those that are live using the above test and the test below. */
- if (jump_insn && jump_count < 10)
+ if (jump_insn)
{
struct resources new_resources;
rtx stop_insn = next_active_insn (jump_insn);
register int i, j;
int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
struct resources needed, set;
- register int slots_to_fill, slots_filled;
+ int slots_to_fill, slots_filled;
rtx delay_list;
for (i = 0; i < num_unfilled_slots; i++)
&& eligible_for_delay (insn, slots_filled, trial, flags)
&& no_labels_between_p (insn, trial))
{
+ rtx *tmp;
slots_filled++;
delay_list = add_to_delay_list (trial, delay_list);
+
+ /* TRIAL may have had its delay slot filled, then unfilled. When
+ the delay slot is unfilled, TRIAL is placed back on the unfilled
+ slots obstack. Unfortunately, it is placed on the end of the
+ obstack, not in its original location. Therefore, we must search
+ from entry i + 1 to the end of the unfilled slots obstack to
+ try and find TRIAL. */
+ tmp = &unfilled_slots_base[i + 1];
+ while (*tmp != trial && tmp != unfilled_slots_next)
+ tmp++;
+
/* Remove the unconditional jump from consideration for delay slot
- filling and unthread it. */
- if (unfilled_slots_base[i + 1] == trial)
- unfilled_slots_base[i + 1] = 0;
+ filling and unthread it. */
+ if (*tmp == trial)
+ *tmp = 0;
{
rtx next = NEXT_INSN (trial);
rtx prev = PREV_INSN (trial);
}
}
+ /* If this is an unconditional jump, then try to get insns from the
+ target of the jump. */
+ if (GET_CODE (insn) == JUMP_INSN
+ && simplejump_p (insn)
+ && slots_filled != slots_to_fill)
+ delay_list
+ = fill_slots_from_thread (insn, const_true_rtx,
+ next_active_insn (JUMP_LABEL (insn)),
+ NULL, 1, 1,
+ own_thread_p (JUMP_LABEL (insn),
+ JUMP_LABEL (insn), 0),
+ 0, slots_to_fill, &slots_filled);
+
if (delay_list)
unfilled_slots_base[i]
= emit_delay_sequence (insn, delay_list,
else
SET_HARD_REG_BIT (needed.regs, STACK_POINTER_REGNUM);
+#ifdef EPILOGUE_USES
+ for (i = 0; i <FIRST_PSEUDO_REGISTER; i++)
+ {
+ if (EPILOGUE_USES (i))
+ SET_HARD_REG_BIT (needed.regs, i);
+ }
+#endif
+
for (trial = get_last_insn (); ! stop_search_p (trial, 1);
trial = PREV_INSN (trial))
{
we did. */
if (prior_insn = redundant_insn (trial, insn, delay_list))
{
+ fix_reg_dead_note (prior_insn, insn);
if (own_thread)
{
update_block (trial, thread);
if (own_thread)
{
update_block (trial, thread);
+ if (trial == thread)
+ {
+ thread = next_active_insn (thread);
+ if (new_thread == trial)
+ new_thread = thread;
+ }
delete_insn (trial);
}
else
depend on the destination register. If so, try to place the opposite
arithmetic insn after the jump insn and put the arithmetic insn in the
delay slot. If we can't do this, return. */
- if (delay_list == 0 && likely && new_thread && GET_CODE (new_thread) == INSN)
+ if (delay_list == 0 && likely && new_thread
+ && GET_CODE (new_thread) == INSN
+ && GET_CODE (PATTERN (new_thread)) != ASM_INPUT
+ && asm_noperands (PATTERN (new_thread)) < 0)
{
rtx pat = PATTERN (new_thread);
rtx dest;
if (own_thread)
{
update_block (trial, thread);
+ if (trial == thread)
+ {
+ thread = next_active_insn (thread);
+ if (new_thread == trial)
+ new_thread = thread;
+ }
delete_insn (trial);
}
else
if (trial && GET_CODE (PATTERN (trial)) != SEQUENCE
&& redundant_insn (trial, insn, 0))
{
- trial = next_active_insn (trial);
- if (trial == 0)
- target_label = find_end_label ();
- else
- target_label = get_label_before (trial);
+ rtx tmp;
+
+ /* Figure out where to emit the special USE insn so we don't
+ later incorrectly compute register live/death info. */
+ tmp = next_active_insn (trial);
+ if (tmp == 0)
+ tmp = find_end_label ();
+
+ /* Insert the special USE insn and update dataflow info. */
+ update_block (trial, tmp);
+
+ /* Now emit a label before the special USE insn, and
+ redirect our jump to the new label. */
+ target_label = get_label_before (PREV_INSN (tmp));
reorg_redirect_jump (delay_insn, target_label);
next = insn;
continue;
&end_of_function_needs, 1);
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
- if (global_regs[i])
+ if (global_regs[i]
+#ifdef EPILOGUE_USES
+ || EPILOGUE_USES (i)
+#endif
+ )
SET_HARD_REG_BIT (end_of_function_needs.regs, i);
/* The registers required to be live at the end of the function are
OSDN Git Service
