haifa-sched.c: Include "hashtab.h"

	* haifa-sched.c: Include "hashtab.h"
	(sched_no_dce): New global variable.
	(INSN_EXACT_TICK, INSN_TICK_ESTIMATE, FEEDS_BACKTRACK_INSN,
	SHADOW_P): New macros.
	(last_clock_var, cycle_issued_insns): Move declarations.
	(must_backtrack): New static variable.
	(struct delay_pair): New structure.
	(delay_htab, delay_htab_i2): New static variables.
	(delay_hash_i1, delay_hash_i2, delay_i1_eq, delay_i2_eq,
	record_delay_slot_pair, pair_delay, add_delay_dependencies): New
	functions.
	(dep_cost_1): If delay pairs exist, try to look up the insns and
	use the correct pair delay if we find them.
	(rank-for_schedule): Tweak priority for insns that must be scheduled
	soon to avoid backtracking.
	(queue_insn): Detect conditions which force backtracking.
	(ready_add): Likewise.
	(struct sched_block_state): Add member shadows_only_p.
	(struct haifa_save_data): New structure.
	(backtrack_queue): New static variable.
	(mark_backtrack_feeds, copy_insn_list, save_backtrack_point,
	unschedule_insns_until, restore_last_backtrack_point,
	free_topmost_backtrack_point, free_backtrack_queue,
	estimate_insn_tick, estimate_shadow_tick): New functions.
	(prune_ready_list): New arg shadows_only_p.  All callers changed.
	If true, remove everything that isn't SHADOW_P.  Look up delay
	pairs and estimate ticks to avoid scheduling the first insn too
	early.
	(verify_shadows): New function.
	(schedule_block): Add machinery to enable backtracking.
	(sched_init): Take sched_no_dce into account when setting
	DF_LR_RUN_DCE.
	(free_delay_pairs): New function.
	(init_h_i_d): Initialize INSN_EXACT_TICK.
	* Makefile.in (haifa-sched.o): Add $(HASHTAB_H).
	* sched-deps.c (sd_unresolve_dep): New function.
	* sched-int.h (struct haifa_sched_info): New fields save_state
	and restore_state.
	(struct _haifa_insn_data): New fields exact_tick, tick_estimate,
	feeds_backtrack_insn and shadow_p.
	(DO_BACKTRACKING): New value in enum SCHED_FLAGS.
	(sched_no_dce): Declare variable.
	(record_delay_slot_pair, free_delay_pairs, add_delay_dependencies,
	sd_unresolve_dep): Declare functions.
	* modulo-sched.c (sms_sched_info): Clear the two new fields.
	* sched-rgn.c (rgn_const_sched_info): Likewise.
	* sel-sched-ir.c (sched_sel_haifa_sched_info): Likewise.
	* sched-ebb.c (save_ebb_state, restore_ebb_state): New functions.
	(ebb_sched_info): Add them for the two new fields.
	(add_deps_for_risky_insns): Call add_delay_dependencies.

From-SVN: r176255

9 files changed, 983 insertions, 88 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 157ad42..0f5c3ae3 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,56 @@
+2011-07-14  Bernd Schmidt  <bernds@codesourcery.com>
+
+	* haifa-sched.c: Include "hashtab.h"
+	(sched_no_dce): New global variable.
+	(INSN_EXACT_TICK, INSN_TICK_ESTIMATE, FEEDS_BACKTRACK_INSN,
+	SHADOW_P): New macros.
+	(last_clock_var, cycle_issued_insns): Move declarations.
+	(must_backtrack): New static variable.
+	(struct delay_pair): New structure.
+	(delay_htab, delay_htab_i2): New static variables.
+	(delay_hash_i1, delay_hash_i2, delay_i1_eq, delay_i2_eq,
+	record_delay_slot_pair, pair_delay, add_delay_dependencies): New
+	functions.
+	(dep_cost_1): If delay pairs exist, try to look up the insns and
+	use the correct pair delay if we find them.
+	(rank-for_schedule): Tweak priority for insns that must be scheduled
+	soon to avoid backtracking.
+	(queue_insn): Detect conditions which force backtracking.
+	(ready_add): Likewise.
+	(struct sched_block_state): Add member shadows_only_p.
+	(struct haifa_save_data): New structure.
+	(backtrack_queue): New static variable.
+	(mark_backtrack_feeds, copy_insn_list, save_backtrack_point,
+	unschedule_insns_until, restore_last_backtrack_point,
+	free_topmost_backtrack_point, free_backtrack_queue,
+	estimate_insn_tick, estimate_shadow_tick): New functions.
+	(prune_ready_list): New arg shadows_only_p.  All callers changed.
+	If true, remove everything that isn't SHADOW_P.  Look up delay
+	pairs and estimate ticks to avoid scheduling the first insn too
+	early.
+	(verify_shadows): New function.
+	(schedule_block): Add machinery to enable backtracking.
+	(sched_init): Take sched_no_dce into account when setting
+	DF_LR_RUN_DCE.
+	(free_delay_pairs): New function.
+	(init_h_i_d): Initialize INSN_EXACT_TICK.
+	* Makefile.in (haifa-sched.o): Add $(HASHTAB_H).
+	* sched-deps.c (sd_unresolve_dep): New function.
+	* sched-int. (struct haifa_sched_info): New fields save_state
+	and restore_state.
+	(struct _haifa_insn_data): New fields exact_tick, tick_estimate,
+	feeds_backtrack_insn and shadow_p.
+	(DO_BACKTRACKING): New value in enum SCHED_FLAGS.
+	(sched_no_dce): Declare variable.
+	(record_delay_slot_pair, free_delay_pairs, add_delay_dependencies,
+	sd_unresolve_dep): Declare functions.
+	* modulo-sched.c (sms_sched_info): Clear the two new fields.
+	* sched-rgn.c (rgn_const_sched_info): Likewise.
+	* sel-sched-ir.c (sched_sel_haifa_sched_info): Likewise.
+	* sched-ebb.c (save_ebb_state, restore_ebb_state): New functions.
+	(ebb_sched_info): Add them for the two new fields.
+	(add_deps_for_risky_insns): Call add_delay_dependencies.
+
 2011-07-13  Michael Meissner  <meissner@linux.vnet.ibm.com>
 
 	* config/rs6000/rs6000.opt (-mpointers-to-nested-functions):
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index cd4f782..0fded4e 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -3397,7 +3397,8 @@ modulo-sched.o : modulo-sched.c $(DDG_H) $(CONFIG_H) $(CONFIG_H) $(SYSTEM_H) \
 haifa-sched.o : haifa-sched.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
    $(SCHED_INT_H) $(REGS_H) hard-reg-set.h $(FLAGS_H) insn-config.h $(FUNCTION_H) \
    $(INSN_ATTR_H) $(DIAGNOSTIC_CORE_H) $(RECOG_H) $(EXCEPT_H) $(TM_P_H) $(TARGET_H) output.h \
-   $(PARAMS_H) $(DBGCNT_H) $(CFGLOOP_H) ira.h $(EMIT_RTL_H) $(COMMON_TARGET_H)
+   $(PARAMS_H) $(DBGCNT_H) $(CFGLOOP_H) ira.h $(EMIT_RTL_H) $(COMMON_TARGET_H) \
+   $(HASHTAB_H)
 sched-deps.o : sched-deps.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
    $(RTL_H) $(SCHED_INT_H) $(REGS_H) hard-reg-set.h $(FLAGS_H) insn-config.h \
    $(FUNCTION_H) $(INSN_ATTR_H) $(DIAGNOSTIC_CORE_H) $(RECOG_H) $(EXCEPT_H) cselib.h \
diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
index 5eba79e..3630924 100644
--- a/gcc/haifa-sched.c
+++ b/gcc/haifa-sched.c
@@ -149,6 +149,7 @@ along with GCC; see the file COPYING3.  If not see
 #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
 
@@ -158,6 +159,10 @@ along with GCC; see the file COPYING3.  If not see
 
 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;
+
 /* 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.
@@ -178,7 +183,11 @@ FILE *sched_dump = 0;
 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)
 
 /* If INSN_TICK of an instruction is equal to INVALID_TICK,
    then it should be recalculated from scratch.  */
@@ -303,6 +312,18 @@ static struct ready_list *readyp = &ready;
 /* 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;
@@ -487,6 +508,147 @@ haifa_classify_insn (const_rtx insn)
   return haifa_classify_rtx (PATTERN (insn));
 }
 
+/* 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;
+};
+
+/* 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;
+
+/* 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.  */
+
+void
+record_delay_slot_pair (rtx i1, rtx i2, int cycles)
+{
+  struct delay_pair *p = XNEW (struct delay_pair);
+  struct delay_pair **slot;
+
+  p->i1 = i1;
+  p->i2 = i2;
+  p->cycles = cycles;
+
+  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;
+}
+
+/* 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)
+{
+  return p->cycles;
+}
+
+/* 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);
+
+  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)
+	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);
+	}
+    }
+}
+
 /* Forward declarations.  */
 
 static int priority (rtx);
@@ -857,6 +1019,22 @@ dep_cost_1 (dep_t link, dw_t dw)
   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
@@ -1213,6 +1391,17 @@ rank_for_schedule (const void *x, const void *y)
       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);
 
@@ -1325,6 +1514,7 @@ 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));
@@ -1341,6 +1531,21 @@ queue_insn (rtx insn, int n_cycles, const char *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.  */
@@ -1400,6 +1605,12 @@ ready_add (struct ready_list *ready, rtx insn, bool first_p)
 
   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
@@ -1546,9 +1757,6 @@ advance_one_cycle (void)
     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
 update_register_pressure (rtx insn)
@@ -1644,6 +1852,9 @@ 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;
   /* Initialized with the machine's issue rate every cycle, and updated
      by calls to the variable_issue hook.  */
   int can_issue_more;
@@ -1900,6 +2111,377 @@ remove_notes (rtx head, rtx tail)
     }
 }
 
+/* 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;
+    }
+}
+
+/* Make a copy of the INSN_LIST list LINK and return it.  */
+static rtx
+copy_insn_list (rtx link)
+{
+  rtx new_queue;
+  rtx *pqueue = &new_queue;
+
+  for (; link; link = XEXP (link, 1))
+    {
+      rtx x = XEXP (link, 0);
+      rtx newlink = alloc_INSN_LIST (x, NULL);
+      *pqueue = newlink;
+      pqueue = &XEXP (newlink, 1);
+    }
+  *pqueue = NULL_RTX;
+  return new_queue;
+}
+
+/* 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) = true;
+      pair = pair->next_same_i1;
+    }
+}
+
+/* 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)
+{
+  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;
+
+      for (sd_it = sd_iterator_start (last, SD_LIST_RES_FORW);
+	   sd_iterator_cond (&sd_it, &dep);)
+	{
+	  rtx con = DEP_CON (dep);
+	  TODO_SPEC (con) |= HARD_DEP;
+	  INSN_TICK (con) = INVALID_TICK;
+	  sd_unresolve_dep (sd_it);
+	}
+
+      if (last == insn)
+	break;
+    }
+}
+
+/* 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++)
+	{
+	  QUEUE_INDEX (first[i]) = QUEUE_NOWHERE;
+	  INSN_TICK (first[i]) = 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++)
+	{
+	  QUEUE_INDEX (first[i]) = QUEUE_READY;
+	  INSN_TICK (first[i]) = 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;
+	  INSN_TICK (x) = save->clock_var + i;
+	}
+    }
+  free (save->insn_queue);
+
+  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 (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;
+}
 
 /* Return the head and tail pointers of ebb starting at BEG and ending
    at END.  */
@@ -2467,11 +3049,6 @@ struct choice_entry
    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;
 
@@ -2884,10 +3461,18 @@ commit_schedule (rtx prev_head, rtx tail, basic_block *target_bb)
    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.  */
+   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.
+
+   Return the number of cycles we must
+   advance to find the next ready instruction, or zero if there remain
+   insns on the ready list.  */
 
 static void
-prune_ready_list (state_t temp_state, bool first_cycle_insn_p)
+prune_ready_list (state_t temp_state, bool first_cycle_insn_p,
+		  bool shadows_only_p)
 {
   int i;
 
@@ -2898,7 +3483,12 @@ prune_ready_list (state_t temp_state, bool first_cycle_insn_p)
       int cost = 0;
       const char *reason = "resource conflict";
 
-      if (recog_memoized (insn) < 0)
+      if (shadows_only_p && !DEBUG_INSN_P (insn) && !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
@@ -2910,12 +3500,34 @@ prune_ready_list (state_t temp_state, bool first_cycle_insn_p)
 	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)
 	{
@@ -2926,6 +3538,60 @@ prune_ready_list (state_t temp_state, bool first_cycle_insn_p)
     }
 }
 
+/* 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.  */
@@ -2955,6 +3621,8 @@ schedule_block (basic_block *target_bb)
 
   haifa_recovery_bb_recently_added_p = false;
 
+  backtrack_queue = NULL;
+
   /* Debug info.  */
   if (sched_verbose)
     dump_new_block_header (0, *target_bb, head, tail);
@@ -3051,6 +3719,8 @@ schedule_block (basic_block *target_bb)
 
   gcc_assert (VEC_length (rtx, scheduled_insns) == 0);
   sort_p = TRUE;
+  must_backtrack = false;
+
   /* Loop until all the insns in BB are scheduled.  */
   while ((*current_sched_info->schedule_more_p) ())
     {
@@ -3080,18 +3750,21 @@ schedule_block (basic_block *target_bb)
       while (advance > 0);
 
       if (ready.n_ready > 0)
-	prune_ready_list (temp_state, true);
+	prune_ready_list (temp_state, true, false);
       if (ready.n_ready == 0)
 	continue;
+      if (must_backtrack)
+	goto do_backtrack;
 
       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)
 	    {
@@ -3130,6 +3803,7 @@ schedule_block (basic_block *target_bb)
 	  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
@@ -3236,6 +3910,22 @@ schedule_block (basic_block *target_bb)
 	      goto restart_choose_ready;
 	    }
 
+	  if (delay_htab)
+	    {
+	      /* 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)
+		{
+		  save_backtrack_point (delay_entry, ls);
+		  if (sched_verbose >= 2)
+		    fprintf (sched_dump, ";;\t\tsaving backtrack point\n");
+		}
+	    }
+
 	  /* DECISION is made.  */
 
           if (TODO_SPEC (insn) & SPECULATIVE)
@@ -3275,18 +3965,70 @@ schedule_block (basic_block *target_bb)
 	    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 (must_backtrack)
+	    break;
+
 	  if (advance != 0)
 	    break;
 
 	  ls.first_cycle_insn_p = false;
 	  if (ready.n_ready > 0)
-	    prune_ready_list (temp_state, false);
+	    prune_ready_list (temp_state, false, ls.shadows_only_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;
+	      }
+	  }
+      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;
+	  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 (clock_var == 0 && ls.first_cycle_insn_p)
+		goto end_schedule;
+	      advance = 1;
+	      break;
+	    }
+	}
+    }
+ end_schedule:
   /* Debug info.  */
   if (sched_verbose)
     {
@@ -3364,6 +4106,8 @@ schedule_block (basic_block *target_bb)
 
   current_sched_info->head = head;
   current_sched_info->tail = tail;
+
+  free_backtrack_queue ();
 }
 
 /* Set_priorities: compute priority of each insn in the block.  */
@@ -3488,7 +4232,8 @@ sched_init (void)
 
   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.  */
@@ -3653,6 +4398,17 @@ sched_finish (void)
 #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
    INSN_TICKs of their dependents.
    HEAD and TAIL are the begin and the end of the current scheduled block.  */
@@ -5453,6 +6209,7 @@ init_h_i_d (rtx insn)
       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;
     }
diff --git a/gcc/modulo-sched.c b/gcc/modulo-sched.c
index e9749b2..85e24d4 100644
--- a/gcc/modulo-sched.c
+++ b/gcc/modulo-sched.c
@@ -283,6 +283,7 @@ static struct haifa_sched_info sms_sched_info =
   0, 0,
 
   NULL, NULL, NULL, NULL,
+  NULL, NULL,
   0
 };
 
diff --git a/gcc/sched-deps.c b/gcc/sched-deps.c
index 4ceea72..0bba96c 100644
--- a/gcc/sched-deps.c
+++ b/gcc/sched-deps.c
@@ -1301,6 +1301,28 @@ sd_resolve_dep (sd_iterator_def sd_it)
 		 INSN_RESOLVED_FORW_DEPS (pro));
 }
 
+/* Perform the inverse operation of sd_resolve_dep.  Restore the dependence
+   pointed to by SD_IT to unresolved state.  */
+void
+sd_unresolve_dep (sd_iterator_def sd_it)
+{
+  dep_node_t node = DEP_LINK_NODE (*sd_it.linkp);
+  dep_t dep = DEP_NODE_DEP (node);
+  rtx pro = DEP_PRO (dep);
+  rtx con = DEP_CON (dep);
+
+  if ((current_sched_info->flags & DO_SPECULATION)
+      && (DEP_STATUS (dep) & SPECULATIVE))
+    move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con),
+		   INSN_SPEC_BACK_DEPS (con));
+  else
+    move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con),
+		   INSN_HARD_BACK_DEPS (con));
+
+  move_dep_link (DEP_NODE_FORW (node), INSN_RESOLVED_FORW_DEPS (pro),
+		 INSN_FORW_DEPS (pro));
+}
+
 /* Make TO depend on all the FROM's producers.
    If RESOLVED_P is true add dependencies to the resolved lists.  */
 void
diff --git a/gcc/sched-ebb.c b/gcc/sched-ebb.c
index 6bb223b..47ce342 100644
--- a/gcc/sched-ebb.c
+++ b/gcc/sched-ebb.c
@@ -74,6 +74,25 @@ static void ebb_add_block (basic_block, basic_block);
 static basic_block advance_target_bb (basic_block, rtx);
 static void ebb_fix_recovery_cfg (int, int, int);
 
+/* Allocate memory and store the state of the frontend.  Return the allocated
+   memory.  */
+static void *
+save_ebb_state (void)
+{
+  int *p = XNEW (int);
+  *p = sched_rgn_n_insns;
+  return p;
+}
+
+/* Restore the state of the frontend from P_, then free it.  */
+static void
+restore_ebb_state (void *p_)
+{
+  int *p = (int *)p_;
+  sched_rgn_n_insns = *p;
+  free (p_);
+}
+
 /* Return nonzero if there are more insns that should be scheduled.  */
 
 static int
@@ -295,6 +314,10 @@ static struct haifa_sched_info ebb_sched_info =
   begin_schedule_ready,
   begin_move_insn,
   advance_target_bb,
+
+  save_ebb_state,
+  restore_ebb_state,
+
   SCHED_EBB
   /* We can create new blocks in begin_schedule_ready ().  */
   | NEW_BBS
@@ -377,76 +400,80 @@ add_deps_for_risky_insns (rtx head, rtx tail)
   basic_block last_block = NULL, bb;
 
   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
-    if (control_flow_insn_p (insn))
-      {
-	bb = BLOCK_FOR_INSN (insn);
-	bb->aux = last_block;
-	last_block = bb;
-	last_jump = insn;
-      }
-    else if (INSN_P (insn) && last_jump != NULL_RTX)
-      {
-	classification = haifa_classify_insn (insn);
-	prev = last_jump;
-	switch (classification)
-	  {
-	  case PFREE_CANDIDATE:
-	    if (flag_schedule_speculative_load)
-	      {
-		bb = earliest_block_with_similiar_load (last_block, insn);
-		if (bb)
-		  {
-		    bb = (basic_block) bb->aux;
-		    if (!bb)
-		      break;
-		    prev = BB_END (bb);
-		  }
-	      }
-	    /* Fall through.  */
-	  case TRAP_RISKY:
-	  case IRISKY:
-	  case PRISKY_CANDIDATE:
-	    /* ??? We could implement better checking PRISKY_CANDIDATEs
-	       analogous to sched-rgn.c.  */
-	    /* We can not change the mode of the backward
-	       dependency because REG_DEP_ANTI has the lowest
-	       rank.  */
-	    if (! sched_insns_conditions_mutex_p (insn, prev))
-	      {
-		dep_def _dep, *dep = &_dep;
-
-		init_dep (dep, prev, insn, REG_DEP_ANTI);
-
-		if (!(current_sched_info->flags & USE_DEPS_LIST))
-		  {
-		    enum DEPS_ADJUST_RESULT res;
-
-		    res = sd_add_or_update_dep (dep, false);
-
-		    /* We can't change an existing dependency with
-		       DEP_ANTI.  */
-		    gcc_assert (res != DEP_CHANGED);
-		  }
-		else
-		  {
-		    if ((current_sched_info->flags & DO_SPECULATION)
-			&& (spec_info->mask & BEGIN_CONTROL))
-		      DEP_STATUS (dep) = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
-						       MAX_DEP_WEAK);
-
-		    sd_add_or_update_dep (dep, false);
-
-		    /* Dep_status could have been changed.
-		       No assertion here.  */
-		  }
-	      }
-
-            break;
-
-          default:
-            break;
-	  }
-      }
+    {
+      add_delay_dependencies (insn);
+      if (control_flow_insn_p (insn))
+	{
+	  bb = BLOCK_FOR_INSN (insn);
+	  bb->aux = last_block;
+	  last_block = bb;
+	  last_jump = insn;
+	}
+      else if (INSN_P (insn) && last_jump != NULL_RTX)
+	{
+	  classification = haifa_classify_insn (insn);
+	  prev = last_jump;
+
+	  switch (classification)
+	    {
+	    case PFREE_CANDIDATE:
+	      if (flag_schedule_speculative_load)
+		{
+		  bb = earliest_block_with_similiar_load (last_block, insn);
+		  if (bb)
+		    {
+		      bb = (basic_block) bb->aux;
+		      if (!bb)
+			break;
+		      prev = BB_END (bb);
+		    }
+		}
+	      /* Fall through.  */
+	    case TRAP_RISKY:
+	    case IRISKY:
+	    case PRISKY_CANDIDATE:
+	      /* ??? We could implement better checking PRISKY_CANDIDATEs
+		 analogous to sched-rgn.c.  */
+	      /* We can not change the mode of the backward
+		 dependency because REG_DEP_ANTI has the lowest
+		 rank.  */
+	      if (! sched_insns_conditions_mutex_p (insn, prev))
+		{
+		  dep_def _dep, *dep = &_dep;
+
+		  init_dep (dep, prev, insn, REG_DEP_ANTI);
+
+		  if (!(current_sched_info->flags & USE_DEPS_LIST))
+		    {
+		      enum DEPS_ADJUST_RESULT res;
+
+		      res = sd_add_or_update_dep (dep, false);
+
+		      /* We can't change an existing dependency with
+			 DEP_ANTI.  */
+		      gcc_assert (res != DEP_CHANGED);
+		    }
+		  else
+		    {
+		      if ((current_sched_info->flags & DO_SPECULATION)
+			  && (spec_info->mask & BEGIN_CONTROL))
+			DEP_STATUS (dep) = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
+							 MAX_DEP_WEAK);
+
+		      sd_add_or_update_dep (dep, false);
+
+		      /* Dep_status could have been changed.
+			 No assertion here.  */
+		    }
+		}
+
+	      break;
+
+	    default:
+	      break;
+	    }
+	}
+    }
   /* Maintain the invariant that bb->aux is clear after use.  */
   while (last_block)
     {
diff --git a/gcc/sched-int.h b/gcc/sched-int.h
index 8b39a22c..348a3cc 100644
--- a/gcc/sched-int.h
+++ b/gcc/sched-int.h
@@ -603,6 +603,13 @@ struct haifa_sched_info
      The first parameter is the current basic block in EBB.  */
   basic_block (*advance_target_bb) (basic_block, rtx);
 
+  /* Allocate memory, store the frontend scheduler state in it, and
+     return it.  */
+  void *(*save_state) (void);
+  /* Restore frontend scheduler state from the argument, and free the
+     memory.  */
+  void (*restore_state) (void *);
+
   /* ??? FIXME: should use straight bitfields inside sched_info instead of
      this flag field.  */
   unsigned int flags;
@@ -762,10 +769,18 @@ struct _haifa_insn_data
      used to note timing constraints for the insns in the pending list.  */
   int tick;
 
+  /* For insns that are scheduled at a fixed difference from another,
+     this records the tick in which they must be ready.  */
+  int exact_tick;
+
   /* INTER_TICK is used to adjust INSN_TICKs of instructions from the
      subsequent blocks in a region.  */
   int inter_tick;
 
+  /* Used temporarily to estimate an INSN_TICK value for an insn given
+     current knowledge.  */
+  int tick_estimate;
+
   /* See comment on QUEUE_INDEX macro in haifa-sched.c.  */
   int queue_index;
 
@@ -775,6 +790,14 @@ struct _haifa_insn_data
      moved load insn and this one.  */
   unsigned int fed_by_spec_load : 1;
   unsigned int is_load_insn : 1;
+  /* Nonzero if this insn has negative-cost forward dependencies against
+     an already scheduled insn.  */
+  unsigned int feeds_backtrack_insn : 1;
+
+  /* Nonzero if this insn is a shadow of another, scheduled after a fixed
+     delay.  We only emit shadows at the end of a cycle, with no other
+     real insns following them.  */
+  unsigned int shadow_p : 1;
 
   /* '> 0' if priority is valid,
      '== 0' if priority was not yet computed,
@@ -1017,7 +1040,8 @@ enum SCHED_FLAGS {
      Results in generation of data and control speculative dependencies.
      Requires USE_DEPS_LIST set.  */
   DO_SPECULATION = USE_DEPS_LIST << 1,
-  SCHED_RGN = DO_SPECULATION << 1,
+  DO_BACKTRACKING = DO_SPECULATION << 1,
+  SCHED_RGN = DO_BACKTRACKING << 1,
   SCHED_EBB = SCHED_RGN << 1,
   /* Scheduler can possibly create new basic blocks.  Used for assertions.  */
   NEW_BBS = SCHED_EBB << 1,
@@ -1304,7 +1328,11 @@ extern int *ebb_head;
 extern int current_nr_blocks;
 extern int current_blocks;
 extern int target_bb;
+extern bool sched_no_dce;
 
+extern void record_delay_slot_pair (rtx, rtx, int);
+extern void free_delay_pairs (void);
+extern void add_delay_dependencies (rtx);
 extern bool sched_is_disabled_for_current_region_p (void);
 extern void sched_rgn_init (bool);
 extern void sched_rgn_finish (void);
@@ -1478,6 +1506,7 @@ extern dep_t sd_find_dep_between (rtx, rtx, bool);
 extern void sd_add_dep (dep_t, bool);
 extern enum DEPS_ADJUST_RESULT sd_add_or_update_dep (dep_t, bool);
 extern void sd_resolve_dep (sd_iterator_def);
+extern void sd_unresolve_dep (sd_iterator_def);
 extern void sd_copy_back_deps (rtx, rtx, bool);
 extern void sd_delete_dep (sd_iterator_def);
 extern void sd_debug_lists (rtx, sd_list_types_def);
diff --git a/gcc/sched-rgn.c b/gcc/sched-rgn.c
index aa9c81d..b4d4c81 100644
--- a/gcc/sched-rgn.c
+++ b/gcc/sched-rgn.c
@@ -2371,6 +2371,7 @@ static const struct haifa_sched_info rgn_const_sched_info =
   begin_schedule_ready,
   NULL,
   advance_target_bb,
+  NULL, NULL,
   SCHED_RGN
 };
 
diff --git a/gcc/sel-sched-ir.c b/gcc/sel-sched-ir.c
index de7629a..ac48325 100644
--- a/gcc/sel-sched-ir.c
+++ b/gcc/sel-sched-ir.c
@@ -5700,6 +5700,10 @@ static struct haifa_sched_info sched_sel_haifa_sched_info =
   NULL, /* begin_schedule_ready */
   NULL, /* begin_move_insn */
   NULL, /* advance_target_bb */
+
+  NULL,
+  NULL,
+
   SEL_SCHED | NEW_BBS
 };