/* Perform instruction reorganizations for delay slot filling.
- Copyright (C) 1992 Free Software Foundation, Inc.
+ Copyright (C) 1992, 1993 Free Software Foundation, Inc.
Contributed by Richard Kenner (kenner@nyu.edu).
Hacked by Michael Tiemann (tiemann@cygnus.com).
along with GNU CC; see the file COPYING. If not, write to
the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
-
-#include "insn-attr.h"
-
-#ifdef DELAY_SLOTS
-
/* Instruction reorganization pass.
This pass runs after register allocation and final jump
optimization. It should be the last pass to run before peephole.
It serves primarily to fill delay slots of insns, typically branch
and call insns. Other insns typically involve more complicated
- interractions of data dependencies and resource constraints, and
+ interactions of data dependencies and resource constraints, and
are better handled by scheduling before register allocation (by the
function `schedule_insns').
target that would only be safe to execute knowing that the branch
is taken.
+ The HP-PA always has a branch delay slot. For unconditional branches
+ its effects can be annulled when the branch is taken. The effects
+ of the delay slot in a conditional branch can be nullified for forward
+ taken branches, or for untaken backward branches. This means
+ we can hoist insns from the fall-through path for forward branches or
+ steal insns from the target of backward branches.
+
Three techniques for filling delay slots have been implemented so far:
(1) `fill_simple_delay_slots' is the simplest, most efficient way
this strategy, but it helps (by keeping more options open).
`fill_eager_delay_slots' tries to guess the direction the branch
will go; if it guesses right 100% of the time, it can reduce the
- branch penalty as much as `fill_eager_delay_slots' does. If it
+ branch penalty as much as `fill_simple_delay_slots' does. If it
guesses wrong 100% of the time, it might as well schedule nops (or
on the m88k, unexpose the branch slot). When
`fill_eager_delay_slots' takes insns from the fall-through path of
On machines that use CC0, we are very conservative. We will not make
a copy of an insn involving CC0 since we want to maintain a 1-1
- correspondance between the insn that sets and uses CC0. The insns are
+ correspondence between the insn that sets and uses CC0. The insns are
allowed to be separated by placing an insn that sets CC0 (but not an insn
that uses CC0; we could do this, but it doesn't seem worthwhile) in a
delay slot. In that case, we point each insn at the other with REG_CC_USER
#include "flags.h"
#include "output.h"
#include "obstack.h"
+#include "insn-attr.h"
+
+#ifdef DELAY_SLOTS
#define obstack_chunk_alloc xmalloc
#define obstack_chunk_free free
-extern int xmalloc ();
-extern void free ();
-
#ifndef ANNUL_IFTRUE_SLOTS
-#define eligible_for_annul_true(INSN, SLOTS, TRIAL) 0
+#define eligible_for_annul_true(INSN, SLOTS, TRIAL, FLAGS) 0
#endif
#ifndef ANNUL_IFFALSE_SLOTS
-#define eligible_for_annul_false(INSN, SLOTS, TRIAL) 0
+#define eligible_for_annul_false(INSN, SLOTS, TRIAL, FLAGS) 0
#endif
/* Insns which have delay slots that have not yet been filled. */
do { (RES)->memory = (RES)->volatil = (RES)->cc = 0; \
CLEAR_HARD_REG_SET ((RES)->regs); } while (0)
+/* Indicates what resources are required at the beginning of the epilogue. */
+static struct resources start_of_epilogue_needs;
+
/* Indicates what resources are required at function end. */
static struct resources end_of_function_needs;
/* Points to the label before the end of the function. */
static rtx end_of_function_label;
-/* This structure is used to record livness information at the targets or
+/* This structure is used to record liveness information at the targets or
fallthrough insns of branches. We will most likely need the information
at targets again, so save them in a hash table rather than recomputing them
each time. */
/* Highest valid index in `uid_to_ruid'. */
static int max_uid;
-/* Forward references: */
-
-static int redundant_insn_p ();
-static void update_block ();
+static void mark_referenced_resources PROTO((rtx, struct resources *, int));
+static void mark_set_resources PROTO((rtx, struct resources *, int, int));
+static int stop_search_p PROTO((rtx, int));
+static int resource_conflicts_p PROTO((struct resources *,
+ struct resources *));
+static int insn_references_resource_p PROTO((rtx, struct resources *, int));
+static int insn_sets_resources_p PROTO((rtx, struct resources *, int));
+static rtx find_end_label PROTO((void));
+static rtx emit_delay_sequence PROTO((rtx, rtx, int, int));
+static rtx add_to_delay_list PROTO((rtx, rtx));
+static void delete_from_delay_slot PROTO((rtx));
+static void delete_scheduled_jump PROTO((rtx));
+static void note_delay_statistics PROTO((int, int));
+static rtx optimize_skip PROTO((rtx));
+static int get_jump_flags PROTO((rtx, rtx));
+static int rare_destination PROTO((rtx));
+static int mostly_true_jump PROTO((rtx, rtx));
+static rtx get_branch_condition PROTO((rtx, rtx));
+static int condition_dominates_p PROTO((rtx, rtx));
+static rtx steal_delay_list_from_target PROTO((rtx, rtx, rtx, rtx,
+ struct resources *,
+ struct resources *,
+ struct resources *,
+ int, int *, int *, rtx *));
+static rtx steal_delay_list_from_fallthrough PROTO((rtx, rtx, rtx, rtx,
+ struct resources *,
+ struct resources *,
+ struct resources *,
+ int, int *, int *));
+static void try_merge_delay_insns PROTO((rtx, rtx));
+static int redundant_insn_p PROTO((rtx, rtx, rtx));
+static int own_thread_p PROTO((rtx, rtx, int));
+static int find_basic_block PROTO((rtx));
+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 update_live_status PROTO((rtx, rtx));
+static rtx next_insn_no_annul PROTO((rtx));
+static void mark_target_live_regs PROTO((rtx, struct resources *));
+static void fill_simple_delay_slots PROTO((rtx, int));
+static rtx fill_slots_from_thread PROTO((rtx, rtx, rtx, rtx, int, int,
+ int, int, int, int *));
+static void fill_eager_delay_slots PROTO((rtx));
+static void relax_delay_slots PROTO((rtx));
+static void make_return_insns PROTO((rtx));
\f
/* Given X, some rtl, and RES, a pointer to a `struct resource', mark
which resources are references by the insn. If INCLUDE_CALLED_ROUTINE
CALL_INSNs. */
static void
-mark_referenced_resources (x, res, include_called_routine)
+mark_referenced_resources (x, res, include_delayed_effects)
register rtx x;
register struct resources *res;
- register int include_called_routine;
+ register int include_delayed_effects;
{
register enum rtx_code code = GET_CODE (x);
register int i, j;
return;
case CALL_INSN:
- if (include_called_routine)
+ if (include_delayed_effects)
{
/* A CALL references memory, the frame pointer if it exists, the
stack pointer, any global registers and any registers given in
}
}
- /* ... fall through to other INSN procesing ... */
+ /* ... fall through to other INSN processing ... */
case INSN:
case JUMP_INSN:
+
+#ifdef INSN_REFERENCES_ARE_DELAYED
+ if (! include_delayed_effects
+ && INSN_REFERENCES_ARE_DELAYED (x))
+ return;
+#endif
+
/* No special processing, just speed up. */
- mark_referenced_resources (PATTERN (x), res, include_called_routine);
+ mark_referenced_resources (PATTERN (x), res, include_delayed_effects);
return;
}
switch (*format_ptr++)
{
case 'e':
- mark_referenced_resources (XEXP (x, i), res, include_called_routine);
+ mark_referenced_resources (XEXP (x, i), res, include_delayed_effects);
break;
case 'E':
for (j = 0; j < XVECLEN (x, i); j++)
mark_referenced_resources (XVECEXP (x, i, j), res,
- include_called_routine);
+ include_delayed_effects);
break;
}
}
\f
-/* Given an insn, INSN, and a pointer to a `struct resource', RES, indicate
- which resources are modified by the insn. If INCLUDE_CALLED_ROUTINE
- is TRUE, also mark resources potentially set by the called routine.
+/* Given X, a part of an insn, and a pointer to a `struct resource', RES,
+ indicate which resources are modified by the insn. If INCLUDE_CALLED_ROUTINE
+ is nonzero, also mark resources potentially set by the called routine.
+
+ If IN_DEST is nonzero, it means we are inside a SET. Otherwise,
+ objects are being referenced instead of set.
We never mark the insn as modifying the condition code unless it explicitly
SETs CC0 even though this is not totally correct. The reason for this is
- that we require a SET of CC0 to immediately preceed the reference to CC0.
+ that we require a SET of CC0 to immediately precede the reference to CC0.
So if some other insn sets CC0 as a side-effect, we know it cannot affect
our computation and thus may be placed in a delay slot. */
static void
-mark_set_resources (insn, res, include_called_routine)
- register rtx insn;
+mark_set_resources (x, res, in_dest, include_delayed_effects)
+ register rtx x;
register struct resources *res;
- int include_called_routine;
+ int in_dest;
+ int include_delayed_effects;
{
- register int i;
+ register enum rtx_code code;
+ register int i, j;
+ register char *format_ptr;
- switch (GET_CODE (insn))
+ restart:
+
+ code = GET_CODE (x);
+
+ switch (code)
{
case NOTE:
case BARRIER:
case CODE_LABEL:
+ case USE:
+ case CONST_INT:
+ case CONST_DOUBLE:
+ case LABEL_REF:
+ case SYMBOL_REF:
+ case CONST:
+ case PC:
/* These don't set any resources. */
return;
+ case CC0:
+ if (in_dest)
+ res->cc = 1;
+ return;
+
case CALL_INSN:
/* Called routine modifies the condition code, memory, any registers
that aren't saved across calls, global registers and anything
explicitly CLOBBERed immediately after the CALL_INSN. */
- if (include_called_routine)
+ if (include_delayed_effects)
{
- rtx next = NEXT_INSN (insn);
+ rtx next = NEXT_INSN (x);
res->cc = res->memory = 1;
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
for (; (next && GET_CODE (next) == INSN
&& GET_CODE (PATTERN (next)) == CLOBBER);
next = NEXT_INSN (next))
- mark_referenced_resources (XEXP (PATTERN (next), 0), res, 0);
+ mark_set_resources (XEXP (PATTERN (next), 0), res, 1, 0);
}
/* ... and also what it's RTL says it modifies, if anything. */
case JUMP_INSN:
case INSN:
- {
- register rtx body = PATTERN (insn);
- register rtx note;
-
- /* An insn consisting of just a CLOBBER (or USE) is
- just for flow and doesn't actually do anything, so we don't check
- for it.
- If the source of a SET is a CALL, this is actually done by
- the called routine. So only include it if we are to include the
- effects of the calling routine. */
+ /* An insn consisting of just a CLOBBER (or USE) is just for flow
+ and doesn't actually do anything, so we ignore it. */
- if (GET_CODE (body) == SET
- && (include_called_routine || GET_CODE (SET_SRC (body)) != CALL))
- mark_referenced_resources (SET_DEST (body), res, 0);
- else if (GET_CODE (body) == PARALLEL)
- {
- for (i = 0; i < XVECLEN (body, 0); i++)
- if ((GET_CODE (XVECEXP (body, 0, i)) == SET
- && (include_called_routine
- || GET_CODE (SET_SRC (XVECEXP (body, 0, i))) != CALL))
- || GET_CODE (XVECEXP (body, 0, i)) == CLOBBER)
- mark_referenced_resources (SET_DEST (XVECEXP (body, 0, i)),
- res, 0);
- }
- else if (GET_CODE (body) == SEQUENCE)
- for (i = 0; i < XVECLEN (body, 0); i++)
- if (! (INSN_ANNULLED_BRANCH_P (XVECEXP (body, 0, 0))
- && INSN_FROM_TARGET_P (XVECEXP (body, 0, i))))
- mark_set_resources (XVECEXP (body, 0, i), res,
- include_called_routine);
-
-#ifdef AUTO_INC_DEC
- /* If any register are incremented or decremented in an address,
- they are set here. */
- for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
- if (REG_NOTE_KIND (note) == REG_INC)
- mark_referenced_resources (XEXP (note, 0), res, 0);
+#ifdef INSN_SETS_ARE_DELAYED
+ if (! include_delayed_effects
+ && INSN_SETS_ARE_DELAYED (x))
+ return;
#endif
-#ifdef PUSH_ROUNDING
- /* An insn that has a PRE_DEC on SP will not have a REG_INC note.
- Until we fix this correctly, consider all insns as modifying
- SP on such machines. So far, we don't have delay slot scheduling
- on any machines with PUSH_ROUNDING. */
- SET_HARD_REG_BIT (res->regs, STACK_POINTER_REGNUM);
-#endif
- return;
- }
+ x = PATTERN (x);
+ if (GET_CODE (x) != USE && GET_CODE (x) != CLOBBER)
+ goto restart;
+ return;
- default:
- abort ();
+ case SET:
+ /* If the source of a SET is a CALL, this is actually done by
+ the called routine. So only include it if we are to include the
+ effects of the calling routine. */
+
+ mark_set_resources (SET_DEST (x), res,
+ (include_delayed_effects
+ || GET_CODE (SET_SRC (x)) != CALL),
+ 0);
+
+ mark_set_resources (SET_SRC (x), res, 0, 0);
+ return;
+
+ case CLOBBER:
+ mark_set_resources (XEXP (x, 0), res, 1, 0);
+ return;
+
+ case SEQUENCE:
+ for (i = 0; i < XVECLEN (x, 0); i++)
+ if (! (INSN_ANNULLED_BRANCH_P (XVECEXP (x, 0, 0))
+ && INSN_FROM_TARGET_P (XVECEXP (x, 0, i))))
+ mark_set_resources (XVECEXP (x, 0, i), res, 0,
+ include_delayed_effects);
+ return;
+
+ case POST_INC:
+ case PRE_INC:
+ case POST_DEC:
+ case PRE_DEC:
+ mark_set_resources (XEXP (x, 0), res, 1, 0);
+ return;
+
+ case ZERO_EXTRACT:
+ mark_set_resources (XEXP (x, 0), res, in_dest, 0);
+ mark_set_resources (XEXP (x, 1), res, 0, 0);
+ mark_set_resources (XEXP (x, 2), res, 0, 0);
+ return;
+
+ case MEM:
+ if (in_dest)
+ {
+ res->memory = 1;
+ res->volatil = MEM_VOLATILE_P (x);
+ }
+
+ mark_set_resources (XEXP (x, 0), res, 0, 0);
+ return;
+
+ case REG:
+ if (in_dest)
+ for (i = 0; i < HARD_REGNO_NREGS (REGNO (x), GET_MODE (x)); i++)
+ SET_HARD_REG_BIT (res->regs, REGNO (x) + i);
+ return;
}
+
+ /* Process each sub-expression and flag what it needs. */
+ format_ptr = GET_RTX_FORMAT (code);
+ for (i = 0; i < GET_RTX_LENGTH (code); i++)
+ switch (*format_ptr++)
+ {
+ case 'e':
+ mark_set_resources (XEXP (x, i), res, in_dest, include_delayed_effects);
+ break;
+
+ case 'E':
+ for (j = 0; j < XVECLEN (x, i); j++)
+ mark_set_resources (XVECEXP (x, i, j), res, in_dest,
+ include_delayed_effects);
+ break;
+ }
}
\f
/* Return TRUE if this insn should stop the search for insn to fill delay
a large block of complex code. */
static int
-insn_references_resource_p (insn, res, include_called_routine)
+insn_references_resource_p (insn, res, include_delayed_effects)
register rtx insn;
register struct resources *res;
- int include_called_routine;
+ int include_delayed_effects;
{
struct resources insn_res;
CLEAR_RESOURCE (&insn_res);
- mark_referenced_resources (insn, &insn_res, include_called_routine);
+ mark_referenced_resources (insn, &insn_res, include_delayed_effects);
return resource_conflicts_p (&insn_res, res);
}
in front of mark_set_resources for details. */
static int
-insn_sets_resource_p (insn, res, include_called_routine)
+insn_sets_resource_p (insn, res, include_delayed_effects)
register rtx insn;
register struct resources *res;
- int include_called_routine;
+ int include_delayed_effects;
{
struct resources insn_sets;
CLEAR_RESOURCE (&insn_sets);
- mark_set_resources (insn, &insn_sets, include_called_routine);
+ mark_set_resources (insn, &insn_sets, 0, include_delayed_effects);
return resource_conflicts_p (&insn_sets, res);
}
\f
|| GET_CODE (PATTERN (insn)) == CLOBBER)))
insn = PREV_INSN (insn);
- if (GET_CODE (insn) == CODE_LABEL)
- end_of_function_label = insn;
+ /* When a target threads its epilogue we might already have a
+ suitable return insn. If so put a label before it for the
+ end_of_function_label. */
+ if (GET_CODE (insn) == BARRIER
+ && GET_CODE (PREV_INSN (insn)) == JUMP_INSN
+ && GET_CODE (PATTERN (PREV_INSN (insn))) == RETURN)
+ {
+ rtx temp = PREV_INSN (PREV_INSN (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. */
+ while (GET_CODE (temp) == USE)
+ temp = PREV_INSN (temp);
+
+ emit_label_after (end_of_function_label, temp);
+ }
+
+ else if (GET_CODE (insn) == CODE_LABEL)
+ end_of_function_label = insn;
else
{
/* Otherwise, make a new label and emit a RETURN and BARRIER,
#ifdef HAVE_return
if (HAVE_return)
{
- emit_jump_insn (gen_return ());
+ /* The return we make may have delay slots too. */
+ rtx insn = gen_return ();
+ insn = emit_jump_insn (insn);
emit_barrier ();
+ if (num_delay_slots (insn) > 0)
+ obstack_ptr_grow (&unfilled_slots_obstack, insn);
}
#endif
}
rtx insn;
rtx delay_list;
{
- /* If we have an empty list, just make a new list element. */
+ /* If we have an empty list, just make a new list element. If
+ INSN has it's block number recorded, clear it since we may
+ be moving the insn to a new block. */
+
if (delay_list == 0)
- return gen_rtx (INSN_LIST, VOIDmode, insn, 0);
+ {
+ struct target_info *tinfo;
+
+ for (tinfo = target_hash_table[INSN_UID (insn) % TARGET_HASH_PRIME];
+ tinfo; tinfo = tinfo->next)
+ if (tinfo->uid == INSN_UID (insn))
+ break;
+
+ if (tinfo)
+ tinfo->block = -1;
+
+ return gen_rtx (INSN_LIST, VOIDmode, insn, NULL_RTX);
+ }
/* Otherwise this must be an INSN_LIST. Add INSN to the end of the
list. */
return delay_list;
}
-
-#ifdef HAVE_cc0
-/* INSN uses CC0 and is being moved into a delay slot. Set up REG_CC_SETTER
- and REG_CC_USER notes so we can find it. */
-
-static void
-link_cc0_insns (insn)
- rtx insn;
-{
- rtx user = next_nonnote_insn (insn);
-
- if (GET_CODE (user) == INSN && GET_CODE (PATTERN (user)) == SEQUENCE)
- user = XVECEXP (PATTERN (user), 0, 0);
-
- REG_NOTES (user) = gen_rtx (INSN_LIST, REG_CC_SETTER, insn,
- REG_NOTES (user));
- REG_NOTES (insn) = gen_rtx (INSN_LIST, REG_CC_USER, user, REG_NOTES (insn));
-}
-#endif
\f
/* Delete INSN from the the delay slot of the insn that it is in. This may
produce an insn without anything in its delay slots. */
#ifdef HAVE_cc0
if (reg_mentioned_p (cc0_rtx, insn))
{
- rtx note = find_reg_note (insn, REG_CC_SETTER, 0);
+ rtx note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
/* If a reg-note was found, it points to an insn to set CC0. This
insn is in the delay list of some other insn. So delete it from
the delay list it was in. */
if (note)
{
- if (! FIND_REG_INC_NOTE (XEXP (note, 0), 0)
+ if (! FIND_REG_INC_NOTE (XEXP (note, 0), NULL_RTX)
&& sets_cc0_p (PATTERN (XEXP (note, 0))) == 1)
delete_from_delay_slot (XEXP (note, 0));
}
1. When a conditional branch skips over only one instruction,
use an annulling branch and put that insn in the delay slot.
- Use either a branch that annulls when the condition if true or
- invert the test with a branch that annulls when the condition is
+ Use either a branch that annuls when the condition if true or
+ invert the test with a branch that annuls when the condition is
false. This saves insns, since otherwise we must copy an insn
from the L1 target.
rtx next_trial = next_active_insn (trial);
rtx delay_list = 0;
rtx target_label;
+ int flags;
+
+ flags = get_jump_flags (insn, JUMP_LABEL (insn));
if (trial == 0
|| GET_CODE (trial) != INSN
|| GET_CODE (PATTERN (trial)) == SEQUENCE
|| recog_memoized (trial) < 0
- || (! eligible_for_annul_false (insn, 0, trial)
- && ! eligible_for_annul_true (insn, 0, trial)))
+ || (! eligible_for_annul_false (insn, 0, trial, flags)
+ && ! eligible_for_annul_true (insn, 0, trial, flags)))
return 0;
/* There are two cases where we are just executing one insn (we assume
&& (simplejump_p (next_trial)
|| GET_CODE (PATTERN (next_trial)) == RETURN)))
{
- if (eligible_for_annul_false (insn, 0, trial))
+ if (eligible_for_annul_false (insn, 0, trial, flags))
{
if (invert_jump (insn, JUMP_LABEL (insn)))
INSN_FROM_TARGET_P (trial) = 1;
- else if (! eligible_for_annul_true (insn, 0, trial))
+ else if (! eligible_for_annul_true (insn, 0, trial, flags))
return 0;
}
- delay_list = add_to_delay_list (trial, 0);
+ delay_list = add_to_delay_list (trial, NULL_RTX);
next_trial = next_active_insn (trial);
update_block (trial, trial);
delete_insn (trial);
target_label = JUMP_LABEL (next_trial);
if (target_label == 0)
target_label = find_end_label ();
- redirect_jump (insn, target_label);
+ reorg_redirect_jump (insn, target_label);
}
INSN_ANNULLED_BRANCH_P (insn) = 1;
}
#endif
\f
+
+/* Encode and return branch direction and prediction information for
+ INSN assuming it will jump to LABEL.
+
+ Non conditional branches return no direction information and
+ are predicted as very likely taken. */
+static int
+get_jump_flags (insn, label)
+ rtx insn, label;
+{
+ int flags;
+
+ /* get_jump_flags can be passed any insn with delay slots, these may
+ be INSNs, CALL_INSNs, or JUMP_INSNs. Only JUMP_INSNs have branch
+ direction information, and only if they are conditional jumps.
+
+ If LABEL is zero, then there is no way to determine the branch
+ direction. */
+ if (GET_CODE (insn) == JUMP_INSN
+ && condjump_p (insn)
+ && INSN_UID (insn) <= max_uid
+ && label != 0
+ && INSN_UID (label) <= max_uid)
+ flags
+ = (uid_to_ruid[INSN_UID (label)] > uid_to_ruid[INSN_UID (insn)])
+ ? ATTR_FLAG_forward : ATTR_FLAG_backward;
+ /* No valid direction information. */
+ else
+ flags = 0;
+
+ /* If insn is a conditional branch call mostly_true_jump to get
+ determine the branch prediction.
+
+ Non conditional branches are predicted as very likely taken. */
+ if (GET_CODE (insn) == JUMP_INSN
+ && condjump_p (insn))
+ {
+ int prediction;
+
+ prediction = mostly_true_jump (insn, get_branch_condition (insn, label));
+ switch (prediction)
+ {
+ case 2:
+ flags |= (ATTR_FLAG_very_likely | ATTR_FLAG_likely);
+ break;
+ case 1:
+ flags |= ATTR_FLAG_likely;
+ break;
+ case 0:
+ flags |= ATTR_FLAG_unlikely;
+ break;
+ case -1:
+ flags |= (ATTR_FLAG_very_unlikely | ATTR_FLAG_unlikely);
+ break;
+
+ default:
+ abort();
+ }
+ }
+ else
+ flags |= (ATTR_FLAG_very_likely | ATTR_FLAG_likely);
+
+ return flags;
+}
+
+/* Return 1 if DEST is a destination that will be branched to rarely (the
+ return point of a function); return 2 if DEST will be branched to very
+ rarely (a call to a function that doesn't return). Otherwise,
+ return 0. */
+
+static int
+rare_destination (insn)
+ rtx insn;
+{
+ int jump_count = 0;
+
+ for (; insn; insn = NEXT_INSN (insn))
+ {
+ if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == SEQUENCE)
+ insn = XVECEXP (PATTERN (insn), 0, 0);
+
+ switch (GET_CODE (insn))
+ {
+ case CODE_LABEL:
+ return 0;
+ case BARRIER:
+ /* A BARRIER can either be after a JUMP_INSN or a CALL_INSN. We
+ don't scan past JUMP_INSNs, so any barrier we find here must
+ have been after a CALL_INSN and hence mean the call doesn't
+ return. */
+ return 2;
+ case JUMP_INSN:
+ if (GET_CODE (PATTERN (insn)) == RETURN)
+ return 1;
+ else if (simplejump_p (insn)
+ && jump_count++ < 10)
+ insn = JUMP_LABEL (insn);
+ else
+ return 0;
+ }
+ }
+
+ /* If we got here it means we hit the end of the function. So this
+ is an unlikely destination. */
+
+ return 1;
+}
+
/* Return truth value of the statement that this branch
is mostly taken. If we think that the branch is extremely likely
to be taken, we return 2. If the branch is slightly more likely to be
- taken, return 1. Otherwise, return 0.
+ taken, return 1. If the branch is slightly less likely to be taken,
+ return 0 and if the branch is highly unlikely to be taken, return -1.
CONDITION, if non-zero, is the condition that JUMP_INSN is testing. */
{
rtx target_label = JUMP_LABEL (jump_insn);
rtx insn;
+ int rare_dest = rare_destination (target_label);
+ int rare_fallthrough = rare_destination (NEXT_INSN (jump_insn));
+
+ /* If this is a branch outside a loop, it is highly unlikely. */
+ if (GET_CODE (PATTERN (jump_insn)) == SET
+ && GET_CODE (SET_SRC (PATTERN (jump_insn))) == IF_THEN_ELSE
+ && ((GET_CODE (XEXP (SET_SRC (PATTERN (jump_insn)), 1)) == LABEL_REF
+ && LABEL_OUTSIDE_LOOP_P (XEXP (SET_SRC (PATTERN (jump_insn)), 1)))
+ || (GET_CODE (XEXP (SET_SRC (PATTERN (jump_insn)), 2)) == LABEL_REF
+ && LABEL_OUTSIDE_LOOP_P (XEXP (SET_SRC (PATTERN (jump_insn)), 2)))))
+ return -1;
+
+ if (target_label)
+ {
+ /* If this is the test of a loop, it is very likely true. We scan
+ backwards from the target label. If we find a NOTE_INSN_LOOP_BEG
+ before the next real insn, we assume the branch is to the top of
+ the loop. */
+ for (insn = PREV_INSN (target_label);
+ insn && GET_CODE (insn) == NOTE;
+ insn = PREV_INSN (insn))
+ if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
+ return 2;
+
+ /* If this is a jump to the test of a loop, it is likely true. We scan
+ forwards from the target label. If we find a NOTE_INSN_LOOP_VTOP
+ before the next real insn, we assume the branch is to the loop branch
+ test. */
+ for (insn = NEXT_INSN (target_label);
+ insn && GET_CODE (insn) == NOTE;
+ insn = PREV_INSN (insn))
+ if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_VTOP)
+ return 1;
+ }
- /* If this is a conditional return insn, assume it won't return. */
- if (target_label == 0)
- return 0;
-
- /* If TARGET_LABEL has no jumps between it and the end of the function,
- this is essentially a conditional return, so predict it as false. */
- for (insn = NEXT_INSN (target_label);
- insn && GET_CODE (insn) != JUMP_INSN;
- insn = NEXT_INSN (insn))
- ;
-
- if (insn == 0)
- return 0;
+ /* Look at the relative rarities of the fallthough and destination. If
+ they differ, we can predict the branch that way. */
- /* If this is the test of a loop, it is very likely true. We scan backwards
- from the target label. If we find a NOTE_INSN_LOOP_BEG before the next
- real insn, we assume the branch is to the top of the loop. */
- for (insn = PREV_INSN (target_label);
- insn && GET_CODE (insn) == NOTE;
- insn = PREV_INSN (insn))
- if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
+ switch (rare_fallthrough - rare_dest)
+ {
+ case -2:
+ return -1;
+ case -1:
+ return 0;
+ case 0:
+ break;
+ case 1:
+ return 1;
+ case 2:
return 2;
+ }
/* If we couldn't figure out what this jump was, assume it won't be
taken. This should be rare. */
/* Predict backward branches usually take, forward branches usually not. If
we don't know whether this is forward or backward, assume the branch
will be taken, since most are. */
- return (INSN_UID (jump_insn) > max_uid || INSN_UID (target_label) > max_uid
+ return (target_label == 0 || INSN_UID (jump_insn) > max_uid
+ || INSN_UID (target_label) > max_uid
|| (uid_to_ruid[INSN_UID (jump_insn)]
> uid_to_ruid[INSN_UID (target_label)]));;
}
return gen_rtx (reverse_condition (GET_CODE (XEXP (src, 0))),
GET_MODE (XEXP (src, 0)),
XEXP (XEXP (src, 0), 0), XEXP (XEXP (src, 0), 1));
+
+ return 0;
}
/* Return non-zero if CONDITION is more strict than the condition of
return comparison_dominates_p (code, other_code);
}
+
+/* Return non-zero if redirecting JUMP to NEWLABEL does not invalidate
+ any insns already in the delay slot of JUMP. */
+
+static int
+redirect_with_delay_slots_safe_p (jump, newlabel, seq)
+ rtx jump, newlabel, seq;
+{
+ int flags, slots, i;
+ rtx pat = PATTERN (seq);
+
+ /* Make sure all the delay slots of this jump would still
+ be valid after threading the jump. If they are still
+ valid, then return non-zero. */
+
+ flags = get_jump_flags (jump, newlabel);
+ for (i = 1; i < XVECLEN (pat, 0); i++)
+ if (! (
+#ifdef ANNUL_IFFALSE_SLOTS
+ (INSN_ANNULLED_BRANCH_P (jump)
+ && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
+ ? eligible_for_annul_false (jump, i - 1,
+ XVECEXP (pat, 0, i), flags) :
+#endif
+#ifdef ANNUL_IFTRUE_SLOTS
+ (INSN_ANNULLED_BRANCH_P (jump)
+ && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
+ ? eligible_for_annul_true (jump, i - 1,
+ XVECEXP (pat, 0, i), flags) :
+#endif
+ eligible_for_delay (jump, i -1, XVECEXP (pat, 0, i), flags)))
+ break;
+
+ return (i == XVECLEN (pat, 0));
+}
+
\f
/* INSN branches to an insn whose pattern SEQ is a SEQUENCE. Given that
the condition tested by INSN is CONDITION and the resources shown in
for (i = 1; i < XVECLEN (seq, 0); i++)
{
rtx trial = XVECEXP (seq, 0, i);
+ int flags;
if (insn_references_resource_p (trial, sets, 0)
|| insn_sets_resource_p (trial, needed, 0)
#ifdef HAVE_cc0
/* If TRIAL sets CC0, we can't copy it, so we can't steal this
delay list. */
- || find_reg_note (trial, REG_CC_USER, 0)
+ || find_reg_note (trial, REG_CC_USER, NULL_RTX)
#endif
/* If TRIAL is from the fallthrough code of an annulled branch insn
in SEQ, we cannot use it. */
if (redundant_insn_p (trial, insn, new_delay_list))
continue;
+ /* We will end up re-vectoring this branch, so compute flags
+ based on jumping to the new label. */
+ flags = get_jump_flags (insn, JUMP_LABEL (XVECEXP (seq, 0, 0)));
+
if (! must_annul
&& ((condition == const_true_rtx
|| (! insn_sets_resource_p (trial, other_needed, 0)
&& ! may_trap_p (PATTERN (trial)))))
- ? eligible_for_delay (insn, total_slots_filled, trial)
+ ? eligible_for_delay (insn, total_slots_filled, trial, flags)
: (must_annul = 1,
- eligible_for_annul_false (insn, total_slots_filled, trial)))
+ eligible_for_annul_false (insn, total_slots_filled, trial, flags)))
{
temp = copy_rtx (trial);
INSN_FROM_TARGET_P (temp) = 1;
int *pannul_p;
{
int i;
+ int flags;
+
+ flags = get_jump_flags (insn, JUMP_LABEL (insn));
/* We can't do anything if SEQ's delay insn isn't an
unconditional branch. */
&& ((condition == const_true_rtx
|| (! insn_sets_resource_p (trial, other_needed, 0)
&& ! may_trap_p (PATTERN (trial)))))
- ? eligible_for_delay (insn, *pslots_filled, trial)
+ ? eligible_for_delay (insn, *pslots_filled, trial, flags)
: (*pannul_p = 1,
- eligible_for_annul_true (insn, *pslots_filled, trial)))
+ eligible_for_annul_true (insn, *pslots_filled, trial, flags)))
{
delete_from_delay_slot (trial);
delay_list = add_to_delay_list (trial, delay_list);
struct resources set, needed;
rtx merged_insns = 0;
int i;
+ int flags;
+
+ flags = get_jump_flags (delay_insn, JUMP_LABEL (delay_insn));
CLEAR_RESOURCE (&needed);
CLEAR_RESOURCE (&set);
&& rtx_equal_p (PATTERN (next_to_match), PATTERN (trial))
/* Have to test this condition if annul condition is different
from (and less restrictive than) non-annulling one. */
- && eligible_for_delay (delay_insn, slot_number - 1, trial))
+ && eligible_for_delay (delay_insn, slot_number - 1, trial, flags))
{
next_trial = next_nonnote_insn (trial);
mark_referenced_resources (next_to_match, &needed, 1);
}
- mark_set_resources (trial, &set, 1);
+ mark_set_resources (trial, &set, 0, 1);
mark_referenced_resources (trial, &needed, 1);
}
&& ! sets_cc0_p (PATTERN (dtrial))
#endif
&& rtx_equal_p (PATTERN (next_to_match), PATTERN (dtrial))
- && eligible_for_delay (delay_insn, slot_number - 1, dtrial))
+ && eligible_for_delay (delay_insn, slot_number - 1, dtrial, flags))
{
if (! annul_p)
{
if (GET_CODE (trial) == CODE_LABEL)
return 0;
- if (GET_CODE (trial) != INSN && GET_CODE (trial) != JUMP_INSN
- && GET_CODE (trial) != JUMP_INSN)
+ if (GET_RTX_CLASS (GET_CODE (trial)) != 'i')
continue;
pat = PATTERN (trial);
if (GET_CODE (pat) == SEQUENCE)
{
- /* Stop for a CALL and its delay slots because it difficult to track
- its resource needs correctly. */
+ /* Stop for a CALL and its delay slots because it is difficult to
+ track its resource needs correctly. */
if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN)
return 0;
+ /* Stop for an INSN or JUMP_INSN with delayed effects and its delay
+ slots because it is difficult to track its resource needs
+ correctly. */
+
+#ifdef INSN_SETS_ARE_DELAYED
+ if (INSN_SETS_ARE_DELAYED (XVECEXP (pat, 0, 0)))
+ return 0;
+#endif
+
+#ifdef INSN_REFERENCES_ARE_DELAYED
+ if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat, 0, 0)))
+ return 0;
+#endif
+
+ /* See if any of the insns in the delay slot match, updating
+ resource requirements as we go. */
for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
if (GET_CODE (XVECEXP (pat, 0, i)) == GET_CODE (insn)
&& rtx_equal_p (PATTERN (XVECEXP (pat, 0, i)), ipat))
CLEAR_RESOURCE (&needed);
CLEAR_RESOURCE (&set);
- mark_set_resources (insn, &set, 1);
+ mark_set_resources (insn, &set, 0, 1);
mark_referenced_resources (insn, &needed, 1);
/* If TARGET is a SEQUENCE, get the main insn. */
if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN)
return 0;
+ /* If this this is an INSN or JUMP_INSN with delayed effects, it
+ is hard to track the resource needs properly, so give up. */
+
+#ifdef INSN_SETS_ARE_DELAYED
+ if (INSN_SETS_ARE_DELAYED (XVECEXP (pat, 0, 0)))
+ return 0;
+#endif
+
+#ifdef INSN_REFERENCES_ARE_DELAYED
+ if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat, 0, 0)))
+ return 0;
+#endif
+
/* See if any of the insns in the delay slot match, updating
resource requirements as we go. */
for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
if (b != -1)
bb_ticks[b]++;
}
+
+/* Similar to REDIRECT_JUMP except that we update the BB_TICKS entry for
+ the basic block containing the jump. */
+
+static int
+reorg_redirect_jump (jump, nlabel)
+ rtx jump;
+ rtx nlabel;
+{
+ int b = find_basic_block (jump);
+
+ if (b != -1)
+ bb_ticks[b]++;
+
+ return redirect_jump (jump, nlabel);
+}
+
+/* Called when INSN is being moved forward into a delay slot of DELAYED_INSN.
+ We check every instruction between INSN and DELAYED_INSN for REG_DEAD notes
+ that reference values used in INSN. If we find one, then we move the
+ REG_DEAD note to INSN.
+
+ This is needed to handle the case where an later insn (after INSN) has a
+ REG_DEAD note for a register used by INSN, and this later insn subsequently
+ gets moved before a CODE_LABEL because it is a redundant insn. In this
+ case, mark_target_live_regs may be confused into thinking the register
+ is dead because it sees a REG_DEAD note immediately before a CODE_LABEL. */
+
+static void
+update_reg_dead_notes (insn, delayed_insn)
+ rtx insn, delayed_insn;
+{
+ rtx p, link, next;
+
+ for (p = next_nonnote_insn (insn); p != delayed_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_referenced_p (XEXP (link, 0), PATTERN (insn)))
+ {
+ /* Move the REG_DEAD note from P to INSN. */
+ remove_note (p, link);
+ XEXP (link, 1) = REG_NOTES (insn);
+ REG_NOTES (insn) = link;
+ }
+ }
+}
\f
/* Marks registers possibly live at the current place being scanned by
mark_target_live_regs. Used only by next two function. */
struct target_info *tinfo;
rtx insn, next;
rtx jump_insn = 0;
+ rtx jump_target;
HARD_REG_SET scratch;
struct resources set, needed;
int jump_count = 0;
if (b != -1)
{
regset regs_live = basic_block_live_at_start[b];
- int offset, bit, j;
+ int offset, j;
+ REGSET_ELT_TYPE bit;
int regno;
rtx start_insn, stop_insn;
for (offset = 0, i = 0; offset < regset_size; offset++)
{
if (regs_live[offset] == 0)
- i += HOST_BITS_PER_INT;
+ i += REGSET_ELT_BITS;
else
for (bit = 1; bit && i < max_regno; bit <<= 1, i++)
if ((regs_live[offset] & bit)
/* If this insn is a USE made by update_block, we care about the
underlying insn. */
if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
- && (GET_CODE (XEXP (PATTERN (insn), 0)) == INSN
- || GET_CODE (XEXP (PATTERN (insn), 0)) == CALL_INSN
- || GET_CODE (XEXP (PATTERN (insn), 0)) == JUMP_INSN))
+ && GET_RTX_CLASS (GET_CODE (XEXP (PATTERN (insn), 0))) == 'i')
real_insn = XEXP (PATTERN (insn), 0);
if (GET_CODE (real_insn) == CALL_INSN)
}
}
- if (GET_CODE (real_insn) == CODE_LABEL)
+ else if (GET_CODE (real_insn) == CODE_LABEL)
{
/* A label clobbers the pending dead registers since neither
reload nor jump will propagate a value across a label. */
AND_COMPL_HARD_REG_SET (current_live_regs, pending_dead_regs);
CLEAR_HARD_REG_SET (pending_dead_regs);
}
+
+ /* The beginning of the epilogue corresponds to the end of the
+ RTL chain when there are no epilogue insns. Certain resources
+ are implicitly required at that point. */
+ else if (GET_CODE (real_insn) == NOTE
+ && NOTE_LINE_NUMBER (real_insn) == NOTE_INSN_EPILOGUE_BEG)
+ IOR_HARD_REG_SET (current_live_regs, start_of_epilogue_needs.regs);
}
COPY_HARD_REG_SET (res->regs, current_live_regs);
for (insn = target; insn; insn = next)
{
- rtx main_insn = insn;
+ rtx this_jump_insn = insn;
next = NEXT_INSN (insn);
switch (GET_CODE (insn))
continue;
case INSN:
- if (GET_CODE (PATTERN (insn)) == USE
- || GET_CODE (PATTERN (insn)) == CLOBBER)
+ 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;
- if (GET_CODE (PATTERN (insn)) == SEQUENCE)
- main_insn = XVECEXP (PATTERN (insn), 0, 0);
+ 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 (main_insn) == JUMP_INSN)
+ if (GET_CODE (this_jump_insn) == JUMP_INSN)
{
if (jump_count++ < 10
- && (simplejump_p (main_insn)
- || GET_CODE (PATTERN (main_insn)) == RETURN))
+ && (simplejump_p (this_jump_insn)
+ || GET_CODE (PATTERN (this_jump_insn)) == RETURN))
{
- next = next_active_insn (JUMP_LABEL (main_insn));
+ next = next_active_insn (JUMP_LABEL (this_jump_insn));
if (jump_insn == 0)
- jump_insn = insn;
+ {
+ jump_insn = insn;
+ jump_target = JUMP_LABEL (this_jump_insn);
+ }
}
else
break;
}
mark_referenced_resources (insn, &needed, 1);
- mark_set_resources (insn, &set, 1);
+ mark_set_resources (insn, &set, 0, 1);
COPY_HARD_REG_SET (scratch, set.regs);
AND_COMPL_HARD_REG_SET (scratch, needed.regs);
if (jump_insn && jump_count < 10)
{
- rtx jump_target = (GET_CODE (jump_insn) == INSN
- ? JUMP_LABEL (XVECEXP (PATTERN (jump_insn), 0, 0))
- : JUMP_LABEL (jump_insn));
struct resources new_resources;
rtx stop_insn = next_active_insn (jump_insn);
AND_COMPL_HARD_REG_SET (scratch, set.regs);
IOR_HARD_REG_SET (new_resources.regs, scratch);
- mark_set_resources (insn, &set, 1);
+ mark_set_resources (insn, &set, 0, 1);
}
AND_HARD_REG_SET (res->regs, new_resources.regs);
static void
fill_simple_delay_slots (first, non_jumps_p)
rtx first;
+ int non_jumps_p;
{
register rtx insn, pat, trial, next_trial;
- register int i;
+ 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;
for (i = 0; i < num_unfilled_slots; i++)
{
+ int flags;
/* Get the next insn to fill. If it has already had any slots assigned,
we can't do anything with it. Maybe we'll improve this later. */
|| (GET_CODE (insn) == JUMP_INSN && non_jumps_p)
|| (GET_CODE (insn) != JUMP_INSN && ! non_jumps_p))
continue;
-
+
+ if (GET_CODE (insn) == JUMP_INSN)
+ flags = get_jump_flags (insn, JUMP_LABEL (insn));
+ else
+ flags = get_jump_flags (insn, NULL_RTX);
slots_to_fill = num_delay_slots (insn);
if (slots_to_fill == 0)
abort ();
/* This insn needs, or can use, some delay slots. SLOTS_TO_FILL
- says how many. After initialization, scan backwards from the
- insn to search for a potential delay-slot candidate. Stop
- searching when a label or jump is hit.
-
+ says how many. After initialization, first try optimizing
+
+ call _foo call _foo
+ nop add %o7,.-L1,%o7
+ b,a L1
+ nop
+
+ If this case applies, the delay slot of the call is filled with
+ the unconditional jump. This is done first to avoid having the
+ delay slot of the call filled in the backward scan. Also, since
+ the unconditional jump is likely to also have a delay slot, that
+ insn must exist when it is subsequently scanned.
+
+ This is tried on each insn with delay slots as some machines
+ have insns which perform calls, but are not represented as
+ CALL_INSNs. */
+
+ slots_filled = 0;
+ delay_list = 0;
+
+ if ((trial = next_active_insn (insn))
+ && GET_CODE (trial) == JUMP_INSN
+ && simplejump_p (trial)
+ && eligible_for_delay (insn, slots_filled, trial, flags)
+ && no_labels_between_p (insn, trial))
+ {
+ slots_filled++;
+ delay_list = add_to_delay_list (trial, delay_list);
+ /* 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;
+ {
+ rtx next = NEXT_INSN (trial);
+ rtx prev = PREV_INSN (trial);
+ if (prev)
+ NEXT_INSN (prev) = next;
+ if (next)
+ PREV_INSN (next) = prev;
+ }
+ }
+
+ /* Now, scan backwards from the insn to search for a potential
+ delay-slot candidate. Stop searching when a label or jump is hit.
+
For each candidate, if it is to go into the delay slot (moved
forward in execution sequence), it must not need or set any resources
that were set by later insns and must not set any resources that
(in which case the called routine, not the insn itself, is doing
the setting). */
- slots_filled = 0;
- delay_list = 0;
- CLEAR_RESOURCE (&needed);
- CLEAR_RESOURCE (&set);
- mark_set_resources (insn, &set, 0);
- mark_referenced_resources (insn, &needed, 0);
-
- for (trial = prev_nonnote_insn (insn); ! stop_search_p (trial, 1);
- trial = next_trial)
+ if (slots_filled < slots_to_fill)
{
- next_trial = prev_nonnote_insn (trial);
+ CLEAR_RESOURCE (&needed);
+ CLEAR_RESOURCE (&set);
+ mark_set_resources (insn, &set, 0, 0);
+ mark_referenced_resources (insn, &needed, 0);
- /* This must be an INSN or CALL_INSN. */
- pat = PATTERN (trial);
+ for (trial = prev_nonnote_insn (insn); ! stop_search_p (trial, 1);
+ trial = next_trial)
+ {
+ next_trial = prev_nonnote_insn (trial);
- /* USE and CLOBBER at this level was just for flow; ignore it. */
- if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
- continue;
+ /* This must be an INSN or CALL_INSN. */
+ pat = PATTERN (trial);
- /* Check for resource conflict first, to avoid unnecessary
- splitting. */
- if (! insn_references_resource_p (trial, &set, 1)
- && ! insn_sets_resource_p (trial, &set, 1)
- && ! insn_sets_resource_p (trial, &needed, 1)
+ /* USE and CLOBBER at this level was just for flow; ignore it. */
+ if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
+ continue;
+
+ /* Check for resource conflict first, to avoid unnecessary
+ splitting. */
+ if (! insn_references_resource_p (trial, &set, 1)
+ && ! insn_sets_resource_p (trial, &set, 1)
+ && ! insn_sets_resource_p (trial, &needed, 1)
#ifdef HAVE_cc0
- /* Can't separate set of cc0 from its use. */
- && ! (reg_mentioned_p (cc0_rtx, pat)
- && ! sets_cc0_p (cc0_rtx, pat))
+ /* Can't separate set of cc0 from its use. */
+ && ! (reg_mentioned_p (cc0_rtx, pat)
+ && ! sets_cc0_p (cc0_rtx, pat))
#endif
- )
- {
- trial = try_split (pat, trial, 1);
- next_trial = prev_nonnote_insn (trial);
- if (eligible_for_delay (insn, slots_filled, trial))
+ )
{
- /* In this case, we are searching backward, so if we
- find insns to put on the delay list, we want
- to put them at the head, rather than the
- tail, of the list. */
-
- delay_list = gen_rtx (INSN_LIST, VOIDmode,
- trial, delay_list);
- update_block (trial, trial);
- delete_insn (trial);
- if (slots_to_fill == ++slots_filled)
- break;
- continue;
+ trial = try_split (pat, trial, 1);
+ next_trial = prev_nonnote_insn (trial);
+ if (eligible_for_delay (insn, slots_filled, trial, flags))
+ {
+ /* In this case, we are searching backward, so if we
+ find insns to put on the delay list, we want
+ to put them at the head, rather than the
+ tail, of the list. */
+
+ update_reg_dead_notes (trial, insn);
+ delay_list = gen_rtx (INSN_LIST, VOIDmode,
+ trial, delay_list);
+ update_block (trial, trial);
+ delete_insn (trial);
+ if (slots_to_fill == ++slots_filled)
+ break;
+ continue;
+ }
}
- }
- mark_set_resources (trial, &set, 1);
- mark_referenced_resources (trial, &needed, 1);
+ mark_set_resources (trial, &set, 0, 1);
+ mark_referenced_resources (trial, &needed, 1);
+ }
}
- if (slots_filled == slots_to_fill)
- /* happy. */ ;
-
/* If all needed slots haven't been filled, we come here. */
/* Try to optimize case of jumping around a single insn. */
#if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
- else if (delay_list == 0
- && GET_CODE (insn) == JUMP_INSN && condjump_p (insn))
+ if (slots_filled != slots_to_fill
+ && delay_list == 0
+ && GET_CODE (insn) == JUMP_INSN && condjump_p (insn))
{
delay_list = optimize_skip (insn);
if (delay_list)
}
#endif
- /* @@ This would be a good place to optimize:
-
- call _foo call _foo
- nop add %o7,.-L1,%o7
- b,a L1
- nop
-
- Someday... */
-
/* Try to get insns from beyond the insn needing the delay slot.
These insns can neither set or reference resources set in insns being
skipped, cannot set resources in the insn being skipped, and, if this
later unconditional jump branches to. In that case, we don't
care about the number of uses of our label. */
- else if (GET_CODE (insn) != JUMP_INSN
- || (condjump_p (insn) && ! simplejump_p (insn)
- && JUMP_LABEL (insn) != 0))
+ if (slots_filled != slots_to_fill
+ && (GET_CODE (insn) != JUMP_INSN
+ || (condjump_p (insn) && ! simplejump_p (insn)
+ && JUMP_LABEL (insn) != 0)))
{
rtx target = 0;
int maybe_never = 0;
if (GET_CODE (insn) == CALL_INSN)
{
- mark_set_resources (insn, &set, 1);
+ mark_set_resources (insn, &set, 0, 1);
mark_referenced_resources (insn, &needed, 1);
maybe_never = 1;
}
- else if (GET_CODE (insn) == JUMP_INSN)
+ else
{
- /* Get our target and show how many more uses we want to
- see before we hit the label. */
- target = JUMP_LABEL (insn);
- target_uses = LABEL_NUSES (target) - 1;
+ mark_set_resources (insn, &set, 0, 1);
+ mark_referenced_resources (insn, &needed, 1);
+ if (GET_CODE (insn) == JUMP_INSN)
+ {
+ /* Get our target and show how many more uses we want to
+ see before we hit the label. */
+ target = JUMP_LABEL (insn);
+ target_uses = LABEL_NUSES (target) - 1;
+ }
+
}
for (trial = next_nonnote_insn (insn); trial; trial = next_trial)
#endif
&& ! (maybe_never && may_trap_p (pat))
&& (trial = try_split (pat, trial, 0))
- && eligible_for_delay (insn, slots_filled, trial))
+ && eligible_for_delay (insn, slots_filled, trial, flags))
{
next_trial = next_nonnote_insn (trial);
delay_list = add_to_delay_list (trial, delay_list);
continue;
}
- mark_set_resources (trial, &set, 1);
+ mark_set_resources (trial, &set, 0, 1);
mark_referenced_resources (trial, &needed, 1);
/* Ensure we don't put insns between the setting of cc and the
&& ! insn_sets_resource_p (next_trial, &set, 1)
&& ! insn_sets_resource_p (next_trial, &needed, 1)
#ifdef HAVE_cc0
- && ! (reg_mentioned_p (cc0_rtx, PATTERN (next_trial))
- && ! sets_cc0_p (PATTERN (next_trial)))
+ && ! reg_mentioned_p (cc0_rtx, PATTERN (next_trial))
#endif
&& ! (maybe_never && may_trap_p (PATTERN (next_trial)))
&& (next_trial = try_split (PATTERN (next_trial), next_trial, 0))
- && eligible_for_delay (insn, slots_filled, next_trial))
+ && eligible_for_delay (insn, slots_filled, next_trial, flags))
{
rtx new_label = next_active_insn (next_trial);
delay_list
= add_to_delay_list (copy_rtx (next_trial), delay_list);
slots_filled++;
- redirect_jump (trial, new_label);
+ reorg_redirect_jump (trial, new_label);
/* If we merged because we both jumped to the same place,
redirect the original insn also. */
if (target)
- redirect_jump (insn, new_label);
+ reorg_redirect_jump (insn, new_label);
}
}
}
}
- mark_set_resources (trial, &set, 1);
+ mark_set_resources (trial, &set, 0, 1);
mark_referenced_resources (trial, &needed, 1);
}
rtx trial;
int lose = 0;
int must_annul = 0;
+ int flags;
/* Validate our arguments. */
if ((condition == const_true_rtx && ! thread_if_true)
|| (! own_thread && ! thread_if_true))
abort ();
+ flags = get_jump_flags (insn, JUMP_LABEL (insn));
+
/* If our thread is the end of subroutine, we can't get any delay
insns from that. */
if (thread == 0)
update THREAD and NEW_THREAD if it is done in the loop below. Also
initialize NEW_THREAD. */
- new_thread = thread = try_split (PATTERN (thread), thread);
+ new_thread = thread = try_split (PATTERN (thread), thread, 0);
/* Scan insns at THREAD. We are looking for an insn that can be removed
from THREAD (it neither sets nor references resources that were set
! stop_search_p (trial, ! thread_if_true) && (! lose || own_thread);
trial = next_nonnote_insn (trial))
{
- rtx pat;
+ rtx pat, old_trial;
/* If we have passed a label, we no longer own this thread. */
if (GET_CODE (trial) == CODE_LABEL)
|| (! insn_sets_resource_p (trial, &opposite_needed, 1)
&& ! may_trap_p (pat)))
{
+ old_trial = trial;
trial = try_split (pat, trial, 0);
+ if (new_thread == old_trial)
+ new_thread = trial;
pat = PATTERN (trial);
- if (eligible_for_delay (insn, *pslots_filled, trial))
+ if (eligible_for_delay (insn, *pslots_filled, trial, flags))
goto winner;
}
else if (0
#endif
)
{
+ old_trial = trial;
trial = try_split (pat, trial, 0);
+ if (new_thread == old_trial)
+ new_thread = trial;
pat = PATTERN (trial);
if ((thread_if_true
- ? eligible_for_annul_false (insn, *pslots_filled, trial)
- : eligible_for_annul_true (insn, *pslots_filled, trial)))
+ ? eligible_for_annul_false (insn, *pslots_filled, trial, flags)
+ : eligible_for_annul_true (insn, *pslots_filled, trial, flags)))
{
rtx temp;
/* This insn can't go into a delay slot. */
lose = 1;
- mark_set_resources (trial, &set, 1);
+ mark_set_resources (trial, &set, 0, 1);
mark_referenced_resources (trial, &needed, 1);
/* Ensure we don't put insns between the setting of cc and the comparison
We could check for more complex cases than those tested below,
but it doesn't seem worth it. It might also be a good idea to try
- to swap the two insns. That might do better. */
+ to swap the two insns. That might do better.
+
+ We can't do this if the next insn modifies our destination, because
+ that would make the replacement into the insn invalid. We also can't
+ do this if it modifies our source, because it might be an earlyclobber
+ operand. This latter test also prevents updating the contents of
+ a PRE_INC. */
if (GET_CODE (trial) == INSN && GET_CODE (pat) == SET
&& GET_CODE (SET_SRC (pat)) == REG
&& GET_CODE (SET_DEST (pat)) == REG)
{
rtx next = next_nonnote_insn (trial);
- int our_dest = REGNO (SET_DEST (pat));
if (next && GET_CODE (next) == INSN
- && GET_CODE (PATTERN (next)) == SET
- && GET_CODE (SET_DEST (PATTERN (next))) == REG
- && REGNO (SET_DEST (PATTERN (next))) != our_dest
- && refers_to_regno_p (our_dest, our_dest + 1,
- SET_SRC (PATTERN (next)), 0))
+ && GET_CODE (PATTERN (next)) != USE
+ && ! reg_set_p (SET_DEST (pat), next)
+ && ! reg_set_p (SET_SRC (pat), next)
+ && reg_referenced_p (SET_DEST (pat), PATTERN (next)))
validate_replace_rtx (SET_DEST (pat), SET_SRC (pat), next);
}
}
pat = PATTERN (trial);
if (GET_CODE (trial) != INSN || GET_CODE (pat) != SET
- || ! eligible_for_delay (insn, 0, trial))
+ || ! eligible_for_delay (insn, 0, trial, flags))
return 0;
dest = SET_DEST (pat), src = SET_SRC (pat);
if (thread_if_true)
INSN_FROM_TARGET_P (ninsn) = 1;
- delay_list = add_to_delay_list (ninsn, 0);
+ delay_list = add_to_delay_list (ninsn, NULL_RTX);
(*pslots_filled)++;
}
}
if (new_thread && GET_CODE (new_thread) == JUMP_INSN
&& (simplejump_p (new_thread)
|| GET_CODE (PATTERN (new_thread)) == RETURN))
- new_thread = follow_jumps (JUMP_LABEL (new_thread), 1);
+ new_thread = follow_jumps (JUMP_LABEL (new_thread));
if (new_thread == 0)
label = find_end_label ();
else
label = get_label_before (new_thread);
- redirect_jump (insn, label);
+ reorg_redirect_jump (insn, label);
}
return delay_list;
else
{
fallthrough_insn = next_active_insn (insn);
- own_fallthrough = own_thread_p (NEXT_INSN (insn), 0, 1);
+ own_fallthrough = own_thread_p (NEXT_INSN (insn), NULL_RTX, 1);
prediction = mostly_true_jump (insn, condition);
}
target, then our fallthrough insns. If it is not, expected to branch,
try the other order. */
- if (prediction)
+ if (prediction > 0)
{
delay_list
= fill_slots_from_thread (insn, condition, insn_at_target,
the next insn, or jumps to a label that is not the last of a
group of consecutive labels. */
if (GET_CODE (insn) == JUMP_INSN
+ && condjump_p (insn)
&& (target_label = JUMP_LABEL (insn)) != 0)
{
- target_label = follow_jumps (target_label, 1);
+ target_label = follow_jumps (target_label);
target_label = prev_label (next_active_insn (target_label));
+ if (target_label == 0)
+ target_label = find_end_label ();
+
if (next_active_insn (target_label) == next)
{
delete_jump (insn);
}
if (target_label != JUMP_LABEL (insn))
- redirect_jump (insn,
- target_label ? target_label : find_end_label ());
+ reorg_redirect_jump (insn, target_label);
/* See if this jump branches around a unconditional jump.
If so, invert this jump and point it to the target of the
&& (other = prev_active_insn (insn)) != 0
&& condjump_p (other)
&& no_labels_between_p (other, insn)
- && ! mostly_true_jump (other,
- get_branch_condition (other,
- JUMP_LABEL (other))))
+ && 0 < mostly_true_jump (other,
+ get_branch_condition (other,
+ JUMP_LABEL (other))))
{
rtx other_target = JUMP_LABEL (other);
+ target_label = JUMP_LABEL (insn);
/* Increment the count of OTHER_TARGET, so it doesn't get deleted
as we move the label. */
++LABEL_NUSES (other_target);
if (invert_jump (other, target_label))
- redirect_jump (insn, other_target);
+ reorg_redirect_jump (insn, other_target);
if (other_target)
--LABEL_NUSES (other_target);
{
/* If this jump goes to another unconditional jump, thread it, but
don't convert a jump into a RETURN here. */
- trial = follow_jumps (target_label, 1);
+ trial = follow_jumps (target_label);
trial = prev_label (next_active_insn (trial));
if (trial == 0 && target_label != 0)
trial = find_end_label ();
- if (trial != target_label)
+ if (trial != target_label
+ && redirect_with_delay_slots_safe_p (delay_insn, trial, insn))
{
- redirect_jump (delay_insn, trial);
+ reorg_redirect_jump (delay_insn, trial);
target_label = trial;
}
target_label = find_end_label ();
else
target_label = get_label_before (trial);
- redirect_jump (delay_insn, target_label);
+ reorg_redirect_jump (delay_insn, target_label);
next = insn;
continue;
}
target_label = JUMP_LABEL (XVECEXP (PATTERN (trial), 0, 0));
if (target_label == 0)
target_label = find_end_label ();
- redirect_jump (delay_insn, target_label);
- next = insn;
- continue;
+
+ if (redirect_with_delay_slots_safe_p (delay_insn, target_label,
+ insn))
+ {
+ reorg_redirect_jump (delay_insn, target_label);
+ next = insn;
+ continue;
+ }
}
}
/* If the last insn in the delay slot sets CC0 for some insn,
various code assumes that it is in a delay slot. We could
put it back where it belonged and delete the register notes,
- but it doesn't seem worhwhile in this uncommon case. */
+ but it doesn't seem worthwhile in this uncommon case. */
&& ! find_reg_note (XVECEXP (pat, 0, XVECLEN (pat, 0) - 1),
- REG_CC_USER, 0)
+ REG_CC_USER, NULL_RTX)
#endif
)
{
+ int i;
+
/* All this insn does is execute its delay list and jump to the
following insn. So delete the jump and just execute the delay
list insns.
This allows the count of the jump target to be properly
decremented. */
+ /* Clear the from target bit, since these insns are no longer
+ in delay slots. */
+ for (i = 0; i < XVECLEN (pat, 0); i++)
+ INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)) = 0;
+
trial = PREV_INSN (insn);
delete_insn (insn);
emit_insn_after (pat, trial);
continue;
}
+ /* See if this is an unconditional jump around a single insn which is
+ identical to the one in its delay slot. In this case, we can just
+ delete the branch and the insn in its delay slot. */
+ if (next && GET_CODE (next) == INSN
+ && prev_label (next_active_insn (next)) == target_label
+ && simplejump_p (insn)
+ && XVECLEN (pat, 0) == 2
+ && rtx_equal_p (PATTERN (next), PATTERN (XVECEXP (pat, 0, 1))))
+ {
+ delete_insn (insn);
+ continue;
+ }
+
/* See if this jump (with its delay slots) branches around another
jump (without delay slots). If so, invert this jump and point
it to the target of the second jump. We cannot do this for
if (label == 0)
label = find_end_label ();
- /* Be careful how we do this to avoid deleting code or labels
- that are momentarily dead. See similar optimization in jump.c */
- if (old_label)
- ++LABEL_NUSES (old_label);
-
- if (invert_jump (delay_insn, label))
+ if (redirect_with_delay_slots_safe_p (delay_insn, label, insn))
{
- delete_insn (next);
- next = insn;
- }
+ /* Be careful how we do this to avoid deleting code or labels
+ that are momentarily dead. See similar optimization in
+ jump.c */
+ if (old_label)
+ ++LABEL_NUSES (old_label);
- if (old_label && --LABEL_NUSES (old_label) == 0)
- delete_insn (old_label);
- continue;
+ if (invert_jump (delay_insn, label))
+ {
+ delete_insn (next);
+ next = insn;
+ }
+
+ if (old_label && --LABEL_NUSES (old_label) == 0)
+ delete_insn (old_label);
+ continue;
+ }
}
/* If we own the thread opposite the way this insn branches, see if we
for (insn = first; insn; insn = NEXT_INSN (insn))
{
+ int flags;
+
/* Only look at filled JUMP_INSNs that go to the end of function
label. */
if (GET_CODE (insn) != INSN
/* If we can't make the jump into a RETURN, redirect it to the best
RETURN and go on to the next insn. */
- if (! redirect_jump (jump_insn, 0))
+ if (! reorg_redirect_jump (jump_insn, NULL_RTX))
{
- redirect_jump (jump_insn, real_return_label);
+ reorg_redirect_jump (jump_insn, real_return_label);
continue;
}
It can if it has more or an equal number of slots and the contents
of each is valid. */
+ flags = get_jump_flags (jump_insn, JUMP_LABEL (jump_insn));
slots = num_delay_slots (jump_insn);
if (slots >= XVECLEN (pat, 0) - 1)
{
(INSN_ANNULLED_BRANCH_P (jump_insn)
&& INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
? eligible_for_annul_false (jump_insn, i - 1,
- XVECEXP (pat, 0, i)) :
+ XVECEXP (pat, 0, i), flags) :
#endif
#ifdef ANNUL_IFTRUE_SLOTS
(INSN_ANNULLED_BRANCH_P (jump_insn)
&& ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
? eligible_for_annul_true (jump_insn, i - 1,
- XVECEXP (pat, 0, i)) :
+ XVECEXP (pat, 0, i), flags) :
#endif
- eligible_for_delay (jump_insn, i -1, XVECEXP (pat, 0, i))))
+ eligible_for_delay (jump_insn, i -1, XVECEXP (pat, 0, i), flags)))
break;
}
else
else
/* It is probably more efficient to keep this with its current
delay slot as a branch to a RETURN. */
- redirect_jump (jump_insn, real_return_label);
+ reorg_redirect_jump (jump_insn, real_return_label);
}
/* Now delete REAL_RETURN_LABEL if we never used it. Then try to fill any
rtx first;
FILE *file;
{
- rtx insn, next;
+ rtx insn, next, epilogue_insn = 0;
int i;
#if 0
int old_flag_no_peephole = flag_no_peephole;
flag_no_peephole = old_flag_no_peephole;
#endif
+ /* If the current function has no insns other than the prologue and
+ epilogue, then do not try to fill any delay slots. */
+ if (n_basic_blocks == 0)
+ return;
+
/* Find the highest INSN_UID and allocate and initialize our map from
INSN_UID's to position in code. */
for (max_uid = 0, insn = first; insn; insn = NEXT_INSN (insn))
- if (INSN_UID (insn) > max_uid)
- max_uid = INSN_UID (insn);
+ {
+ if (INSN_UID (insn) > max_uid)
+ max_uid = INSN_UID (insn);
+ if (GET_CODE (insn) == NOTE
+ && NOTE_LINE_NUMBER (insn) == NOTE_INSN_EPILOGUE_BEG)
+ epilogue_insn = insn;
+ }
uid_to_ruid = (int *) alloca ((max_uid + 1) * sizeof (int *));
for (i = 0, insn = first; insn; i++, insn = NEXT_INSN (insn))
function. The condition code never is and memory always is. If the
frame pointer is needed, it is and so is the stack pointer unless
EXIT_IGNORE_STACK is non-zero. If the frame pointer is not needed, the
- stack pointer is. In addition, registers used to return the function
- value are needed. */
+ stack pointer is. Registers used to return the function value are
+ needed. Registers holding global variables are needed. */
end_of_function_needs.cc = 0;
end_of_function_needs.memory = 1;
if (current_function_return_rtx != 0
&& GET_CODE (current_function_return_rtx) == REG)
mark_referenced_resources (current_function_return_rtx,
- &end_of_function_needs, 0);
+ &end_of_function_needs, 1);
+
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ if (global_regs[i])
+ SET_HARD_REG_BIT (end_of_function_needs.regs, i);
+
+ /* The registers required to be live at the end of the function are
+ represented in the flow information as being dead just prior to
+ reaching the end of the function. For example, the return of a value
+ might be represented by a USE of the return register immediately
+ followed by an unconditional jump to the return label where the
+ return label is the end of the RTL chain. The end of the RTL chain
+ is then taken to mean that the return register is live.
+
+ This sequence is no longer maintained when epilogue instructions are
+ added to the RTL chain. To reconstruct the original meaning, the
+ start of the epilogue (NOTE_INSN_EPILOGUE_BEG) is regarded as the
+ point where these registers become live (start_of_epilogue_needs).
+ If epilogue instructions are present, the registers set by those
+ instructions won't have been processed by flow. Thus, those
+ registers are additionally required at the end of the RTL chain
+ (end_of_function_needs). */
+
+ start_of_epilogue_needs = end_of_function_needs;
+
+ while (epilogue_insn = next_nonnote_insn (epilogue_insn))
+ mark_set_resources (epilogue_insn, &end_of_function_needs, 0, 1);
/* Show we haven't computed an end-of-function label yet. */
end_of_function_label = 0;
next = NEXT_INSN (insn);
if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
- && (GET_CODE (XEXP (PATTERN (insn), 0)) == INSN
- || GET_CODE (XEXP (PATTERN (insn), 0)) == JUMP_INSN
- || GET_CODE (XEXP (PATTERN (insn), 0)) == CALL_INSN))
+ && GET_RTX_CLASS (GET_CODE (XEXP (PATTERN (insn), 0))) == 'i')
next = delete_insn (insn);
}
/* It is not clear why the line below is needed, but it does seem to be. */
unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0);
+ /* Reposition the prologue and epilogue notes in case we moved the
+ prologue/epilogue insns. */
+ reposition_prologue_and_epilogue_notes (first);
+
if (file)
{
register int i, j, need_comma;
OSDN Git Service
