public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH] Fix scheduling at the end of blocks.
@ 2007-11-21 20:37 Maxim Kuvyrkov
  2007-12-05 21:37 ` Maxim Kuvyrkov
  0 siblings, 1 reply; 9+ messages in thread
From: Maxim Kuvyrkov @ 2007-11-21 20:37 UTC (permalink / raw)
  To: Vladimir Makarov; +Cc: gcc-patches, Andrey Belevantsev

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

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

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

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.
	

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

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,

^ permalink raw reply	[flat|nested] 9+ messages in thread

end of thread, other threads:[~2008-06-03 15:00 UTC | newest]

Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2007-11-21 20:37 [PATCH] Fix scheduling at the end of blocks Maxim Kuvyrkov
2007-12-05 21:37 ` Maxim Kuvyrkov
2007-12-05 22:02   ` Richard Guenther
2007-12-06 11:33     ` Maxim Kuvyrkov
2007-12-10 18:01       ` Vladimir Makarov
2008-03-14 12:21         ` Maxim Kuvyrkov
2008-03-28 15:57           ` [PATCH][PING] " Maxim Kuvyrkov
2008-03-28 18:23             ` Vladimir Makarov
2008-06-03 15:00               ` Maxim Kuvyrkov

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).