/* Instruction scheduling pass.
Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
- 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
+ 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
Free Software Foundation, Inc.
Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
and currently maintained by, Jim Wilson (wilson@cygnus.com)
#include "coretypes.h"
#include "tm.h"
#include "diagnostic-core.h"
+#include "hard-reg-set.h"
#include "rtl.h"
#include "tm_p.h"
-#include "hard-reg-set.h"
#include "regs.h"
#include "function.h"
#include "flags.h"
#include "recog.h"
#include "sched-int.h"
#include "target.h"
+#include "common/common-target.h"
#include "output.h"
#include "params.h"
#include "vecprim.h"
#include "cfgloop.h"
#include "ira.h"
#include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
+#include "hashtab.h"
#ifdef INSN_SCHEDULING
int issue_rate;
+/* This can be set to true by a backend if the scheduler should not
+ enable a DCE pass. */
+bool sched_no_dce;
+
+/* The current initiation interval used when modulo scheduling. */
+static int modulo_ii;
+
+/* The maximum number of stages we are prepared to handle. */
+static int modulo_max_stages;
+
+/* The number of insns that exist in each iteration of the loop. We use this
+ to detect when we've scheduled all insns from the first iteration. */
+static int modulo_n_insns;
+
+/* The current count of insns in the first iteration of the loop that have
+ already been scheduled. */
+static int modulo_insns_scheduled;
+
+/* The maximum uid of insns from the first iteration of the loop. */
+static int modulo_iter0_max_uid;
+
+/* The number of times we should attempt to backtrack when modulo scheduling.
+ Decreased each time we have to backtrack. */
+static int modulo_backtracks_left;
+
+/* The stage in which the last insn from the original loop was
+ scheduled. */
+static int modulo_last_stage;
+
/* 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.
struct common_sched_info_def *common_sched_info;
#define INSN_TICK(INSN) (HID (INSN)->tick)
+#define INSN_EXACT_TICK(INSN) (HID (INSN)->exact_tick)
+#define INSN_TICK_ESTIMATE(INSN) (HID (INSN)->tick_estimate)
#define INTER_TICK(INSN) (HID (INSN)->inter_tick)
+#define FEEDS_BACKTRACK_INSN(INSN) (HID (INSN)->feeds_backtrack_insn)
+#define SHADOW_P(INSN) (HID (INSN)->shadow_p)
+#define MUST_RECOMPUTE_SPEC_P(INSN) (HID (INSN)->must_recompute_spec)
/* If INSN_TICK of an instruction is equal to INVALID_TICK,
then it should be recalculated from scratch. */
/* Scheduling clock. */
static int clock_var;
+/* Clock at which the previous instruction was issued. */
+static int last_clock_var;
+
+/* Set to true if, when queuing a shadow insn, we discover that it would be
+ scheduled too late. */
+static bool must_backtrack;
+
+/* 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. */
+int cycle_issued_insns;
+
+/* This records the actual schedule. It is built up during the main phase
+ of schedule_block, and afterwards used to reorder the insns in the RTL. */
+static VEC(rtx, heap) *scheduled_insns;
+
static int may_trap_exp (const_rtx, int);
/* Nonzero iff the address is comprised from at most 1 register. */
SCHED_PASS_UNKNOWN /* sched_pass_id */
};
-const struct sched_scan_info_def *sched_scan_info;
-
/* Mapping from instruction UID to its Logical UID. */
VEC (int, heap) *sched_luids = NULL;
/* Create empty basic block after the specified block. */
basic_block (* sched_create_empty_bb) (basic_block);
+/* Return the number of cycles until INSN is expected to be ready.
+ Return zero if it already is. */
+static int
+insn_delay (rtx insn)
+{
+ return MAX (INSN_TICK (insn) - clock_var, 0);
+}
+
static int
may_trap_exp (const_rtx x, int is_store)
{
{
return haifa_classify_rtx (PATTERN (insn));
}
+\f
+/* After the scheduler initialization function has been called, this function
+ can be called to enable modulo scheduling. II is the initiation interval
+ we should use, it affects the delays for delay_pairs that were recorded as
+ separated by a given number of stages.
+
+ MAX_STAGES provides us with a limit
+ after which we give up scheduling; the caller must have unrolled at least
+ as many copies of the loop body and recorded delay_pairs for them.
+
+ INSNS is the number of real (non-debug) insns in one iteration of
+ the loop. MAX_UID can be used to test whether an insn belongs to
+ the first iteration of the loop; all of them have a uid lower than
+ MAX_UID. */
+void
+set_modulo_params (int ii, int max_stages, int insns, int max_uid)
+{
+ modulo_ii = ii;
+ modulo_max_stages = max_stages;
+ modulo_n_insns = insns;
+ modulo_iter0_max_uid = max_uid;
+ modulo_backtracks_left = PARAM_VALUE (PARAM_MAX_MODULO_BACKTRACK_ATTEMPTS);
+}
+
+/* A structure to record a pair of insns where the first one is a real
+ insn that has delay slots, and the second is its delayed shadow.
+ I1 is scheduled normally and will emit an assembly instruction,
+ while I2 describes the side effect that takes place at the
+ transition between cycles CYCLES and (CYCLES + 1) after I1. */
+struct delay_pair
+{
+ struct delay_pair *next_same_i1;
+ rtx i1, i2;
+ int cycles;
+ /* When doing modulo scheduling, we a delay_pair can also be used to
+ show that I1 and I2 are the same insn in a different stage. If that
+ is the case, STAGES will be nonzero. */
+ int stages;
+};
+
+/* Two hash tables to record delay_pairs, one indexed by I1 and the other
+ indexed by I2. */
+static htab_t delay_htab;
+static htab_t delay_htab_i2;
+
+/* Called through htab_traverse. Walk the hashtable using I2 as
+ index, and delete all elements involving an UID higher than
+ that pointed to by *DATA. */
+static int
+htab_i2_traverse (void **slot, void *data)
+{
+ int maxuid = *(int *)data;
+ struct delay_pair *p = *(struct delay_pair **)slot;
+ if (INSN_UID (p->i2) >= maxuid || INSN_UID (p->i1) >= maxuid)
+ {
+ htab_clear_slot (delay_htab_i2, slot);
+ }
+ return 1;
+}
+
+/* Called through htab_traverse. Walk the hashtable using I2 as
+ index, and delete all elements involving an UID higher than
+ that pointed to by *DATA. */
+static int
+htab_i1_traverse (void **slot, void *data)
+{
+ int maxuid = *(int *)data;
+ struct delay_pair **pslot = (struct delay_pair **)slot;
+ struct delay_pair *p, *first, **pprev;
+
+ if (INSN_UID ((*pslot)->i1) >= maxuid)
+ {
+ htab_clear_slot (delay_htab, slot);
+ return 1;
+ }
+ pprev = &first;
+ for (p = *pslot; p; p = p->next_same_i1)
+ {
+ if (INSN_UID (p->i2) < maxuid)
+ {
+ *pprev = p;
+ pprev = &p->next_same_i1;
+ }
+ }
+ *pprev = NULL;
+ if (first == NULL)
+ htab_clear_slot (delay_htab, slot);
+ else
+ *pslot = first;
+ return 1;
+}
+
+/* Discard all delay pairs which involve an insn with an UID higher
+ than MAX_UID. */
+void
+discard_delay_pairs_above (int max_uid)
+{
+ htab_traverse (delay_htab, htab_i1_traverse, &max_uid);
+ htab_traverse (delay_htab_i2, htab_i2_traverse, &max_uid);
+}
+
+/* Returns a hash value for X (which really is a delay_pair), based on
+ hashing just I1. */
+static hashval_t
+delay_hash_i1 (const void *x)
+{
+ return htab_hash_pointer (((const struct delay_pair *) x)->i1);
+}
+
+/* Returns a hash value for X (which really is a delay_pair), based on
+ hashing just I2. */
+static hashval_t
+delay_hash_i2 (const void *x)
+{
+ return htab_hash_pointer (((const struct delay_pair *) x)->i2);
+}
+/* Return nonzero if I1 of pair X is the same as that of pair Y. */
+static int
+delay_i1_eq (const void *x, const void *y)
+{
+ return ((const struct delay_pair *) x)->i1 == y;
+}
+
+/* Return nonzero if I2 of pair X is the same as that of pair Y. */
+static int
+delay_i2_eq (const void *x, const void *y)
+{
+ return ((const struct delay_pair *) x)->i2 == y;
+}
+
+/* This function can be called by a port just before it starts the final
+ scheduling pass. It records the fact that an instruction with delay
+ slots has been split into two insns, I1 and I2. The first one will be
+ scheduled normally and initiates the operation. The second one is a
+ shadow which must follow a specific number of cycles after I1; its only
+ purpose is to show the side effect that occurs at that cycle in the RTL.
+ If a JUMP_INSN or a CALL_INSN has been split, I1 should be a normal INSN,
+ while I2 retains the original insn type.
+
+ There are two ways in which the number of cycles can be specified,
+ involving the CYCLES and STAGES arguments to this function. If STAGES
+ is zero, we just use the value of CYCLES. Otherwise, STAGES is a factor
+ which is multiplied by MODULO_II to give the number of cycles. This is
+ only useful if the caller also calls set_modulo_params to enable modulo
+ scheduling. */
+
+void
+record_delay_slot_pair (rtx i1, rtx i2, int cycles, int stages)
+{
+ struct delay_pair *p = XNEW (struct delay_pair);
+ struct delay_pair **slot;
+
+ p->i1 = i1;
+ p->i2 = i2;
+ p->cycles = cycles;
+ p->stages = stages;
+
+ if (!delay_htab)
+ {
+ delay_htab = htab_create (10, delay_hash_i1, delay_i1_eq, NULL);
+ delay_htab_i2 = htab_create (10, delay_hash_i2, delay_i2_eq, free);
+ }
+ slot = ((struct delay_pair **)
+ htab_find_slot_with_hash (delay_htab, i1, htab_hash_pointer (i1),
+ INSERT));
+ p->next_same_i1 = *slot;
+ *slot = p;
+ slot = ((struct delay_pair **)
+ htab_find_slot_with_hash (delay_htab_i2, i2, htab_hash_pointer (i2),
+ INSERT));
+ *slot = p;
+}
+
+/* Examine the delay pair hashtable to see if INSN is a shadow for another,
+ and return the other insn if so. Return NULL otherwise. */
+rtx
+real_insn_for_shadow (rtx insn)
+{
+ struct delay_pair *pair;
+
+ if (delay_htab == NULL)
+ return NULL_RTX;
+
+ pair
+ = (struct delay_pair *)htab_find_with_hash (delay_htab_i2, insn,
+ htab_hash_pointer (insn));
+ if (!pair || pair->stages > 0)
+ return NULL_RTX;
+ return pair->i1;
+}
+
+/* For a pair P of insns, return the fixed distance in cycles from the first
+ insn after which the second must be scheduled. */
+static int
+pair_delay (struct delay_pair *p)
+{
+ if (p->stages == 0)
+ return p->cycles;
+ else
+ return p->stages * modulo_ii;
+}
+
+/* Given an insn INSN, add a dependence on its delayed shadow if it
+ has one. Also try to find situations where shadows depend on each other
+ and add dependencies to the real insns to limit the amount of backtracking
+ needed. */
+void
+add_delay_dependencies (rtx insn)
+{
+ struct delay_pair *pair;
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ if (!delay_htab)
+ return;
+
+ pair
+ = (struct delay_pair *)htab_find_with_hash (delay_htab_i2, insn,
+ htab_hash_pointer (insn));
+ if (!pair)
+ return;
+ add_dependence (insn, pair->i1, REG_DEP_ANTI);
+ if (pair->stages)
+ return;
+
+ FOR_EACH_DEP (pair->i2, SD_LIST_BACK, sd_it, dep)
+ {
+ rtx pro = DEP_PRO (dep);
+ struct delay_pair *other_pair
+ = (struct delay_pair *)htab_find_with_hash (delay_htab_i2, pro,
+ htab_hash_pointer (pro));
+ if (!other_pair || other_pair->stages)
+ continue;
+ if (pair_delay (other_pair) >= pair_delay (pair))
+ {
+ if (sched_verbose >= 4)
+ {
+ fprintf (sched_dump, ";;\tadding dependence %d <- %d\n",
+ INSN_UID (other_pair->i1),
+ INSN_UID (pair->i1));
+ fprintf (sched_dump, ";;\tpair1 %d <- %d, cost %d\n",
+ INSN_UID (pair->i1),
+ INSN_UID (pair->i2),
+ pair_delay (pair));
+ fprintf (sched_dump, ";;\tpair2 %d <- %d, cost %d\n",
+ INSN_UID (other_pair->i1),
+ INSN_UID (other_pair->i2),
+ pair_delay (other_pair));
+ }
+ add_dependence (pair->i1, other_pair->i1, REG_DEP_ANTI);
+ }
+ }
+}
+\f
/* Forward declarations. */
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 void queue_insn (rtx, int, const char *);
static int schedule_insn (rtx);
static void adjust_priority (rtx);
static void advance_one_cycle (void);
static void extend_h_i_d (void);
static void init_h_i_d (rtx);
+static int haifa_speculate_insn (rtx, ds_t, rtx *);
static void generate_recovery_code (rtx);
static void process_insn_forw_deps_be_in_spec (rtx, rtx, ds_t);
static void begin_speculative_block (rtx);
static void init_before_recovery (basic_block *);
static void create_check_block_twin (rtx, bool);
static void fix_recovery_deps (basic_block);
-static void haifa_change_pattern (rtx, rtx);
+static bool haifa_change_pattern (rtx, rtx);
static void dump_new_block_header (int, basic_block, rtx, rtx);
static void restore_bb_notes (basic_block);
static void fix_jump_move (rtx);
static void clear_priorities (rtx, rtx_vec_t *);
static void calc_priorities (rtx_vec_t);
static void add_jump_dependencies (rtx, rtx);
-#ifdef ENABLE_CHECKING
-static int has_edge_p (VEC(edge,gc) *, int);
-static void check_cfg (rtx, rtx);
-#endif
#endif /* INSN_SCHEDULING */
\f
/* Do register pressure sensitive insn scheduling if the flag is set
up. */
-bool sched_pressure_p;
+enum sched_pressure_algorithm sched_pressure;
-/* Map regno -> its cover class. The map defined only when
- SCHED_PRESSURE_P is true. */
-enum reg_class *sched_regno_cover_class;
+/* Map regno -> its pressure class. The map defined only when
+ SCHED_PRESSURE != SCHED_PRESSURE_NONE. */
+enum reg_class *sched_regno_pressure_class;
-/* The current register pressure. Only elements corresponding cover
+/* The current register pressure. Only elements corresponding pressure
classes are defined. */
static int curr_reg_pressure[N_REG_CLASSES];
bitmap_clear (region_ref_regs);
}
-/* Update current register pressure related info after birth (if
- BIRTH_P) or death of register REGNO. */
-static void
-mark_regno_birth_or_death (int regno, bool birth_p)
+/* PRESSURE[CL] describes the pressure on register class CL. Update it
+ for the birth (if BIRTH_P) or death (if !BIRTH_P) of register REGNO.
+ LIVE tracks the set of live registers; if it is null, assume that
+ every birth or death is genuine. */
+static inline void
+mark_regno_birth_or_death (bitmap live, int *pressure, int regno, bool birth_p)
{
- enum reg_class cover_class;
+ enum reg_class pressure_class;
- cover_class = sched_regno_cover_class[regno];
+ pressure_class = sched_regno_pressure_class[regno];
if (regno >= FIRST_PSEUDO_REGISTER)
{
- if (cover_class != NO_REGS)
+ if (pressure_class != NO_REGS)
{
if (birth_p)
{
- bitmap_set_bit (curr_reg_live, regno);
- curr_reg_pressure[cover_class]
- += ira_reg_class_nregs[cover_class][PSEUDO_REGNO_MODE (regno)];
+ if (!live || bitmap_set_bit (live, regno))
+ pressure[pressure_class]
+ += (ira_reg_class_max_nregs
+ [pressure_class][PSEUDO_REGNO_MODE (regno)]);
}
else
{
- bitmap_clear_bit (curr_reg_live, regno);
- curr_reg_pressure[cover_class]
- -= ira_reg_class_nregs[cover_class][PSEUDO_REGNO_MODE (regno)];
+ if (!live || bitmap_clear_bit (live, regno))
+ pressure[pressure_class]
+ -= (ira_reg_class_max_nregs
+ [pressure_class][PSEUDO_REGNO_MODE (regno)]);
}
}
}
- else if (cover_class != NO_REGS
+ else if (pressure_class != NO_REGS
&& ! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
{
if (birth_p)
{
- bitmap_set_bit (curr_reg_live, regno);
- curr_reg_pressure[cover_class]++;
+ if (!live || bitmap_set_bit (live, regno))
+ pressure[pressure_class]++;
}
else
{
- bitmap_clear_bit (curr_reg_live, regno);
- curr_reg_pressure[cover_class]--;
+ if (!live || bitmap_clear_bit (live, regno))
+ pressure[pressure_class]--;
}
}
}
unsigned int j;
bitmap_iterator bi;
- for (i = 0; i < ira_reg_class_cover_size; i++)
- curr_reg_pressure[ira_reg_class_cover[i]] = 0;
+ for (i = 0; i < ira_pressure_classes_num; i++)
+ curr_reg_pressure[ira_pressure_classes[i]] = 0;
bitmap_clear (curr_reg_live);
EXECUTE_IF_SET_IN_BITMAP (live, 0, j, bi)
- if (current_nr_blocks == 1 || bitmap_bit_p (region_ref_regs, j))
- mark_regno_birth_or_death (j, true);
+ if (sched_pressure == SCHED_PRESSURE_MODEL
+ || current_nr_blocks == 1
+ || bitmap_bit_p (region_ref_regs, j))
+ mark_regno_birth_or_death (curr_reg_live, curr_reg_pressure, j, true);
}
/* Mark registers in X as mentioned in the current region. */
if (REG_P (x))
{
regno = REGNO (x);
- if (regno >= FIRST_PSEUDO_REGISTER)
- bitmap_set_bit (region_ref_regs, REGNO (x));
+ if (HARD_REGISTER_NUM_P (regno))
+ bitmap_set_range (region_ref_regs, regno,
+ hard_regno_nregs[regno][GET_MODE (x)]);
else
- for (i = hard_regno_nregs[regno][GET_MODE (x)] - 1; i >= 0; i--)
- bitmap_set_bit (region_ref_regs, regno + i);
+ bitmap_set_bit (region_ref_regs, REGNO (x));
return;
}
fmt = GET_RTX_FORMAT (code);
if (regno == INVALID_REGNUM)
break;
if (! bitmap_bit_p (df_get_live_in (bb), regno))
- mark_regno_birth_or_death (regno, true);
+ mark_regno_birth_or_death (curr_reg_live, curr_reg_pressure,
+ regno, true);
}
#endif
}
{
int i;
- for (i = 0; i < ira_reg_class_cover_size; i++)
- saved_reg_pressure[ira_reg_class_cover[i]]
- = curr_reg_pressure[ira_reg_class_cover[i]];
+ for (i = 0; i < ira_pressure_classes_num; i++)
+ saved_reg_pressure[ira_pressure_classes[i]]
+ = curr_reg_pressure[ira_pressure_classes[i]];
bitmap_copy (saved_reg_live, curr_reg_live);
}
{
int i;
- for (i = 0; i < ira_reg_class_cover_size; i++)
- curr_reg_pressure[ira_reg_class_cover[i]]
- = saved_reg_pressure[ira_reg_class_cover[i]];
+ for (i = 0; i < ira_pressure_classes_num; i++)
+ curr_reg_pressure[ira_pressure_classes[i]]
+ = saved_reg_pressure[ira_pressure_classes[i]];
bitmap_copy (curr_reg_live, saved_reg_live);
}
}
/* Print info about the current register pressure and its excess for
- each cover class. */
+ each pressure class. */
static void
print_curr_reg_pressure (void)
{
enum reg_class cl;
fprintf (sched_dump, ";;\t");
- for (i = 0; i < ira_reg_class_cover_size; i++)
+ for (i = 0; i < ira_pressure_classes_num; i++)
{
- cl = ira_reg_class_cover[i];
+ cl = ira_pressure_classes[i];
gcc_assert (curr_reg_pressure[cl] >= 0);
fprintf (sched_dump, " %s:%d(%d)", reg_class_names[cl],
curr_reg_pressure[cl],
}
fprintf (sched_dump, "\n");
}
+\f
+/* Determine if INSN has a condition that is clobbered if a register
+ in SET_REGS is modified. */
+static bool
+cond_clobbered_p (rtx insn, HARD_REG_SET set_regs)
+{
+ rtx pat = PATTERN (insn);
+ gcc_assert (GET_CODE (pat) == COND_EXEC);
+ if (TEST_HARD_REG_BIT (set_regs, REGNO (XEXP (COND_EXEC_TEST (pat), 0))))
+ {
+ sd_iterator_def sd_it;
+ dep_t dep;
+ haifa_change_pattern (insn, ORIG_PAT (insn));
+ FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
+ DEP_STATUS (dep) &= ~DEP_CANCELLED;
+ TODO_SPEC (insn) = HARD_DEP;
+ if (sched_verbose >= 2)
+ fprintf (sched_dump,
+ ";;\t\tdequeue insn %s because of clobbered condition\n",
+ (*current_sched_info->print_insn) (insn, 0));
+ return true;
+ }
+
+ return false;
+}
+
+/* Look at the remaining dependencies for insn NEXT, and compute and return
+ the TODO_SPEC value we should use for it. This is called after one of
+ NEXT's dependencies has been resolved. */
+
+static ds_t
+recompute_todo_spec (rtx next)
+{
+ ds_t new_ds;
+ sd_iterator_def sd_it;
+ dep_t dep, control_dep = NULL;
+ int n_spec = 0;
+ int n_control = 0;
+ bool first_p = true;
+
+ if (sd_lists_empty_p (next, SD_LIST_BACK))
+ /* NEXT has all its dependencies resolved. */
+ return 0;
+
+ if (!sd_lists_empty_p (next, SD_LIST_HARD_BACK))
+ return HARD_DEP;
+
+ /* Now we've got NEXT with speculative deps only.
+ 1. Look at the deps to see what we have to do.
+ 2. Check if we can do 'todo'. */
+ new_ds = 0;
+
+ FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep)
+ {
+ ds_t ds = DEP_STATUS (dep) & SPECULATIVE;
+
+ if (DEBUG_INSN_P (DEP_PRO (dep)) && !DEBUG_INSN_P (next))
+ continue;
+
+ if (ds)
+ {
+ n_spec++;
+ if (first_p)
+ {
+ first_p = false;
+
+ new_ds = ds;
+ }
+ else
+ new_ds = ds_merge (new_ds, ds);
+ }
+ if (DEP_TYPE (dep) == REG_DEP_CONTROL)
+ {
+ n_control++;
+ control_dep = dep;
+ DEP_STATUS (dep) &= ~DEP_CANCELLED;
+ }
+ }
+
+ if (n_control == 1 && n_spec == 0)
+ {
+ rtx pro, other, new_pat;
+ rtx cond = NULL_RTX;
+ bool success;
+ rtx prev = NULL_RTX;
+ int i;
+ unsigned regno;
+
+ if ((current_sched_info->flags & DO_PREDICATION) == 0
+ || (ORIG_PAT (next) != NULL_RTX
+ && PREDICATED_PAT (next) == NULL_RTX))
+ return HARD_DEP;
+
+ pro = DEP_PRO (control_dep);
+ other = real_insn_for_shadow (pro);
+ if (other != NULL_RTX)
+ pro = other;
+
+ cond = sched_get_reverse_condition_uncached (pro);
+ regno = REGNO (XEXP (cond, 0));
+
+ /* Find the last scheduled insn that modifies the condition register.
+ We can stop looking once we find the insn we depend on through the
+ REG_DEP_CONTROL; if the condition register isn't modified after it,
+ we know that it still has the right value. */
+ if (QUEUE_INDEX (pro) == QUEUE_SCHEDULED)
+ FOR_EACH_VEC_ELT_REVERSE (rtx, scheduled_insns, i, prev)
+ {
+ HARD_REG_SET t;
+
+ find_all_hard_reg_sets (prev, &t);
+ if (TEST_HARD_REG_BIT (t, regno))
+ return HARD_DEP;
+ if (prev == pro)
+ break;
+ }
+ if (ORIG_PAT (next) == NULL_RTX)
+ {
+ ORIG_PAT (next) = PATTERN (next);
+
+ new_pat = gen_rtx_COND_EXEC (VOIDmode, cond, PATTERN (next));
+ success = haifa_change_pattern (next, new_pat);
+ if (!success)
+ return HARD_DEP;
+ PREDICATED_PAT (next) = new_pat;
+ }
+ else if (PATTERN (next) != PREDICATED_PAT (next))
+ {
+ bool success = haifa_change_pattern (next,
+ PREDICATED_PAT (next));
+ gcc_assert (success);
+ }
+ DEP_STATUS (control_dep) |= DEP_CANCELLED;
+ return DEP_CONTROL;
+ }
-/* Pointer to the last instruction scheduled. Used by rank_for_schedule,
- so that insns independent of the last scheduled insn will be preferred
- over dependent instructions. */
+ if (PREDICATED_PAT (next) != NULL_RTX)
+ {
+ int tick = INSN_TICK (next);
+ bool success = haifa_change_pattern (next,
+ ORIG_PAT (next));
+ INSN_TICK (next) = tick;
+ gcc_assert (success);
+ }
+ /* We can't handle the case where there are both speculative and control
+ dependencies, so we return HARD_DEP in such a case. Also fail if
+ we have speculative dependencies with not enough points, or more than
+ one control dependency. */
+ if ((n_spec > 0 && n_control > 0)
+ || (n_spec > 0
+ /* Too few points? */
+ && ds_weak (new_ds) < spec_info->data_weakness_cutoff)
+ || (n_control > 1))
+ return HARD_DEP;
+
+ return new_ds;
+}
+\f
+/* Pointer to the last instruction scheduled. */
static rtx last_scheduled_insn;
+/* Pointer to the last nondebug instruction scheduled within the
+ block, or the prev_head of the scheduling block. Used by
+ rank_for_schedule, so that insns independent of the last scheduled
+ insn will be preferred over dependent instructions. */
+static rtx last_nondebug_scheduled_insn;
+
+/* Pointer that iterates through the list of unscheduled insns if we
+ have a dbg_cnt enabled. It always points at an insn prior to the
+ first unscheduled one. */
+static rtx nonscheduled_insns_begin;
+
/* Cached cost of the instruction. Use below function to get cost of the
insn. -1 here means that the field is not initialized. */
#define INSN_COST(INSN) (HID (INSN)->cost)
rtx used = DEP_CON (link);
int cost;
+ if (DEP_COST (link) != UNKNOWN_DEP_COST)
+ return DEP_COST (link);
+
+ if (delay_htab)
+ {
+ struct delay_pair *delay_entry;
+ delay_entry
+ = (struct delay_pair *)htab_find_with_hash (delay_htab_i2, used,
+ htab_hash_pointer (used));
+ if (delay_entry)
+ {
+ if (delay_entry->i1 == insn)
+ {
+ DEP_COST (link) = pair_delay (delay_entry);
+ return DEP_COST (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. We don't care about the
- the dependence cost when only decreasing register pressure. */
+ dependence cost when only decreasing register pressure. */
if (recog_memoized (used) < 0)
{
cost = 0;
cost = 0;
}
+ DEP_COST (link) = cost;
return cost;
}
return true;
}
-/* Compute the number of nondebug forward deps of an insn. */
+/* Compute the number of nondebug deps in list LIST for INSN. */
static int
-dep_list_size (rtx insn)
+dep_list_size (rtx insn, sd_list_types_def list)
{
sd_iterator_def sd_it;
dep_t dep;
int dbgcount = 0, nodbgcount = 0;
if (!MAY_HAVE_DEBUG_INSNS)
- return sd_lists_size (insn, SD_LIST_FORW);
+ return sd_lists_size (insn, list);
- FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
+ FOR_EACH_DEP (insn, list, sd_it, dep)
{
if (DEBUG_INSN_P (DEP_CON (dep)))
dbgcount++;
nodbgcount++;
}
- gcc_assert (dbgcount + nodbgcount == sd_lists_size (insn, SD_LIST_FORW));
+ gcc_assert (dbgcount + nodbgcount == sd_lists_size (insn, list));
return nodbgcount;
}
{
int this_priority = -1;
- if (dep_list_size (insn) == 0)
+ if (dep_list_size (insn, SD_LIST_FORW) == 0)
/* ??? We should set INSN_PRIORITY to insn_cost when and insn has
some forward deps but all of them are ignored by
contributes_to_priority hook. At the moment we set priority of
qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
while (0)
+/* For each pressure class CL, set DEATH[CL] to the number of registers
+ in that class that die in INSN. */
+
+static void
+calculate_reg_deaths (rtx insn, int *death)
+{
+ int i;
+ struct reg_use_data *use;
+
+ for (i = 0; i < ira_pressure_classes_num; i++)
+ death[ira_pressure_classes[i]] = 0;
+ for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
+ if (dying_use_p (use))
+ mark_regno_birth_or_death (0, death, use->regno, true);
+}
+
/* Setup info about the current register pressure impact of scheduling
INSN at the current scheduling point. */
static void
enum reg_class cl;
struct reg_pressure_data *pressure_info;
int *max_reg_pressure;
- struct reg_use_data *use;
static int death[N_REG_CLASSES];
gcc_checking_assert (!DEBUG_INSN_P (insn));
excess_cost_change = 0;
- for (i = 0; i < ira_reg_class_cover_size; i++)
- death[ira_reg_class_cover[i]] = 0;
- for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
- if (dying_use_p (use))
- {
- cl = sched_regno_cover_class[use->regno];
- if (use->regno < FIRST_PSEUDO_REGISTER)
- death[cl]++;
- else
- death[cl] += ira_reg_class_nregs[cl][PSEUDO_REGNO_MODE (use->regno)];
- }
+ calculate_reg_deaths (insn, death);
pressure_info = INSN_REG_PRESSURE (insn);
max_reg_pressure = INSN_MAX_REG_PRESSURE (insn);
gcc_assert (pressure_info != NULL && max_reg_pressure != NULL);
- for (i = 0; i < ira_reg_class_cover_size; i++)
+ for (i = 0; i < ira_pressure_classes_num; i++)
{
- cl = ira_reg_class_cover[i];
+ cl = ira_pressure_classes[i];
gcc_assert (curr_reg_pressure[cl] >= 0);
change = (int) pressure_info[i].set_increase - death[cl];
before = MAX (0, max_reg_pressure[i] - ira_available_class_regs[cl]);
}
INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insn) = excess_cost_change;
}
+\f
+/* This is the first page of code related to SCHED_PRESSURE_MODEL.
+ It tries to make the scheduler take register pressure into account
+ without introducing too many unnecessary stalls. It hooks into the
+ main scheduling algorithm at several points:
+
+ - Before scheduling starts, model_start_schedule constructs a
+ "model schedule" for the current block. This model schedule is
+ chosen solely to keep register pressure down. It does not take the
+ target's pipeline or the original instruction order into account,
+ except as a tie-breaker. It also doesn't work to a particular
+ pressure limit.
+
+ This model schedule gives us an idea of what pressure can be
+ achieved for the block and gives us an example of a schedule that
+ keeps to that pressure. It also makes the final schedule less
+ dependent on the original instruction order. This is important
+ because the original order can either be "wide" (many values live
+ at once, such as in user-scheduled code) or "narrow" (few values
+ live at once, such as after loop unrolling, where several
+ iterations are executed sequentially).
+
+ We do not apply this model schedule to the rtx stream. We simply
+ record it in model_schedule. We also compute the maximum pressure,
+ MP, that was seen during this schedule.
+
+ - Instructions are added to the ready queue even if they require
+ a stall. The length of the stall is instead computed as:
+
+ MAX (INSN_TICK (INSN) - clock_var, 0)
+
+ (= insn_delay). This allows rank_for_schedule to choose between
+ introducing a deliberate stall or increasing pressure.
+
+ - Before sorting the ready queue, model_set_excess_costs assigns
+ a pressure-based cost to each ready instruction in the queue.
+ This is the instruction's INSN_REG_PRESSURE_EXCESS_COST_CHANGE
+ (ECC for short) and is effectively measured in cycles.
+
+ - rank_for_schedule ranks instructions based on:
+
+ ECC (insn) + insn_delay (insn)
+
+ then as:
+
+ insn_delay (insn)
+
+ So, for example, an instruction X1 with an ECC of 1 that can issue
+ now will win over an instruction X0 with an ECC of zero that would
+ introduce a stall of one cycle. However, an instruction X2 with an
+ ECC of 2 that can issue now will lose to both X0 and X1.
+
+ - When an instruction is scheduled, model_recompute updates the model
+ schedule with the new pressures (some of which might now exceed the
+ original maximum pressure MP). model_update_limit_points then searches
+ for the new point of maximum pressure, if not already known. */
+
+/* Used to separate high-verbosity debug information for SCHED_PRESSURE_MODEL
+ from surrounding debug information. */
+#define MODEL_BAR \
+ ";;\t\t+------------------------------------------------------\n"
+
+/* Information about the pressure on a particular register class at a
+ particular point of the model schedule. */
+struct model_pressure_data {
+ /* The pressure at this point of the model schedule, or -1 if the
+ point is associated with an instruction that has already been
+ scheduled. */
+ int ref_pressure;
+
+ /* The maximum pressure during or after this point of the model schedule. */
+ int max_pressure;
+};
-/* Returns a positive value if x is preferred; returns a negative value if
- y is preferred. Should never return 0, since that will make the sort
- unstable. */
+/* Per-instruction information that is used while building the model
+ schedule. Here, "schedule" refers to the model schedule rather
+ than the main schedule. */
+struct model_insn_info {
+ /* The instruction itself. */
+ rtx insn;
-static int
-rank_for_schedule (const void *x, const void *y)
-{
- rtx tmp = *(const rtx *) y;
- rtx tmp2 = *(const rtx *) x;
- rtx last;
- int tmp_class, tmp2_class;
- int val, priority_val, info_val;
+ /* If this instruction is in model_worklist, these fields link to the
+ previous (higher-priority) and next (lower-priority) instructions
+ in the list. */
+ struct model_insn_info *prev;
+ struct model_insn_info *next;
+
+ /* While constructing the schedule, QUEUE_INDEX describes whether an
+ instruction has already been added to the schedule (QUEUE_SCHEDULED),
+ is in model_worklist (QUEUE_READY), or neither (QUEUE_NOWHERE).
+ old_queue records the value that QUEUE_INDEX had before scheduling
+ started, so that we can restore it once the schedule is complete. */
+ int old_queue;
+
+ /* The relative importance of an unscheduled instruction. Higher
+ values indicate greater importance. */
+ unsigned int model_priority;
+
+ /* The length of the longest path of satisfied true dependencies
+ that leads to this instruction. */
+ unsigned int depth;
+
+ /* The length of the longest path of dependencies of any kind
+ that leads from this instruction. */
+ unsigned int alap;
+
+ /* The number of predecessor nodes that must still be scheduled. */
+ int unscheduled_preds;
+};
- if (MAY_HAVE_DEBUG_INSNS)
- {
- /* Schedule debug insns as early as possible. */
- if (DEBUG_INSN_P (tmp) && !DEBUG_INSN_P (tmp2))
- return -1;
- else if (DEBUG_INSN_P (tmp2))
- return 1;
- }
+/* Information about the pressure limit for a particular register class.
+ This structure is used when applying a model schedule to the main
+ schedule. */
+struct model_pressure_limit {
+ /* The maximum register pressure seen in the original model schedule. */
+ int orig_pressure;
- /* The insn in a schedule group should be issued the first. */
- if (flag_sched_group_heuristic &&
- SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
- return SCHED_GROUP_P (tmp2) ? 1 : -1;
+ /* The maximum register pressure seen in the current model schedule
+ (which excludes instructions that have already been scheduled). */
+ int pressure;
- /* Make sure that priority of TMP and TMP2 are initialized. */
- gcc_assert (INSN_PRIORITY_KNOWN (tmp) && INSN_PRIORITY_KNOWN (tmp2));
+ /* The point of the current model schedule at which PRESSURE is first
+ reached. It is set to -1 if the value needs to be recomputed. */
+ int point;
+};
- if (sched_pressure_p)
- {
- int diff;
+/* Describes a particular way of measuring register pressure. */
+struct model_pressure_group {
+ /* Index PCI describes the maximum pressure on ira_pressure_classes[PCI]. */
+ struct model_pressure_limit limits[N_REG_CLASSES];
- /* Prefer insn whose scheduling results in the smallest register
- pressure excess. */
- if ((diff = (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp)
- + (INSN_TICK (tmp) > clock_var
- ? INSN_TICK (tmp) - clock_var : 0)
- - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2)
- - (INSN_TICK (tmp2) > clock_var
- ? INSN_TICK (tmp2) - clock_var : 0))) != 0)
- return diff;
- }
+ /* Index (POINT * ira_num_pressure_classes + PCI) describes the pressure
+ on register class ira_pressure_classes[PCI] at point POINT of the
+ current model schedule. A POINT of model_num_insns describes the
+ pressure at the end of the schedule. */
+ struct model_pressure_data *model;
+};
+/* Index POINT gives the instruction at point POINT of the model schedule.
+ This array doesn't change during main scheduling. */
+static VEC (rtx, heap) *model_schedule;
- if (sched_pressure_p
- && (INSN_TICK (tmp2) > clock_var || INSN_TICK (tmp) > clock_var))
- {
- if (INSN_TICK (tmp) <= clock_var)
- return -1;
- else if (INSN_TICK (tmp2) <= clock_var)
- return 1;
- else
- return INSN_TICK (tmp) - INSN_TICK (tmp2);
- }
- /* Prefer insn with higher priority. */
- priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
+/* The list of instructions in the model worklist, sorted in order of
+ decreasing priority. */
+static struct model_insn_info *model_worklist;
- if (flag_sched_critical_path_heuristic && priority_val)
- return priority_val;
+/* Index I describes the instruction with INSN_LUID I. */
+static struct model_insn_info *model_insns;
- /* Prefer speculative insn with greater dependencies weakness. */
- if (flag_sched_spec_insn_heuristic && spec_info)
- {
- ds_t ds1, ds2;
- dw_t dw1, dw2;
- int dw;
+/* The number of instructions in the model schedule. */
+static int model_num_insns;
- ds1 = TODO_SPEC (tmp) & SPECULATIVE;
- if (ds1)
- dw1 = ds_weak (ds1);
- else
- dw1 = NO_DEP_WEAK;
-
- ds2 = TODO_SPEC (tmp2) & SPECULATIVE;
- if (ds2)
- dw2 = ds_weak (ds2);
- else
- dw2 = NO_DEP_WEAK;
-
- dw = dw2 - dw1;
- if (dw > (NO_DEP_WEAK / 8) || dw < -(NO_DEP_WEAK / 8))
- return dw;
- }
-
- info_val = (*current_sched_info->rank) (tmp, tmp2);
- if(flag_sched_rank_heuristic && info_val)
- return info_val;
-
- if (flag_sched_last_insn_heuristic)
- {
- last = last_scheduled_insn;
+/* The index of the first instruction in model_schedule that hasn't yet been
+ added to the main schedule, or model_num_insns if all of them have. */
+static int model_curr_point;
- if (DEBUG_INSN_P (last) && last != current_sched_info->prev_head)
- do
- last = PREV_INSN (last);
- while (!NONDEBUG_INSN_P (last)
- && last != current_sched_info->prev_head);
- }
+/* Describes the pressure before each instruction in the model schedule. */
+static struct model_pressure_group model_before_pressure;
- /* Compare insns based on their relation to the last scheduled
- non-debug insn. */
- if (flag_sched_last_insn_heuristic && NONDEBUG_INSN_P (last))
- {
- dep_t dep1;
- dep_t dep2;
+/* The first unused model_priority value (as used in model_insn_info). */
+static unsigned int model_next_priority;
- /* Classify the instructions into three classes:
- 1) Data dependent on last schedule insn.
- 2) Anti/Output dependent on last scheduled insn.
- 3) Independent of last scheduled insn, or has latency of one.
- Choose the insn from the highest numbered class if different. */
- dep1 = sd_find_dep_between (last, tmp, true);
- if (dep1 == NULL || dep_cost (dep1) == 1)
- tmp_class = 3;
- else if (/* Data dependence. */
- DEP_TYPE (dep1) == REG_DEP_TRUE)
- tmp_class = 1;
- else
- tmp_class = 2;
+/* The model_pressure_data for ira_pressure_classes[PCI] in GROUP
+ at point POINT of the model schedule. */
+#define MODEL_PRESSURE_DATA(GROUP, POINT, PCI) \
+ (&(GROUP)->model[(POINT) * ira_pressure_classes_num + (PCI)])
- dep2 = sd_find_dep_between (last, tmp2, true);
+/* The maximum pressure on ira_pressure_classes[PCI] in GROUP at or
+ after point POINT of the model schedule. */
+#define MODEL_MAX_PRESSURE(GROUP, POINT, PCI) \
+ (MODEL_PRESSURE_DATA (GROUP, POINT, PCI)->max_pressure)
- if (dep2 == NULL || dep_cost (dep2) == 1)
- tmp2_class = 3;
- else if (/* Data dependence. */
- DEP_TYPE (dep2) == REG_DEP_TRUE)
- tmp2_class = 1;
- else
- tmp2_class = 2;
+/* The pressure on ira_pressure_classes[PCI] in GROUP at point POINT
+ of the model schedule. */
+#define MODEL_REF_PRESSURE(GROUP, POINT, PCI) \
+ (MODEL_PRESSURE_DATA (GROUP, POINT, PCI)->ref_pressure)
- if ((val = tmp2_class - tmp_class))
- return val;
- }
+/* Information about INSN that is used when creating the model schedule. */
+#define MODEL_INSN_INFO(INSN) \
+ (&model_insns[INSN_LUID (INSN)])
- /* Prefer the insn which has more later insns that depend on it.
- This gives the scheduler more freedom when scheduling later
- instructions at the expense of added register pressure. */
+/* The instruction at point POINT of the model schedule. */
+#define MODEL_INSN(POINT) \
+ (VEC_index (rtx, model_schedule, POINT))
- val = (dep_list_size (tmp2) - dep_list_size (tmp));
- if (flag_sched_dep_count_heuristic && val != 0)
- return val;
+/* Return INSN's index in the model schedule, or model_num_insns if it
+ doesn't belong to that schedule. */
- /* If insns are equally good, sort by INSN_LUID (original insn order),
- so that we make the sort stable. This minimizes instruction movement,
- thus minimizing sched's effect on debugging and cross-jumping. */
- return INSN_LUID (tmp) - INSN_LUID (tmp2);
+static int
+model_index (rtx insn)
+{
+ if (INSN_MODEL_INDEX (insn) == 0)
+ return model_num_insns;
+ return INSN_MODEL_INDEX (insn) - 1;
}
-/* Resort the array A in which only element at index N may be out of order. */
+/* Make sure that GROUP->limits is up-to-date for the current point
+ of the model schedule. */
-HAIFA_INLINE static void
-swap_sort (rtx *a, int n)
+static void
+model_update_limit_points_in_group (struct model_pressure_group *group)
{
- rtx insn = a[n - 1];
- int i = n - 2;
+ int pci, max_pressure, point;
- while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
+ for (pci = 0; pci < ira_pressure_classes_num; pci++)
{
- a[i + 1] = a[i];
- i -= 1;
+ /* We may have passed the final point at which the pressure in
+ group->limits[pci].pressure was reached. Update the limit if so. */
+ max_pressure = MODEL_MAX_PRESSURE (group, model_curr_point, pci);
+ group->limits[pci].pressure = max_pressure;
+
+ /* Find the point at which MAX_PRESSURE is first reached. We need
+ to search in three cases:
+
+ - We've already moved past the previous pressure point.
+ In this case we search forward from model_curr_point.
+
+ - We scheduled the previous point of maximum pressure ahead of
+ its position in the model schedule, but doing so didn't bring
+ the pressure point earlier. In this case we search forward
+ from that previous pressure point.
+
+ - Scheduling an instruction early caused the maximum pressure
+ to decrease. In this case we will have set the pressure
+ point to -1, and we search forward from model_curr_point. */
+ point = MAX (group->limits[pci].point, model_curr_point);
+ while (point < model_num_insns
+ && MODEL_REF_PRESSURE (group, point, pci) < max_pressure)
+ point++;
+ group->limits[pci].point = point;
+
+ gcc_assert (MODEL_REF_PRESSURE (group, point, pci) == max_pressure);
+ gcc_assert (MODEL_MAX_PRESSURE (group, point, pci) == max_pressure);
}
- a[i + 1] = insn;
}
-/* Add INSN to the insn queue so that it can be executed at least
- N_CYCLES after the currently executing insn. Preserve insns
- chain for debugging purposes. */
+/* Make sure that all register-pressure limits are up-to-date for the
+ current position in the model schedule. */
-HAIFA_INLINE static void
-queue_insn (rtx insn, int n_cycles)
+static void
+model_update_limit_points (void)
{
- int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
- rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
-
- gcc_assert (n_cycles <= max_insn_queue_index);
- gcc_assert (!DEBUG_INSN_P (insn));
-
- insn_queue[next_q] = link;
- q_size += 1;
+ model_update_limit_points_in_group (&model_before_pressure);
+}
- if (sched_verbose >= 2)
- {
- fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ",
- (*current_sched_info->print_insn) (insn, 0));
+/* Return the model_index of the last unscheduled use in chain USE
+ outside of USE's instruction. Return -1 if there are no other uses,
+ or model_num_insns if the register is live at the end of the block. */
- fprintf (sched_dump, "queued for %d cycles.\n", n_cycles);
- }
+static int
+model_last_use_except (struct reg_use_data *use)
+{
+ struct reg_use_data *next;
+ int last, index;
- QUEUE_INDEX (insn) = next_q;
+ last = -1;
+ for (next = use->next_regno_use; next != use; next = next->next_regno_use)
+ if (NONDEBUG_INSN_P (next->insn)
+ && QUEUE_INDEX (next->insn) != QUEUE_SCHEDULED)
+ {
+ index = model_index (next->insn);
+ if (index == model_num_insns)
+ return model_num_insns;
+ if (last < index)
+ last = index;
+ }
+ return last;
}
-/* Remove INSN from queue. */
+/* An instruction with model_index POINT has just been scheduled, and it
+ adds DELTA to the pressure on ira_pressure_classes[PCI] after POINT - 1.
+ Update MODEL_REF_PRESSURE (GROUP, POINT, PCI) and
+ MODEL_MAX_PRESSURE (GROUP, POINT, PCI) accordingly. */
+
static void
-queue_remove (rtx insn)
+model_start_update_pressure (struct model_pressure_group *group,
+ int point, int pci, int delta)
{
- gcc_assert (QUEUE_INDEX (insn) >= 0);
- remove_free_INSN_LIST_elem (insn, &insn_queue[QUEUE_INDEX (insn)]);
- q_size--;
- QUEUE_INDEX (insn) = QUEUE_NOWHERE;
+ int next_max_pressure;
+
+ if (point == model_num_insns)
+ {
+ /* The instruction wasn't part of the model schedule; it was moved
+ from a different block. Update the pressure for the end of
+ the model schedule. */
+ MODEL_REF_PRESSURE (group, point, pci) += delta;
+ MODEL_MAX_PRESSURE (group, point, pci) += delta;
+ }
+ else
+ {
+ /* Record that this instruction has been scheduled. Nothing now
+ changes between POINT and POINT + 1, so get the maximum pressure
+ from the latter. If the maximum pressure decreases, the new
+ pressure point may be before POINT. */
+ MODEL_REF_PRESSURE (group, point, pci) = -1;
+ next_max_pressure = MODEL_MAX_PRESSURE (group, point + 1, pci);
+ if (MODEL_MAX_PRESSURE (group, point, pci) > next_max_pressure)
+ {
+ MODEL_MAX_PRESSURE (group, point, pci) = next_max_pressure;
+ if (group->limits[pci].point == point)
+ group->limits[pci].point = -1;
+ }
+ }
}
-/* Return a pointer to the bottom of the ready list, i.e. the insn
- with the lowest priority. */
+/* Record that scheduling a later instruction has changed the pressure
+ at point POINT of the model schedule by DELTA (which might be 0).
+ Update GROUP accordingly. Return nonzero if these changes might
+ trigger changes to previous points as well. */
-rtx *
-ready_lastpos (struct ready_list *ready)
+static int
+model_update_pressure (struct model_pressure_group *group,
+ int point, int pci, int delta)
{
- gcc_assert (ready->n_ready >= 1);
- return ready->vec + ready->first - ready->n_ready + 1;
+ int ref_pressure, max_pressure, next_max_pressure;
+
+ /* If POINT hasn't yet been scheduled, update its pressure. */
+ ref_pressure = MODEL_REF_PRESSURE (group, point, pci);
+ if (ref_pressure >= 0 && delta != 0)
+ {
+ ref_pressure += delta;
+ MODEL_REF_PRESSURE (group, point, pci) = ref_pressure;
+
+ /* Check whether the maximum pressure in the overall schedule
+ has increased. (This means that the MODEL_MAX_PRESSURE of
+ every point <= POINT will need to increae too; see below.) */
+ if (group->limits[pci].pressure < ref_pressure)
+ group->limits[pci].pressure = ref_pressure;
+
+ /* If we are at maximum pressure, and the maximum pressure
+ point was previously unknown or later than POINT,
+ bring it forward. */
+ if (group->limits[pci].pressure == ref_pressure
+ && !IN_RANGE (group->limits[pci].point, 0, point))
+ group->limits[pci].point = point;
+
+ /* If POINT used to be the point of maximum pressure, but isn't
+ any longer, we need to recalculate it using a forward walk. */
+ if (group->limits[pci].pressure > ref_pressure
+ && group->limits[pci].point == point)
+ group->limits[pci].point = -1;
+ }
+
+ /* Update the maximum pressure at POINT. Changes here might also
+ affect the maximum pressure at POINT - 1. */
+ next_max_pressure = MODEL_MAX_PRESSURE (group, point + 1, pci);
+ max_pressure = MAX (ref_pressure, next_max_pressure);
+ if (MODEL_MAX_PRESSURE (group, point, pci) != max_pressure)
+ {
+ MODEL_MAX_PRESSURE (group, point, pci) = max_pressure;
+ return 1;
+ }
+ return 0;
}
-/* Add an element INSN to the ready list so that it ends up with the
- lowest/highest priority depending on FIRST_P. */
+/* INSN has just been scheduled. Update the model schedule accordingly. */
-HAIFA_INLINE static void
-ready_add (struct ready_list *ready, rtx insn, bool first_p)
+static void
+model_recompute (rtx insn)
{
- if (!first_p)
+ struct {
+ int last_use;
+ int regno;
+ } uses[FIRST_PSEUDO_REGISTER + MAX_RECOG_OPERANDS];
+ struct reg_use_data *use;
+ struct reg_pressure_data *reg_pressure;
+ int delta[N_REG_CLASSES];
+ int pci, point, mix, new_last, cl, ref_pressure, queue;
+ unsigned int i, num_uses, num_pending_births;
+ bool print_p;
+
+ /* The destinations of INSN were previously live from POINT onwards, but are
+ now live from model_curr_point onwards. Set up DELTA accordingly. */
+ point = model_index (insn);
+ reg_pressure = INSN_REG_PRESSURE (insn);
+ for (pci = 0; pci < ira_pressure_classes_num; pci++)
{
- if (ready->first == ready->n_ready)
- {
- memmove (ready->vec + ready->veclen - ready->n_ready,
- ready_lastpos (ready),
- ready->n_ready * sizeof (rtx));
- ready->first = ready->veclen - 1;
- }
- ready->vec[ready->first - ready->n_ready] = insn;
+ cl = ira_pressure_classes[pci];
+ delta[cl] = reg_pressure[pci].set_increase;
}
- else
+
+ /* Record which registers previously died at POINT, but which now die
+ before POINT. Adjust DELTA so that it represents the effect of
+ this change after POINT - 1. Set NUM_PENDING_BIRTHS to the number of
+ registers that will be born in the range [model_curr_point, POINT). */
+ num_uses = 0;
+ num_pending_births = 0;
+ for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
{
- if (ready->first == ready->veclen - 1)
+ new_last = model_last_use_except (use);
+ if (new_last < point)
{
- if (ready->n_ready)
- /* ready_lastpos() fails when called with (ready->n_ready == 0). */
- memmove (ready->vec + ready->veclen - ready->n_ready - 1,
- ready_lastpos (ready),
- ready->n_ready * sizeof (rtx));
- ready->first = ready->veclen - 2;
+ gcc_assert (num_uses < ARRAY_SIZE (uses));
+ uses[num_uses].last_use = new_last;
+ uses[num_uses].regno = use->regno;
+ /* This register is no longer live after POINT - 1. */
+ mark_regno_birth_or_death (NULL, delta, use->regno, false);
+ num_uses++;
+ if (new_last >= 0)
+ num_pending_births++;
}
- ready->vec[++(ready->first)] = insn;
}
- ready->n_ready++;
- if (DEBUG_INSN_P (insn))
- ready->n_debug++;
-
- gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY);
- QUEUE_INDEX (insn) = QUEUE_READY;
-}
+ /* Update the MODEL_REF_PRESSURE and MODEL_MAX_PRESSURE for POINT.
+ Also set each group pressure limit for POINT. */
+ for (pci = 0; pci < ira_pressure_classes_num; pci++)
+ {
+ cl = ira_pressure_classes[pci];
+ model_start_update_pressure (&model_before_pressure,
+ point, pci, delta[cl]);
+ }
-/* Remove the element with the highest priority from the ready list and
- return it. */
+ /* Walk the model schedule backwards, starting immediately before POINT. */
+ print_p = false;
+ if (point != model_curr_point)
+ do
+ {
+ point--;
+ insn = MODEL_INSN (point);
+ queue = QUEUE_INDEX (insn);
-HAIFA_INLINE static rtx
-ready_remove_first (struct ready_list *ready)
-{
- rtx t;
+ if (queue != QUEUE_SCHEDULED)
+ {
+ /* DELTA describes the effect of the move on the register pressure
+ after POINT. Make it describe the effect on the pressure
+ before POINT. */
+ i = 0;
+ while (i < num_uses)
+ {
+ if (uses[i].last_use == point)
+ {
+ /* This register is now live again. */
+ mark_regno_birth_or_death (NULL, delta,
+ uses[i].regno, true);
+
+ /* Remove this use from the array. */
+ uses[i] = uses[num_uses - 1];
+ num_uses--;
+ num_pending_births--;
+ }
+ else
+ i++;
+ }
- gcc_assert (ready->n_ready);
- t = ready->vec[ready->first--];
- ready->n_ready--;
- if (DEBUG_INSN_P (t))
- ready->n_debug--;
- /* If the queue becomes empty, reset it. */
- if (ready->n_ready == 0)
- ready->first = ready->veclen - 1;
+ if (sched_verbose >= 5)
+ {
+ char buf[2048];
+
+ if (!print_p)
+ {
+ fprintf (sched_dump, MODEL_BAR);
+ fprintf (sched_dump, ";;\t\t| New pressure for model"
+ " schedule\n");
+ fprintf (sched_dump, MODEL_BAR);
+ print_p = true;
+ }
+
+ print_pattern (buf, PATTERN (insn), 0);
+ fprintf (sched_dump, ";;\t\t| %3d %4d %-30s ",
+ point, INSN_UID (insn), buf);
+ for (pci = 0; pci < ira_pressure_classes_num; pci++)
+ {
+ cl = ira_pressure_classes[pci];
+ ref_pressure = MODEL_REF_PRESSURE (&model_before_pressure,
+ point, pci);
+ fprintf (sched_dump, " %s:[%d->%d]",
+ reg_class_names[ira_pressure_classes[pci]],
+ ref_pressure, ref_pressure + delta[cl]);
+ }
+ fprintf (sched_dump, "\n");
+ }
+ }
- gcc_assert (QUEUE_INDEX (t) == QUEUE_READY);
- QUEUE_INDEX (t) = QUEUE_NOWHERE;
+ /* Adjust the pressure at POINT. Set MIX to nonzero if POINT - 1
+ might have changed as well. */
+ mix = num_pending_births;
+ for (pci = 0; pci < ira_pressure_classes_num; pci++)
+ {
+ cl = ira_pressure_classes[pci];
+ mix |= delta[cl];
+ mix |= model_update_pressure (&model_before_pressure,
+ point, pci, delta[cl]);
+ }
+ }
+ while (mix && point > model_curr_point);
- return t;
+ if (print_p)
+ fprintf (sched_dump, MODEL_BAR);
}
+\f
+/* model_spill_cost (CL, P, P') returns the cost of increasing the
+ pressure on CL from P to P'. We use this to calculate a "base ECC",
+ baseECC (CL, X), for each pressure class CL and each instruction X.
+ Supposing X changes the pressure on CL from P to P', and that the
+ maximum pressure on CL in the current model schedule is MP', then:
-/* 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. */
+ * if X occurs before or at the next point of maximum pressure in
+ the model schedule and P' > MP', then:
+
+ baseECC (CL, X) = model_spill_cost (CL, MP, P')
-/* 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. */
+ The idea is that the pressure after scheduling a fixed set of
+ instructions -- in this case, the set up to and including the
+ next maximum pressure point -- is going to be the same regardless
+ of the order; we simply want to keep the intermediate pressure
+ under control. Thus X has a cost of zero unless scheduling it
+ now would exceed MP'.
-rtx
-ready_element (struct ready_list *ready, int index)
-{
- gcc_assert (ready->n_ready && index < ready->n_ready);
+ If all increases in the set are by the same amount, no zero-cost
+ instruction will ever cause the pressure to exceed MP'. However,
+ if X is instead moved past an instruction X' with pressure in the
+ range (MP' - (P' - P), MP'), the pressure at X' will increase
+ beyond MP'. Since baseECC is very much a heuristic anyway,
+ it doesn't seem worth the overhead of tracking cases like these.
- return ready->vec[ready->first - index];
-}
+ The cost of exceeding MP' is always based on the original maximum
+ pressure MP. This is so that going 2 registers over the original
+ limit has the same cost regardless of whether it comes from two
+ separate +1 deltas or from a single +2 delta.
-/* 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. */
+ * if X occurs after the next point of maximum pressure in the model
+ schedule and P' > P, then:
-HAIFA_INLINE static rtx
-ready_remove (struct ready_list *ready, int index)
-{
- rtx t;
- int i;
+ baseECC (CL, X) = model_spill_cost (CL, MP, MP' + (P' - P))
- 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--;
- if (DEBUG_INSN_P (t))
- ready->n_debug--;
- for (i = index; i < ready->n_ready; i++)
- ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
- QUEUE_INDEX (t) = QUEUE_NOWHERE;
- return t;
-}
+ That is, if we move X forward across a point of maximum pressure,
+ and if X increases the pressure by P' - P, then we conservatively
+ assume that scheduling X next would increase the maximum pressure
+ by P' - P. Again, the cost of doing this is based on the original
+ maximum pressure MP, for the same reason as above.
-/* Remove INSN from the ready list. */
-static void
-ready_remove_insn (rtx insn)
-{
- int i;
+ * if P' < P, P > MP, and X occurs at or after the next point of
+ maximum pressure, then:
- for (i = 0; i < readyp->n_ready; i++)
- if (ready_element (readyp, i) == insn)
- {
- ready_remove (readyp, i);
- return;
- }
- gcc_unreachable ();
-}
+ baseECC (CL, X) = -model_spill_cost (CL, MAX (MP, P'), P)
-/* Sort the ready list READY by ascending priority, using the SCHED_SORT
- macro. */
+ That is, if we have already exceeded the original maximum pressure MP,
+ and if X might reduce the maximum pressure again -- or at least push
+ it further back, and thus allow more scheduling freedom -- it is given
+ a negative cost to reflect the improvement.
-void
-ready_sort (struct ready_list *ready)
-{
- int i;
- rtx *first = ready_lastpos (ready);
+ * otherwise,
- if (sched_pressure_p)
- {
- for (i = 0; i < ready->n_ready; i++)
- if (!DEBUG_INSN_P (first[i]))
- setup_insn_reg_pressure_info (first[i]);
- }
- SCHED_SORT (first, ready->n_ready);
-}
+ baseECC (CL, X) = 0
-/* PREV is an insn that is ready to execute. Adjust its priority if that
- will help shorten or lengthen register lifetimes as appropriate. Also
- provide a hook for the target to tweak itself. */
+ In this case, X is not expected to affect the maximum pressure MP',
+ so it has zero cost.
-HAIFA_INLINE static void
-adjust_priority (rtx prev)
+ We then create a combined value baseECC (X) that is the sum of
+ baseECC (CL, X) for each pressure class CL.
+
+ baseECC (X) could itself be used as the ECC value described above.
+ However, this is often too conservative, in the sense that it
+ tends to make high-priority instructions that increase pressure
+ wait too long in cases where introducing a spill would be better.
+ For this reason the final ECC is a priority-adjusted form of
+ baseECC (X). Specifically, we calculate:
+
+ P (X) = INSN_PRIORITY (X) - insn_delay (X) - baseECC (X)
+ baseP = MAX { P (X) | baseECC (X) <= 0 }
+
+ Then:
+
+ ECC (X) = MAX (MIN (baseP - P (X), baseECC (X)), 0)
+
+ Thus an instruction's effect on pressure is ignored if it has a high
+ enough priority relative to the ones that don't increase pressure.
+ Negative values of baseECC (X) do not increase the priority of X
+ itself, but they do make it harder for other instructions to
+ increase the pressure further.
+
+ This pressure cost is deliberately timid. The intention has been
+ to choose a heuristic that rarely interferes with the normal list
+ scheduler in cases where that scheduler would produce good code.
+ We simply want to curb some of its worst excesses. */
+
+/* Return the cost of increasing the pressure in class CL from FROM to TO.
+
+ Here we use the very simplistic cost model that every register above
+ ira_available_class_regs[CL] has a spill cost of 1. We could use other
+ measures instead, such as one based on MEMORY_MOVE_COST. However:
+
+ (1) In order for an instruction to be scheduled, the higher cost
+ would need to be justified in a single saving of that many stalls.
+ This is overly pessimistic, because the benefit of spilling is
+ often to avoid a sequence of several short stalls rather than
+ a single long one.
+
+ (2) The cost is still arbitrary. Because we are not allocating
+ registers during scheduling, we have no way of knowing for
+ sure how many memory accesses will be required by each spill,
+ where the spills will be placed within the block, or even
+ which block(s) will contain the spills.
+
+ So a higher cost than 1 is often too conservative in practice,
+ forcing blocks to contain unnecessary stalls instead of spill code.
+ The simple cost below seems to be the best compromise. It reduces
+ the interference with the normal list scheduler, which helps make
+ it more suitable for a default-on option. */
+
+static int
+model_spill_cost (int cl, int from, int to)
+{
+ from = MAX (from, ira_available_class_regs[cl]);
+ return MAX (to, from) - from;
+}
+
+/* Return baseECC (ira_pressure_classes[PCI], POINT), given that
+ P = curr_reg_pressure[ira_pressure_classes[PCI]] and that
+ P' = P + DELTA. */
+
+static int
+model_excess_group_cost (struct model_pressure_group *group,
+ int point, int pci, int delta)
+{
+ int pressure, cl;
+
+ cl = ira_pressure_classes[pci];
+ if (delta < 0 && point >= group->limits[pci].point)
+ {
+ pressure = MAX (group->limits[pci].orig_pressure,
+ curr_reg_pressure[cl] + delta);
+ return -model_spill_cost (cl, pressure, curr_reg_pressure[cl]);
+ }
+
+ if (delta > 0)
+ {
+ if (point > group->limits[pci].point)
+ pressure = group->limits[pci].pressure + delta;
+ else
+ pressure = curr_reg_pressure[cl] + delta;
+
+ if (pressure > group->limits[pci].pressure)
+ return model_spill_cost (cl, group->limits[pci].orig_pressure,
+ pressure);
+ }
+
+ return 0;
+}
+
+/* Return baseECC (MODEL_INSN (INSN)). Dump the costs to sched_dump
+ if PRINT_P. */
+
+static int
+model_excess_cost (rtx insn, bool print_p)
+{
+ int point, pci, cl, cost, this_cost, delta;
+ struct reg_pressure_data *insn_reg_pressure;
+ int insn_death[N_REG_CLASSES];
+
+ calculate_reg_deaths (insn, insn_death);
+ point = model_index (insn);
+ insn_reg_pressure = INSN_REG_PRESSURE (insn);
+ cost = 0;
+
+ if (print_p)
+ fprintf (sched_dump, ";;\t\t| %3d %4d | %4d %+3d |", point,
+ INSN_UID (insn), INSN_PRIORITY (insn), insn_delay (insn));
+
+ /* Sum up the individual costs for each register class. */
+ for (pci = 0; pci < ira_pressure_classes_num; pci++)
+ {
+ cl = ira_pressure_classes[pci];
+ delta = insn_reg_pressure[pci].set_increase - insn_death[cl];
+ this_cost = model_excess_group_cost (&model_before_pressure,
+ point, pci, delta);
+ cost += this_cost;
+ if (print_p)
+ fprintf (sched_dump, " %s:[%d base cost %d]",
+ reg_class_names[cl], delta, this_cost);
+ }
+
+ if (print_p)
+ fprintf (sched_dump, "\n");
+
+ return cost;
+}
+
+/* Dump the next points of maximum pressure for GROUP. */
+
+static void
+model_dump_pressure_points (struct model_pressure_group *group)
+{
+ int pci, cl;
+
+ fprintf (sched_dump, ";;\t\t| pressure points");
+ for (pci = 0; pci < ira_pressure_classes_num; pci++)
+ {
+ cl = ira_pressure_classes[pci];
+ fprintf (sched_dump, " %s:[%d->%d at ", reg_class_names[cl],
+ curr_reg_pressure[cl], group->limits[pci].pressure);
+ if (group->limits[pci].point < model_num_insns)
+ fprintf (sched_dump, "%d:%d]", group->limits[pci].point,
+ INSN_UID (MODEL_INSN (group->limits[pci].point)));
+ else
+ fprintf (sched_dump, "end]");
+ }
+ fprintf (sched_dump, "\n");
+}
+
+/* Set INSN_REG_PRESSURE_EXCESS_COST_CHANGE for INSNS[0...COUNT-1]. */
+
+static void
+model_set_excess_costs (rtx *insns, int count)
+{
+ int i, cost, priority_base, priority;
+ bool print_p;
+
+ /* Record the baseECC value for each instruction in the model schedule,
+ except that negative costs are converted to zero ones now rather thatn
+ later. Do not assign a cost to debug instructions, since they must
+ not change code-generation decisions. Experiments suggest we also
+ get better results by not assigning a cost to instructions from
+ a different block.
+
+ Set PRIORITY_BASE to baseP in the block comment above. This is the
+ maximum priority of the "cheap" instructions, which should always
+ include the next model instruction. */
+ priority_base = 0;
+ print_p = false;
+ for (i = 0; i < count; i++)
+ if (INSN_MODEL_INDEX (insns[i]))
+ {
+ if (sched_verbose >= 6 && !print_p)
+ {
+ fprintf (sched_dump, MODEL_BAR);
+ fprintf (sched_dump, ";;\t\t| Pressure costs for ready queue\n");
+ model_dump_pressure_points (&model_before_pressure);
+ fprintf (sched_dump, MODEL_BAR);
+ print_p = true;
+ }
+ cost = model_excess_cost (insns[i], print_p);
+ if (cost <= 0)
+ {
+ priority = INSN_PRIORITY (insns[i]) - insn_delay (insns[i]) - cost;
+ priority_base = MAX (priority_base, priority);
+ cost = 0;
+ }
+ INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns[i]) = cost;
+ }
+ if (print_p)
+ fprintf (sched_dump, MODEL_BAR);
+
+ /* Use MAX (baseECC, 0) and baseP to calculcate ECC for each
+ instruction. */
+ for (i = 0; i < count; i++)
+ {
+ cost = INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns[i]);
+ priority = INSN_PRIORITY (insns[i]) - insn_delay (insns[i]);
+ if (cost > 0 && priority > priority_base)
+ {
+ cost += priority_base - priority;
+ INSN_REG_PRESSURE_EXCESS_COST_CHANGE (insns[i]) = MAX (cost, 0);
+ }
+ }
+}
+\f
+/* Returns a positive value if x is preferred; returns a negative value if
+ y is preferred. Should never return 0, since that will make the sort
+ unstable. */
+
+static int
+rank_for_schedule (const void *x, const void *y)
+{
+ rtx tmp = *(const rtx *) y;
+ rtx tmp2 = *(const rtx *) x;
+ int tmp_class, tmp2_class;
+ int val, priority_val, info_val;
+
+ if (MAY_HAVE_DEBUG_INSNS)
+ {
+ /* Schedule debug insns as early as possible. */
+ if (DEBUG_INSN_P (tmp) && !DEBUG_INSN_P (tmp2))
+ return -1;
+ else if (!DEBUG_INSN_P (tmp) && DEBUG_INSN_P (tmp2))
+ return 1;
+ else if (DEBUG_INSN_P (tmp) && DEBUG_INSN_P (tmp2))
+ return INSN_LUID (tmp) - INSN_LUID (tmp2);
+ }
+
+ /* The insn in a schedule group should be issued the first. */
+ if (flag_sched_group_heuristic &&
+ SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
+ return SCHED_GROUP_P (tmp2) ? 1 : -1;
+
+ /* Make sure that priority of TMP and TMP2 are initialized. */
+ gcc_assert (INSN_PRIORITY_KNOWN (tmp) && INSN_PRIORITY_KNOWN (tmp2));
+
+ if (sched_pressure != SCHED_PRESSURE_NONE)
+ {
+ int diff;
+
+ /* Prefer insn whose scheduling results in the smallest register
+ pressure excess. */
+ if ((diff = (INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp)
+ + insn_delay (tmp)
+ - INSN_REG_PRESSURE_EXCESS_COST_CHANGE (tmp2)
+ - insn_delay (tmp2))))
+ return diff;
+ }
+
+ if (sched_pressure != SCHED_PRESSURE_NONE
+ && (INSN_TICK (tmp2) > clock_var || INSN_TICK (tmp) > clock_var))
+ {
+ if (INSN_TICK (tmp) <= clock_var)
+ return -1;
+ else if (INSN_TICK (tmp2) <= clock_var)
+ return 1;
+ else
+ return INSN_TICK (tmp) - INSN_TICK (tmp2);
+ }
+
+ /* If we are doing backtracking in this schedule, prefer insns that
+ have forward dependencies with negative cost against an insn that
+ was already scheduled. */
+ if (current_sched_info->flags & DO_BACKTRACKING)
+ {
+ priority_val = FEEDS_BACKTRACK_INSN (tmp2) - FEEDS_BACKTRACK_INSN (tmp);
+ if (priority_val)
+ return priority_val;
+ }
+
+ /* Prefer insn with higher priority. */
+ priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
+
+ if (flag_sched_critical_path_heuristic && priority_val)
+ return priority_val;
+
+ /* Prefer speculative insn with greater dependencies weakness. */
+ if (flag_sched_spec_insn_heuristic && spec_info)
+ {
+ ds_t ds1, ds2;
+ dw_t dw1, dw2;
+ int dw;
+
+ ds1 = TODO_SPEC (tmp) & SPECULATIVE;
+ if (ds1)
+ dw1 = ds_weak (ds1);
+ else
+ dw1 = NO_DEP_WEAK;
+
+ ds2 = TODO_SPEC (tmp2) & SPECULATIVE;
+ if (ds2)
+ dw2 = ds_weak (ds2);
+ else
+ dw2 = NO_DEP_WEAK;
+
+ dw = dw2 - dw1;
+ if (dw > (NO_DEP_WEAK / 8) || dw < -(NO_DEP_WEAK / 8))
+ return dw;
+ }
+
+ info_val = (*current_sched_info->rank) (tmp, tmp2);
+ if(flag_sched_rank_heuristic && info_val)
+ return info_val;
+
+ /* Compare insns based on their relation to the last scheduled
+ non-debug insn. */
+ if (flag_sched_last_insn_heuristic && last_nondebug_scheduled_insn)
+ {
+ dep_t dep1;
+ dep_t dep2;
+ rtx last = last_nondebug_scheduled_insn;
+
+ /* Classify the instructions into three classes:
+ 1) Data dependent on last schedule insn.
+ 2) Anti/Output dependent on last scheduled insn.
+ 3) Independent of last scheduled insn, or has latency of one.
+ Choose the insn from the highest numbered class if different. */
+ dep1 = sd_find_dep_between (last, tmp, true);
+
+ if (dep1 == NULL || dep_cost (dep1) == 1)
+ tmp_class = 3;
+ else if (/* Data dependence. */
+ DEP_TYPE (dep1) == REG_DEP_TRUE)
+ tmp_class = 1;
+ else
+ tmp_class = 2;
+
+ dep2 = sd_find_dep_between (last, tmp2, true);
+
+ if (dep2 == NULL || dep_cost (dep2) == 1)
+ tmp2_class = 3;
+ else if (/* Data dependence. */
+ DEP_TYPE (dep2) == REG_DEP_TRUE)
+ tmp2_class = 1;
+ else
+ tmp2_class = 2;
+
+ if ((val = tmp2_class - tmp_class))
+ return val;
+ }
+
+ /* Prefer instructions that occur earlier in the model schedule. */
+ if (sched_pressure == SCHED_PRESSURE_MODEL)
+ {
+ int diff;
+
+ diff = model_index (tmp) - model_index (tmp2);
+ if (diff != 0)
+ return diff;
+ }
+
+ /* Prefer the insn which has more later insns that depend on it.
+ This gives the scheduler more freedom when scheduling later
+ instructions at the expense of added register pressure. */
+
+ val = (dep_list_size (tmp2, SD_LIST_FORW)
+ - dep_list_size (tmp, SD_LIST_FORW));
+
+ if (flag_sched_dep_count_heuristic && val != 0)
+ return val;
+
+ /* If insns are equally good, sort by INSN_LUID (original insn order),
+ so that we make the sort stable. This minimizes instruction movement,
+ thus minimizing sched's effect on debugging and cross-jumping. */
+ return INSN_LUID (tmp) - INSN_LUID (tmp2);
+}
+
+/* Resort the array A in which only element at index N may be out of order. */
+
+HAIFA_INLINE static void
+swap_sort (rtx *a, int n)
+{
+ rtx insn = a[n - 1];
+ int i = n - 2;
+
+ while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
+ {
+ a[i + 1] = a[i];
+ i -= 1;
+ }
+ a[i + 1] = insn;
+}
+
+/* Add INSN to the insn queue so that it can be executed at least
+ N_CYCLES after the currently executing insn. Preserve insns
+ chain for debugging purposes. REASON will be printed in debugging
+ output. */
+
+HAIFA_INLINE static void
+queue_insn (rtx insn, int n_cycles, const char *reason)
+{
+ int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
+ rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
+ int new_tick;
+
+ gcc_assert (n_cycles <= max_insn_queue_index);
+ gcc_assert (!DEBUG_INSN_P (insn));
+
+ insn_queue[next_q] = link;
+ q_size += 1;
+
+ if (sched_verbose >= 2)
+ {
+ fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ",
+ (*current_sched_info->print_insn) (insn, 0));
+
+ fprintf (sched_dump, "queued for %d cycles (%s).\n", n_cycles, reason);
+ }
+
+ QUEUE_INDEX (insn) = next_q;
+
+ if (current_sched_info->flags & DO_BACKTRACKING)
+ {
+ new_tick = clock_var + n_cycles;
+ if (INSN_TICK (insn) == INVALID_TICK || INSN_TICK (insn) < new_tick)
+ INSN_TICK (insn) = new_tick;
+
+ if (INSN_EXACT_TICK (insn) != INVALID_TICK
+ && INSN_EXACT_TICK (insn) < clock_var + n_cycles)
+ {
+ must_backtrack = true;
+ if (sched_verbose >= 2)
+ fprintf (sched_dump, ";;\t\tcausing a backtrack.\n");
+ }
+ }
+}
+
+/* Remove INSN from queue. */
+static void
+queue_remove (rtx insn)
+{
+ gcc_assert (QUEUE_INDEX (insn) >= 0);
+ remove_free_INSN_LIST_elem (insn, &insn_queue[QUEUE_INDEX (insn)]);
+ q_size--;
+ QUEUE_INDEX (insn) = QUEUE_NOWHERE;
+}
+
+/* Return a pointer to the bottom of the ready list, i.e. the insn
+ with the lowest priority. */
+
+rtx *
+ready_lastpos (struct ready_list *ready)
+{
+ gcc_assert (ready->n_ready >= 1);
+ return ready->vec + ready->first - ready->n_ready + 1;
+}
+
+/* Add an element INSN to the ready list so that it ends up with the
+ lowest/highest priority depending on FIRST_P. */
+
+HAIFA_INLINE static void
+ready_add (struct ready_list *ready, rtx insn, bool first_p)
+{
+ if (!first_p)
+ {
+ if (ready->first == ready->n_ready)
+ {
+ memmove (ready->vec + ready->veclen - ready->n_ready,
+ ready_lastpos (ready),
+ ready->n_ready * sizeof (rtx));
+ ready->first = ready->veclen - 1;
+ }
+ ready->vec[ready->first - ready->n_ready] = insn;
+ }
+ else
+ {
+ if (ready->first == ready->veclen - 1)
+ {
+ if (ready->n_ready)
+ /* ready_lastpos() fails when called with (ready->n_ready == 0). */
+ memmove (ready->vec + ready->veclen - ready->n_ready - 1,
+ ready_lastpos (ready),
+ ready->n_ready * sizeof (rtx));
+ ready->first = ready->veclen - 2;
+ }
+ ready->vec[++(ready->first)] = insn;
+ }
+
+ ready->n_ready++;
+ if (DEBUG_INSN_P (insn))
+ ready->n_debug++;
+
+ gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY);
+ QUEUE_INDEX (insn) = QUEUE_READY;
+
+ if (INSN_EXACT_TICK (insn) != INVALID_TICK
+ && INSN_EXACT_TICK (insn) < clock_var)
+ {
+ must_backtrack = true;
+ }
+}
+
+/* Remove the element with the highest priority from the ready list and
+ return it. */
+
+HAIFA_INLINE static rtx
+ready_remove_first (struct ready_list *ready)
+{
+ rtx t;
+
+ gcc_assert (ready->n_ready);
+ t = ready->vec[ready->first--];
+ ready->n_ready--;
+ if (DEBUG_INSN_P (t))
+ ready->n_debug--;
+ /* If the queue becomes empty, reset it. */
+ if (ready->n_ready == 0)
+ ready->first = ready->veclen - 1;
+
+ gcc_assert (QUEUE_INDEX (t) == QUEUE_READY);
+ QUEUE_INDEX (t) = QUEUE_NOWHERE;
+
+ 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. */
+
+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--;
+ if (DEBUG_INSN_P (t))
+ ready->n_debug--;
+ for (i = index; i < ready->n_ready; i++)
+ ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
+ QUEUE_INDEX (t) = QUEUE_NOWHERE;
+ return t;
+}
+
+/* Remove INSN from the ready list. */
+static void
+ready_remove_insn (rtx insn)
+{
+ int i;
+
+ for (i = 0; i < readyp->n_ready; i++)
+ if (ready_element (readyp, i) == insn)
+ {
+ ready_remove (readyp, i);
+ return;
+ }
+ gcc_unreachable ();
+}
+
+/* Sort the ready list READY by ascending priority, using the SCHED_SORT
+ macro. */
+
+void
+ready_sort (struct ready_list *ready)
+{
+ int i;
+ rtx *first = ready_lastpos (ready);
+
+ if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
+ {
+ for (i = 0; i < ready->n_ready; i++)
+ if (!DEBUG_INSN_P (first[i]))
+ setup_insn_reg_pressure_info (first[i]);
+ }
+ if (sched_pressure == SCHED_PRESSURE_MODEL
+ && model_curr_point < model_num_insns)
+ model_set_excess_costs (first, ready->n_ready);
+ SCHED_SORT (first, ready->n_ready);
+}
+
+/* PREV is an insn that is ready to execute. Adjust its priority if that
+ will help shorten or lengthen register lifetimes as appropriate. Also
+ provide a hook for the target to tweak itself. */
+
+HAIFA_INLINE static void
+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
advance_state (curr_state);
if (sched_verbose >= 6)
fprintf (sched_dump, ";;\tAdvanced a state.\n");
-}
-
-/* Clock at which the previous instruction was issued. */
-static int last_clock_var;
+}
/* Update register pressure after scheduling INSN. */
static void
gcc_checking_assert (!DEBUG_INSN_P (insn));
for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use)
- if (dying_use_p (use) && bitmap_bit_p (curr_reg_live, use->regno))
- mark_regno_birth_or_death (use->regno, false);
+ if (dying_use_p (use))
+ mark_regno_birth_or_death (curr_reg_live, curr_reg_pressure,
+ use->regno, false);
for (set = INSN_REG_SET_LIST (insn); set != NULL; set = set->next_insn_set)
- mark_regno_birth_or_death (set->regno, true);
+ mark_regno_birth_or_death (curr_reg_live, curr_reg_pressure,
+ set->regno, true);
}
/* Set up or update (if UPDATE_P) max register pressure (see its
static int max_reg_pressure[N_REG_CLASSES];
save_reg_pressure ();
- for (i = 0; i < ira_reg_class_cover_size; i++)
- max_reg_pressure[ira_reg_class_cover[i]]
- = curr_reg_pressure[ira_reg_class_cover[i]];
+ for (i = 0; i < ira_pressure_classes_num; i++)
+ max_reg_pressure[ira_pressure_classes[i]]
+ = curr_reg_pressure[ira_pressure_classes[i]];
for (insn = NEXT_INSN (after);
insn != NULL_RTX && ! BARRIER_P (insn)
&& BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (after);
if (NONDEBUG_INSN_P (insn))
{
eq_p = true;
- for (i = 0; i < ira_reg_class_cover_size; i++)
+ for (i = 0; i < ira_pressure_classes_num; i++)
{
- p = max_reg_pressure[ira_reg_class_cover[i]];
+ p = max_reg_pressure[ira_pressure_classes[i]];
if (INSN_MAX_REG_PRESSURE (insn)[i] != p)
{
eq_p = false;
INSN_MAX_REG_PRESSURE (insn)[i]
- = max_reg_pressure[ira_reg_class_cover[i]];
+ = max_reg_pressure[ira_pressure_classes[i]];
}
}
if (update_p && eq_p)
break;
update_register_pressure (insn);
- for (i = 0; i < ira_reg_class_cover_size; i++)
- if (max_reg_pressure[ira_reg_class_cover[i]]
- < curr_reg_pressure[ira_reg_class_cover[i]])
- max_reg_pressure[ira_reg_class_cover[i]]
- = curr_reg_pressure[ira_reg_class_cover[i]];
+ for (i = 0; i < ira_pressure_classes_num; i++)
+ if (max_reg_pressure[ira_pressure_classes[i]]
+ < curr_reg_pressure[ira_pressure_classes[i]])
+ max_reg_pressure[ira_pressure_classes[i]]
+ = curr_reg_pressure[ira_pressure_classes[i]];
}
restore_reg_pressure ();
}
int i;
int before[N_REG_CLASSES];
- for (i = 0; i < ira_reg_class_cover_size; i++)
- before[i] = curr_reg_pressure[ira_reg_class_cover[i]];
+ for (i = 0; i < ira_pressure_classes_num; i++)
+ before[i] = curr_reg_pressure[ira_pressure_classes[i]];
update_register_pressure (insn);
- for (i = 0; i < ira_reg_class_cover_size; i++)
- if (curr_reg_pressure[ira_reg_class_cover[i]] != before[i])
+ for (i = 0; i < ira_pressure_classes_num; i++)
+ if (curr_reg_pressure[ira_pressure_classes[i]] != before[i])
break;
- if (i < ira_reg_class_cover_size)
+ if (i < ira_pressure_classes_num)
setup_insn_max_reg_pressure (insn, true);
}
-/* Set up register pressure at the beginning of basic block BB whose
- insns starting after insn AFTER. Set up also max register pressure
- for all insns of the basic block. */
-void
-sched_setup_bb_reg_pressure_info (basic_block bb, rtx after)
+/* Set up register pressure at the beginning of basic block BB whose
+ insns starting after insn AFTER. Set up also max register pressure
+ for all insns of the basic block. */
+void
+sched_setup_bb_reg_pressure_info (basic_block bb, rtx after)
+{
+ gcc_assert (sched_pressure == SCHED_PRESSURE_WEIGHTED);
+ initiate_bb_reg_pressure_info (bb);
+ setup_insn_max_reg_pressure (after, false);
+}
+\f
+/* If doing predication while scheduling, verify whether INSN, which
+ has just been scheduled, clobbers the conditions of any
+ instructions that must be predicated in order to break their
+ dependencies. If so, remove them from the queues so that they will
+ only be scheduled once their control dependency is resolved. */
+
+static void
+check_clobbered_conditions (rtx insn)
+{
+ HARD_REG_SET t;
+ int i;
+
+ if ((current_sched_info->flags & DO_PREDICATION) == 0)
+ return;
+
+ find_all_hard_reg_sets (insn, &t);
+
+ restart:
+ for (i = 0; i < ready.n_ready; i++)
+ {
+ rtx x = ready_element (&ready, i);
+ if (TODO_SPEC (x) == DEP_CONTROL && cond_clobbered_p (x, t))
+ {
+ ready_remove_insn (x);
+ goto restart;
+ }
+ }
+ for (i = 0; i <= max_insn_queue_index; i++)
+ {
+ rtx link;
+ int q = NEXT_Q_AFTER (q_ptr, i);
+
+ restart_queue:
+ for (link = insn_queue[q]; link; link = XEXP (link, 1))
+ {
+ rtx x = XEXP (link, 0);
+ if (TODO_SPEC (x) == DEP_CONTROL && cond_clobbered_p (x, t))
+ {
+ queue_remove (x);
+ goto restart_queue;
+ }
+ }
+ }
+}
+\f
+/* Return (in order):
+
+ - positive if INSN adversely affects the pressure on one
+ register class
+
+ - negative if INSN reduces the pressure on one register class
+
+ - 0 if INSN doesn't affect the pressure on any register class. */
+
+static int
+model_classify_pressure (struct model_insn_info *insn)
+{
+ struct reg_pressure_data *reg_pressure;
+ int death[N_REG_CLASSES];
+ int pci, cl, sum;
+
+ calculate_reg_deaths (insn->insn, death);
+ reg_pressure = INSN_REG_PRESSURE (insn->insn);
+ sum = 0;
+ for (pci = 0; pci < ira_pressure_classes_num; pci++)
+ {
+ cl = ira_pressure_classes[pci];
+ if (death[cl] < reg_pressure[pci].set_increase)
+ return 1;
+ sum += reg_pressure[pci].set_increase - death[cl];
+ }
+ return sum;
+}
+
+/* Return true if INSN1 should come before INSN2 in the model schedule. */
+
+static int
+model_order_p (struct model_insn_info *insn1, struct model_insn_info *insn2)
+{
+ unsigned int height1, height2;
+ unsigned int priority1, priority2;
+
+ /* Prefer instructions with a higher model priority. */
+ if (insn1->model_priority != insn2->model_priority)
+ return insn1->model_priority > insn2->model_priority;
+
+ /* Combine the length of the longest path of satisfied true dependencies
+ that leads to each instruction (depth) with the length of the longest
+ path of any dependencies that leads from the instruction (alap).
+ Prefer instructions with the greatest combined length. If the combined
+ lengths are equal, prefer instructions with the greatest depth.
+
+ The idea is that, if we have a set S of "equal" instructions that each
+ have ALAP value X, and we pick one such instruction I, any true-dependent
+ successors of I that have ALAP value X - 1 should be preferred over S.
+ This encourages the schedule to be "narrow" rather than "wide".
+ However, if I is a low-priority instruction that we decided to
+ schedule because of its model_classify_pressure, and if there
+ is a set of higher-priority instructions T, the aforementioned
+ successors of I should not have the edge over T. */
+ height1 = insn1->depth + insn1->alap;
+ height2 = insn2->depth + insn2->alap;
+ if (height1 != height2)
+ return height1 > height2;
+ if (insn1->depth != insn2->depth)
+ return insn1->depth > insn2->depth;
+
+ /* We have no real preference between INSN1 an INSN2 as far as attempts
+ to reduce pressure go. Prefer instructions with higher priorities. */
+ priority1 = INSN_PRIORITY (insn1->insn);
+ priority2 = INSN_PRIORITY (insn2->insn);
+ if (priority1 != priority2)
+ return priority1 > priority2;
+
+ /* Use the original rtl sequence as a tie-breaker. */
+ return insn1 < insn2;
+}
+
+/* Add INSN to the model worklist immediately after PREV. Add it to the
+ beginning of the list if PREV is null. */
+
+static void
+model_add_to_worklist_at (struct model_insn_info *insn,
+ struct model_insn_info *prev)
+{
+ gcc_assert (QUEUE_INDEX (insn->insn) == QUEUE_NOWHERE);
+ QUEUE_INDEX (insn->insn) = QUEUE_READY;
+
+ insn->prev = prev;
+ if (prev)
+ {
+ insn->next = prev->next;
+ prev->next = insn;
+ }
+ else
+ {
+ insn->next = model_worklist;
+ model_worklist = insn;
+ }
+ if (insn->next)
+ insn->next->prev = insn;
+}
+
+/* Remove INSN from the model worklist. */
+
+static void
+model_remove_from_worklist (struct model_insn_info *insn)
+{
+ gcc_assert (QUEUE_INDEX (insn->insn) == QUEUE_READY);
+ QUEUE_INDEX (insn->insn) = QUEUE_NOWHERE;
+
+ if (insn->prev)
+ insn->prev->next = insn->next;
+ else
+ model_worklist = insn->next;
+ if (insn->next)
+ insn->next->prev = insn->prev;
+}
+
+/* Add INSN to the model worklist. Start looking for a suitable position
+ between neighbors PREV and NEXT, testing at most MAX_SCHED_READY_INSNS
+ insns either side. A null PREV indicates the beginning of the list and
+ a null NEXT indicates the end. */
+
+static void
+model_add_to_worklist (struct model_insn_info *insn,
+ struct model_insn_info *prev,
+ struct model_insn_info *next)
+{
+ int count;
+
+ count = MAX_SCHED_READY_INSNS;
+ if (count > 0 && prev && model_order_p (insn, prev))
+ do
+ {
+ count--;
+ prev = prev->prev;
+ }
+ while (count > 0 && prev && model_order_p (insn, prev));
+ else
+ while (count > 0 && next && model_order_p (next, insn))
+ {
+ count--;
+ prev = next;
+ next = next->next;
+ }
+ model_add_to_worklist_at (insn, prev);
+}
+
+/* INSN may now have a higher priority (in the model_order_p sense)
+ than before. Move it up the worklist if necessary. */
+
+static void
+model_promote_insn (struct model_insn_info *insn)
+{
+ struct model_insn_info *prev;
+ int count;
+
+ prev = insn->prev;
+ count = MAX_SCHED_READY_INSNS;
+ while (count > 0 && prev && model_order_p (insn, prev))
+ {
+ count--;
+ prev = prev->prev;
+ }
+ if (prev != insn->prev)
+ {
+ model_remove_from_worklist (insn);
+ model_add_to_worklist_at (insn, prev);
+ }
+}
+
+/* Add INSN to the end of the model schedule. */
+
+static void
+model_add_to_schedule (rtx insn)
+{
+ unsigned int point;
+
+ gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
+ QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
+
+ point = VEC_length (rtx, model_schedule);
+ VEC_quick_push (rtx, model_schedule, insn);
+ INSN_MODEL_INDEX (insn) = point + 1;
+}
+
+/* Analyze the instructions that are to be scheduled, setting up
+ MODEL_INSN_INFO (...) and model_num_insns accordingly. Add ready
+ instructions to model_worklist. */
+
+static void
+model_analyze_insns (void)
+{
+ rtx start, end, iter;
+ sd_iterator_def sd_it;
+ dep_t dep;
+ struct model_insn_info *insn, *con;
+
+ model_num_insns = 0;
+ start = PREV_INSN (current_sched_info->next_tail);
+ end = current_sched_info->prev_head;
+ for (iter = start; iter != end; iter = PREV_INSN (iter))
+ if (NONDEBUG_INSN_P (iter))
+ {
+ insn = MODEL_INSN_INFO (iter);
+ insn->insn = iter;
+ FOR_EACH_DEP (iter, SD_LIST_FORW, sd_it, dep)
+ {
+ con = MODEL_INSN_INFO (DEP_CON (dep));
+ if (con->insn && insn->alap < con->alap + 1)
+ insn->alap = con->alap + 1;
+ }
+
+ insn->old_queue = QUEUE_INDEX (iter);
+ QUEUE_INDEX (iter) = QUEUE_NOWHERE;
+
+ insn->unscheduled_preds = dep_list_size (iter, SD_LIST_HARD_BACK);
+ if (insn->unscheduled_preds == 0)
+ model_add_to_worklist (insn, NULL, model_worklist);
+
+ model_num_insns++;
+ }
+}
+
+/* The global state describes the register pressure at the start of the
+ model schedule. Initialize GROUP accordingly. */
+
+static void
+model_init_pressure_group (struct model_pressure_group *group)
+{
+ int pci, cl;
+
+ for (pci = 0; pci < ira_pressure_classes_num; pci++)
+ {
+ cl = ira_pressure_classes[pci];
+ group->limits[pci].pressure = curr_reg_pressure[cl];
+ group->limits[pci].point = 0;
+ }
+ /* Use index model_num_insns to record the state after the last
+ instruction in the model schedule. */
+ group->model = XNEWVEC (struct model_pressure_data,
+ (model_num_insns + 1) * ira_pressure_classes_num);
+}
+
+/* Record that MODEL_REF_PRESSURE (GROUP, POINT, PCI) is PRESSURE.
+ Update the maximum pressure for the whole schedule. */
+
+static void
+model_record_pressure (struct model_pressure_group *group,
+ int point, int pci, int pressure)
+{
+ MODEL_REF_PRESSURE (group, point, pci) = pressure;
+ if (group->limits[pci].pressure < pressure)
+ {
+ group->limits[pci].pressure = pressure;
+ group->limits[pci].point = point;
+ }
+}
+
+/* INSN has just been added to the end of the model schedule. Record its
+ register-pressure information. */
+
+static void
+model_record_pressures (struct model_insn_info *insn)
+{
+ struct reg_pressure_data *reg_pressure;
+ int point, pci, cl, delta;
+ int death[N_REG_CLASSES];
+
+ point = model_index (insn->insn);
+ if (sched_verbose >= 2)
+ {
+ char buf[2048];
+
+ if (point == 0)
+ {
+ fprintf (sched_dump, "\n;;\tModel schedule:\n;;\n");
+ fprintf (sched_dump, ";;\t| idx insn | mpri hght dpth prio |\n");
+ }
+ print_pattern (buf, PATTERN (insn->insn), 0);
+ fprintf (sched_dump, ";;\t| %3d %4d | %4d %4d %4d %4d | %-30s ",
+ point, INSN_UID (insn->insn), insn->model_priority,
+ insn->depth + insn->alap, insn->depth,
+ INSN_PRIORITY (insn->insn), buf);
+ }
+ calculate_reg_deaths (insn->insn, death);
+ reg_pressure = INSN_REG_PRESSURE (insn->insn);
+ for (pci = 0; pci < ira_pressure_classes_num; pci++)
+ {
+ cl = ira_pressure_classes[pci];
+ delta = reg_pressure[pci].set_increase - death[cl];
+ if (sched_verbose >= 2)
+ fprintf (sched_dump, " %s:[%d,%+d]", reg_class_names[cl],
+ curr_reg_pressure[cl], delta);
+ model_record_pressure (&model_before_pressure, point, pci,
+ curr_reg_pressure[cl]);
+ }
+ if (sched_verbose >= 2)
+ fprintf (sched_dump, "\n");
+}
+
+/* All instructions have been added to the model schedule. Record the
+ final register pressure in GROUP and set up all MODEL_MAX_PRESSUREs. */
+
+static void
+model_record_final_pressures (struct model_pressure_group *group)
+{
+ int point, pci, max_pressure, ref_pressure, cl;
+
+ for (pci = 0; pci < ira_pressure_classes_num; pci++)
+ {
+ /* Record the final pressure for this class. */
+ cl = ira_pressure_classes[pci];
+ point = model_num_insns;
+ ref_pressure = curr_reg_pressure[cl];
+ model_record_pressure (group, point, pci, ref_pressure);
+
+ /* Record the original maximum pressure. */
+ group->limits[pci].orig_pressure = group->limits[pci].pressure;
+
+ /* Update the MODEL_MAX_PRESSURE for every point of the schedule. */
+ max_pressure = ref_pressure;
+ MODEL_MAX_PRESSURE (group, point, pci) = max_pressure;
+ while (point > 0)
+ {
+ point--;
+ ref_pressure = MODEL_REF_PRESSURE (group, point, pci);
+ max_pressure = MAX (max_pressure, ref_pressure);
+ MODEL_MAX_PRESSURE (group, point, pci) = max_pressure;
+ }
+ }
+}
+
+/* Update all successors of INSN, given that INSN has just been scheduled. */
+
+static void
+model_add_successors_to_worklist (struct model_insn_info *insn)
+{
+ sd_iterator_def sd_it;
+ struct model_insn_info *con;
+ dep_t dep;
+
+ FOR_EACH_DEP (insn->insn, SD_LIST_FORW, sd_it, dep)
+ {
+ con = MODEL_INSN_INFO (DEP_CON (dep));
+ /* Ignore debug instructions, and instructions from other blocks. */
+ if (con->insn)
+ {
+ con->unscheduled_preds--;
+
+ /* Update the depth field of each true-dependent successor.
+ Increasing the depth gives them a higher priority than
+ before. */
+ if (DEP_TYPE (dep) == REG_DEP_TRUE && con->depth < insn->depth + 1)
+ {
+ con->depth = insn->depth + 1;
+ if (QUEUE_INDEX (con->insn) == QUEUE_READY)
+ model_promote_insn (con);
+ }
+
+ /* If this is a true dependency, or if there are no remaining
+ dependencies for CON (meaning that CON only had non-true
+ dependencies), make sure that CON is on the worklist.
+ We don't bother otherwise because it would tend to fill the
+ worklist with a lot of low-priority instructions that are not
+ yet ready to issue. */
+ if ((con->depth > 0 || con->unscheduled_preds == 0)
+ && QUEUE_INDEX (con->insn) == QUEUE_NOWHERE)
+ model_add_to_worklist (con, insn, insn->next);
+ }
+ }
+}
+
+/* Give INSN a higher priority than any current instruction, then give
+ unscheduled predecessors of INSN a higher priority still. If any of
+ those predecessors are not on the model worklist, do the same for its
+ predecessors, and so on. */
+
+static void
+model_promote_predecessors (struct model_insn_info *insn)
+{
+ struct model_insn_info *pro, *first;
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ if (sched_verbose >= 7)
+ fprintf (sched_dump, ";;\t+--- priority of %d = %d, priority of",
+ INSN_UID (insn->insn), model_next_priority);
+ insn->model_priority = model_next_priority++;
+ model_remove_from_worklist (insn);
+ model_add_to_worklist_at (insn, NULL);
+
+ first = NULL;
+ for (;;)
+ {
+ FOR_EACH_DEP (insn->insn, SD_LIST_HARD_BACK, sd_it, dep)
+ {
+ pro = MODEL_INSN_INFO (DEP_PRO (dep));
+ /* The first test is to ignore debug instructions, and instructions
+ from other blocks. */
+ if (pro->insn
+ && pro->model_priority != model_next_priority
+ && QUEUE_INDEX (pro->insn) != QUEUE_SCHEDULED)
+ {
+ pro->model_priority = model_next_priority;
+ if (sched_verbose >= 7)
+ fprintf (sched_dump, " %d", INSN_UID (pro->insn));
+ if (QUEUE_INDEX (pro->insn) == QUEUE_READY)
+ {
+ /* PRO is already in the worklist, but it now has
+ a higher priority than before. Move it at the
+ appropriate place. */
+ model_remove_from_worklist (pro);
+ model_add_to_worklist (pro, NULL, model_worklist);
+ }
+ else
+ {
+ /* PRO isn't in the worklist. Recursively process
+ its predecessors until we find one that is. */
+ pro->next = first;
+ first = pro;
+ }
+ }
+ }
+ if (!first)
+ break;
+ insn = first;
+ first = insn->next;
+ }
+ if (sched_verbose >= 7)
+ fprintf (sched_dump, " = %d\n", model_next_priority);
+ model_next_priority++;
+}
+
+/* Pick one instruction from model_worklist and process it. */
+
+static void
+model_choose_insn (void)
+{
+ struct model_insn_info *insn, *fallback;
+ int count;
+
+ if (sched_verbose >= 7)
+ {
+ fprintf (sched_dump, ";;\t+--- worklist:\n");
+ insn = model_worklist;
+ count = MAX_SCHED_READY_INSNS;
+ while (count > 0 && insn)
+ {
+ fprintf (sched_dump, ";;\t+--- %d [%d, %d, %d, %d]\n",
+ INSN_UID (insn->insn), insn->model_priority,
+ insn->depth + insn->alap, insn->depth,
+ INSN_PRIORITY (insn->insn));
+ count--;
+ insn = insn->next;
+ }
+ }
+
+ /* Look for a ready instruction whose model_classify_priority is zero
+ or negative, picking the highest-priority one. Adding such an
+ instruction to the schedule now should do no harm, and may actually
+ do some good.
+
+ Failing that, see whether there is an instruction with the highest
+ extant model_priority that is not yet ready, but which would reduce
+ pressure if it became ready. This is designed to catch cases like:
+
+ (set (mem (reg R1)) (reg R2))
+
+ where the instruction is the last remaining use of R1 and where the
+ value of R2 is not yet available (or vice versa). The death of R1
+ means that this instruction already reduces pressure. It is of
+ course possible that the computation of R2 involves other registers
+ that are hard to kill, but such cases are rare enough for this
+ heuristic to be a win in general.
+
+ Failing that, just pick the highest-priority instruction in the
+ worklist. */
+ count = MAX_SCHED_READY_INSNS;
+ insn = model_worklist;
+ fallback = 0;
+ for (;;)
+ {
+ if (count == 0 || !insn)
+ {
+ insn = fallback ? fallback : model_worklist;
+ break;
+ }
+ if (insn->unscheduled_preds)
+ {
+ if (model_worklist->model_priority == insn->model_priority
+ && !fallback
+ && model_classify_pressure (insn) < 0)
+ fallback = insn;
+ }
+ else
+ {
+ if (model_classify_pressure (insn) <= 0)
+ break;
+ }
+ count--;
+ insn = insn->next;
+ }
+
+ if (sched_verbose >= 7 && insn != model_worklist)
+ {
+ if (insn->unscheduled_preds)
+ fprintf (sched_dump, ";;\t+--- promoting insn %d, with dependencies\n",
+ INSN_UID (insn->insn));
+ else
+ fprintf (sched_dump, ";;\t+--- promoting insn %d, which is ready\n",
+ INSN_UID (insn->insn));
+ }
+ if (insn->unscheduled_preds)
+ /* INSN isn't yet ready to issue. Give all its predecessors the
+ highest priority. */
+ model_promote_predecessors (insn);
+ else
+ {
+ /* INSN is ready. Add it to the end of model_schedule and
+ process its successors. */
+ model_add_successors_to_worklist (insn);
+ model_remove_from_worklist (insn);
+ model_add_to_schedule (insn->insn);
+ model_record_pressures (insn);
+ update_register_pressure (insn->insn);
+ }
+}
+
+/* Restore all QUEUE_INDEXs to the values that they had before
+ model_start_schedule was called. */
+
+static void
+model_reset_queue_indices (void)
+{
+ unsigned int i;
+ rtx insn;
+
+ FOR_EACH_VEC_ELT (rtx, model_schedule, i, insn)
+ QUEUE_INDEX (insn) = MODEL_INSN_INFO (insn)->old_queue;
+}
+
+/* We have calculated the model schedule and spill costs. Print a summary
+ to sched_dump. */
+
+static void
+model_dump_pressure_summary (void)
+{
+ int pci, cl;
+
+ fprintf (sched_dump, ";; Pressure summary:");
+ for (pci = 0; pci < ira_pressure_classes_num; pci++)
+ {
+ cl = ira_pressure_classes[pci];
+ fprintf (sched_dump, " %s:%d", reg_class_names[cl],
+ model_before_pressure.limits[pci].pressure);
+ }
+ fprintf (sched_dump, "\n\n");
+}
+
+/* Initialize the SCHED_PRESSURE_MODEL information for the current
+ scheduling region. */
+
+static void
+model_start_schedule (void)
+{
+ basic_block bb;
+
+ model_next_priority = 1;
+ model_schedule = VEC_alloc (rtx, heap, sched_max_luid);
+ model_insns = XCNEWVEC (struct model_insn_info, sched_max_luid);
+
+ bb = BLOCK_FOR_INSN (NEXT_INSN (current_sched_info->prev_head));
+ initiate_reg_pressure_info (df_get_live_in (bb));
+
+ model_analyze_insns ();
+ model_init_pressure_group (&model_before_pressure);
+ while (model_worklist)
+ model_choose_insn ();
+ gcc_assert (model_num_insns == (int) VEC_length (rtx, model_schedule));
+ if (sched_verbose >= 2)
+ fprintf (sched_dump, "\n");
+
+ model_record_final_pressures (&model_before_pressure);
+ model_reset_queue_indices ();
+
+ XDELETEVEC (model_insns);
+
+ model_curr_point = 0;
+ initiate_reg_pressure_info (df_get_live_in (bb));
+ if (sched_verbose >= 1)
+ model_dump_pressure_summary ();
+}
+
+/* Free the information associated with GROUP. */
+
+static void
+model_finalize_pressure_group (struct model_pressure_group *group)
+{
+ XDELETEVEC (group->model);
+}
+
+/* Free the information created by model_start_schedule. */
+
+static void
+model_end_schedule (void)
{
- gcc_assert (sched_pressure_p);
- initiate_bb_reg_pressure_info (bb);
- setup_insn_max_reg_pressure (after, false);
+ model_finalize_pressure_group (&model_before_pressure);
+ VEC_free (rtx, heap, model_schedule);
}
+\f
+/* A structure that holds local state for the loop in schedule_block. */
+struct sched_block_state
+{
+ /* True if no real insns have been scheduled in the current cycle. */
+ bool first_cycle_insn_p;
+ /* True if a shadow insn has been scheduled in the current cycle, which
+ means that no more normal insns can be issued. */
+ bool shadows_only_p;
+ /* True if we're winding down a modulo schedule, which means that we only
+ issue insns with INSN_EXACT_TICK set. */
+ bool modulo_epilogue;
+ /* Initialized with the machine's issue rate every cycle, and updated
+ by calls to the variable_issue hook. */
+ int can_issue_more;
+};
/* INSN is the "currently executing insn". Launch each insn which was
waiting on INSN. READY is the ready list which contains the insns
if (pressure_info != NULL)
{
fputc (':', sched_dump);
- for (i = 0; i < ira_reg_class_cover_size; i++)
+ for (i = 0; i < ira_pressure_classes_num; i++)
fprintf (sched_dump, "%s%+d(%d)",
- reg_class_names[ira_reg_class_cover[i]],
+ reg_class_names[ira_pressure_classes[i]],
pressure_info[i].set_increase, pressure_info[i].change);
}
+ if (sched_pressure == SCHED_PRESSURE_MODEL
+ && model_curr_point < model_num_insns
+ && model_index (insn) == model_curr_point)
+ fprintf (sched_dump, ":model %d", model_curr_point);
fputc ('\n', sched_dump);
}
- if (sched_pressure_p && !DEBUG_INSN_P (insn))
+ if (sched_pressure == SCHED_PRESSURE_WEIGHTED && !DEBUG_INSN_P (insn))
update_reg_and_insn_max_reg_pressure (insn);
/* Scheduling instruction should have all its dependencies resolved and
should have been removed from the ready list. */
- gcc_assert (sd_lists_empty_p (insn, SD_LIST_BACK));
+ gcc_assert (sd_lists_empty_p (insn, SD_LIST_HARD_BACK));
/* Reset debug insns invalidated by moving this insn. */
if (MAY_HAVE_DEBUG_INSNS && !DEBUG_INSN_P (insn))
rtx dbg = DEP_PRO (dep);
struct reg_use_data *use, *next;
+ if (DEP_STATUS (dep) & DEP_CANCELLED)
+ {
+ sd_iterator_next (&sd_it);
+ continue;
+ }
+
gcc_assert (DEBUG_INSN_P (dbg));
if (sched_verbose >= 6)
gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
+ if (sched_pressure == SCHED_PRESSURE_MODEL
+ && model_curr_point < model_num_insns
+ && NONDEBUG_INSN_P (insn))
+ {
+ if (model_index (insn) == model_curr_point)
+ do
+ model_curr_point++;
+ while (model_curr_point < model_num_insns
+ && (QUEUE_INDEX (MODEL_INSN (model_curr_point))
+ == QUEUE_SCHEDULED));
+ else
+ model_recompute (insn);
+ model_update_limit_points ();
+ update_register_pressure (insn);
+ if (sched_verbose >= 2)
+ print_curr_reg_pressure ();
+ }
+
gcc_assert (INSN_TICK (insn) >= MIN_TICK);
if (INSN_TICK (insn) > clock_var)
/* INSN has been prematurely moved from the queue to the ready list.
INSN_TICK untouched. This is a machine-dependent issue, actually. */
INSN_TICK (insn) = clock_var;
+ check_clobbered_conditions (insn);
+
/* Update dependent instructions. */
for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
sd_iterator_cond (&sd_it, &dep);)
{
rtx next = DEP_CON (dep);
+ bool cancelled = (DEP_STATUS (dep) & DEP_CANCELLED) != 0;
/* Resolve the dependence between INSN and NEXT.
sd_resolve_dep () moves current dep to another list thus
advancing the iterator. */
sd_resolve_dep (sd_it);
+ if (cancelled)
+ {
+ if (QUEUE_INDEX (next) != QUEUE_SCHEDULED)
+ {
+ int tick = INSN_TICK (next);
+ gcc_assert (ORIG_PAT (next) != NULL_RTX);
+ haifa_change_pattern (next, ORIG_PAT (next));
+ INSN_TICK (next) = tick;
+ if (sd_lists_empty_p (next, SD_LIST_BACK))
+ TODO_SPEC (next) = 0;
+ else if (!sd_lists_empty_p (next, SD_LIST_HARD_BACK))
+ TODO_SPEC (next) = HARD_DEP;
+ }
+ continue;
+ }
+
/* Don't bother trying to mark next as ready if insn is a debug
insn. If insn is the last hard dependency, it will have
already been discounted. */
}
}
- /* This is the place where scheduler doesn't *basically* need backward and
- forward dependencies for INSN anymore. Nevertheless they are used in
- heuristics in rank_for_schedule (), early_queue_to_ready () and in
- some targets (e.g. rs6000). Thus the earliest place where we *can*
- remove dependencies is after targetm.sched.finish () call in
- schedule_block (). But, on the other side, the safest place to remove
- dependencies is when we are finishing scheduling entire region. As we
- don't generate [many] dependencies during scheduling itself, we won't
- need memory until beginning of next region.
- Bottom line: Dependencies are removed for all insns in the end of
- scheduling the region. */
-
/* Annotate the instruction with issue information -- TImode
indicates that the instruction is expected not to be able
to issue on the same cycle as the previous insn. A machine
{
rtx next_tail, insn, next;
- note_list = 0;
- if (head == tail && !INSN_P (head))
+ note_list = 0;
+ if (head == tail && !INSN_P (head))
+ return;
+
+ next_tail = NEXT_INSN (tail);
+ for (insn = head; insn != next_tail; insn = next)
+ {
+ next = NEXT_INSN (insn);
+ if (!NOTE_P (insn))
+ continue;
+
+ switch (NOTE_KIND (insn))
+ {
+ case NOTE_INSN_BASIC_BLOCK:
+ continue;
+
+ case NOTE_INSN_EPILOGUE_BEG:
+ if (insn != tail)
+ {
+ remove_insn (insn);
+ add_reg_note (next, REG_SAVE_NOTE,
+ GEN_INT (NOTE_INSN_EPILOGUE_BEG));
+ break;
+ }
+ /* FALLTHRU */
+
+ default:
+ remove_insn (insn);
+
+ /* Add the note to list that ends at NOTE_LIST. */
+ PREV_INSN (insn) = note_list;
+ NEXT_INSN (insn) = NULL_RTX;
+ if (note_list)
+ NEXT_INSN (note_list) = insn;
+ note_list = insn;
+ break;
+ }
+
+ gcc_assert ((sel_sched_p () || insn != tail) && insn != head);
+ }
+}
+
+/* A structure to record enough data to allow us to backtrack the scheduler to
+ a previous state. */
+struct haifa_saved_data
+{
+ /* Next entry on the list. */
+ struct haifa_saved_data *next;
+
+ /* Backtracking is associated with scheduling insns that have delay slots.
+ DELAY_PAIR points to the structure that contains the insns involved, and
+ the number of cycles between them. */
+ struct delay_pair *delay_pair;
+
+ /* Data used by the frontend (e.g. sched-ebb or sched-rgn). */
+ void *fe_saved_data;
+ /* Data used by the backend. */
+ void *be_saved_data;
+
+ /* Copies of global state. */
+ int clock_var, last_clock_var;
+ struct ready_list ready;
+ state_t curr_state;
+
+ rtx last_scheduled_insn;
+ rtx last_nondebug_scheduled_insn;
+ int cycle_issued_insns;
+
+ /* Copies of state used in the inner loop of schedule_block. */
+ struct sched_block_state sched_block;
+
+ /* We don't need to save q_ptr, as its value is arbitrary and we can set it
+ to 0 when restoring. */
+ int q_size;
+ rtx *insn_queue;
+};
+
+/* A record, in reverse order, of all scheduled insns which have delay slots
+ and may require backtracking. */
+static struct haifa_saved_data *backtrack_queue;
+
+/* For every dependency of INSN, set the FEEDS_BACKTRACK_INSN bit according
+ to SET_P. */
+static void
+mark_backtrack_feeds (rtx insn, int set_p)
+{
+ sd_iterator_def sd_it;
+ dep_t dep;
+ FOR_EACH_DEP (insn, SD_LIST_HARD_BACK, sd_it, dep)
+ {
+ FEEDS_BACKTRACK_INSN (DEP_PRO (dep)) = set_p;
+ }
+}
+
+/* Save the current scheduler state so that we can backtrack to it
+ later if necessary. PAIR gives the insns that make it necessary to
+ save this point. SCHED_BLOCK is the local state of schedule_block
+ that need to be saved. */
+static void
+save_backtrack_point (struct delay_pair *pair,
+ struct sched_block_state sched_block)
+{
+ int i;
+ struct haifa_saved_data *save = XNEW (struct haifa_saved_data);
+
+ save->curr_state = xmalloc (dfa_state_size);
+ memcpy (save->curr_state, curr_state, dfa_state_size);
+
+ save->ready.first = ready.first;
+ save->ready.n_ready = ready.n_ready;
+ save->ready.n_debug = ready.n_debug;
+ save->ready.veclen = ready.veclen;
+ save->ready.vec = XNEWVEC (rtx, ready.veclen);
+ memcpy (save->ready.vec, ready.vec, ready.veclen * sizeof (rtx));
+
+ save->insn_queue = XNEWVEC (rtx, max_insn_queue_index + 1);
+ save->q_size = q_size;
+ for (i = 0; i <= max_insn_queue_index; i++)
+ {
+ int q = NEXT_Q_AFTER (q_ptr, i);
+ save->insn_queue[i] = copy_INSN_LIST (insn_queue[q]);
+ }
+
+ save->clock_var = clock_var;
+ save->last_clock_var = last_clock_var;
+ save->cycle_issued_insns = cycle_issued_insns;
+ save->last_scheduled_insn = last_scheduled_insn;
+ save->last_nondebug_scheduled_insn = last_nondebug_scheduled_insn;
+
+ save->sched_block = sched_block;
+
+ if (current_sched_info->save_state)
+ save->fe_saved_data = (*current_sched_info->save_state) ();
+
+ if (targetm.sched.alloc_sched_context)
+ {
+ save->be_saved_data = targetm.sched.alloc_sched_context ();
+ targetm.sched.init_sched_context (save->be_saved_data, false);
+ }
+ else
+ save->be_saved_data = NULL;
+
+ save->delay_pair = pair;
+
+ save->next = backtrack_queue;
+ backtrack_queue = save;
+
+ while (pair)
+ {
+ mark_backtrack_feeds (pair->i2, 1);
+ INSN_TICK (pair->i2) = INVALID_TICK;
+ INSN_EXACT_TICK (pair->i2) = clock_var + pair_delay (pair);
+ SHADOW_P (pair->i2) = pair->stages == 0;
+ pair = pair->next_same_i1;
+ }
+}
+
+/* Walk the ready list and all queues. If any insns have unresolved backwards
+ dependencies, these must be cancelled deps, broken by predication. Set or
+ clear (depending on SET) the DEP_CANCELLED bit in DEP_STATUS. */
+
+static void
+toggle_cancelled_flags (bool set)
+{
+ int i;
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ if (ready.n_ready > 0)
+ {
+ rtx *first = ready_lastpos (&ready);
+ for (i = 0; i < ready.n_ready; i++)
+ FOR_EACH_DEP (first[i], SD_LIST_BACK, sd_it, dep)
+ if (!DEBUG_INSN_P (DEP_PRO (dep)))
+ {
+ if (set)
+ DEP_STATUS (dep) |= DEP_CANCELLED;
+ else
+ DEP_STATUS (dep) &= ~DEP_CANCELLED;
+ }
+ }
+ for (i = 0; i <= max_insn_queue_index; i++)
+ {
+ int q = NEXT_Q_AFTER (q_ptr, i);
+ rtx link;
+ for (link = insn_queue[q]; link; link = XEXP (link, 1))
+ {
+ rtx insn = XEXP (link, 0);
+ FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
+ if (!DEBUG_INSN_P (DEP_PRO (dep)))
+ {
+ if (set)
+ DEP_STATUS (dep) |= DEP_CANCELLED;
+ else
+ DEP_STATUS (dep) &= ~DEP_CANCELLED;
+ }
+ }
+ }
+}
+
+/* Pop entries from the SCHEDULED_INSNS vector up to and including INSN.
+ Restore their dependencies to an unresolved state, and mark them as
+ queued nowhere. */
+
+static void
+unschedule_insns_until (rtx insn)
+{
+ VEC (rtx, heap) *recompute_vec;
+
+ recompute_vec = VEC_alloc (rtx, heap, 0);
+
+ /* Make two passes over the insns to be unscheduled. First, we clear out
+ dependencies and other trivial bookkeeping. */
+ for (;;)
+ {
+ rtx last;
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ last = VEC_pop (rtx, scheduled_insns);
+
+ /* This will be changed by restore_backtrack_point if the insn is in
+ any queue. */
+ QUEUE_INDEX (last) = QUEUE_NOWHERE;
+ if (last != insn)
+ INSN_TICK (last) = INVALID_TICK;
+
+ if (modulo_ii > 0 && INSN_UID (last) < modulo_iter0_max_uid)
+ modulo_insns_scheduled--;
+
+ for (sd_it = sd_iterator_start (last, SD_LIST_RES_FORW);
+ sd_iterator_cond (&sd_it, &dep);)
+ {
+ rtx con = DEP_CON (dep);
+ sd_unresolve_dep (sd_it);
+ if (!MUST_RECOMPUTE_SPEC_P (con))
+ {
+ MUST_RECOMPUTE_SPEC_P (con) = 1;
+ VEC_safe_push (rtx, heap, recompute_vec, con);
+ }
+ }
+
+ if (last == insn)
+ break;
+ }
+
+ /* A second pass, to update ready and speculation status for insns
+ depending on the unscheduled ones. The first pass must have
+ popped the scheduled_insns vector up to the point where we
+ restart scheduling, as recompute_todo_spec requires it to be
+ up-to-date. */
+ while (!VEC_empty (rtx, recompute_vec))
+ {
+ rtx con;
+
+ con = VEC_pop (rtx, recompute_vec);
+ MUST_RECOMPUTE_SPEC_P (con) = 0;
+ if (!sd_lists_empty_p (con, SD_LIST_HARD_BACK))
+ {
+ TODO_SPEC (con) = HARD_DEP;
+ INSN_TICK (con) = INVALID_TICK;
+ if (PREDICATED_PAT (con) != NULL_RTX)
+ haifa_change_pattern (con, ORIG_PAT (con));
+ }
+ else if (QUEUE_INDEX (con) != QUEUE_SCHEDULED)
+ TODO_SPEC (con) = recompute_todo_spec (con);
+ }
+ VEC_free (rtx, heap, recompute_vec);
+}
+
+/* Restore scheduler state from the topmost entry on the backtracking queue.
+ PSCHED_BLOCK_P points to the local data of schedule_block that we must
+ overwrite with the saved data.
+ The caller must already have called unschedule_insns_until. */
+
+static void
+restore_last_backtrack_point (struct sched_block_state *psched_block)
+{
+ rtx link;
+ int i;
+ struct haifa_saved_data *save = backtrack_queue;
+
+ backtrack_queue = save->next;
+
+ if (current_sched_info->restore_state)
+ (*current_sched_info->restore_state) (save->fe_saved_data);
+
+ if (targetm.sched.alloc_sched_context)
+ {
+ targetm.sched.set_sched_context (save->be_saved_data);
+ targetm.sched.free_sched_context (save->be_saved_data);
+ }
+
+ /* Clear the QUEUE_INDEX of everything in the ready list or one
+ of the queues. */
+ if (ready.n_ready > 0)
+ {
+ rtx *first = ready_lastpos (&ready);
+ for (i = 0; i < ready.n_ready; i++)
+ {
+ rtx insn = first[i];
+ QUEUE_INDEX (insn) = QUEUE_NOWHERE;
+ INSN_TICK (insn) = INVALID_TICK;
+ }
+ }
+ for (i = 0; i <= max_insn_queue_index; i++)
+ {
+ int q = NEXT_Q_AFTER (q_ptr, i);
+
+ for (link = insn_queue[q]; link; link = XEXP (link, 1))
+ {
+ rtx x = XEXP (link, 0);
+ QUEUE_INDEX (x) = QUEUE_NOWHERE;
+ INSN_TICK (x) = INVALID_TICK;
+ }
+ free_INSN_LIST_list (&insn_queue[q]);
+ }
+
+ free (ready.vec);
+ ready = save->ready;
+
+ if (ready.n_ready > 0)
+ {
+ rtx *first = ready_lastpos (&ready);
+ for (i = 0; i < ready.n_ready; i++)
+ {
+ rtx insn = first[i];
+ QUEUE_INDEX (insn) = QUEUE_READY;
+ TODO_SPEC (insn) = recompute_todo_spec (insn);
+ INSN_TICK (insn) = save->clock_var;
+ }
+ }
+
+ q_ptr = 0;
+ q_size = save->q_size;
+ for (i = 0; i <= max_insn_queue_index; i++)
+ {
+ int q = NEXT_Q_AFTER (q_ptr, i);
+
+ insn_queue[q] = save->insn_queue[q];
+
+ for (link = insn_queue[q]; link; link = XEXP (link, 1))
+ {
+ rtx x = XEXP (link, 0);
+ QUEUE_INDEX (x) = i;
+ TODO_SPEC (x) = recompute_todo_spec (x);
+ INSN_TICK (x) = save->clock_var + i;
+ }
+ }
+ free (save->insn_queue);
+
+ toggle_cancelled_flags (true);
+
+ clock_var = save->clock_var;
+ last_clock_var = save->last_clock_var;
+ cycle_issued_insns = save->cycle_issued_insns;
+ last_scheduled_insn = save->last_scheduled_insn;
+ last_nondebug_scheduled_insn = save->last_nondebug_scheduled_insn;
+
+ *psched_block = save->sched_block;
+
+ memcpy (curr_state, save->curr_state, dfa_state_size);
+ free (save->curr_state);
+
+ mark_backtrack_feeds (save->delay_pair->i2, 0);
+
+ free (save);
+
+ for (save = backtrack_queue; save; save = save->next)
+ {
+ mark_backtrack_feeds (save->delay_pair->i2, 1);
+ }
+}
+
+/* Discard all data associated with the topmost entry in the backtrack
+ queue. If RESET_TICK is false, we just want to free the data. If true,
+ we are doing this because we discovered a reason to backtrack. In the
+ latter case, also reset the INSN_TICK for the shadow insn. */
+static void
+free_topmost_backtrack_point (bool reset_tick)
+{
+ struct haifa_saved_data *save = backtrack_queue;
+ int i;
+
+ backtrack_queue = save->next;
+
+ if (reset_tick)
+ {
+ struct delay_pair *pair = save->delay_pair;
+ while (pair)
+ {
+ INSN_TICK (pair->i2) = INVALID_TICK;
+ INSN_EXACT_TICK (pair->i2) = INVALID_TICK;
+ pair = pair->next_same_i1;
+ }
+ }
+ if (targetm.sched.free_sched_context)
+ targetm.sched.free_sched_context (save->be_saved_data);
+ if (current_sched_info->restore_state)
+ free (save->fe_saved_data);
+ for (i = 0; i <= max_insn_queue_index; i++)
+ free_INSN_LIST_list (&save->insn_queue[i]);
+ free (save->insn_queue);
+ free (save->curr_state);
+ free (save->ready.vec);
+ free (save);
+}
+
+/* Free the entire backtrack queue. */
+static void
+free_backtrack_queue (void)
+{
+ while (backtrack_queue)
+ free_topmost_backtrack_point (false);
+}
+
+/* Compute INSN_TICK_ESTIMATE for INSN. PROCESSED is a bitmap of
+ instructions we've previously encountered, a set bit prevents
+ recursion. BUDGET is a limit on how far ahead we look, it is
+ reduced on recursive calls. Return true if we produced a good
+ estimate, or false if we exceeded the budget. */
+static bool
+estimate_insn_tick (bitmap processed, rtx insn, int budget)
+{
+ sd_iterator_def sd_it;
+ dep_t dep;
+ int earliest = INSN_TICK (insn);
+
+ FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
+ {
+ rtx pro = DEP_PRO (dep);
+ int t;
+
+ if (DEP_STATUS (dep) & DEP_CANCELLED)
+ continue;
+
+ if (QUEUE_INDEX (pro) == QUEUE_SCHEDULED)
+ gcc_assert (INSN_TICK (pro) + dep_cost (dep) <= INSN_TICK (insn));
+ else
+ {
+ int cost = dep_cost (dep);
+ if (cost >= budget)
+ return false;
+ if (!bitmap_bit_p (processed, INSN_LUID (pro)))
+ {
+ if (!estimate_insn_tick (processed, pro, budget - cost))
+ return false;
+ }
+ gcc_assert (INSN_TICK_ESTIMATE (pro) != INVALID_TICK);
+ t = INSN_TICK_ESTIMATE (pro) + cost;
+ if (earliest == INVALID_TICK || t > earliest)
+ earliest = t;
+ }
+ }
+ bitmap_set_bit (processed, INSN_LUID (insn));
+ INSN_TICK_ESTIMATE (insn) = earliest;
+ return true;
+}
+
+/* Examine the pair of insns in P, and estimate (optimistically, assuming
+ infinite resources) the cycle in which the delayed shadow can be issued.
+ Return the number of cycles that must pass before the real insn can be
+ issued in order to meet this constraint. */
+static int
+estimate_shadow_tick (struct delay_pair *p)
+{
+ bitmap_head processed;
+ int t;
+ bool cutoff;
+ bitmap_initialize (&processed, 0);
+
+ cutoff = !estimate_insn_tick (&processed, p->i2,
+ max_insn_queue_index + pair_delay (p));
+ bitmap_clear (&processed);
+ if (cutoff)
+ return max_insn_queue_index;
+ t = INSN_TICK_ESTIMATE (p->i2) - (clock_var + pair_delay (p) + 1);
+ if (t > 0)
+ return t;
+ return 0;
+}
+
+/* If INSN has no unresolved backwards dependencies, add it to the schedule and
+ recursively resolve all its forward dependencies. */
+static void
+resolve_dependencies (rtx insn)
+{
+ sd_iterator_def sd_it;
+ dep_t dep;
+
+ /* Don't use sd_lists_empty_p; it ignores debug insns. */
+ if (DEPS_LIST_FIRST (INSN_HARD_BACK_DEPS (insn)) != NULL
+ || DEPS_LIST_FIRST (INSN_SPEC_BACK_DEPS (insn)) != NULL)
return;
- next_tail = NEXT_INSN (tail);
- for (insn = head; insn != next_tail; insn = next)
- {
- next = NEXT_INSN (insn);
- if (!NOTE_P (insn))
- continue;
+ if (sched_verbose >= 4)
+ fprintf (sched_dump, ";;\tquickly resolving %d\n", INSN_UID (insn));
- switch (NOTE_KIND (insn))
- {
- case NOTE_INSN_BASIC_BLOCK:
- continue;
+ if (QUEUE_INDEX (insn) >= 0)
+ queue_remove (insn);
- case NOTE_INSN_EPILOGUE_BEG:
- if (insn != tail)
- {
- remove_insn (insn);
- add_reg_note (next, REG_SAVE_NOTE,
- GEN_INT (NOTE_INSN_EPILOGUE_BEG));
- break;
- }
- /* FALLTHRU */
+ VEC_safe_push (rtx, heap, scheduled_insns, insn);
- default:
- remove_insn (insn);
+ /* Update dependent instructions. */
+ for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
+ sd_iterator_cond (&sd_it, &dep);)
+ {
+ rtx next = DEP_CON (dep);
- /* Add the note to list that ends at NOTE_LIST. */
- PREV_INSN (insn) = note_list;
- NEXT_INSN (insn) = NULL_RTX;
- if (note_list)
- NEXT_INSN (note_list) = insn;
- note_list = insn;
- break;
- }
+ if (sched_verbose >= 4)
+ fprintf (sched_dump, ";;\t\tdep %d against %d\n", INSN_UID (insn),
+ INSN_UID (next));
- gcc_assert ((sel_sched_p () || insn != tail) && insn != head);
+ /* Resolve the dependence between INSN and NEXT.
+ sd_resolve_dep () moves current dep to another list thus
+ advancing the iterator. */
+ sd_resolve_dep (sd_it);
+
+ if (!IS_SPECULATION_BRANCHY_CHECK_P (insn))
+ {
+ resolve_dependencies (next);
+ }
+ else
+ /* Check always has only one forward dependence (to the first insn in
+ the recovery block), therefore, this will be executed only once. */
+ {
+ gcc_assert (sd_lists_empty_p (insn, SD_LIST_FORW));
+ }
}
}
fprintf (sched_dump, "reorder %i\n", INSN_UID (note));
reorder_insns_nobb (note, note, PREV_INSN (beg_head));
+
+ if (BLOCK_FOR_INSN (note) != beg)
+ df_insn_change_bb (note, beg);
}
else if (!DEBUG_INSN_P (note))
break;
reorder_insns_nobb (note, note, end_tail);
if (end_tail == BB_END (end))
- df_insn_change_bb (note, NULL);
+ BB_END (end) = note;
+
+ if (BLOCK_FOR_INSN (note) != end)
+ df_insn_change_bb (note, end);
}
else if (!DEBUG_INSN_P (note))
break;
q_ptr = NEXT_Q (q_ptr);
if (dbg_cnt (sched_insn) == false)
- /* If debug counter is activated do not requeue insn next after
- last_scheduled_insn. */
- skip_insn = next_nonnote_nondebug_insn (last_scheduled_insn);
+ {
+ /* If debug counter is activated do not requeue the first
+ nonscheduled insn. */
+ skip_insn = nonscheduled_insns_begin;
+ do
+ {
+ skip_insn = next_nonnote_nondebug_insn (skip_insn);
+ }
+ while (QUEUE_INDEX (skip_insn) == QUEUE_SCHEDULED);
+ }
else
skip_insn = NULL_RTX;
/* If the ready list is full, delay the insn for 1 cycle.
See the comment in schedule_block for the rationale. */
if (!reload_completed
- && ready->n_ready - ready->n_debug > MAX_SCHED_READY_INSNS
+ && (ready->n_ready - ready->n_debug > MAX_SCHED_READY_INSNS
+ || (sched_pressure == SCHED_PRESSURE_MODEL
+ /* Limit pressure recalculations to MAX_SCHED_READY_INSNS
+ instructions too. */
+ && model_index (insn) > (model_curr_point
+ + MAX_SCHED_READY_INSNS)))
+ && !(sched_pressure == SCHED_PRESSURE_MODEL
+ && model_curr_point < model_num_insns
+ /* Always allow the next model instruction to issue. */
+ && model_index (insn) == model_curr_point)
&& !SCHED_GROUP_P (insn)
&& insn != skip_insn)
- {
- if (sched_verbose >= 2)
- fprintf (sched_dump, "requeued because ready full\n");
- queue_insn (insn, 1);
- }
+ queue_insn (insn, 1, "ready full");
else
{
ready_add (ready, insn, false);
static bool
ok_for_early_queue_removal (rtx insn)
{
- int n_cycles;
- rtx prev_insn = last_scheduled_insn;
-
if (targetm.sched.is_costly_dependence)
{
+ rtx prev_insn;
+ int n_cycles;
+ int i = VEC_length (rtx, scheduled_insns);
for (n_cycles = flag_sched_stalled_insns_dep; n_cycles; n_cycles--)
{
- for ( ; prev_insn; prev_insn = PREV_INSN (prev_insn))
+ while (i-- > 0)
{
int cost;
- if (prev_insn == current_sched_info->prev_head)
- {
- prev_insn = NULL;
- break;
- }
+ prev_insn = VEC_index (rtx, scheduled_insns, i);
if (!NOTE_P (prev_insn))
{
break;
}
- if (!prev_insn)
+ if (i == 0)
break;
- prev_insn = PREV_INSN (prev_insn);
}
}
fprintf (sched_dump, " %s:%d",
(*current_sched_info->print_insn) (p[i], 0),
INSN_LUID (p[i]));
- if (sched_pressure_p)
+ if (sched_pressure != SCHED_PRESSURE_NONE)
fprintf (sched_dump, "(cost=%d",
INSN_REG_PRESSURE_EXCESS_COST_CHANGE (p[i]));
if (INSN_TICK (p[i]) > clock_var)
fprintf (sched_dump, ":delay=%d", INSN_TICK (p[i]) - clock_var);
- if (sched_pressure_p)
+ if (sched_pressure != SCHED_PRESSURE_NONE)
fprintf (sched_dump, ")");
}
fprintf (sched_dump, "\n");
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. */
-int cycle_issued_insns;
-
/* This holds the value of the target dfa_lookahead hook. */
int dfa_lookahead;
{
n = privileged_n;
/* Try to find issued privileged insn. */
- while (n && !ready_try[--n]);
+ while (n && !ready_try[--n])
+ ;
}
if (/* If all insns are equally good... */
{
if (state_dead_lock_p (state)
|| insn_finishes_cycle_p (insn))
- /* We won't issue any more instructions in the next
- choice_state. */
+ /* We won't issue any more instructions in the next
+ choice_state. */
top->rest = 0;
else
top->rest--;
if (dbg_cnt (sched_insn) == false)
{
- rtx insn;
-
- insn = next_nonnote_insn (last_scheduled_insn);
+ rtx insn = nonscheduled_insns_begin;
+ do
+ {
+ insn = next_nonnote_insn (insn);
+ }
+ while (QUEUE_INDEX (insn) == QUEUE_SCHEDULED);
if (QUEUE_INDEX (insn) == QUEUE_READY)
/* INSN is in the ready_list. */
{
+ nonscheduled_insns_begin = insn;
ready_remove_insn (insn);
*insn_ptr = insn;
return 0;
}
}
+/* This function is called when we have successfully scheduled a
+ block. It uses the schedule stored in the scheduled_insns vector
+ to rearrange the RTL. PREV_HEAD is used as the anchor to which we
+ append the scheduled insns; TAIL is the insn after the scheduled
+ block. TARGET_BB is the argument passed to schedule_block. */
+
+static void
+commit_schedule (rtx prev_head, rtx tail, basic_block *target_bb)
+{
+ unsigned int i;
+ rtx insn;
+
+ last_scheduled_insn = prev_head;
+ for (i = 0;
+ VEC_iterate (rtx, scheduled_insns, i, insn);
+ i++)
+ {
+ if (control_flow_insn_p (last_scheduled_insn)
+ || current_sched_info->advance_target_bb (*target_bb, insn))
+ {
+ *target_bb = current_sched_info->advance_target_bb (*target_bb, 0);
+
+ if (sched_verbose)
+ {
+ rtx x;
+
+ x = next_real_insn (last_scheduled_insn);
+ gcc_assert (x);
+ dump_new_block_header (1, *target_bb, x, tail);
+ }
+
+ last_scheduled_insn = bb_note (*target_bb);
+ }
+
+ if (current_sched_info->begin_move_insn)
+ (*current_sched_info->begin_move_insn) (insn, last_scheduled_insn);
+ move_insn (insn, last_scheduled_insn,
+ current_sched_info->next_tail);
+ if (!DEBUG_INSN_P (insn))
+ reemit_notes (insn);
+ last_scheduled_insn = insn;
+ }
+
+ VEC_truncate (rtx, scheduled_insns, 0);
+}
+
+/* Examine all insns on the ready list and queue those which can't be
+ issued in this cycle. TEMP_STATE is temporary scheduler state we
+ can use as scratch space. If FIRST_CYCLE_INSN_P is true, no insns
+ have been issued for the current cycle, which means it is valid to
+ issue an asm statement.
+
+ If SHADOWS_ONLY_P is true, we eliminate all real insns and only
+ leave those for which SHADOW_P is true. If MODULO_EPILOGUE is true,
+ we only leave insns which have an INSN_EXACT_TICK. */
+
+static void
+prune_ready_list (state_t temp_state, bool first_cycle_insn_p,
+ bool shadows_only_p, bool modulo_epilogue_p)
+{
+ int i, pass;
+ bool sched_group_found = false;
+ int min_cost_group = 1;
+
+ for (i = 0; i < ready.n_ready; i++)
+ {
+ rtx insn = ready_element (&ready, i);
+ if (SCHED_GROUP_P (insn))
+ {
+ sched_group_found = true;
+ break;
+ }
+ }
+
+ /* Make two passes if there's a SCHED_GROUP_P insn; make sure to handle
+ such an insn first and note its cost, then schedule all other insns
+ for one cycle later. */
+ for (pass = sched_group_found ? 0 : 1; pass < 2; )
+ {
+ int n = ready.n_ready;
+ for (i = 0; i < n; i++)
+ {
+ rtx insn = ready_element (&ready, i);
+ int cost = 0;
+ const char *reason = "resource conflict";
+
+ if (DEBUG_INSN_P (insn))
+ continue;
+
+ if (sched_group_found && !SCHED_GROUP_P (insn))
+ {
+ if (pass == 0)
+ continue;
+ cost = min_cost_group;
+ reason = "not in sched group";
+ }
+ else if (modulo_epilogue_p
+ && INSN_EXACT_TICK (insn) == INVALID_TICK)
+ {
+ cost = max_insn_queue_index;
+ reason = "not an epilogue insn";
+ }
+ else if (shadows_only_p && !SHADOW_P (insn))
+ {
+ cost = 1;
+ reason = "not a shadow";
+ }
+ else if (recog_memoized (insn) < 0)
+ {
+ if (!first_cycle_insn_p
+ && (GET_CODE (PATTERN (insn)) == ASM_INPUT
+ || asm_noperands (PATTERN (insn)) >= 0))
+ cost = 1;
+ reason = "asm";
+ }
+ else if (sched_pressure != SCHED_PRESSURE_NONE)
+ {
+ if (sched_pressure == SCHED_PRESSURE_MODEL
+ && INSN_TICK (insn) <= clock_var)
+ {
+ memcpy (temp_state, curr_state, dfa_state_size);
+ if (state_transition (temp_state, insn) >= 0)
+ INSN_TICK (insn) = clock_var + 1;
+ }
+ cost = 0;
+ }
+ else
+ {
+ int delay_cost = 0;
+
+ if (delay_htab)
+ {
+ struct delay_pair *delay_entry;
+ delay_entry
+ = (struct delay_pair *)htab_find_with_hash (delay_htab, insn,
+ htab_hash_pointer (insn));
+ while (delay_entry && delay_cost == 0)
+ {
+ delay_cost = estimate_shadow_tick (delay_entry);
+ if (delay_cost > max_insn_queue_index)
+ delay_cost = max_insn_queue_index;
+ delay_entry = delay_entry->next_same_i1;
+ }
+ }
+
+ memcpy (temp_state, curr_state, dfa_state_size);
+ cost = state_transition (temp_state, insn);
+ if (cost < 0)
+ cost = 0;
+ else if (cost == 0)
+ cost = 1;
+ if (cost < delay_cost)
+ {
+ cost = delay_cost;
+ reason = "shadow tick";
+ }
+ }
+ if (cost >= 1)
+ {
+ if (SCHED_GROUP_P (insn) && cost > min_cost_group)
+ min_cost_group = cost;
+ ready_remove (&ready, i);
+ queue_insn (insn, cost, reason);
+ if (i + 1 < n)
+ break;
+ }
+ }
+ if (i == n)
+ pass++;
+ }
+}
+
+/* Called when we detect that the schedule is impossible. We examine the
+ backtrack queue to find the earliest insn that caused this condition. */
+
+static struct haifa_saved_data *
+verify_shadows (void)
+{
+ struct haifa_saved_data *save, *earliest_fail = NULL;
+ for (save = backtrack_queue; save; save = save->next)
+ {
+ int t;
+ struct delay_pair *pair = save->delay_pair;
+ rtx i1 = pair->i1;
+
+ for (; pair; pair = pair->next_same_i1)
+ {
+ rtx i2 = pair->i2;
+
+ if (QUEUE_INDEX (i2) == QUEUE_SCHEDULED)
+ continue;
+
+ t = INSN_TICK (i1) + pair_delay (pair);
+ if (t < clock_var)
+ {
+ if (sched_verbose >= 2)
+ fprintf (sched_dump,
+ ";;\t\tfailed delay requirements for %d/%d (%d->%d)"
+ ", not ready\n",
+ INSN_UID (pair->i1), INSN_UID (pair->i2),
+ INSN_TICK (pair->i1), INSN_EXACT_TICK (pair->i2));
+ earliest_fail = save;
+ break;
+ }
+ if (QUEUE_INDEX (i2) >= 0)
+ {
+ int queued_for = INSN_TICK (i2);
+
+ if (t < queued_for)
+ {
+ if (sched_verbose >= 2)
+ fprintf (sched_dump,
+ ";;\t\tfailed delay requirements for %d/%d"
+ " (%d->%d), queued too late\n",
+ INSN_UID (pair->i1), INSN_UID (pair->i2),
+ INSN_TICK (pair->i1), INSN_EXACT_TICK (pair->i2));
+ earliest_fail = save;
+ break;
+ }
+ }
+ }
+ }
+
+ return earliest_fail;
+}
+
/* Use forward list scheduling to rearrange insns of block pointed to by
TARGET_BB, possibly bringing insns from subsequent blocks in the same
region. */
-void
+bool
schedule_block (basic_block *target_bb)
{
int i;
- bool first_cycle_insn_p;
- int can_issue_more;
+ bool success = modulo_ii == 0;
+ struct sched_block_state ls;
state_t temp_state = NULL; /* It is used for multipass scheduling. */
int sort_p, advance, start_clock_var;
haifa_recovery_bb_recently_added_p = false;
+ backtrack_queue = NULL;
+
/* Debug info. */
if (sched_verbose)
dump_new_block_header (0, *target_bb, head, tail);
targetm.sched.init (sched_dump, sched_verbose, ready.veclen);
/* We start inserting insns after PREV_HEAD. */
- last_scheduled_insn = prev_head;
+ last_scheduled_insn = nonscheduled_insns_begin = prev_head;
+ last_nondebug_scheduled_insn = NULL_RTX;
gcc_assert ((NOTE_P (last_scheduled_insn)
|| DEBUG_INSN_P (last_scheduled_insn))
in try_ready () (which is called through init_ready_list ()). */
(*current_sched_info->init_ready_list) ();
+ if (sched_pressure == SCHED_PRESSURE_MODEL)
+ model_start_schedule ();
+
/* The algorithm is O(n^2) in the number of ready insns at any given
time in the worst case. Before reload we are more likely to have
big lists so truncate them to a reasonable size. */
/* Delay all insns past it for 1 cycle. If debug counter is
activated make an exception for the insn right after
- last_scheduled_insn. */
+ nonscheduled_insns_begin. */
{
rtx skip_insn;
if (dbg_cnt (sched_insn) == false)
- skip_insn = next_nonnote_insn (last_scheduled_insn);
+ skip_insn = next_nonnote_insn (nonscheduled_insns_begin);
else
skip_insn = NULL_RTX;
insn = ready_remove (&ready, i);
if (insn != skip_insn)
- queue_insn (insn, 1);
+ queue_insn (insn, 1, "list truncated");
}
+ if (skip_insn)
+ ready_add (&ready, skip_insn, true);
}
}
advance = 0;
+ gcc_assert (VEC_length (rtx, scheduled_insns) == 0);
sort_p = TRUE;
+ must_backtrack = false;
+ modulo_insns_scheduled = 0;
+
+ ls.modulo_epilogue = false;
+
/* Loop until all the insns in BB are scheduled. */
while ((*current_sched_info->schedule_more_p) ())
{
}
while (advance > 0);
- if (sort_p)
+ if (ls.modulo_epilogue)
{
- /* Sort the ready list based on priority. */
- ready_sort (&ready);
-
- if (sched_verbose >= 2)
+ int stage = clock_var / modulo_ii;
+ if (stage > modulo_last_stage * 2 + 2)
{
- fprintf (sched_dump, ";;\t\tReady list after ready_sort: ");
- debug_ready_list (&ready);
+ if (sched_verbose >= 2)
+ fprintf (sched_dump,
+ ";;\t\tmodulo scheduled succeeded at II %d\n",
+ modulo_ii);
+ success = true;
+ goto end_schedule;
}
}
-
- /* We don't want md sched reorder to even see debug isns, so put
- them out right away. */
- if (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0)))
+ else if (modulo_ii > 0)
{
- if (control_flow_insn_p (last_scheduled_insn))
+ int stage = clock_var / modulo_ii;
+ if (stage > modulo_max_stages)
{
- *target_bb = current_sched_info->advance_target_bb
- (*target_bb, 0);
-
- if (sched_verbose)
- {
- rtx x;
-
- x = next_real_insn (last_scheduled_insn);
- gcc_assert (x);
- dump_new_block_header (1, *target_bb, x, tail);
- }
-
- last_scheduled_insn = bb_note (*target_bb);
+ if (sched_verbose >= 2)
+ fprintf (sched_dump,
+ ";;\t\tfailing schedule due to excessive stages\n");
+ goto end_schedule;
}
-
- while (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0)))
+ if (modulo_n_insns == modulo_insns_scheduled
+ && stage > modulo_last_stage)
{
- rtx insn = ready_remove_first (&ready);
- gcc_assert (DEBUG_INSN_P (insn));
- (*current_sched_info->begin_schedule_ready) (insn,
- last_scheduled_insn);
- move_insn (insn, last_scheduled_insn,
- current_sched_info->next_tail);
- last_scheduled_insn = insn;
- advance = schedule_insn (insn);
- gcc_assert (advance == 0);
- if (ready.n_ready > 0)
- ready_sort (&ready);
+ if (sched_verbose >= 2)
+ fprintf (sched_dump,
+ ";;\t\tfound kernel after %d stages, II %d\n",
+ stage, modulo_ii);
+ ls.modulo_epilogue = true;
}
-
- if (!ready.n_ready)
- continue;
}
- /* Allow the target to reorder the list, typically for
- better instruction bundling. */
- 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;
+ prune_ready_list (temp_state, true, false, ls.modulo_epilogue);
+ if (ready.n_ready == 0)
+ continue;
+ if (must_backtrack)
+ goto do_backtrack;
- first_cycle_insn_p = true;
+ ls.first_cycle_insn_p = true;
+ ls.shadows_only_p = false;
cycle_issued_insns = 0;
+ ls.can_issue_more = issue_rate;
for (;;)
{
rtx insn;
int cost;
- bool asm_p = false;
+ bool asm_p;
+
+ if (sort_p && ready.n_ready > 0)
+ {
+ /* Sort the ready list based on priority. This must be
+ done every iteration through the loop, as schedule_insn
+ may have readied additional insns that will not be
+ sorted correctly. */
+ ready_sort (&ready);
+
+ if (sched_verbose >= 2)
+ {
+ fprintf (sched_dump, ";;\t\tReady list after ready_sort: ");
+ debug_ready_list (&ready);
+ }
+ }
+
+ /* We don't want md sched reorder to even see debug isns, so put
+ them out right away. */
+ if (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0))
+ && (*current_sched_info->schedule_more_p) ())
+ {
+ while (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0)))
+ {
+ rtx insn = ready_remove_first (&ready);
+ gcc_assert (DEBUG_INSN_P (insn));
+ (*current_sched_info->begin_schedule_ready) (insn);
+ VEC_safe_push (rtx, heap, scheduled_insns, insn);
+ last_scheduled_insn = insn;
+ advance = schedule_insn (insn);
+ gcc_assert (advance == 0);
+ if (ready.n_ready > 0)
+ ready_sort (&ready);
+ }
+ }
+
+ if (ls.first_cycle_insn_p && !ready.n_ready)
+ break;
+
+ resume_after_backtrack:
+ /* Allow the target to reorder the list, typically for
+ better instruction bundling. */
+ if (sort_p
+ && (ready.n_ready == 0
+ || !SCHED_GROUP_P (ready_element (&ready, 0))))
+ {
+ if (ls.first_cycle_insn_p && targetm.sched.reorder)
+ ls.can_issue_more
+ = targetm.sched.reorder (sched_dump, sched_verbose,
+ ready_lastpos (&ready),
+ &ready.n_ready, clock_var);
+ else if (!ls.first_cycle_insn_p && targetm.sched.reorder2)
+ ls.can_issue_more
+ = targetm.sched.reorder2 (sched_dump, sched_verbose,
+ ready.n_ready
+ ? ready_lastpos (&ready) : NULL,
+ &ready.n_ready, clock_var);
+ }
+ restart_choose_ready:
if (sched_verbose >= 2)
{
fprintf (sched_dump, ";;\tReady list (t = %3d): ",
clock_var);
debug_ready_list (&ready);
- if (sched_pressure_p)
+ if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
print_curr_reg_pressure ();
}
if (ready.n_ready == 0
- && can_issue_more
+ && ls.can_issue_more
&& reload_completed)
{
/* Allow scheduling insns directly from the queue in case
}
if (ready.n_ready == 0
- || !can_issue_more
+ || !ls.can_issue_more
|| state_dead_lock_p (curr_state)
|| !(*current_sched_info->schedule_more_p) ())
break;
int res;
insn = NULL_RTX;
- res = choose_ready (&ready, first_cycle_insn_p, &insn);
+ res = choose_ready (&ready, ls.first_cycle_insn_p, &insn);
if (res < 0)
/* Finish cycle. */
break;
if (res > 0)
- /* Restart choose_ready (). */
- continue;
+ goto restart_choose_ready;
gcc_assert (insn != NULL_RTX);
}
else
insn = ready_remove_first (&ready);
- if (sched_pressure_p && INSN_TICK (insn) > clock_var)
+ if (sched_pressure != SCHED_PRESSURE_NONE
+ && INSN_TICK (insn) > clock_var)
{
ready_add (&ready, insn, true);
advance = 1;
}
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 tried 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 if (sched_pressure_p)
- 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
&& ! (*current_sched_info->can_schedule_ready_p) (insn))
/* We normally get here only if we don't want to move
insn from the split block. */
{
- TODO_SPEC (insn) = (TODO_SPEC (insn) & ~SPECULATIVE) | HARD_DEP;
- continue;
+ TODO_SPEC (insn) = HARD_DEP;
+ goto restart_choose_ready;
}
- /* DECISION is made. */
-
- if (TODO_SPEC (insn) & SPECULATIVE)
- generate_recovery_code (insn);
-
- if (control_flow_insn_p (last_scheduled_insn)
- /* This is used to switch basic blocks by request
- from scheduler front-end (actually, sched-ebb.c only).
- This is used to process blocks with single fallthru
- edge. If succeeding block has jump, it [jump] will try
- move at the end of current bb, thus corrupting CFG. */
- || current_sched_info->advance_target_bb (*target_bb, insn))
+ if (delay_htab)
{
- *target_bb = current_sched_info->advance_target_bb
- (*target_bb, 0);
-
- if (sched_verbose)
+ /* If this insn is the first part of a delay-slot pair, record a
+ backtrack point. */
+ struct delay_pair *delay_entry;
+ delay_entry
+ = (struct delay_pair *)htab_find_with_hash (delay_htab, insn,
+ htab_hash_pointer (insn));
+ if (delay_entry)
{
- rtx x;
-
- x = next_real_insn (last_scheduled_insn);
- gcc_assert (x);
- dump_new_block_header (1, *target_bb, x, tail);
+ save_backtrack_point (delay_entry, ls);
+ if (sched_verbose >= 2)
+ fprintf (sched_dump, ";;\t\tsaving backtrack point\n");
}
-
- last_scheduled_insn = bb_note (*target_bb);
}
- /* Update counters, etc in the scheduler's front end. */
- (*current_sched_info->begin_schedule_ready) (insn,
- last_scheduled_insn);
+ /* DECISION is made. */
- move_insn (insn, last_scheduled_insn, current_sched_info->next_tail);
+ if (modulo_ii > 0 && INSN_UID (insn) < modulo_iter0_max_uid)
+ {
+ modulo_insns_scheduled++;
+ modulo_last_stage = clock_var / modulo_ii;
+ }
+ if (TODO_SPEC (insn) & SPECULATIVE)
+ generate_recovery_code (insn);
if (targetm.sched.dispatch (NULL_RTX, IS_DISPATCH_ON))
targetm.sched.dispatch_do (insn, ADD_TO_DISPATCH_WINDOW);
- reemit_notes (insn);
- last_scheduled_insn = insn;
+ /* Update counters, etc in the scheduler's front end. */
+ (*current_sched_info->begin_schedule_ready) (insn);
+ VEC_safe_push (rtx, heap, scheduled_insns, insn);
+ gcc_assert (NONDEBUG_INSN_P (insn));
+ last_nondebug_scheduled_insn = last_scheduled_insn = insn;
- if (memcmp (curr_state, temp_state, dfa_state_size) != 0)
- {
- cycle_issued_insns++;
- memcpy (curr_state, temp_state, dfa_state_size);
- }
+ if (recog_memoized (insn) >= 0)
+ {
+ memcpy (temp_state, curr_state, dfa_state_size);
+ cost = state_transition (curr_state, insn);
+ if (sched_pressure != SCHED_PRESSURE_WEIGHTED)
+ gcc_assert (cost < 0);
+ if (memcmp (temp_state, curr_state, dfa_state_size) != 0)
+ cycle_issued_insns++;
+ asm_p = false;
+ }
+ else
+ asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT
+ || asm_noperands (PATTERN (insn)) >= 0);
if (targetm.sched.variable_issue)
- can_issue_more =
+ ls.can_issue_more =
targetm.sched.variable_issue (sched_dump, sched_verbose,
- insn, can_issue_more);
+ insn, ls.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--;
+ ls.can_issue_more--;
advance = schedule_insn (insn);
+ if (SHADOW_P (insn))
+ ls.shadows_only_p = true;
+
/* After issuing an asm insn we should start a new cycle. */
if (advance == 0 && asm_p)
advance = 1;
- if (advance != 0)
+
+ if (must_backtrack)
break;
- first_cycle_insn_p = false;
+ if (advance != 0)
+ break;
- /* 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. */
+ ls.first_cycle_insn_p = false;
if (ready.n_ready > 0)
- ready_sort (&ready);
+ prune_ready_list (temp_state, false, ls.shadows_only_p,
+ ls.modulo_epilogue);
+ }
- /* Quickly go through debug insns such that md sched
- reorder2 doesn't have to deal with debug insns. */
- if (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0))
- && (*current_sched_info->schedule_more_p) ())
+ do_backtrack:
+ if (!must_backtrack)
+ for (i = 0; i < ready.n_ready; i++)
+ {
+ rtx insn = ready_element (&ready, i);
+ if (INSN_EXACT_TICK (insn) == clock_var)
+ {
+ must_backtrack = true;
+ clock_var++;
+ break;
+ }
+ }
+ if (must_backtrack && modulo_ii > 0)
+ {
+ if (modulo_backtracks_left == 0)
+ goto end_schedule;
+ modulo_backtracks_left--;
+ }
+ while (must_backtrack)
+ {
+ struct haifa_saved_data *failed;
+ rtx failed_insn;
+
+ must_backtrack = false;
+ failed = verify_shadows ();
+ gcc_assert (failed);
+
+ failed_insn = failed->delay_pair->i1;
+ toggle_cancelled_flags (false);
+ unschedule_insns_until (failed_insn);
+ while (failed != backtrack_queue)
+ free_topmost_backtrack_point (true);
+ restore_last_backtrack_point (&ls);
+ if (sched_verbose >= 2)
+ fprintf (sched_dump, ";;\t\trewind to cycle %d\n", clock_var);
+ /* Delay by at least a cycle. This could cause additional
+ backtracking. */
+ queue_insn (failed_insn, 1, "backtracked");
+ advance = 0;
+ if (must_backtrack)
+ continue;
+ if (ready.n_ready > 0)
+ goto resume_after_backtrack;
+ else
{
- if (control_flow_insn_p (last_scheduled_insn))
- {
- *target_bb = current_sched_info->advance_target_bb
- (*target_bb, 0);
-
- if (sched_verbose)
- {
- rtx x;
-
- x = next_real_insn (last_scheduled_insn);
- gcc_assert (x);
- dump_new_block_header (1, *target_bb, x, tail);
- }
-
- last_scheduled_insn = bb_note (*target_bb);
- }
+ if (clock_var == 0 && ls.first_cycle_insn_p)
+ goto end_schedule;
+ advance = 1;
+ break;
+ }
+ }
+ }
+ if (ls.modulo_epilogue)
+ success = true;
+ end_schedule:
+ if (modulo_ii > 0)
+ {
+ /* Once again, debug insn suckiness: they can be on the ready list
+ even if they have unresolved dependencies. To make our view
+ of the world consistent, remove such "ready" insns. */
+ restart_debug_insn_loop:
+ for (i = ready.n_ready - 1; i >= 0; i--)
+ {
+ rtx x;
- while (ready.n_ready && DEBUG_INSN_P (ready_element (&ready, 0)))
- {
- insn = ready_remove_first (&ready);
- gcc_assert (DEBUG_INSN_P (insn));
- (*current_sched_info->begin_schedule_ready)
- (insn, last_scheduled_insn);
- move_insn (insn, last_scheduled_insn,
- current_sched_info->next_tail);
- advance = schedule_insn (insn);
- last_scheduled_insn = insn;
- gcc_assert (advance == 0);
- if (ready.n_ready > 0)
- ready_sort (&ready);
- }
+ x = ready_element (&ready, i);
+ if (DEPS_LIST_FIRST (INSN_HARD_BACK_DEPS (x)) != NULL
+ || DEPS_LIST_FIRST (INSN_SPEC_BACK_DEPS (x)) != NULL)
+ {
+ ready_remove (&ready, i);
+ goto restart_debug_insn_loop;
}
+ }
+ for (i = ready.n_ready - 1; i >= 0; i--)
+ {
+ rtx x;
- if (targetm.sched.reorder2
- && (ready.n_ready == 0
- || !SCHED_GROUP_P (ready_element (&ready, 0))))
+ x = ready_element (&ready, i);
+ resolve_dependencies (x);
+ }
+ for (i = 0; i <= max_insn_queue_index; i++)
+ {
+ rtx link;
+ while ((link = insn_queue[i]) != NULL)
{
- can_issue_more =
- targetm.sched.reorder2 (sched_dump, sched_verbose,
- ready.n_ready
- ? ready_lastpos (&ready) : NULL,
- &ready.n_ready, clock_var);
+ rtx x = XEXP (link, 0);
+ insn_queue[i] = XEXP (link, 1);
+ QUEUE_INDEX (x) = QUEUE_NOWHERE;
+ free_INSN_LIST_node (link);
+ resolve_dependencies (x);
}
}
}
debug_ready_list (&ready);
}
- if (current_sched_info->queue_must_finish_empty)
+ if (modulo_ii == 0 && current_sched_info->queue_must_finish_empty)
/* Sanity check -- queue must be empty now. Meaningless if region has
multiple bbs. */
gcc_assert (!q_size && !ready.n_ready && !ready.n_debug);
- else
+ else if (modulo_ii == 0)
{
/* We must maintain QUEUE_INDEX between blocks in region. */
for (i = ready.n_ready - 1; i >= 0; i--)
x = ready_element (&ready, i);
QUEUE_INDEX (x) = QUEUE_NOWHERE;
- TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP;
+ TODO_SPEC (x) = HARD_DEP;
}
if (q_size)
x = XEXP (link, 0);
QUEUE_INDEX (x) = QUEUE_NOWHERE;
- TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP;
+ TODO_SPEC (x) = HARD_DEP;
}
free_INSN_LIST_list (&insn_queue[i]);
}
}
- if (sched_verbose)
- fprintf (sched_dump, ";; total time = %d\n", clock_var);
+ if (sched_pressure == SCHED_PRESSURE_MODEL)
+ model_end_schedule ();
+
+ if (success)
+ {
+ commit_schedule (prev_head, tail, target_bb);
+ if (sched_verbose)
+ fprintf (sched_dump, ";; total time = %d\n", clock_var);
+ }
+ else
+ last_scheduled_insn = tail;
+
+ VEC_truncate (rtx, scheduled_insns, 0);
if (!current_sched_info->queue_must_finish_empty
|| haifa_recovery_bb_recently_added_p)
in its md_finish () hook. These new insns don't have any data
initialized and to identify them we extend h_i_d so that they'll
get zero luids. */
- sched_init_luids (NULL, NULL, NULL, NULL);
+ sched_extend_luids ();
}
if (sched_verbose)
current_sched_info->head = head;
current_sched_info->tail = tail;
+
+ free_backtrack_queue ();
+
+ return success;
}
\f
/* Set_priorities: compute priority of each insn in the block. */
if (targetm.sched.dispatch (NULL_RTX, IS_DISPATCH_ON))
targetm.sched.dispatch_do (NULL_RTX, DISPATCH_INIT);
- sched_pressure_p = (flag_sched_pressure && ! reload_completed
- && common_sched_info->sched_pass_id == SCHED_RGN_PASS);
+ if (flag_sched_pressure
+ && !reload_completed
+ && common_sched_info->sched_pass_id == SCHED_RGN_PASS)
+ sched_pressure = flag_sched_pressure_algorithm;
+ else
+ sched_pressure = SCHED_PRESSURE_NONE;
- if (sched_pressure_p)
+ if (sched_pressure != SCHED_PRESSURE_NONE)
ira_setup_eliminable_regset ();
/* Initialize SPEC_INFO. */
init_alias_analysis ();
- df_set_flags (DF_LR_RUN_DCE);
+ if (!sched_no_dce)
+ df_set_flags (DF_LR_RUN_DCE);
df_note_add_problem ();
/* More problems needed for interloop dep calculation in SMS. */
if (targetm.sched.init_global)
targetm.sched.init_global (sched_dump, sched_verbose, get_max_uid () + 1);
- if (sched_pressure_p)
+ if (sched_pressure != SCHED_PRESSURE_NONE)
{
int i, max_regno = max_reg_num ();
+ if (sched_dump != NULL)
+ /* We need info about pseudos for rtl dumps about pseudo
+ classes and costs. */
+ regstat_init_n_sets_and_refs ();
ira_set_pseudo_classes (sched_verbose ? sched_dump : NULL);
- sched_regno_cover_class
+ sched_regno_pressure_class
= (enum reg_class *) xmalloc (max_regno * sizeof (enum reg_class));
for (i = 0; i < max_regno; i++)
- sched_regno_cover_class[i]
+ sched_regno_pressure_class[i]
= (i < FIRST_PSEUDO_REGISTER
- ? ira_class_translate[REGNO_REG_CLASS (i)]
- : reg_cover_class (i));
+ ? ira_pressure_class_translate[REGNO_REG_CLASS (i)]
+ : ira_pressure_class_translate[reg_allocno_class (i)]);
curr_reg_live = BITMAP_ALLOC (NULL);
- saved_reg_live = BITMAP_ALLOC (NULL);
- region_ref_regs = BITMAP_ALLOC (NULL);
+ if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
+ {
+ saved_reg_live = BITMAP_ALLOC (NULL);
+ region_ref_regs = BITMAP_ALLOC (NULL);
+ }
}
curr_state = xmalloc (dfa_state_size);
setup_sched_dump ();
sched_init ();
+ scheduled_insns = VEC_alloc (rtx, heap, 0);
+
if (spec_info != NULL)
{
sched_deps_info->use_deps_list = 1;
FOR_EACH_BB (bb)
VEC_quick_push (basic_block, bbs, bb);
- sched_init_luids (bbs, NULL, NULL, NULL);
+ sched_init_luids (bbs);
sched_deps_init (true);
sched_extend_target ();
- haifa_init_h_i_d (bbs, NULL, NULL, NULL);
+ haifa_init_h_i_d (bbs);
VEC_free (basic_block, heap, bbs);
}
sched_create_empty_bb = sched_create_empty_bb_1;
haifa_recovery_bb_ever_added_p = false;
-#ifdef ENABLE_CHECKING
- /* This is used preferably for finding bugs in check_cfg () itself.
- We must call sched_bbs_init () before check_cfg () because check_cfg ()
- assumes that the last insn in the last bb has a non-null successor. */
- check_cfg (0, 0);
-#endif
-
nr_begin_data = nr_begin_control = nr_be_in_data = nr_be_in_control = 0;
before_recovery = 0;
after_recovery = 0;
+
+ modulo_ii = 0;
}
/* Finish work with the data specific to the Haifa scheduler. */
c, nr_be_in_control);
}
+ VEC_free (rtx, heap, scheduled_insns);
+
/* Finalize h_i_d, dependency caches, and luids for the whole
function. Target will be finalized in md_global_finish (). */
sched_deps_finish ();
sched_finish (void)
{
haifa_finish_h_i_d ();
- if (sched_pressure_p)
+ if (sched_pressure != SCHED_PRESSURE_NONE)
{
- free (sched_regno_cover_class);
- BITMAP_FREE (region_ref_regs);
- BITMAP_FREE (saved_reg_live);
+ if (regstat_n_sets_and_refs != NULL)
+ regstat_free_n_sets_and_refs ();
+ if (sched_pressure == SCHED_PRESSURE_WEIGHTED)
+ {
+ BITMAP_FREE (region_ref_regs);
+ BITMAP_FREE (saved_reg_live);
+ }
BITMAP_FREE (curr_reg_live);
+ free (sched_regno_pressure_class);
}
free (curr_state);
regstat_free_calls_crossed ();
dfa_finish ();
+}
-#ifdef ENABLE_CHECKING
- /* After reload ia64 backend clobbers CFG, so can't check anything. */
- if (!reload_completed)
- check_cfg (0, 0);
-#endif
+/* Free all delay_pair structures that were recorded. */
+void
+free_delay_pairs (void)
+{
+ if (delay_htab)
+ {
+ htab_empty (delay_htab);
+ htab_empty (delay_htab_i2);
+ }
}
/* Fix INSN_TICKs of the instructions in the current block as well as
bitmap_clear (&processed);
}
-static int haifa_speculate_insn (rtx, ds_t, rtx *);
-
/* Check if NEXT is ready to be added to the ready or queue list.
If "yes", add it to the proper list.
Returns:
int
try_ready (rtx next)
{
- ds_t old_ts, *ts;
+ ds_t old_ts, new_ts;
- ts = &TODO_SPEC (next);
- old_ts = *ts;
+ old_ts = TODO_SPEC (next);
- gcc_assert (!(old_ts & ~(SPECULATIVE | HARD_DEP))
+ gcc_assert (!(old_ts & ~(SPECULATIVE | HARD_DEP | DEP_CONTROL))
&& ((old_ts & HARD_DEP)
- || (old_ts & SPECULATIVE)));
-
- if (sd_lists_empty_p (next, SD_LIST_BACK))
- /* NEXT has all its dependencies resolved. */
- {
- /* Remove HARD_DEP bit from NEXT's status. */
- *ts &= ~HARD_DEP;
-
- if (current_sched_info->flags & DO_SPECULATION)
- /* Remove all speculative bits from NEXT's status. */
- *ts &= ~SPECULATIVE;
- }
- else
- {
- /* One of the NEXT's dependencies has been resolved.
- Recalculate NEXT's status. */
-
- *ts &= ~SPECULATIVE & ~HARD_DEP;
+ || (old_ts & SPECULATIVE)
+ || (old_ts & DEP_CONTROL)));
- if (sd_lists_empty_p (next, SD_LIST_HARD_BACK))
- /* Now we've got NEXT with speculative deps only.
- 1. Look at the deps to see what we have to do.
- 2. Check if we can do 'todo'. */
- {
- sd_iterator_def sd_it;
- dep_t dep;
- bool first_p = true;
-
- FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep)
- {
- ds_t ds = DEP_STATUS (dep) & SPECULATIVE;
-
- if (DEBUG_INSN_P (DEP_PRO (dep))
- && !DEBUG_INSN_P (next))
- continue;
-
- if (first_p)
- {
- first_p = false;
-
- *ts = ds;
- }
- else
- *ts = ds_merge (*ts, ds);
- }
-
- if (ds_weak (*ts) < spec_info->data_weakness_cutoff)
- /* Too few points. */
- *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
- }
- else
- *ts |= HARD_DEP;
- }
+ new_ts = recompute_todo_spec (next);
- if (*ts & HARD_DEP)
- gcc_assert (*ts == old_ts
+ if (new_ts & HARD_DEP)
+ gcc_assert (new_ts == old_ts
&& QUEUE_INDEX (next) == QUEUE_NOWHERE);
else if (current_sched_info->new_ready)
- *ts = current_sched_info->new_ready (next, *ts);
+ new_ts = current_sched_info->new_ready (next, new_ts);
/* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
have its original pattern or changed (speculative) one. This is due
* But if (old_ts & SPECULATIVE), then we are pretty sure that insn
has speculative pattern.
- We can't assert (!(*ts & HARD_DEP) || *ts == old_ts) here because
+ We can't assert (!(new_ts & HARD_DEP) || new_ts == old_ts) here because
control-speculative NEXT could have been discarded by sched-rgn.c
(the same case as when discarded by can_schedule_ready_p ()). */
- if ((*ts & SPECULATIVE)
- /* If (old_ts == *ts), then (old_ts & SPECULATIVE) and we don't
+ if ((new_ts & SPECULATIVE)
+ /* If (old_ts == new_ts), then (old_ts & SPECULATIVE) and we don't
need to change anything. */
- && *ts != old_ts)
+ && new_ts != old_ts)
{
int res;
rtx new_pat;
- gcc_assert ((*ts & SPECULATIVE) && !(*ts & ~SPECULATIVE));
+ gcc_assert ((new_ts & SPECULATIVE) && !(new_ts & ~SPECULATIVE));
- res = haifa_speculate_insn (next, *ts, &new_pat);
+ res = haifa_speculate_insn (next, new_ts, &new_pat);
switch (res)
{
case -1:
/* It would be nice to change DEP_STATUS of all dependences,
- which have ((DEP_STATUS & SPECULATIVE) == *ts) to HARD_DEP,
+ which have ((DEP_STATUS & SPECULATIVE) == new_ts) to HARD_DEP,
so we won't reanalyze anything. */
- *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
+ new_ts = HARD_DEP;
break;
case 0:
save it. */
ORIG_PAT (next) = PATTERN (next);
- haifa_change_pattern (next, new_pat);
+ res = haifa_change_pattern (next, new_pat);
+ gcc_assert (res);
break;
default:
}
}
- /* We need to restore pattern only if (*ts == 0), because otherwise it is
- either correct (*ts & SPECULATIVE),
- or we simply don't care (*ts & HARD_DEP). */
+ /* We need to restore pattern only if (new_ts == 0), because otherwise it is
+ either correct (new_ts & SPECULATIVE),
+ or we simply don't care (new_ts & HARD_DEP). */
gcc_assert (!ORIG_PAT (next)
|| !IS_SPECULATION_BRANCHY_CHECK_P (next));
- if (*ts & HARD_DEP)
+ TODO_SPEC (next) = new_ts;
+
+ if (new_ts & HARD_DEP)
{
/* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
control-speculative NEXT could have been discarded by sched-rgn.c
/*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
change_queue_index (next, QUEUE_NOWHERE);
+
return -1;
}
- else if (!(*ts & BEGIN_SPEC) && ORIG_PAT (next) && !IS_SPECULATION_CHECK_P (next))
+ else if (!(new_ts & BEGIN_SPEC)
+ && ORIG_PAT (next) && PREDICATED_PAT (next) == NULL_RTX
+ && !IS_SPECULATION_CHECK_P (next))
/* We should change pattern of every previously speculative
instruction - and we determine if NEXT was speculative by using
ORIG_PAT field. Except one case - speculation checks have ORIG_PAT
pat too, so skip them. */
{
- haifa_change_pattern (next, ORIG_PAT (next));
+ bool success = haifa_change_pattern (next, ORIG_PAT (next));
+ gcc_assert (success);
ORIG_PAT (next) = 0;
}
if (sched_verbose >= 2)
{
- int s = TODO_SPEC (next);
-
fprintf (sched_dump, ";;\t\tdependencies resolved: insn %s",
(*current_sched_info->print_insn) (next, 0));
if (spec_info && spec_info->dump)
{
- if (s & BEGIN_DATA)
+ if (new_ts & BEGIN_DATA)
fprintf (spec_info->dump, "; data-spec;");
- if (s & BEGIN_CONTROL)
+ if (new_ts & BEGIN_CONTROL)
fprintf (spec_info->dump, "; control-spec;");
- if (s & BE_IN_CONTROL)
+ if (new_ts & BE_IN_CONTROL)
fprintf (spec_info->dump, "; in-control-spec;");
}
-
+ if (TODO_SPEC (next) & DEP_CONTROL)
+ fprintf (sched_dump, " predicated");
fprintf (sched_dump, "\n");
}
{
int tick, delay;
- if (!sd_lists_empty_p (next, SD_LIST_RES_BACK))
+ if (!DEBUG_INSN_P (next) && !sd_lists_empty_p (next, SD_LIST_RES_BACK))
{
int full_p;
sd_iterator_def sd_it;
INSN_TICK (next) = tick;
delay = tick - clock_var;
- if (delay <= 0 || sched_pressure_p)
+ if (delay <= 0 || sched_pressure != SCHED_PRESSURE_NONE)
delay = QUEUE_READY;
change_queue_index (next, delay);
if (delay == QUEUE_READY)
ready_add (readyp, next, false);
else if (delay >= 1)
- queue_insn (next, delay);
+ queue_insn (next, delay, "change queue index");
if (sched_verbose >= 2)
{
{
i = 0;
sched_ready_n_insns = 0;
+ VEC_reserve (rtx, heap, scheduled_insns, new_sched_ready_n_insns);
}
else
i = sched_ready_n_insns + 1;
{
/* Rewritten from cfgrtl.c. */
if (flag_reorder_blocks_and_partition
- && targetm.have_named_sections)
+ && targetm_common.have_named_sections)
{
/* We don't need the same note for the check because
any_condjump_p (check) == true. */
add_jump_dependencies (insn, jump);
}
-/* Change pattern of INSN to NEW_PAT. */
-void
-sched_change_pattern (rtx insn, rtx new_pat)
+/* Change pattern of INSN to NEW_PAT. Invalidate cached haifa
+ instruction data. */
+static bool
+haifa_change_pattern (rtx insn, rtx new_pat)
{
+ sd_iterator_def sd_it;
+ dep_t dep;
int t;
t = validate_change (insn, &PATTERN (insn), new_pat, 0);
- gcc_assert (t);
+ if (!t)
+ return false;
dfa_clear_single_insn_cache (insn);
-}
-/* Change pattern of INSN to NEW_PAT. Invalidate cached haifa
- instruction data. */
-static void
-haifa_change_pattern (rtx insn, rtx new_pat)
-{
- sched_change_pattern (insn, new_pat);
+ sd_it = sd_iterator_start (insn,
+ SD_LIST_FORW | SD_LIST_BACK | SD_LIST_RES_BACK);
+ while (sd_iterator_cond (&sd_it, &dep))
+ {
+ DEP_COST (dep) = UNKNOWN_DEP_COST;
+ sd_iterator_next (&sd_it);
+ }
/* Invalidate INSN_COST, so it'll be recalculated. */
INSN_COST (insn) = -1;
/* Invalidate INSN_TICK, so it'll be recalculated. */
INSN_TICK (insn) = INVALID_TICK;
+ return true;
}
/* -1 - can't speculate,
if (insn == jump)
break;
- if (dep_list_size (insn) == 0)
+ if (dep_list_size (insn, SD_LIST_FORW) == 0)
{
dep_def _new_dep, *new_dep = &_new_dep;
gcc_assert (!sd_lists_empty_p (jump, SD_LIST_BACK));
}
-/* Return the NOTE_INSN_BASIC_BLOCK of BB. */
-rtx
-bb_note (basic_block bb)
-{
- rtx note;
-
- note = BB_HEAD (bb);
- if (LABEL_P (note))
- note = NEXT_INSN (note);
-
- gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
- return note;
-}
-
-#ifdef ENABLE_CHECKING
-/* Helper function for check_cfg.
- Return nonzero, if edge vector pointed to by EL has edge with TYPE in
- its flags. */
-static int
-has_edge_p (VEC(edge,gc) *el, int type)
-{
- edge e;
- edge_iterator ei;
-
- FOR_EACH_EDGE (e, ei, el)
- if (e->flags & type)
- return 1;
- return 0;
-}
-
-/* Search back, starting at INSN, for an insn that is not a
- NOTE_INSN_VAR_LOCATION. Don't search beyond HEAD, and return it if
- no such insn can be found. */
-static inline rtx
-prev_non_location_insn (rtx insn, rtx head)
-{
- while (insn != head && NOTE_P (insn)
- && NOTE_KIND (insn) == NOTE_INSN_VAR_LOCATION)
- insn = PREV_INSN (insn);
-
- return insn;
-}
-
-/* Check few properties of CFG between HEAD and TAIL.
- If HEAD (TAIL) is NULL check from the beginning (till the end) of the
- instruction stream. */
-static void
-check_cfg (rtx head, rtx tail)
-{
- rtx next_tail;
- basic_block bb = 0;
- int not_first = 0, not_last;
-
- if (head == NULL)
- head = get_insns ();
- if (tail == NULL)
- tail = get_last_insn ();
- next_tail = NEXT_INSN (tail);
-
- do
- {
- not_last = head != tail;
-
- if (not_first)
- gcc_assert (NEXT_INSN (PREV_INSN (head)) == head);
- if (not_last)
- gcc_assert (PREV_INSN (NEXT_INSN (head)) == head);
-
- if (LABEL_P (head)
- || (NOTE_INSN_BASIC_BLOCK_P (head)
- && (!not_first
- || (not_first && !LABEL_P (PREV_INSN (head))))))
- {
- gcc_assert (bb == 0);
- bb = BLOCK_FOR_INSN (head);
- if (bb != 0)
- gcc_assert (BB_HEAD (bb) == head);
- else
- /* This is the case of jump table. See inside_basic_block_p (). */
- gcc_assert (LABEL_P (head) && !inside_basic_block_p (head));
- }
-
- if (bb == 0)
- {
- gcc_assert (!inside_basic_block_p (head));
- head = NEXT_INSN (head);
- }
- else
- {
- gcc_assert (inside_basic_block_p (head)
- || NOTE_P (head));
- gcc_assert (BLOCK_FOR_INSN (head) == bb);
-
- if (LABEL_P (head))
- {
- head = NEXT_INSN (head);
- gcc_assert (NOTE_INSN_BASIC_BLOCK_P (head));
- }
- else
- {
- if (control_flow_insn_p (head))
- {
- gcc_assert (prev_non_location_insn (BB_END (bb), head)
- == head);
-
- if (any_uncondjump_p (head))
- gcc_assert (EDGE_COUNT (bb->succs) == 1
- && BARRIER_P (NEXT_INSN (head)));
- else if (any_condjump_p (head))
- gcc_assert (/* Usual case. */
- (EDGE_COUNT (bb->succs) > 1
- && !BARRIER_P (NEXT_INSN (head)))
- /* Or jump to the next instruction. */
- || (EDGE_COUNT (bb->succs) == 1
- && (BB_HEAD (EDGE_I (bb->succs, 0)->dest)
- == JUMP_LABEL (head))));
- }
- if (BB_END (bb) == head)
- {
- if (EDGE_COUNT (bb->succs) > 1)
- gcc_assert (control_flow_insn_p (prev_non_location_insn
- (head, BB_HEAD (bb)))
- || has_edge_p (bb->succs, EDGE_COMPLEX));
- bb = 0;
- }
-
- head = NEXT_INSN (head);
- }
- }
-
- not_first = 1;
- }
- while (head != next_tail);
-
- gcc_assert (bb == 0);
-}
-
-#endif /* ENABLE_CHECKING */
-
-/* Extend per basic block data structures. */
-static void
-extend_bb (void)
-{
- if (sched_scan_info->extend_bb)
- sched_scan_info->extend_bb ();
-}
-
-/* Init data for BB. */
-static void
-init_bb (basic_block bb)
-{
- if (sched_scan_info->init_bb)
- sched_scan_info->init_bb (bb);
-}
-
-/* Extend per insn data structures. */
-static void
-extend_insn (void)
-{
- if (sched_scan_info->extend_insn)
- sched_scan_info->extend_insn ();
-}
-
-/* Init data structures for INSN. */
-static void
-init_insn (rtx insn)
-{
- if (sched_scan_info->init_insn)
- sched_scan_info->init_insn (insn);
-}
-
-/* Init all insns in BB. */
-static void
-init_insns_in_bb (basic_block bb)
-{
- rtx insn;
-
- FOR_BB_INSNS (bb, insn)
- init_insn (insn);
-}
-
-/* A driver function to add a set of basic blocks (BBS),
- a single basic block (BB), a set of insns (INSNS) or a single insn (INSN)
- to the scheduling region. */
-void
-sched_scan (const struct sched_scan_info_def *ssi,
- bb_vec_t bbs, basic_block bb, insn_vec_t insns, rtx insn)
-{
- sched_scan_info = ssi;
-
- if (bbs != NULL || bb != NULL)
- {
- extend_bb ();
-
- if (bbs != NULL)
- {
- unsigned i;
- basic_block x;
-
- FOR_EACH_VEC_ELT (basic_block, bbs, i, x)
- init_bb (x);
- }
-
- if (bb != NULL)
- init_bb (bb);
- }
-
- extend_insn ();
-
- if (bbs != NULL)
- {
- unsigned i;
- basic_block x;
-
- FOR_EACH_VEC_ELT (basic_block, bbs, i, x)
- init_insns_in_bb (x);
- }
-
- if (bb != NULL)
- init_insns_in_bb (bb);
-
- if (insns != NULL)
- {
- unsigned i;
- rtx x;
-
- FOR_EACH_VEC_ELT (rtx, insns, i, x)
- init_insn (x);
- }
-
- if (insn != NULL)
- init_insn (insn);
-}
-
-
/* Extend data structures for logical insn UID. */
-static void
-luids_extend_insn (void)
+void
+sched_extend_luids (void)
{
int new_luids_max_uid = get_max_uid () + 1;
}
/* Initialize LUID for INSN. */
-static void
-luids_init_insn (rtx insn)
+void
+sched_init_insn_luid (rtx insn)
{
int i = INSN_P (insn) ? 1 : common_sched_info->luid_for_non_insn (insn);
int luid;
SET_INSN_LUID (insn, luid);
}
-/* Initialize luids for BBS, BB, INSNS and INSN.
+/* Initialize luids for BBS.
The hook common_sched_info->luid_for_non_insn () is used to determine
if notes, labels, etc. need luids. */
void
-sched_init_luids (bb_vec_t bbs, basic_block bb, insn_vec_t insns, rtx insn)
+sched_init_luids (bb_vec_t bbs)
{
- const struct sched_scan_info_def ssi =
+ int i;
+ basic_block bb;
+
+ sched_extend_luids ();
+ FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
{
- NULL, /* extend_bb */
- NULL, /* init_bb */
- luids_extend_insn, /* extend_insn */
- luids_init_insn /* init_insn */
- };
+ rtx insn;
- sched_scan (&ssi, bbs, bb, insns, insn);
+ FOR_BB_INSNS (bb, insn)
+ sched_init_insn_luid (insn);
+ }
}
/* Free LUIDs. */
INSN_COST (insn) = -1;
QUEUE_INDEX (insn) = QUEUE_NOWHERE;
INSN_TICK (insn) = INVALID_TICK;
+ INSN_EXACT_TICK (insn) = INVALID_TICK;
INTER_TICK (insn) = INVALID_TICK;
TODO_SPEC (insn) = HARD_DEP;
}
}
-/* Initialize haifa_insn_data for BBS, BB, INSNS and INSN. */
+/* Initialize haifa_insn_data for BBS. */
void
-haifa_init_h_i_d (bb_vec_t bbs, basic_block bb, insn_vec_t insns, rtx insn)
+haifa_init_h_i_d (bb_vec_t bbs)
{
- const struct sched_scan_info_def ssi =
+ int i;
+ basic_block bb;
+
+ extend_h_i_d ();
+ FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
{
- NULL, /* extend_bb */
- NULL, /* init_bb */
- extend_h_i_d, /* extend_insn */
- init_h_i_d /* init_insn */
- };
+ rtx insn;
- sched_scan (&ssi, bbs, bb, insns, insn);
+ FOR_BB_INSNS (bb, insn)
+ init_h_i_d (insn);
+ }
}
/* Finalize haifa_insn_data. */
FOR_EACH_VEC_ELT (haifa_insn_data_def, h_i_d, i, data)
{
- if (data->reg_pressure != NULL)
- free (data->reg_pressure);
+ free (data->max_reg_pressure);
+ free (data->reg_pressure);
for (use = data->reg_use_list; use != NULL; use = next)
{
next = use->next_insn_use;
{
gcc_assert (insn != NULL);
- sched_init_luids (NULL, NULL, NULL, insn);
+ sched_extend_luids ();
+ sched_init_insn_luid (insn);
sched_extend_target ();
sched_deps_init (false);
- haifa_init_h_i_d (NULL, NULL, NULL, insn);
+ extend_h_i_d ();
+ init_h_i_d (insn);
if (adding_bb_to_current_region_p)
{
/* Extend dependency caches by one element. */
extend_dependency_caches (1, false);
}
+ if (sched_pressure != SCHED_PRESSURE_NONE)
+ init_insn_reg_pressure_info (insn);
}
/* Init data for the new basic block BB which comes after AFTER. */
rtx
sched_emit_insn (rtx pat)
{
- rtx insn = emit_insn_after (pat, last_scheduled_insn);
- last_scheduled_insn = insn;
+ rtx insn = emit_insn_before (pat, nonscheduled_insns_begin);
haifa_init_insn (insn);
+
+ if (current_sched_info->add_remove_insn)
+ current_sched_info->add_remove_insn (insn, 0);
+
+ (*current_sched_info->begin_schedule_ready) (insn);
+ VEC_safe_push (rtx, heap, scheduled_insns, insn);
+
+ last_scheduled_insn = insn;
return insn;
}