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

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