diff mbox

[SMS,1/4] Fix calculation of row_rest_count

Message ID BANLkTi=nuhqM3JWyA2PE4MjKP_LsGuwRbw@mail.gmail.com
State New
Headers show

Commit Message

Revital Eres May 19, 2011, 4:44 a.m. UTC 
Hello,

The calculation of the number of instructions in a row is currently
done by updating row_rest_count field in struct ps_insn on the fly
while creating a new instruction.  It is used to make sure we do not
exceed
the issue_rate.
This calculation assumes the instruction is inserted in the beginning of a
row thus does not take into account the cases where it must follow other
instructions.  Also, it's not been property updated when an instruction
is removed.
To avoid the overhead of maintaining this row_rest_count count in every
instruction in each row as is currently done; this patch maintains one
count per row which holds the number of instructions in the row.

The patch was tested together with the rest of the patches in this series.
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 regtseted on c,c++. Bootstrap c language with SMS
flags enabling SMS also on loops with stage count 1.

OK for mainline?

Thanks,
Revital

        * modulo-sched.c (struct ps_insn): Remove row_rest_count field.
        (struct partial_schedule): Add rows_length field.
        (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.

Comments

Ayal Zaks May 29, 2011, 6:12 p.m. UTC | #1 
> The calculation of the number of instructions in a row is currently
> done by updating row_rest_count field in struct ps_insn on the fly
> while creating a new instruction.  It is used to make sure we do not
> exceed
> the issue_rate.
> This calculation assumes the instruction is inserted in the beginning of
a
> row thus does not take into account the cases where it must follow other
> instructions.  Also, it's not been property updated when an instruction
> is removed.
> To avoid the overhead of maintaining this row_rest_count count in every
> instruction in each row as is currently done; this patch maintains one
> count per row which holds the number of instructions in the row.
>
> The patch was tested together with the rest of the patches in this
series.
> 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 regtseted on c,c++. Bootstrap c language with SMS
> flags enabling SMS also on loops with stage count 1.
>
> OK for mainline?
>

OK. The current situation is indeed broken, and inefficient, as you noted:
o We are checking only the first node in a row for its row_rest_count
value, to figure out if the row is full; hence it's really a property of
the row, not of a node.
o When scheduling a node, we update only that node's row_rest_count; hence
if we schedule a node in position other than the first, the row_rest_count
value of the first node is not incremented.
o When removing a node, we do not decrement any row_rest_count value.

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...).

Thanks for fixing this,
Ayal.

> Thanks,
> Revital
>
>         * modulo-sched.c (struct ps_insn): Remove row_rest_count field.
>         (struct partial_schedule): Add rows_length field.
>         (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.
> [attachment "patch_row_rest_count_17_5.txt" deleted by Ayal
Zaks/Haifa/IBM]
Revital Eres May 30, 2011, 7:46 a.m. UTC | #2 
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...).

OK, I'm now testing a patch with these additions.

Thanks,
Revital
diff mbox

Patch

Index: modulo-sched.c
===================================================================
--- modulo-sched.c	(revision 173814)
+++ modulo-sched.c	(working copy)
@@ -134,8 +135,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 +148,9 @@  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.  */
+  int *rows_length;
+
   /* The earliest absolute cycle of an insn in the partial schedule.  */
   int min_cycle;
 
@@ -1908,6 +2140,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,6 +2155,7 @@  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];
@@ -1966,6 +2200,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);
 
@@ -2456,6 +2692,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 +2731,7 @@  free_partial_schedule (partial_schedule_
     return;
   free_ps_insns (ps);
   free (ps->rows);
+  free (ps->rows_length);
   free (ps);
 }
 
@@ -2511,6 +2749,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 +2784,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 +2823,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 +2981,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 +2996,7 @@  add_node_to_ps (partial_schedule_ptr ps,
       return NULL;
     }
 
+  ps->rows_length[row] += 1;
   return ps_i;
 }