Re: [PATCH] Fix scheduling at the end of blocks.

[Maxim Kuvyrkov <maxim@codesourcery.com>]

[-- Attachment #1: Type: text/plain, Size: 276 bytes --]

Maxim Kuvyrkov wrote:
> Hi,
> 
> This patch makes haifa scheduler better process instructions at the end 
> of blocks (basic blocks or extended basic blocks).

Sorry, I posted an early version of the patch without comments.  Here's 
a proper patch.

> OK for trunk?

--
Maxim

[-- Attachment #2: max-issue.ChangeLog --]
[-- Type: text/plain, Size: 499 bytes --]

2007-11-20  Maxim Kuvyrkov  <maxim@codesourcery.com>

	Make scheduler better process end of the blocks.

	gcc/

	* haifa-sched.c (insn_finishes_cycle_p): New static function.
	(max_issue): Use it.  Fix handling of number of instruction to try.
	* sched-int.h (struct sched_info: insn_finished_block_p): New
	scheduler hook.
	* sched-rgn.c (rgn_insn_finishes_block_p): Implement it.
	(region_sched_info): Update.
	* sched-ebb.c (ebb_sched_info): Update.
	* modulo-sched.c (sms_sched_info): Update.
	

[-- Attachment #3: max-issue.patch --]
[-- Type: text/plain, Size: 4903 bytes --]

Index: sched-ebb.c
===================================================================
--- sched-ebb.c	(revision 188738)
+++ sched-ebb.c	(working copy)
@@ -263,6 +263,7 @@ static struct sched_info ebb_sched_info 
   ebb_print_insn,
   contributes_to_priority,
   compute_jump_reg_dependencies,
+  NULL, /* insn_finishes_block_p */
 
   NULL, NULL,
   NULL, NULL,
Index: haifa-sched.c
===================================================================
--- haifa-sched.c	(revision 188738)
+++ haifa-sched.c	(working copy)
@@ -2027,6 +2027,23 @@ move_insn (rtx insn)
   SCHED_GROUP_P (insn) = 0;  
 }
 
+/* Return true if scheduling INSN will finish current clock cycle.  */
+static bool
+insn_finishes_cycle_p (rtx insn)
+{
+  if (SCHED_GROUP_P (insn))
+    /* After issuing INSN, rest of the sched_group will be forced to issue
+       in order.  Don't make any plans for the rest of cycle.  */
+    return true;
+
+  /* Finishing the block will, apparently, finish the cycle.  */
+  if (current_sched_info->insn_finishes_block_p
+      && current_sched_info->insn_finishes_block_p (insn))
+    return true;
+
+  return false;
+}
+
 /* The following structure describe an entry of the stack of choices.  */
 struct choice_entry
 {
@@ -2083,13 +2100,15 @@ static int
 max_issue (struct ready_list *ready, int *index, int max_points)
 {
   int n, i, all, n_ready, best, delay, tries_num, points = -1;
+  int rest;
   struct choice_entry *top;
   rtx insn;
 
   best = 0;
   memcpy (choice_stack->state, curr_state, dfa_state_size);
   top = choice_stack;
-  top->rest = cached_first_cycle_multipass_dfa_lookahead;
+  /* Add +1 to account the empty initial state.  */
+  top->rest = cached_first_cycle_multipass_dfa_lookahead + 1;
   top->n = 0;
   n_ready = ready->n_ready;
   for (all = i = 0; i < n_ready; i++)
@@ -2099,7 +2118,10 @@ max_issue (struct ready_list *ready, int
   tries_num = 0;
   for (;;)
     {
-      if (top->rest == 0 || i >= n_ready)
+      if (/* Enough instructions are issued (or we won't issue more).  */
+	  top->rest == 0
+	  /* Or there's nothing left to try.  */
+	  || i >= n_ready)
 	{
 	  if (top == choice_stack)
 	    break;
@@ -2123,17 +2145,27 @@ max_issue (struct ready_list *ready, int
 	    break;
 	  insn = ready_element (ready, i);
 	  delay = state_transition (curr_state, insn);
+
 	  if (delay < 0)
 	    {
-	      if (state_dead_lock_p (curr_state))
-		top->rest = 0;
+	      rest = top->rest;
+	      if (state_dead_lock_p (curr_state)
+		  || insn_finishes_cycle_p (insn))
+		/* We won't issue any more instructions in the next
+		   choice_state.  */
+		rest = 0;
 	      else
-		top->rest--;
+		rest--;
+
 	      n = top->n;
 	      if (memcmp (top->state, curr_state, dfa_state_size) != 0)
 		n += ISSUE_POINTS (insn);
+
+	      /* Go to next choice_state.  */
 	      top++;
-	      top->rest = cached_first_cycle_multipass_dfa_lookahead;
+
+	      /* Initialize it.  */
+	      top->rest = rest;
 	      top->index = i;
 	      top->n = n;
 	      memcpy (top->state, curr_state, dfa_state_size);
Index: modulo-sched.c
===================================================================
--- modulo-sched.c	(revision 188738)
+++ modulo-sched.c	(working copy)
@@ -253,6 +253,7 @@ static struct sched_info sms_sched_info 
   sms_print_insn,
   NULL,
   compute_jump_reg_dependencies,
+  NULL, /* insn_finishes_block_p */
   NULL, NULL,
   NULL, NULL,
   0, 0, 0,
Index: sched-int.h
===================================================================
--- sched-int.h	(revision 188738)
+++ sched-int.h	(working copy)
@@ -171,6 +171,10 @@ struct sched_info
      the jump in the regset.  */
   void (*compute_jump_reg_dependencies) (rtx, regset, regset, regset);
 
+  /* Return true if scheduling insn (passed as the parameter) will trigger
+     finish of scheduling current block.  */
+  bool (*insn_finishes_block_p) (rtx);
+
   /* The boundaries of the set of insns to be scheduled.  */
   rtx prev_head, next_tail;
 
Index: sched-rgn.c
===================================================================
--- sched-rgn.c	(revision 188738)
+++ sched-rgn.c	(working copy)
@@ -2187,6 +2187,19 @@ compute_jump_reg_dependencies (rtx insn 
      add_branch_dependences.  */
 }
 
+/* Return true if scheduling INSN will trigger finish of scheduling
+   current block.  */
+static bool
+rgn_insn_finishes_block_p (rtx insn)
+{
+  if (INSN_BB (insn) == target_bb
+      && sched_target_n_insns + 1 == target_n_insns)
+    /* INSN is the last not-scheduled instruction in the current block.  */
+    return true;
+
+  return false;
+}
+
 /* Used in schedule_insns to initialize current_sched_info for scheduling
    regions (or single basic blocks).  */
 
@@ -2200,6 +2213,7 @@ static struct sched_info region_sched_in
   rgn_print_insn,
   contributes_to_priority,
   compute_jump_reg_dependencies,
+  rgn_insn_finishes_block_p,
 
   NULL, NULL,
   NULL, NULL,