diff mbox

[1/3] Transformation replay mechanism

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

Commit Message

Alexander Monakov Oct. 26, 2011, 5:26 p.m. UTC
(Note, this is a prerequisite for predication support but also is an
 improvement on its own.  This patch can be installed separately.)

This patch implements transformation replay mechanism (redo_transformations).
Currently, after choosing an expression to schedule and finding its original
expressions below the scheduling fence in move_op, we need to move the
original expressions up (e.g. to correctly generate bookkeeping copies).  That
moving up would call moveup_expr_cached.

The patch slightly optimizes this by performing lookups in the history vector
of the chosen expression, which must contain all transformations of all
original expressions.  Not much changes are needed: the most notable is
perhaps that for speculation transformation, both old and new speculative
statuses are saved.

This patch is needed by the following predication patch, which uses
redo_transformations to correctly apply inverted/non-inverted predicate on
jumps without needing to remember the branch from which the expression
originated.

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

	* sel-sched-ir.c (free_history_vect): Export.
	(insert_in_history_vect): Rename argument spec_ds to old_spec_ds, add
	new argument (new_spec_ds).  Record it in the history vector.  Update
	all callers.
	(init_expr): Assert that initial history is empty.  Simplify code.
	(copy_history_of_changes): Split out from copy_expr.
	* sel-sched-ir.h (struct expr_history_def_1): Rename spec_ds to
	old_spec_ds.  Add new member (new_spec_ds).
	(copy_history_of_changes, free_history_vect): Declare.
	(insert_in_history_vect): Adjust prototype.
	* sel-sched.c (undo_transformations): Adjust.
	(move_exprs_to_boundary): Discard history of expression to be
	scheduled.
	(move_op_orig_expr_found): Populate history vector of c_expr for use
	in redo_transformations.
	(redo_transformations): New.
	(move_op_ascend): Use redo_transformations.

Comments

Andrey Belevantsev Nov. 15, 2011, 7:40 a.m. UTC | #1
Hello,

On 26.10.2011 21:26, Alexander Monakov wrote:
> (Note, this is a prerequisite for predication support but also is an
>   improvement on its own.  This patch can be installed separately.)
>
...

> diff --git a/gcc/sel-sched.c b/gcc/sel-sched.c
> index f11faca..91fb0fe 100644
> --- a/gcc/sel-sched.c
> +++ b/gcc/sel-sched.c
> @@ -5234,6 +5234,7 @@ move_exprs_to_boundary (bnd_t bnd, expr_t expr_vliw,
>
>     b = move_op (BND_TO (bnd), expr_seq, expr_vliw,
>                  get_dest_from_orig_ops (expr_seq), c_expr,&should_move);
> +  free_history_vect (&EXPR_HISTORY_OF_CHANGES (c_expr));
Why do we need this?  Upon returning from move_exprs_to_boundary (in 
schedule_expr_on_boundary), we immediately call clear_expr on c_expr which 
in turn calls free_history_vect.  So the history vector would be cleared 
anyways, no?  In this case we don't have to export free_history_vect, too.

Otherwise OK.

Thanks,
Andrey
diff mbox

Patch

diff --git a/gcc/sel-sched-ir.c b/gcc/sel-sched-ir.c
index 1bbc3ed..1a73308 100644
--- a/gcc/sel-sched-ir.c
+++ b/gcc/sel-sched-ir.c
@@ -149,7 +149,6 @@  static expr_t set_insn_init (expr_t, vinsn_t, int);
 
 static void cfg_preds (basic_block, insn_t **, int *);
 static void prepare_insn_expr (insn_t, int);
-static void free_history_vect (VEC (expr_history_def, heap) **);
 
 static void move_bb_info (basic_block, basic_block);
 static void remove_empty_bb (basic_block, bool);
@@ -1503,13 +1502,13 @@  find_in_history_vect (VEC(expr_history_def, heap) *vect, rtx insn,
 
 /* Insert new element in a sorted history vector pointed to by PVECT,
    if it is not there already.  The element is searched using
-   UID/NEW_EXPR_VINSN pair.  TYPE, OLD_EXPR_VINSN and SPEC_DS save
-   the history of a transformation.  */
+   UID/NEW_EXPR_VINSN pair.  TYPE, OLD_EXPR_VINSN, OLD_SPEC_DS and
+   NEW_SPEC_DS save the history of a transformation.  */
 void
 insert_in_history_vect (VEC (expr_history_def, heap) **pvect,
                         unsigned uid, enum local_trans_type type,
                         vinsn_t old_expr_vinsn, vinsn_t new_expr_vinsn,
-                        ds_t spec_ds)
+                        ds_t old_spec_ds, ds_t new_spec_ds)
 {
   VEC(expr_history_def, heap) *vect = *pvect;
   expr_history_def temp;
@@ -1525,15 +1524,16 @@  insert_in_history_vect (VEC (expr_history_def, heap) **pvect,
       /* It is possible that speculation types of expressions that were
          propagated through different paths will be different here.  In this
          case, merge the status to get the correct check later.  */
-      if (phist->spec_ds != spec_ds)
-        phist->spec_ds = ds_max_merge (phist->spec_ds, spec_ds);
+      if (phist->old_spec_ds != old_spec_ds)
+        phist->old_spec_ds = ds_max_merge (phist->old_spec_ds, old_spec_ds);
       return;
     }
 
   temp.uid = uid;
   temp.old_expr_vinsn = old_expr_vinsn;
   temp.new_expr_vinsn = new_expr_vinsn;
-  temp.spec_ds = spec_ds;
+  temp.old_spec_ds = old_spec_ds;
+  temp.new_spec_ds = new_spec_ds;
   temp.type = type;
 
   vinsn_attach (old_expr_vinsn);
@@ -1543,7 +1543,7 @@  insert_in_history_vect (VEC (expr_history_def, heap) **pvect,
 }
 
 /* Free history vector PVECT.  */
-static void
+void
 free_history_vect (VEC (expr_history_def, heap) **pvect)
 {
   unsigned i;
@@ -1576,7 +1576,7 @@  merge_history_vect (VEC (expr_history_def, heap) **pvect,
   for (i = 0; VEC_iterate (expr_history_def, from, i, phist); i++)
     insert_in_history_vect (pvect, phist->uid, phist->type,
                             phist->old_expr_vinsn, phist->new_expr_vinsn,
-                            phist->spec_ds);
+                            phist->old_spec_ds, phist->new_spec_ds);
 }
 
 /* Compare two vinsns as rhses if possible and as vinsns otherwise.  */
@@ -1632,10 +1632,8 @@  init_expr (expr_t expr, vinsn_t vi, int spec, int use, int priority,
   EXPR_SPEC_DONE_DS (expr) = spec_done_ds;
   EXPR_SPEC_TO_CHECK_DS (expr) = spec_to_check_ds;
 
-  if (history)
-    EXPR_HISTORY_OF_CHANGES (expr) = history;
-  else
-    EXPR_HISTORY_OF_CHANGES (expr) = NULL;
+  gcc_assert (!history);
+  EXPR_HISTORY_OF_CHANGES (expr) = history;
 
   EXPR_TARGET_AVAILABLE (expr) = target_available;
   EXPR_WAS_SUBSTITUTED (expr) = was_substituted;
@@ -1644,35 +1642,39 @@  init_expr (expr_t expr, vinsn_t vi, int spec, int use, int priority,
   EXPR_CANT_MOVE (expr) = cant_move;
 }
 
-/* Make a copy of the expr FROM into the expr TO.  */
+/* Copy history vector of the expr FROM to the expr TO.  */
 void
-copy_expr (expr_t to, expr_t from)
+copy_history_of_changes (expr_t to, expr_t from)
 {
-  VEC(expr_history_def, heap) *temp = NULL;
-
   if (EXPR_HISTORY_OF_CHANGES (from))
     {
       unsigned i;
       expr_history_def *phist;
 
-      temp = VEC_copy (expr_history_def, heap, EXPR_HISTORY_OF_CHANGES (from));
-      for (i = 0;
-           VEC_iterate (expr_history_def, temp, i, phist);
-           i++)
+      EXPR_HISTORY_OF_CHANGES (to)
+        = VEC_copy (expr_history_def, heap, EXPR_HISTORY_OF_CHANGES (from));
+      FOR_EACH_VEC_ELT (expr_history_def, EXPR_HISTORY_OF_CHANGES (to), i,
+			phist)
         {
           vinsn_attach (phist->old_expr_vinsn);
           vinsn_attach (phist->new_expr_vinsn);
         }
     }
+}
 
+/* Make a copy of the expr FROM into the expr TO.  */
+void
+copy_expr (expr_t to, expr_t from)
+{
   init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from),
              EXPR_USEFULNESS (from), EXPR_PRIORITY (from),
 	     EXPR_SCHED_TIMES (from), EXPR_ORIG_BB_INDEX (from),
 	     EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from),
-	     EXPR_ORIG_SCHED_CYCLE (from), temp,
+	     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));
+  copy_history_of_changes (to, from);
 }
 
 /* Same, but the final expr will not ever be in av sets, so don't copy
@@ -1798,7 +1800,7 @@  update_speculative_bits (expr_t to, expr_t from, insn_t split_point)
               insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
                                       INSN_UID (split_point), TRANS_SPECULATION,
                                       EXPR_VINSN (from), EXPR_VINSN (to),
-                                      record_ds);
+                                      record_ds, EXPR_SPEC_DONE_DS (to));
             }
         }
     }
diff --git a/gcc/sel-sched-ir.h b/gcc/sel-sched-ir.h
index c8f8be6..bcb47c6 100644
--- a/gcc/sel-sched-ir.h
+++ b/gcc/sel-sched-ir.h
@@ -89,8 +89,11 @@  struct expr_history_def_1
   /* How the expression looks after the transformation.  */
   vinsn_t new_expr_vinsn;
 
-  /* And its speculative status.  */
-  ds_t spec_ds;
+  /* Its previous speculative status.  */
+  ds_t old_spec_ds;
+
+  /* Its new speculative status.  */
+  ds_t new_spec_ds;
 
   /* Type of the transformation.  */
   enum local_trans_type type;
@@ -1537,6 +1540,8 @@  extern bool vinsn_equal_p (vinsn_t, vinsn_t);
 
 /* EXPR functions.  */
 extern void copy_expr (expr_t, expr_t);
+extern void copy_history_of_changes (expr_t, expr_t);
+extern void free_history_vect (VEC (expr_history_def, heap) **);
 extern void copy_expr_onside (expr_t, expr_t);
 extern void merge_expr_data (expr_t, expr_t, insn_t);
 extern void merge_expr (expr_t, expr_t, insn_t);
@@ -1547,7 +1552,7 @@  extern int find_in_history_vect (VEC(expr_history_def, heap) *,
                                  rtx, vinsn_t, bool);
 extern void insert_in_history_vect (VEC(expr_history_def, heap) **,
                                     unsigned, enum local_trans_type,
-                                    vinsn_t, vinsn_t, ds_t);
+                                    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);
 
diff --git a/gcc/sel-sched.c b/gcc/sel-sched.c
index f11faca..91fb0fe 100644
--- a/gcc/sel-sched.c
+++ b/gcc/sel-sched.c
@@ -1965,7 +1965,7 @@  undo_transformations (av_set_t *av_ptr, rtx insn)
                    and in the case of merging different probabilities of the
                    same speculative status along different paths we do not
                    record this in the history vector.  */
-                old_ds = phist->spec_ds;
+                old_ds = phist->old_spec_ds;
                 new_ds = EXPR_SPEC_DONE_DS (expr);
 
                 old_ds &= SPECULATIVE;
@@ -2409,7 +2409,7 @@  try_transformation_cache (expr_t expr, insn_t insn,
       insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (expr),
                               INSN_UID (insn), pti->type,
                               pti->vinsn_old, pti->vinsn_new,
-                              EXPR_SPEC_DONE_DS (expr));
+                              EXPR_SPEC_DONE_DS (expr), pti->ds);
 
       if (INSN_IN_STREAM_P (VINSN_INSN_RTX (pti->vinsn_new)))
         pti->vinsn_new = vinsn_copy (pti->vinsn_new, true);
@@ -2564,7 +2564,7 @@  moveup_expr_cached (expr_t expr, insn_t insn, bool inside_insn_group)
           insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (expr),
                                   INSN_UID (insn), trans_type,
                                   expr_old_vinsn, EXPR_VINSN (expr),
-                                  expr_old_spec_ds);
+                                  expr_old_spec_ds, EXPR_SPEC_DONE_DS (expr));
           update_transformation_cache (expr, insn, inside_insn_group,
                                        trans_type, expr_old_vinsn);
           if (sched_verbose >= 6)
@@ -5234,6 +5234,7 @@  move_exprs_to_boundary (bnd_t bnd, expr_t expr_vliw,
 
   b = move_op (BND_TO (bnd), expr_seq, expr_vliw,
                get_dest_from_orig_ops (expr_seq), c_expr, &should_move);
+  free_history_vect (&EXPR_HISTORY_OF_CHANGES (c_expr));
 
   /* We should be able to find the expression we've chosen for
      scheduling.  */
@@ -5999,6 +6000,7 @@  move_op_orig_expr_found (insn_t insn, expr_t expr,
   moveop_static_params_p params = (moveop_static_params_p) static_params;
 
   copy_expr_onside (params->c_expr, INSN_EXPR (insn));
+  copy_history_of_changes (params->c_expr, expr);
   track_scheduled_insns_and_blocks (insn);
   insn_emitted = handle_emitting_transformations (insn, expr, params);
   only_disconnect = (params->uid == INSN_UID (insn)
@@ -6149,19 +6151,78 @@  fur_at_first_insn (insn_t insn,
 	      || AV_LEVEL (insn) == -1);
 }
 
+/* Redo the transformation that moveup_expr performed on EXPR for INSN, as
+   recorded in EXPR's history vector.  */
+static void
+redo_transformations (expr_t expr, insn_t insn)
+{
+  unsigned i, insn_uid = INSN_UID (insn);
+  rtx orig_expr_lhs = EXPR_LHS (expr);
+  expr_history_def *hist;
+  VEC(expr_history_def, heap) *vect = EXPR_HISTORY_OF_CHANGES (expr);
+
+  if (sched_verbose >= 6)
+    {
+      sel_print ("Moving ");
+      dump_expr (expr);
+      sel_print (" through %d: ", INSN_UID (insn));
+    }
+
+  FOR_EACH_VEC_ELT (expr_history_def, vect, i, hist)
+    if (hist->uid == insn_uid)
+      {
+	if (vinsn_equal_p (EXPR_VINSN (expr), hist->old_expr_vinsn))
+	  {
+	    switch (hist->type)
+	      {
+	      case TRANS_SPECULATION:
+		EXPR_SPEC_DONE_DS (expr) = hist->new_spec_ds;
+		/* Fallthru.  */
+	      case TRANS_SUBSTITUTION:
+		change_vinsn_in_expr (expr, hist->new_expr_vinsn);
+		break;
+	      default:
+		gcc_unreachable ();
+	      }
+
+	    if (EXPR_LHS (expr) != orig_expr_lhs && expr_dest_reg (expr))
+	      replace_dest_with_reg_in_expr (expr, orig_expr_lhs);
+
+	    if (sched_verbose >= 6)
+	      {
+		sel_print ("changed (redoing): ");
+		dump_expr (expr);
+		sel_print ("\n");
+	      }
+	    return;
+	  }
+	else
+	  {
+	    /* We cannot assert the following; consider:
+	       r1 = r3;
+	       r2 = r3;
+	       r4 = r1;
+	       r5 = r2;
+	       We choose to schedule r4 = r3, find it at r4 = r1, and
+	       attempt to redo transformation on r2 = r3, which was recorded,
+	       because r5 = r2 was moved through it and unified afterwards.  */
+	    /* gcc_assert (vinsn_equal_p (EXPR_VINSN (expr), hist->new_expr_vinsn)); */
+	    break;
+	  }
+      }
+  if (sched_verbose >= 6)
+    sel_print ("unchanged (redoing)\n");
+}
+
 /* Called on the backward stage of recursion to call moveup_expr for insn
    and sparams->c_expr.  */
 static void
 move_op_ascend (insn_t insn, void *static_params)
 {
-  enum MOVEUP_EXPR_CODE res;
   moveop_static_params_p sparams = (moveop_static_params_p) static_params;
 
   if (! INSN_NOP_P (insn))
-    {
-      res = moveup_expr_cached (sparams->c_expr, insn, false);
-      gcc_assert (res != MOVEUP_EXPR_NULL);
-    }
+    redo_transformations (sparams->c_expr, insn);
 
   /* Update liveness for this insn as it was invalidated.  */
   update_liveness_on_insn (insn);