/* Instruction scheduling pass.
Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
- 1999, 2000 Free Software Foundation, Inc.
+ 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
and currently maintained by, Jim Wilson (wilson@cygnus.com)
-This file is part of GNU CC.
+This file is part of GCC.
-GNU CC is free software; you can redistribute it and/or modify it
-under the terms of the GNU General Public License as published by the
-Free Software Foundation; either version 2, or (at your option) any
-later version.
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 2, or (at your option) any later
+version.
-GNU CC is distributed in the hope that it will be useful, but WITHOUT
-ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License
-along with GNU CC; see the file COPYING. If not, write to the Free
-the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+along with GCC; see the file COPYING. If not, write to the Free
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
/* Instruction scheduling pass. This file, along with sched-deps.c,
contains the generic parts. The actual entry point is found for
as short as possible. The remaining insns are then scheduled in
remaining slots.
- Function unit conflicts are resolved during forward list scheduling
- by tracking the time when each insn is committed to the schedule
- and from that, the time the function units it uses must be free.
- As insns on the ready list are considered for scheduling, those
- that would result in a blockage of the already committed insns are
- queued until no blockage will result.
-
The following list shows the order in which we want to break ties
among insns in the ready list:
This pass must update information that subsequent passes expect to
be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
- reg_n_calls_crossed, and reg_live_length. Also, BLOCK_HEAD,
- BLOCK_END.
+ reg_n_calls_crossed, and reg_live_length. Also, BB_HEAD, BB_END.
The information in the line number notes is carefully retained by
this pass. Notes that refer to the starting and ending of
\f
#include "config.h"
#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
#include "toplev.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
-#include "basic-block.h"
#include "regs.h"
#include "function.h"
#include "flags.h"
#include "insn-config.h"
#include "insn-attr.h"
-#include "insn-flags.h"
#include "except.h"
#include "toplev.h"
#include "recog.h"
#include "sched-int.h"
+#include "target.h"
#ifdef INSN_SCHEDULING
static int issue_rate;
-#ifndef ISSUE_RATE
-#define ISSUE_RATE 1
-#endif
-
/* sched-verbose controls the amount of debugging output the
scheduler prints. It is controlled by -fsched-verbose=N:
N>0 and no -DSR : the output is directed to stderr.
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);
else
- warning ("fix_sched_param: unknown param: %s", param);
+ warning (0, "fix_sched_param: unknown param: %s", param);
}
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)
"Pending" list have their dependencies satisfied and move to either
the "Ready" list or the "Queued" set depending on whether
sufficient time has passed to make them ready. As time passes,
- insns move from the "Queued" set to the "Ready" list. Insns may
- move from the "Ready" list to the "Queued" set if they are blocked
- due to a function unit conflict.
+ insns move from the "Queued" set to the "Ready" list.
The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled
insns, i.e., those that are ready, queued, and pending.
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 `queue_insn' when an
- 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.
The transition (Q->R) is implemented in 'queue_to_insn' as time
passes or stalls are introduced. */
/* Implement a circular buffer to delay instructions until sufficient
- time has passed. INSN_QUEUE_SIZE is a power of two larger than
- MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c. This is the
- longest time an isnsn may be queued. */
-static rtx insn_queue[INSN_QUEUE_SIZE];
+ time has passed. For the new pipeline description interface,
+ MAX_INSN_QUEUE_INDEX is a power of two minus one which is larger
+ than maximal time of instruction execution computed by genattr.c on
+ the base maximal time of functional unit reservations and getting a
+ result. This is the longest time an insn may be queued. */
+
+static rtx *insn_queue;
static int q_ptr = 0;
static int q_size = 0;
-#define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
-#define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
+#define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
+#define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
+
+/* The following variable value refers for all current and future
+ reservations of the processor units. */
+state_t curr_state;
+
+/* The following variable value is size of memory representing all
+ current and future reservations of the processor units. */
+static size_t dfa_state_size;
+
+/* The following array is used to find the best insn from ready when
+ the automaton pipeline interface is used. */
+static char *ready_try;
/* Describe the ready list of the scheduler.
VEC holds space enough for all insns in the current region. VECLEN
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) \
+ (REG_P (x) \
+ || ((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. */
-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 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. */
+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 (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
static rtx last_scheduled_insn;
-/* 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
- mask if the value is negative. A function unit index is the
- non-negative encoding. */
-
-HAIFA_INLINE int
-insn_unit (insn)
- rtx insn;
-{
- register int unit = INSN_UNIT (insn);
-
- if (unit == 0)
- {
- recog_memoized (insn);
-
- /* A USE insn, or something else we don't need to understand.
- We can't pass these directly to function_units_used because it will
- trigger a fatal error for unrecognizable insns. */
- if (INSN_CODE (insn) < 0)
- unit = -1;
- else
- {
- unit = function_units_used (insn);
- /* Increment non-negative values so we can cache zero. */
- if (unit >= 0)
- unit++;
- }
- /* We only cache 16 bits of the result, so if the value is out of
- range, don't cache it. */
- if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
- || unit >= 0
- || (unit & ~((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
- INSN_UNIT (insn) = unit;
- }
- return (unit > 0 ? unit - 1 : unit);
-}
-
-/* Compute the blockage range for executing INSN on UNIT. This caches
- the value returned by the blockage_range_function for the unit.
- These values are encoded in an int where the upper half gives the
- minimum value and the lower half gives the maximum value. */
-
-HAIFA_INLINE static unsigned int
-blockage_range (unit, insn)
- int unit;
- rtx insn;
-{
- unsigned int blockage = INSN_BLOCKAGE (insn);
- unsigned int range;
-
- 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
- the values fit. */
- if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
- INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
- }
- else
- range = BLOCKAGE_RANGE (blockage);
-
- return range;
-}
-
-/* A vector indexed by function unit instance giving the last insn to use
- the unit. The value of the function unit instance index for unit U
- instance I is (U + I * FUNCTION_UNITS_SIZE). */
-static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
-
-/* A vector indexed by function unit instance giving the minimum time when
- the unit will unblock based on the maximum blockage cost. */
-static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
-
-/* A vector indexed by function unit number giving the number of insns
- that remain to use the unit. */
-static int unit_n_insns[FUNCTION_UNITS_SIZE];
-
-/* Access the unit_last_insn array. Used by the visualization code. */
-
-rtx
-get_unit_last_insn (instance)
- int instance;
-{
- return unit_last_insn[instance];
-}
-
-/* Reset the function unit state to the null state. */
-
-static void
-clear_units ()
-{
- 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));
-}
-
-/* Return the issue-delay of an insn. */
-
-HAIFA_INLINE int
-insn_issue_delay (insn)
- rtx insn;
-{
- int i, delay = 0;
- int unit = insn_unit (insn);
-
- /* Efficiency note: in fact, we are working 'hard' to compute a
- value that was available in md file, and is not available in
- function_units[] structure. It would be nice to have this
- value there, too. */
- if (unit >= 0)
- {
- if (function_units[unit].blockage_range_function &&
- function_units[unit].blockage_function)
- delay = function_units[unit].blockage_function (insn, insn);
- }
- else
- for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
- if ((unit & 1) != 0 && function_units[i].blockage_range_function
- && function_units[i].blockage_function)
- delay = MAX (delay, function_units[i].blockage_function (insn, insn));
-
- return delay;
-}
-
-/* Return the actual hazard cost of executing INSN on the unit UNIT,
- instance INSTANCE at time CLOCK if the previous actual hazard cost
- was COST. */
-
-HAIFA_INLINE int
-actual_hazard_this_instance (unit, instance, insn, clock, cost)
- int unit, instance, clock, cost;
- rtx insn;
-{
- int tick = unit_tick[instance]; /* Issue time of the last issued insn. */
-
- if (tick - clock > cost)
- {
- /* The scheduler is operating forward, so unit's last insn is the
- executing insn and INSN is the candidate insn. We want a
- more exact measure of the blockage if we execute INSN at CLOCK
- given when we committed the execution of the unit's last insn.
-
- The blockage value is given by either the unit's max blockage
- constant, blockage range function, or blockage function. Use
- the most exact form for the given unit. */
-
- if (function_units[unit].blockage_range_function)
- {
- if (function_units[unit].blockage_function)
- tick += (function_units[unit].blockage_function
- (unit_last_insn[instance], insn)
- - function_units[unit].max_blockage);
- else
- tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
- - function_units[unit].max_blockage);
- }
- if (tick - clock > cost)
- cost = tick - clock;
- }
- return cost;
-}
-
-/* Record INSN as having begun execution on the units encoded by UNIT at
- time CLOCK. */
-
-HAIFA_INLINE static void
-schedule_unit (unit, insn, clock)
- int unit, clock;
- rtx insn;
-{
- int i;
-
- if (unit >= 0)
- {
- int instance = unit;
-#if MAX_MULTIPLICITY > 1
- /* Find the first free instance of the function unit and use that
- one. We assume that one is free. */
- for (i = function_units[unit].multiplicity - 1; i > 0; i--)
- {
- if (!actual_hazard_this_instance (unit, instance, insn, clock, 0))
- break;
- instance += FUNCTION_UNITS_SIZE;
- }
-#endif
- unit_last_insn[instance] = insn;
- unit_tick[instance] = (clock + function_units[unit].max_blockage);
- }
- else
- for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
- if ((unit & 1) != 0)
- schedule_unit (i, insn, clock);
-}
-
-/* Return the actual hazard cost of executing INSN on the units encoded by
- UNIT at time CLOCK if the previous actual hazard cost was COST. */
-
-HAIFA_INLINE static int
-actual_hazard (unit, insn, clock, cost)
- int unit, clock, cost;
- rtx insn;
-{
- int i;
-
- if (unit >= 0)
- {
- /* Find the instance of the function unit with the minimum hazard. */
- int instance = unit;
- int best_cost = actual_hazard_this_instance (unit, instance, insn,
- clock, cost);
-#if MAX_MULTIPLICITY > 1
- int this_cost;
-
- if (best_cost > cost)
- {
- for (i = function_units[unit].multiplicity - 1; i > 0; i--)
- {
- instance += FUNCTION_UNITS_SIZE;
- this_cost = actual_hazard_this_instance (unit, instance, insn,
- clock, cost);
- if (this_cost < best_cost)
- {
- best_cost = this_cost;
- if (this_cost <= cost)
- break;
- }
- }
- }
-#endif
- cost = MAX (cost, best_cost);
- }
- else
- for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
- if ((unit & 1) != 0)
- cost = actual_hazard (i, insn, clock, cost);
-
- return cost;
-}
-
-/* Return the potential hazard cost of executing an instruction on the
- units encoded by UNIT if the previous potential hazard cost was COST.
- An insn with a large blockage time is chosen in preference to one
- with a smaller time; an insn that uses a unit that is more likely
- to be used is chosen in preference to one with a unit that is less
- used. We are trying to minimize a subsequent actual hazard. */
-
-HAIFA_INLINE static int
-potential_hazard (unit, insn, cost)
- int unit, cost;
- rtx insn;
-{
- int i, ncost;
- unsigned int minb, maxb;
-
- if (unit >= 0)
- {
- minb = maxb = function_units[unit].max_blockage;
- if (maxb > 1)
- {
- if (function_units[unit].blockage_range_function)
- {
- maxb = minb = blockage_range (unit, insn);
- maxb = MAX_BLOCKAGE_COST (maxb);
- minb = MIN_BLOCKAGE_COST (minb);
- }
-
- if (maxb > 1)
- {
- /* Make the number of instructions left dominate. Make the
- minimum delay dominate the maximum delay. If all these
- are the same, use the unit number to add an arbitrary
- ordering. Other terms can be added. */
- ncost = minb * 0x40 + maxb;
- ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
- if (ncost > cost)
- cost = ncost;
- }
- }
- }
- else
- for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
- if ((unit & 1) != 0)
- cost = potential_hazard (i, insn, cost);
-
- return cost;
-}
-
/* Compute cost of executing INSN given the dependence LINK on the insn USED.
This is the number of cycles between instruction issue and
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)
+ if (cost < 0)
{
- recog_memoized (insn);
-
- /* A USE insn, or something else we don't need to understand.
- We can't pass these directly to result_ready_cost because it will
- trigger a fatal error for unrecognizable insns. */
- if (INSN_CODE (insn) < 0)
+ /* A USE insn, or something else we don't need to
+ understand. We can't pass these directly to
+ result_ready_cost or insn_default_latency because it will
+ trigger a fatal error for unrecognizable insns. */
+ if (recog_memoized (insn) < 0)
{
- INSN_COST (insn) = 1;
- return 1;
+ INSN_COST (insn) = 0;
+ return 0;
}
else
{
- cost = result_ready_cost (insn);
-
- if (cost < 1)
- cost = 1;
+ cost = insn_default_latency (insn);
+ if (cost < 0)
+ cost = 0;
INSN_COST (insn) = cost;
}
}
/* In this case estimate cost without caring how insn is used. */
- if (link == 0 && used == 0)
+ if (link == 0 || used == 0)
return cost;
- /* A USE insn should never require the value used to be computed. This
- allows the computation of a function's result and parameter values to
- overlap the return and call. */
- recog_memoized (used);
- if (INSN_CODE (used) < 0)
- LINK_COST_FREE (link) = 1;
-
- /* If some dependencies vary the cost, compute the adjustment. Most
- commonly, the adjustment is complete: either the cost is ignored
- (in the case of an output- or anti-dependence), or the cost is
- unchanged. These values are cached in the link as LINK_COST_FREE
- and LINK_COST_ZERO. */
-
- if (LINK_COST_FREE (link))
+ /* A USE insn should never require the value used to be computed.
+ This allows the computation of a function's result and parameter
+ values to overlap the return and call. */
+ if (recog_memoized (used) < 0)
cost = 0;
-#ifdef ADJUST_COST
- else if (!LINK_COST_ZERO (link))
+ else
{
- int ncost = cost;
-
- ADJUST_COST (used, link, insn, ncost);
- if (ncost < 1)
+ if (INSN_CODE (insn) >= 0)
{
- LINK_COST_FREE (link) = 1;
- ncost = 0;
+ if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
+ cost = 0;
+ else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
+ {
+ cost = (insn_default_latency (insn)
+ - insn_default_latency (used));
+ if (cost <= 0)
+ cost = 1;
+ }
+ else if (bypass_p (insn))
+ cost = insn_latency (insn, used);
}
- if (cost == ncost)
- LINK_COST_ZERO (link) = 1;
- cost = ncost;
+
+ if (targetm.sched.adjust_cost)
+ cost = targetm.sched.adjust_cost (used, link, insn, cost);
+
+ if (cost < 0)
+ cost = 0;
}
-#endif
+
return cost;
}
/* Compute the priority number for INSN. */
static int
-priority (insn)
- rtx insn;
+priority (rtx insn)
{
- int this_priority;
rtx link;
if (! INSN_P (insn))
return 0;
- if ((this_priority = INSN_PRIORITY (insn)) == 0)
+ if (! INSN_PRIORITY_KNOWN (insn))
{
+ int this_priority = 0;
+
if (INSN_DEPEND (insn) == 0)
this_priority = insn_cost (insn, 0, 0);
else
- for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
- {
- rtx next;
- int next_priority;
-
- if (RTX_INTEGRATED_P (link))
- continue;
+ {
+ for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
+ {
+ rtx next;
+ int next_priority;
- next = XEXP (link, 0);
+ next = XEXP (link, 0);
- /* Critical path is meaningful in block boundaries only. */
- if (! (*current_sched_info->contributes_to_priority) (next, insn))
- continue;
+ /* Critical path is meaningful in block boundaries only. */
+ if (! (*current_sched_info->contributes_to_priority) (next, insn))
+ continue;
- next_priority = insn_cost (insn, link, next) + priority (next);
- if (next_priority > this_priority)
- this_priority = next_priority;
- }
+ next_priority = insn_cost (insn, link, next) + priority (next);
+ if (next_priority > this_priority)
+ this_priority = next_priority;
+ }
+ }
INSN_PRIORITY (insn) = this_priority;
+ INSN_PRIORITY_KNOWN (insn) = 1;
}
- return this_priority;
+
+ return INSN_PRIORITY (insn);
}
\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 ();
+ gcc_assert (ready->n_ready);
return ready->vec + ready->first - ready->n_ready + 1;
}
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)
- abort ();
+
+ gcc_assert (ready->n_ready);
t = ready->vec[ready->first--];
ready->n_ready--;
/* If the queue becomes empty, reset it. */
return t;
}
+/* The following code implements multi-pass scheduling for the first
+ cycle. In other words, we will try to choose ready insn which
+ permits to start maximum number of insns on the same cycle. */
+
+/* Return a pointer to the element INDEX from the ready. INDEX for
+ insn with the highest priority is 0, and the lowest priority has
+ N_READY - 1. */
+
+HAIFA_INLINE static rtx
+ready_element (struct ready_list *ready, int index)
+{
+ gcc_assert (ready->n_ready && index < ready->n_ready);
+
+ return ready->vec[ready->first - index];
+}
+
+/* Remove the element INDEX from the ready list and return it. INDEX
+ for insn with the highest priority is 0, and the lowest priority
+ has N_READY - 1. */
+
+HAIFA_INLINE static rtx
+ready_remove (struct ready_list *ready, int index)
+{
+ rtx t;
+ int i;
+
+ if (index == 0)
+ return ready_remove_first (ready);
+ gcc_assert (ready->n_ready && index < ready->n_ready);
+ t = ready->vec[ready->first - index];
+ ready->n_ready--;
+ for (i = index; i < ready->n_ready; i++)
+ ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
+ return t;
+}
+
+
/* Sort the ready list READY by ascending priority, using the SCHED_SORT
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 ATTRIBUTE_UNUSED;
+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
Revisit when we have a machine model to work with and not before. */
-#ifdef ADJUST_PRIORITY
- ADJUST_PRIORITY (prev);
-#endif
+ if (targetm.sched.adjust_priority)
+ INSN_PRIORITY (prev) =
+ targetm.sched.adjust_priority (prev, INSN_PRIORITY (prev));
+}
+
+/* Advance time on one cycle. */
+HAIFA_INLINE static void
+advance_one_cycle (void)
+{
+ 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. */
/* 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 unit;
-
- unit = insn_unit (insn);
+ int advance = 0;
+ int premature_issue = 0;
- if (sched_verbose >= 2)
+ if (sched_verbose >= 1)
{
- fprintf (sched_dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ",
- INSN_UID (insn));
- insn_print_units (insn);
- fprintf (sched_dump, "\n");
- }
+ char buf[2048];
- if (sched_verbose && unit == -1)
- visualize_no_unit (insn);
+ print_insn (buf, insn, 0);
+ buf[40] = 0;
+ fprintf (sched_dump, ";;\t%3i--> %-40s:", clock, buf);
- if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose)
- schedule_unit (unit, insn, clock);
+ if (recog_memoized (insn) < 0)
+ fprintf (sched_dump, "nothing");
+ else
+ print_reservation (sched_dump, insn);
+ fputc ('\n', sched_dump);
+ }
- if (INSN_DEPEND (insn) == 0)
- return;
+ 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);
- while (insn != tail && GET_CODE (insn) == NOTE)
+ while (insn != tail && NOTE_P (insn))
{
rtx next = NEXT_INSN (insn);
/* Delete the note from its current position. */
PREV_INSN (next) = prev;
/* See sched_analyze to see how these are handled. */
- if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_SETJMP
- && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
+ 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);
- while (insn != tail && GET_CODE (insn) == NOTE)
+ while (insn != tail && NOTE_P (insn))
{
rtx next = NEXT_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);
- rtx tail = BLOCK_END (b);
+ rtx head = BB_HEAD (BASIC_BLOCK (b));
+ rtx tail = BB_END (BASIC_BLOCK (b));
/* Don't include any notes or labels at the beginning of the
basic block, or notes at the ends of basic blocks. */
while (head != tail)
{
- if (GET_CODE (head) == NOTE)
+ if (NOTE_P (head))
head = NEXT_INSN (head);
- else if (GET_CODE (tail) == NOTE)
+ else if (NOTE_P (tail))
tail = PREV_INSN (tail);
- else if (GET_CODE (head) == CODE_LABEL)
+ else if (LABEL_P (head))
head = NEXT_INSN (head);
else
break;
/* 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))
{
- if (GET_CODE (head) != NOTE && GET_CODE (head) != CODE_LABEL)
+ if (!NOTE_P (head) && !LABEL_P (head))
return 0;
head = NEXT_INSN (head);
}
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;
/* Farm out notes, and maybe save them in NOTE_LIST.
This is needed to keep the debugger from
getting completely deranged. */
- if (GET_CODE (insn) == NOTE)
+ if (NOTE_P (insn))
{
prev = insn;
insn = unlink_line_notes (insn, next_tail);
- if (prev == tail)
- abort ();
- if (prev == head)
- abort ();
- if (insn == next_tail)
- abort ();
+ gcc_assert (prev != tail && prev != head && insn != next_tail);
}
}
}
/* 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;
next_tail = NEXT_INSN (tail);
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
- if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
+ if (NOTE_P (insn) && NOTE_LINE_NUMBER (insn) > 0)
line = insn;
else
LINE_NOTE (insn) = line;
}
-/* After block B was scheduled, insert line notes into the insns list.
+/* 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 (b, head, tail)
- int b;
- rtx head, tail;
+restore_line_notes (rtx head, rtx tail)
{
rtx line, note, prev, new;
int added_notes = 0;
of this block. If it happens to be the same, then we don't want to
emit another line number note here. */
for (line = head; line; line = PREV_INSN (line))
- if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
+ if (NOTE_P (line) && NOTE_LINE_NUMBER (line) > 0)
break;
/* Walk the insns keeping track of the current line-number and inserting
the line-number notes as needed. */
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
- if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
+ if (NOTE_P (insn) && NOTE_LINE_NUMBER (insn) > 0)
line = insn;
/* This used to emit line number notes before every non-deleted note.
However, this confuses a debugger, because line notes not separated
by real instructions all end up at the same address. I can find no
use for line number notes before other notes, so none are emitted. */
- else if (GET_CODE (insn) != NOTE
+ else if (!NOTE_P (insn)
&& INSN_UID (insn) < old_max_uid
&& (note = LINE_NOTE (insn)) != 0
&& note != line
&& (line == 0
+#ifdef USE_MAPPED_LOCATION
+ || NOTE_SOURCE_LOCATION (note) != NOTE_SOURCE_LOCATION (line)
+#else
|| NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
- || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
+ || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)
+#endif
+ ))
{
line = note;
prev = PREV_INSN (insn);
{
added_notes++;
new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
+#ifndef USE_MAPPED_LOCATION
NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
- RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note);
+#endif
}
}
if (sched_verbose && added_notes)
insns list. */
void
-rm_redundant_line_notes ()
+rm_redundant_line_notes (void)
{
rtx line = 0;
rtx insn = get_insns ();
are already present. The remainder tend to occur at basic
block boundaries. */
for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
- if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
+ if (NOTE_P (insn) && NOTE_LINE_NUMBER (insn) > 0)
{
/* If there are no active insns following, INSN is redundant. */
if (active_insn == 0)
{
notes++;
- NOTE_SOURCE_FILE (insn) = 0;
- NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
+ SET_INSN_DELETED (insn);
}
/* If the line number is unchanged, LINE is redundant. */
else if (line
+#ifdef USE_MAPPED_LOCATION
+ && NOTE_SOURCE_LOCATION (line) == NOTE_SOURCE_LOCATION (insn)
+#else
&& NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
- && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
+ && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn)
+#endif
+)
{
notes++;
- NOTE_SOURCE_FILE (line) = 0;
- NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
+ SET_INSN_DELETED (line);
line = insn;
}
else
line = insn;
active_insn = 0;
}
- else if (!((GET_CODE (insn) == NOTE
+ else if (!((NOTE_P (insn)
&& NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
- || (GET_CODE (insn) == INSN
+ || (NONJUMP_INSN_P (insn)
&& (GET_CODE (PATTERN (insn)) == USE
|| GET_CODE (PATTERN (insn)) == CLOBBER))))
active_insn++;
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;
/* Farm out notes, and maybe save them in NOTE_LIST.
This is needed to keep the debugger from
getting completely deranged. */
- if (GET_CODE (insn) == NOTE)
+ if (NOTE_P (insn))
{
prev = insn;
insn = unlink_other_notes (insn, next_tail);
- if (prev == tail)
- abort ();
- if (prev == head)
- abort ();
- if (insn == next_tail)
- abort ();
+ gcc_assert (prev != tail && prev != head && insn != next_tail);
}
}
}
/* 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 (REG_P (SET_DEST (x)))
+ {
+ 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 < INSN_QUEUE_SIZE; stalls++)
+ for (stalls = 1; stalls <= max_insn_queue_index; stalls++)
{
if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
{
}
insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
- if (ready->n_ready)
- break;
+ advance_one_cycle ();
+
+ break;
}
+
+ advance_one_cycle ();
}
- if (sched_verbose && stalls)
- visualize_stall_cycles (stalls);
q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
clock_var += 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 (!NOTE_P (prev_insn))
+ {
+ 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;
if (ready->n_ready == 0)
- return;
+ {
+ fprintf (sched_dump, "\n");
+ return;
+ }
p = ready_lastpos (ready);
for (i = 0; i < ready->n_ready; 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);
return insn;
}
-/* Search INSN for REG_SAVE_NOTE note pairs for NOTE_INSN_SETJMP,
+/* Search INSN for REG_SAVE_NOTE note pairs for
NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
NOTEs. The REG_SAVE_NOTE note following first one is contains the
saved value for NOTE_BLOCK_NUMBER which is useful for
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_SETJMP)
- {
- retval = emit_note_after (NOTE_INSN_SETJMP, insn);
- CONST_CALL_P (retval) = CONST_CALL_P (note);
- remove_note (insn, note);
- note = XEXP (note, 1);
- }
- else 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);
}
}
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 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. 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 (struct ready_list *ready, int *index)
+{
+ int n, i, all, n_ready, best, delay, tries_num;
+ struct choice_entry *top;
+ rtx insn;
+
+ best = 0;
+ 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])
+ 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;
+}
+
+/* The following function chooses insn from READY and modifies
+ *N_READY and READY. The following function is used only for first
+ cycle multipass scheduling. */
+
+static rtx
+choose_ready (struct ready_list *ready)
+{
+ 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 = 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);
+ }
+}
+
/* 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 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;
and caused problems because schedule_block and compute_forward_dependences
had different notions of what the "head" insn was. */
- if (head == tail && (! INSN_P (head)))
- abort ();
+ gcc_assert (head != tail || INSN_P (head));
/* Debug info. */
if (sched_verbose)
{
- fprintf (sched_dump, ";; ======================================================\n");
+ fprintf (sched_dump,
+ ";; ======================================================\n");
fprintf (sched_dump,
";; -- basic block %d from %d to %d -- %s reload\n",
b, INSN_UID (head), INSN_UID (tail),
(reload_completed ? "after" : "before"));
- fprintf (sched_dump, ";; ======================================================\n");
+ fprintf (sched_dump,
+ ";; ======================================================\n");
fprintf (sched_dump, "\n");
-
- visualize_alloc ();
- init_block_visualization ();
}
- clear_units ();
+ state_reset (curr_state);
/* Allocate the ready list. */
- ready.veclen = rgn_n_insns + 1 + ISSUE_RATE;
+ 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;
+ /* It is used for first cycle multipass scheduling. */
+ temp_state = alloca (dfa_state_size);
+ 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);
-#ifdef MD_SCHED_INIT
- MD_SCHED_INIT (sched_dump, sched_verbose, ready.veclen);
-#endif
+ 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;
- last_clock_var = 0;
- memset ((char *) insn_queue, 0, sizeof (insn_queue));
+
+ 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++;
+ do
+ {
+ start_clock_var = clock_var;
- /* 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);
+ clock_var++;
-#ifdef HAVE_cycle_display
- if (HAVE_cycle_display)
- last = emit_insn_after (gen_cycle_display (GEN_INT (clock_var)), last);
-#endif
+ advance_one_cycle ();
- if (ready.n_ready == 0)
- abort ();
+ /* 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 >= 2)
- {
- fprintf (sched_dump, ";;\t\tReady list after queue_to_ready: ");
- debug_ready_list (&ready);
+ gcc_assert (ready.n_ready);
+
+ 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);
- /* Sort the ready list based on priority. */
- ready_sort (&ready);
+ if (sort_p)
+ {
+ /* 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. */
-#ifdef MD_SCHED_REORDER
- MD_SCHED_REORDER (sched_dump, sched_verbose, ready_lastpos (&ready),
- ready.n_ready, clock_var, can_issue_more);
-#else
- can_issue_more = issue_rate;
-#endif
+ 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),
+ &ready.n_ready, clock_var);
+ else
+ can_issue_more = issue_rate;
- if (sched_verbose)
+ first_cycle_insn_p = 1;
+ cycle_issued_insns = 0;
+ for (;;)
{
- fprintf (sched_dump, "\n;;\tReady list (t =%3d): ", clock_var);
- debug_ready_list (&ready);
- }
+ rtx insn;
+ int cost;
+ bool asm_p = false;
+
+ if (sched_verbose >= 2)
+ {
+ fprintf (sched_dump, ";;\tReady list (t =%3d): ",
+ clock_var);
+ debug_ready_list (&ready);
+ }
+
+ 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;
- /* Issue insns from ready list. */
- while (ready.n_ready != 0
- && can_issue_more
- && (*current_sched_info->schedule_more_p) ())
- {
/* Select and remove the insn from the ready list. */
- rtx insn = ready_remove_first (&ready);
- int cost = actual_hazard (insn_unit (insn), insn, clock_var, 0);
+ 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)
+ {
+ asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT
+ || asm_noperands (PATTERN (insn)) >= 0);
+ if (!first_cycle_insn_p && asm_p)
+ /* This is asm insn which is tryed to be issued on the
+ cycle not first. Issue it on the next cycle. */
+ cost = 1;
+ else
+ /* A USE insn, or something else we don't need to
+ understand. We can't pass these directly to
+ state_transition because it will trigger a
+ fatal error for unrecognizable insns. */
+ cost = 0;
+ }
+ else
+ {
+ cost = state_transition (temp_state, insn);
+ if (cost < 0)
+ cost = 0;
+ else if (cost == 0)
+ cost = 1;
+ }
if (cost >= 1)
{
queue_insn (insn, cost);
+ if (SCHED_GROUP_P (insn))
+ {
+ advance = cost;
+ break;
+ }
+
continue;
}
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);
-#ifdef MD_SCHED_VARIABLE_ISSUE
- MD_SCHED_VARIABLE_ISSUE (sched_dump, sched_verbose, insn,
- can_issue_more);
-#else
- can_issue_more--;
-#endif
+ 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);
+ /* 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--;
+
+ advance = schedule_insn (insn, &ready, clock_var);
- schedule_insn (insn, &ready, clock_var);
+ /* After issuing an asm insn we should start a new cycle. */
+ if (advance == 0 && asm_p)
+ advance = 1;
+ if (advance != 0)
+ break;
next:
- ;
-#ifdef MD_SCHED_REORDER2
- /* Sort the ready list based on priority. */
+ first_cycle_insn_p = 0;
+
+ /* 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);
- MD_SCHED_REORDER2 (sched_dump, sched_verbose,
- ready.n_ready ? ready_lastpos (&ready) : NULL,
- ready.n_ready, clock_var, can_issue_more);
-#endif
- }
- /* Debug info. */
- if (sched_verbose)
- visualize_scheduled_insns (clock_var);
+ if (targetm.sched.reorder2
+ && (ready.n_ready == 0
+ || !SCHED_GROUP_P (ready_element (&ready, 0))))
+ {
+ can_issue_more =
+ targetm.sched.reorder2 (sched_dump, sched_verbose,
+ ready.n_ready
+ ? ready_lastpos (&ready) : NULL,
+ &ready.n_ready, clock_var);
+ }
+ }
}
-#ifdef MD_SCHED_FINISH
- MD_SCHED_FINISH (sched_dump, sched_verbose);
-#endif
+ if (targetm.sched.md_finish)
+ targetm.sched.md_finish (sched_dump, sched_verbose);
/* Debug info. */
if (sched_verbose)
{
fprintf (sched_dump, ";;\tReady list (final): ");
debug_ready_list (&ready);
- print_block_visualization ("");
}
/* Sanity check -- queue must be empty now. Meaningless if region has
multiple bbs. */
- if (current_sched_info->queue_must_finish_empty && q_size != 0)
- abort ();
+ gcc_assert (!current_sched_info->queue_must_finish_empty || !q_size);
/* 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
clock_var, INSN_UID (head));
fprintf (sched_dump, ";; new tail = %d\n\n",
INSN_UID (tail));
- visualize_free ();
}
current_sched_info->head = head;
current_sched_info->tail = tail;
free (ready.vec);
+
+ 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)
+ if (NOTE_P (insn))
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;
/* Disable speculative loads in their presence if cc0 defined. */
#ifdef HAVE_cc0
? stderr : dump_file);
/* Initialize issue_rate. */
- issue_rate = ISSUE_RATE;
+ if (targetm.sched.issue_rate)
+ issue_rate = targetm.sched.issue_rate ();
+ else
+ issue_rate = 1;
- split_all_insns (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.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 ();
+
+ 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 = BB_HEAD (b); ; insn = NEXT_INSN (insn))
{
INSN_LUID (insn) = luid;
schedule differently depending on whether or not there are
line-number notes, i.e., depending on whether or not we're
generating debugging information. */
- if (GET_CODE (insn) != NOTE)
+ if (!NOTE_P (insn))
++luid;
- if (insn == BLOCK_END (b))
+ if (insn == BB_END (b))
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))
- if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
+ for (line = BB_HEAD (b); line; line = PREV_INSN (line))
+ if (NOTE_P (line) && 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 = BB_HEAD (b); 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;
+ if (NOTE_P (line) && NOTE_LINE_NUMBER (line) > 0)
+ line_note_head[b->index] = line;
}
}
}
- /* Find units used in this fuction, for visualization. */
- if (sched_verbose)
- 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 = BB_END (EXIT_BLOCK_PTR->prev_bb);
if (NEXT_INSN (insn) == 0
- || (GET_CODE (insn) != NOTE
- && GET_CODE (insn) != CODE_LABEL
+ || (!NOTE_P (insn)
+ && !LABEL_P (insn)
/* 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));
+ && !BARRIER_P (NEXT_INSN (insn))))
+ {
+ emit_note_after (NOTE_INSN_DELETED, BB_END (EXIT_BLOCK_PTR->prev_bb));
+ /* Make insn to appear outside BB. */
+ BB_END (EXIT_BLOCK_PTR->prev_bb) = PREV_INSN (BB_END (EXIT_BLOCK_PTR->prev_bb));
+ }
/* 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);
+
+ if (targetm.sched.md_init_global)
+ targetm.sched.md_init_global (sched_dump, sched_verbose, old_max_uid);
}
/* Free global data used during insn scheduling. */
void
-sched_finish ()
+sched_finish (void)
{
free (h_i_d);
+ free (curr_state);
+ dfa_finish ();
free_dependency_caches ();
end_alias_analysis ();
if (write_symbols != NO_DEBUG)
free (line_note_head);
+
+ if (targetm.sched.md_finish_global)
+ targetm.sched.md_finish_global (sched_dump, sched_verbose);
}
#endif /* INSN_SCHEDULING */