This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[sel-sched] Initial caching of dependence queries and various substitution fixes


Hello,

These patches start our work on compile-time numbers, which are not that great atm. The first patch adds a bitmap to every expression that records the insns on which that expression was changed. Later, we undo transformations only for the recorded insns. The second patch adds two bitmaps to the insn data, which are used for marking those insns that are already analyzed and found to have no dependence or hard dependence. This reduces the number of queries to the dependence analyzer. In the future, we will do better with creating read-only dependence contexts, so that every insn will have a context with insn's effects reflected in it, and that context will not change when propagating anything through this insn.

The third patch fixes substitution to work, which was accidentally broken with the updates to the scheduler infrastructure. There are a couple of thinkos fixed. Two problems worth noting are disabling substitution for 'reg=const' insns, as we did previously for subregs (that is because we cannot deduce the original form of an instruction just looking on the result and the insn we're propagating through), and removing from av sets any expression that uses registers set by the current insn. We were thinking about the latter fix as an optimization, but it is really needed for correctness. Unfortunately, this patch revealed that we can't use bitmaps for caching insns on which an expression was changed, so this is disabled until I will turn this to vectors. I would like to commit the vector fix after the speculation updates will go in.

Bootstrapped and tested on ia64-linux, committed to sel-sched branch.

Andrey


2007-06-14 Andrey Belevantsev <abel@ispras.ru>


        * sel-sched-ir.h (struct _expr): New field changed_on_insns.
        (EXPR_CHANGED_ON_INSNS): New macro.
        (copy_expr_onside): Declare.

* sel-sched.c: Kill #if 0'd code.
(undo_transformations): New function.
(un_substitute): Adapt for undo_transformations. Add RHS parameter,
rename AV_PTR parameter to NEW_SET_PTR. Kill #if 0'd code. Process
just one RHS instead of looping through the whole av set.
(un_speculate): Likewise.
(moveup_set_rhs): When an expr has been changed, mark this.
(equal_after_moveup_path_p): Use copy_expr_onside instead of
copy_expr.
(generate_bookkeeping_insns): Likewise.
(find_used_regs_1): Use undo_transformations.
(move_op): Likewise. Also use copy_expr_onside.


* sel-sched-ir.c (init_expr): Add changed_on parameter. Use it.
Update all callers.
(copy_expr_onside): New function.
(merge_expr_data): Merge cache bitmaps.
(clear_expr): Free the cache bitmap.
(av_set_union_and_clear): Set *FROMP to NULL to mark that it's empty.


	
2007-06-14  Andrey Belevantsev  <abel@ispras.ru>

	* sel-sched.c (moveup_set_rhs): When analyzing an expression,
	first check the caches.  When a hard dependence/no dependence
	is found, record this in the caches.

	* sel-sched-ir.h (struct sel_insn_data): Reorder fields.
	New fields analyzed_deps, found_deps.
	(INSN_ANALYZED_DEPS, INSN_FOUND_DEPS): New macros.
	
	* sel-sched-ir.c (init_global_and_expr_for_insn, init_insn,
	init_simplejump): Initialize INSN_ANALYZED_DEPS and
	INSN_FOUND_DEPS caches.
	(finish_global_and_expr_1): Free them.


2007-06-14 Andrey Belevantsev <abel@ispras.ru> Alexander Monakov <amonakov@ispras.ru>

	* sel-sched.c (substitue_reg_in_rhs): Fix vertical spacing.
	(un_substitute): Use correct vinsn when fixing expr.
	(identical_copy_p): New function.
	(undo_transformations): Use it when killing from the current av set
	all exprs that use registers set by an insn.  Do not use
	expression caches for now.
	(moveup_rhs): Fix spacing.  Add missing line_finish ().

	* sel-sched-ir.c (deps_init_id_finish_insn): When downgrading to USE,
	leave LHS and RHS fields of an expression intact for future use.
	(insn_eligible_for_subst_p): Fix thinko.  Do not consider 'reg=const'
	insns.
Index: gcc/sel-sched.c
===================================================================
--- gcc/sel-sched.c	(revision 125704)
+++ gcc/sel-sched.c	(working copy)
@@ -442,153 +442,76 @@ rtx_search (rtx what, rtx where)
   return (count_occurrences_equiv (what, where, 1) > 0);
 }
 
-/* FIXME: see comment in the un_substitute function regarding filtering
-   input av_set.  */
-#if 0
-/* Remove all RHSes which use X from av_set DATA.  Auxiliary function for 
-   un_substitute.  */
-static void
-remove_if_has_source (rtx x, rtx pat ATTRIBUTE_UNUSED, void *data)
-{
-  rtx_search_arg_p arg = (rtx_search_arg_p) data;
-  rhs_t rhs;
-
-  /* Already removed with another call.  */
-  if (arg->n > 0)
-    return;
-
-  /* Don't count scratches.  */
-  if (GET_CODE (x) == SCRATCH)
-    return;
-
-  arg->n++;
-
-  rhs = _AV_SET_RHS (*arg->iter->lp);
-
-  if (RHS_SCHEDULE_AS_RHS (rhs))
-    {
-      /* Search only in VINSN_RHS.  */
-      if (rtx_search (x, VINSN_RHS (RHS_VINSN (rhs))))
-	av_set_iter_remove (arg->iter);
-    }
-  else
-    {
-      /* Search the whole insn.  Count also set's dest.  */
-      if (rtx_search (x, RHS_PAT (rhs)))
-	av_set_iter_remove (arg->iter);
-    }
-}
-#endif
-
 /* if INSN is a copy x:=y and if there is an rhs r in AV that uses y, 
    it adds all variants of r to AV derived by replacing one or more
    occurrences of y by x.  */
 static void
-un_substitute (av_set_t *av_ptr, rtx insn)
+un_substitute (rhs_t rhs, rtx insn, av_set_t *new_set_ptr)
 {
-  av_set_iterator av_iter;
-  rhs_t rhs;
-  av_set_t new_set;
   rtx pat, src_reg, dst_reg;
-
+  vinsn_t vi;
+  rtx where_count;
+  unsigned n_occur;
+  unsigned long bitmask;
+  
   if (!flag_sel_sched_substitution)
     return;
 
-  new_set = NULL;
-
-  pat = PATTERN (insn);
-
-
-  /* FIXME: Enable *AV_PTR filtering, so un_substitute will remove those
-     elements of AV whose sources (and destinations for !RHS_SCHEDULE_AS_RHS 
-     rhses) are set by INSN.  This filtering used for optimization, and it's
-     presence doesn't affect the correctness.  */
-#if 0
-  /* First remove all elements of SETP whose sources are set by INSN, but
-     it's insn isn't conditionally mutexed by the predicates.  */
-  FOR_EACH_RHS_1 (rhs, av_iter, av_ptr)
-    {
-      struct rtx_search_arg arg;
-
-      arg.iter = &av_iter;
-      /* Only first note_store matters.  */
-      arg.n = 0;
-
-      /* FIXME: this is written with assumption that cond_execs are not yet
-	 schedulable as rhses.  */
-      gcc_assert (rhs == _AV_SET_RHS (*av_iter.lp));
-      if (RHS_SCHEDULE_AS_RHS (rhs) 
-	  || !sched_insns_conditions_mutex_p (insn, RHS_INSN (rhs)))
-	note_stores (pat, remove_if_has_source, (void *) &arg);
-    }
-#endif
-
   /* Catch X := Y insns, where X and Y are regs.  Otherwise return.  */
   if (!insn_eligible_for_subst_p (insn))
     return;
 
+  pat = PATTERN (insn);
   src_reg = SET_SRC (pat);
   dst_reg = SET_DEST (pat);
+  vi = RHS_VINSN (rhs);
 
-  FOR_EACH_RHS (rhs, av_iter, *av_ptr)
-    {
-      vinsn_t vi = RHS_VINSN (rhs);
-      rtx where_count;
-      unsigned n_occur;
-      unsigned long bitmask;
-
-      where_count = (VINSN_SEPARABLE_P (vi) ?
-		     VINSN_RHS (vi) : VINSN_PATTERN (vi));
-
-      n_occur = count_occurrences_equiv (src_reg, where_count, 0);
-
-      /* Try next rhs, if no occurences.  */
-      if (!n_occur)
-	continue;
-
-      /* Make sure we have enough bits to handle all substitutions.  */
-      gcc_assert (n_occur < sizeof (unsigned long) * 8);
-
-      /* Generate the replacement mask and perform the substitution
-	 according to it.  Every "one" with index K in bitmap mask means 
-	 we change the K-th occurence of SRC_REG with DST_REG, "0" means we
-	 skip it.  We already have the replacement configuration for 
-	 bitmask == 0 in the original set.  */	 
-      for (bitmask = 1; bitmask < ((unsigned long)1 << n_occur); bitmask++)
-	{
-	  vinsn_t vi = RHS_VINSN (rhs);
-	  expr_def _tmp_rhs, *tmp_rhs = &_tmp_rhs;
-	  rtx new_insn;
-	  rtx *wherep;
-
-  	  new_insn = create_copy_of_insn_rtx (VINSN_INSN (vi));
-
-	  wherep = (VINSN_SEPARABLE_P (vi)
-		    ? &SET_SRC (PATTERN (new_insn))
-		    : &PATTERN (new_insn));
-
-	  replace_in_rtx_using_bitmask (wherep, src_reg, dst_reg, bitmask);
+  where_count = (VINSN_SEPARABLE_P (vi) 
+                 ? VINSN_RHS (vi) : VINSN_PATTERN (vi));
 
-	  if (!insn_rtx_valid (new_insn))
-	    {
-	      /* It would nice to free new_insn or return it to some pool.  */
-	      continue;
-	    }
+  n_occur = count_occurrences_equiv (src_reg, where_count, 0);
 
-	  vi = create_vinsn_from_insn_rtx (new_insn);
+  /* Try next rhs, if no occurences.  */
+  if (!n_occur)
+    return;
+  
+  /* Make sure we have enough bits to handle all substitutions.  */
+  gcc_assert (n_occur < sizeof (unsigned long) * 8);
 
-	  gcc_assert (VINSN_SEPARABLE_P (vi)
-		      == EXPR_SEPARABLE_P (rhs));
+  /* Generate the replacement mask and perform the substitution
+     according to it.  Every "one" with index K in bitmap mask means 
+     we change the K-th occurence of SRC_REG with DST_REG, "0" means we
+     skip it.  We already have the replacement configuration for 
+     bitmask == 0 in the original set.  */	 
+  for (bitmask = 1; bitmask < ((unsigned long)1 << n_occur); bitmask++)
+    {
+      expr_def _tmp_rhs, *tmp_rhs = &_tmp_rhs;
+      rtx new_insn;
+      vinsn_t new_vi;
+      rtx *wherep;
 
-	  copy_expr (tmp_rhs, rhs);
-	  change_vinsn_in_expr (tmp_rhs, vi);
+      new_insn = create_copy_of_insn_rtx (VINSN_INSN (vi));
 
-	  av_set_add (&new_set, tmp_rhs);
+      wherep = (VINSN_SEPARABLE_P (vi)
+                ? &SET_SRC (PATTERN (new_insn))
+                : &PATTERN (new_insn));
+      
+      replace_in_rtx_using_bitmask (wherep, src_reg, dst_reg, bitmask);
+      
+      if (!insn_rtx_valid (new_insn))
+        continue;
+      
+      new_vi = create_vinsn_from_insn_rtx (new_insn);
 
-	  clear_expr (tmp_rhs);
-	}
+      gcc_assert (VINSN_SEPARABLE_P (new_vi) == EXPR_SEPARABLE_P (rhs));
+      
+      copy_expr (tmp_rhs, rhs);
+      change_vinsn_in_expr (tmp_rhs, vi);
+      
+      av_set_add (new_set_ptr, tmp_rhs);
+      
+      clear_expr (tmp_rhs);
     }
-  av_set_union_and_clear (av_ptr, &new_set);
 }
 
 
@@ -1481,55 +1404,72 @@ has_spec_dependence_p (expr_t expr, insn
 /* Add to AVP those exprs that might have been transformed to their speculative
    versions when moved through INSN.  */
 static void
-un_speculate (av_set_t *avp, insn_t insn)
+un_speculate (expr_t expr, insn_t insn, av_set_t *new_set_ptr)
 {
-  av_set_iterator av_it;
-  expr_t expr;
-  av_set_t new_av;
+  ds_t expr_spec_done_ds;
+  ds_t full_ds;
 
   if (spec_info == NULL || !sel_speculation_p)
     return;
+  
+  expr_spec_done_ds = EXPR_SPEC_DONE_DS (expr);
+  if (expr_spec_done_ds == 0)
+    return;
 
-  new_av = NULL;
-
-  FOR_EACH_RHS (expr, av_it, *avp)
+  full_ds = has_spec_dependence_p (expr, insn);
+  if (full_ds == 0)
+    return;
+  
+  {
+    expr_def _new_expr, *new_expr = &_new_expr;
+    
+    copy_expr (new_expr, expr);
+    
     {
-      ds_t expr_spec_done_ds = EXPR_SPEC_DONE_DS (expr);
-      ds_t full_ds;
-
-      if (expr_spec_done_ds == 0)
-	continue;
-
-      full_ds = has_spec_dependence_p (expr, insn);
-
-      if (full_ds == 0)
-	continue;
-
-      {
-	expr_def _new_expr, *new_expr = &_new_expr;
-
-	copy_expr (new_expr, expr);
-
-	{
-	  bool b;
-
-	  full_ds = ds_get_speculation_types (full_ds);
-	  expr_spec_done_ds &= ~full_ds;
-
-	  b = apply_spec_to_expr (new_expr, expr_spec_done_ds);
-	  gcc_assert (b);
+      bool b;
+      
+      full_ds = ds_get_speculation_types (full_ds);
+      expr_spec_done_ds &= ~full_ds;
+      
+      b = apply_spec_to_expr (new_expr, expr_spec_done_ds);
+      gcc_assert (b);
+      
+      EXPR_SPEC_TO_CHECK_DS (new_expr) |= full_ds;
+    }
+    
+    av_set_add (new_set_ptr, new_expr);
+    
+    clear_expr (new_expr);
+  }
+}
 
-	  EXPR_SPEC_TO_CHECK_DS (new_expr) |= full_ds;
-	}
 
-	av_set_add (&new_av, new_expr);
+/* Undo all transformations on *AV_PTR that were done when 
+   moving through INSN.  */
+static void
+undo_transformations (av_set_t *av_ptr, rtx insn)
+{
+  av_set_iterator av_iter;
+  rhs_t rhs;
+  av_set_t new_set = NULL;
 
-	clear_expr (new_expr);
-      }
+  FOR_EACH_RHS (rhs, av_iter, *av_ptr)
+    {
+      if (bitmap_bit_p (EXPR_CHANGED_ON_INSNS (rhs), INSN_LUID (insn)))
+        un_speculate (rhs, insn, &new_set);
     }
+  
+  av_set_union_and_clear (av_ptr, &new_set);
 
-  av_set_union_and_clear (avp, &new_av);
+  FOR_EACH_RHS (rhs, av_iter, *av_ptr)
+    {
+      if (bitmap_bit_p (EXPR_CHANGED_ON_INSNS (rhs), INSN_LUID (insn)))
+        un_substitute (rhs, insn, &new_set);
+    }
+  
+  av_set_union_and_clear (av_ptr, &new_set);
 }
+
 
 /* Moveup_* helpers for code motion and computing av sets.  */
 
@@ -1759,6 +1699,9 @@ moveup_set_rhs (av_set_t *avp, insn_t in
 	  break;
 	case MOVEUP_RHS_CHANGED:
 	  print (" - changed");
+          
+          /* Mark that this insn changed this expr.  */
+          bitmap_set_bit (EXPR_CHANGED_ON_INSNS (rhs), INSN_LUID (insn));
 
 	  {
 	    rhs_t rhs2 = av_set_lookup_other_equiv_rhs (*avp, RHS_VINSN (rhs));
@@ -1846,7 +1789,7 @@ equal_after_moveup_path_p (rhs_t cur_rhs
   expr_def _tmp, *tmp = &_tmp;
   bool res_p;
 
-  copy_expr (tmp, cur_rhs);
+  copy_expr_onside (tmp, cur_rhs);
 
   if (path)
     {
@@ -2409,9 +2352,7 @@ find_used_regs_1 (insn_t insn, av_set_t 
 	 To find them below it, we have to un-speculate and un-substitute
 	 them.  */
 
-      un_speculate (&orig_ops, insn);
-
-      un_substitute (&orig_ops, insn);
+      undo_transformations (&orig_ops, insn);
 
       /* If all original operands have been filtered on this branch,
 	 return.  */
@@ -3357,7 +3298,7 @@ generate_bookkeeping_insn (rhs_t c_rhs, 
 
     new_insn_rtx = create_copy_of_insn_rtx (EXPR_INSN_RTX (c_rhs));
     new_vinsn = create_vinsn_from_insn_rtx (new_insn_rtx);
-    copy_expr (new_expr, c_rhs);
+    copy_expr_onside (new_expr, c_rhs);
     change_vinsn_in_expr (new_expr, new_vinsn);
 
     if (EXPR_SCHED_TIMES (new_expr)
@@ -3973,7 +3914,7 @@ move_op (insn_t insn, av_set_t orig_ops,
     /* We have found the original operation.  Replace it by REG, if 
        it is scheduled as RHS, or just remove it later, if it's an insn.  */
     {
-      copy_expr (c_rhs, INSN_EXPR (insn));
+      copy_expr_onside (c_rhs, INSN_EXPR (insn));
       c_rhs_inited_p = true;
 
       /* When an insn we found is not equal to the insn from the orig_ops 
@@ -4106,13 +4047,9 @@ move_op (insn_t insn, av_set_t orig_ops,
 	   clonable but not separable insns.  */
 	av_set_clear (&orig_ops);
       else
-	{
-	  un_speculate (&orig_ops, insn);
-
-	  /* Av set ops could have been changed when moving through this insn.
-	     To find them below it, we have to un-substitute them.  */
-	  un_substitute (&orig_ops, insn);
-	}
+        /* Av set ops could have been changed when moving through this insn.
+           To find them below it, we have to un-substitute them.  */
+        undo_transformations (&orig_ops, insn);
 
       /* If all original opernads have been filtered on this branch,
 	 return.  */
@@ -4149,7 +4086,7 @@ move_op (insn_t insn, av_set_t orig_ops,
 
 	      if (!c_rhs_inited_p)
 		{
-		  copy_expr (c_rhs, x);
+		  copy_expr_onside (c_rhs, x);
 		  c_rhs_inited_p = true;
 		}
 	      else
Index: gcc/sel-sched-ir.c
===================================================================
--- gcc/sel-sched-ir.c	(revision 125704)
+++ gcc/sel-sched-ir.c	(working copy)
@@ -1128,7 +1128,7 @@ vinsns_correlate_as_rhses_p (vinsn_t x, 
 /* Initialize RHS.  */
 static void
 init_expr (expr_t expr, vinsn_t vi, int spec, int priority, int sched_times,
-	   ds_t spec_done_ds, ds_t spec_to_check_ds)
+	   ds_t spec_done_ds, ds_t spec_to_check_ds, bitmap changed_on)
 {
   vinsn_attach (vi);
 
@@ -1138,15 +1138,33 @@ init_expr (expr_t expr, vinsn_t vi, int 
   EXPR_SCHED_TIMES (expr) = sched_times;
   EXPR_SPEC_DONE_DS (expr) = spec_done_ds;
   EXPR_SPEC_TO_CHECK_DS (expr) = spec_to_check_ds;
+
+  if (changed_on)
+    EXPR_CHANGED_ON_INSNS (expr) = changed_on;
+  else
+    EXPR_CHANGED_ON_INSNS (expr) = BITMAP_ALLOC (NULL);
 }
 
 /* Make a copy of the rhs FROM into the rhs TO.  */
 void
 copy_expr (expr_t to, expr_t from)
 {
+  bitmap temp = BITMAP_ALLOC (NULL);
+
+  bitmap_copy (temp, EXPR_CHANGED_ON_INSNS (from));
   init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from), EXPR_PRIORITY (from),
 	     EXPR_SCHED_TIMES (from), EXPR_SPEC_DONE_DS (from),
-	     EXPR_SPEC_TO_CHECK_DS (from));
+	     EXPR_SPEC_TO_CHECK_DS (from), temp);
+}
+
+/* Same, but the final expr will not ever be in av sets, so don't copy 
+   "uninteresting" data such as bitmap cache.  */
+void
+copy_expr_onside (expr_t to, expr_t from)
+{
+  init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from), EXPR_PRIORITY (from),
+	     EXPR_SCHED_TIMES (from), EXPR_SPEC_DONE_DS (from),
+	     EXPR_SPEC_TO_CHECK_DS (from), NULL);
 }
 
 /* Merge bits of FROM rhs to TO rhs.  */
@@ -1168,6 +1186,8 @@ merge_expr_data (expr_t to, expr_t from)
 					  EXPR_SPEC_DONE_DS (from));
 
   EXPR_SPEC_TO_CHECK_DS (to) |= EXPR_SPEC_TO_CHECK_DS (from);
+  bitmap_ior_into (EXPR_CHANGED_ON_INSNS (to),
+                   EXPR_CHANGED_ON_INSNS (from));
 }
 
 /* Merge bits of FROM rhs to TO rhs.  Vinsns in the rhses should correlate.  */
@@ -1189,6 +1209,7 @@ clear_expr (rhs_t rhs)
 {
   vinsn_detach (RHS_VINSN (rhs));
   RHS_VINSN (rhs) = NULL;
+  BITMAP_FREE (EXPR_CHANGED_ON_INSNS (rhs));
 }
 
 
@@ -1297,6 +1318,7 @@ av_set_union_and_clear (av_set_t *top, a
 
   /* Connect FROMP to the end of the TOP.  */
   *i.lp = *fromp;
+  *fromp = NULL;
 }
 
 /* Clear av_set pointed to by SETP.  */
@@ -1653,7 +1675,7 @@ init_global_and_expr_for_insn (insn_t in
 
     /* Initialize INSN's expr.  */
     init_expr (INSN_EXPR (insn), vinsn_create (insn, force_unique_p), 0,
-	       INSN_PRIORITY (insn), 0, spec_done_ds, 0);
+	       INSN_PRIORITY (insn), 0, spec_done_ds, 0, NULL);
   }
 }
 
@@ -2502,7 +2524,8 @@ init_simplejump (insn_t insn)
       COPY_REG_SET (LV_SET (insn), LV_SET (succ));
     }
 
-  init_expr (INSN_EXPR (insn), vinsn_create (insn, false), 0, 0, 0, 0, 0);
+  init_expr (INSN_EXPR (insn), vinsn_create (insn, false), 0, 0, 0, 
+             0, 0, NULL);
 
   INSN_SEQNO (insn) = get_seqno_of_a_pred (insn);
 }
Index: gcc/sel-sched-ir.h
===================================================================
--- gcc/sel-sched-ir.h	(revision 125704)
+++ gcc/sel-sched-ir.h	(working copy)
@@ -106,6 +106,10 @@ struct _expr
   /* SPEC_TO_CHECK_DS hold speculation types that should be checked
      (used only during move_op ()).  */
   ds_t spec_to_check_ds;
+
+  /* Here an INSN_LUID (insn) bit is set when this expr was changed when 
+     moving through insn.  */
+  bitmap changed_on_insns;
 };
 
 typedef struct _expr expr_def;
@@ -127,6 +131,7 @@ typedef expr_t rhs_t;
 #define EXPR_SCHED_TIMES(EXPR) ((EXPR)->sched_times)
 #define EXPR_SPEC_DONE_DS(EXPR) ((EXPR)->spec_done_ds)
 #define EXPR_SPEC_TO_CHECK_DS(EXPR) ((EXPR)->spec_to_check_ds)
+#define EXPR_CHANGED_ON_INSNS(EXPR) ((EXPR)->changed_on_insns)
 
 /* Obsolete. */
 #define RHS_VINSN(RHS) ((RHS)->vinsn)
@@ -835,6 +840,7 @@ extern insn_t sel_gen_insn_from_expr_aft
 /* RHS functions.  */
 extern bool vinsns_correlate_as_rhses_p (vinsn_t, vinsn_t);
 extern void copy_expr (expr_t, expr_t);
+extern void copy_expr_onside (expr_t, expr_t);
 extern void merge_expr_data (expr_t, expr_t);
 extern void merge_expr (expr_t, expr_t);
 extern void clear_expr (expr_t);
Index: gcc/sel-sched.c
===================================================================
--- gcc/sel-sched.c	(revision 125706)
+++ gcc/sel-sched.c	(working copy)
@@ -1688,12 +1688,37 @@ moveup_set_rhs (av_set_t *avp, insn_t in
 
   FOR_EACH_RHS_1 (rhs, i, avp)    
     { 
+      int rhs_uid = INSN_UID (EXPR_INSN_RTX (rhs));
+      bool unique_p = VINSN_UNIQUE_P (RHS_VINSN (rhs));
+
       line_start ();
       dump_rhs (rhs);
 
+      /* First check whether we've analyzed this situation already.  */
+      if (bitmap_bit_p (INSN_ANALYZED_DEPS (insn), rhs_uid))
+        {
+          if (bitmap_bit_p (INSN_FOUND_DEPS (insn), rhs_uid))
+            {
+              av_set_iter_remove (&i);
+              print (" - removed (cached)");
+            }
+          else
+            print (" - unchanged (cached)");
+
+          line_finish ();
+          continue;
+        }
+      
       switch (moveup_rhs (rhs, insn, inside_insn_group))
 	{
 	case MOVEUP_RHS_NULL:
+          /* Cache that there is a hard dependence.  */
+          if (!unique_p)
+            {
+              bitmap_set_bit (INSN_ANALYZED_DEPS (insn), rhs_uid);
+              bitmap_set_bit (INSN_FOUND_DEPS (insn), rhs_uid);
+            }
+
 	  av_set_iter_remove (&i);
 	  print (" - removed");
 	  break;
@@ -1723,6 +1748,13 @@ moveup_set_rhs (av_set_t *avp, insn_t in
 	  }
 	  break;
 	case MOVEUP_RHS_SAME:
+          /* Cache that there is a no dependence.  */
+          if (!unique_p)
+            {
+              bitmap_set_bit (INSN_ANALYZED_DEPS (insn), rhs_uid);
+              bitmap_clear_bit (INSN_FOUND_DEPS (insn), rhs_uid);
+            }
+
 	  print (" - unchanged");
 	  break;
 	default:
Index: gcc/sel-sched-ir.c
===================================================================
--- gcc/sel-sched-ir.c	(revision 125706)
+++ gcc/sel-sched-ir.c	(working copy)
@@ -1677,6 +1677,9 @@ init_global_and_expr_for_insn (insn_t in
     init_expr (INSN_EXPR (insn), vinsn_create (insn, force_unique_p), 0,
 	       INSN_PRIORITY (insn), 0, spec_done_ds, 0, NULL);
   }
+
+  INSN_ANALYZED_DEPS (insn) = BITMAP_ALLOC (NULL);
+  INSN_FOUND_DEPS (insn) = BITMAP_ALLOC (NULL);
 }
 
 static void extend_insn (void);
@@ -1710,6 +1713,9 @@ finish_global_and_expr_insn_1 (insn_t in
 
   if (INSN_LUID (insn) > 0)
     av_set_clear (&AV_SET (insn));
+
+  BITMAP_FREE (INSN_ANALYZED_DEPS (insn));
+  BITMAP_FREE (INSN_FOUND_DEPS (insn));
 }
 
 /* Perform stage 2 of finalization of the INSN's data.  */
@@ -2507,6 +2513,9 @@ init_insn (insn_t insn)
     change_vinsn_in_expr (expr, vinsn_create (insn, false));
 
   INSN_SEQNO (insn) = ssid->seqno;
+
+  INSN_ANALYZED_DEPS (insn) = BITMAP_ALLOC (NULL);
+  INSN_FOUND_DEPS (insn) = BITMAP_ALLOC (NULL);
 }
 
 /* This is used to initialize spurious jumps generated by
@@ -2528,6 +2537,9 @@ init_simplejump (insn_t insn)
              0, 0, NULL);
 
   INSN_SEQNO (insn) = get_seqno_of_a_pred (insn);
+
+  INSN_ANALYZED_DEPS (insn) = BITMAP_ALLOC (NULL);
+  INSN_FOUND_DEPS (insn) = BITMAP_ALLOC (NULL);
 }
 
 /* This is used to move lv_sets to the first insn of basic block if that
Index: gcc/sel-sched-ir.h
===================================================================
--- gcc/sel-sched-ir.h	(revision 125706)
+++ gcc/sel-sched-ir.h	(working copy)
@@ -552,15 +552,6 @@ struct vinsn_def
    a single instruction that is in the stream.  */
 struct _sel_insn_data
 {
-  /* Insn is an ASM.  */
-  bool asm_p;
-
-  /* This field is initialized at the beginning of scheduling and is used
-     to handle sched group instructions.  If it is non-null, then it points
-     to the instruction, which should be forced to schedule next.  Such
-     instructions are unique.  */
-  insn_t sched_next;
-
   /* Every insn in the stream has an associated vinsn.  This is used
      to reduce memory consumption and give use the fact that many insns
      (all of them at the moment) don't change through the scheduler.
@@ -575,15 +566,32 @@ struct _sel_insn_data
 
   int seqno;
 
-  /* True when an insn is scheduled after we've determined that a stall is
-     required.
-     This is used when emulating the Haifa scheduler for bundling.  */
-  BOOL_BITFIELD after_stall_p : 1;
+  /* An INSN_LUID bit is set when deps analysis result is already known.  */
+  bitmap analyzed_deps;
+
+  /* An INSN_LUID bit is set when a hard dep was found, not set when 
+     no dependence is found.  This is meaningful only when the analyzed_deps
+     bitmap has its bit set.  */
+  bitmap found_deps;
+
+  /* Insn is an ASM.  */
+  bool asm_p;
+
+  /* This field is initialized at the beginning of scheduling and is used
+     to handle sched group instructions.  If it is non-null, then it points
+     to the instruction, which should be forced to schedule next.  Such
+     instructions are unique.  */
+  insn_t sched_next;
 
   /* Cycle at which insn was scheduled.  It is greater than zero if insn was
      scheduled.
      This is used for bundling.  */
   int sched_cycle;
+
+  /* True when an insn is scheduled after we've determined that a stall is
+     required.
+     This is used when emulating the Haifa scheduler for bundling.  */
+  BOOL_BITFIELD after_stall_p : 1;
 };
 
 typedef struct _sel_insn_data sel_insn_data_def;
@@ -593,11 +601,13 @@ DEF_VEC_O (sel_insn_data_def);
 DEF_VEC_ALLOC_O (sel_insn_data_def, heap);
 extern VEC (sel_insn_data_def, heap) *s_i_d;
 
-/* Accessor macros for s_s_i_d.  */
+/* Accessor macros for s_i_d.  */
 #define SID(INSN) (VEC_index (sel_insn_data_def, s_i_d,	INSN_LUID (INSN)))
 
 #define INSN_ASM_P(INSN) (SID (INSN)->asm_p)
 #define INSN_SCHED_NEXT(INSN) (SID (INSN)->sched_next)
+#define INSN_ANALYZED_DEPS(INSN) (SID (INSN)->analyzed_deps)
+#define INSN_FOUND_DEPS(INSN) (SID (INSN)->found_deps) 
 
 #define INSN_EXPR(INSN) (&SID (INSN)->_expr)
 #define INSN_VINSN(INSN) (RHS_VINSN (INSN_EXPR (INSN)))
Index: gcc/sel-sched.c
===================================================================
--- gcc/sel-sched.c	(revision 125707)
+++ gcc/sel-sched.c	(working copy)
@@ -276,6 +276,7 @@ substitute_reg_in_rhs (rhs_t rhs, insn_t
      If the insn is not SET, we may still be able to substitute something
      in it, and if we're here (don't have deps), it doesn't write INSN's 
      dest.  */
+
   where = (VINSN_SEPARABLE_P (*vi)
 	   ? &VINSN_RHS (*vi)
 	   : &PATTERN (VINSN_INSN (*vi)));
@@ -506,7 +507,7 @@ un_substitute (rhs_t rhs, rtx insn, av_s
       gcc_assert (VINSN_SEPARABLE_P (new_vi) == EXPR_SEPARABLE_P (rhs));
       
       copy_expr (tmp_rhs, rhs);
-      change_vinsn_in_expr (tmp_rhs, vi);
+      change_vinsn_in_expr (tmp_rhs, new_vi);
       
       av_set_add (new_set_ptr, tmp_rhs);
       
@@ -1444,6 +1445,28 @@ un_speculate (expr_t expr, insn_t insn, 
 }
 
 
+/* True when INSN is a "regN = regN" copy.  */
+static bool
+identical_copy_p (rtx insn)
+{
+  rtx lhs, rhs, pat;
+
+  pat = PATTERN (insn);
+
+  if (GET_CODE (pat) != SET)
+    return false;
+
+  lhs = SET_DEST (pat);
+  if (!REG_P (lhs))
+    return false;
+
+  rhs = SET_SRC (pat);
+  if (!REG_P (rhs))
+    return false;
+
+  return REGNO (lhs) == REGNO (rhs);
+}
+
 /* Undo all transformations on *AV_PTR that were done when 
    moving through INSN.  */
 static void
@@ -1453,9 +1476,27 @@ undo_transformations (av_set_t *av_ptr, 
   rhs_t rhs;
   av_set_t new_set = NULL;
 
+  /* First, kill any RHS that uses registers set by an insn.  This is 
+     required for correctness.  */
+  FOR_EACH_RHS_1 (rhs, av_iter, av_ptr)
+    if (!sched_insns_conditions_mutex_p (insn, RHS_INSN (rhs))
+        && bitmap_intersect_p (INSN_REG_SETS (insn), 
+                               VINSN_REG_USES (EXPR_VINSN (rhs)))
+        /* When an insn looks like 'r1 = r1', we could substitute through
+           it, but the above condition will still hold.  This happend with
+           gcc.c-torture/execute/961125-1.c.  */ 
+        && !identical_copy_p (insn))
+      {
+        dump_rhs (rhs);
+        print ("- removed due to use/set conflict\n");
+        av_set_iter_remove (&av_iter);
+      }
+
+  /* FIXME: don't use the tracking bitmaps until we'll be able to use 
+     vinsn hashes.  */
   FOR_EACH_RHS (rhs, av_iter, *av_ptr)
     {
-      if (bitmap_bit_p (EXPR_CHANGED_ON_INSNS (rhs), INSN_LUID (insn)))
+      if (1 || bitmap_bit_p (EXPR_CHANGED_ON_INSNS (rhs), INSN_LUID (insn)))
         un_speculate (rhs, insn, &new_set);
     }
   
@@ -1463,7 +1504,7 @@ undo_transformations (av_set_t *av_ptr, 
 
   FOR_EACH_RHS (rhs, av_iter, *av_ptr)
     {
-      if (bitmap_bit_p (EXPR_CHANGED_ON_INSNS (rhs), INSN_LUID (insn)))
+      if (1 || bitmap_bit_p (EXPR_CHANGED_ON_INSNS (rhs), INSN_LUID (insn)))
         un_substitute (rhs, insn, &new_set);
     }
   
@@ -1635,8 +1676,8 @@ moveup_rhs (rhs_t insn_to_move_up, insn_
       if (can_overcome_dep_p (*rhs_dsp))
 	{
 	  if (speculate_expr (insn_to_move_up, *rhs_dsp))
-	    /* Speculation was successful.  */
-	    *rhs_dsp = 0;
+            /* Speculation was successful.  */
+            *rhs_dsp = 0;
 	  else
 	    return MOVEUP_RHS_NULL;
 	}
@@ -1652,10 +1693,11 @@ moveup_rhs (rhs_t insn_to_move_up, insn_
 	  print ("After: ");
 
 	  if (substitute_reg_in_rhs (insn_to_move_up, through_insn))
-	    sel_print_rtl (insn);
+            sel_print_rtl (insn);
 	  else
 	    {
 	      print ("Can't move up due to architecture constraints.\n");
+	      line_finish ();
 	      return MOVEUP_RHS_NULL;
 	    }
 
Index: gcc/sel-sched-ir.c
===================================================================
--- gcc/sel-sched-ir.c	(revision 125707)
+++ gcc/sel-sched-ir.c	(working copy)
@@ -1540,8 +1540,16 @@ deps_init_id_finish_insn (void)
       rtx rhs = IDATA_RHS (deps_init_id_data.id);
 
       if (lhs == NULL || rhs == NULL || !lhs_and_rhs_separable_p (lhs, rhs))
-	/* Downgrade to USE.  */
-	deps_init_id_downgrade_to_use ();
+	{
+          /* This should be a USE, as we don't want to schedule its RHS 
+             separately.  However, we still want to have them recorded
+             for the purposes of substitution.  That's why we don't 
+             simply call downgrade_to_use () here.  */
+	  gcc_assert (IDATA_TYPE (deps_init_id_data.id) == SET);
+	  gcc_assert (!lhs == !rhs);
+
+	  IDATA_TYPE (deps_init_id_data.id) = USE;
+	}
     }
 
   deps_init_id_data.where = DEPS_IN_NOWHERE;
@@ -2229,9 +2237,10 @@ insn_eligible_for_subst_p (insn_t insn)
 	  gcc_assert (GET_MODE (INSN_LHS (insn)) 
 		      == GET_MODE (INSN_RHS (insn)));
 	}
-      if ((REG_P (INSN_RHS (insn)) 
-	   && (REG_P (INSN_LHS (insn)) 
-	       || GET_CODE (INSN_RHS (insn)) == CONST_INT)))
+      if ((REG_P (INSN_LHS (insn)) 
+	   && (REG_P (INSN_RHS (insn)) 
+               /* Not supported atm.  
+	       || GET_CODE (INSN_RHS (insn)) == CONST_INT  */)))
 	  return true;             
     }
   return false;

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]