[PATCH] Fix scheduling at the end of blocks.

[Maxim Kuvyrkov <maxim at codesourcery dot com>]

Hi,

This patch makes haifa scheduler better process instructions at the end 
of blocks (basic blocks or extended basic blocks).

First, it fixes bug in max_issue () in handling of the number of 
instructions rest to try (top->rest).  Current behavior is to decrease 
rest field of the current choice state rather than that of a child state.

Second, this patch introduces new scheduler hook 'insn_finishes_block_p 
()'.  This hook aimed to handle situations when DFA permits to issue 
both 'jump' and 'move' on the same cycle (see example below).  As jump 
has greater priority (because it is not speculative), max_issue will 
decide to issue first 'jump' and then 'move'.  But after issuing 'jump', 
scheduler advances to the next block never gave a chance to 
speculatively schedule 'move' in empty_slot for free.

------------
BB1:

empty_slot  // Free stuff!
jump BB3

BB2:

move

BB3:
-------------

OK for trunk?


--
Maxim

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

	* 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.
	

Index: sched-ebb.c
===================================================================
--- sched-ebb.c	(revision 186892)
+++ 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 186892)
+++ haifa-sched.c	(working copy)
@@ -2027,6 +2027,15 @@ move_insn (rtx insn)
   SCHED_GROUP_P (insn) = 0;  
 }
 
+static bool
+insn_finishes_cycle_p (rtx insn)
+{
+  if (current_sched_info->insn_finishes_block_p)
+    return current_sched_info->insn_finishes_block_p (insn);
+
+  return false;
+}
+
 /* The following structure describe an entry of the stack of choices.  */
 struct choice_entry
 {
@@ -2083,13 +2092,14 @@ 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;
+  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++)
@@ -2123,17 +2133,23 @@ 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))
+		rest = 0;
 	      else
-		top->rest--;
+		rest--;
+
 	      n = top->n;
 	      if (memcmp (top->state, curr_state, dfa_state_size) != 0)
 		n += ISSUE_POINTS (insn);
+
 	      top++;
-	      top->rest = cached_first_cycle_multipass_dfa_lookahead;
+
+	      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 186892)
+++ 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 186892)
+++ sched-int.h	(working copy)
@@ -171,6 +171,8 @@ struct sched_info
      the jump in the regset.  */
   void (*compute_jump_reg_dependencies) (rtx, regset, regset, regset);
 
+  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 186892)
+++ sched-rgn.c	(working copy)
@@ -2187,6 +2187,29 @@ compute_jump_reg_dependencies (rtx insn 
      add_branch_dependences.  */
 }
 
+static bool
+rgn_insn_finishes_block_p (rtx insn)
+{
+  if (INSN_BB (insn) == target_bb)
+    {
+      if (sched_target_n_insns + 1 == target_n_insns)
+	return true;
+      else if (control_flow_insn_p (insn))
+	{
+	  rtx head;
+	  rtx tail;
+
+	  get_ebb_head_tail (EBB_FIRST_BB (target_bb), EBB_LAST_BB (target_bb),
+			     &head, &tail);
+
+	  if (insn == tail)
+	    return true;
+	}
+    }
+
+  return false;
+}
+
 /* Used in schedule_insns to initialize current_sched_info for scheduling
    regions (or single basic blocks).  */
 
@@ -2200,6 +2223,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,