* sel-sched-dump.c (dump_expr_1): Print correct value of

        EXPR_TARGET_AVAILABLE.
        * sel-sched-ir.h (struct vinsn_def): New field hash_rtx.
        (VINSN_HASH_RTX): New accessor.
        (struct transformed_insns): New.
        (struct _sel_insn_data): New field transformed_insns.
        (INSN_TRANSFORMED_INSNS): New accessor.
        * sel-sched-ir.c (vinsn_init): Initialize VINSN_HASH_RTX.
        (vinsn_delete): Kill outdated comment.
        (speculate_expr): Return 2 when we think that the target
        register is unavailable for speculation.
        (hash_transformed_insns, eq_transformed_insns,
        free_transformed_insns): New.
        (init_first_time_insn_data): Init INSN_TRANSFORMED_INSNS.
        (free_first_time_insn_data): Free INSN_TRANSFORMED_INSNS.
        (finish_insns): Likewise.
        (finish_global_and_expr_insn): Do not assert that the vinsn
        is connected only to one insn.
        * sel-sched.c (undo_transformations): Also undo when only
        a dependence status has changed, not insn's pattern.
        Update comment.
        (was_target_conflict): New static variable.
        (moveup_rhs): Set it when a target conflict is encountered.
        (moveup_set_rhs): When an expression is changed, record this
        in INSN_TRANSFORMED_INSNS.  Lookup this hashtable before calling
        moveup_rhs.  Use was_target_conflict when recording.



git-svn-id: https://gcc.gnu.org/svn/gcc/branches/sel-sched-branch@132752 138bc75d-0d04-0410-961f-82ee72b054a4

5 files changed, 189 insertions, 28 deletions

diff --git a/gcc/ChangeLog.sel-sched b/gcc/ChangeLog.sel-sched
index d408ec7ed5c..c4784bcd9a0 100644
--- a/gcc/ChangeLog.sel-sched
+++ b/gcc/ChangeLog.sel-sched
@@ -1,4 +1,33 @@
 2008-02-28  Andrey Belevantsev  <abel@ispras.ru>
+	
+	* sel-sched-dump.c (dump_expr_1): Print correct value of 
+	EXPR_TARGET_AVAILABLE.
+	* sel-sched-ir.h (struct vinsn_def): New field hash_rtx.
+	(VINSN_HASH_RTX): New accessor.
+	(struct transformed_insns): New.
+	(struct _sel_insn_data): New field transformed_insns.
+	(INSN_TRANSFORMED_INSNS): New accessor.
+	* sel-sched-ir.c (vinsn_init): Initialize VINSN_HASH_RTX.
+	(vinsn_delete): Kill outdated comment.
+	(speculate_expr): Return 2 when we think that the target
+	register is unavailable for speculation.
+	(hash_transformed_insns, eq_transformed_insns,
+	free_transformed_insns): New.
+	(init_first_time_insn_data): Init INSN_TRANSFORMED_INSNS.
+	(free_first_time_insn_data): Free INSN_TRANSFORMED_INSNS.
+	(finish_insns): Likewise.
+	(finish_global_and_expr_insn): Do not assert that the vinsn
+	is connected only to one insn.
+	* sel-sched.c (undo_transformations): Also undo when only
+	a dependence status has changed, not insn's pattern.
+	Update comment.
+	(was_target_conflict): New static variable.
+	(moveup_rhs): Set it when a target conflict is encountered.
+	(moveup_set_rhs): When an expression is changed, record this
+	in INSN_TRANSFORMED_INSNS.  Lookup this hashtable before calling
+	moveup_rhs.  Use was_target_conflict when recording.
+
+2008-02-28  Andrey Belevantsev  <abel@ispras.ru>
 
 	* sel-sched.c (sel_region_init): Move the removing empty blocks loop 
         to a proper place.  Fix the call to sel_remove_empty_bb.
diff --git a/gcc/sel-sched-dump.c b/gcc/sel-sched-dump.c
index a0ccfc3cb4e..67b4facc2c6 100644
--- a/gcc/sel-sched-dump.c
+++ b/gcc/sel-sched-dump.c
@@ -413,8 +413,8 @@ dump_expr_1 (expr_t expr, int flags)
 	print ("orig_bb:%d;", orig_bb);
     }
   
-  if (!EXPR_TARGET_AVAILABLE (expr))
-    print ("targ_un;");
+  if (EXPR_TARGET_AVAILABLE (expr) < 1)
+    print ("target:%d;", EXPR_TARGET_AVAILABLE (expr));
   print ("]");
   line_finish ();
 }
diff --git a/gcc/sel-sched-ir.c b/gcc/sel-sched-ir.c
index 8fce1691911..0ed2bf0258f 100644
--- a/gcc/sel-sched-ir.c
+++ b/gcc/sel-sched-ir.c
@@ -1373,9 +1373,13 @@ vinsn_init (vinsn_t vi, insn_t insn, bool force_unique_p)
       rtx rhs = VINSN_RHS (vi);
 
       VINSN_HASH (vi) = sel_hash_rtx (rhs, GET_MODE (rhs));
+      VINSN_HASH_RTX (vi) = sel_hash_rtx (VINSN_PATTERN (vi), VOIDmode);
     }
   else
-    VINSN_HASH (vi) = sel_hash_rtx (VINSN_PATTERN (vi), VOIDmode);
+    {
+      VINSN_HASH (vi) = sel_hash_rtx (VINSN_PATTERN (vi), VOIDmode); 
+      VINSN_HASH_RTX (vi) = VINSN_HASH (vi);
+    }
     
   VINSN_COUNT (vi) = 0;
 
@@ -1425,10 +1429,6 @@ vinsn_delete (vinsn_t vi)
   return_regset_to_pool (VINSN_REG_CLOBBERS (vi));
 
   free (VINSN_ID (vi));
-
-  /* This insn should not be deleted as it may have shared parts.  */
-  /*  if (!INSN_IN_STREAM_P (insn))  expr_clear (&insn); */
-
   free (vi);
 }
 
@@ -1978,8 +1978,9 @@ set_unavailable_target_for_expr (expr_t expr, regset lv_set)
     }
 }
 
-/* Try to make EXPR speculative.  Return true when EXPR's pattern 
-   had to be changed. */
+/* Try to make EXPR speculative.  Return 1 when EXPR's pattern 
+   or dependence status have changed, 2 when also the target register
+   became unavailable, 0 if nothing had to be changed. */
 int
 speculate_expr (expr_t expr, ds_t ds)
 {
@@ -2001,7 +2002,7 @@ speculate_expr (expr_t expr, ds_t ds)
     {
     case 0:
       EXPR_SPEC_DONE_DS (expr) = ds;
-      return 0;
+      return current_ds != ds ? 1 : 0;
       
     case 1:
       {
@@ -2016,7 +2017,10 @@ speculate_expr (expr_t expr, ds_t ds)
            insns.  */
         if (bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr)), 
                           expr_dest_regno (expr)))
-          EXPR_TARGET_AVAILABLE (expr) = false;
+          {
+            EXPR_TARGET_AVAILABLE (expr) = false;
+            return 2;
+          }
 
 	return 1;
       }
@@ -2638,6 +2642,36 @@ first_time_insn_init (insn_t insn)
   return INSN_ANALYZED_DEPS (insn) == NULL;
 }
 
+/* Hash an entry in a transformed_insns hashtable.  */
+static hashval_t
+hash_transformed_insns (const void *p)
+{
+  return VINSN_HASH_RTX (((struct transformed_insns *) p)->vinsn_old);
+}
+
+/* Compare the entries in a transformed_insns hashtable.  */
+static int
+eq_transformed_insns (const void *p, const void *q)
+{
+  rtx i1 = VINSN_INSN_RTX (((struct transformed_insns *) p)->vinsn_old);
+  rtx i2 = VINSN_INSN_RTX (((struct transformed_insns *) q)->vinsn_old);
+
+  if (INSN_UID (i1) == INSN_UID (i2))
+    return 1;
+  return rtx_equal_p (PATTERN (i1), PATTERN (i2));
+}
+
+/* Free an entry in a transformed_insns hashtable.  */
+static void
+free_transformed_insns (void *p)
+{
+  struct transformed_insns *pti = (struct transformed_insns *) p;
+
+  vinsn_detach (pti->vinsn_old);
+  vinsn_detach (pti->vinsn_new);
+  free (pti);
+}
+
 /* Init the s_i_d data for INSN which should be inited just once, when 
    we first see the insn.  */
 static void
@@ -2651,6 +2685,9 @@ init_first_time_insn_data (insn_t insn)
     {
       INSN_ANALYZED_DEPS (insn) = BITMAP_ALLOC (NULL);
       INSN_FOUND_DEPS (insn) = BITMAP_ALLOC (NULL);
+      INSN_TRANSFORMED_INSNS (insn) 
+        = htab_create (16, hash_transformed_insns,
+                       eq_transformed_insns, free_transformed_insns);
       init_deps (&INSN_DEPS_CONTEXT (insn));
     }
 }
@@ -2663,6 +2700,7 @@ free_first_time_insn_data (insn_t insn)
 
   BITMAP_FREE (INSN_ANALYZED_DEPS (insn));
   BITMAP_FREE (INSN_FOUND_DEPS (insn));
+  htab_delete (INSN_TRANSFORMED_INSNS (insn));
 
   /* This is allocated only for bookkeeping insns.  */
   if (INSN_ORIGINATORS (insn))
@@ -2794,11 +2832,12 @@ finish_global_and_expr_insn (insn_t insn)
   if (INSN_LUID (insn) > 0)
     {
       free_first_time_insn_data (insn);
-
       INSN_WS_LEVEL (insn) = 0;
-
-      gcc_assert (VINSN_COUNT (INSN_VINSN (insn)) == 1);
-
+      
+      /* We can no longer assert this, as vinsns of this insn could be 
+         easily live in other insn's caches.  This should be changed to 
+         a counter-like approach among all vinsns.  */
+      gcc_assert (true || VINSN_COUNT (INSN_VINSN (insn)) == 1);
       clear_expr (INSN_EXPR (insn));
     }
 }
@@ -3619,6 +3658,7 @@ finish_insns (void)
 	{
 	  BITMAP_FREE (sid_entry->analyzed_deps);
 	  BITMAP_FREE (sid_entry->found_deps);
+          htab_delete (sid_entry->transformed_insns);
 	  free_deps (&sid_entry->deps_context);
 	}
     }
diff --git a/gcc/sel-sched-ir.h b/gcc/sel-sched-ir.h
index b1df3b1d22f..07ec8cd4493 100644
--- a/gcc/sel-sched-ir.h
+++ b/gcc/sel-sched-ir.h
@@ -604,6 +604,9 @@ struct vinsn_def
      hash_rtx.  It is not placed in ID for faster compares.  */
   unsigned hash;
 
+  /* Hash of the insn_rtx pattern.  */
+  unsigned hash_rtx;
+
   /* Smart pointer counter.  */
   int count;
 
@@ -621,6 +624,7 @@ struct vinsn_def
 
 #define VINSN_ID(VI) ((VI)->id)
 #define VINSN_HASH(VI) ((VI)->hash)
+#define VINSN_HASH_RTX(VI) ((VI)->hash_rtx)
 #define VINSN_TYPE(VI) (IDATA_TYPE (VINSN_ID (VI)))
 #define VINSN_SEPARABLE_P(VI) (VINSN_TYPE (VI) == SET)
 #define VINSN_CLONABLE_P(VI) (VINSN_SEPARABLE_P (VI) || VINSN_TYPE (VI) == USE)
@@ -630,13 +634,28 @@ struct vinsn_def
 #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)))
-
 #define VINSN_COUNT(VI) ((VI)->count)
-
 #define VINSN_MAY_TRAP_P(VI) ((VI)->may_trap_p)
-
 
 
+/* An entry of the hashtable describing transformations happened when 
+   moving up through an insn.  */
+struct transformed_insns
+{
+  /* Previous vinsn.  Used to find the proper element.  */
+  vinsn_t vinsn_old;
+  /* A new vinsn.  */
+  vinsn_t vinsn_new;
+  /* Speculative status.  */
+  ds_t ds;
+  /* Type of transformation happened.  */
+  enum local_trans_type type;
+  /* Whether a conflict on the target register happened.  */
+  BOOL_BITFIELD was_target_conflict : 1;
+  /* Whether a check was needed.  */
+  BOOL_BITFIELD needs_check : 1;
+};
+
 /* Indexed by INSN_LUID, the collection of all data associated with
    a single instruction that is in the stream.  */
 struct _sel_insn_data
@@ -666,6 +685,9 @@ struct _sel_insn_data
   /* An INSN_UID bit is set when this is a bookkeeping insn generated from 
      a parent with this uid.  */
   bitmap originators;
+
+  /* A hashtable caching the result of insn transformations through this one.  */
+  htab_t transformed_insns;
   
   /* A context incapsulating this insn.  */
   struct deps deps_context;
@@ -713,7 +735,7 @@ extern sel_insn_data_def insn_sid (insn_t);
 #define INSN_DEPS_CONTEXT(INSN) (SID (INSN)->deps_context) 
 #define INSN_ORIGINATORS(INSN) (SID (INSN)->originators)
 #define INSN_ORIGINATORS_BY_UID(UID) (SID_BY_UID (UID)->originators)
-
+#define INSN_TRANSFORMED_INSNS(INSN) (SID (INSN)->transformed_insns)
 
 #define INSN_EXPR(INSN) (&SID (INSN)->_expr)
 #define INSN_VINSN(INSN) (RHS_VINSN (INSN_EXPR (INSN)))
diff --git a/gcc/sel-sched.c b/gcc/sel-sched.c
index 4c52d221aed..208034b89a9 100644
--- a/gcc/sel-sched.c
+++ b/gcc/sel-sched.c
@@ -1563,15 +1563,17 @@ undo_transformations (av_set_t *av_ptr, rtx insn)
               {
                 ds_t old_ds, new_ds;
                 
+                /* Compute the difference between old and new speculative
+                   statuses: that's what we need to check.  
+                   Earlier we used to assert that the status will really
+                   change.  This no longer works because only the probability
+                   bits in the status may have changed during compute_av_set,
+                   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;
                 new_ds = EXPR_SPEC_DONE_DS (rhs);
-                gcc_assert (spec_info && sel_speculation_p
-                            && new_ds 
-                            && ((old_ds & SPECULATIVE) 
-                                != (new_ds & SPECULATIVE)));
 
-                /* Compute the difference between old and new speculative
-                   statuses: that's what we need to check.  */
                 old_ds &= SPECULATIVE;
                 new_ds &= SPECULATIVE;
                 new_ds &= ~old_ds;
@@ -1666,6 +1668,9 @@ moveup_rhs_inside_insn_group (rhs_t insn_to_move_up, insn_t through_insn)
    && !sel_insn_has_single_succ_p ((through_insn), SUCCS_ALL) \
    && !sel_insn_is_speculation_check (through_insn))
 
+/* True when a conflict on a target register was found during moveup_rhs.  */
+static bool was_target_conflict = false;
+
 /* Modifies INSN_TO_MOVE_UP so it can be moved through the THROUGH_INSN,
    performing necessary transformations.  Record the type of transformation 
    made in PTRANS_TYPE, when it is not NULL.  When INSIDE_INSN_GROUP, 
@@ -1737,6 +1742,7 @@ moveup_rhs (rhs_t insn_to_move_up, insn_t through_insn, bool inside_insn_group,
   else
     gcc_assert (!control_flow_insn_p (insn));
 
+  was_target_conflict = false;
   full_ds = has_dependence_p (insn_to_move_up, through_insn, &has_dep_p);
 
   if (full_ds == 0)
@@ -1761,7 +1767,9 @@ moveup_rhs (rhs_t insn_to_move_up, insn_t through_insn, bool inside_insn_group,
 	{
           /* Speculation was successful.  */
           full_ds = 0;
-          was_changed = (res == 1);
+          was_changed = (res > 0);
+          if (res == 2)
+            was_target_conflict = true;
           if (ptrans_type)
             *ptrans_type = TRANS_SPECULATION;
 	  sel_clear_has_dependence ();
@@ -1781,6 +1789,7 @@ moveup_rhs (rhs_t insn_to_move_up, insn_t through_insn, bool inside_insn_group,
         return MOVEUP_RHS_NULL;
 
       EXPR_TARGET_AVAILABLE (insn_to_move_up) = false;
+      was_target_conflict = true;
       as_rhs = true;
     }
 
@@ -1815,7 +1824,9 @@ moveup_rhs (rhs_t insn_to_move_up, insn_t through_insn, bool inside_insn_group,
             {
               /* Speculation was successful.  */
               *rhs_dsp = 0;
-              was_changed = (res == 1);
+              was_changed = (res > 0);
+              if (res == 2)
+                was_target_conflict = true;
               if (ptrans_type)
                 *ptrans_type = TRANS_SPECULATION;
             }
@@ -1899,10 +1910,46 @@ moveup_set_rhs (av_set_t *avp, insn_t insn, bool inside_insn_group)
           line_finish ();
           continue;
         }
+      else
+        {
+          struct transformed_insns *pti 
+            = htab_find_with_hash (INSN_TRANSFORMED_INSNS (insn),
+                                   &expr_old_vinsn, 
+                                   VINSN_HASH_RTX (expr_old_vinsn));
+          if (pti)
+            {
+              /* This RHS was already moved through this insn and was 
+                 changed as a result.  Fetch the proper data from 
+                 the hashtable.  */
+              insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (rhs), 
+                                      INSN_UID (insn), pti->type, 
+                                      pti->vinsn_old, pti->vinsn_new, 
+                                      EXPR_SPEC_DONE_DS (rhs));
+              change_vinsn_in_expr (rhs, pti->vinsn_new);
+              if (pti->was_target_conflict)
+                EXPR_TARGET_AVAILABLE (rhs) = false;
+              if (pti->type == TRANS_SPECULATION)
+                {
+                  ds_t ds;
+
+                  ds = EXPR_SPEC_DONE_DS (rhs);
+                  
+                  EXPR_SPEC_DONE_DS (rhs) = pti->ds;
+                  EXPR_NEEDS_SPEC_CHECK_P (rhs) |= pti->needs_check;
+                }
+              rhs = merge_with_other_exprs (avp, &i, rhs);
+
+              print (" - changed (cached): ");
+              dump_rhs (rhs);
+              line_finish ();
+              continue;
+            }
+        }
 
       /* ??? Invent something better than this.  We can't allow old_vinsn 
          to go, we need it for the history vector.  */
       vinsn_attach (expr_old_vinsn);
+
       switch (moveup_rhs (rhs, insn, inside_insn_group, &trans_type))
 	{
 	case MOVEUP_RHS_NULL:
@@ -1914,20 +1961,41 @@ moveup_set_rhs (av_set_t *avp, insn_t insn, bool inside_insn_group)
 
 	  print (" - removed");
 	  break;
+
 	case MOVEUP_RHS_CHANGED:
 	  print (" - changed");
-          gcc_assert (INSN_UID (EXPR_INSN_RTX (rhs)) != rhs_uid);
+          gcc_assert (INSN_UID (EXPR_INSN_RTX (rhs)) != rhs_uid
+                      || EXPR_SPEC_DONE_DS (rhs) != expr_old_spec_ds);
 
           /* Mark that this insn changed this expr.  */
           insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (rhs), 
                                   INSN_UID (insn), trans_type, 
                                   expr_old_vinsn, EXPR_VINSN (rhs), 
                                   expr_old_spec_ds);
+          {
+            /* Save the result of transformation to the hashtable.  */
+            struct transformed_insns *pti = XNEW (struct transformed_insns);
+
+            pti->vinsn_old = expr_old_vinsn;
+            pti->vinsn_new = EXPR_VINSN (rhs);
+            pti->type = trans_type;
+            pti->was_target_conflict = was_target_conflict;
+            pti->ds = EXPR_SPEC_DONE_DS (rhs);
+            pti->needs_check = EXPR_NEEDS_SPEC_CHECK_P (rhs);
+            vinsn_attach (pti->vinsn_old);
+            vinsn_attach (pti->vinsn_new);
+            *((struct transformed_insns **) 
+              htab_find_slot_with_hash (INSN_TRANSFORMED_INSNS (insn),
+                                        pti, VINSN_HASH_RTX (expr_old_vinsn),
+                                        INSERT)) = pti;
+          }
+          
           rhs = merge_with_other_exprs (avp, &i, rhs);
 
           print (" result: ");
           dump_rhs (rhs);
 	  break;
+
 	case MOVEUP_RHS_SAME:
           /* Cache that there is a no dependence.  */
           bitmap_set_bit (INSN_ANALYZED_DEPS (insn), rhs_uid);
@@ -1935,6 +2003,7 @@ moveup_set_rhs (av_set_t *avp, insn_t insn, bool inside_insn_group)
 
 	  print (" - unchanged");
 	  break;
+
         case MOVEUP_RHS_AS_RHS:
           /* Only an LHS dependence was found.  Cache that there is 
              no dependence, but the target register is not available.  */
@@ -1944,6 +2013,7 @@ moveup_set_rhs (av_set_t *avp, insn_t insn, bool inside_insn_group)
 
 	  print (" - unchanged (as RHS)");
 	  break;
+
 	default:
 	  gcc_unreachable ();
 	}