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

login
register
mail settings
Submitter Revital Eres
Date Nov. 21, 2011, 5:07 a.m.
Message ID <CAHz1=dVPV6xEyjWsG-ic7JSHE1k8tkQBRi-pZwD+Zhj87WZa2A@mail.gmail.com>
Download mbox | patch
Permalink /patch/126683/
State New
Headers show

Comments

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

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;
     }