diff mbox

[2/3] Predication support

Message ID alpine.LNX.2.00.1110262127220.6939@monoid.intra.ispras.ru
State New
Headers show

Commit Message

Alexander Monakov Oct. 26, 2011, 5:49 p.m. UTC 
This patch contains the implementation of predication support.

The selective scheduler is adjusted to recognize COND_EXEC instructions.  They
can be renamed like normal assignments.  Selective scheduler itself will add
predicated variants of instructions in availability sets when computing them
on CFG splits, using the predicate of the conditional jump.

Converting an instruction to a predicated form is treated similar to other
transformations (speculation, substitition or renaming) in
{undo,redo}_transformation.  Predication cache is maintained to quickly
retrieve predicated variants of instructions.

In particular, predication support  allows to pipeline non-doloop loops on
ia64 more cleanly, as no recovery code for speculative loads is needed.  Also,
it allows to pipeline loads on arm.

2011-10-26  Alexander Monakov  <amonakov@ispras.ru>

	* common.opt: Add -fsel-sched-predication option.
	* config/ia64/ia64.c (get_mode_no_for_insn): Support conditional loads.
	* rtl.h (COND_SET_SRC_PTR, COND_SET_SRC_PTR): New macros.
	* sched-deps.c (conditions_mutex_with_rev_p): Rename from
	conditions_mutex_p.  Adjust the caller.
	(conditions_mutex_p, conditions_same_p,
	conditions_same_or_mutex_p): New functions.
	(sched_analyze_insn): Extract LHS/RHS for conditional assignments.
	* sched-int.h (conditions_mutex_p, conditions_same_p,
	conditions_same_or_mutex_p): Declare.
	* sel-sched-ir.c (vinsn_equal_p): Support conditional insns.
	(vinsn_equal_skip_cond_p): New function.
	(init_expr): Add new argument (was_predicated).  Update all callers. 
	(merge_expr_data): Assert equality of merged predicates.
	(av_set_add_nocopy, join_distinct_sets): Export.
	(av_set_tail, av_set_concat): New functions.
	(av_set_union_and_live): Add parameter to_fallthru_p, generate
	predicated insns.
	(setup_id_lhs_rhs): Support conditional insns.
	(setup_id_cond): New function.
	(init_id_from_df, deps_init_id): Use it.
	(get_dest_and_mode): Support conditional insns.
	* sel-sched-ir.h (enum local_trans_type): Add TRANS_PREDICATION.
	(struct _expr): Add new member (was_predicated).
	(EXPR_COND, EXPR_WAS_PREDICATED): New accessor macros.
	(struct idata_def): Add new member (cond).
	(IDATA_COND, VINSN_COND, INSN_COND): New accessor macros.
	(vinsn_equal_skip_cond_p, maybe_predicate_expr_into,
	av_set_add_nocopy, av_set_intersect, join_distinct_sets,
	av_set_concat): Declare.
	(av_set_union_and_live): Change prototype.
	(in_fallthru_bb_p): Add new parameter (skip_nops_p).  Update all
	callers.
	(can_substitute_through_p): Do not substitute through conditional
	insns.
	(substitute_reg_in_expr, replace_src_with_reg_ok_p): Support
	substitution in conditional moves.
	(create_insn_rtx_with_rhs, replace_dest_with_reg_ok_p,
	replace_dest_with_reg_in_expr): Support renaming of conditional moves.
	(create_insn_rtx_with_lhs): Delete.
	(mark_unavailable_hard_regs, choose_best_reg_1,
	choose_best_pseudo_reg, verify_target_availability): Support
	conditional insns.
	(undo_transformations): Add support for TRANS_PREDICATION.
	(redo_transformations): Ditto.
	(moveup_expr): Add support for predicated exprs.
	(struct predication_cache, predication_cache_hash,
	predication_cache_free, predication_cache_eq,
	find_in_predication_cache, predicate_expr, maybe_predicate_expr_into,
	populate_av_set_with_predicated, filter_av_set_by_predicate): New.
	(compute_av_set_at_bb_end): Generate predicated instructions.
	(sel_rank_for_schedule): Adjust heuristics.
	(vinsn_vec_has_expr_p): Allow inexact match for predicated insns.
	(move_op_orig_expr_not_found): Ignore insns with matching LHS if the
	condition is mutually exclusive.
	(code_motion_process_successors): Add new argument (cond).  Use it to
	skip predicated-off paths.  Update the caller.
	(av_set_common_cond): New.
	(sel_region_init): Initialize predication cache.
	(sel_region_finish): Free predication cache.

Comments

Andrey Belevantsev Nov. 15, 2011, 8:36 a.m. UTC | #1 
Hello,

On 26.10.2011 21:49, Alexander Monakov wrote:
> 2011-10-26  Alexander Monakov<amonakov@ispras.ru>
>
> 	* common.opt: Add -fsel-sched-predication option.
> 	* config/ia64/ia64.c (get_mode_no_for_insn): Support conditional loads.
> 	* rtl.h (COND_SET_SRC_PTR, COND_SET_SRC_PTR): New macros.
> 	* sched-deps.c (conditions_mutex_with_rev_p): Rename from
> 	conditions_mutex_p.  Adjust the caller.
> 	(conditions_mutex_p, conditions_same_p,
> 	conditions_same_or_mutex_p): New functions.
> 	(sched_analyze_insn): Extract LHS/RHS for conditional assignments.
> 	* sched-int.h (conditions_mutex_p, conditions_same_p,
> 	conditions_same_or_mutex_p): Declare.
> 	* sel-sched-ir.c (vinsn_equal_p): Support conditional insns.
> 	(vinsn_equal_skip_cond_p): New function.
> 	(init_expr): Add new argument (was_predicated).  Update all callers.
> 	(merge_expr_data): Assert equality of merged predicates.
> 	(av_set_add_nocopy, join_distinct_sets): Export.
> 	(av_set_tail, av_set_concat): New functions.
> 	(av_set_union_and_live): Add parameter to_fallthru_p, generate
> 	predicated insns.
> 	(setup_id_lhs_rhs): Support conditional insns.
> 	(setup_id_cond): New function.
> 	(init_id_from_df, deps_init_id): Use it.
> 	(get_dest_and_mode): Support conditional insns.
> 	* sel-sched-ir.h (enum local_trans_type): Add TRANS_PREDICATION.
> 	(struct _expr): Add new member (was_predicated).
> 	(EXPR_COND, EXPR_WAS_PREDICATED): New accessor macros.
> 	(struct idata_def): Add new member (cond).
> 	(IDATA_COND, VINSN_COND, INSN_COND): New accessor macros.
> 	(vinsn_equal_skip_cond_p, maybe_predicate_expr_into,
> 	av_set_add_nocopy, av_set_intersect, join_distinct_sets,
> 	av_set_concat): Declare.
> 	(av_set_union_and_live): Change prototype.
	* sel-sched.c is lost somewhere here.

>
>
> 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
> @@ -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)
> +{
As we discussed offline, this functionality can be integrated in 
vinsn_equal_p, so we don't need extra predicate for that.

> @@ -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,
from the fallthru edge


> @@ -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);
> +
Do we need to conditionalize this on flag_sel_sched_predication?

> 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
> @@ -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;
No comment before this variable.  Also, this section is worth a comment 
describing why we need a separate cache for predicated insns.

> +/* 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)))
We are throwing away this insn when it is valid and making it again below 
with create_insn_rtx_from_pattern, please avoid doing that.

> +	{
> +	  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");
> +    }
We don't have similar debug output with speculation/substitution, do we 
want it here because of the different place where the transformation is 
happening?  In this case, please expand the debug message, otherwise it is 
better to remove it.

> @@ -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);
Why do we need to skip nop blocks here?

>     /* 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))
Comment needs an update.

> @@ -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;
> +	}
Also worth a comment before if.


> @@ -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;
Why this?  Also needs a comment, and there is no ChangeLog entry for 
code_motion_path_driver changes.


Andrey
diff mbox

Patch

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 ();