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] Improve calculation of target register availability


Hello,

These two small patches resulted from fixes of the previous patch. First, when caching dependence queries, we must account for the case when an expression does not change during propagation, but its target register becomes unavailable. This is true for separable expressions which have dependencies in LHS. In this case, we must set appropriate bit in the expression data.

Second, the changes resulted in some degradation of performance, which was fixed by sorting the resulting ready list once again. Also, now we always form extended basic block regions in the situation when regular region forming gives up and decides to schedule single basic blocks. This partly fixes the perlbmk performance regression.

Tested on ia64, committed to sel-sched branch.
Andrey
2007-12-27  Andrey Belevantsev  <abel@ispras.ru>

	Cache that an expression can be moved up only as RHS.

	* sel-sched.c (enum MOVEUP_RHS_CODE): New value MOVEUP_RHS_AS_RHS.
	(moveup_rhs): Return it when an expression can be moved up as 
	a RHS only.  Return MOVEUP_RHS_CHANGED only when expression
	was really changed.
	(moveup_set_rhs): Use fourth bit in INSN_ANALYZED_DEPS / 
	INSN_FOUND_DEPS bitmaps for caching MOVEUP_RHS_AS_RHS results.
	Set EXPR_TARGET_AVAILABLE to false when moveup_rhs returns
	MOVEUP_RHS_AS_RHS.  Assert that when MOVEUP_RHS_CHANGED,
	expression's UID has been really changed.
	(fill_vec_av_set): Properly handle max_insns_to_rename.
	(sel_global_init): Use setup_sched_dumps.

	* sel-sched-dump.c (setup_sched_dump_to_stderr): Rename to 
	setup_sched_dumps.  When sched_verbose_param >= 10, print to
	stderr.  
	* sel-sched-dump.h (setup_sched_dumps): Export.
2007-12-27  Andrey Belevantsev  <abel@ispras.ru>

	* sel-sched.c (sel_rank_for_schedule): Tidy.
	(fill_vec_av_set): Use VEC_unordered_remove instead of ordered.
	Properly calculate is_orig_reg_p.  Add the final qsort call
	after filtering out the av set.
	* sched-rgn.c (sched_rgn_init): With selective scheduling,
	always try to compute ebb regions instead of single block reagions.
Index: gcc/sel-sched.c
===================================================================
--- gcc/sel-sched.c	(revision 131184)
+++ gcc/sel-sched.c	(working copy)
@@ -94,7 +94,8 @@ int max_insns_to_rename;
 /* Definitions of local types and macros.  */
 
 /* Represents possible outcomes of moving an expression through an insn.  */
-enum MOVEUP_RHS_CODE { MOVEUP_RHS_SAME, MOVEUP_RHS_NULL, MOVEUP_RHS_CHANGED };
+enum MOVEUP_RHS_CODE { MOVEUP_RHS_SAME, MOVEUP_RHS_AS_RHS, 
+                       MOVEUP_RHS_NULL, MOVEUP_RHS_CHANGED };
 
 /* The container to be passed into rtx search & replace functions.  */
 struct rtx_search_arg
@@ -1826,6 +1827,8 @@ moveup_rhs (rhs_t insn_to_move_up, insn_
 {
   vinsn_t vi = RHS_VINSN (insn_to_move_up);
   insn_t insn = VINSN_INSN (vi);
+  bool was_changed = false;
+  bool as_rhs = false;
   ds_t *has_dep_p;
   ds_t full_ds;
 
@@ -1899,6 +1902,7 @@ moveup_rhs (rhs_t insn_to_move_up, insn_
 	/* Speculation was successful.  */
 	{
 	  full_ds = 0;
+          was_changed = true;
 	  sel_clear_has_dependence ();
 	}
     }
@@ -1916,11 +1920,12 @@ moveup_rhs (rhs_t insn_to_move_up, insn_
         return MOVEUP_RHS_NULL;
 
       EXPR_TARGET_AVAILABLE (insn_to_move_up) = false;
+      as_rhs = true;
     }
 
   /* At this point we have either separable insns, that will be lifted
      up only as RHSes, or non-separable insns with no dependency in lhs.
-     If dependency is in RHS, then try perform substitution and move up
+     If dependency is in RHS, then try to perform substitution and move up
      substituted RHS:
 
       Ex. 1:				  Ex.2
@@ -1943,8 +1948,11 @@ 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;
+              was_changed = true;
+            }
 	  else
 	    return MOVEUP_RHS_NULL;
 	}
@@ -1970,7 +1978,8 @@ moveup_rhs (rhs_t insn_to_move_up, insn_
 	      line_finish ();
 	      return MOVEUP_RHS_NULL;
 	    }
-
+          
+          was_changed = true;
 	  line_finish ();
 	}
       else
@@ -1983,7 +1992,11 @@ moveup_rhs (rhs_t insn_to_move_up, insn_
   if (CANT_MOVE_TRAPPING (insn_to_move_up, through_insn))
     return MOVEUP_RHS_NULL;
 
-  return MOVEUP_RHS_CHANGED;
+  return (was_changed 
+          ? MOVEUP_RHS_CHANGED 
+          : (as_rhs 
+             ? MOVEUP_RHS_AS_RHS
+             : MOVEUP_RHS_SAME));
 }
 
 /* Moves an av set AVP up through INSN, performing necessary 
@@ -2015,6 +2028,14 @@ moveup_set_rhs (av_set_t *avp, insn_t in
             }
           else
             print (" - unchanged (cached)");
+          
+          line_finish ();
+          continue;
+        }
+      else if (bitmap_bit_p (INSN_FOUND_DEPS (insn), rhs_uid))
+        {
+          EXPR_TARGET_AVAILABLE (rhs) = false;
+          print (" - unchanged (as RHS, cached)");
 
           line_finish ();
           continue;
@@ -2024,18 +2045,17 @@ moveup_set_rhs (av_set_t *avp, insn_t in
 	{
 	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);
-            }
+          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;
 	case MOVEUP_RHS_CHANGED:
 	  print (" - changed");
-          
+          gcc_assert (INSN_UID (EXPR_INSN_RTX (rhs)) != rhs_uid);
+
           /* Mark that this insn changed this expr.  */
           insert_in_hash_vect (&EXPR_CHANGED_ON_INSNS (rhs), 
                                VINSN_HASH (INSN_VINSN (insn)));
@@ -2046,14 +2066,20 @@ 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);
-            }
+          bitmap_set_bit (INSN_ANALYZED_DEPS (insn), rhs_uid);
+          bitmap_clear_bit (INSN_FOUND_DEPS (insn), rhs_uid);
 
 	  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.  */
+          gcc_assert (!unique_p);
+          bitmap_clear_bit (INSN_ANALYZED_DEPS (insn), rhs_uid);
+          bitmap_set_bit (INSN_FOUND_DEPS (insn), rhs_uid);
+
+	  print (" - unchanged (as RHS)");
+	  break;
 	default:
 	  gcc_unreachable ();
 	}
@@ -3309,8 +3335,7 @@ fill_vec_av_set (av_set_t av, blist_t bn
                (target_available == false
                 && !EXPR_SEPARABLE_P (rhs))
                /* Don't try to find a register for low-priority expression.  */
-               || (max_insns_to_rename >= 0
-                   && n > max_insns_to_rename))
+               || n >= max_insns_to_rename)
         {
           succ++;
           VEC_ordered_remove (rhs_t, vec_av_set, n);
@@ -6159,7 +6184,7 @@ sel_global_init (void)
 
   init_sched_pools ();
 
-  setup_sched_dump_to_stderr ();
+  setup_sched_dumps ();
 
   /* Setup the infos for sched_init.  */
   sel_setup_sched_infos ();
Index: gcc/sel-sched-dump.c
===================================================================
--- gcc/sel-sched-dump.c	(revision 131184)
+++ gcc/sel-sched-dump.c	(working copy)
@@ -32,6 +32,7 @@
 #include "insn-config.h"
 #include "insn-attr.h"
 #include "params.h"
+#include "output.h"
 #include "basic-block.h"
 #include "cselib.h"
 #include "sel-sched-ir.h"
@@ -185,8 +186,13 @@ print_marker_to_log (void)
 }
 
 void
-setup_sched_dump_to_stderr (void)
+setup_sched_dumps (void)
 {
+  sched_verbose = sched_verbose_param;
+  if (sched_verbose_param == 0 && dump_file)
+    sched_verbose = 1;
+  sched_dump = ((sched_verbose_param >= 10 || !dump_file)
+		? stderr : dump_file);
   sched_dump1 = stderr;
 }
  
Index: gcc/sel-sched-dump.h
===================================================================
--- gcc/sel-sched-dump.h	(revision 131182)
+++ gcc/sel-sched-dump.h	(working copy)
@@ -183,7 +183,7 @@ extern bool new_line;
 /* Functions from sel-sched-dump.c.  */
 extern const char * sel_print_insn (rtx, int);
 extern void free_sel_dump_data (void);
-extern void setup_sched_dump_to_stderr (void);
+extern void setup_sched_dumps (void);
 
 extern void block_start (void);
 extern void block_finish (void);
Index: gcc/sel-sched.c
===================================================================
--- gcc/sel-sched.c	(revision 131202)
+++ gcc/sel-sched.c	(working copy)
@@ -2960,6 +2960,7 @@ sel_rank_for_schedule (const void *x, co
     {
       if (VINSN_UNIQUE_P (tmp_vinsn) && VINSN_UNIQUE_P (tmp2_vinsn)) 
         return SCHED_GROUP_P (tmp2_insn) ? 1 : -1;
+
       /* Now uniqueness means SCHED_GROUP_P is set, because schedule groups
          cannot be cloned.  */
       if (VINSN_UNIQUE_P (tmp2_vinsn))
@@ -3312,7 +3313,7 @@ fill_vec_av_set (av_set_t av, blist_t bn
       /* Don't allow any insns other than from SCHED_GROUP if we have one.  */
       if (FENCE_SCHED_NEXT (fence) && insn != FENCE_SCHED_NEXT (fence))
         {
-          VEC_ordered_remove (rhs_t, vec_av_set, n);
+          VEC_unordered_remove (rhs_t, vec_av_set, n);
           continue;
         }
 
@@ -3328,8 +3329,11 @@ fill_vec_av_set (av_set_t av, blist_t bn
       target_available = EXPR_TARGET_AVAILABLE (rhs);
 
       if (target_available == true)
-        /* Do nothing -- we can use an existing register.  */
-        succ++;
+	{
+          /* Do nothing -- we can use an existing register.  */
+          succ++;
+	  is_orig_reg_p = EXPR_SEPARABLE_P (rhs);
+        }
       else if (/* Non-separable instruction will never 
                   get another register. */
                (target_available == false
@@ -3338,7 +3342,7 @@ fill_vec_av_set (av_set_t av, blist_t bn
                || n >= max_insns_to_rename)
         {
           succ++;
-          VEC_ordered_remove (rhs_t, vec_av_set, n);
+          VEC_unordered_remove (rhs_t, vec_av_set, n);
           print ("- no register; ");
           continue;
         }
@@ -3349,7 +3353,7 @@ fill_vec_av_set (av_set_t av, blist_t bn
                  not available in separable RHS.  Do it the hard way.  */
               ! find_best_reg_for_rhs (rhs, bnds, &is_orig_reg_p))
             {
-              VEC_ordered_remove (rhs_t, vec_av_set, n);
+              VEC_unordered_remove (rhs_t, vec_av_set, n);
               print ("- no register; ");
               continue;
             }
@@ -3369,11 +3373,11 @@ fill_vec_av_set (av_set_t av, blist_t bn
           /* We need to know whether we do need to stall for any insns.  */
           stalled++;
           print ("- not ready yet; ");
-          VEC_ordered_remove (rhs_t, vec_av_set, n);
+          VEC_unordered_remove (rhs_t, vec_av_set, n);
 	  continue;
 	}
 
-      print ("; ");
+      print (" - ok; ");
       n++;
     }
 
@@ -3396,6 +3400,10 @@ fill_vec_av_set (av_set_t av, blist_t bn
       return false;
     }
 
+  /* Sort the vector.  */
+  qsort (VEC_address (rhs_t, vec_av_set), VEC_length (rhs_t, vec_av_set),
+         sizeof (rhs_t), sel_rank_for_schedule);
+
   line_start ();
   print ("Sorted av set (%d): ", VEC_length (rhs_t, vec_av_set));
 
Index: gcc/sched-rgn.c
===================================================================
--- gcc/sched-rgn.c	(revision 131184)
+++ gcc/sched-rgn.c	(working copy)
@@ -2913,7 +2913,7 @@ sched_rgn_init (bool single_blocks_p, bo
       || !flag_schedule_interblock
       || is_cfg_nonregular ())
     {
-      find_single_block_region (ebbs_p);
+      find_single_block_region (SEL_SCHED_P ? true : ebbs_p);
     }
   else
     {

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