diff mbox

Predication during scheduling

Message ID 4E85E077.902@codesourcery.com
State New
Headers show

Commit Message

Bernd Schmidt Sept. 30, 2011, 3:29 p.m. UTC
This patch allows a backend to set a new scheduler flag, DO_PREDICATION,
which will make the haifa scheduler try to move insns across jumps by
predicating them. On C6X, the primary benefit is to fill jump delay slots.

There is a new type of dependency, REG_DEP_CONTROL, which is used where
possible for dependencies against jumps rather than REG_DEP_ANTI. It
represents a dependency that can be broken if the dependent insn is
predicated with a condition opposite to that of the jump. If only one
such dependency is left, it is marked as cancelled, and the pattern of
the insn is replaced by a conditional version. Care needs to be taken to
undo these changes when backtracking. Since the whole idea can be
thought of as a type of speculation, I've reused the TODO_SPEC field to
hold information about the predication status.

When generating REG_DEP_CONTROL deps, we ensure that the insn is also
made to depend on the producer of the condition (nothing is ever lost by
adding these extra dependencies, since a normal dependency against the
jump would obviously also ensure that the insn is scheduled after the
producer of the jump's condition).

This alone is not sufficient, however: we must also verify while
scheduling that the condition register is not clobbered before such a
predicated instruction. If we schedule an insn that clobbers the
condition reg, we must restore the old pattern of a predicated insn, and
de-cancel the dependency.

The patch was forward ported from 4.5; it replaces the NON_FLUSH_JUMP_P
mechanism that Jakub added in the meantime by a new pending_jumps list.
The two should be equivalent - we independently came to the conclusion
that something like this is necessary, but I think it's slightly clearer
with the extra list for jumps.

Bootstrapped and tested on ia64-linux (c, c++ as always - anything else
doesn't build on gcc60). This was slightly pointless as I forgot to set
the DO_PREDICATION bit for ia64, so the only value was to find a
sched-deps crash when using sel-sched. I'll probably rerun that. Also
tested on c6x-elf (some small fluctuations in libstdc++ tests which I've
also seen with other patches and which appear random - possibly timeouts).


Bernd
gcc/
	* reg-notes.def (DEP_CONTROL): New.
	* sched-ebb.c (add_deps_for_risky_insns): Add a REG_DEP_CONTROL when
	not doing speculation.
	* rtlanal.c: Swap includes of "rtl.h" and "hard-reg-set.h".
	(record_hard_reg_sets, find_all_hard_reg_sets, record_hard_reg_uses_1,
	record_hard_reg_uses): New functions.
	* function.c (record_hard_reg_sets): Remove; move to rtlanal.c.
	* lists.c (copy_INSN_LIST, concat_INSN_LIST): New functions.
	* haifa-sched.c: Swap includes of "rtl.h" and "hard-reg-set.h".
	(MUST_RECOMPUTE_SPEC_P): New macro.
	(real_insn_for_shadow): New function.
	(cond_clobbered_p, recompute_todo_spec, check_clobbered_conditions,
	toggle_cancelled_flags): New static functions.
	(schedule_insn): Relax an assert to only check for empty hard back
	dependencies.  Skip cancelled dependencies.  Call
	check_clobbered_conditions.
	(copy_insn_list): Remove function, renamed moved to lists.c.
	(save_backtrack_point): Use new spelling copy_INSN_LIST.
	(unschedule_insns_until): Ensure TODO_SPEC is reset properly.
	(restore_last_backtrack_point): Likewise.  Call toggle_cancelled_flags.
	(estimate_insn_tick): Ignore cancelled dependencies.
	(haifa_speculate_insn): Move declaration.
	(try_ready): Move code into recompute_todo_spec and call it.  Tweak
	some asserts.  Ensure predicated patterns are restored if necessary.
	Dump DEP_CONTROL flag.
	(haifa_change_pattern): Merge with sched_change_pattern.
	(sched_change_pattern): Remove function.
	* sched-deps.c (NON_FLUSH_JUMP_KIND, NON_FLUSH_JUMP): Remove.  All
	uses changed to simply not test NON_FLUSH_JUMP_P.
	(ds_to_dk, dk_to_ds, dump_dep, ds_to_dt, dump_ds, check_dep): Handle
	REG_DEP_CONTROL.
	(dep_spec_p): If DO_PREDICATION, REG_DEP_CONTROL is speculative.
	(reg_pending_control_uses, control_dependency_cache): New static
	variables.
	(sched_get_reverse_condition_uncached): New function.
	(sd_find_dep_between): Remove pointless assert.  Look in
	control_dependency_cache.
	(ask_dependency_caches, set_dependency_caches, sd_delete_dep,
	extend_dependency_caches, sched_deps_finish): Handle REG_DEP_CONTROL
	and control_dependency_cache.
	(sd_unresolve_dep): Use dep_spec_p.
	(add_dependence): Now a wrapper around add_dependence_1, handling
	REG_DEP_CONTROL specially.
	(flush_pending_lists): Clear pending_jump_insns.
	(sched_analyze_1): Handle pending_jump_insns like a memory flush.
	(sched_analyze_2): Unconditionally add to pending memory flushes,
	keep previous behaviour but apply it to pending_jump_insns instead.
	(sched_analyze_insn): Defer adding jump reg dependencies using
	reg_pending_control_uses; add them to the control_uses list.  Handle
	pending_jump_insns and control_uses when adding dependence lists.
	(deps_analyze_insn): Update INSN_COND_DEPS.
	(deps_analyze_insn): Add jumps to pending_jump_insns rather than
	last_pending_memory_flush.
	(init_deps): Initialize pending_jump_insns.
	(free_deps): Free control_uses.
	(remove_from_deps): Remove from pending_jump_insns.
	(init_deps_global): Allocate reg_pending_control_uses).
	(finish_deps_global): Free it.
	(add_dependence_1): Renamed from add_dependence.  Handle
	REG_DEP_CONTROL.
	* rtl.h (record_hard_reg_uses, find_all_hard_reg_sets): Declare.
	(copy_INSN_LIST, concat_INSN_LIST): Declare.
	* sched-int.h (struct deps_reg): Add control_uses.
	(struct deps_desc): Add pending_jump_insns.
	(struct _haifa_deps_insn_data): Add cond_deps.
	(struct _haifa_insn_data): Add must_recompute_spec and predicated_pat.
	(INSN_COND_DEPS, PREDICATED_PAT): New macros.
	(BITS_PER_DEP_WEAK): Adjust for two extra bits in the word.
	(DEP_CONTROL): New macro.
	(DEP_TYPES): Include it.
	(HARD_DEP): Adjust definition.
	(DEP_CANCELLED): New macro.
	(enum SCHED_FLAGS): Add DO_PREDICATION.
	(sched_get_reverse_condition_uncached, real_insn_for_shadow): Declare.
	* sched-rgn.c (concat_INSN_LIST): Remove function.
	(deps_join): Handle pending_jump_insns.
	(free_pending_lists): Likewise.
	* config/c6x/c6x.c (c6x_set_sched_flags): Set DO_PREDICATION for final
	schedule.

Comments

Bernd Schmidt Oct. 13, 2011, 9:01 p.m. UTC | #1
On 09/30/11 17:29, Bernd Schmidt wrote:
> This patch allows a backend to set a new scheduler flag, DO_PREDICATION,
> which will make the haifa scheduler try to move insns across jumps by
> predicating them. On C6X, the primary benefit is to fill jump delay slots.

Ping.

http://gcc.gnu.org/ml/gcc-patches/2011-09/msg02053.html


Bernd
Vladimir Makarov Oct. 14, 2011, 3:35 p.m. UTC | #2
On 10/13/2011 05:01 PM, Bernd Schmidt wrote:
> On 09/30/11 17:29, Bernd Schmidt wrote:
>> This patch allows a backend to set a new scheduler flag, DO_PREDICATION,
>> which will make the haifa scheduler try to move insns across jumps by
>> predicating them. On C6X, the primary benefit is to fill jump delay slots.
> Ping.
>
> http://gcc.gnu.org/ml/gcc-patches/2011-09/msg02053.html
>
>
It is hard to read the patch without function names.

As I understand, changes for tree/sra.c is in the patch by accident.

Thanks for additional scheduler code cleaning.

The scheduler part of the patch is ok for me (other part changes are 
obvious).  Could you only commit it at the beginning of the next week.

Thanks, Bernd.
Bernd Schmidt Oct. 14, 2011, 4:04 p.m. UTC | #3
On 10/14/11 17:35, Vladimir Makarov wrote:
> On 10/13/2011 05:01 PM, Bernd Schmidt wrote:
>> http://gcc.gnu.org/ml/gcc-patches/2011-09/msg02053.html
>>
>>
> It is hard to read the patch without function names.

Oh, you mean without -p? Not sure how that happened, svn diff seems to
add them when run on my machine. I may have run it on gcc60 during ia64
testing.

> As I understand, changes for tree/sra.c is in the patch by accident.

Yes - it was necessary to get ia64 to bootstrap.

> Thanks for additional scheduler code cleaning.
> 
> The scheduler part of the patch is ok for me (other part changes are
> obvious).  Could you only commit it at the beginning of the next week.

Thank you!


Bernd
diff mbox

Patch

Index: gcc/sched-ebb.c
===================================================================
--- gcc/sched-ebb.c	(revision 179045)
+++ gcc/sched-ebb.c	(working copy)
@@ -432,32 +432,23 @@ 
 		 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))
+		  if ((current_sched_info->flags & DO_SPECULATION)
+		      && (spec_info->mask & BEGIN_CONTROL))
 		    {
-		      enum DEPS_ADJUST_RESULT res;
+		      dep_def _dep, *dep = &_dep;
 
-		      res = sd_add_or_update_dep (dep, false);
+		      init_dep (dep, prev, insn, REG_DEP_ANTI);
 
-		      /* 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);
+		      if (current_sched_info->flags & USE_DEPS_LIST)
+			{
+			  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.  */
 		    }
+		  else
+		    add_dependence (insn, prev, REG_DEP_CONTROL);
 		}
 
 	      break;
Index: gcc/rtlanal.c
===================================================================
--- gcc/rtlanal.c	(revision 179045)
+++ gcc/rtlanal.c	(working copy)
@@ -999,6 +999,56 @@ 
   note_stores (INSN_P (insn) ? PATTERN (insn) : insn, set_of_1, &data);
   return data.found;
 }
+
+/* This function, called through note_stores, collects sets and
+   clobbers of hard registers in a HARD_REG_SET, which is pointed to
+   by DATA.  */
+void
+record_hard_reg_sets (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
+{
+  HARD_REG_SET *pset = (HARD_REG_SET *)data;
+  if (REG_P (x) && HARD_REGISTER_P (x))
+    add_to_hard_reg_set (pset, GET_MODE (x), REGNO (x));
+}
+
+/* Examine INSN, and compute the set of hard registers written by it.
+   Store it in *PSET.  Should only be called after reload.  */
+void
+find_all_hard_reg_sets (const_rtx insn, HARD_REG_SET *pset)
+{
+  rtx link;
+
+  CLEAR_HARD_REG_SET (*pset);
+  note_stores (PATTERN (insn), record_hard_reg_sets, pset);
+  if (CALL_P (insn))
+    IOR_HARD_REG_SET (*pset, call_used_reg_set);
+  for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
+    if (REG_NOTE_KIND (link) == REG_INC)
+      record_hard_reg_sets (XEXP (link, 0), NULL, pset);
+}
+
+/* A for_each_rtx subroutine of record_hard_reg_uses.  */
+static int
+record_hard_reg_uses_1 (rtx *px, void *data)
+{
+  rtx x = *px;
+  HARD_REG_SET *pused = (HARD_REG_SET *)data;
+
+  if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER)
+    {
+      int nregs = hard_regno_nregs[REGNO (x)][GET_MODE (x)];
+      while (nregs-- > 0)
+	SET_HARD_REG_BIT (*pused, REGNO (x) + nregs);
+    }
+  return 0;
+}
+
+/* Like record_hard_reg_sets, but called through note_uses.  */
+void
+record_hard_reg_uses (rtx *px, void *data)
+{
+  for_each_rtx (px, record_hard_reg_uses_1, data);
+}
 
 /* Given an INSN, return a SET expression if this insn has only a single SET.
    It may also have CLOBBERs, USEs, or SET whose output
Index: gcc/lists.c
===================================================================
--- gcc/lists.c	(revision 179045)
+++ gcc/lists.c	(working copy)
@@ -164,6 +164,38 @@ 
   free_list (listp, &unused_insn_list);
 }
 
+/* Make a copy of the INSN_LIST list LINK and return it.  */
+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;
+}
+
+/* Duplicate the INSN_LIST elements of COPY and prepend them to OLD.  */
+
+rtx
+concat_INSN_LIST (rtx copy, rtx old)
+{
+  rtx new_rtx = old;
+  for (; copy ; copy = XEXP (copy, 1))
+    {
+      new_rtx = alloc_INSN_LIST (XEXP (copy, 0), new_rtx);
+      PUT_REG_NOTE_KIND (new_rtx, REG_NOTE_KIND (copy));
+    }
+  return new_rtx;
+}
+
 /* This function will free up an individual EXPR_LIST node.  */
 void
 free_EXPR_LIST_node (rtx ptr)
Index: gcc/haifa-sched.c
===================================================================
--- gcc/haifa-sched.c	(revision 179045)
+++ gcc/haifa-sched.c	(working copy)
@@ -129,9 +129,9 @@ 
 #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"
@@ -188,6 +188,7 @@ 
 #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.  */
@@ -591,6 +592,24 @@ 
   *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)
+    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
@@ -700,6 +719,7 @@ 
 
 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);
@@ -707,7 +727,7 @@ 
 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);
@@ -936,7 +956,178 @@ 
     }
   fprintf (sched_dump, "\n");
 }
+
+/* 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.
+	 If we have a true dependency on it, it sets it to the correct value,
+	 otherwise it must be a later insn scheduled in-between that clobbers
+	 the condition.  */
+      FOR_EACH_VEC_ELT_REVERSE (rtx, scheduled_insns, i, prev)
+	{
+	  sd_iterator_def sd_it;
+	  dep_t dep;
+	  HARD_REG_SET t;
+	  bool found;
+
+	  find_all_hard_reg_sets (prev, &t);
+	  if (!TEST_HARD_REG_BIT (t, regno))
+	    continue;
+
+	  found = false;
+	  FOR_EACH_DEP (next, SD_LIST_RES_BACK, sd_it, dep)
+	    {
+	      if (DEP_PRO (dep) == prev && DEP_TYPE (dep) == REG_DEP_TRUE)
+		{
+		  found = true;
+		  break;
+		}
+	    }
+	  if (!found)
+	    return HARD_DEP;
+	  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;
+    }
+
+  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;
+}
+
 /* Pointer to the last instruction scheduled.  */
 static rtx last_scheduled_insn;
 
@@ -1843,6 +2034,51 @@ 
   setup_insn_max_reg_pressure (after, false);
 }
 
+/* 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;
+	    }
+	}
+    }
+}
+
 /* A structure that holds local state for the loop in schedule_block.  */
 struct sched_block_state
 {
@@ -1900,7 +2136,7 @@ 
 
   /* 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))
@@ -1910,6 +2146,12 @@ 
 	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)
@@ -1963,17 +2205,36 @@ 
      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.  */
@@ -2147,24 +2408,6 @@ 
     }
 }
 
-/* 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
@@ -2191,7 +2434,7 @@ 
   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->insn_queue[i] = copy_INSN_LIST (insn_queue[q]);
     }
 
   save->clock_var = clock_var;
@@ -2228,6 +2471,49 @@ 
     }
 }
 
+/* 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.  */
@@ -2235,6 +2521,12 @@ 
 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;
@@ -2253,14 +2545,40 @@ 
 	   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 (!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.
@@ -2270,7 +2588,6 @@ 
 
 static void
 restore_last_backtrack_point (struct sched_block_state *psched_block)
-
 {
   rtx link;
   int i;
@@ -2294,8 +2611,9 @@ 
       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;
+	  rtx insn = first[i];
+	  QUEUE_INDEX (insn) = QUEUE_NOWHERE;
+	  INSN_TICK (insn) = INVALID_TICK;
 	}
     }
   for (i = 0; i <= max_insn_queue_index; i++)
@@ -2319,8 +2637,10 @@ 
       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;
+	  rtx insn = first[i];
+	  QUEUE_INDEX (insn) = QUEUE_READY;
+	  TODO_SPEC (insn) = recompute_todo_spec (insn);
+	  INSN_TICK (insn) = save->clock_var;
 	}
     }
 
@@ -2336,11 +2656,14 @@ 
 	{
 	  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;
@@ -2421,6 +2744,9 @@ 
       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
@@ -3989,6 +4315,7 @@ 
 	  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);
@@ -4452,8 +4779,6 @@ 
   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:
@@ -4467,57 +4792,15 @@ 
 
   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)));
+		  || (old_ts & SPECULATIVE)
+		  || (old_ts & DEP_CONTROL)));
 
-  if (sd_lists_empty_p (next, SD_LIST_BACK))
-    /* NEXT has all its dependencies resolved.  */
-    new_ts = 0;
-  else
-    {
-      /* One of the NEXT's dependencies has been resolved.
-	 Recalculate NEXT's status.  */
+  new_ts = recompute_todo_spec (next);
 
-      if (!sd_lists_empty_p (next, SD_LIST_HARD_BACK))
-	new_ts = HARD_DEP;
-      else
-	/* 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;
-
-	  new_ts = 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 (first_p)
-		{
-		  first_p = false;
-
-		  new_ts = ds;
-		}
-	      else
-		new_ts = ds_merge (new_ts, ds);
-	    }
-
-	  if (ds_weak (new_ts) < spec_info->data_weakness_cutoff)
-	    /* Too few points.  */
-	    new_ts = HARD_DEP;
-	}
-    }
-
   if (new_ts & HARD_DEP)
-    gcc_assert (new_ts == HARD_DEP && new_ts == old_ts
+    gcc_assert (new_ts == old_ts
 		&& QUEUE_INDEX (next) == QUEUE_NOWHERE);
   else if (current_sched_info->new_ready)
     new_ts = current_sched_info->new_ready (next, new_ts);
@@ -4540,7 +4823,7 @@ 
       int res;
       rtx new_pat;
 
-      gcc_assert (!(new_ts & ~SPECULATIVE));
+      gcc_assert ((new_ts & SPECULATIVE) && !(new_ts & ~SPECULATIVE));
 
       res = haifa_speculate_insn (next, new_ts, &new_pat);
 
@@ -4566,7 +4849,8 @@ 
 	       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:
@@ -4591,16 +4875,19 @@ 
       /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
 
       change_queue_index (next, QUEUE_NOWHERE);
+
       return -1;
     }
   else if (!(new_ts & BEGIN_SPEC)
-	   && ORIG_PAT (next) && !IS_SPECULATION_CHECK_P (next))
+	   && 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;
     }
 
@@ -4618,7 +4905,8 @@ 
           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");
     }
 
@@ -5594,38 +5882,33 @@ 
   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);
 
-  for (sd_it = sd_iterator_start (insn, (SD_LIST_FORW | SD_LIST_BACK
-					 | SD_LIST_RES_BACK));
-       sd_iterator_cond (&sd_it, &dep);)
+  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);
     }
-}
 
-/* 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);
-
   /* 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,
Index: gcc/function.c
===================================================================
--- gcc/function.c	(revision 179045)
+++ gcc/function.c	(working copy)
@@ -2895,17 +2895,6 @@ 
   SET_DECL_RTL (parm, stack_parm);
 }
 
-/* A subroutine of assign_parm_setup_reg, called through note_stores.
-   This collects sets and clobbers of hard registers in a HARD_REG_SET,
-   which is pointed to by DATA.  */
-static void
-record_hard_reg_sets (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
-{
-  HARD_REG_SET *pset = (HARD_REG_SET *)data;
-  if (REG_P (x) && HARD_REGISTER_P (x))
-    add_to_hard_reg_set (pset, GET_MODE (x), REGNO (x));
-}
-
 /* A subroutine of assign_parms.  Allocate a pseudo to hold the current
    parameter.  Get it there.  Perform all ABI specified conversions.  */
 
Index: gcc/tree-sra.c
===================================================================
--- gcc/tree-sra.c	(revision 179045)
+++ gcc/tree-sra.c	(working copy)
@@ -2075,25 +2075,13 @@ 
 	  || ((root->grp_scalar_read || root->grp_assignment_read)
 	      && (root->grp_scalar_write || root->grp_assignment_write))))
     {
-      bool new_integer_type;
-      if (TREE_CODE (root->type) == ENUMERAL_TYPE)
-	{
-	  tree rt = root->type;
-	  root->type = build_nonstandard_integer_type (TYPE_PRECISION (rt),
-						       TYPE_UNSIGNED (rt));
-	  new_integer_type = true;
-	}
-      else
-	new_integer_type = false;
-
       if (dump_file && (dump_flags & TDF_DETAILS))
 	{
 	  fprintf (dump_file, "Marking ");
 	  print_generic_expr (dump_file, root->base, 0);
-	  fprintf (dump_file, " offset: %u, size: %u ",
+	  fprintf (dump_file, " offset: %u, size: %u: ",
 		   (unsigned) root->offset, (unsigned) root->size);
-	  fprintf (dump_file, " to be replaced%s.\n",
-		   new_integer_type ? " with an integer": "");
+	  fprintf (dump_file, " to be replaced.\n");
 	}
 
       root->grp_to_be_replaced = 1;
Index: gcc/sched-deps.c
===================================================================
--- gcc/sched-deps.c	(revision 179045)
+++ gcc/sched-deps.c	(working copy)
@@ -52,12 +52,6 @@ 
 #define CHECK (false)
 #endif
 
-/* In deps->last_pending_memory_flush marks JUMP_INSNs that weren't
-   added to the list because of flush_pending_lists, stands just
-   for itself and not for any other pending memory reads/writes.  */
-#define NON_FLUSH_JUMP_KIND REG_DEP_ANTI
-#define NON_FLUSH_JUMP_P(x) (REG_NOTE_KIND (x) == NON_FLUSH_JUMP_KIND)
-
 /* Holds current parameters for the dependency analyzer.  */
 struct sched_deps_info_def *sched_deps_info;
 
@@ -74,6 +68,9 @@ 
   if (ds & DEP_OUTPUT)
     return REG_DEP_OUTPUT;
 
+  if (ds & DEP_CONTROL)
+    return REG_DEP_CONTROL;
+
   gcc_assert (ds & DEP_ANTI);
 
   return REG_DEP_ANTI;
@@ -91,6 +88,9 @@ 
     case REG_DEP_OUTPUT:
       return DEP_OUTPUT;
 
+    case REG_DEP_CONTROL:
+      return DEP_CONTROL;
+
     default:
       gcc_assert (dk == REG_DEP_ANTI);
       return DEP_ANTI;
@@ -187,6 +187,10 @@ 
 	  t = 'o';
 	  break;
 
+	case REG_DEP_CONTROL:
+	  t = 'c';
+	  break;
+
 	case REG_DEP_ANTI:
 	  t = 'a';
 	  break;
@@ -420,13 +424,22 @@ 
 dep_spec_p (dep_t dep)
 {
   if (current_sched_info->flags & DO_SPECULATION)
-    return (DEP_STATUS (dep) & SPECULATIVE) != 0;
+    {
+      if (DEP_STATUS (dep) & SPECULATIVE)
+	return true;
+    }
+  if (current_sched_info->flags & DO_PREDICATION)
+    {
+      if (DEP_TYPE (dep) == REG_DEP_CONTROL)
+	return true;
+    }
   return false;
 }
 
 static regset reg_pending_sets;
 static regset reg_pending_clobbers;
 static regset reg_pending_uses;
+static regset reg_pending_control_uses;
 static enum reg_pending_barrier_mode reg_pending_barrier;
 
 /* Hard registers implicitly clobbered or used (or may be implicitly
@@ -454,10 +467,12 @@ 
 static bitmap_head *true_dependency_cache = NULL;
 static bitmap_head *output_dependency_cache = NULL;
 static bitmap_head *anti_dependency_cache = NULL;
+static bitmap_head *control_dependency_cache = NULL;
 static bitmap_head *spec_dependency_cache = NULL;
 static int cache_size;
 
 static int deps_may_trap_p (const_rtx);
+static void add_dependence_1 (rtx, rtx, enum reg_note);
 static void add_dependence_list (rtx, rtx, int, enum reg_note);
 static void add_dependence_list_and_free (struct deps_desc *, rtx,
 					  rtx *, int, enum reg_note);
@@ -538,6 +553,27 @@ 
   return 0;
 }
 
+/* Return the condition under which INSN does not execute (i.e.  the
+   not-taken condition for a conditional branch), or NULL if we cannot
+   find such a condition.  The caller should make a copy of the condition
+   before using it.  */
+rtx
+sched_get_reverse_condition_uncached (const_rtx insn)
+{
+  bool rev;
+  rtx cond = sched_get_condition_with_rev_uncached (insn, &rev);
+  if (cond == NULL_RTX)
+    return cond;
+  if (!rev)
+    {
+      enum rtx_code revcode = reversed_comparison_code (cond, insn);
+      cond = gen_rtx_fmt_ee (revcode, GET_MODE (cond),
+			     XEXP (cond, 0),
+			     XEXP (cond, 1));
+    }
+  return cond;
+}
+
 /* Caching variant of sched_get_condition_with_rev_uncached.
    We only do actual work the first time we come here for an insn; the
    results are cached in INSN_CACHED_COND and INSN_REVERSE_COND.  */
@@ -861,12 +897,10 @@ 
       int elem_luid = INSN_LUID (pro);
       int insn_luid = INSN_LUID (con);
 
-      gcc_assert (output_dependency_cache != NULL
-		  && anti_dependency_cache != NULL);
-
       if (!bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid)
 	  && !bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid)
-	  && !bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
+	  && !bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid)
+	  && !bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
 	return NULL;
     }
 
@@ -919,7 +953,8 @@ 
 
   gcc_assert (true_dependency_cache != NULL
 	      && output_dependency_cache != NULL
-	      && anti_dependency_cache != NULL);
+	      && anti_dependency_cache != NULL
+	      && control_dependency_cache != NULL);
 
   if (!(current_sched_info->flags & USE_DEPS_LIST))
     {
@@ -931,6 +966,8 @@ 
 	present_dep_type = REG_DEP_OUTPUT;
       else if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
 	present_dep_type = REG_DEP_ANTI;
+      else if (bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
+	present_dep_type = REG_DEP_CONTROL;
       else
 	/* There is no existing dep so it should be created.  */
 	return DEP_CREATED;
@@ -949,6 +986,8 @@ 
 	present_dep_types |= DEP_OUTPUT;
       if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid))
 	present_dep_types |= DEP_ANTI;
+      if (bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid))
+	present_dep_types |= DEP_CONTROL;
 
       if (present_dep_types == 0)
 	/* There is no existing dep so it should be created.  */
@@ -1002,6 +1041,10 @@ 
 	  bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
 	  break;
 
+	case REG_DEP_CONTROL:
+	  bitmap_set_bit (&control_dependency_cache[insn_luid], elem_luid);
+	  break;
+
 	default:
 	  gcc_unreachable ();
 	}
@@ -1016,6 +1059,8 @@ 
 	bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid);
       if (ds & DEP_ANTI)
 	bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid);
+      if (ds & DEP_CONTROL)
+	bitmap_set_bit (&control_dependency_cache[insn_luid], elem_luid);
 
       if (ds & SPECULATIVE)
 	{
@@ -1047,6 +1092,10 @@ 
 	  bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
 	  break;
 
+	case REG_DEP_CONTROL:
+	  bitmap_clear_bit (&control_dependency_cache[insn_luid], elem_luid);
+	  break;
+
 	default:
 	  gcc_unreachable ();
 	}
@@ -1330,8 +1379,7 @@ 
   rtx pro = DEP_PRO (dep);
   rtx con = DEP_CON (dep);
 
-  if ((current_sched_info->flags & DO_SPECULATION)
-      && (DEP_STATUS (dep) & SPECULATIVE))
+  if (dep_spec_p (dep))
     move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con),
 		   INSN_SPEC_BACK_DEPS (con));
   else
@@ -1382,6 +1430,7 @@ 
 
       bitmap_clear_bit (&true_dependency_cache[insn_luid], elem_luid);
       bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid);
+      bitmap_clear_bit (&control_dependency_cache[insn_luid], elem_luid);
       bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid);
 
       if (current_sched_info->flags & DO_SPECULATION)
@@ -1447,6 +1496,48 @@ 
   fprintf (stderr, "\n");
 }
 
+/* A wrapper around add_dependence_1, to add a dependence of CON on
+   PRO, with type DEP_TYPE.  This function implements special handling
+   for REG_DEP_CONTROL dependencies.  For these, we optionally promote
+   the type to REG_DEP_ANTI if we can determine that predication is
+   impossible; otherwise we add additional true dependencies on the
+   INSN_COND_DEPS list of the jump (which PRO must be).  */
+void
+add_dependence (rtx con, rtx pro, enum reg_note dep_type)
+{
+  /* A REG_DEP_CONTROL dependence may be eliminated through predication,
+     so we must also make the insn dependent on the setter of the
+     condition.  */
+  if (dep_type == REG_DEP_CONTROL)
+    {
+      rtx real_pro = pro;
+      rtx other = real_insn_for_shadow (real_pro);
+      rtx cond;
+
+      if (other != NULL_RTX)
+	real_pro = other;
+      cond = sched_get_reverse_condition_uncached (real_pro);
+      /* Verify that the insn does not use a different value in
+	 the condition register than the one that was present at
+	 the jump.  */
+      if (cond == NULL_RTX)
+	dep_type = REG_DEP_ANTI;
+      else if (INSN_CACHED_COND (real_pro) == const_true_rtx)
+	{
+	  HARD_REG_SET uses;
+	  CLEAR_HARD_REG_SET (uses);
+	  note_uses (&PATTERN (con), record_hard_reg_uses, &uses);
+	  if (TEST_HARD_REG_BIT (uses, REGNO (XEXP (cond, 0))))
+	    dep_type = REG_DEP_ANTI;
+	}
+      if (dep_type == REG_DEP_CONTROL)
+	add_dependence_list (con, INSN_COND_DEPS (real_pro), 0,
+			     REG_DEP_TRUE);
+    }
+	  
+  add_dependence_1 (con, pro, dep_type);
+}
+
 /* A convenience wrapper to operate on an entire list.  */
 
 static void
@@ -1662,6 +1753,10 @@ 
   add_dependence_list_and_free (deps, insn,
                                 &deps->last_pending_memory_flush, 1,
                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
+
+  add_dependence_list_and_free (deps, insn, &deps->pending_jump_insns, 1,
+				REG_DEP_ANTI);
+
   if (!deps->readonly)
     {
       free_EXPR_LIST_list (&deps->pending_write_mems);
@@ -1783,10 +1878,12 @@ 
     return REG_DEP_TRUE;
   else if (ds & DEP_OUTPUT)
     return REG_DEP_OUTPUT;
+  else if (ds & DEP_ANTI)
+    return REG_DEP_ANTI;
   else
     {
-      gcc_assert (ds & DEP_ANTI);
-      return REG_DEP_ANTI;
+      gcc_assert (ds & DEP_CONTROL);
+      return REG_DEP_CONTROL;
     }
 }
 
@@ -2394,6 +2491,8 @@ 
 
 	  add_dependence_list (insn, deps->last_pending_memory_flush, 1,
 			       REG_DEP_ANTI);
+	  add_dependence_list (insn, deps->pending_jump_insns, 1,
+			       REG_DEP_CONTROL);
 
           if (!deps->readonly)
             add_insn_mem_dependence (deps, false, insn, dest);
@@ -2541,23 +2640,22 @@ 
 	      }
 
 	    for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
-	      {
-		if (! NON_FLUSH_JUMP_P (u))
-		  add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-		else if (deps_may_trap_p (x))
-		  {
-		    if ((sched_deps_info->generate_spec_deps)
-			&& sel_sched_p () && (spec_info->mask & BEGIN_CONTROL))
-		      {
-			ds_t ds = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
-						MAX_DEP_WEAK);
+	      add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
 
-			note_dep (XEXP (u, 0), ds);
-		      }
-		    else
-		      add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
-		  }
-	      }
+	    for (u = deps->pending_jump_insns; u; u = XEXP (u, 1))
+	      if (deps_may_trap_p (x))
+		{
+		  if ((sched_deps_info->generate_spec_deps)
+		      && sel_sched_p () && (spec_info->mask & BEGIN_CONTROL))
+		    {
+		      ds_t ds = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
+					      MAX_DEP_WEAK);
+		      
+		      note_dep (XEXP (u, 0), ds);
+		    }
+		  else
+		    add_dependence (insn, XEXP (u, 0), REG_DEP_CONTROL);
+		}
 	  }
 
 	/* Always add these dependencies to pending_reads, since
@@ -2776,13 +2874,11 @@ 
 
           if (sched_deps_info->compute_jump_reg_dependencies)
             {
-              regset_head tmp;
-              INIT_REG_SET (&tmp);
+              (*sched_deps_info->compute_jump_reg_dependencies)
+		(insn, reg_pending_control_uses);
 
-              (*sched_deps_info->compute_jump_reg_dependencies) (insn, &tmp);
-
               /* Make latency of jump equal to 0 by using anti-dependence.  */
-              EXECUTE_IF_SET_IN_REG_SET (&tmp, 0, i, rsi)
+              EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
                 {
                   struct deps_reg *reg_last = &deps->reg_last[i];
                   add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI);
@@ -2790,15 +2886,7 @@ 
 				       0, REG_DEP_ANTI);
                   add_dependence_list (insn, reg_last->clobbers, 0,
 				       REG_DEP_ANTI);
-
-                  if (!deps->readonly)
-                    {
-                      reg_last->uses_length++;
-                      reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
-                    }
                 }
-
-              CLEAR_REG_SET (&tmp);
             }
 
 	  /* All memory writes and volatile reads must happen before the
@@ -2828,6 +2916,8 @@ 
 
 	  add_dependence_list (insn, deps->last_pending_memory_flush, 1,
 			       REG_DEP_ANTI);
+	  add_dependence_list (insn, deps->pending_jump_insns, 1,
+			       REG_DEP_ANTI);
 	}
     }
 
@@ -2863,13 +2953,15 @@ 
 			   REG_DEP_ANTI);
 
       for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
-	if (! NON_FLUSH_JUMP_P (u) || !sel_sched_p ())
+	if (!sel_sched_p ())
 	  add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
 
       EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
 	{
 	  struct deps_reg *reg_last = &deps->reg_last[i];
 	  add_dependence_list (insn, reg_last->sets, 1, REG_DEP_ANTI);
+	  /* There's no point in making REG_DEP_CONTROL dependencies for
+	     debug insns.  */
 	  add_dependence_list (insn, reg_last->clobbers, 1, REG_DEP_ANTI);
 
 	  if (!deps->readonly)
@@ -2953,6 +3045,8 @@ 
 	      add_dependence_list (insn, reg_last->implicit_sets, 0,
 				   REG_DEP_ANTI);
 	      add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
+	      add_dependence_list (insn, reg_last->control_uses, 0,
+				   REG_DEP_CONTROL);
 
 	      if (!deps->readonly)
 		{
@@ -2969,6 +3063,8 @@ 
 				   REG_DEP_ANTI);
 	      add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT);
 	      add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
+	      add_dependence_list (insn, reg_last->control_uses, 0,
+				   REG_DEP_CONTROL);
 
 	      if (!deps->readonly)
 		reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
@@ -2989,6 +3085,9 @@ 
 						REG_DEP_ANTI);
 		  add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
 						REG_DEP_ANTI);
+		  add_dependence_list_and_free (deps, insn,
+						&reg_last->control_uses, 0,
+						REG_DEP_ANTI);
 		  add_dependence_list_and_free
 		    (deps, insn, &reg_last->clobbers, 0, REG_DEP_OUTPUT);
 
@@ -3005,6 +3104,8 @@ 
 		  add_dependence_list (insn, reg_last->implicit_sets, 0,
 				       REG_DEP_ANTI);
 		  add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
+		  add_dependence_list (insn, reg_last->control_uses, 0,
+				       REG_DEP_CONTROL);
 		}
 
 	      if (!deps->readonly)
@@ -3027,6 +3128,8 @@ 
 					    REG_DEP_OUTPUT);
 	      add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
 					    REG_DEP_ANTI);
+	      add_dependence_list (insn, reg_last->control_uses, 0,
+				   REG_DEP_CONTROL);
 
 	      if (!deps->readonly)
 		{
@@ -3036,6 +3139,15 @@ 
 		}
 	    }
 	}
+      if (!deps->readonly)
+	{
+	  EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi)
+	    {
+	      struct deps_reg *reg_last = &deps->reg_last[i];
+	      reg_last->control_uses
+		= alloc_INSN_LIST (insn, reg_last->control_uses);
+	    }
+	}
     }
 
   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
@@ -3045,6 +3157,7 @@ 
 	add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI);
 	add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI);
 	add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
+	add_dependence_list (insn, reg_last->control_uses, 0, REG_DEP_ANTI);
 
 	if (!deps->readonly)
 	  reg_last->implicit_sets
@@ -3068,6 +3181,7 @@ 
   CLEAR_REG_SET (reg_pending_uses);
   CLEAR_REG_SET (reg_pending_clobbers);
   CLEAR_REG_SET (reg_pending_sets);
+  CLEAR_REG_SET (reg_pending_control_uses);
   CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers);
   CLEAR_HARD_REG_SET (implicit_reg_pending_uses);
 
@@ -3099,6 +3213,9 @@ 
 	      struct deps_reg *reg_last = &deps->reg_last[i];
 	      add_dependence_list_and_free (deps, insn, &reg_last->uses, 0,
 					    REG_DEP_ANTI);
+	      add_dependence_list_and_free (deps, insn,
+					    &reg_last->control_uses, 0,
+					    REG_DEP_CONTROL);
 	      add_dependence_list_and_free (deps, insn, &reg_last->sets, 0,
 					    reg_pending_barrier == TRUE_BARRIER
 					    ? REG_DEP_TRUE : REG_DEP_ANTI);
@@ -3312,7 +3429,30 @@ 
 
   /* Record the condition for this insn.  */
   if (NONDEBUG_INSN_P (insn))
-    sched_get_condition_with_rev (insn, NULL);
+    {
+      rtx t;
+      sched_get_condition_with_rev (insn, NULL);
+      t = INSN_CACHED_COND (insn);
+      INSN_COND_DEPS (insn) = NULL_RTX;
+      if (reload_completed
+	  && (current_sched_info->flags & DO_PREDICATION)
+	  && COMPARISON_P (t)
+	  && REG_P (XEXP (t, 0))
+	  && CONSTANT_P (XEXP (t, 1)))
+	{
+	  unsigned int regno;
+	  t = XEXP (t, 0);
+	  regno = REGNO (t);
+	  if (hard_regno_nregs[regno][GET_MODE (t)] == 1)
+	    {
+	      struct deps_reg *reg_last = &deps->reg_last[regno];
+	      t = copy_INSN_LIST (reg_last->sets);
+	      t = concat_INSN_LIST (t, reg_last->clobbers);
+	      t = concat_INSN_LIST (t, reg_last->implicit_sets);
+	      INSN_COND_DEPS (insn) = t;
+	    }
+	}
+    }
 
   if (JUMP_P (insn))
     {
@@ -3326,15 +3466,8 @@ 
           if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
             flush_pending_lists (deps, insn, true, true);
           else
-	    {
-	      deps->last_pending_memory_flush
-		= alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
-	      /* Signal to sched_analyze_insn that this jump stands
-		 just for its own, not any other pending memory
-		 reads/writes flush_pending_lists had to flush.  */
-	      PUT_REG_NOTE_KIND (deps->last_pending_memory_flush,
-				 NON_FLUSH_JUMP_KIND);
-	    }
+	    deps->pending_jump_insns
+              = alloc_INSN_LIST (insn, deps->pending_jump_insns);
         }
 
       /* For each insn which shouldn't cross a jump, add a dependence.  */
@@ -3584,6 +3717,7 @@ 
   deps->pending_read_mems = 0;
   deps->pending_write_insns = 0;
   deps->pending_write_mems = 0;
+  deps->pending_jump_insns = 0;
   deps->pending_read_list_length = 0;
   deps->pending_write_list_length = 0;
   deps->pending_flush_length = 0;
@@ -3644,6 +3778,8 @@ 
 	free_INSN_LIST_list (&reg_last->sets);
       if (reg_last->implicit_sets)
 	free_INSN_LIST_list (&reg_last->implicit_sets);
+      if (reg_last->control_uses)
+	free_INSN_LIST_list (&reg_last->control_uses);
       if (reg_last->clobbers)
 	free_INSN_LIST_list (&reg_last->clobbers);
     }
@@ -3672,6 +3808,9 @@ 
   removed = remove_from_both_dependence_lists (insn, &deps->pending_write_insns,
                                                &deps->pending_write_mems);
   deps->pending_write_list_length -= removed;
+
+  removed = remove_from_dependence_list (insn, &deps->pending_jump_insns);
+  deps->pending_flush_length -= removed;
   removed = remove_from_dependence_list (insn, &deps->last_pending_memory_flush);
   deps->pending_flush_length -= removed;
 
@@ -3766,6 +3905,8 @@ 
 					    output_dependency_cache, luid);
       anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
 					  luid);
+      control_dependency_cache = XRESIZEVEC (bitmap_head, control_dependency_cache,
+					  luid);
 
       if (current_sched_info->flags & DO_SPECULATION)
         spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
@@ -3776,6 +3917,7 @@ 
 	  bitmap_initialize (&true_dependency_cache[i], 0);
 	  bitmap_initialize (&output_dependency_cache[i], 0);
 	  bitmap_initialize (&anti_dependency_cache[i], 0);
+	  bitmap_initialize (&control_dependency_cache[i], 0);
 
           if (current_sched_info->flags & DO_SPECULATION)
             bitmap_initialize (&spec_dependency_cache[i], 0);
@@ -3805,6 +3947,7 @@ 
 	  bitmap_clear (&true_dependency_cache[i]);
 	  bitmap_clear (&output_dependency_cache[i]);
 	  bitmap_clear (&anti_dependency_cache[i]);
+	  bitmap_clear (&control_dependency_cache[i]);
 
           if (sched_deps_info->generate_spec_deps)
             bitmap_clear (&spec_dependency_cache[i]);
@@ -3815,6 +3958,8 @@ 
       output_dependency_cache = NULL;
       free (anti_dependency_cache);
       anti_dependency_cache = NULL;
+      free (control_dependency_cache);
+      control_dependency_cache = NULL;
 
       if (sched_deps_info->generate_spec_deps)
         {
@@ -3836,6 +3981,7 @@ 
   reg_pending_sets = ALLOC_REG_SET (&reg_obstack);
   reg_pending_clobbers = ALLOC_REG_SET (&reg_obstack);
   reg_pending_uses = ALLOC_REG_SET (&reg_obstack);
+  reg_pending_control_uses = ALLOC_REG_SET (&reg_obstack);
   reg_pending_barrier = NOT_A_BARRIER;
 
   if (!sel_sched_p () || sched_emulate_haifa_p)
@@ -3860,6 +4006,7 @@ 
   FREE_REG_SET (reg_pending_sets);
   FREE_REG_SET (reg_pending_clobbers);
   FREE_REG_SET (reg_pending_uses);
+  FREE_REG_SET (reg_pending_control_uses);
 }
 
 /* Estimate the weakness of dependence between MEM1 and MEM2.  */
@@ -3893,8 +4040,8 @@ 
 /* Add or update backward dependence between INSN and ELEM with type DEP_TYPE.
    This function can handle same INSN and ELEM (INSN == ELEM).
    It is a convenience wrapper.  */
-void
-add_dependence (rtx insn, rtx elem, enum reg_note dep_type)
+static void
+add_dependence_1 (rtx insn, rtx elem, enum reg_note dep_type)
 {
   ds_t ds;
   bool internal;
@@ -3903,6 +4050,8 @@ 
     ds = DEP_TRUE;
   else if (dep_type == REG_DEP_OUTPUT)
     ds = DEP_OUTPUT;
+  else if (dep_type == REG_DEP_CONTROL)
+    ds = DEP_CONTROL;
   else
     {
       gcc_assert (dep_type == REG_DEP_ANTI);
@@ -4169,10 +4318,12 @@ 
 
   if (s & DEP_TRUE)
     fprintf (f, "DEP_TRUE; ");
+  if (s & DEP_OUTPUT)
+    fprintf (f, "DEP_OUTPUT; ");
   if (s & DEP_ANTI)
     fprintf (f, "DEP_ANTI; ");
-  if (s & DEP_OUTPUT)
-    fprintf (f, "DEP_OUTPUT; ");
+  if (s & DEP_CONTROL)
+    fprintf (f, "DEP_CONTROL; ");
 
   fprintf (f, "}");
 }
@@ -4207,10 +4358,13 @@ 
   else if (dt == REG_DEP_OUTPUT)
     gcc_assert ((ds & DEP_OUTPUT)
 		&& !(ds & DEP_TRUE));
+  else if (dt == REG_DEP_ANTI)
+    gcc_assert ((ds & DEP_ANTI)
+		&& !(ds & (DEP_OUTPUT | DEP_TRUE)));
   else
-    gcc_assert ((dt == REG_DEP_ANTI)
-		&& (ds & DEP_ANTI)
-		&& !(ds & (DEP_OUTPUT | DEP_TRUE)));
+    gcc_assert (dt == REG_DEP_CONTROL
+		&& (ds & DEP_CONTROL)
+		&& !(ds & (DEP_OUTPUT | DEP_ANTI | DEP_TRUE)));
 
   /* HARD_DEP can not appear in dep_status of a link.  */
   gcc_assert (!(ds & HARD_DEP));
Index: gcc/rtl.h
===================================================================
--- gcc/rtl.h	(revision 179045)
+++ gcc/rtl.h	(working copy)
@@ -1932,6 +1932,11 @@ 
 extern int refers_to_regno_p (unsigned int, unsigned int, const_rtx, rtx *);
 extern int reg_overlap_mentioned_p (const_rtx, const_rtx);
 extern const_rtx set_of (const_rtx, const_rtx);
+extern void record_hard_reg_sets (rtx, const_rtx, void *);
+extern void record_hard_reg_uses (rtx *, void *);
+#ifdef HARD_CONST
+extern void find_all_hard_reg_sets (const_rtx, HARD_REG_SET *);
+#endif
 extern void note_stores (const_rtx, void (*) (rtx, const_rtx, void *), void *);
 extern void note_uses (rtx *, void (*) (rtx *, void *), void *);
 extern int dead_or_set_p (const_rtx, const_rtx);
@@ -2027,12 +2032,14 @@ 
 
 /* lists.c */
 
-extern void free_EXPR_LIST_list		(rtx *);
-extern void free_INSN_LIST_list		(rtx *);
-extern void free_EXPR_LIST_node		(rtx);
-extern void free_INSN_LIST_node		(rtx);
-extern rtx alloc_INSN_LIST			(rtx, rtx);
-extern rtx alloc_EXPR_LIST			(int, rtx, rtx);
+extern void free_EXPR_LIST_list (rtx *);
+extern void free_INSN_LIST_list (rtx *);
+extern void free_EXPR_LIST_node (rtx);
+extern void free_INSN_LIST_node (rtx);
+extern rtx alloc_INSN_LIST (rtx, rtx);
+extern rtx copy_INSN_LIST (rtx);
+extern rtx concat_INSN_LIST (rtx, rtx);
+extern rtx alloc_EXPR_LIST (int, rtx, rtx);
 extern void remove_free_INSN_LIST_elem (rtx, rtx *);
 extern rtx remove_list_elem (rtx, rtx *);
 extern rtx remove_free_INSN_LIST_node (rtx *);
Index: gcc/sched-int.h
===================================================================
--- gcc/sched-int.h	(revision 179045)
+++ gcc/sched-int.h	(working copy)
@@ -424,6 +424,7 @@ 
   rtx uses;
   rtx sets;
   rtx implicit_sets;
+  rtx control_uses;
   rtx clobbers;
   int uses_length;
   int clobbers_length;
@@ -453,6 +454,9 @@ 
   /* An EXPR_LIST containing all MEM rtx's which are pending writes.  */
   rtx pending_write_mems;
 
+  /* An INSN_LIST containing all jump insns.  */
+  rtx pending_jump_insns;
+
   /* We must prevent the above lists from ever growing too large since
      the number of dependencies produced is at least O(N*N),
      and execution time is at least O(4*N*N), as a function of the
@@ -464,8 +468,9 @@ 
   /* Indicates the length of the pending_write list.  */
   int pending_write_list_length;
 
-  /* Length of the pending memory flush list. Large functions with no
-     calls may build up extremely large lists.  */
+  /* Length of the pending memory flush list plus the length of the pending
+     jump insn list.  Large functions with no calls may build up extremely
+     large lists.  */
   int pending_flush_length;
 
   /* The last insn upon which all memory references must depend.
@@ -699,6 +704,10 @@ 
      condition that has been clobbered by a subsequent insn.  */
   rtx cond;
 
+  /* For a conditional insn, a list of insns that could set the condition
+     register.  Used when generating control dependencies.  */
+  rtx cond_deps;
+
   /* True if the condition in 'cond' should be reversed to get the actual
      condition.  */
   unsigned int reverse_cond : 1;
@@ -799,6 +808,10 @@ 
      real insns following them.  */
   unsigned int shadow_p : 1;
 
+  /* Used internally in unschedule_insns_until to mark insns that must have
+     their TODO_SPEC recomputed.  */
+  unsigned int must_recompute_spec : 1;
+
   /* '> 0' if priority is valid,
      '== 0' if priority was not yet computed,
      '< 0' if priority in invalid and should be recomputed.  */
@@ -819,6 +832,10 @@ 
   /* Original pattern of the instruction.  */
   rtx orig_pat;
 
+  /* For insns with DEP_CONTROL dependencies, the predicated pattern if it
+     was ever successfully constructed.  */
+  rtx predicated_pat;
+
   /* The following array contains info how the insn increases register
      pressure.  There is an element for each cover class of pseudos
      referenced in insns.  */
@@ -880,6 +897,7 @@ 
 #define INSN_SPEC_BACK_DEPS(INSN) (HDID (INSN)->spec_back_deps)
 #define INSN_CACHED_COND(INSN)	(HDID (INSN)->cond)
 #define INSN_REVERSE_COND(INSN) (HDID (INSN)->reverse_cond)
+#define INSN_COND_DEPS(INSN)	(HDID (INSN)->cond_deps)
 #define CANT_MOVE(INSN)	(HDID (INSN)->cant_move)
 #define CANT_MOVE_BY_LUID(LUID)	(VEC_index (haifa_deps_insn_data_def, h_d_i_d, \
                                             LUID)->cant_move)
@@ -893,6 +911,7 @@ 
 #define CHECK_SPEC(INSN) (HID (INSN)->check_spec)
 #define RECOVERY_BLOCK(INSN) (HID (INSN)->recovery_block)
 #define ORIG_PAT(INSN) (HID (INSN)->orig_pat)
+#define PREDICATED_PAT(INSN) (HID (INSN)->predicated_pat)
 
 /* INSN is either a simple or a branchy speculation check.  */
 #define IS_SPECULATION_CHECK_P(INSN) \
@@ -932,10 +951,11 @@ 
 /* We exclude sign bit.  */
 #define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1)
 
-/* First '4' stands for 3 dep type bits and HARD_DEP bit.
+/* First '6' stands for 4 dep type bits and the HARD_DEP and DEP_CANCELLED
+   bits.
    Second '4' stands for BEGIN_{DATA, CONTROL}, BE_IN_{DATA, CONTROL}
    dep weakness.  */
-#define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 4) / 4)
+#define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 6) / 4)
 
 /* Mask of speculative weakness in dep_status.  */
 #define DEP_WEAK_MASK ((1 << BITS_PER_DEP_WEAK) - 1)
@@ -1009,14 +1029,17 @@ 
 #define DEP_TRUE (((ds_t) 1) << (BE_IN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK))
 #define DEP_OUTPUT (DEP_TRUE << 1)
 #define DEP_ANTI (DEP_OUTPUT << 1)
+#define DEP_CONTROL (DEP_ANTI << 1)
 
-#define DEP_TYPES (DEP_TRUE | DEP_OUTPUT | DEP_ANTI)
+#define DEP_TYPES (DEP_TRUE | DEP_OUTPUT | DEP_ANTI | DEP_CONTROL)
 
 /* Instruction has non-speculative dependence.  This bit represents the
    property of an instruction - not the one of a dependence.
    Therefore, it can appear only in TODO_SPEC field of an instruction.  */
-#define HARD_DEP (DEP_ANTI << 1)
+#define HARD_DEP (DEP_CONTROL << 1)
 
+#define DEP_CANCELLED (HARD_DEP << 1)
+
 /* This represents the results of calling sched-deps.c functions,
    which modify dependencies.  */
 enum DEPS_ADJUST_RESULT {
@@ -1041,7 +1064,8 @@ 
      Requires USE_DEPS_LIST set.  */
   DO_SPECULATION = USE_DEPS_LIST << 1,
   DO_BACKTRACKING = DO_SPECULATION << 1,
-  SCHED_RGN = DO_BACKTRACKING << 1,
+  DO_PREDICATION = DO_BACKTRACKING << 1,
+  SCHED_RGN = DO_PREDICATION << 1,
   SCHED_EBB = SCHED_RGN << 1,
   /* Scheduler can possibly create new basic blocks.  Used for assertions.  */
   NEW_BBS = SCHED_EBB << 1,
@@ -1202,6 +1226,7 @@ 
 
 
 /* Functions in sched-deps.c.  */
+extern rtx sched_get_reverse_condition_uncached (const_rtx);
 extern bool sched_insns_conditions_mutex_p (const_rtx, const_rtx);
 extern bool sched_insn_is_legitimate_for_speculation_p (const_rtx, ds_t);
 extern void add_dependence (rtx, rtx, enum reg_note);
@@ -1331,6 +1356,7 @@ 
 extern bool sched_no_dce;
 
 extern void record_delay_slot_pair (rtx, rtx, int);
+extern rtx real_insn_for_shadow (rtx);
 extern void free_delay_pairs (void);
 extern void add_delay_dependencies (rtx);
 extern bool sched_is_disabled_for_current_region_p (void);
@@ -1520,3 +1546,4 @@ 
 extern void print_value (char *, const_rtx, int);
 
 #endif /* GCC_SCHED_INT_H */
+
Index: gcc/sched-rgn.c
===================================================================
--- gcc/sched-rgn.c	(revision 179045)
+++ gcc/sched-rgn.c	(working copy)
@@ -234,7 +234,6 @@ 
 static void compute_block_dependences (int);
 
 static void schedule_region (int);
-static rtx concat_INSN_LIST (rtx, rtx);
 static void concat_insn_mem_list (rtx, rtx, rtx *, rtx *);
 static void propagate_deps (int, struct deps_desc *);
 static void free_pending_lists (void);
@@ -2552,20 +2551,6 @@ 
 
 static struct deps_desc *bb_deps;
 
-/* Duplicate the INSN_LIST elements of COPY and prepend them to OLD.  */
-
-static rtx
-concat_INSN_LIST (rtx copy, rtx old)
-{
-  rtx new_rtx = old;
-  for (; copy ; copy = XEXP (copy, 1))
-    {
-      new_rtx = alloc_INSN_LIST (XEXP (copy, 0), new_rtx);
-      PUT_REG_NOTE_KIND (new_rtx, REG_NOTE_KIND (copy));
-    }
-  return new_rtx;
-}
-
 static void
 concat_insn_mem_list (rtx copy_insns, rtx copy_mems, rtx *old_insns_p,
 		      rtx *old_mems_p)
@@ -2619,6 +2604,9 @@ 
                         &succ_deps->pending_write_insns,
                         &succ_deps->pending_write_mems);
 
+  succ_deps->pending_jump_insns
+    = concat_INSN_LIST (pred_deps->pending_jump_insns,
+                        succ_deps->pending_jump_insns);
   succ_deps->last_pending_memory_flush
     = concat_INSN_LIST (pred_deps->last_pending_memory_flush,
                         succ_deps->last_pending_memory_flush);
@@ -2670,12 +2658,14 @@ 
   bb_deps[bb].pending_read_mems = pred_deps->pending_read_mems;
   bb_deps[bb].pending_write_insns = pred_deps->pending_write_insns;
   bb_deps[bb].pending_write_mems = pred_deps->pending_write_mems;
+  bb_deps[bb].pending_jump_insns = pred_deps->pending_jump_insns;
 
   /* Can't allow these to be freed twice.  */
   pred_deps->pending_read_insns = 0;
   pred_deps->pending_read_mems = 0;
   pred_deps->pending_write_insns = 0;
   pred_deps->pending_write_mems = 0;
+  pred_deps->pending_jump_insns = 0;
 }
 
 /* Compute dependences inside bb.  In a multiple blocks region:
@@ -2754,6 +2744,7 @@ 
       free_INSN_LIST_list (&bb_deps[bb].pending_write_insns);
       free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems);
       free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems);
+      free_INSN_LIST_list (&bb_deps[bb].pending_jump_insns);
     }
 }
 
Index: gcc/config/c6x/c6x.c
===================================================================
--- gcc/config/c6x/c6x.c	(revision 179045)
+++ gcc/config/c6x/c6x.c	(working copy)
@@ -3500,7 +3500,7 @@ 
 
   if (*flags & SCHED_EBB)
     {
-      *flags |= DO_BACKTRACKING;
+      *flags |= DO_BACKTRACKING | DO_PREDICATION;
     }
 
   spec_info->mask = 0;
Index: gcc/reg-notes.def
===================================================================
--- gcc/reg-notes.def	(revision 179045)
+++ gcc/reg-notes.def	(working copy)
@@ -92,6 +92,7 @@ 
    respectively.  */
 REG_NOTE (DEP_OUTPUT)
 REG_NOTE (DEP_ANTI)
+REG_NOTE (DEP_CONTROL)
 
 /* REG_BR_PROB is attached to JUMP_INSNs and CALL_INSNs.  It has an
    integer value.  For jumps, it is the probability that this is a