/* Instruction scheduling pass.
Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
- 1999, 2000, 2001 Free Software Foundation, Inc.
+ 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
and currently maintained by, Jim Wilson (wilson@cygnus.com)
for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to the Free the
-Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+along with GCC; see the file COPYING. If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA. */
/* Instruction scheduling pass. This file, along with sched-deps.c,
\f
#include "config.h"
#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
#include "toplev.h"
#include "rtl.h"
#include "tm_p.h"
static int issue_rate;
-/* If the following variable value is non zero, the scheduler inserts
+/* If the following variable value is nonzero, the scheduler inserts
bubbles (nop insns). The value of variable affects on scheduler
behavior only if automaton pipeline interface with multipass
scheduling is used and hook dfa_bubble is defined. */
of the -fsched-verbose=N option. */
void
-fix_sched_param (param, val)
- const char *param, *val;
+fix_sched_param (const char *param, const char *val)
{
if (!strcmp (param, "verbose"))
sched_verbose_param = atoi (val);
struct haifa_insn_data *h_i_d;
-#define DONE_PRIORITY -1
-#define MAX_PRIORITY 0x7fffffff
-#define TAIL_PRIORITY 0x7ffffffe
-#define LAUNCH_PRIORITY 0x7f000001
-#define DONE_PRIORITY_P(INSN) (INSN_PRIORITY (INSN) < 0)
-#define LOW_PRIORITY_P(INSN) ((INSN_PRIORITY (INSN) & 0x7f000000) == 0)
-
#define LINE_NOTE(INSN) (h_i_d[INSN_UID (INSN)].line_note)
#define INSN_TICK(INSN) (h_i_d[INSN_UID (INSN)].tick)
int n_ready;
};
+static int may_trap_exp (rtx, int);
+
+/* Nonzero iff the address is comprised from at most 1 register. */
+#define CONST_BASED_ADDRESS_P(x) \
+ (GET_CODE (x) == REG \
+ || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
+ || (GET_CODE (x) == LO_SUM)) \
+ && (CONSTANT_P (XEXP (x, 0)) \
+ || CONSTANT_P (XEXP (x, 1)))))
+
+/* Returns a class that insn with GET_DEST(insn)=x may belong to,
+ as found by analyzing insn's expression. */
+
+static int
+may_trap_exp (rtx x, int is_store)
+{
+ enum rtx_code code;
+
+ if (x == 0)
+ return TRAP_FREE;
+ code = GET_CODE (x);
+ if (is_store)
+ {
+ if (code == MEM && may_trap_p (x))
+ return TRAP_RISKY;
+ else
+ return TRAP_FREE;
+ }
+ if (code == MEM)
+ {
+ /* The insn uses memory: a volatile load. */
+ if (MEM_VOLATILE_P (x))
+ return IRISKY;
+ /* An exception-free load. */
+ if (!may_trap_p (x))
+ return IFREE;
+ /* A load with 1 base register, to be further checked. */
+ if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
+ return PFREE_CANDIDATE;
+ /* No info on the load, to be further checked. */
+ return PRISKY_CANDIDATE;
+ }
+ else
+ {
+ const char *fmt;
+ int i, insn_class = TRAP_FREE;
+
+ /* Neither store nor load, check if it may cause a trap. */
+ if (may_trap_p (x))
+ return TRAP_RISKY;
+ /* Recursive step: walk the insn... */
+ fmt = GET_RTX_FORMAT (code);
+ for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ {
+ if (fmt[i] == 'e')
+ {
+ int tmp_class = may_trap_exp (XEXP (x, i), is_store);
+ insn_class = WORST_CLASS (insn_class, tmp_class);
+ }
+ else if (fmt[i] == 'E')
+ {
+ int j;
+ for (j = 0; j < XVECLEN (x, i); j++)
+ {
+ int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
+ insn_class = WORST_CLASS (insn_class, tmp_class);
+ if (insn_class == TRAP_RISKY || insn_class == IRISKY)
+ break;
+ }
+ }
+ if (insn_class == TRAP_RISKY || insn_class == IRISKY)
+ break;
+ }
+ return insn_class;
+ }
+}
+
+/* Classifies insn for the purpose of verifying that it can be
+ moved speculatively, by examining it's patterns, returning:
+ TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
+ TRAP_FREE: non-load insn.
+ IFREE: load from a globally safe location.
+ IRISKY: volatile load.
+ PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
+ being either PFREE or PRISKY. */
+
+int
+haifa_classify_insn (rtx insn)
+{
+ rtx pat = PATTERN (insn);
+ int tmp_class = TRAP_FREE;
+ int insn_class = TRAP_FREE;
+ enum rtx_code code;
+
+ if (GET_CODE (pat) == PARALLEL)
+ {
+ int i, len = XVECLEN (pat, 0);
+
+ for (i = len - 1; i >= 0; i--)
+ {
+ code = GET_CODE (XVECEXP (pat, 0, i));
+ switch (code)
+ {
+ case CLOBBER:
+ /* Test if it is a 'store'. */
+ tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
+ break;
+ case SET:
+ /* Test if it is a store. */
+ tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
+ if (tmp_class == TRAP_RISKY)
+ break;
+ /* Test if it is a load. */
+ tmp_class
+ = WORST_CLASS (tmp_class,
+ may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)),
+ 0));
+ break;
+ case COND_EXEC:
+ case TRAP_IF:
+ tmp_class = TRAP_RISKY;
+ break;
+ default:
+ ;
+ }
+ insn_class = WORST_CLASS (insn_class, tmp_class);
+ if (insn_class == TRAP_RISKY || insn_class == IRISKY)
+ break;
+ }
+ }
+ else
+ {
+ code = GET_CODE (pat);
+ switch (code)
+ {
+ case CLOBBER:
+ /* Test if it is a 'store'. */
+ tmp_class = may_trap_exp (XEXP (pat, 0), 1);
+ break;
+ case SET:
+ /* Test if it is a store. */
+ tmp_class = may_trap_exp (SET_DEST (pat), 1);
+ if (tmp_class == TRAP_RISKY)
+ break;
+ /* Test if it is a load. */
+ tmp_class =
+ WORST_CLASS (tmp_class,
+ may_trap_exp (SET_SRC (pat), 0));
+ break;
+ case COND_EXEC:
+ case TRAP_IF:
+ tmp_class = TRAP_RISKY;
+ break;
+ default:;
+ }
+ insn_class = tmp_class;
+ }
+
+ return insn_class;
+}
+
/* Forward declarations. */
/* The scheduler using only DFA description should never use the
following five functions: */
-static unsigned int blockage_range PARAMS ((int, rtx));
-static void clear_units PARAMS ((void));
-static void schedule_unit PARAMS ((int, rtx, int));
-static int actual_hazard PARAMS ((int, rtx, int, int));
-static int potential_hazard PARAMS ((int, rtx, int));
-
-static int priority PARAMS ((rtx));
-static int rank_for_schedule PARAMS ((const PTR, const PTR));
-static void swap_sort PARAMS ((rtx *, int));
-static void queue_insn PARAMS ((rtx, int));
-static void schedule_insn PARAMS ((rtx, struct ready_list *, int));
-static void find_insn_reg_weight PARAMS ((int));
-static void adjust_priority PARAMS ((rtx));
+static unsigned int blockage_range (int, rtx);
+static void clear_units (void);
+static void schedule_unit (int, rtx, int);
+static int actual_hazard (int, rtx, int, int);
+static int potential_hazard (int, rtx, int);
+
+static int priority (rtx);
+static int rank_for_schedule (const void *, const void *);
+static void swap_sort (rtx *, int);
+static void queue_insn (rtx, int);
+static int schedule_insn (rtx, struct ready_list *, int);
+static int find_set_reg_weight (rtx);
+static void find_insn_reg_weight (int);
+static void adjust_priority (rtx);
+static void advance_one_cycle (void);
/* Notes handling mechanism:
=========================
unlink_other_notes ()). After scheduling the block, these notes are
inserted at the beginning of the block (in schedule_block()). */
-static rtx unlink_other_notes PARAMS ((rtx, rtx));
-static rtx unlink_line_notes PARAMS ((rtx, rtx));
-static rtx reemit_notes PARAMS ((rtx, rtx));
+static rtx unlink_other_notes (rtx, rtx);
+static rtx unlink_line_notes (rtx, rtx);
+static rtx reemit_notes (rtx, rtx);
-static rtx *ready_lastpos PARAMS ((struct ready_list *));
-static void ready_sort PARAMS ((struct ready_list *));
-static rtx ready_remove_first PARAMS ((struct ready_list *));
+static rtx *ready_lastpos (struct ready_list *);
+static void ready_sort (struct ready_list *);
+static rtx ready_remove_first (struct ready_list *);
-static void queue_to_ready PARAMS ((struct ready_list *));
+static void queue_to_ready (struct ready_list *);
+static int early_queue_to_ready (state_t, struct ready_list *);
-static void debug_ready_list PARAMS ((struct ready_list *));
+static void debug_ready_list (struct ready_list *);
-static rtx move_insn1 PARAMS ((rtx, rtx));
-static rtx move_insn PARAMS ((rtx, rtx));
+static rtx move_insn1 (rtx, rtx);
+static rtx move_insn (rtx, rtx);
/* The following functions are used to implement multi-pass scheduling
on the first cycle. It is used only for DFA based scheduler. */
-static rtx ready_element PARAMS ((struct ready_list *, int));
-static rtx ready_remove PARAMS ((struct ready_list *, int));
-static int max_issue PARAMS ((struct ready_list *, state_t, int *, int *));
+static rtx ready_element (struct ready_list *, int);
+static rtx ready_remove (struct ready_list *, int);
+static int max_issue (struct ready_list *, int *);
-static rtx choose_ready PARAMS ((struct ready_list *));
+static rtx choose_ready (struct ready_list *);
#endif /* INSN_SCHEDULING */
\f
\f
#ifndef INSN_SCHEDULING
void
-schedule_insns (dump_file)
- FILE *dump_file ATTRIBUTE_UNUSED;
+schedule_insns (FILE *dump_file ATTRIBUTE_UNUSED)
{
}
#else
/* Compute the function units used by INSN. This caches the value
returned by function_units_used. A function unit is encoded as the
- unit number if the value is non-negative and the compliment of a
+ unit number if the value is non-negative and the complement of a
mask if the value is negative. A function unit index is the
non-negative encoding. The scheduler using only DFA description
should never use the following function. */
HAIFA_INLINE int
-insn_unit (insn)
- rtx insn;
+insn_unit (rtx insn)
{
- register int unit = INSN_UNIT (insn);
+ int unit = INSN_UNIT (insn);
if (unit == 0)
{
function. */
HAIFA_INLINE static unsigned int
-blockage_range (unit, insn)
- int unit;
- rtx insn;
+blockage_range (int unit, rtx insn)
{
unsigned int blockage = INSN_BLOCKAGE (insn);
unsigned int range;
following function. */
rtx
-get_unit_last_insn (instance)
- int instance;
+get_unit_last_insn (int instance)
{
return unit_last_insn[instance];
}
/* Reset the function unit state to the null state. */
static void
-clear_units ()
+clear_units (void)
{
- memset ((char *) unit_last_insn, 0, sizeof (unit_last_insn));
- memset ((char *) unit_tick, 0, sizeof (unit_tick));
- memset ((char *) unit_n_insns, 0, sizeof (unit_n_insns));
+ memset (unit_last_insn, 0, sizeof (unit_last_insn));
+ memset (unit_tick, 0, sizeof (unit_tick));
+ memset (unit_n_insns, 0, sizeof (unit_n_insns));
}
/* Return the issue-delay of an insn. The scheduler using only DFA
description should never use the following function. */
HAIFA_INLINE int
-insn_issue_delay (insn)
- rtx insn;
+insn_issue_delay (rtx insn)
{
int i, delay = 0;
int unit = insn_unit (insn);
use the following function. */
HAIFA_INLINE int
-actual_hazard_this_instance (unit, instance, insn, clock, cost)
- int unit, instance, clock, cost;
- rtx insn;
+actual_hazard_this_instance (int unit, int instance, rtx insn, int clock, int cost)
{
int tick = unit_tick[instance]; /* Issue time of the last issued insn. */
never use the following function. */
HAIFA_INLINE static void
-schedule_unit (unit, insn, clock)
- int unit, clock;
- rtx insn;
+schedule_unit (int unit, rtx insn, int clock)
{
int i;
use the following function. */
HAIFA_INLINE static int
-actual_hazard (unit, insn, clock, cost)
- int unit, clock, cost;
- rtx insn;
+actual_hazard (int unit, rtx insn, int clock, int cost)
{
int i;
the following function. */
HAIFA_INLINE static int
-potential_hazard (unit, insn, cost)
- int unit, cost;
- rtx insn;
+potential_hazard (int unit, rtx insn, int cost)
{
int i, ncost;
unsigned int minb, maxb;
instruction results. */
HAIFA_INLINE int
-insn_cost (insn, link, used)
- rtx insn, link, used;
+insn_cost (rtx insn, rtx link, rtx used)
{
- register int cost = INSN_COST (insn);
+ int cost = INSN_COST (insn);
if (cost < 0)
{
}
else
{
- if (targetm.sched.use_dfa_pipeline_interface)
+ if (targetm.sched.use_dfa_pipeline_interface
+ && (*targetm.sched.use_dfa_pipeline_interface) ())
cost = insn_default_latency (insn);
else
cost = result_ready_cost (insn);
-
+
if (cost < 0)
cost = 0;
-
+
INSN_COST (insn) = cost;
}
}
cost = 0;
else
{
- if (targetm.sched.use_dfa_pipeline_interface)
+ if (targetm.sched.use_dfa_pipeline_interface
+ && (*targetm.sched.use_dfa_pipeline_interface) ())
{
if (INSN_CODE (insn) >= 0)
{
if (cost < 0)
cost = 0;
}
-
+
return cost;
}
/* Compute the priority number for INSN. */
static int
-priority (insn)
- rtx insn;
+priority (rtx insn)
{
rtx link;
}
\f
/* Macros and functions for keeping the priority queue sorted, and
- dealing with queueing and dequeueing of instructions. */
+ dealing with queuing and dequeuing of instructions. */
#define SCHED_SORT(READY, N_READY) \
do { if ((N_READY) == 2) \
unstable. */
static int
-rank_for_schedule (x, y)
- const PTR x;
- const PTR y;
+rank_for_schedule (const void *x, const void *y)
{
rtx tmp = *(const rtx *) y;
rtx tmp2 = *(const rtx *) x;
int tmp_class, tmp2_class, depend_count1, depend_count2;
int val, priority_val, weight_val, info_val;
+ /* The insn in a schedule group should be issued the first. */
+ if (SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
+ return SCHED_GROUP_P (tmp2) ? 1 : -1;
+
/* Prefer insn with higher priority. */
priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
+
if (priority_val)
return priority_val;
/* Prefer an insn with smaller contribution to registers-pressure. */
if (!reload_completed &&
(weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
- return (weight_val);
+ return weight_val;
info_val = (*current_sched_info->rank) (tmp, tmp2);
if (info_val)
/* Resort the array A in which only element at index N may be out of order. */
HAIFA_INLINE static void
-swap_sort (a, n)
- rtx *a;
- int n;
+swap_sort (rtx *a, int n)
{
rtx insn = a[n - 1];
int i = n - 2;
chain for debugging purposes. */
HAIFA_INLINE static void
-queue_insn (insn, n_cycles)
- rtx insn;
- int n_cycles;
+queue_insn (rtx insn, int n_cycles)
{
int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
with the lowest priority. */
HAIFA_INLINE static rtx *
-ready_lastpos (ready)
- struct ready_list *ready;
+ready_lastpos (struct ready_list *ready)
{
if (ready->n_ready == 0)
abort ();
priority. */
HAIFA_INLINE void
-ready_add (ready, insn)
- struct ready_list *ready;
- rtx insn;
+ready_add (struct ready_list *ready, rtx insn)
{
if (ready->first == ready->n_ready)
{
return it. */
HAIFA_INLINE static rtx
-ready_remove_first (ready)
- struct ready_list *ready;
+ready_remove_first (struct ready_list *ready)
{
rtx t;
if (ready->n_ready == 0)
N_READY - 1. */
HAIFA_INLINE static rtx
-ready_element (ready, index)
- struct ready_list *ready;
- int index;
+ready_element (struct ready_list *ready, int index)
{
+#ifdef ENABLE_CHECKING
if (ready->n_ready == 0 || index >= ready->n_ready)
abort ();
+#endif
return ready->vec[ready->first - index];
}
has N_READY - 1. */
HAIFA_INLINE static rtx
-ready_remove (ready, index)
- struct ready_list *ready;
- int index;
+ready_remove (struct ready_list *ready, int index)
{
rtx t;
int i;
t = ready->vec[ready->first - index];
ready->n_ready--;
for (i = index; i < ready->n_ready; i++)
- ready [ready->first - i] = ready [ready->first - i - 1];
+ ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
return t;
}
macro. */
HAIFA_INLINE static void
-ready_sort (ready)
- struct ready_list *ready;
+ready_sort (struct ready_list *ready)
{
rtx *first = ready_lastpos (ready);
SCHED_SORT (first, ready->n_ready);
provide a hook for the target to tweek itself. */
HAIFA_INLINE static void
-adjust_priority (prev)
- rtx prev;
+adjust_priority (rtx prev)
{
/* ??? There used to be code here to try and estimate how an insn
affected register lifetimes, but it did it by looking at REG_DEAD
(*targetm.sched.adjust_priority) (prev, INSN_PRIORITY (prev));
}
+/* Advance time on one cycle. */
+HAIFA_INLINE static void
+advance_one_cycle (void)
+{
+ if (targetm.sched.use_dfa_pipeline_interface
+ && (*targetm.sched.use_dfa_pipeline_interface) ())
+ {
+ if (targetm.sched.dfa_pre_cycle_insn)
+ state_transition (curr_state,
+ (*targetm.sched.dfa_pre_cycle_insn) ());
+
+ state_transition (curr_state, NULL);
+
+ if (targetm.sched.dfa_post_cycle_insn)
+ state_transition (curr_state,
+ (*targetm.sched.dfa_post_cycle_insn) ());
+ }
+}
+
/* Clock at which the previous instruction was issued. */
static int last_clock_var;
/* INSN is the "currently executing insn". Launch each insn which was
waiting on INSN. READY is the ready list which contains the insns
- that are ready to fire. CLOCK is the current cycle.
- */
+ that are ready to fire. CLOCK is the current cycle. The function
+ returns necessary cycle advance after issuing the insn (it is not
+ zero for insns in a schedule group). */
-static void
-schedule_insn (insn, ready, clock)
- rtx insn;
- struct ready_list *ready;
- int clock;
+static int
+schedule_insn (rtx insn, struct ready_list *ready, int clock)
{
rtx link;
+ int advance = 0;
int unit = 0;
+ int premature_issue = 0;
- if (!targetm.sched.use_dfa_pipeline_interface)
+ if (!targetm.sched.use_dfa_pipeline_interface
+ || !(*targetm.sched.use_dfa_pipeline_interface) ())
unit = insn_unit (insn);
- if (sched_verbose >= 2)
+ if (targetm.sched.use_dfa_pipeline_interface
+ && (*targetm.sched.use_dfa_pipeline_interface) ()
+ && sched_verbose >= 1)
{
+ char buf[2048];
- if (targetm.sched.use_dfa_pipeline_interface)
- {
- fprintf (sched_dump,
- ";;\t\t--> scheduling insn <<<%d>>>:reservation ",
- INSN_UID (insn));
-
- if (recog_memoized (insn) < 0)
- fprintf (sched_dump, "nothing");
- else
- print_reservation (sched_dump, insn);
- }
- else
- {
- fprintf (sched_dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ",
- INSN_UID (insn));
- insn_print_units (insn);
- }
+ print_insn (buf, insn, 0);
+ buf[40] = 0;
+ fprintf (sched_dump, ";;\t%3i--> %-40s:", clock, buf);
- fprintf (sched_dump, "\n");
+ if (recog_memoized (insn) < 0)
+ fprintf (sched_dump, "nothing");
+ else
+ print_reservation (sched_dump, insn);
+ fputc ('\n', sched_dump);
+ }
+ else if (sched_verbose >= 2)
+ {
+ fprintf (sched_dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ",
+ INSN_UID (insn));
+ insn_print_units (insn);
+ fputc ('\n', sched_dump);
}
- if (!targetm.sched.use_dfa_pipeline_interface)
+ if (!targetm.sched.use_dfa_pipeline_interface
+ || !(*targetm.sched.use_dfa_pipeline_interface) ())
{
if (sched_verbose && unit == -1)
visualize_no_unit (insn);
if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose)
schedule_unit (unit, insn, clock);
-
+
if (INSN_DEPEND (insn) == 0)
- return;
+ return 0;
+ }
+
+ if (INSN_TICK (insn) > clock)
+ {
+ /* 'insn' has been prematurely moved from the queue to the
+ ready list. */
+ premature_issue = INSN_TICK (insn) - clock;
}
for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
rtx next = XEXP (link, 0);
int cost = insn_cost (insn, link, next);
- INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost);
+ INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost + premature_issue);
if ((INSN_DEP_COUNT (next) -= 1) == 0)
{
if (effective_cost < 1)
fprintf (sched_dump, "into ready\n");
else
- fprintf (sched_dump, "into queue with cost=%d\n", effective_cost);
+ fprintf (sched_dump, "into queue with cost=%d\n",
+ effective_cost);
}
/* Adjust the priority of NEXT and either put it on the ready
if (effective_cost < 1)
ready_add (ready, next);
else
- queue_insn (next, effective_cost);
+ {
+ queue_insn (next, effective_cost);
+
+ if (SCHED_GROUP_P (next) && advance < effective_cost)
+ advance = effective_cost;
+ }
}
}
to issue on the same cycle as the previous insn. A machine
may use this information to decide how the instruction should
be aligned. */
- if (reload_completed && issue_rate > 1
+ if (issue_rate > 1
&& GET_CODE (PATTERN (insn)) != USE
&& GET_CODE (PATTERN (insn)) != CLOBBER)
{
- PUT_MODE (insn, clock > last_clock_var ? TImode : VOIDmode);
+ if (reload_completed)
+ PUT_MODE (insn, clock > last_clock_var ? TImode : VOIDmode);
last_clock_var = clock;
}
+ return advance;
}
/* Functions for handling of notes. */
Returns the insn following the notes. */
static rtx
-unlink_other_notes (insn, tail)
- rtx insn, tail;
+unlink_other_notes (rtx insn, rtx tail)
{
rtx prev = PREV_INSN (insn);
/* See sched_analyze to see how these are handled. */
if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
- && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_BEG
- && NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_END
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
{
they can be reused. Returns the insn following the notes. */
static rtx
-unlink_line_notes (insn, tail)
- rtx insn, tail;
+unlink_line_notes (rtx insn, rtx tail)
{
rtx prev = PREV_INSN (insn);
/* Return the head and tail pointers of BB. */
void
-get_block_head_tail (b, headp, tailp)
- int b;
- rtx *headp;
- rtx *tailp;
+get_block_head_tail (int b, rtx *headp, rtx *tailp)
{
/* HEAD and TAIL delimit the basic block being scheduled. */
rtx head = BLOCK_HEAD (b);
/* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
int
-no_real_insns_p (head, tail)
- rtx head, tail;
+no_real_insns_p (rtx head, rtx tail)
{
while (head != NEXT_INSN (tail))
{
block in which notes should be processed. */
void
-rm_line_notes (head, tail)
- rtx head, tail;
+rm_line_notes (rtx head, rtx tail)
{
rtx next_tail;
rtx insn;
}
/* Save line number notes for each insn in block B. HEAD and TAIL are
- the boundaries of the block in which notes should be processed.*/
+ the boundaries of the block in which notes should be processed. */
void
-save_line_notes (b, head, tail)
- int b;
- rtx head, tail;
+save_line_notes (int b, rtx head, rtx tail)
{
rtx next_tail;
/* After a block was scheduled, insert line notes into the insns list.
HEAD and TAIL are the boundaries of the block in which notes should
- be processed.*/
+ be processed. */
void
-restore_line_notes (head, tail)
- rtx head, tail;
+restore_line_notes (rtx head, rtx tail)
{
rtx line, note, prev, new;
int added_notes = 0;
insns list. */
void
-rm_redundant_line_notes ()
+rm_redundant_line_notes (void)
{
rtx line = 0;
rtx insn = get_insns ();
of notes ended by NOTE_LIST. */
void
-rm_other_notes (head, tail)
- rtx head;
- rtx tail;
+rm_other_notes (rtx head, rtx tail)
{
rtx next_tail;
rtx insn;
/* Functions for computation of registers live/usage info. */
+/* This function looks for a new register being defined.
+ If the destination register is already used by the source,
+ a new register is not needed. */
+
+static int
+find_set_reg_weight (rtx x)
+{
+ if (GET_CODE (x) == CLOBBER
+ && register_operand (SET_DEST (x), VOIDmode))
+ return 1;
+ if (GET_CODE (x) == SET
+ && register_operand (SET_DEST (x), VOIDmode))
+ {
+ if (GET_CODE (SET_DEST (x)) == REG)
+ {
+ if (!reg_mentioned_p (SET_DEST (x), SET_SRC (x)))
+ return 1;
+ else
+ return 0;
+ }
+ return 1;
+ }
+ return 0;
+}
+
/* Calculate INSN_REG_WEIGHT for all insns of a block. */
static void
-find_insn_reg_weight (b)
- int b;
+find_insn_reg_weight (int b)
{
rtx insn, next_tail, head, tail;
/* Increment weight for each register born here. */
x = PATTERN (insn);
- if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
- && register_operand (SET_DEST (x), VOIDmode))
- reg_weight++;
- else if (GET_CODE (x) == PARALLEL)
+ reg_weight += find_set_reg_weight (x);
+ if (GET_CODE (x) == PARALLEL)
{
int j;
for (j = XVECLEN (x, 0) - 1; j >= 0; j--)
{
x = XVECEXP (PATTERN (insn), 0, j);
- if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
- && register_operand (SET_DEST (x), VOIDmode))
- reg_weight++;
+ reg_weight += find_set_reg_weight (x);
}
}
-
/* Decrement weight for each register that dies here. */
for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
{
/* Move insns that became ready to fire from queue to ready list. */
static void
-queue_to_ready (ready)
- struct ready_list *ready;
+queue_to_ready (struct ready_list *ready)
{
rtx insn;
rtx link;
of the pending insns at that point to the ready list. */
if (ready->n_ready == 0)
{
- register int stalls;
+ int stalls;
for (stalls = 1; stalls <= MAX_INSN_QUEUE_INDEX; stalls++)
{
}
insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
- /* Advance time on one cycle. */
- if (targetm.sched.use_dfa_pipeline_interface)
- {
- if (targetm.sched.dfa_pre_cycle_insn)
- state_transition (curr_state,
- (*targetm.sched.dfa_pre_cycle_insn) ());
-
- state_transition (curr_state, NULL);
-
- if (targetm.sched.dfa_post_cycle_insn)
- state_transition (curr_state,
- (*targetm.sched.dfa_post_cycle_insn) ());
- }
+ advance_one_cycle ();
- if (ready->n_ready)
- break;
+ break;
}
+
+ advance_one_cycle ();
}
- if (!targetm.sched.use_dfa_pipeline_interface && sched_verbose && stalls)
+ if ((!targetm.sched.use_dfa_pipeline_interface
+ || !(*targetm.sched.use_dfa_pipeline_interface) ())
+ && sched_verbose && stalls)
visualize_stall_cycles (stalls);
q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
}
}
+/* Used by early_queue_to_ready. Determines whether it is "ok" to
+ prematurely move INSN from the queue to the ready list. Currently,
+ if a target defines the hook 'is_costly_dependence', this function
+ uses the hook to check whether there exist any dependences which are
+ considered costly by the target, between INSN and other insns that
+ have already been scheduled. Dependences are checked up to Y cycles
+ back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
+ controlling this value.
+ (Other considerations could be taken into account instead (or in
+ addition) depending on user flags and target hooks. */
+
+static bool
+ok_for_early_queue_removal (rtx insn)
+{
+ int n_cycles;
+ rtx prev_insn = last_scheduled_insn;
+
+ if (targetm.sched.is_costly_dependence)
+ {
+ for (n_cycles = flag_sched_stalled_insns_dep; n_cycles; n_cycles--)
+ {
+ for ( ; prev_insn; prev_insn = PREV_INSN (prev_insn))
+ {
+ rtx dep_link = 0;
+ int dep_cost;
+
+ if (GET_CODE (prev_insn) != NOTE)
+ {
+ dep_link = find_insn_list (insn, INSN_DEPEND (prev_insn));
+ if (dep_link)
+ {
+ dep_cost = insn_cost (prev_insn, dep_link, insn) ;
+ if (targetm.sched.is_costly_dependence (prev_insn, insn,
+ dep_link, dep_cost,
+ flag_sched_stalled_insns_dep - n_cycles))
+ return false;
+ }
+ }
+
+ if (GET_MODE (prev_insn) == TImode) /* end of dispatch group */
+ break;
+ }
+
+ if (!prev_insn)
+ break;
+ prev_insn = PREV_INSN (prev_insn);
+ }
+ }
+
+ return true;
+}
+
+
+/* Remove insns from the queue, before they become "ready" with respect
+ to FU latency considerations. */
+
+static int
+early_queue_to_ready (state_t state, struct ready_list *ready)
+{
+ rtx insn;
+ rtx link;
+ rtx next_link;
+ rtx prev_link;
+ bool move_to_ready;
+ int cost;
+ state_t temp_state = alloca (dfa_state_size);
+ int stalls;
+ int insns_removed = 0;
+
+ /*
+ Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
+ function:
+
+ X == 0: There is no limit on how many queued insns can be removed
+ prematurely. (flag_sched_stalled_insns = -1).
+
+ X >= 1: Only X queued insns can be removed prematurely in each
+ invocation. (flag_sched_stalled_insns = X).
+
+ Otherwise: Early queue removal is disabled.
+ (flag_sched_stalled_insns = 0)
+ */
+
+ if (! flag_sched_stalled_insns)
+ return 0;
+
+ for (stalls = 0; stalls <= MAX_INSN_QUEUE_INDEX; stalls++)
+ {
+ if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
+ {
+ if (sched_verbose > 6)
+ fprintf (sched_dump, ";; look at index %d + %d\n", q_ptr, stalls);
+
+ prev_link = 0;
+ while (link)
+ {
+ next_link = XEXP (link, 1);
+ insn = XEXP (link, 0);
+ if (insn && sched_verbose > 6)
+ print_rtl_single (sched_dump, insn);
+
+ memcpy (temp_state, state, dfa_state_size);
+ if (recog_memoized (insn) < 0)
+ /* non-negative to indicate that it's not ready
+ to avoid infinite Q->R->Q->R... */
+ cost = 0;
+ else
+ cost = state_transition (temp_state, insn);
+
+ if (sched_verbose >= 6)
+ fprintf (sched_dump, "transition cost = %d\n", cost);
+
+ move_to_ready = false;
+ if (cost < 0)
+ {
+ move_to_ready = ok_for_early_queue_removal (insn);
+ if (move_to_ready == true)
+ {
+ /* move from Q to R */
+ q_size -= 1;
+ ready_add (ready, insn);
+
+ if (prev_link)
+ XEXP (prev_link, 1) = next_link;
+ else
+ insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = next_link;
+
+ free_INSN_LIST_node (link);
+
+ if (sched_verbose >= 2)
+ fprintf (sched_dump, ";;\t\tEarly Q-->Ready: insn %s\n",
+ (*current_sched_info->print_insn) (insn, 0));
+
+ insns_removed++;
+ if (insns_removed == flag_sched_stalled_insns)
+ /* remove only one insn from Q at a time */
+ return insns_removed;
+ }
+ }
+
+ if (move_to_ready == false)
+ prev_link = link;
+
+ link = next_link;
+ } /* while link */
+ } /* if link */
+
+ } /* for stalls.. */
+
+ return insns_removed;
+}
+
+
/* Print the ready list for debugging purposes. Callable from debugger. */
static void
-debug_ready_list (ready)
- struct ready_list *ready;
+debug_ready_list (struct ready_list *ready)
{
rtx *p;
int i;
/* move_insn1: Remove INSN from insn chain, and link it after LAST insn. */
static rtx
-move_insn1 (insn, last)
- rtx insn, last;
+move_insn1 (rtx insn, rtx last)
{
NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
output by the instruction scheduler. Return the new value of LAST. */
static rtx
-reemit_notes (insn, last)
- rtx insn;
- rtx last;
+reemit_notes (rtx insn, rtx last)
{
rtx note, retval;
{
enum insn_note note_type = INTVAL (XEXP (note, 0));
- if (note_type == NOTE_INSN_RANGE_BEG
- || note_type == NOTE_INSN_RANGE_END)
- {
- last = emit_note_before (note_type, last);
- remove_note (insn, note);
- note = XEXP (note, 1);
- NOTE_RANGE_INFO (last) = XEXP (note, 0);
- }
- else
- {
- last = emit_note_before (note_type, last);
- remove_note (insn, note);
- note = XEXP (note, 1);
- if (note_type == NOTE_INSN_EH_REGION_BEG
- || note_type == NOTE_INSN_EH_REGION_END)
- NOTE_EH_HANDLER (last) = INTVAL (XEXP (note, 0));
- }
+ last = emit_note_before (note_type, last);
+ remove_note (insn, note);
+ note = XEXP (note, 1);
+ if (note_type == NOTE_INSN_EH_REGION_BEG
+ || note_type == NOTE_INSN_EH_REGION_END)
+ NOTE_EH_HANDLER (last) = INTVAL (XEXP (note, 0));
remove_note (insn, note);
}
}
return retval;
}
-/* Move INSN, and all insns which should be issued before it,
- due to SCHED_GROUP_P flag. Reemit notes if needed.
+/* Move INSN. Reemit notes if needed.
Return the last insn emitted by the scheduler, which is the
return value from the first call to reemit_notes. */
static rtx
-move_insn (insn, last)
- rtx insn, last;
+move_insn (rtx insn, rtx last)
{
rtx retval = NULL;
- /* If INSN has SCHED_GROUP_P set, then issue it and any other
- insns with SCHED_GROUP_P set first. */
- while (SCHED_GROUP_P (insn))
- {
- rtx prev = PREV_INSN (insn);
-
- /* Move a SCHED_GROUP_P insn. */
- move_insn1 (insn, last);
- /* If this is the first call to reemit_notes, then record
- its return value. */
- if (retval == NULL_RTX)
- retval = reemit_notes (insn, insn);
- else
- reemit_notes (insn, insn);
- insn = prev;
- }
-
- /* Now move the first non SCHED_GROUP_P insn. */
move_insn1 (insn, last);
/* If this is the first call to reemit_notes, then record
else
reemit_notes (insn, insn);
+ SCHED_GROUP_P (insn) = 0;
+
return retval;
}
+/* The following structure describe an entry of the stack of choices. */
+struct choice_entry
+{
+ /* Ordinal number of the issued insn in the ready queue. */
+ int index;
+ /* The number of the rest insns whose issues we should try. */
+ int rest;
+ /* The number of issued essential insns. */
+ int n;
+ /* State after issuing the insn. */
+ state_t state;
+};
+
+/* The following array is used to implement a stack of choices used in
+ function max_issue. */
+static struct choice_entry *choice_stack;
+
+/* The following variable value is number of essential insns issued on
+ the current cycle. An insn is essential one if it changes the
+ processors state. */
+static int cycle_issued_insns;
+
+/* The following variable value is maximal number of tries of issuing
+ insns for the first cycle multipass insn scheduling. We define
+ this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not
+ need this constraint if all real insns (with non-negative codes)
+ had reservations because in this case the algorithm complexity is
+ O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions
+ might be incomplete and such insn might occur. For such
+ descriptions, the complexity of algorithm (without the constraint)
+ could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */
+static int max_lookahead_tries;
+
+/* The following value is value of hook
+ `first_cycle_multipass_dfa_lookahead' at the last call of
+ `max_issue'. */
+static int cached_first_cycle_multipass_dfa_lookahead = 0;
+
+/* The following value is value of `issue_rate' at the last call of
+ `sched_init'. */
+static int cached_issue_rate = 0;
+
/* The following function returns maximal (or close to maximal) number
of insns which can be issued on the same cycle and one of which
- insns is insns with the best rank (the last insn in READY). To
+ insns is insns with the best rank (the first insn in READY). To
make this function tries different samples of ready insns. READY
is current queue `ready'. Global array READY_TRY reflects what
- insns are already issued in this try. STATE is current processor
- state. If the function returns nonzero, INDEX will contain index
- of the best insn in READY. *LAST_P is nonzero if the insn with the
- highest rank is in the current sample. The following function is
- used only for first cycle multipass scheduling. */
-
+ insns are already issued in this try. INDEX will contain index
+ of the best insn in READY. The following function is used only for
+ first cycle multipass scheduling. */
static int
-max_issue (ready, state, index, last_p)
- struct ready_list *ready;
- state_t state;
- int *index;
- int *last_p;
-
+max_issue (struct ready_list *ready, int *index)
{
- int i, best, n, temp_index, delay;
- state_t temp_state;
+ int n, i, all, n_ready, best, delay, tries_num;
+ struct choice_entry *top;
rtx insn;
- int max_lookahead = (*targetm.sched.first_cycle_multipass_dfa_lookahead) ();
- if (state_dead_lock_p (state))
- return 0;
-
- temp_state = alloca (dfa_state_size);
best = 0;
-
- for (i = 0; i < ready->n_ready; i++)
+ memcpy (choice_stack->state, curr_state, dfa_state_size);
+ top = choice_stack;
+ top->rest = cached_first_cycle_multipass_dfa_lookahead;
+ top->n = 0;
+ n_ready = ready->n_ready;
+ for (all = i = 0; i < n_ready; i++)
if (!ready_try [i])
- {
- insn = ready_element (ready, i);
-
- if (INSN_CODE (insn) < 0)
- continue;
-
- memcpy (temp_state, state, dfa_state_size);
-
- delay = state_transition (temp_state, insn);
-
- if (delay == 0)
- {
- if (!targetm.sched.dfa_bubble)
- continue;
- else
- {
- int j;
- rtx bubble;
-
- for (j = 0;
- (bubble = (*targetm.sched.dfa_bubble) (j)) != NULL_RTX;
- j++)
- if (state_transition (temp_state, bubble) < 0
- && state_transition (temp_state, insn) < 0)
- break;
-
- if (bubble == NULL_RTX)
- continue;
- }
- }
- else if (delay > 0)
- continue;
-
- --max_lookahead;
-
- if (max_lookahead < 0)
- break;
-
- ready_try [i] = 1;
- *last_p = 0;
-
- n = max_issue (ready, temp_state, &temp_index, last_p) + 1;
-
- if (best < n && (ready_try [0] || *last_p))
- {
- best = n;
- *index = i;
- *last_p = 1;
- }
- ready_try [i] = 0;
- }
-
+ all++;
+ i = 0;
+ tries_num = 0;
+ for (;;)
+ {
+ if (top->rest == 0 || i >= n_ready)
+ {
+ if (top == choice_stack)
+ break;
+ if (best < top - choice_stack && ready_try [0])
+ {
+ best = top - choice_stack;
+ *index = choice_stack [1].index;
+ if (top->n == issue_rate - cycle_issued_insns || best == all)
+ break;
+ }
+ i = top->index;
+ ready_try [i] = 0;
+ top--;
+ memcpy (curr_state, top->state, dfa_state_size);
+ }
+ else if (!ready_try [i])
+ {
+ tries_num++;
+ if (tries_num > max_lookahead_tries)
+ break;
+ insn = ready_element (ready, i);
+ delay = state_transition (curr_state, insn);
+ if (delay < 0)
+ {
+ if (state_dead_lock_p (curr_state))
+ top->rest = 0;
+ else
+ top->rest--;
+ n = top->n;
+ if (memcmp (top->state, curr_state, dfa_state_size) != 0)
+ n++;
+ top++;
+ top->rest = cached_first_cycle_multipass_dfa_lookahead;
+ top->index = i;
+ top->n = n;
+ memcpy (top->state, curr_state, dfa_state_size);
+ ready_try [i] = 1;
+ i = -1;
+ }
+ }
+ i++;
+ }
+ while (top != choice_stack)
+ {
+ ready_try [top->index] = 0;
+ top--;
+ }
+ memcpy (curr_state, choice_stack->state, dfa_state_size);
return best;
}
cycle multipass scheduling. */
static rtx
-choose_ready (ready)
- struct ready_list *ready;
+choose_ready (struct ready_list *ready)
{
- if (!targetm.sched.first_cycle_multipass_dfa_lookahead
- || (*targetm.sched.first_cycle_multipass_dfa_lookahead) () <= 0)
+ int lookahead = 0;
+
+ if (targetm.sched.first_cycle_multipass_dfa_lookahead)
+ lookahead = (*targetm.sched.first_cycle_multipass_dfa_lookahead) ();
+ if (lookahead <= 0 || SCHED_GROUP_P (ready_element (ready, 0)))
return ready_remove_first (ready);
else
{
/* Try to choose the better insn. */
- int index;
- int last_p = 0;
-
- if (max_issue (ready, curr_state, &index, &last_p) == 0)
+ int index = 0, i;
+ rtx insn;
+
+ if (cached_first_cycle_multipass_dfa_lookahead != lookahead)
+ {
+ cached_first_cycle_multipass_dfa_lookahead = lookahead;
+ max_lookahead_tries = 100;
+ for (i = 0; i < issue_rate; i++)
+ max_lookahead_tries *= lookahead;
+ }
+ insn = ready_element (ready, 0);
+ if (INSN_CODE (insn) < 0)
+ return ready_remove_first (ready);
+ for (i = 1; i < ready->n_ready; i++)
+ {
+ insn = ready_element (ready, i);
+ ready_try [i]
+ = (INSN_CODE (insn) < 0
+ || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard
+ && !(*targetm.sched.first_cycle_multipass_dfa_lookahead_guard) (insn)));
+ }
+ if (max_issue (ready, &index) == 0)
return ready_remove_first (ready);
else
return ready_remove (ready, index);
}
}
+/* Called from backends from targetm.sched.reorder to emit stuff into
+ the instruction stream. */
+
+rtx
+sched_emit_insn (rtx pat)
+{
+ rtx insn = emit_insn_after (pat, last_scheduled_insn);
+ last_scheduled_insn = insn;
+ return insn;
+}
+
/* Use forward list scheduling to rearrange insns of block B in region RGN,
possibly bringing insns from subsequent blocks in the same region. */
void
-schedule_block (b, rgn_n_insns)
- int b;
- int rgn_n_insns;
+schedule_block (int b, int rgn_n_insns)
{
- rtx last;
struct ready_list ready;
- int first_cycle_insn_p;
+ int i, first_cycle_insn_p;
int can_issue_more;
state_t temp_state = NULL; /* It is used for multipass scheduling. */
+ int sort_p, advance, start_clock_var;
/* Head/tail info for this block. */
rtx prev_head = current_sched_info->prev_head;
init_block_visualization ();
}
- if (targetm.sched.use_dfa_pipeline_interface)
+ if (targetm.sched.use_dfa_pipeline_interface
+ && (*targetm.sched.use_dfa_pipeline_interface) ())
state_reset (curr_state);
else
clear_units ();
/* Allocate the ready list. */
ready.veclen = rgn_n_insns + 1 + issue_rate;
ready.first = ready.veclen - 1;
- ready.vec = (rtx *) xmalloc (ready.veclen * sizeof (rtx));
+ ready.vec = xmalloc (ready.veclen * sizeof (rtx));
ready.n_ready = 0;
- if (targetm.sched.use_dfa_pipeline_interface)
+ if (targetm.sched.use_dfa_pipeline_interface
+ && (*targetm.sched.use_dfa_pipeline_interface) ())
{
/* It is used for first cycle multipass scheduling. */
temp_state = alloca (dfa_state_size);
- ready_try = (char *) xmalloc ((rgn_n_insns + 1) * sizeof (char));
- memset (ready_try, 0, (rgn_n_insns + 1) * sizeof (char));
+ ready_try = xcalloc ((rgn_n_insns + 1), sizeof (char));
+ choice_stack = xmalloc ((rgn_n_insns + 1)
+ * sizeof (struct choice_entry));
+ for (i = 0; i <= rgn_n_insns; i++)
+ choice_stack[i].state = xmalloc (dfa_state_size);
}
(*current_sched_info->init_ready_list) (&ready);
if (targetm.sched.md_init)
(*targetm.sched.md_init) (sched_dump, sched_verbose, ready.veclen);
- /* No insns scheduled in this block yet. */
- last_scheduled_insn = 0;
+ /* We start inserting insns after PREV_HEAD. */
+ last_scheduled_insn = prev_head;
/* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
queue. */
q_ptr = 0;
q_size = 0;
- if (!targetm.sched.use_dfa_pipeline_interface)
+ if (!targetm.sched.use_dfa_pipeline_interface
+ || !(*targetm.sched.use_dfa_pipeline_interface) ())
max_insn_queue_index_macro_value = INSN_QUEUE_SIZE - 1;
else
max_insn_queue_index_macro_value = max_insn_queue_index;
- insn_queue = (rtx *) alloca ((MAX_INSN_QUEUE_INDEX + 1) * sizeof (rtx));
- memset ((char *) insn_queue, 0, (MAX_INSN_QUEUE_INDEX + 1) * sizeof (rtx));
+ insn_queue = alloca ((MAX_INSN_QUEUE_INDEX + 1) * sizeof (rtx));
+ memset (insn_queue, 0, (MAX_INSN_QUEUE_INDEX + 1) * sizeof (rtx));
last_clock_var = -1;
/* Start just before the beginning of time. */
clock_var = -1;
+ advance = 0;
- /* We start inserting insns after PREV_HEAD. */
- last = prev_head;
-
+ sort_p = TRUE;
/* Loop until all the insns in BB are scheduled. */
while ((*current_sched_info->schedule_more_p) ())
{
- clock_var++;
-
- if (targetm.sched.use_dfa_pipeline_interface)
+ do
{
- if (targetm.sched.dfa_pre_cycle_insn)
- state_transition (curr_state,
- (*targetm.sched.dfa_pre_cycle_insn) ());
+ start_clock_var = clock_var;
- /* Advance time on one cycle. */
- state_transition (curr_state, NULL);
+ clock_var++;
- if (targetm.sched.dfa_post_cycle_insn)
- state_transition (curr_state,
- (*targetm.sched.dfa_post_cycle_insn) ());
- }
+ advance_one_cycle ();
- /* Add to the ready list all pending insns that can be issued now.
- If there are no ready insns, increment clock until one
- is ready and add all pending insns at that point to the ready
- list. */
- queue_to_ready (&ready);
+ /* Add to the ready list all pending insns that can be issued now.
+ If there are no ready insns, increment clock until one
+ is ready and add all pending insns at that point to the ready
+ list. */
+ queue_to_ready (&ready);
- if (sched_verbose && targetm.sched.cycle_display)
- last = (*targetm.sched.cycle_display) (clock_var, last);
+ if (ready.n_ready == 0)
+ abort ();
- if (ready.n_ready == 0)
- abort ();
+ if (sched_verbose >= 2)
+ {
+ fprintf (sched_dump, ";;\t\tReady list after queue_to_ready: ");
+ debug_ready_list (&ready);
+ }
+ advance -= clock_var - start_clock_var;
+ }
+ while (advance > 0);
- if (sched_verbose >= 2)
+ if (sort_p)
{
- fprintf (sched_dump, ";;\t\tReady list after queue_to_ready: ");
- debug_ready_list (&ready);
- }
+ /* Sort the ready list based on priority. */
+ ready_sort (&ready);
- /* Sort the ready list based on priority. */
- ready_sort (&ready);
+ if (sched_verbose >= 2)
+ {
+ fprintf (sched_dump, ";;\t\tReady list after ready_sort: ");
+ debug_ready_list (&ready);
+ }
+ }
/* Allow the target to reorder the list, typically for
better instruction bundling. */
- if (targetm.sched.reorder)
+ if (sort_p && targetm.sched.reorder
+ && (ready.n_ready == 0
+ || !SCHED_GROUP_P (ready_element (&ready, 0))))
can_issue_more =
(*targetm.sched.reorder) (sched_dump, sched_verbose,
ready_lastpos (&ready),
can_issue_more = issue_rate;
first_cycle_insn_p = 1;
+ cycle_issued_insns = 0;
for (;;)
{
rtx insn;
int cost;
- if (sched_verbose)
+ if (sched_verbose >= 2)
{
fprintf (sched_dump, ";;\tReady list (t =%3d): ",
clock_var);
debug_ready_list (&ready);
}
- if (!targetm.sched.use_dfa_pipeline_interface)
+ if (!targetm.sched.use_dfa_pipeline_interface
+ || !(*targetm.sched.use_dfa_pipeline_interface) ())
{
if (ready.n_ready == 0 || !can_issue_more
|| !(*current_sched_info->schedule_more_p) ())
break;
- insn = choose_ready (&ready);
+ insn = ready_remove_first (&ready);
cost = actual_hazard (insn_unit (insn), insn, clock_var, 0);
}
else
{
+ if (ready.n_ready == 0
+ && can_issue_more
+ && reload_completed)
+ {
+ /* Allow scheduling insns directly from the queue in case
+ there's nothing better to do (ready list is empty) but
+ there are still vacant dispatch slots in the current cycle. */
+ if (sched_verbose >= 6)
+ fprintf(sched_dump,";;\t\tSecond chance\n");
+ memcpy (temp_state, curr_state, dfa_state_size);
+ if (early_queue_to_ready (temp_state, &ready))
+ ready_sort (&ready);
+ }
+
if (ready.n_ready == 0 || !can_issue_more
|| state_dead_lock_p (curr_state)
|| !(*current_sched_info->schedule_more_p) ())
break;
-
+
/* Select and remove the insn from the ready list. */
- insn = choose_ready (&ready);
-
+ if (sort_p)
+ insn = choose_ready (&ready);
+ else
+ insn = ready_remove_first (&ready);
+
+ if (targetm.sched.dfa_new_cycle
+ && (*targetm.sched.dfa_new_cycle) (sched_dump, sched_verbose,
+ insn, last_clock_var,
+ clock_var, &sort_p))
+ {
+ ready_add (&ready, insn);
+ break;
+ }
+
+ sort_p = TRUE;
+ memcpy (temp_state, curr_state, dfa_state_size);
if (recog_memoized (insn) < 0)
{
if (!first_cycle_insn_p
}
else
{
- cost = state_transition (curr_state, insn);
+ cost = state_transition (temp_state, insn);
if (targetm.sched.first_cycle_multipass_dfa_lookahead
&& targetm.sched.dfa_bubble)
{
int j;
rtx bubble;
-
+
for (j = 0;
(bubble = (*targetm.sched.dfa_bubble) (j))
!= NULL_RTX;
j++)
{
memcpy (temp_state, curr_state, dfa_state_size);
-
+
if (state_transition (temp_state, bubble) < 0
&& state_transition (temp_state, insn) < 0)
break;
}
-
+
if (bubble != NULL_RTX)
{
- memcpy (curr_state, temp_state, dfa_state_size);
-
if (insert_schedule_bubbles_p)
{
rtx copy;
-
+
copy = copy_rtx (PATTERN (bubble));
- emit_insn_after (copy, last);
- last = NEXT_INSN (last);
- INSN_CODE (last) = INSN_CODE (bubble);
-
+ emit_insn_after (copy, last_scheduled_insn);
+ last_scheduled_insn
+ = NEXT_INSN (last_scheduled_insn);
+ INSN_CODE (last_scheduled_insn)
+ = INSN_CODE (bubble);
+
/* Annotate the same for the first insns
scheduling by using mode. */
- PUT_MODE (last, (clock_var > last_clock_var
- ? clock_var - last_clock_var
- : VOIDmode));
+ PUT_MODE (last_scheduled_insn,
+ (clock_var > last_clock_var
+ ? clock_var - last_clock_var
+ : VOIDmode));
last_clock_var = clock_var;
-
+
if (sched_verbose >= 2)
{
fprintf (sched_dump,
";;\t\t--> scheduling bubble insn <<<%d>>>:reservation ",
- INSN_UID (last));
-
- if (recog_memoized (last) < 0)
+ INSN_UID (last_scheduled_insn));
+
+ if (recog_memoized (last_scheduled_insn)
+ < 0)
fprintf (sched_dump, "nothing");
else
- print_reservation (sched_dump, last);
-
+ print_reservation
+ (sched_dump, last_scheduled_insn);
+
fprintf (sched_dump, "\n");
}
}
if (! (*current_sched_info->can_schedule_ready_p) (insn))
goto next;
- last_scheduled_insn = insn;
- last = move_insn (insn, last);
+ last_scheduled_insn = move_insn (insn, last_scheduled_insn);
+
+ if (targetm.sched.use_dfa_pipeline_interface
+ && (*targetm.sched.use_dfa_pipeline_interface) ())
+ {
+ if (memcmp (curr_state, temp_state, dfa_state_size) != 0)
+ cycle_issued_insns++;
+ memcpy (curr_state, temp_state, dfa_state_size);
+ }
if (targetm.sched.variable_issue)
can_issue_more =
(*targetm.sched.variable_issue) (sched_dump, sched_verbose,
insn, can_issue_more);
- else
+ /* A naked CLOBBER or USE generates no instruction, so do
+ not count them against the issue rate. */
+ else if (GET_CODE (PATTERN (insn)) != USE
+ && GET_CODE (PATTERN (insn)) != CLOBBER)
can_issue_more--;
- schedule_insn (insn, &ready, clock_var);
+ advance = schedule_insn (insn, &ready, clock_var);
+ if (advance != 0)
+ break;
next:
first_cycle_insn_p = 0;
- if (targetm.sched.reorder2)
+ /* Sort the ready list based on priority. This must be
+ redone here, as schedule_insn may have readied additional
+ insns that will not be sorted correctly. */
+ if (ready.n_ready > 0)
+ ready_sort (&ready);
+
+ if (targetm.sched.reorder2
+ && (ready.n_ready == 0
+ || !SCHED_GROUP_P (ready_element (&ready, 0))))
{
- /* Sort the ready list based on priority. */
- if (ready.n_ready > 0)
- ready_sort (&ready);
can_issue_more =
- (*targetm.sched.reorder2) (sched_dump,sched_verbose,
+ (*targetm.sched.reorder2) (sched_dump, sched_verbose,
ready.n_ready
? ready_lastpos (&ready) : NULL,
&ready.n_ready, clock_var);
}
}
- if (!targetm.sched.use_dfa_pipeline_interface && sched_verbose)
+ if ((!targetm.sched.use_dfa_pipeline_interface
+ || !(*targetm.sched.use_dfa_pipeline_interface) ())
+ && sched_verbose)
/* Debug info. */
visualize_scheduled_insns (clock_var);
}
{
fprintf (sched_dump, ";;\tReady list (final): ");
debug_ready_list (&ready);
- if (!targetm.sched.use_dfa_pipeline_interface)
+ if (!targetm.sched.use_dfa_pipeline_interface
+ || !(*targetm.sched.use_dfa_pipeline_interface) ())
print_block_visualization ("");
}
/* Update head/tail boundaries. */
head = NEXT_INSN (prev_head);
- tail = last;
+ tail = last_scheduled_insn;
+
+ if (!reload_completed)
+ {
+ rtx insn, link, next;
+
+ /* INSN_TICK (minimum clock tick at which the insn becomes
+ ready) may be not correct for the insn in the subsequent
+ blocks of the region. We should use a correct value of
+ `clock_var' or modify INSN_TICK. It is better to keep
+ clock_var value equal to 0 at the start of a basic block.
+ Therefore we modify INSN_TICK here. */
+ for (insn = head; insn != tail; insn = NEXT_INSN (insn))
+ if (INSN_P (insn))
+ {
+ for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
+ {
+ next = XEXP (link, 0);
+ INSN_TICK (next) -= clock_var;
+ }
+ }
+ }
/* Restore-other-notes: NOTE_LIST is the end of a chain of notes
previously found among the insns. Insert them at the beginning
free (ready.vec);
- if (targetm.sched.use_dfa_pipeline_interface)
- free (ready_try);
+ if (targetm.sched.use_dfa_pipeline_interface
+ && (*targetm.sched.use_dfa_pipeline_interface) ())
+ {
+ free (ready_try);
+ for (i = 0; i <= rgn_n_insns; i++)
+ free (choice_stack [i].state);
+ free (choice_stack);
+ }
}
\f
/* Set_priorities: compute priority of each insn in the block. */
int
-set_priorities (head, tail)
- rtx head, tail;
+set_priorities (rtx head, rtx tail)
{
rtx insn;
int n_insn;
-
+ int sched_max_insns_priority =
+ current_sched_info->sched_max_insns_priority;
rtx prev_head;
prev_head = PREV_INSN (head);
return 0;
n_insn = 0;
+ sched_max_insns_priority = 0;
for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
{
if (GET_CODE (insn) == NOTE)
continue;
- if (!(SCHED_GROUP_P (insn)))
- n_insn++;
+ n_insn++;
(void) priority (insn);
+
+ if (INSN_PRIORITY_KNOWN (insn))
+ sched_max_insns_priority =
+ MAX (sched_max_insns_priority, INSN_PRIORITY (insn));
}
+ sched_max_insns_priority += 1;
+ current_sched_info->sched_max_insns_priority =
+ sched_max_insns_priority;
return n_insn;
}
for debugging output. */
void
-sched_init (dump_file)
- FILE *dump_file;
+sched_init (FILE *dump_file)
{
- int luid, b;
+ int luid;
+ basic_block b;
rtx insn;
int i;
else
issue_rate = 1;
+ if (cached_issue_rate != issue_rate)
+ {
+ cached_issue_rate = issue_rate;
+ /* To invalidate max_lookahead_tries: */
+ cached_first_cycle_multipass_dfa_lookahead = 0;
+ }
+
/* We use LUID 0 for the fake insn (UID 0) which holds dependencies for
pseudos which do not cross calls. */
old_max_uid = get_max_uid () + 1;
- h_i_d = (struct haifa_insn_data *) xcalloc (old_max_uid, sizeof (*h_i_d));
+ h_i_d = xcalloc (old_max_uid, sizeof (*h_i_d));
for (i = 0; i < old_max_uid; i++)
h_i_d [i].cost = -1;
- if (targetm.sched.use_dfa_pipeline_interface)
+ if (targetm.sched.use_dfa_pipeline_interface
+ && (*targetm.sched.use_dfa_pipeline_interface) ())
{
if (targetm.sched.init_dfa_pre_cycle_insn)
(*targetm.sched.init_dfa_pre_cycle_insn) ();
-
+
if (targetm.sched.init_dfa_post_cycle_insn)
(*targetm.sched.init_dfa_post_cycle_insn) ();
-
+
if (targetm.sched.first_cycle_multipass_dfa_lookahead
&& targetm.sched.init_dfa_bubbles)
(*targetm.sched.init_dfa_bubbles) ();
-
+
dfa_start ();
dfa_state_size = state_size ();
curr_state = xmalloc (dfa_state_size);
h_i_d[0].luid = 0;
luid = 1;
- for (b = 0; b < n_basic_blocks; b++)
- for (insn = BLOCK_HEAD (b);; insn = NEXT_INSN (insn))
+ FOR_EACH_BB (b)
+ for (insn = b->head;; insn = NEXT_INSN (insn))
{
INSN_LUID (insn) = luid;
if (GET_CODE (insn) != NOTE)
++luid;
- if (insn == BLOCK_END (b))
+ if (insn == b->end)
break;
}
init_dependency_caches (luid);
- compute_bb_for_insn (old_max_uid);
-
init_alias_analysis ();
if (write_symbols != NO_DEBUG)
{
rtx line;
- line_note_head = (rtx *) xcalloc (n_basic_blocks, sizeof (rtx));
+ line_note_head = xcalloc (last_basic_block, sizeof (rtx));
/* Save-line-note-head:
Determine the line-number at the start of each basic block.
predecessor has been scheduled, it is impossible to accurately
determine the correct line number for the first insn of the block. */
- for (b = 0; b < n_basic_blocks; b++)
+ FOR_EACH_BB (b)
{
- for (line = BLOCK_HEAD (b); line; line = PREV_INSN (line))
+ for (line = b->head; line; line = PREV_INSN (line))
if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
{
- line_note_head[b] = line;
+ line_note_head[b->index] = line;
break;
}
/* Do a forward search as well, since we won't get to see the first
notes in a basic block. */
- for (line = BLOCK_HEAD (b); line; line = NEXT_INSN (line))
+ for (line = b->head; line; line = NEXT_INSN (line))
{
if (INSN_P (line))
break;
if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
- line_note_head[b] = line;
+ line_note_head[b->index] = line;
}
}
}
- if (!targetm.sched.use_dfa_pipeline_interface && sched_verbose)
+ if ((!targetm.sched.use_dfa_pipeline_interface
+ || !(*targetm.sched.use_dfa_pipeline_interface) ())
+ && sched_verbose)
/* Find units used in this function, for visualization. */
init_target_units ();
/* ??? Add a NOTE after the last insn of the last basic block. It is not
known why this is done. */
- insn = BLOCK_END (n_basic_blocks - 1);
+ insn = EXIT_BLOCK_PTR->prev_bb->end;
if (NEXT_INSN (insn) == 0
|| (GET_CODE (insn) != NOTE
&& GET_CODE (insn) != CODE_LABEL
/* Don't emit a NOTE if it would end up before a BARRIER. */
&& GET_CODE (NEXT_INSN (insn)) != BARRIER))
- emit_note_after (NOTE_INSN_DELETED, BLOCK_END (n_basic_blocks - 1));
+ {
+ emit_note_after (NOTE_INSN_DELETED, EXIT_BLOCK_PTR->prev_bb->end);
+ /* Make insn to appear outside BB. */
+ EXIT_BLOCK_PTR->prev_bb->end = PREV_INSN (EXIT_BLOCK_PTR->prev_bb->end);
+ }
/* Compute INSN_REG_WEIGHT for all blocks. We must do this before
removing death notes. */
- for (b = n_basic_blocks - 1; b >= 0; b--)
- find_insn_reg_weight (b);
+ FOR_EACH_BB_REVERSE (b)
+ find_insn_reg_weight (b->index);
}
/* Free global data used during insn scheduling. */
void
-sched_finish ()
+sched_finish (void)
{
free (h_i_d);
- if (targetm.sched.use_dfa_pipeline_interface)
+ if (targetm.sched.use_dfa_pipeline_interface
+ && (*targetm.sched.use_dfa_pipeline_interface) ())
{
free (curr_state);
dfa_finish ();
OSDN Git Service
