diff --git a/gcc/common.opt b/gcc/common.opt
index d1f286f..3a7114d 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -1695,6 +1695,10 @@ fsel-sched-reschedule-pipelined
 Common Report Var(flag_sel_sched_reschedule_pipelined) Init(0) Optimization
 Reschedule pipelined regions without pipelining
 
+fsel-sched-predication
+Common Report Var(flag_sel_sched_predication) Init(0) Optimization
+Perform predication in selective scheduling
+
 ; sched_stalled_insns means that insns can be moved prematurely from the queue
 ; of stalled insns into the ready list.
 fsched-stalled-insns
diff --git a/gcc/config/ia64/ia64.c b/gcc/config/ia64/ia64.c
index 78d2441..94dbff2 100644
--- a/gcc/config/ia64/ia64.c
+++ b/gcc/config/ia64/ia64.c
@@ -7640,6 +7640,15 @@ get_mode_no_for_insn (rtx insn)
   int mode_no;
   bool extend_p;
 
+  /* Extract mode of predicated loads to allow transforming them into a
+     speculative form.  */
+  if (flag_sel_sched_predication && GET_CODE (PATTERN (insn)) == COND_EXEC)
+    {
+      rtx cond = COND_EXEC_TEST (PATTERN (insn));
+      if (GET_CODE (cond) != UNSPEC)
+	insn = make_insn_raw (COND_EXEC_CODE (PATTERN (insn)));
+    }
+
   extract_insn_cached (insn);
 
   /* We use WHICH_ALTERNATIVE only after reload.  This will
diff --git a/gcc/rtl.h b/gcc/rtl.h
index f2c2983..ec76b0c 100644
--- a/gcc/rtl.h
+++ b/gcc/rtl.h
@@ -1378,6 +1378,16 @@ do {									\
 #define COND_EXEC_TEST(RTX) XCEXP (RTX, 0, COND_EXEC)
 #define COND_EXEC_CODE(RTX) XCEXP (RTX, 1, COND_EXEC)
 
+/* Obtain a pointer to SET_SRC or SET_DEST of a SET which may be wrapped
+   in a COND_EXEC.  */
+#define COND_SET_SRC_PTR(x) (GET_CODE (x) == COND_EXEC \
+			     ? &SET_SRC (COND_EXEC_CODE (x)) \
+			     : &SET_SRC (x))
+
+#define COND_SET_DEST_PTR(x) (GET_CODE (x) == COND_EXEC \
+			      ? &SET_DEST (COND_EXEC_CODE (x)) \
+			      : &SET_DEST (x))
+
 /* 1 if RTX is a symbol_ref that addresses this function's rtl
    constants pool.  */
 #define CONSTANT_POOL_ADDRESS_P(RTX)					\
diff --git a/gcc/sched-deps.c b/gcc/sched-deps.c
index a82df5d..92f4b7c 100644
--- a/gcc/sched-deps.c
+++ b/gcc/sched-deps.c
@@ -459,7 +459,6 @@ static void sched_analyze_2 (struct deps_desc *, rtx, rtx);
 static void sched_analyze_insn (struct deps_desc *, rtx, rtx);
 
 static bool sched_has_condition_p (const_rtx);
-static int conditions_mutex_p (const_rtx, const_rtx, bool, bool);
 
 static enum DEPS_ADJUST_RESULT maybe_add_or_update_dep_1 (dep_t, bool,
 							  rtx, rtx);
@@ -571,7 +570,7 @@ sched_has_condition_p (const_rtx insn)
 
 /* Return nonzero if conditions COND1 and COND2 can never be both true.  */
 static int
-conditions_mutex_p (const_rtx cond1, const_rtx cond2, bool rev1, bool rev2)
+conditions_mutex_with_rev_p (const_rtx cond1, const_rtx cond2, bool rev1, bool rev2)
 {
   if (COMPARISON_P (cond1)
       && COMPARISON_P (cond2)
@@ -585,6 +584,27 @@ conditions_mutex_p (const_rtx cond1, const_rtx cond2, bool rev1, bool rev2)
   return 0;
 }
 
+/* Return true iff COND1 and COND2 are opposite.  */
+bool
+conditions_mutex_p (const_rtx cond1, const_rtx cond2)
+{
+  return conditions_mutex_with_rev_p (cond1, cond2, false, false);
+}
+
+/* Return true iff COND1 and COND2 are equal.  */
+bool
+conditions_same_p (const_rtx cond1, const_rtx cond2)
+{
+  return conditions_mutex_with_rev_p (cond1, cond2, false, true);
+}
+
+/* Return true iff COND1 and COND2 are either equal or opposite.  */
+bool
+conditions_same_or_mutex_p (const_rtx cond1, const_rtx cond2)
+{
+  return conditions_mutex_p (cond1, cond2) || conditions_same_p (cond1, cond2);
+}
+
 /* Return true if insn1 and insn2 can never depend on one another because
    the conditions under which they are executed are mutually exclusive.  */
 bool
@@ -600,7 +620,7 @@ sched_insns_conditions_mutex_p (const_rtx insn1, const_rtx insn2)
       cond1 = sched_get_condition_with_rev (insn1, &rev1);
       cond2 = sched_get_condition_with_rev (insn2, &rev2);
       if (cond1 && cond2
-	  && conditions_mutex_p (cond1, cond2, rev1, rev2)
+	  && conditions_mutex_with_rev_p (cond1, cond2, rev1, rev2)
 	  /* Make sure first instruction doesn't affect condition of second
 	     instruction if switched.  */
 	  && !modified_in_p (cond1, insn2)
@@ -2673,6 +2693,10 @@ sched_analyze_insn (struct deps_desc *deps, rtx x, rtx insn)
 	 false dependencies.  */
       x = COND_EXEC_CODE (x);
       code = GET_CODE (x);
+
+      if (flag_sel_sched_predication)
+	can_start_lhs_rhs_p = (NONJUMP_INSN_P (insn)
+			       && code == SET);
     }
   if (code == SET || code == CLOBBER)
     {
diff --git a/gcc/sched-int.h b/gcc/sched-int.h
index b8240d7..a81a7a1 100644
--- a/gcc/sched-int.h
+++ b/gcc/sched-int.h
@@ -1172,6 +1172,9 @@ extern struct sched_deps_info_def *sched_deps_info;
 
 
 /* Functions in sched-deps.c.  */
+extern bool conditions_mutex_p (const_rtx, const_rtx);
+extern bool conditions_same_p (const_rtx, const_rtx);
+extern bool conditions_same_or_mutex_p (const_rtx, 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);
diff --git a/gcc/sel-sched-ir.c b/gcc/sel-sched-ir.c
index 1a73308..85e469a 100644
--- a/gcc/sel-sched-ir.c
+++ b/gcc/sel-sched-ir.c
@@ -1584,6 +1584,8 @@ bool
 vinsn_equal_p (vinsn_t x, vinsn_t y)
 {
   rtx_equal_p_callback_function repcf;
+  rtx condx = VINSN_COND (x);
+  rtx condy = VINSN_COND (y);
 
   if (x == y)
     return true;
@@ -1594,6 +1596,11 @@ vinsn_equal_p (vinsn_t x, vinsn_t y)
   if (VINSN_HASH (x) != VINSN_HASH (y))
     return false;
 
+  /* If only one vinsn is predicated, they are not equal.  If both are
+     predicated, the conditions need to be equivalent.  */
+  if (condx != condy && !(condx && condy && conditions_same_p (condx, condy)))
+    return false;
+
   repcf = targetm.sched.skip_rtx_p ? skip_unspecs_callback : NULL;
   if (VINSN_SEPARABLE_P (x))
     {
@@ -1607,6 +1614,39 @@ vinsn_equal_p (vinsn_t x, vinsn_t y)
   return rtx_equal_p_cb (VINSN_PATTERN (x), VINSN_PATTERN (y), repcf);
 }
 
+/* Compare two vinsns as rhses if possible and as vinsns otherwise.
+   Ignore potential differences in conditions.  */
+bool
+vinsn_equal_skip_cond_p (vinsn_t x, vinsn_t y)
+{
+  rtx_equal_p_callback_function repcf;
+  rtx patx = VINSN_PATTERN (x);
+  rtx paty = VINSN_PATTERN (y);
+
+  if (x == y)
+    return true;
+
+  if (VINSN_TYPE (x) != VINSN_TYPE (y))
+    return false;
+
+  repcf = targetm.sched.skip_rtx_p ? skip_unspecs_callback : NULL;
+  if (VINSN_SEPARABLE_P (x))
+    {
+      /* Compare RHSes of VINSNs.  */
+      gcc_assert (VINSN_RHS (x));
+      gcc_assert (VINSN_RHS (y));
+
+      return rtx_equal_p_cb (VINSN_RHS (x), VINSN_RHS (y), repcf);
+    }
+
+  if (GET_CODE (patx) == COND_EXEC)
+    patx = COND_EXEC_CODE (patx);
+
+  if (GET_CODE (paty) == COND_EXEC)
+    paty = COND_EXEC_CODE (paty);
+
+  return rtx_equal_p_cb (patx, paty, repcf);
+}
 
 /* Functions for working with expressions.  */
 
@@ -1616,8 +1656,8 @@ init_expr (expr_t expr, vinsn_t vi, int spec, int use, int priority,
 	   int sched_times, int orig_bb_index, ds_t spec_done_ds,
 	   ds_t spec_to_check_ds, int orig_sched_cycle,
 	   VEC(expr_history_def, heap) *history, signed char target_available,
-           bool was_substituted, bool was_renamed, bool needs_spec_check_p,
-           bool cant_move)
+           bool was_substituted, bool was_renamed, bool was_predicated,
+	   bool needs_spec_check_p, bool cant_move)
 {
   vinsn_attach (vi);
 
@@ -1638,6 +1678,7 @@ init_expr (expr_t expr, vinsn_t vi, int spec, int use, int priority,
   EXPR_TARGET_AVAILABLE (expr) = target_available;
   EXPR_WAS_SUBSTITUTED (expr) = was_substituted;
   EXPR_WAS_RENAMED (expr) = was_renamed;
+  EXPR_WAS_PREDICATED (expr) = was_predicated;
   EXPR_NEEDS_SPEC_CHECK_P (expr) = needs_spec_check_p;
   EXPR_CANT_MOVE (expr) = cant_move;
 }
@@ -1672,8 +1713,8 @@ copy_expr (expr_t to, expr_t from)
 	     EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from),
 	     EXPR_ORIG_SCHED_CYCLE (from), NULL,
              EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
-             EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
-             EXPR_CANT_MOVE (from));
+             EXPR_WAS_RENAMED (from), EXPR_WAS_PREDICATED (from),
+	     EXPR_NEEDS_SPEC_CHECK_P (from), EXPR_CANT_MOVE (from));
   copy_history_of_changes (to, from);
 }
 
@@ -1686,8 +1727,8 @@ copy_expr_onside (expr_t to, expr_t from)
 	     EXPR_PRIORITY (from), EXPR_SCHED_TIMES (from), 0,
 	     EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from), 0, NULL,
 	     EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
-	     EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
-             EXPR_CANT_MOVE (from));
+	     EXPR_WAS_RENAMED (from), EXPR_WAS_PREDICATED (from),
+	     EXPR_NEEDS_SPEC_CHECK_P (from), EXPR_CANT_MOVE (from));
 }
 
 /* Prepare the expr of INSN for scheduling.  Used when moving insn and when
@@ -1841,6 +1882,11 @@ merge_expr_data (expr_t to, expr_t from, insn_t split_point)
 
   merge_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
 		      EXPR_HISTORY_OF_CHANGES (from));
+
+  if (EXPR_COND (to) || EXPR_COND (from))
+    gcc_assert (EXPR_COND (to) && EXPR_COND (from)
+		&& conditions_same_p (EXPR_COND (to), EXPR_COND (from)));
+
   update_target_availability (to, from, split_point);
   update_speculative_bits (to, from, split_point);
 }
@@ -2071,7 +2117,7 @@ av_set_add (av_set_t *setp, expr_t expr)
 }
 
 /* Same, but do not copy EXPR.  */
-static void
+void
 av_set_add_nocopy (av_set_t *setp, expr_t expr)
 {
   av_set_t elem;
@@ -2189,7 +2235,7 @@ av_set_copy (av_set_t set)
 /* Join two av sets that do not have common elements by attaching second set
    (pointed to by FROMP) to the end of first set (TO_TAILP must point to
    _AV_SET_NEXT of first set's last element).  */
-static void
+void
 join_distinct_sets (av_set_t *to_tailp, av_set_t *fromp)
 {
   gcc_assert (*to_tailp == NULL);
@@ -2197,6 +2243,26 @@ join_distinct_sets (av_set_t *to_tailp, av_set_t *fromp)
   *fromp = NULL;
 }
 
+/* Return the pointer to _AV_SET_NEXT of the last element of AV.  */
+static av_set_t *
+av_set_tail (av_set_t *av)
+{
+  av_set_iterator avi;
+  expr_t expr;
+
+  FOR_EACH_EXPR (expr, avi, *av)
+    {}
+  return avi.lp;
+}
+
+/* Concatenate two av sets that do not have common elements by attaching second set
+   (pointed to by FROMP) to the end of first set (pointed to by TOP).  */
+void
+av_set_concat (av_set_t *top, av_set_t *fromp)
+{
+  join_distinct_sets (av_set_tail (top), fromp);
+}
+
 /* Makes set pointed to by TO to be the union of TO and FROM.  Clear av_set
    pointed to by FROMP afterwards.  */
 void
@@ -2221,22 +2287,41 @@ av_set_union_and_clear (av_set_t *top, av_set_t *fromp, insn_t insn)
 }
 
 /* Same as above, but also update availability of target register in
-   TOP judging by TO_LV_SET and FROM_LV_SET.  */
+   TOP judging by TO_LV_SET and FROM_LV_SET.  INSN is the conditional branch,
+   and TO_FALLTHRU_P indicates whether TOP is from the fallthrough arm.  */
 void
 av_set_union_and_live (av_set_t *top, av_set_t *fromp, regset to_lv_set,
-                       regset from_lv_set, insn_t insn)
+                       regset from_lv_set, insn_t insn, bool to_fallthru_p)
 {
   expr_t expr1;
   av_set_iterator i;
-  av_set_t *to_tailp, in_both_set = NULL;
+  av_set_t *to_tailp, in_both_set = NULL, pred_forms_set = NULL;
+  rtx cond = INSN_COND (insn), to_cond, from_cond;
+
+  /* It may happen that cond is not NULL for a speculation check when that
+     check itself was predicated earlier.  Unlike for normal jumps, we cannot
+     use its condition for predication.  */
+  if (sel_insn_is_speculation_check (insn))
+    cond = NULL;
+
+  if (cond)
+    {
+      rtx inv_cond = reversed_comparison (cond, GET_MODE (cond));
+      to_cond = to_fallthru_p ? cond : inv_cond;
+      from_cond = to_fallthru_p ? inv_cond : cond;
+    }
+  else
+    to_cond = from_cond = NULL;
 
   /* Delete from TOP all expres, that present in FROMP.  */
   FOR_EACH_EXPR_1 (expr1, i, top)
     {
       expr_t expr2 = av_set_lookup_and_remove (fromp, EXPR_VINSN (expr1));
+      maybe_predicate_expr_into (&pred_forms_set, expr1, insn, to_cond);
 
       if (expr2)
 	{
+	  maybe_predicate_expr_into (&pred_forms_set, expr2, insn, from_cond);
           /* It may be that the expressions have different destination
              registers, in which case we need to check liveness here.  */
           if (EXPR_SEPARABLE_P (expr1))
@@ -2266,12 +2351,17 @@ av_set_union_and_live (av_set_t *top, av_set_t *fromp, regset to_lv_set,
     }
   to_tailp = i.lp;
 
+  av_set_concat (&pred_forms_set, &in_both_set);
+
   /* These expressions are not present in TOP.  Check liveness
      restrictions on TO_LV_SET.  */
   FOR_EACH_EXPR (expr1, i, *fromp)
-    set_unavailable_target_for_expr (expr1, to_lv_set);
+    {
+      maybe_predicate_expr_into (&pred_forms_set, expr1, insn, from_cond);
+      set_unavailable_target_for_expr (expr1, to_lv_set);
+    }
 
-  join_distinct_sets (i.lp, &in_both_set);
+  join_distinct_sets (i.lp, &pred_forms_set);
   join_distinct_sets (to_tailp, fromp);
 }
 
@@ -2577,6 +2667,8 @@ static void
 setup_id_lhs_rhs (idata_t id, insn_t insn, bool force_unique_p)
 {
   rtx pat = PATTERN (insn);
+  if (flag_sel_sched_predication && GET_CODE (pat) == COND_EXEC)
+    pat = COND_EXEC_CODE (pat);
 
   if (NONJUMP_INSN_P (insn)
       && GET_CODE (pat) == SET
@@ -2695,6 +2787,29 @@ setup_id_reg_sets (idata_t id, insn_t insn)
   return_regset_to_pool (tmp);
 }
 
+/* Setup predicate data for INSN in ID.  */
+static void
+setup_id_cond (idata_t id, insn_t insn)
+{
+  if (flag_sel_sched_predication)
+    {
+      rtx pat = PATTERN (insn);
+      if (GET_CODE (pat) == COND_EXEC)
+	IDATA_COND (id) = COND_EXEC_TEST (pat);
+      else if (GET_CODE (pat) == SET && SET_DEST (pat) == pc_rtx
+	       && GET_CODE (SET_SRC (pat)) == IF_THEN_ELSE)
+	{
+	  rtx cond = XEXP (SET_SRC (pat), 0);
+	  if (GET_CODE (XEXP (cond, 0)) != UNSPEC)
+	    {
+	      if (XEXP (SET_SRC (pat), 2) == pc_rtx)
+		cond = reversed_comparison (cond, GET_MODE (cond));
+	      IDATA_COND (id) = cond;
+	    }
+	}
+    }
+}
+
 /* Initialize instruction data for INSN in ID using DF's data.  */
 static void
 init_id_from_df (idata_t id, insn_t insn, bool force_unique_p)
@@ -2703,6 +2818,7 @@ init_id_from_df (idata_t id, insn_t insn, bool force_unique_p)
 
   setup_id_for_insn (id, insn, force_unique_p);
   setup_id_lhs_rhs (id, insn, force_unique_p);
+  setup_id_cond (id, insn);
 
   if (INSN_NOP_P (insn))
     return;
@@ -2735,6 +2851,8 @@ deps_init_id (idata_t id, insn_t insn, bool force_unique_p)
 
   deps_analyze_insn (dc, insn);
 
+  setup_id_cond (id, insn);
+
   free_deps (dc);
 
   deps_init_id_data.id = NULL;
@@ -2996,7 +3114,7 @@ init_global_and_expr_for_insn (insn_t insn)
     /* Initialize INSN's expr.  */
     init_expr (INSN_EXPR (insn), vinsn_create (insn, force_unique_p), 0,
 	       REG_BR_PROB_BASE, INSN_PRIORITY (insn), 0, BLOCK_NUM (insn),
-	       spec_done_ds, 0, 0, NULL, true, false, false, false,
+	       spec_done_ds, 0, 0, NULL, true, false, false, false, false,
                CANT_MOVE (insn));
   }
 
@@ -3567,6 +3685,10 @@ get_dest_and_mode (rtx insn, rtx *dst_loc, enum machine_mode *mode)
   rtx pat = PATTERN (insn);
 
   gcc_assert (dst_loc);
+
+  if (GET_CODE (pat) == COND_EXEC)
+    pat = COND_EXEC_CODE (pat);
+
   gcc_assert (GET_CODE (pat) == SET);
 
   *dst_loc = SET_DEST (pat);
@@ -4224,7 +4349,7 @@ init_simplejump_data (insn_t insn)
 {
   init_expr (INSN_EXPR (insn), vinsn_create (insn, false), 0,
 	     REG_BR_PROB_BASE, 0, 0, 0, 0, 0, 0, NULL, true, false, false,
-	     false, true);
+	     false, false, true);
   INSN_SEQNO (insn) = get_seqno_for_a_jump (insn);
   init_first_time_insn_data (insn);
 }
diff --git a/gcc/sel-sched-ir.h b/gcc/sel-sched-ir.h
index bcb47c6..dc5ee76 100644
--- a/gcc/sel-sched-ir.h
+++ b/gcc/sel-sched-ir.h
@@ -73,7 +73,8 @@ typedef _xlist_t ilist_t;
 enum local_trans_type
   {
     TRANS_SUBSTITUTION,
-    TRANS_SPECULATION
+    TRANS_SPECULATION,
+    TRANS_PREDICATION
   };
 
 /* This struct is used to record the history of expression's
@@ -166,6 +167,9 @@ struct _expr
   /* True when the expression was renamed.  */
   BOOL_BITFIELD was_renamed : 1;
 
+  /* True when the expression was predicated.  */
+  BOOL_BITFIELD was_predicated : 1;
+
   /* True when expression can't be moved.  */
   BOOL_BITFIELD cant_move : 1;
 };
@@ -178,6 +182,7 @@ typedef expr_def *expr_t;
 #define EXPR_PATTERN(EXPR) (VINSN_PATTERN (EXPR_VINSN (EXPR)))
 #define EXPR_LHS(EXPR) (VINSN_LHS (EXPR_VINSN (EXPR)))
 #define EXPR_RHS(EXPR) (VINSN_RHS (EXPR_VINSN (EXPR)))
+#define EXPR_COND(EXPR) (VINSN_COND (EXPR_VINSN (EXPR)))
 #define EXPR_TYPE(EXPR) (VINSN_TYPE (EXPR_VINSN (EXPR)))
 #define EXPR_SEPARABLE_P(EXPR) (VINSN_SEPARABLE_P (EXPR_VINSN (EXPR)))
 
@@ -195,6 +200,7 @@ typedef expr_def *expr_t;
 #define EXPR_NEEDS_SPEC_CHECK_P(EXPR) ((EXPR)->needs_spec_check_p)
 #define EXPR_WAS_SUBSTITUTED(EXPR) ((EXPR)->was_substituted)
 #define EXPR_WAS_RENAMED(EXPR) ((EXPR)->was_renamed)
+#define EXPR_WAS_PREDICATED(EXPR) ((EXPR)->was_predicated)
 #define EXPR_CANT_MOVE(EXPR) ((EXPR)->cant_move)
 
 #define EXPR_WAS_CHANGED(EXPR) (VEC_length (expr_history_def, \
@@ -593,6 +599,9 @@ struct idata_def
   /* If insn is a SET, this is its right hand side.  */
   rtx rhs;
 
+  /* If insn is conditionally executed, this is its controlling predicate.  */
+  rtx cond;
+
   /* Registers that are set/used by this insn.  This info is now gathered
      via sched-deps.c.  The downside of this is that we also use live info
      from flow that is accumulated in the basic blocks.  These two infos
@@ -612,6 +621,7 @@ struct idata_def
 #define IDATA_TYPE(ID) ((ID)->type)
 #define IDATA_LHS(ID) ((ID)->lhs)
 #define IDATA_RHS(ID) ((ID)->rhs)
+#define IDATA_COND(ID) ((ID)->cond)
 #define IDATA_REG_SETS(ID) ((ID)->reg_sets)
 #define IDATA_REG_USES(ID) ((ID)->reg_uses)
 #define IDATA_REG_CLOBBERS(ID) ((ID)->reg_clobbers)
@@ -666,6 +676,7 @@ struct vinsn_def
 #define VINSN_UNIQUE_P(VI) (!VINSN_CLONABLE_P (VI))
 #define VINSN_LHS(VI) (IDATA_LHS (VINSN_ID (VI)))
 #define VINSN_RHS(VI) (IDATA_RHS (VINSN_ID (VI)))
+#define VINSN_COND(VI) (IDATA_COND (VINSN_ID (VI)))
 #define VINSN_REG_SETS(VI) (IDATA_REG_SETS (VINSN_ID (VI)))
 #define VINSN_REG_USES(VI) (IDATA_REG_USES (VINSN_ID (VI)))
 #define VINSN_REG_CLOBBERS(VI) (IDATA_REG_CLOBBERS (VINSN_ID (VI)))
@@ -789,6 +800,7 @@ extern sel_insn_data_def insn_sid (insn_t);
 #define INSN_SIMPLEJUMP_P(INSN) (INSN_TYPE (INSN) == PC)
 #define INSN_LHS(INSN) (VINSN_LHS (INSN_VINSN (INSN)))
 #define INSN_RHS(INSN) (VINSN_RHS (INSN_VINSN (INSN)))
+#define INSN_COND(INSN) (VINSN_COND (INSN_VINSN (INSN)))
 #define INSN_REG_SETS(INSN) (VINSN_REG_SETS (INSN_VINSN (INSN)))
 #define INSN_REG_CLOBBERS(INSN) (VINSN_REG_CLOBBERS (INSN_VINSN (INSN)))
 #define INSN_REG_USES(INSN) (VINSN_REG_USES (INSN_VINSN (INSN)))
@@ -1537,6 +1549,7 @@ extern void vinsn_attach (vinsn_t);
 extern void vinsn_detach (vinsn_t);
 extern vinsn_t vinsn_copy (vinsn_t, bool);
 extern bool vinsn_equal_p (vinsn_t, vinsn_t);
+extern bool vinsn_equal_skip_cond_p (vinsn_t x, vinsn_t y);
 
 /* EXPR functions.  */
 extern void copy_expr (expr_t, expr_t);
@@ -1555,22 +1568,27 @@ extern void insert_in_history_vect (VEC(expr_history_def, heap) **,
                                     vinsn_t, vinsn_t, ds_t, ds_t);
 extern void mark_unavailable_targets (av_set_t, av_set_t, regset);
 extern int speculate_expr (expr_t, ds_t);
+extern void maybe_predicate_expr_into (av_set_t *, expr_t, insn_t, rtx);
 
 /* Av set functions.  */
 extern void av_set_add (av_set_t *, expr_t);
+extern void av_set_add_nocopy (av_set_t *, expr_t);
 extern void av_set_iter_remove (av_set_iterator *);
 extern expr_t av_set_lookup (av_set_t, vinsn_t);
 extern expr_t merge_with_other_exprs (av_set_t *, av_set_iterator *, expr_t);
 extern bool av_set_is_in_p (av_set_t, vinsn_t);
 extern av_set_t av_set_copy (av_set_t);
 extern void av_set_union_and_clear (av_set_t *, av_set_t *, insn_t);
-extern void av_set_union_and_live (av_set_t *, av_set_t *, regset, regset, insn_t);
+extern void av_set_union_and_live (av_set_t *, av_set_t *, regset, regset, insn_t, bool);
 extern void av_set_clear (av_set_t *);
 extern void av_set_leave_one_nonspec (av_set_t *);
 extern expr_t av_set_element (av_set_t, int);
 extern void av_set_substract_cond_branches (av_set_t *);
 extern void av_set_split_usefulness (av_set_t, int, int);
 extern void av_set_code_motion_filter (av_set_t *, av_set_t);
+extern void av_set_intersect (av_set_t *, av_set_t);
+extern void join_distinct_sets (av_set_t *, av_set_t *);
+extern void av_set_concat (av_set_t *, av_set_t *);
 
 extern void sel_save_haifa_priorities (void);
 
diff --git a/gcc/sel-sched.c b/gcc/sel-sched.c
index 91fb0fe..f5c6f8b 100644
--- a/gcc/sel-sched.c
+++ b/gcc/sel-sched.c
@@ -607,24 +607,23 @@ advance_one_cycle (fence_t fence)
     }
 }
 
-/* Returns true when SUCC in a fallthru bb of INSN, possibly
-   skipping empty basic blocks.  */
+/* Returns true when SUCC in a fallthru bb of INSN, possibly skipping empty
+   basic blocks.  Blocks with a nop are also skipped if SKIP_NOPS_P is set.  */
 static bool
-in_fallthru_bb_p (rtx insn, rtx succ)
+in_fallthru_bb_p (rtx insn, rtx succ, bool skip_nops_p)
 {
   basic_block bb = BLOCK_FOR_INSN (insn);
   edge e;
 
-  if (bb == BLOCK_FOR_INSN (succ))
-    return true;
-
   e = find_fallthru_edge_from (bb);
   if (e)
     bb = e->dest;
   else
     return false;
 
-  while (sel_bb_empty_p (bb))
+  while (skip_nops_p
+	 ? sel_bb_empty_or_nop_p (bb)
+	 : sel_bb_empty_p (bb))
     bb = bb->next_bb;
 
   return bb == BLOCK_FOR_INSN (succ);
@@ -690,7 +689,7 @@ extract_new_fences_from (flist_t old_fences, flist_tail_t new_fences,
           && (pipelining_p || INSN_SCHED_TIMES (succ) <= 0))
         {
           bool b = (in_same_ebb_p (insn, succ)
-                    || in_fallthru_bb_p (insn, succ));
+                    || in_fallthru_bb_p (insn, succ, false));
 
           if (sched_verbose >= 1)
             sel_print ("Fence %d continues as %d[%d] (state %s)\n",
@@ -722,7 +721,8 @@ can_substitute_through_p (insn_t insn, ds_t ds)
   if ((ds & DEP_OUTPUT)
       || (ds & DEP_ANTI)
       || ! INSN_RHS (insn)
-      || ! INSN_LHS (insn))
+      || ! INSN_LHS (insn)
+      || INSN_COND (insn))
     return false;
 
   /* Now we just need to make sure the INSN_RHS consists of only one
@@ -773,7 +773,7 @@ substitute_reg_in_expr (expr_t expr, insn_t insn, bool undo)
          WHERE_REPLACE should point inside NEW_INSN, so INSN_RHS couldn't be
 	 used instead of SET_SRC.  */
       where_replace = (has_rhs
-		       ? &SET_SRC (PATTERN (new_insn))
+		       ? COND_SET_SRC_PTR (PATTERN (new_insn))
 		       : &PATTERN (new_insn));
 
       new_insn_valid
@@ -882,15 +882,13 @@ rtx_ok_for_substitution_p (rtx what, rtx where)
 static rtx
 create_insn_rtx_with_rhs (vinsn_t vi, rtx rhs_rtx)
 {
-  rtx lhs_rtx;
-  rtx pattern;
   rtx insn_rtx;
+  bool res;
 
-  lhs_rtx = copy_rtx (VINSN_LHS (vi));
-
-  pattern = gen_rtx_SET (VOIDmode, lhs_rtx, rhs_rtx);
-  insn_rtx = create_insn_rtx_from_pattern (pattern, NULL_RTX);
+  insn_rtx = create_copy_of_insn_rtx (VINSN_INSN_RTX (vi));
 
+  res = validate_change (insn_rtx, COND_SET_SRC_PTR (PATTERN (insn_rtx)), rhs_rtx, 0);
+  gcc_assert (res);
   return insn_rtx;
 }
 
@@ -932,7 +930,7 @@ replace_src_with_reg_ok_p (insn_t insn, rtx new_src_reg)
     return true;
 
   /* See whether SET_SRC can be replaced with this register.  */
-  validate_change (insn, &SET_SRC (PATTERN (insn)), new_src_reg, 1);
+  validate_change (insn, COND_SET_SRC_PTR (PATTERN (insn)), new_src_reg, 1);
   res = verify_changes (0);
   cancel_changes (0);
 
@@ -952,38 +950,26 @@ replace_dest_with_reg_ok_p (insn_t insn, rtx new_reg)
   gcc_assert (GET_MODE (VINSN_LHS (vi)) == GET_MODE (new_reg));
 
   /* See whether SET_DEST can be replaced with this register.  */
-  validate_change (insn, &SET_DEST (PATTERN (insn)), new_reg, 1);
+  validate_change (insn, COND_SET_DEST_PTR (PATTERN (insn)), new_reg, 1);
   res = verify_changes (0);
   cancel_changes (0);
 
   return res;
 }
 
-/* Create a pattern with rhs of VI and lhs of LHS_RTX.  */
-static rtx
-create_insn_rtx_with_lhs (vinsn_t vi, rtx lhs_rtx)
-{
-  rtx rhs_rtx;
-  rtx pattern;
-  rtx insn_rtx;
-
-  rhs_rtx = copy_rtx (VINSN_RHS (vi));
-
-  pattern = gen_rtx_SET (VOIDmode, lhs_rtx, rhs_rtx);
-  insn_rtx = create_insn_rtx_from_pattern (pattern, NULL_RTX);
-
-  return insn_rtx;
-}
-
-/* Substitute lhs in the given expression EXPR for the register with number
-   NEW_REGNO.  SET_DEST may be arbitrary rtx, not only register.  */
+/* Substitute lhs in the given expression EXPR with register NEW_REG.  */
 static void
 replace_dest_with_reg_in_expr (expr_t expr, rtx new_reg)
 {
   rtx insn_rtx;
   vinsn_t vinsn;
+  bool res;
+
+  insn_rtx = create_copy_of_insn_rtx (EXPR_INSN_RTX (expr));
+
+  res = validate_change (insn_rtx, COND_SET_DEST_PTR (PATTERN (insn_rtx)), new_reg, 0);
+  gcc_assert (res);
 
-  insn_rtx = create_insn_rtx_with_lhs (EXPR_VINSN (expr), new_reg);
   vinsn = create_vinsn_from_insn_rtx (insn_rtx, false);
 
   change_vinsn_in_expr (expr, vinsn);
@@ -1219,10 +1205,9 @@ mark_unavailable_hard_regs (def_t def, struct reg_rename *reg_rename_p,
   unsigned cur_reg, regno;
   hard_reg_set_iterator hrsi;
 
-  gcc_assert (GET_CODE (PATTERN (def->orig_insn)) == SET);
   gcc_assert (reg_rename_p);
 
-  orig_dest = SET_DEST (PATTERN (def->orig_insn));
+  orig_dest = INSN_LHS (def->orig_insn);
 
   /* We have decided not to rename 'mem = something;' insns, as 'something'
      is usually a register.  */
@@ -1394,7 +1379,7 @@ choose_best_reg_1 (HARD_REG_SET hard_regs_used,
 
   FOR_EACH_DEF (def, di, original_insns)
     {
-      rtx orig_dest = SET_DEST (PATTERN (def->orig_insn));
+      rtx orig_dest = INSN_LHS (def->orig_insn);
 
       gcc_assert (REG_P (orig_dest));
 
@@ -1505,7 +1490,7 @@ choose_best_pseudo_reg (regset used_regs,
 
   FOR_EACH_DEF (def, i, original_insns)
     {
-      rtx dest = SET_DEST (PATTERN (def->orig_insn));
+      rtx dest = *COND_SET_DEST_PTR (PATTERN (def->orig_insn));
       int orig_regno;
 
       gcc_assert (REG_P (dest));
@@ -1577,6 +1562,10 @@ verify_target_availability (expr_t expr, regset used_regs,
 
   if (!REG_P (EXPR_LHS (expr)) || EXPR_TARGET_AVAILABLE (expr) < 0)
     return;
+  /* Making an expression predicated when moving it up across a branch
+     does not affect liveness on the predicated-off path.  */
+  if (EXPR_COND (expr))
+    return;
 
   regno = expr_dest_regno (expr);
   mode = GET_MODE (EXPR_LHS (expr));
@@ -2000,6 +1989,11 @@ undo_transformations (av_set_t *av_ptr, rtx insn)
                 clear_expr (tmp_expr);
                 break;
               }
+	    case TRANS_PREDICATION:
+	      {
+		change_vinsn_in_expr (expr, phist->old_expr_vinsn);
+		break;
+	      }
             default:
               gcc_unreachable ();
             }
@@ -2205,6 +2199,16 @@ moveup_expr (expr_t expr, insn_t through_insn, bool inside_insn_group,
       && moving_insn_creates_bookkeeping_block_p (insn, through_insn))
     return MOVEUP_EXPR_NULL;
 
+  if (flag_sel_sched_predication && any_condjump_p (through_insn)
+      && EXPR_COND (expr) && INSN_COND (through_insn)
+      && !modified_in_p (INSN_COND (through_insn), EXPR_INSN_RTX (expr)))
+    {
+      if (conditions_same_or_mutex_p (INSN_COND (through_insn), EXPR_COND (expr)))
+	return MOVEUP_EXPR_SAME;
+      else
+	return MOVEUP_EXPR_NULL;
+    }
+
   /* Deal with data dependencies.  */
   was_target_conflict = false;
   full_ds = has_dependence_p (expr, through_insn, &has_dep_p);
@@ -2712,6 +2716,181 @@ is_ineligible_successor (insn_t insn, ilist_t p)
     return false;
 }
 
+/* An entry in the predication cache.  */
+struct predication_cache
+{
+  /* A predicate that would be added.  */
+  rtx cond;
+  /* Original vinsn.  */
+  vinsn_t vinsn_old;
+  /* The vinsn resulting from applying predicate COND to vinsn VINSN_OLD.  */
+  vinsn_t vinsn_new;
+};
+
+static htab_t predication_cache;
+
+/* Hash function for predication cache entries.  */
+static hashval_t
+predication_cache_hash (const void *p)
+{
+  const struct predication_cache *data = (const struct predication_cache *)p;
+  return iterative_hash_rtx (data->cond, VINSN_HASH_RTX (data->vinsn_old));
+}
+
+/* Free function for predication cache entries.  */
+static void
+predication_cache_free (void *p)
+{
+  struct predication_cache *data = (struct predication_cache *)p;
+  vinsn_detach (data->vinsn_old);
+  if (data->vinsn_new)
+    vinsn_detach (data->vinsn_new);
+  free (p);
+}
+
+/* Comparison function for predication cache entries.  */
+static int
+predication_cache_eq (const void *p, const void *q)
+{
+  const struct predication_cache *data1 = (const struct predication_cache *)p;
+  const struct predication_cache *data2 = (const struct predication_cache *)q;
+  rtx i1, i2;
+  if (!conditions_same_p (data1->cond, data2->cond))
+    return false;
+  i1 = VINSN_INSN_RTX (data1->vinsn_old);
+  i2 = VINSN_INSN_RTX (data2->vinsn_old);
+  return (INSN_UID (i1) == INSN_UID (i2)
+	  || rtx_equal_p (PATTERN (i1), PATTERN (i2)));
+}
+
+/* Find an entry for applying predicate COND to vinsn VI in the predication
+   cache.  */
+static struct predication_cache*
+find_in_predication_cache (rtx cond, vinsn_t vi)
+{
+  struct predication_cache key;
+  key.cond = cond;
+  key.vinsn_old = vi;
+  return (struct predication_cache *) htab_find (predication_cache, &key);
+}
+
+/* Try to construct NEW_EXPR as the result of applying predicate COND to
+   EXPR, using uid of INSN to record the transformation in the history vector.
+   Return value indicates whether transformation is valid.  */
+static bool
+predicate_expr (expr_t new_expr, expr_t expr, insn_t insn, rtx cond)
+{
+  struct predication_cache *entry;
+  vinsn_t vi = EXPR_VINSN (expr), new_vi;
+  rtx pat = PATTERN (EXPR_INSN_RTX (expr));
+
+  if (VINSN_UNIQUE_P (vi)
+      || modified_in_p (cond, EXPR_INSN_RTX (expr)))
+    return false;
+
+  entry = find_in_predication_cache (cond, vi);
+
+  if (entry)
+    {
+      new_vi = entry->vinsn_new;
+      if (!new_vi)
+	return false;
+      if (INSN_IN_STREAM_P (VINSN_INSN_RTX (new_vi)))
+	new_vi = vinsn_copy (new_vi, false);
+    }
+  else
+    {
+      entry = XNEW (struct predication_cache);
+      entry->cond = cond;
+      entry->vinsn_old = vi;
+      vinsn_attach (vi);
+
+      pat = gen_rtx_COND_EXEC (VOIDmode, copy_rtx (cond), copy_rtx (pat));
+      if (insn_invalid_p (make_insn_raw (pat)))
+	{
+	  entry->vinsn_new = NULL;
+	  *(struct predication_cache **) htab_find_slot (predication_cache,
+							 entry,
+							 INSERT) = entry;
+	  return false;
+	}
+      pat = create_insn_rtx_from_pattern (pat, NULL_RTX);
+      new_vi = entry->vinsn_new = create_vinsn_from_insn_rtx (pat, false);
+      vinsn_attach (new_vi);
+      *(struct predication_cache **) htab_find_slot (predication_cache, entry,
+						     INSERT) = entry;
+    }
+
+  if (sched_verbose >= 6)
+    {
+      sel_print ("  new from pred: ");
+      dump_vinsn (new_vi);
+      sel_print ("\n");
+    }
+  copy_expr (new_expr, expr);
+  change_vinsn_in_expr (new_expr, new_vi);
+  insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (new_expr),
+			  INSN_UID (insn), TRANS_PREDICATION,
+			  vi, new_vi, EXPR_SPEC_DONE_DS (expr),
+			  EXPR_SPEC_DONE_DS (expr));
+  return true;
+}
+
+/* Invoke predicate_expr on EXPR, INSN, COND, and if the transformation is
+   valid, add the resulting expression into av set pointed by TOP.  */
+void
+maybe_predicate_expr_into (av_set_t *top, expr_t expr, insn_t insn, rtx cond)
+{
+  expr_def _tmp_expr, *tmp_expr = &_tmp_expr;
+
+  if (!cond)
+    return;
+  if (predicate_expr (tmp_expr, expr, insn, cond))
+    av_set_add_nocopy (top, tmp_expr);
+}
+
+/* Add to av set pointed by TOP expressions from AV predicated by INSN's
+   condition (or its inversion, if SUCC is not in the fallthru block).  */
+static void
+populate_av_set_with_predicated (av_set_t *top, av_set_t av, insn_t insn, insn_t succ)
+{
+  av_set_iterator avi;
+  expr_t expr;
+  rtx cond = INSN_COND (insn);
+
+  if (!cond || !any_condjump_p (insn)
+      || EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) != 2)
+    return;
+
+  if (!in_fallthru_bb_p (insn, succ, true))
+    cond = reversed_comparison (cond, GET_MODE (cond));
+
+  FOR_EACH_EXPR (expr, avi, av)
+    maybe_predicate_expr_into (top, expr, insn, cond);
+}
+
+/* Remove from av set pointed by AV expressions predicated by INSN's
+   condition (or its inverse, if SUCC is not in the fallthru block).  */
+static void
+filter_av_set_by_predicate (av_set_t *av, insn_t insn, insn_t succ)
+{
+  av_set_iterator avi;
+  expr_t expr;
+  rtx cond = INSN_COND (insn);
+
+  if (!cond || !any_condjump_p (insn)
+      || EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) != 2)
+    return;
+
+  if (!in_fallthru_bb_p (insn, succ, true))
+    cond = reversed_comparison (cond, GET_MODE (cond));
+
+  FOR_EACH_EXPR_1 (expr, avi, av)
+    if (EXPR_COND (expr)
+        && conditions_mutex_p (EXPR_COND (expr), cond))
+      av_set_iter_remove (&avi);
+}
+
 /* Computes the av_set below the last bb insn INSN, doing all the 'dirty work'
    of handling multiple successors and properly merging its av_sets.  P is
    the current path traversed.  WS is the size of lookahead window.
@@ -2723,7 +2902,7 @@ compute_av_set_at_bb_end (insn_t insn, ilist_t p, int ws)
   av_set_t expr_in_all_succ_branches = NULL;
   int is;
   insn_t succ, zero_succ = NULL;
-  av_set_t av1 = NULL;
+  av_set_t av1 = NULL, pred_forms_set = NULL;
 
   gcc_assert (sel_bb_end_p (insn));
 
@@ -2751,6 +2930,12 @@ compute_av_set_at_bb_end (insn_t insn, ilist_t p, int ws)
       /* We will edit SUCC_SET and EXPR_SPEC field of its elements.  */
       succ_set = compute_av_set_inside_bb (succ, p, ws, true);
 
+      /* Remove insns that are predicated-off for the current successor.  */
+      filter_av_set_by_predicate (&succ_set, insn, succ);
+
+      if (sinfo->succs_ok_n == 1)
+	populate_av_set_with_predicated (&pred_forms_set, succ_set, insn, succ);
+
       av_set_split_usefulness (succ_set,
                                VEC_index (int, sinfo->probs_ok, is),
                                sinfo->all_prob);
@@ -2784,12 +2969,13 @@ compute_av_set_at_bb_end (insn_t insn, ilist_t p, int ws)
         {
           basic_block bb0 = BLOCK_FOR_INSN (zero_succ);
           basic_block bb1 = BLOCK_FOR_INSN (succ);
+	  bool to_fallthru_p = in_fallthru_bb_p (insn, zero_succ, true);
 
           gcc_assert (BB_LV_SET_VALID_P (bb0) && BB_LV_SET_VALID_P (bb1));
           av_set_union_and_live (&av1, &succ_set,
                                  BB_LV_SET (bb0),
                                  BB_LV_SET (bb1),
-                                 insn);
+                                 insn, to_fallthru_p);
         }
       else
         av_set_union_and_clear (&av1, &succ_set, insn);
@@ -2813,6 +2999,8 @@ compute_av_set_at_bb_end (insn_t insn, ilist_t p, int ws)
       mark_unavailable_targets
         (av1, NULL, BB_LV_SET (BLOCK_FOR_INSN (succ)));
 
+  av_set_concat (&av1, &pred_forms_set);
+
   if (sinfo->all_succs_n > 1)
     {
       av_set_iterator i;
@@ -3391,6 +3579,12 @@ sel_rank_for_schedule (const void *x, const void *y)
   if (val)
     return val;
 
+  /* Prefer an expr that would not need renaming.  */
+  if (EXPR_TARGET_AVAILABLE (tmp) >= 0 && EXPR_TARGET_AVAILABLE (tmp2) >= 0)
+    val = EXPR_TARGET_AVAILABLE (tmp2) - EXPR_TARGET_AVAILABLE (tmp);
+  if (val)
+    return val;
+
   if (spec_info != NULL && spec_info->mask != 0)
     /* This code was taken from haifa-sched.c: rank_for_schedule ().  */
     {
@@ -3415,6 +3609,11 @@ sel_rank_for_schedule (const void *x, const void *y)
 	return dw;
     }
 
+  /* Prefer a conditionally executed expr.  */
+  val = !EXPR_COND (tmp) - !EXPR_COND(tmp2);
+  if (val)
+    return val;
+
   /* Prefer an old insn to a bookkeeping insn.  */
   if (INSN_UID (tmp_insn) < first_emitted_uid
       && INSN_UID (tmp2_insn) >= first_emitted_uid)
@@ -3581,7 +3780,12 @@ vinsn_vec_has_expr_p (vinsn_vec_t vinsn_vec, expr_t expr)
   int n;
 
   FOR_EACH_VEC_ELT (vinsn_t, vinsn_vec, n, vinsn)
-    if (VINSN_SEPARABLE_P (vinsn))
+    if (EXPR_COND (expr) || VINSN_COND (vinsn))
+      {
+	if (vinsn_equal_skip_cond_p (vinsn, EXPR_VINSN (expr)))
+	  return true;
+      }
+    else if (VINSN_SEPARABLE_P (vinsn))
       {
         if (vinsn_equal_p (vinsn, EXPR_VINSN (expr)))
           return true;
@@ -6179,6 +6383,7 @@ redo_transformations (expr_t expr, insn_t insn)
 		EXPR_SPEC_DONE_DS (expr) = hist->new_spec_ds;
 		/* Fallthru.  */
 	      case TRANS_SUBSTITUTION:
+	      case TRANS_PREDICATION:
 		change_vinsn_in_expr (expr, hist->new_expr_vinsn);
 		break;
 	      default:
@@ -6275,16 +6480,27 @@ static bool
 move_op_orig_expr_not_found (insn_t insn, av_set_t orig_ops ATTRIBUTE_UNUSED,
 			    void *static_params)
 {
+  bool mutexed;
+  expr_t r;
+  av_set_iterator avi;
   moveop_static_params_p sparams = (moveop_static_params_p) static_params;
 
 #ifdef ENABLE_CHECKING
   sparams->failed_insn = insn;
 #endif
 
+  mutexed = true;
+  FOR_EACH_EXPR (r, avi, orig_ops)
+    if (!sched_insns_conditions_mutex_p (insn, EXPR_INSN_RTX (r)))
+      {
+	mutexed = false;
+	break;
+      }
+
   /* If we're scheduling separate expr, in order to generate correct code
      we need to stop the search at bookkeeping code generated with the
      same destination register or memory.  */
-  if (lhs_of_insn_equals_to_dest_p (insn, sparams->dest))
+  if (!mutexed && lhs_of_insn_equals_to_dest_p (insn, sparams->dest))
     return false;
   return true;
 }
@@ -6370,13 +6586,14 @@ struct code_motion_path_driver_info_def fur_hooks = {
    was found at least on one path that is starting with one of INSN's
    successors (this fact is asserted).  ORIG_OPS is expressions we're looking
    for, PATH is the path we've traversed, STATIC_PARAMS is the parameters
-   of either move_op or find_used_regs depending on the caller.
+   of either move_op or find_used_regs depending on the caller.  COND, if not
+   null, is the common predicate of expressions in ORIG_OPS.
 
    Return 0 if we haven't found expression, 1 if we found it, -1 if we don't
    know for sure at this point.  */
 static int
 code_motion_process_successors (insn_t insn, av_set_t orig_ops,
-                                ilist_t path, void *static_params)
+                                ilist_t path, void *static_params, rtx cond)
 {
   int res = 0;
   succ_iterator succ_i;
@@ -6409,6 +6626,17 @@ code_motion_process_successors (insn_t insn, av_set_t orig_ops,
     {
       int b;
 
+      if (cond
+          && conditions_same_or_mutex_p (cond, INSN_COND (insn))
+          && !(single_succ_p (succ_i.e1->src))
+	  && (((succ_i.e1->flags & EDGE_FALLTHRU) != 0)
+	      == conditions_mutex_p (cond, INSN_COND (insn))))
+	{
+	  if (sched_verbose >= 6)
+	    sel_print ("Not following predicated-off path from %d\n",
+		       INSN_UID (succ));
+	  continue;
+	}
       lparams.e1 = succ_i.e1;
       lparams.e2 = succ_i.e2;
 
@@ -6472,6 +6700,27 @@ code_motion_path_driver_cleanup (av_set_t *orig_ops_p, ilist_t *path_p)
   av_set_clear (orig_ops_p);
 }
 
+/* Verify that all elements of AV have the same predicate.  Return the
+   common predicate.  */
+static rtx
+av_set_common_cond (av_set_t av)
+{
+  av_set_iterator i;
+  expr_t expr;
+  bool first_p = true;
+  rtx cond = NULL;
+
+  FOR_EACH_EXPR (expr, i, av)
+    if (first_p)
+      {
+	first_p = false;
+	cond = EXPR_COND (expr);
+      }
+    else
+      gcc_assert (cond == EXPR_COND (expr) || conditions_same_p (cond, EXPR_COND (expr)));
+  return cond;
+}
+
 /* The driver function that implements move_op or find_used_regs
    functionality dependent whether code_motion_path_driver_INFO is set to
    &MOVE_OP_HOOKS or &FUR_HOOKS.  This function implements the common parts
@@ -6492,6 +6741,7 @@ code_motion_path_driver (insn_t insn, av_set_t orig_ops, ilist_t path,
   basic_block bb = BLOCK_FOR_INSN (insn);
   insn_t first_insn, bb_tail, before_first;
   bool removed_last_insn = false;
+  rtx orig_cond;
 
   if (sched_verbose >= 6)
     {
@@ -6571,6 +6821,8 @@ code_motion_path_driver (insn_t insn, av_set_t orig_ops, ilist_t path,
   /* It is not possible that all ORIG_OPS are filtered out.  */
   gcc_assert (orig_ops);
 
+  orig_cond = av_set_common_cond (orig_ops);
+
   /* It is enough to place only heads and tails of visited basic blocks into
      the PATH.  */
   ilist_add (&path, insn);
@@ -6659,6 +6911,12 @@ code_motion_path_driver (insn_t insn, av_set_t orig_ops, ilist_t path,
 
       gcc_assert (insn == sel_bb_end (bb));
 
+      if (orig_cond && av_set_common_cond (orig_ops))
+	orig_cond = NULL;
+      if (orig_cond)
+	gcc_assert (INSN_COND (insn)
+		    && conditions_same_or_mutex_p (orig_cond, INSN_COND (insn)));
+
       /* Add bb tail to PATH (but it doesn't make any sense if it's a bb_head -
 	 it's already in PATH then).  */
       if (insn != first_insn)
@@ -6672,7 +6930,7 @@ code_motion_path_driver (insn_t insn, av_set_t orig_ops, ilist_t path,
       /* Process_successors should be able to find at least one
 	 successor for which code_motion_path_driver returns TRUE.  */
       res = code_motion_process_successors (insn, orig_ops,
-                                            path, static_params);
+                                            path, static_params, orig_cond);
 
       /* Jump in the end of basic block could have been removed or replaced
          during code_motion_process_successors, so recompute insn as the
@@ -7004,6 +7262,9 @@ sel_region_init (int rgn)
   current_copies = BITMAP_ALLOC (NULL);
   current_originators = BITMAP_ALLOC (NULL);
   code_motion_visited_blocks = BITMAP_ALLOC (NULL);
+  predication_cache = htab_create (16, predication_cache_hash,
+				   predication_cache_eq,
+				   predication_cache_free);
 
   return false;
 }
@@ -7299,6 +7560,7 @@ sel_region_target_finish (bool reset_sched_cycles_p)
 static void
 sel_region_finish (bool reset_sched_cycles_p)
 {
+  htab_delete (predication_cache);
   simplify_changed_insns ();
   sched_finish_ready_list ();
   free_nop_pool ();
