Patch: Support IA-64 speculation [1/5]

[Andrey Belevantsev <abel at ispras dot ru>]

Hi,

This patch is the first one of the five patches implementing support of 
IA-64 speculation. The parts are two independent scheduler fixes, the 
fix in sched-deps.c of calculating dependencies, the main part of the 
patch, and ia64-specific part.

All five patches were bootstrapped and regtested separately and together 
on the 20051125 weekly snapshot on ia64-linux and i686-linux. The single 
"big" patch was bootstrapped and tested on today's revision 109012 on 
i686-linux. We couldn't bootstrap the mainline on ia64, so we'll send 
the last two patches (which influence ia64) in a few days, when this 
will be possible. We'll send the speedup numbers of the patch with the 
main part.

This patch fixes the instruction addition to the ready list. When the 
target denies scheduling of an insn on the current cycle, the following 
happens on ia64 during sched-ebb:

  1. The backend remembers to issue a stop bit before insn X
  2. The scheduler queues X for 1 cycle and advances to the next cycle
  3. If there are more than one insn in the ready list, then another
     insn Y is chosen
  4. And the backend issues unnecessary stop bit before Y.

This is fixed with adding a new function, which adds an insn to the 
ready list so that the insn ends up with a highest priority and will be 
chosen on the next scheduling step.

Ok for mainline?

Thanks, Andrey


diff -urp -x .svn trunk/gcc/haifa-sched.c trunk-spec/gcc/haifa-sched.c
--- trunk/gcc/haifa-sched.c	2005-12-23 11:50:50.000000000 +0300
+++ trunk-spec/gcc/haifa-sched.c	2005-12-23 12:36:12.000000000 +0300
@@ -475,6 +475,7 @@ static rtx unlink_line_notes (rtx, rtx);
 static rtx reemit_notes (rtx, rtx);
 
 static rtx *ready_lastpos (struct ready_list *);
+static void ready_add_first (struct ready_list *, rtx);
 static void ready_sort (struct ready_list *);
 static rtx ready_remove_first (struct ready_list *);
 
@@ -662,7 +663,7 @@ rank_for_schedule (const void *x, const 
     return info_val;
 
   /* Compare insns based on their relation to the last-scheduled-insn.  */
-  if (last_scheduled_insn)
+  if (INSN_P (last_scheduled_insn))
     {
       /* Classify the instructions into three classes:
          1) Data dependent on last schedule insn.
@@ -774,6 +775,26 @@ ready_add (struct ready_list *ready, rtx
   ready->n_ready++;
 }
 
+/* Add an element INSN to the ready list so that it ends up with the highest
+   priority.  */
+
+static void
+ready_add_first (struct ready_list *ready, rtx insn)
+{
+  if (ready->first == ready->veclen - 1)
+    {
+      if (ready->n_ready)
+	/* ready_lastpos() fails when called with (ready->n_ready == 0).  */
+	memmove (ready->vec + ready->veclen - ready->n_ready - 1,
+		 ready_lastpos (ready),
+		 ready->n_ready * sizeof (rtx));
+      ready->first = ready->veclen - 2;
+    }
+
+  ready->vec[++(ready->first)] = insn;
+  ready->n_ready++;
+}
+
 /* Remove the element with the highest priority from the ready list and
    return it.  */
 
@@ -2004,9 +2025,20 @@ schedule_block (int b, int rgn_n_insns)
 	      && targetm.sched.dfa_new_cycle (sched_dump, sched_verbose,
 					      insn, last_clock_var,
 					      clock_var, &sort_p))
+	    /* SORT_P is used by the target to override sorting
+	       of the ready list.  This is needed when the target
+	       has modified its internal structures expecting that
+	       the insn will be issued next.  But ready_add would add
+	       the insn with the lowest priority.  As we need the insn
+	       to have the highest priority (so it will be returned by
+	       the ready_remove_first call above), we are calling
+	       ready_add_first instead.
+	       But, still, there is one issue: INSN can be later 
+	       discarded by scheduler's frontend through 
+	       current_sched_info->can_schedule_ready_p.  */ 
 	    {
-	      ready_add (&ready, insn);
-	      break;
+	      ready_add_first (&ready, insn);
+              break;
 	    }
 
 	  sort_p = TRUE;
@@ -2053,8 +2085,10 @@ schedule_block (int b, int rgn_n_insns)
 	  last_scheduled_insn = move_insn (insn, last_scheduled_insn);
 
 	  if (memcmp (curr_state, temp_state, dfa_state_size) != 0)
-	    cycle_issued_insns++;
-	  memcpy (curr_state, temp_state, dfa_state_size);
+            {
+              cycle_issued_insns++;
+              memcpy (curr_state, temp_state, dfa_state_size);
+            }
 
 	  if (targetm.sched.variable_issue)
 	    can_issue_more =
@@ -2323,8 +2357,7 @@ sched_init (FILE *dump_file)
 	}
     }
 
-  /* ??? Add a NOTE after the last insn of the last basic block.  It is not
-     known why this is done.  */
+  /* The following is done to keep current_sched_info->next_tail non null.  */
 
   insn = BB_END (EXIT_BLOCK_PTR->prev_bb);
   if (NEXT_INSN (insn) == 0
@@ -2333,9 +2366,9 @@ sched_init (FILE *dump_file)
 	  /* Don't emit a NOTE if it would end up before a BARRIER.  */
 	  && !BARRIER_P (NEXT_INSN (insn))))
     {
-      emit_note_after (NOTE_INSN_DELETED, BB_END (EXIT_BLOCK_PTR->prev_bb));
+      emit_note_after (NOTE_INSN_DELETED, insn);
       /* Make insn to appear outside BB.  */
-      BB_END (EXIT_BLOCK_PTR->prev_bb) = PREV_INSN (BB_END (EXIT_BLOCK_PTR->prev_bb));
+      BB_END (EXIT_BLOCK_PTR->prev_bb) = insn;
     }
 
   /* Compute INSN_REG_WEIGHT for all blocks.  We must do this before

2005-12-23  Maxim Kuvyrkov <mkuvyrkov@ispras.ru>

        * haifa-sched.c (ready_add_first): New function.
        (schedule_block): Use it.
        (rank_for_schedule): Use INSN_P when checking last_schedule_insn.
        (sched_init): Added comment.