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

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