[SMS,1/2,RFC] Support traversing PS in reverse order

Submitted by Revital Eres on Nov. 21, 2011, 5:07 a.m.

Details

Message ID CAHz1=dVPV6xEyjWsG-ic7JSHE1k8tkQBRi-pZwD+Zhj87WZa2A@mail.gmail.com
State New
Headers show

Commit Message

Revital Eres Nov. 21, 2011, 5:07 a.m.
Hello,

This patch support the estimation of register pressure in SMS.
Although GCC is in stage 3 I would appreciate comments on it.
Thanks to Richard and Ayal for discussing the implementation and their insights.

This part of the patch enables iterating on the partial schedule in the
reverse order (from the last instruction the the first).

Tested and bootstrap with the other patches in the series on
ppc64-redhat-linux,
enabling SMS on loops with SC 1.

Comments are welcome.

Thanks,
Revital

Changelog:
        * modulo-sched.c (rows_reverse): New field in struct partial_schedule.
        (create_partial_schedule, free_partial_schedule,
        ps_insert_empty_row, ps_insn_advance_column,
        ps_insn_find_column, remove_node_from_ps, reset_partial_schedule,
        rotate_partial_schedule, verify_partial_schedule): Update the
        new field.

Comments

Ayal Zaks Nov. 23, 2011, 9:46 a.m.
On Mon, Nov 21, 2011 at 7:07 AM, Revital Eres <revital.eres@linaro.org> wrote:
> Hello,
>
> This patch support the estimation of register pressure in SMS.
> Although GCC is in stage 3 I would appreciate comments on it.
> Thanks to Richard and Ayal for discussing the implementation and their insights.
>
> This part of the patch enables iterating on the partial schedule in the
> reverse order (from the last instruction the the first).
>
> Tested and bootstrap with the other patches in the series on
> ppc64-redhat-linux,
> enabling SMS on loops with SC 1.
>
> Comments are welcome.
>

This looks fine. Please rename rows_reverse to rows_last as discussed,
and simplify the bit that tracks last_in_row in ps_insn_find_column().
Thanks,
Ayal.

> Thanks,
> Revital
>
> Changelog:
>        * modulo-sched.c (rows_reverse): New field in struct partial_schedule.
>        (create_partial_schedule, free_partial_schedule,
>        ps_insert_empty_row, ps_insn_advance_column,
>        ps_insn_find_column, remove_node_from_ps, reset_partial_schedule,
>        rotate_partial_schedule, verify_partial_schedule): Update the
>        new field.
>

Patch hide | download patch | download mbox

Index: modulo-sched.c
===================================================================
--- modulo-sched.c	(revision 181149)
+++ modulo-sched.c	(working copy)
@@ -177,6 +177,10 @@  struct partial_schedule
   /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii).  */
   ps_insn_ptr *rows;
 
+  /* rows_reverse[i] points to the last insn in the linked list pointed
+     by rows[i].  */
+  ps_insn_ptr *rows_reverse;
+  
   /* All the moves added for this partial schedule.  Index X has
      a ps_insn id of X + g->num_nodes.  */
   VEC (ps_reg_move_info, heap) *reg_moves;
@@ -2272,6 +2276,7 @@  ps_insert_empty_row (partial_schedule_pt
 {
   ps_insn_ptr crr_insn;
   ps_insn_ptr *rows_new;
+  ps_insn_ptr *rows_reverse_new;
   int ii = ps->ii;
   int new_ii = ii + 1;
   int row;
@@ -2290,10 +2295,12 @@  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_reverse_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_reverse_new[row] = ps->rows_reverse[row];
       rows_length_new[row] = ps->rows_length[row];
       ps->rows[row] = NULL;
       for (crr_insn = rows_new[row];
@@ -2315,6 +2322,7 @@  ps_insert_empty_row (partial_schedule_pt
   for (row = split_row; row < ii; row++)
     {
       rows_new[row + 1] = ps->rows[row];
+      rows_reverse_new[row + 1] = ps->rows_reverse[row];
       rows_length_new[row + 1] = ps->rows_length[row];
       ps->rows[row] = NULL;
       for (crr_insn = rows_new[row + 1];
@@ -2337,6 +2345,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_reverse);
+  ps->rows_reverse = rows_reverse_new;
   free (ps->rows_length);
   ps->rows_length = rows_length_new;
   ps->ii = new_ii;
@@ -2428,6 +2438,9 @@  verify_partial_schedule (partial_schedul
 	     popcount (sched_nodes) == number of insns in ps.  */
 	  gcc_assert (SCHED_TIME (u) >= ps->min_cycle);
 	  gcc_assert (SCHED_TIME (u) <= ps->max_cycle);
+	  if (ps->rows_length[row] == length)
+	    gcc_assert (ps->rows_reverse[row] == crr_insn);
+
 	}
       
       gcc_assert (ps->rows_length[row] == length);
@@ -2837,6 +2850,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_reverse = (ps_insn_ptr *) xcalloc (ii, sizeof (ps_insn_ptr));
   ps->rows_length = (int *) xcalloc (ii, sizeof (int));
   ps->reg_moves = NULL;
   ps->ii = ii;
@@ -2885,6 +2899,7 @@  free_partial_schedule (partial_schedule_
 
   free_ps_insns (ps);
   free (ps->rows);
+  free (ps->rows_reverse);
   free (ps->rows_length);
   free (ps);
 }
@@ -2903,6 +2918,9 @@  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_reverse = (ps_insn_ptr *) xrealloc (ps->rows_reverse, new_ii
+					       * sizeof (ps_insn_ptr));
+  memset (ps->rows_reverse, 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;
@@ -2960,6 +2978,15 @@  remove_node_from_ps (partial_schedule_pt
   gcc_assert (ps && ps_i);
   
   row = SMODULO (ps_i->cycle, ps->ii);
+
+  if (! ps_i->next_in_row)
+    {
+      if (ps_i->prev_in_row)
+	ps->rows_reverse[row] = ps_i->prev_in_row;
+      else
+	ps->rows_reverse[row] = NULL;
+    }
+  
   if (! ps_i->prev_in_row)
     {
       gcc_assert (ps_i == ps->rows[row]);
@@ -3048,6 +3075,8 @@  ps_insn_find_column (partial_schedule_pt
 	}
       else
 	ps->rows[row] = ps_i;
+
+      ps->rows_reverse[row] = ps_i;
       return true;
     }
   
@@ -3070,6 +3099,9 @@  ps_insn_find_column (partial_schedule_pt
         ps_i->next_in_row->prev_in_row = ps_i;
     }
 
+  if (! ps_i->next_in_row)
+    ps->rows_reverse[row] = ps_i;
+  
   return true;
 }
 
@@ -3116,6 +3148,9 @@  ps_insn_advance_column (partial_schedule
   if (prev)
     prev->next_in_row = next;
 
+  if (ps_i->next_in_row == NULL)
+    ps->rows_reverse[row] = ps_i;
+
   return true;
 }
 
@@ -3298,14 +3333,17 @@  rotate_partial_schedule (partial_schedul
   for (i = 0; i < backward_rotates; i++)
     {
       ps_insn_ptr first_row = ps->rows[0];
+      ps_insn_ptr rows_reverse = ps->rows_reverse[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_reverse[row] = ps->rows_reverse[row + 1];
 	  ps->rows_length[row] = ps->rows_length[row + 1]; 
 	}
 
+      ps->rows_reverse[last_row] = rows_reverse;
       ps->rows[last_row] = first_row;
       ps->rows_length[last_row] = first_row_length;
     }