/* Instruction scheduling pass.
- Copyright (C) 1992, 93-96, 1997 Free Software Foundation, Inc.
+ Copyright (C) 1992, 93-97, 1998 Free Software Foundation, Inc.
Contributed by Michael Tiemann (tiemann@cygnus.com)
Enhanced by, and currently maintained by, Jim Wilson (wilson@cygnus.com)
beginning of basic blocks that have been scheduled. */
\f
#include "config.h"
-#include <stdio.h>
+#include "system.h"
#include "rtl.h"
#include "basic-block.h"
#include "regs.h"
#include "flags.h"
#include "insn-config.h"
#include "insn-attr.h"
+#include "recog.h"
+
+#ifndef INSN_SCHEDULING
+void
+schedule_insns (dump_file)
+ FILE *dump_file ATTRIBUTE_UNUSED;
+{
+}
+#else /* INSN_SCHEDULING -- rest of file */
extern char *reg_known_equiv_p;
extern rtx *reg_known_value;
-#ifdef INSN_SCHEDULING
/* Arrays set up by scheduling for the same respective purposes as
similar-named arrays set up by flow analysis. We work with these
arrays during the scheduling pass so we can compare values against
#define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS))
#define BLOCKAGE_RANGE(B) \
(((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
- | (B) & BLOCKAGE_MASK)
+ | ((B) & BLOCKAGE_MASK))
/* Encodings of the `<name>_unit_blockage_range' function. */
#define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
The transition (R->S) is implemented in the scheduling loop in
`schedule_block' when the best insn to schedule is chosen.
The transition (R->Q) is implemented in `schedule_select' when an
- insn is found to to have a function unit conflict with the already
+ insn is found to have a function unit conflict with the already
committed insns.
The transitions (P->R and P->Q) are implemented in `schedule_insn' as
insns move from the ready list to the scheduled list.
static void sched_analyze_2 PROTO((rtx, rtx));
static void sched_analyze_insn PROTO((rtx, rtx, rtx));
static int sched_analyze PROTO((rtx, rtx));
-static void sched_note_set PROTO((int, rtx, int));
-static int rank_for_schedule PROTO((rtx *, rtx *));
+static void sched_note_set PROTO((rtx, int));
+static int rank_for_schedule PROTO((const GENERIC_PTR, const GENERIC_PTR));
static void swap_sort PROTO((rtx *, int));
static void queue_insn PROTO((rtx, int));
static int birthing_insn_p PROTO((rtx));
static rtx reemit_notes PROTO((rtx, rtx));
static void schedule_block PROTO((int, FILE *));
static rtx regno_use_in PROTO((int, rtx));
-static void split_hard_reg_notes PROTO((rtx, rtx, rtx, rtx));
+static void split_hard_reg_notes PROTO((rtx, rtx, rtx));
static void new_insn_dead_notes PROTO((rtx, rtx, rtx, rtx));
static void update_n_sets PROTO((rtx, int));
static void update_flow_info PROTO((rtx, rtx, rtx, rtx));
/* Main entry point of this file. */
void schedule_insns PROTO((FILE *));
-
-#endif /* INSN_SCHEDULING */
\f
#define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
return;
}
\f
-#ifndef INSN_SCHEDULING
-void
-schedule_insns (dump_file)
- FILE *dump_file;
-{
-}
-#else
#ifndef __GNUC__
#define __inline
#endif
unsigned int blockage = INSN_BLOCKAGE (insn);
unsigned int range;
- if (UNIT_BLOCKED (blockage) != unit + 1)
+ if ((int) UNIT_BLOCKED (blockage) != unit + 1)
{
range = function_units[unit].blockage_range_function (insn);
/* We only cache the blockage range for one unit and then only if
int instance = unit;
int best_cost = actual_hazard_this_instance (unit, instance, insn,
clock, cost);
+#if MAX_MULTIPLICITY > 1
int this_cost;
-#if MAX_MULTIPLICITY > 1
if (best_cost > cost)
{
for (i = function_units[unit].multiplicity - 1; i > 0; i--)
while (--i >= 0)
{
reg_last_uses[regno + i]
- = gen_rtx (INSN_LIST, VOIDmode,
- insn, reg_last_uses[regno + i]);
+ = gen_rtx_INSN_LIST (VOIDmode,
+ insn, reg_last_uses[regno + i]);
if (reg_last_sets[regno + i])
add_dependence (insn, reg_last_sets[regno + i], 0);
if ((call_used_regs[regno + i] || global_regs[regno + i])
else
{
reg_last_uses[regno]
- = gen_rtx (INSN_LIST, VOIDmode, insn, reg_last_uses[regno]);
+ = gen_rtx_INSN_LIST (VOIDmode, insn, reg_last_uses[regno]);
if (reg_last_sets[regno])
add_dependence (insn, reg_last_sets[regno], 0);
REG_NOTES (insn) = loop_notes;
}
- /* After reload, it is possible for an instruction to have a REG_DEAD note
- for a register that actually dies a few instructions earlier. For
- example, this can happen with SECONDARY_MEMORY_NEEDED reloads.
- In this case, we must consider the insn to use the register mentioned
- in the REG_DEAD note. Otherwise, we may accidentally move this insn
- after another insn that sets the register, thus getting obviously invalid
- rtl. This confuses reorg which believes that REG_DEAD notes are still
- meaningful.
-
- ??? We would get better code if we fixed reload to put the REG_DEAD
- notes in the right places, but that may not be worth the effort. */
-
- if (reload_completed)
- {
- rtx note;
-
- for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
- if (REG_NOTE_KIND (note) == REG_DEAD)
- sched_analyze_2 (XEXP (note, 0), insn);
- }
-
EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
{
reg_last_sets[i] = insn;
/* Add a pair of fake REG_NOTEs which we will later
convert back into a NOTE_INSN_SETJMP note. See
- reemit_notes for why we use a pair of of NOTEs. */
-
- REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_DEAD,
- GEN_INT (0),
- REG_NOTES (insn));
- REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_DEAD,
- GEN_INT (NOTE_INSN_SETJMP),
- REG_NOTES (insn));
+ reemit_notes for why we use a pair of NOTEs. */
+
+ REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_DEAD,
+ GEN_INT (0),
+ REG_NOTES (insn));
+ REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_DEAD,
+ GEN_INT (NOTE_INSN_SETJMP),
+ REG_NOTES (insn));
}
else
{
|| NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
|| NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
|| NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END
+ || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_START
+ || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END
|| (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP
&& GET_CODE (PREV_INSN (insn)) != CALL_INSN)))
{
- loop_notes = gen_rtx (EXPR_LIST, REG_DEAD,
- GEN_INT (NOTE_BLOCK_NUMBER (insn)), loop_notes);
- loop_notes = gen_rtx (EXPR_LIST, REG_DEAD,
- GEN_INT (NOTE_LINE_NUMBER (insn)), loop_notes);
+ loop_notes = gen_rtx_EXPR_LIST (REG_DEAD,
+ GEN_INT (NOTE_BLOCK_NUMBER (insn)),
+ loop_notes);
+ loop_notes = gen_rtx_EXPR_LIST (REG_DEAD,
+ GEN_INT (NOTE_LINE_NUMBER (insn)),
+ loop_notes);
CONST_CALL_P (loop_notes) = CONST_CALL_P (insn);
}
are scanning forwards. Mark that register as being born. */
static void
-sched_note_set (b, x, death)
- int b;
+sched_note_set (x, death)
rtx x;
int death;
{
static int
rank_for_schedule (x, y)
- rtx *x, *y;
+ const GENERIC_PTR x;
+ const GENERIC_PTR y;
{
- rtx tmp = *y;
- rtx tmp2 = *x;
+ rtx tmp = *(rtx *)y;
+ rtx tmp2 = *(rtx *)x;
rtx link;
int tmp_class, tmp2_class;
int value;
/* Choose the instruction with the highest priority, if different. */
- if (value = INSN_PRIORITY (tmp) - INSN_PRIORITY (tmp2))
+ if ((value = INSN_PRIORITY (tmp) - INSN_PRIORITY (tmp2)))
return value;
if (last_scheduled_insn)
else
tmp2_class = 2;
- if (value = tmp_class - tmp2_class)
+ if ((value = tmp_class - tmp2_class))
return value;
}
{
rtx temp_reg, temp_link;
- temp_reg = gen_rtx (REG, word_mode, 0);
+ temp_reg = gen_rtx_REG (word_mode, 0);
temp_link = rtx_alloc (EXPR_LIST);
PUT_REG_NOTE_KIND (temp_link, REG_DEAD);
XEXP (temp_link, 0) = temp_reg;
#endif
&& regno != STACK_POINTER_REGNUM)
{
- /* ??? It is perhaps a dead_or_set_p bug that it does
- not check for REG_UNUSED notes itself. This is necessary
- for the case where the SET_DEST is a subreg of regno, as
- dead_or_set_p handles subregs specially. */
- if (! all_needed && ! dead_or_set_p (insn, x)
- && ! find_reg_note (insn, REG_UNUSED, x))
+ if (! all_needed && ! dead_or_set_p (insn, x))
{
/* Check for the case where the register dying partially
overlaps the register set by this insn. */
i >= 0; i--)
if (! REGNO_REG_SET_P (old_live_regs, regno + i)
&& ! dead_or_set_regno_p (insn, regno + i))
- create_reg_dead_note (gen_rtx (REG,
- reg_raw_mode[regno + i],
- regno + i),
+ create_reg_dead_note (gen_rtx_REG (reg_raw_mode[regno + i],
+ regno + i),
insn);
}
}
return;
case SUBREG:
+ attach_deaths (SUBREG_REG (x), insn,
+ set_p && ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
+ <= UNITS_PER_WORD)
+ || (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))
+ == GET_MODE_SIZE (GET_MODE ((x))))));
+ return;
+
case STRICT_LOW_PART:
- /* These two cases preserve the value of SET_P, so handle them
- separately. */
- attach_deaths (XEXP (x, 0), insn, set_p);
+ attach_deaths (XEXP (x, 0), insn, 0);
return;
case ZERO_EXTRACT:
case SIGN_EXTRACT:
- /* This case preserves the value of SET_P for the first operand, but
- clears it for the other two. */
- attach_deaths (XEXP (x, 0), insn, set_p);
+ attach_deaths (XEXP (x, 0), insn, 0);
attach_deaths (XEXP (x, 1), insn, 0);
attach_deaths (XEXP (x, 2), insn, 0);
return;
else if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_SETJMP
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_START
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_END
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
{
reg_pending_sets_all = 0;
clear_units ();
+#if 0
+ /* We used to have code to avoid getting parameters moved from hard
+ argument registers into pseudos.
+
+ However, it was removed when it proved to be of marginal benefit and
+ caused problems because of different notions of what the "head" insn
+ was. */
+
/* Remove certain insns at the beginning from scheduling,
by advancing HEAD. */
head = NEXT_INSN (head);
}
}
+#endif
/* Don't include any notes or labels at the beginning of the
basic block, or notes at the ends of basic blocks. */
a register must be marked as dead after this insn. */
if (GET_CODE (PATTERN (insn)) == SET
|| GET_CODE (PATTERN (insn)) == CLOBBER)
- sched_note_set (b, PATTERN (insn), 0);
+ sched_note_set (PATTERN (insn), 0);
else if (GET_CODE (PATTERN (insn)) == PARALLEL)
{
int j;
for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
|| GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
- sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
+ sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
/* ??? This code is obsolete and should be deleted. It
is harmless though, so we will leave it in for now. */
for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
- sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
+ sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
}
/* Each call clobbers (makes live) all call-clobbered regs
must be marked as dead after this insn. */
if (GET_CODE (PATTERN (insn)) == SET
|| GET_CODE (PATTERN (insn)) == CLOBBER)
- sched_note_set (b, PATTERN (insn), 0);
+ sched_note_set (PATTERN (insn), 0);
else if (GET_CODE (PATTERN (insn)) == PARALLEL)
{
int j;
for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
|| GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
- sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
+ sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
/* ??? This code is obsolete and should be deleted. It
is harmless though, so we will leave it in for now. */
for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == USE)
- sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 0);
+ sched_note_set (XVECEXP (PATTERN (insn), 0, j), 0);
}
/* Each call clobbers (makes live) all call-clobbered regs that are
register int stalls;
for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++)
- if (insn = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)])
+ if ((insn = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
{
for (; insn; insn = NEXT_INSN (insn))
{
/* See if this is the last notice we must take of a register. */
if (GET_CODE (PATTERN (insn)) == SET
|| GET_CODE (PATTERN (insn)) == CLOBBER)
- sched_note_set (b, PATTERN (insn), 1);
+ sched_note_set (PATTERN (insn), 1);
else if (GET_CODE (PATTERN (insn)) == PARALLEL)
{
int j;
for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
|| GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER)
- sched_note_set (b, XVECEXP (PATTERN (insn), 0, j), 1);
+ sched_note_set (XVECEXP (PATTERN (insn), 0, j), 1);
}
/* This code keeps life analysis information up to date. */
{
if (fmt[i] == 'e')
{
- if (tem = regno_use_in (regno, XEXP (x, i)))
+ if ((tem = regno_use_in (regno, XEXP (x, i))))
return tem;
}
else if (fmt[i] == 'E')
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
- if (tem = regno_use_in (regno , XVECEXP (x, i, j)))
+ if ((tem = regno_use_in (regno , XVECEXP (x, i, j))))
return tem;
}
several smaller hard register references in the split insns. */
static void
-split_hard_reg_notes (note, first, last, orig_insn)
- rtx note, first, last, orig_insn;
+split_hard_reg_notes (note, first, last)
+ rtx note, first, last;
{
rtx reg, temp, link;
int n_regs, i, new_reg;
if (GET_CODE (dest) == REG)
{
+ /* If the original insn already used this register, we may not add new
+ notes for it. One example for a split that needs this test is
+ when a multi-word memory access with register-indirect addressing
+ is split into multiple memory accesses with auto-increment and
+ one adjusting add instruction for the address register. */
+ if (reg_referenced_p (dest, PATTERN (orig_insn)))
+ return;
for (tem = last; tem != insn; tem = PREV_INSN (tem))
{
if (GET_RTX_CLASS (GET_CODE (tem)) == 'i'
&& GET_CODE (temp) == REG
&& REGNO (temp) < FIRST_PSEUDO_REGISTER
&& HARD_REGNO_NREGS (REGNO (temp), GET_MODE (temp)) > 1)
- split_hard_reg_notes (note, first, last, orig_insn);
+ split_hard_reg_notes (note, first, last);
else
{
XEXP (note, 1) = REG_NOTES (insn);
register that was not needed by this instantiation of the
pattern, so we can safely ignore it. */
if (insn == first)
- {
- /* After reload, REG_DEAD notes come sometimes an
- instruction after the register actually dies. */
- if (reload_completed && REG_NOTE_KIND (note) == REG_DEAD)
- {
- XEXP (note, 1) = REG_NOTES (insn);
- REG_NOTES (insn) = note;
- break;
- }
-
+ {
if (REG_NOTE_KIND (note) != REG_UNUSED)
abort ();
break;
case REG_WAS_0:
+ /* If the insn that set the register to 0 was deleted, this
+ note cannot be relied on any longer. The destination might
+ even have been moved to memory.
+ This was observed for SH4 with execute/920501-6.c compilation,
+ -O2 -fomit-frame-pointer -finline-functions . */
+ if (GET_CODE (XEXP (note, 0)) == NOTE
+ || INSN_DELETED_P (XEXP (note, 0)))
+ break;
/* This note applies to the dest of the original insn. Find the
first new insn that now has the same dest, and move the note
there. */
for (insn = first; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
&& reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
- REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_LABEL,
- XEXP (note, 0), REG_NOTES (insn));
+ REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL,
+ XEXP (note, 0),
+ REG_NOTES (insn));
break;
case REG_CC_SETTER:
}
else if (! found_orig_dest)
{
- /* This should never happen. */
- abort ();
+ int i, regno;
+
+ /* Should never reach here for a pseudo reg. */
+ if (REGNO (orig_dest) >= FIRST_PSEUDO_REGISTER)
+ abort ();
+
+ /* This can happen for a hard register, if the splitter
+ does not bother to emit instructions which would be no-ops.
+ We try to verify that this is the case by checking to see if
+ the original instruction uses all of the registers that it
+ set. This case is OK, because deleting a no-op can not affect
+ REG_DEAD notes on other insns. If this is not the case, then
+ abort. */
+
+ regno = REGNO (orig_dest);
+ for (i = HARD_REGNO_NREGS (regno, GET_MODE (orig_dest)) - 1;
+ i >= 0; i--)
+ if (! refers_to_regno_p (regno + i, regno + i + 1, orig_insn,
+ NULL_PTR))
+ break;
+ if (i >= 0)
+ abort ();
}
}
{
int max_uid = MAX_INSNS_PER_SPLIT * (get_max_uid () + 1);
int b;
- int i;
rtx insn;
/* Taking care of this degenerate case makes the rest of
/* Create an insn here so that we can hang dependencies off of it later. */
sched_before_next_call
- = gen_rtx (INSN, VOIDmode, 0, NULL_RTX, NULL_RTX,
- NULL_RTX, 0, NULL_RTX, NULL_RTX);
+ = gen_rtx_INSN (VOIDmode, 0, NULL_RTX, NULL_RTX,
+ NULL_RTX, 0, NULL_RTX, NULL_RTX);
/* Initialize the unused_*_lists. We can't use the ones left over from
the previous function, because gcc has freed that memory. We can use
remember how far we can cut back the stack on exit. */
/* Allocate data for this pass. See comments, above,
- for what these vectors do. */
- insn_luid = (int *) alloca (max_uid * sizeof (int));
- insn_priority = (int *) alloca (max_uid * sizeof (int));
- insn_tick = (int *) alloca (max_uid * sizeof (int));
- insn_costs = (short *) alloca (max_uid * sizeof (short));
- insn_units = (short *) alloca (max_uid * sizeof (short));
- insn_blockage = (unsigned int *) alloca (max_uid * sizeof (unsigned int));
- insn_ref_count = (int *) alloca (max_uid * sizeof (int));
+ for what these vectors do.
+
+ We use xmalloc instead of alloca, because max_uid can be very large
+ when there is a lot of function inlining. If we used alloca, we could
+ exceed stack limits on some hosts for some inputs. */
+ insn_luid = (int *) xmalloc (max_uid * sizeof (int));
+ insn_priority = (int *) xmalloc (max_uid * sizeof (int));
+ insn_tick = (int *) xmalloc (max_uid * sizeof (int));
+ insn_costs = (short *) xmalloc (max_uid * sizeof (short));
+ insn_units = (short *) xmalloc (max_uid * sizeof (short));
+ insn_blockage = (unsigned int *) xmalloc (max_uid * sizeof (unsigned int));
+ insn_ref_count = (int *) xmalloc (max_uid * sizeof (int));
if (reload_completed == 0)
{
{
rtx line;
- line_note = (rtx *) alloca (max_uid * sizeof (rtx));
+ line_note = (rtx *) xmalloc (max_uid * sizeof (rtx));
bzero ((char *) line_note, max_uid * sizeof (rtx));
line_note_head = (rtx *) alloca (n_basic_blocks * sizeof (rtx));
bzero ((char *) line_note_head, n_basic_blocks * sizeof (rtx));
}
}
+ free (insn_luid);
+ free (insn_priority);
+ free (insn_tick);
+ free (insn_costs);
+ free (insn_units);
+ free (insn_blockage);
+ free (insn_ref_count);
+
+ if (write_symbols != NO_DEBUG)
+ free (line_note);
+
if (reload_completed == 0)
{
FREE_REG_SET (bb_dead_regs);