Patchwork [SMS,1/4] Fix calculation of row_rest_count

login
register
mail settings
Submitter Revital Eres
Date June 14, 2011, 6:27 a.m.
Message ID <BANLkTi=JPGL=M7GsxOy3HVgOS3Fo__NSig@mail.gmail.com>
Download mbox | patch
Permalink /patch/100284/
State New
Headers show

Comments

Revital Eres - June 14, 2011, 6:27 a.m.
Hello,

> Please add the following:
> o A clarification that rows_length is used only (as an optimization) to
> back off quickly from trying to schedule a node in a full row; that is, to
> avoid running through futile DFA state transitions.
> o An assert that ps->rows_length[i] equals the number of nodes in ps->rows
> [i] (e.g., in verify_partial_schedule(); and then recheck...).

Done. Besides the additions to address your comments I also added two
more bits to update rows_length field into rotate_partial_schedule ()
and ps_insert_empty_row () that were missing in the previous
implementation of the patch.

The patch was re-tested on top of the patch to fix violation of memory
dependence (http://gcc.gnu.org/ml/gcc-patches/2011-06/msg00960.html)
as follows: On ppc64-redhat-linux regtest as well as bootstrap with
SMS flags, enabling SMS also on loops with stage count 1.  Regtested
on SPU.
On arm-linux-gnueabi bootstrap c language with SMS
flags enabling SMS also on loops with stage count 1 and currently
regtseted on c,c++.

OK for mainline with these changes once regtests on arm-linux-gnueabi completes?

Thanks,
Revital


        * modulo-sched.c (struct ps_insn): Remove row_rest_count field.
        (struct partial_schedule): Add rows_length field.
        (verify_partial_schedule): Check rows_length.
        (ps_insert_empty_row): Handle rows_length.
        (create_partial_schedule): Likewise.
        (free_partial_schedule): Likewise.
        (reset_partial_schedule): Likewise.
        (create_ps_insn): Remove rest_count argument.
        (remove_node_from_ps): Update rows_length.
        (add_node_to_ps): Update rows_length and call create_ps_insn
        without passing row_rest_count.
        (rotate_partial_schedule): Update rows_length.
Ayal Zaks - June 16, 2011, 5:06 a.m.
Revital Eres <revital.eres@linaro.org> wrote on 14/06/2011 09:27:32 AM:

> From: Revital Eres <revital.eres@linaro.org>
> To: Ayal Zaks/Haifa/IBM@IBMIL
> Cc: gcc-patches@gcc.gnu.org, Patch Tracking <patches@linaro.org>
> Date: 14/06/2011 09:27 AM
> Subject: Re: [PATCH, SMS 1/4] Fix calculation of row_rest_count
>
> Hello,
>
> > Please add the following:
> > o A clarification that rows_length is used only (as an optimization) to
> > back off quickly from trying to schedule a node in a full row; that is,
to
> > avoid running through futile DFA state transitions.
> > o An assert that ps->rows_length[i] equals the number of nodes in ps->
rows
> > [i] (e.g., in verify_partial_schedule(); and then recheck...).
>
> Done. Besides the additions to address your comments I also added two
> more bits to update rows_length field into rotate_partial_schedule ()
> and ps_insert_empty_row () that were missing in the previous
> implementation of the patch.
>

Glad the additional assertion already proved useful ;-)

> The patch was re-tested on top of the patch to fix violation of memory
> dependence (http://gcc.gnu.org/ml/gcc-patches/2011-06/msg00960.html)
> as follows: On ppc64-redhat-linux regtest as well as bootstrap with
> SMS flags, enabling SMS also on loops with stage count 1.  Regtested
> on SPU.
> On arm-linux-gnueabi bootstrap c language with SMS
> flags enabling SMS also on loops with stage count 1 and currently
> regtseted on c,c++.
>
> OK for mainline with these changes once regtests on arm-linux-gnueabi
completes?
>

OK.
Thanks,
Ayal.

> Thanks,
> Revital
>
>
>         * modulo-sched.c (struct ps_insn): Remove row_rest_count field.
>         (struct partial_schedule): Add rows_length field.
>         (verify_partial_schedule): Check rows_length.
>         (ps_insert_empty_row): Handle rows_length.
>         (create_partial_schedule): Likewise.
>         (free_partial_schedule): Likewise.
>         (reset_partial_schedule): Likewise.
>         (create_ps_insn): Remove rest_count argument.
>         (remove_node_from_ps): Update rows_length.
>         (add_node_to_ps): Update rows_length and call create_ps_insn
>         without passing row_rest_count.
>         (rotate_partial_schedule): Update rows_length.
> [attachment "patch_sms_5_6.txt" deleted by Ayal Zaks/Haifa/IBM]

Patch

Index: modulo-sched.c

===================================================================
--- modulo-sched.c	(revision 173786)

+++ modulo-sched.c	(working copy)

@@ -134,8 +134,6 @@  struct ps_insn

   ps_insn_ptr next_in_row,
 	      prev_in_row;
 
-  /* The number of nodes in the same row that come after this node.  */

-  int row_rest_count;

 };
 
 /* Holds the partial schedule as an array of II rows.  Each entry of the
@@ -149,6 +147,12 @@  struct partial_schedule

   /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii).  */
   ps_insn_ptr *rows;
 
+  /*  rows_length[i] holds the number of instructions in the row.

+      It is used only (as an optimization) to back off quickly from

+      trying to schedule a node in a full row; that is, to avoid running

+      through futile DFA state transitions.  */

+  int *rows_length;

+  

   /* The earliest absolute cycle of an insn in the partial schedule.  */
   int min_cycle;
 
@@ -1908,6 +1912,7 @@  ps_insert_empty_row (partial_schedule_pt

   int ii = ps->ii;
   int new_ii = ii + 1;
   int row;
+  int *rows_length_new;

 
   verify_partial_schedule (ps, sched_nodes);
 
@@ -1922,9 +1927,11 @@  ps_insert_empty_row (partial_schedule_pt

   rotate_partial_schedule (ps, PS_MIN_CYCLE (ps));
 
   rows_new = (ps_insn_ptr *) xcalloc (new_ii, sizeof (ps_insn_ptr));
+  rows_length_new = (int *) xcalloc (new_ii, sizeof (int));

   for (row = 0; row < split_row; row++)
     {
       rows_new[row] = ps->rows[row];
+      rows_length_new[row] = ps->rows_length[row];

       ps->rows[row] = NULL;
       for (crr_insn = rows_new[row];
 	   crr_insn; crr_insn = crr_insn->next_in_row)
@@ -1945,6 +1952,7 @@  ps_insert_empty_row (partial_schedule_pt

   for (row = split_row; row < ii; row++)
     {
       rows_new[row + 1] = ps->rows[row];
+      rows_length_new[row + 1] = ps->rows_length[row];

       ps->rows[row] = NULL;
       for (crr_insn = rows_new[row + 1];
 	   crr_insn; crr_insn = crr_insn->next_in_row)
@@ -1966,6 +1974,8 @@  ps_insert_empty_row (partial_schedule_pt

     + (SMODULO (ps->max_cycle, ii) >= split_row ? 1 : 0);
   free (ps->rows);
   ps->rows = rows_new;
+  free (ps->rows_length);

+  ps->rows_length = rows_length_new;

   ps->ii = new_ii;
   gcc_assert (ps->min_cycle >= 0);
 
@@ -2041,16 +2051,23 @@  verify_partial_schedule (partial_schedul

   ps_insn_ptr crr_insn;
 
   for (row = 0; row < ps->ii; row++)
-    for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row)

-      {

-	ddg_node_ptr u = crr_insn->node;

-

-	gcc_assert (TEST_BIT (sched_nodes, u->cuid));

-	/* ??? Test also that all nodes of sched_nodes are in ps, perhaps by

-	   popcount (sched_nodes) == number of insns in ps.  */

-	gcc_assert (SCHED_TIME (u) >= ps->min_cycle);

-	gcc_assert (SCHED_TIME (u) <= ps->max_cycle);

-      }

+    {

+      int length = 0;

+      

+      for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row)

+	{

+	  ddg_node_ptr u = crr_insn->node;

+	  

+	  length++;

+	  gcc_assert (TEST_BIT (sched_nodes, u->cuid));

+	  /* ??? Test also that all nodes of sched_nodes are in ps, perhaps by

+	     popcount (sched_nodes) == number of insns in ps.  */

+	  gcc_assert (SCHED_TIME (u) >= ps->min_cycle);

+	  gcc_assert (SCHED_TIME (u) <= ps->max_cycle);

+	}

+      

+      gcc_assert (ps->rows_length[row] == length);

+    }

 }
 
 
@@ -2456,6 +2473,7 @@  create_partial_schedule (int ii, ddg_ptr

 {
   partial_schedule_ptr ps = XNEW (struct partial_schedule);
   ps->rows = (ps_insn_ptr *) xcalloc (ii, sizeof (ps_insn_ptr));
+  ps->rows_length = (int *) xcalloc (ii, sizeof (int));

   ps->ii = ii;
   ps->history = history;
   ps->min_cycle = INT_MAX;
@@ -2494,6 +2512,7 @@  free_partial_schedule (partial_schedule_

     return;
   free_ps_insns (ps);
   free (ps->rows);
+  free (ps->rows_length);

   free (ps);
 }
 
@@ -2511,6 +2530,8 @@  reset_partial_schedule (partial_schedule

   ps->rows = (ps_insn_ptr *) xrealloc (ps->rows, new_ii
 						 * sizeof (ps_insn_ptr));
   memset (ps->rows, 0, new_ii * sizeof (ps_insn_ptr));
+  ps->rows_length = (int *) xrealloc (ps->rows_length, new_ii * sizeof (int));

+  memset (ps->rows_length, 0, new_ii * sizeof (int));

   ps->ii = new_ii;
   ps->min_cycle = INT_MAX;
   ps->max_cycle = INT_MIN;
@@ -2539,14 +2560,13 @@  print_partial_schedule (partial_schedule

 
 /* Creates an object of PS_INSN and initializes it to the given parameters.  */
 static ps_insn_ptr
-create_ps_insn (ddg_node_ptr node, int rest_count, int cycle)

+create_ps_insn (ddg_node_ptr node, int cycle)

 {
   ps_insn_ptr ps_i = XNEW (struct ps_insn);
 
   ps_i->node = node;
   ps_i->next_in_row = NULL;
   ps_i->prev_in_row = NULL;
-  ps_i->row_rest_count = rest_count;

   ps_i->cycle = cycle;
 
   return ps_i;
@@ -2579,6 +2599,8 @@  remove_node_from_ps (partial_schedule_pt

       if (ps_i->next_in_row)
 	ps_i->next_in_row->prev_in_row = ps_i->prev_in_row;
     }
+   

+  ps->rows_length[row] -= 1; 

   free (ps_i);
   return true;
 }
@@ -2735,17 +2757,12 @@  add_node_to_ps (partial_schedule_ptr ps,

 		sbitmap must_precede, sbitmap must_follow)
 {
   ps_insn_ptr ps_i;
-  int rest_count = 1;

   int row = SMODULO (cycle, ps->ii);
 
-  if (ps->rows[row]

-      && ps->rows[row]->row_rest_count >= issue_rate)

+  if (ps->rows_length[row] >= issue_rate)

     return NULL;
 
-  if (ps->rows[row])

-    rest_count += ps->rows[row]->row_rest_count;

-

-  ps_i = create_ps_insn (node, rest_count, cycle);

+  ps_i = create_ps_insn (node, cycle);

 
   /* Finds and inserts PS_I according to MUST_FOLLOW and
      MUST_PRECEDE.  */
@@ -2755,6 +2772,7 @@  add_node_to_ps (partial_schedule_ptr ps,

       return NULL;
     }
 
+  ps->rows_length[row] += 1;

   return ps_i;
 }
 
@@ -2910,11 +2928,16 @@  rotate_partial_schedule (partial_schedul

   for (i = 0; i < backward_rotates; i++)
     {
       ps_insn_ptr first_row = ps->rows[0];
+      int first_row_length = ps->rows_length[0];

 
       for (row = 0; row < last_row; row++)
-	ps->rows[row] = ps->rows[row+1];

+	{

+	  ps->rows[row] = ps->rows[row + 1];

+	  ps->rows_length[row] = ps->rows_length[row + 1]; 

+	}

 
       ps->rows[last_row] = first_row;
+      ps->rows_length[last_row] = first_row_length;

     }
 
   ps->max_cycle -= start_cycle;