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

login
register
mail settings
Submitter Revital Eres
Date Dec. 18, 2011, 6:37 a.m.
Message ID <CAHz1=dV5L=Gc+up3mMJnJ=qztE-8_5dodK=OO+XLw-iddLOhFQ@mail.gmail.com>
Download mbox | patch
Permalink /patch/132043/
State New
Headers show

Comments

Revital Eres - Dec. 18, 2011, 6:37 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.
>>
>
> 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, attached is the new version of the patch following your comments.

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

Revital

        * modulo-sched.c (rows_last): New field in struct partial_schedule.
        (create_partial_schedule, free_partial_schedule,
        ps_insert_empty_row, ps_insn_advance_column, remove_node_from_ps,
        reset_partial_schedule, rotate_partial_schedule,
        verify_partial_schedule): Update the new field.
        (ps_insn_find_column): Likewise and remove last_in_row.

Patch

Index: modulo-sched.c

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

+++ 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_last[i] points to the last insn in the linked list pointed

+     by rows[i].  */

+  ps_insn_ptr *rows_last;

+  

   /* 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_last_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_last_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_last_new[row] = ps->rows_last[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_last_new[row + 1] = ps->rows_last[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_last);

+  ps->rows_last = rows_last_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_last[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_last = (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_last);

   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_last = (ps_insn_ptr *) xrealloc (ps->rows_last, new_ii

+					       * sizeof (ps_insn_ptr));

+  memset (ps->rows_last, 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,10 @@  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)

+    ps->rows_last[row] = ps_i->prev_in_row;

+  

   if (! ps_i->prev_in_row)
     {
       gcc_assert (ps_i == ps->rows[row]);
@@ -2992,7 +3014,6 @@  ps_insn_find_column (partial_schedule_pt

   ps_insn_ptr next_ps_i;
   ps_insn_ptr first_must_follow = NULL;
   ps_insn_ptr last_must_precede = NULL;
-  ps_insn_ptr last_in_row = NULL;

   int row;
 
   if (! ps_i)
@@ -3024,9 +3045,7 @@  ps_insn_find_column (partial_schedule_pt

       if (must_precede 
 	  && TEST_BIT (must_precede, next_ps_i->id)
 	  && JUMP_P (ps_rtl_insn (ps, next_ps_i->id)))
-	return false;

-             

-       last_in_row = next_ps_i;

+	return false;    

     }
 
   /* The closing branch is scheduled as well.  Make sure there is no
@@ -3036,18 +3055,20 @@  ps_insn_find_column (partial_schedule_pt

     {
       if (first_must_follow)
 	return false;
-      if (last_in_row)

+

+      if (ps->rows_last[row])

 	{
 	  /* Make the branch the last in the row.  New instructions
 	     will be inserted at the beginning of the row or after the
 	     last must_precede instruction thus the branch is guaranteed
 	     to remain the last instruction in the row.  */
-	  last_in_row->next_in_row = ps_i;

-	  ps_i->prev_in_row = last_in_row;

-	  ps_i->next_in_row = NULL;

+	  ps->rows_last[row]->next_in_row = ps_i;

+	  ps_i->prev_in_row = ps->rows_last[row];

 	}
       else
-	ps->rows[row] = ps_i;

+        ps->rows[row] = ps_i;

+      

+      ps->rows_last[row] = ps_i;

       return true;
     }
   
@@ -3070,6 +3091,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_last[row] = ps_i;

+  

   return true;
 }
 
@@ -3116,6 +3140,9 @@  ps_insn_advance_column (partial_schedule

   if (prev)
     prev->next_in_row = next;
 
+  if (ps_i->next_in_row == NULL)

+    ps->rows_last[row] = ps_i;

+

   return true;
 }
 
@@ -3298,14 +3325,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_last = ps->rows_last[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_last[row] = ps->rows_last[row + 1];

 	  ps->rows_length[row] = ps->rows_length[row + 1]; 
 	}
 
+      ps->rows_last[last_row] = rows_last;

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