More scheduler infrastructure.

From-SVN: r38381

10 files changed, 156 insertions, 55 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index a5d3171..76da5ee 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,36 @@
 2000-12-19  Bernd Schmidt  <bernds@redhat.co.uk>
 
+	* haifa-sched.c (rm_line_notes): Arguments are now head and tail,
+	not block number.  All callers and prototype changed.
+	(set_priorities): Likewise.
+	(save_line_notes): Add head and tail arguments; all callers and
+	prototype changed.
+	(restore_line_notes): Likewise.  Don't crash on insns generated
+	during scheduling.
+	(schedule_block): Don't use BLOCK_HEAD/BLOCK_END macros.
+	Call MD_SCHED_INIT with additional argument.
+	When starting a new cycle, emit cycle_display insns if available.
+	Don't stop scheduling when encountering a JUMP_INSN, but add another
+	call to schedule_more_p in the inner loop.
+	Call MD_SCHED_REORDER2 after scheduling an insn.
+	Call MD_SCHED_FINISH once all insns are scheduled.
+	(sched_init): Compensate for the fact that get_block_head_tail
+	doesn't include leading notes.
+	* sched-deps.c (free_deps): Free vectors here.
+	* sched-rgn.c (compute_block_backward_dependencies): Not here.
+	(last_was_jump): New static variable.
+	(schedule_more_p): Test it.
+	(init_ready_list): Initialize it.
+	(can_schedule_ready_p): Set it if we have a JUMP_INSN.
+
+	* config/i386/i386.h (MD_SCHED_INIT): Add new arg.
+	* config/m32r/m32r.h (MD_SCHED_INIT): Add new arg.
+	* config/sparc/sparc.h (MD_SCHED_INIT): Add new arg.
+
+	* md.texi (cycle_display): Document.
+	* tm.texi (MD_SCHED_INIT): Document new arg.
+	(MD_SCHED_FINISH, MD_SCHED_REORDER2): Document.
+
 	* flow.c (ior_reg_cond, nand_reg_cond, not_reg_cond): Rewrite
 	to use different representation.  All callers changed.
 	(and_reg_cond): Renamed from nand_reg_cond; caller changed.
diff --git a/gcc/config/i386/i386.h b/gcc/config/i386/i386.h
index d5ad42d..111ea18 100644
--- a/gcc/config/i386/i386.h
+++ b/gcc/config/i386/i386.h
@@ -2462,7 +2462,7 @@ while (0)
 #define ISSUE_RATE \
   ix86_issue_rate ()
 
-#define MD_SCHED_INIT(DUMP, SCHED_VERBOSE) \
+#define MD_SCHED_INIT(DUMP, SCHED_VERBOSE, MAX_READY) \
   ix86_sched_init (DUMP, SCHED_VERBOSE)
 
 #define MD_SCHED_REORDER(DUMP, SCHED_VERBOSE, READY, N_READY, CLOCK, CIM) \
diff --git a/gcc/config/m32r/m32r.h b/gcc/config/m32r/m32r.h
index 7ab89ae..d83e2fe 100644
--- a/gcc/config/m32r/m32r.h
+++ b/gcc/config/m32r/m32r.h
@@ -1554,7 +1554,8 @@ do {									\
 extern int m32r_sched_odd_word_p;
 
 /* Hook to run before scheduling a block of insns.  */
-#define MD_SCHED_INIT(STREAM, VERBOSE) m32r_sched_init (STREAM, VERBOSE)
+#define MD_SCHED_INIT(STREAM, VERBOSE, MAX_READY) \
+  m32r_sched_init (STREAM, VERBOSE)
 
 /* Hook to reorder the list of ready instructions.  */
 #define MD_SCHED_REORDER(STREAM, VERBOSE, READY, N_READY, CLOCK, CIM) 	\
diff --git a/gcc/config/sparc/sparc.h b/gcc/config/sparc/sparc.h
index 78a870e..50ab2ab 100644
--- a/gcc/config/sparc/sparc.h
+++ b/gcc/config/sparc/sparc.h
@@ -2897,7 +2897,7 @@ do {                                                                    \
 #define ADJUST_COST(INSN,LINK,DEP,COST) \
   (COST) = sparc_adjust_cost(INSN, LINK, DEP, COST)
 
-#define MD_SCHED_INIT(DUMP, SCHED_VERBOSE)				\
+#define MD_SCHED_INIT(DUMP, SCHED_VERBOSE, MAX_READY)			\
   if (sparc_cpu == PROCESSOR_ULTRASPARC)				\
     ultrasparc_sched_init (DUMP, SCHED_VERBOSE)
 
diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
index b1d3eff..32ccf82 100644
--- a/gcc/haifa-sched.c
+++ b/gcc/haifa-sched.c
@@ -1163,23 +1163,17 @@ no_real_insns_p (head, tail)
   return 1;
 }
 
-/* Delete line notes from bb. Save them so they can be later restored
-   (in restore_line_notes ()).  */
+/* Delete line notes from one block. Save them so they can be later restored
+   (in restore_line_notes).  HEAD and TAIL are the boundaries of the
+   block in which notes should be processed.  */
 
 void
-rm_line_notes (b)
-     int b;
+rm_line_notes (head, tail)
+     rtx head, tail;
 {
   rtx next_tail;
-  rtx tail;
-  rtx head;
   rtx insn;
 
-  get_block_head_tail (b, &head, &tail);
-
-  if (head == tail && (! INSN_P (head)))
-    return;
-
   next_tail = NEXT_INSN (tail);
   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
     {
@@ -1203,13 +1197,14 @@ rm_line_notes (b)
     }
 }
 
-/* Save line number notes for each insn in block B.  */
+/* Save line number notes for each insn in block B.  HEAD and TAIL are
+   the boundaries of the block in which notes should be processed.*/
 
 void
-save_line_notes (b)
+save_line_notes (b, head, tail)
      int b;
+     rtx head, tail;
 {
-  rtx head, tail;
   rtx next_tail;
 
   /* We must use the true line number for the first insn in the block
@@ -1220,28 +1215,30 @@ save_line_notes (b)
   rtx line = line_note_head[b];
   rtx insn;
 
-  get_block_head_tail (b, &head, &tail);
   next_tail = NEXT_INSN (tail);
 
-  for (insn = BLOCK_HEAD (b); insn != next_tail; insn = NEXT_INSN (insn))
+  for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
     if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
       line = insn;
     else
       LINE_NOTE (insn) = line;
 }
 
-/* After block B was scheduled, insert line notes into the insns list.  */
+/* After block B was scheduled, insert line notes into the insns list.
+   HEAD and TAIL are the boundaries of the block in which notes should
+   be processed.*/
 
 void
-restore_line_notes (b)
+restore_line_notes (b, head, tail)
      int b;
+     rtx head, tail;
 {
   rtx line, note, prev, new;
   int added_notes = 0;
-  rtx head, next_tail, insn;
+  rtx next_tail, insn;
 
-  head = BLOCK_HEAD (b);
-  next_tail = NEXT_INSN (BLOCK_END (b));
+  head = head;
+  next_tail = NEXT_INSN (tail);
 
   /* Determine the current line-number.  We want to know the current
      line number of the first insn of the block here, in case it is
@@ -1263,6 +1260,7 @@ restore_line_notes (b)
      by real instructions all end up at the same address.  I can find no
      use for line number notes before other notes, so none are emitted.  */
     else if (GET_CODE (insn) != NOTE
+	     && INSN_UID (insn) < old_max_uid
 	     && (note = LINE_NOTE (insn)) != 0
 	     && note != line
 	     && (line == 0
@@ -1341,7 +1339,7 @@ rm_redundant_line_notes ()
     fprintf (sched_dump, ";; deleted %d line-number notes\n", notes);
 }
 
-/* Delete notes between head and tail and put them in the chain
+/* Delete notes between HEAD and TAIL and put them in the chain
    of notes ended by NOTE_LIST.  */
 
 void
@@ -1662,7 +1660,7 @@ schedule_block (b, rgn_n_insns)
       fprintf (sched_dump, ";;   ======================================================\n");
       fprintf (sched_dump,
 	       ";;   -- basic block %d from %d to %d -- %s reload\n",
-	       b, INSN_UID (BLOCK_HEAD (b)), INSN_UID (BLOCK_END (b)),
+	       b, INSN_UID (head), INSN_UID (tail),
 	       (reload_completed ? "after" : "before"));
       fprintf (sched_dump, ";;   ======================================================\n");
       fprintf (sched_dump, "\n");
@@ -1682,7 +1680,7 @@ schedule_block (b, rgn_n_insns)
   (*current_sched_info->init_ready_list) (&ready);
 
 #ifdef MD_SCHED_INIT
-  MD_SCHED_INIT (sched_dump, sched_verbose);
+  MD_SCHED_INIT (sched_dump, sched_verbose, ready.veclen);
 #endif
 
   /* No insns scheduled in this block yet.  */
@@ -1712,6 +1710,11 @@ schedule_block (b, rgn_n_insns)
          list.  */
       queue_to_ready (&ready);
 
+#ifdef HAVE_cycle_display
+      if (HAVE_cycle_display)
+	last = emit_insn_after (gen_cycle_display (GEN_INT (clock_var)), last);
+#endif
+
       if (ready.n_ready == 0)
 	abort ();
 
@@ -1740,7 +1743,9 @@ schedule_block (b, rgn_n_insns)
 	}
 
       /* Issue insns from ready list.  */
-      while (ready.n_ready != 0 && can_issue_more)
+      while (ready.n_ready != 0
+	     && can_issue_more
+	     && (*current_sched_info->schedule_more_p) ())
 	{
 	  /* Select and remove the insn from the ready list.  */
 	  rtx insn = ready_remove_first (&ready);
@@ -1768,9 +1773,14 @@ schedule_block (b, rgn_n_insns)
 	  schedule_insn (insn, &ready, clock_var);
 
 	next:
-	  /* Close this block after scheduling its jump.  */
-	  if (GET_CODE (last_scheduled_insn) == JUMP_INSN)
-	    break;
+#ifdef MD_SCHED_REORDER2
+	  /* Sort the ready list based on priority.  */
+	  if (ready.n_ready > 0)
+	    ready_sort (&ready);
+	  MD_SCHED_REORDER2 (sched_dump, sched_verbose,
+			     ready.n_ready ? ready_lastpos (&ready) : NULL,
+			     ready.n_ready, clock_var, can_issue_more);
+#endif
 	}
 
       /* Debug info.  */
@@ -1778,6 +1788,10 @@ schedule_block (b, rgn_n_insns)
 	visualize_scheduled_insns (clock_var);
     }
 
+#ifdef MD_SCHED_FINISH
+  MD_SCHED_FINISH (sched_dump, sched_verbose);
+#endif
+
   /* Debug info.  */
   if (sched_verbose)
     {
@@ -1833,17 +1847,14 @@ schedule_block (b, rgn_n_insns)
 /* Set_priorities: compute priority of each insn in the block.  */
 
 int
-set_priorities (b)
-     int b;
+set_priorities (head, tail)
+     rtx head, tail;
 {
   rtx insn;
   int n_insn;
 
-  rtx tail;
   rtx prev_head;
-  rtx head;
 
-  get_block_head_tail (b, &head, &tail);
   prev_head = PREV_INSN (head);
 
   if (head == tail && (! INSN_P (head)))
@@ -1936,12 +1947,23 @@ sched_init (dump_file)
          determine the correct line number for the first insn of the block.  */
 
       for (b = 0; b < n_basic_blocks; b++)
-	for (line = BLOCK_HEAD (b); line; line = PREV_INSN (line))
-	  if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
+	{
+	  for (line = BLOCK_HEAD (b); line; line = PREV_INSN (line))
+	    if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
+	      {
+		line_note_head[b] = line;
+		break;
+	      }
+	  /* Do a forward search as well, since we won't get to see the first
+	     notes in a basic block.  */
+	  for (line = BLOCK_HEAD (b); line; line = NEXT_INSN (line))
 	    {
-	      line_note_head[b] = line;
-	      break;
+	      if (INSN_P (line))
+		break;
+	      if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
+		line_note_head[b] = line;
 	    }
+	}
     }
 
   /* Find units used in this fuction, for visualization.  */
diff --git a/gcc/md.texi b/gcc/md.texi
index 2c464b5..5ab116a 100644
--- a/gcc/md.texi
+++ b/gcc/md.texi
@@ -2858,6 +2858,14 @@ A typical @code{conditional_trap} pattern looks like
   "@dots{}")
 @end smallexample
 
+@cindex @code{cycle_display} instruction pattern
+@item @samp{cycle_display}
+
+This pattern, if present, will be emitted by the instruction scheduler at
+the beginning of each new clock cycle.  This can be used for annotating the
+assembler output with cycle counts.  Operand 0 is a @code{const_int} that
+holds the clock cycle.
+
 @end table
 
 @node Pattern Ordering
diff --git a/gcc/sched-deps.c b/gcc/sched-deps.c
index 7f9914c..b5f7328 100644
--- a/gcc/sched-deps.c
+++ b/gcc/sched-deps.c
@@ -1327,6 +1327,9 @@ free_deps (deps)
       if (deps->reg_last_uses[i])
 	free_INSN_LIST_list (&deps->reg_last_uses[i]);
     }
+  free (deps->reg_last_clobbers);
+  free (deps->reg_last_sets);
+  free (deps->reg_last_uses);
 }
 
 /* If it is profitable to use them, initialize caches for tracking
diff --git a/gcc/sched-int.h b/gcc/sched-int.h
index 4a15f12..ffa23a1 100644
--- a/gcc/sched-int.h
+++ b/gcc/sched-int.h
@@ -252,14 +252,14 @@ extern void free_dependency_caches PARAMS ((void));
 extern void get_block_head_tail PARAMS ((int, rtx *, rtx *));
 extern int no_real_insns_p PARAMS ((rtx, rtx));
 
-extern void rm_line_notes PARAMS ((int));
-extern void save_line_notes PARAMS ((int));
-extern void restore_line_notes PARAMS ((int));
+extern void rm_line_notes PARAMS ((rtx, rtx));
+extern void save_line_notes PARAMS ((int, rtx, rtx));
+extern void restore_line_notes PARAMS ((int, rtx, rtx));
 extern void rm_redundant_line_notes PARAMS ((void));
 extern void rm_other_notes PARAMS ((rtx, rtx));
 
 extern int insn_issue_delay PARAMS ((rtx));
-extern int set_priorities PARAMS ((int));
+extern int set_priorities PARAMS ((rtx, rtx));
 
 extern void schedule_block PARAMS ((int, int));
 extern void sched_init PARAMS ((FILE *));
diff --git a/gcc/sched-rgn.c b/gcc/sched-rgn.c
index 46a7905..9e1bfd9 100644
--- a/gcc/sched-rgn.c
+++ b/gcc/sched-rgn.c
@@ -2032,6 +2032,8 @@ static int sched_target_n_insns;
 static int target_n_insns;
 /* The number of insns from the entire region scheduled so far.  */
 static int sched_n_insns;
+/* Nonzero if the last scheduled insn was a jump.  */
+static int last_was_jump;
 
 /* Implementations of the sched_info functions for region scheduling.  */
 static void init_ready_list PARAMS ((struct ready_list *));
@@ -2046,7 +2048,7 @@ static int rgn_rank PARAMS ((rtx, rtx));
 static int
 schedule_more_p ()
 {
-  return sched_target_n_insns < target_n_insns;
+  return ! last_was_jump && sched_target_n_insns < target_n_insns;
 }
 
 /* Add all insns that are initially ready to the ready list READY.  Called
@@ -2064,6 +2066,7 @@ init_ready_list (ready)
   target_n_insns = 0;
   sched_target_n_insns = 0;
   sched_n_insns = 0;
+  last_was_jump = 0;
 
   /* Print debugging information.  */
   if (sched_verbose >= 5)
@@ -2155,6 +2158,9 @@ static int
 can_schedule_ready_p (insn)
      rtx insn;
 {
+  if (GET_CODE (insn) == JUMP_INSN)
+    last_was_jump = 1;
+
   /* An interblock motion?  */
   if (INSN_BB (insn) != target_bb)
     {
@@ -2589,10 +2595,9 @@ compute_block_backward_dependences (bb)
   /* Free up the INSN_LISTs.  */
   free_deps (&tmp_deps);
 
-  /* Assert that we won't need bb_reg_last_* for this block anymore.  */
-  free (bb_deps[bb].reg_last_uses);
-  free (bb_deps[bb].reg_last_sets);
-  free (bb_deps[bb].reg_last_clobbers);
+  /* Assert that we won't need bb_reg_last_* for this block anymore.  
+     The vectors we're zeroing out have just been freed by the call to
+     free_deps.  */
   bb_deps[bb].reg_last_uses = 0;
   bb_deps[bb].reg_last_sets = 0;
   bb_deps[bb].reg_last_clobbers = 0;
@@ -2726,7 +2731,12 @@ schedule_region (rgn)
 
   /* Set priorities.  */
   for (bb = 0; bb < current_nr_blocks; bb++)
-    rgn_n_insns += set_priorities (BB_TO_BLOCK (bb));
+    {
+      rtx head, tail;
+      get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
+
+      rgn_n_insns += set_priorities (head, tail);
+    }
 
   /* Compute interblock info: probabilities, split-edges, dominators, etc.  */
   if (current_nr_blocks > 1)
@@ -2788,8 +2798,8 @@ schedule_region (rgn)
 
       if (write_symbols != NO_DEBUG)
 	{
-	  save_line_notes (b);
-	  rm_line_notes (b);
+	  save_line_notes (b, head, tail);
+	  rm_line_notes (head, tail);
 	}
 
       /* rm_other_notes only removes notes which are _inside_ the
@@ -2855,7 +2865,11 @@ schedule_region (rgn)
   if (write_symbols != NO_DEBUG)
     {
       for (bb = 0; bb < current_nr_blocks; bb++)
-	restore_line_notes (BB_TO_BLOCK (bb));
+	{
+	  rtx head, tail;
+	  get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
+	  restore_line_notes (BB_TO_BLOCK (bb), head, tail);
+	}
     }
 
   /* Done with this region.  */
diff --git a/gcc/tm.texi b/gcc/tm.texi
index a7fb124..85923e6 100644
--- a/gcc/tm.texi
+++ b/gcc/tm.texi
@@ -8134,11 +8134,22 @@ A C expression that returns how many instructions can be issued at the
 same time if the machine is a superscalar machine.
 
 @findex MD_SCHED_INIT
-@item MD_SCHED_INIT (@var{file}, @var{verbose})
+@item MD_SCHED_INIT (@var{file}, @var{verbose}, @var{max_ready})
 A C statement which is executed by the scheduler at the
 beginning of each block of instructions that are to be scheduled.
 @var{file} is either a null pointer, or a stdio stream to write any
 debug output to.  @var{verbose} is the verbose level provided by
+@samp{-fsched-verbose-}@var{n}.  @var{max_ready} is the maximum number
+of insns in the current scheduling region that can be live at the same
+time.  This can be used to allocate scratch space if it is needed.
+
+@findex MD_SCHED_FINISH
+@item MD_SCHED_FINISH (@var{file}, @var{verbose})
+A C statement which is executed by the scheduler at the end of each block
+of instructions that are to be scheduled.  It can be used to perform
+cleanup of any actions done by the other scheduling macros.
+@var{file} is either a null pointer, or a stdio stream to write any
+debug output to.  @var{verbose} is the verbose level provided by
 @samp{-fsched-verbose-}@var{n}.
 
 @findex MD_SCHED_REORDER
@@ -8155,7 +8166,18 @@ scheduler reads the ready list in reverse order, starting with
 @var{ready}[@var{n_ready}-1] and going to @var{ready}[0].  @var{clock}
 is the timer tick of the scheduler.  @var{can_issue_more} is an output
 parameter that is set to the number of insns that can issue this clock;
-normally this is just @code{issue_rate}.
+normally this is just @code{issue_rate}.  See also @samp{MD_SCHED_REORDER2}.
+
+@findex MD_SCHED_REORDER2
+@item MD_SCHED_REORDER2 (@var{file}, @var{verbose}, @var{ready}, @var{n_ready}, @var{clock}, @var{can_issue_more})
+Like @samp{MD_SCHED_REORDER}, but called at a different time.  While the
+@samp{MD_SCHED_REORDER} macro is called whenever the scheduler starts a
+new cycle, this macro is used immediately after @samp{MD_SCHED_VARIABLE_ISSUE}
+is called; it can reorder the ready list and set @var{can_issue_more} to
+determine whether there are more insns to be scheduled in the same cycle.
+Defining this macro can be useful if there are frequent situations where
+scheduling one insn causes other insns to become ready in the same cycle,
+these other insns can then be taken into account properly.
 
 @findex MD_SCHED_VARIABLE_ISSUE
 @item MD_SCHED_VARIABLE_ISSUE (@var{file}, @var{verbose}, @var{insn}, @var{more})