[PATCH 12/18] haifa-sched.c: make insn_queue[] a vec<rtx_insn *>

[tbsaunde+gcc at tbsaunde dot org]

From: Trevor Saunders <tbsaunde+gcc@tbsaunde.org>

gcc/ChangeLog:

2016-04-19  Trevor Saunders  <tbsaunde+gcc@tbsaunde.org>

	* haifa-sched.c (queue_insn): Adjust.
	(queue_remove): Likewise.
	(check_clobbered_conditions): Likewise.
	(struct haifa_saved_data): Make insn_queue a vector.
	(save_backtrack_point): Adjust.
	(toggle_cancelled_flags): Likewise.
	(restore_last_backtrack_point): Likewise.
	(free_topmost_backtrack_point): Likewise.
	(queue_to_ready): Likewise.
	(early_queue_to_ready): Likewise.
	(autopref_multipass_dfa_lookahead_guard): Likewise.
	(schedule_block): Likewise.
---
 gcc/haifa-sched.c | 205 +++++++++++++++++++++++++++---------------------------
 1 file changed, 101 insertions(+), 104 deletions(-)

diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
index e972531..0721ec5 100644
--- a/gcc/haifa-sched.c
+++ b/gcc/haifa-sched.c
@@ -122,6 +122,7 @@ along with GCC; see the file COPYING3.  If not see
    other NOTE insns are grouped in their same relative order at the
    beginning of basic blocks and regions that have been scheduled.  */
 
+#define INCLUDE_ALGORITHM
 #include "config.h"
 #include "system.h"
 #include "coretypes.h"
@@ -320,7 +321,7 @@ bool adding_bb_to_current_region_p = true;
    the base maximal time of functional unit reservations and getting a
    result.  This is the longest time an insn may be queued.  */
 
-static rtx_insn_list **insn_queue;
+static vec<rtx_insn *> *insn_queue;
 static int q_ptr = 0;
 static int q_size = 0;
 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
@@ -2826,13 +2827,12 @@ HAIFA_INLINE static void
 queue_insn (rtx_insn *insn, int n_cycles, const char *reason)
 {
   int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
-  rtx_insn_list *link = alloc_INSN_LIST (insn, insn_queue[next_q]);
   int new_tick;
 
   gcc_assert (n_cycles <= max_insn_queue_index);
   gcc_assert (!DEBUG_INSN_P (insn));
 
-  insn_queue[next_q] = link;
+  insn_queue[next_q].safe_push (insn);
   q_size += 1;
 
   if (sched_verbose >= 2)
@@ -2861,14 +2861,26 @@ queue_insn (rtx_insn *insn, int n_cycles, const char *reason)
     }
 }
 
-/* Remove INSN from queue.  */
+/* Remove INSN at idx from queue.  */
+static void
+queue_remove (unsigned int q, unsigned int idx)
+{
+  QUEUE_INDEX (insn_queue[q][idx]) = QUEUE_NOWHERE;
+  insn_queue[q].ordered_remove (idx);
+  q_size--;
+}
+
+/* Remove insn from the queue.  */
+
 static void
 queue_remove (rtx_insn *insn)
 {
   gcc_assert (QUEUE_INDEX (insn) >= 0);
-  remove_free_INSN_LIST_elem (insn, &insn_queue[QUEUE_INDEX (insn)]);
-  q_size--;
-  QUEUE_INDEX (insn) = QUEUE_NOWHERE;
+
+  unsigned int q = QUEUE_INDEX (insn);
+  unsigned int idx = std::find (insn_queue[q].begin (), insn_queue[q].end (),
+				insn) - insn_queue[q].begin ();
+  queue_remove (q, idx);
 }
 
 /* Return a pointer to the bottom of the ready list, i.e. the insn
@@ -3267,17 +3279,16 @@ check_clobbered_conditions (rtx_insn *insn)
     }
   for (i = 0; i <= max_insn_queue_index; i++)
     {
-      rtx_insn_list *link;
       int q = NEXT_Q_AFTER (q_ptr, i);
 
-    restart_queue:
-      for (link = insn_queue[q]; link; link = link->next ())
+      unsigned int len = insn_queue[q].length ();
+      for (unsigned int i = len - 1; i < len; i--)
 	{
-	  rtx_insn *x = link->insn ();
+	  rtx_insn *x = insn_queue[q][i];
 	  if (TODO_SPEC (x) == DEP_CONTROL && cond_clobbered_p (x, t))
 	    {
 	      queue_remove (x);
-	      goto restart_queue;
+	      i = insn_queue[q].length ();
 	    }
 	}
     }
@@ -4277,7 +4288,7 @@ struct haifa_saved_data
   /* We don't need to save q_ptr, as its value is arbitrary and we can set it
      to 0 when restoring.  */
   int q_size;
-  rtx_insn_list **insn_queue;
+  vec<rtx_insn *> *insn_queue;
 
   /* Describe pattern replacements that occurred since this backtrack point
      was queued.  */
@@ -4328,12 +4339,12 @@ save_backtrack_point (struct delay_pair *pair,
   save->ready.vec = XNEWVEC (rtx_insn *, ready.veclen);
   memcpy (save->ready.vec, ready.vec, ready.veclen * sizeof (rtx));
 
-  save->insn_queue = XNEWVEC (rtx_insn_list *, max_insn_queue_index + 1);
+  save->insn_queue = XNEWVEC (vec<rtx_insn *>, max_insn_queue_index + 1);
   save->q_size = q_size;
   for (i = 0; i <= max_insn_queue_index; i++)
     {
       int q = NEXT_Q_AFTER (q_ptr, i);
-      save->insn_queue[i] = copy_INSN_LIST (insn_queue[q]);
+      save->insn_queue[i] = insn_queue[q].copy ();
     }
 
   save->clock_var = clock_var;
@@ -4403,10 +4414,10 @@ toggle_cancelled_flags (bool set)
   for (i = 0; i <= max_insn_queue_index; i++)
     {
       int q = NEXT_Q_AFTER (q_ptr, i);
-      rtx_insn_list *link;
-      for (link = insn_queue[q]; link; link = link->next ())
+      unsigned int len = insn_queue[q].length ();
+      for (unsigned int i = len - 1; i < len; i--)
 	{
-	  rtx_insn *insn = link->insn ();
+	  rtx_insn *insn = insn_queue[q][i];
 	  FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
 	    if (!DEBUG_INSN_P (DEP_PRO (dep)))
 	      {
@@ -4546,14 +4557,14 @@ restore_last_backtrack_point (struct sched_block_state *psched_block)
   for (i = 0; i <= max_insn_queue_index; i++)
     {
       int q = NEXT_Q_AFTER (q_ptr, i);
-
-      for (rtx_insn_list *link = insn_queue[q]; link; link = link->next ())
+      unsigned int len = insn_queue[q].length ();
+      for (unsigned int i = len - 1; i < len; i--)
 	{
-	  rtx_insn *x = link->insn ();
+	  rtx_insn *x = insn_queue[q][i];
 	  QUEUE_INDEX (x) = QUEUE_NOWHERE;
 	  INSN_TICK (x) = INVALID_TICK;
 	}
-      free_INSN_LIST_list (&insn_queue[q]);
+      insn_queue[q].release ();
     }
 
   free (ready.vec);
@@ -4577,11 +4588,13 @@ restore_last_backtrack_point (struct sched_block_state *psched_block)
     {
       int q = NEXT_Q_AFTER (q_ptr, i);
 
+      insn_queue[q].release ();
       insn_queue[q] = save->insn_queue[q];
 
-      for (rtx_insn_list *link = insn_queue[q]; link; link = link->next ())
+      unsigned int len = insn_queue[q].length ();
+      for (unsigned int j = len - 1; j < len; j--)
 	{
-	  rtx_insn *x = link->insn ();
+	  rtx_insn *x = insn_queue[q][j];
 	  QUEUE_INDEX (x) = i;
 	  TODO_SPEC (x) = recompute_todo_spec (x, true);
 	  INSN_TICK (x) = save->clock_var + i;
@@ -4651,7 +4664,7 @@ free_topmost_backtrack_point (bool reset_tick)
   if (current_sched_info->restore_state)
     free (save->fe_saved_data);
   for (i = 0; i <= max_insn_queue_index; i++)
-    free_INSN_LIST_list (&save->insn_queue[i]);
+    save->insn_queue[i].release ();
   free (save->insn_queue);
   free (save->curr_state);
   free (save->ready.vec);
@@ -5090,7 +5103,6 @@ static void
 queue_to_ready (struct ready_list *ready)
 {
   rtx_insn *insn;
-  rtx_insn_list *link;
   rtx_insn *skip_insn;
 
   q_ptr = NEXT_Q (q_ptr);
@@ -5104,9 +5116,10 @@ queue_to_ready (struct ready_list *ready)
 
   /* Add all pending insns that can be scheduled without stalls to the
      ready list.  */
-  for (link = insn_queue[q_ptr]; link; link = link->next ())
+  unsigned int len = insn_queue[q_ptr].length ();
+  for (unsigned int i = len - 1; i < len; i--)
     {
-      insn = link->insn ();
+      insn = insn_queue[q_ptr][i];
       q_size -= 1;
 
       if (sched_verbose >= 2)
@@ -5140,7 +5153,7 @@ queue_to_ready (struct ready_list *ready)
 	    fprintf (sched_dump, "moving to ready without stalls\n");
         }
     }
-  free_INSN_LIST_list (&insn_queue[q_ptr]);
+  insn_queue[q_ptr].release ();
 
   /* If there are no ready insns, stall until one is ready and add all
      of the pending insns at that point to the ready list.  */
@@ -5150,11 +5163,13 @@ queue_to_ready (struct ready_list *ready)
 
       for (stalls = 1; stalls <= max_insn_queue_index; stalls++)
 	{
-	  if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
+	  int q = NEXT_Q_AFTER (q_ptr, stalls);
+	  if (!insn_queue[q].is_empty ())
 	    {
-	      for (; link; link = link->next ())
+	      unsigned int len = insn_queue[q].length ();
+	      for (unsigned int i = len - 1; i < len; i--)
 		{
-		  insn = link->insn ();
+		  insn = insn_queue[q][i];
 		  q_size -= 1;
 
 		  if (sched_verbose >= 2)
@@ -5165,7 +5180,7 @@ queue_to_ready (struct ready_list *ready)
 		  if (sched_verbose >= 2)
 		    fprintf (sched_dump, "moving to ready with %d stalls\n", stalls);
 		}
-	      free_INSN_LIST_list (&insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]);
+	      insn_queue[q].release ();
 
 	      advance_one_cycle ();
 
@@ -5245,9 +5260,6 @@ static int
 early_queue_to_ready (state_t state, struct ready_list *ready)
 {
   rtx_insn *insn;
-  rtx_insn_list *link;
-  rtx_insn_list *next_link;
-  rtx_insn_list *prev_link;
   bool move_to_ready;
   int cost;
   state_t temp_state = alloca (dfa_state_size);
@@ -5273,66 +5285,54 @@ early_queue_to_ready (state_t state, struct ready_list *ready)
 
   for (stalls = 0; stalls <= max_insn_queue_index; stalls++)
     {
-      if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
-	{
-	  if (sched_verbose > 6)
-	    fprintf (sched_dump, ";; look at index %d + %d\n", q_ptr, stalls);
+      if (insn_queue[NEXT_Q_AFTER (q_ptr, stalls)].is_empty ())
+	continue;
 
-	  prev_link = 0;
-	  while (link)
-	    {
-	      next_link = link->next ();
-	      insn = link->insn ();
-	      if (insn && sched_verbose > 6)
-		print_rtl_single (sched_dump, insn);
-
-	      memcpy (temp_state, state, dfa_state_size);
-	      if (recog_memoized (insn) < 0)
-		/* non-negative to indicate that it's not ready
-		   to avoid infinite Q->R->Q->R... */
-		cost = 0;
-	      else
-		cost = state_transition (temp_state, insn);
+      if (sched_verbose > 6)
+	fprintf (sched_dump, ";; look at index %d + %d\n", q_ptr, stalls);
 
-	      if (sched_verbose >= 6)
-		fprintf (sched_dump, "transition cost = %d\n", cost);
+      unsigned int len = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)].length ();
+      for (unsigned int i = len - 1; i < len; i--)
+	{
+	  insn = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)][i];
+	  if (insn && sched_verbose > 6)
+	    print_rtl_single (sched_dump, insn);
+
+	  memcpy (temp_state, state, dfa_state_size);
+	  if (recog_memoized (insn) < 0)
+	    /* non-negative to indicate that it's not ready
+	       to avoid infinite Q->R->Q->R... */
+	    cost = 0;
+	  else
+	    cost = state_transition (temp_state, insn);
 
-	      move_to_ready = false;
-	      if (cost < 0)
-		{
-		  move_to_ready = ok_for_early_queue_removal (insn);
-		  if (move_to_ready == true)
-		    {
-		      /* move from Q to R */
-		      q_size -= 1;
-		      ready_add (ready, insn, false);
+	  if (sched_verbose >= 6)
+	    fprintf (sched_dump, "transition cost = %d\n", cost);
 
-		      if (prev_link)
-			XEXP (prev_link, 1) = next_link;
-		      else
-			insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = next_link;
+	  move_to_ready = false;
+	  if (cost < 0)
+	    {
+	      move_to_ready = ok_for_early_queue_removal (insn);
+	      if (move_to_ready == true)
+		{
+		  /* move from Q to R */
+		  q_size -= 1;
+		  ready_add (ready, insn, false);
 
-		      free_INSN_LIST_node (link);
+		  insn_queue[NEXT_Q_AFTER (q_ptr, stalls)].ordered_remove (i);
 
-		      if (sched_verbose >= 2)
-			fprintf (sched_dump, ";;\t\tEarly Q-->Ready: insn %s\n",
-				 (*current_sched_info->print_insn) (insn, 0));
+		  if (sched_verbose >= 2)
+		    fprintf (sched_dump, ";;\t\tEarly Q-->Ready: insn %s\n",
+			     (*current_sched_info->print_insn) (insn, 0));
 
-		      insns_removed++;
-		      if (insns_removed == flag_sched_stalled_insns)
-			/* Remove no more than flag_sched_stalled_insns insns
-			   from Q at a time.  */
-			return insns_removed;
-		    }
+		  insns_removed++;
+		  if (insns_removed == flag_sched_stalled_insns)
+		    /* Remove no more than flag_sched_stalled_insns insns
+		       from Q at a time.  */
+		    return insns_removed;
 		}
-
-	      if (move_to_ready == false)
-		prev_link = link;
-
-	      link = next_link;
-	    } /* while link */
-	} /* if link */
-
+	    }
+	} /* while link */
     } /* for stalls.. */
 
   return insns_removed;
@@ -5845,7 +5845,7 @@ autopref_multipass_dfa_lookahead_guard (rtx_insn *insn1, int ready_index)
 
       /* Everything from the current queue slot should have been moved to
 	 the ready list.  */
-      gcc_assert (insn_queue[NEXT_Q_AFTER (q_ptr, 0)] == NULL_RTX);
+      gcc_assert (insn_queue[NEXT_Q_AFTER (q_ptr, 0)].is_empty ());
 
       int n_stalls = PARAM_VALUE (PARAM_SCHED_AUTOPREF_QUEUE_DEPTH) - 1;
       if (n_stalls > max_insn_queue_index)
@@ -5853,11 +5853,12 @@ autopref_multipass_dfa_lookahead_guard (rtx_insn *insn1, int ready_index)
 
       for (int stalls = 1; stalls <= n_stalls; ++stalls)
 	{
-	  for (rtx_insn_list *link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)];
-	       link != NULL_RTX;
-	       link = link->next ())
+	  const vec<rtx_insn *> &insns =
+	    insn_queue[NEXT_Q_AFTER (q_ptr, stalls)];
+	  unsigned int len = insns.length ();
+	  for (unsigned int j = len - 1; j < len; j--)
 	    {
-	      rtx_insn *insn2 = link->insn ();
+	      rtx_insn *insn2 = insns[j];
 	      r = autopref_multipass_dfa_lookahead_guard_1 (insn1, insn2,
 							    write);
 	      if (r)
@@ -6578,7 +6579,7 @@ schedule_block (basic_block *target_bb, state_t init_state)
   q_ptr = 0;
   q_size = 0;
 
-  insn_queue = XALLOCAVEC (rtx_insn_list *, max_insn_queue_index + 1);
+  insn_queue = XALLOCAVEC (vec<rtx_insn *>, max_insn_queue_index + 1);
   memset (insn_queue, 0, (max_insn_queue_index + 1) * sizeof (rtx));
 
   /* Start just before the beginning of time.  */
@@ -7045,13 +7046,10 @@ schedule_block (basic_block *target_bb, state_t init_state)
 	}
       for (i = 0; i <= max_insn_queue_index; i++)
 	{
-	  rtx_insn_list *link;
-	  while ((link = insn_queue[i]) != NULL)
+	  rtx_insn *x;
+	  while ((x = insn_queue[i].pop ()))
 	    {
-	      rtx_insn *x = link->insn ();
-	      insn_queue[i] = link->next ();
 	      QUEUE_INDEX (x) = QUEUE_NOWHERE;
-	      free_INSN_LIST_node (link);
 	      resolve_dependencies (x);
 	    }
 	}
@@ -7086,16 +7084,15 @@ schedule_block (basic_block *target_bb, state_t init_state)
       if (q_size)
 	for (i = 0; i <= max_insn_queue_index; i++)
 	  {
-	    rtx_insn_list *link;
-	    for (link = insn_queue[i]; link; link = link->next ())
+	    unsigned int len = insn_queue[i].length ();
+	    for (unsigned int j = len - 1; j < len; j--)
 	      {
-		rtx_insn *x;
+		rtx_insn *x = insn_queue[i][j];
 
-		x = link->insn ();
 		QUEUE_INDEX (x) = QUEUE_NOWHERE;
 		TODO_SPEC (x) = HARD_DEP;
 	      }
-	    free_INSN_LIST_list (&insn_queue[i]);
+	    insn_queue[i].release ();
 	  }
     }
 
-- 
2.7.4