Patchwork Scheduler patch: Remove insns that can't be issued from the ready list

login
register
mail settings
Submitter Bernd Schmidt
Date Aug. 30, 2010, 2:54 p.m.
Message ID <4C7BC63C.8070506@codesourcery.com>
Download mbox | patch
Permalink /patch/63047/
State New
Headers show

Comments

Bernd Schmidt - Aug. 30, 2010, 2:54 p.m.
I'm working on a new port which requires accurate scheduling for
correctness.  This patch, and another which I'll submit afterwards, is
necessary to make it work.

The problem here is that the ready list can contain insns that can't be
issued in the current cycle.  When we pick an insn, we try
state_transition, and if that fails, we queue the insn for a later cycle
and try to pick a different insn.

This interacts badly with my code in target_sched_reorder, where I also
need to detect certain cases in which an insn can't be issued.  Assume
the ready list contains two insns, and the target specific code detects
that one of these can't be issued.  It will be moved to the end of the
ready list by target_sched_reorder, which then returns 1 to indicate
that only the first insn on the ready list should be issued.  However,
if schedule_block then finds that this insn can't be issued at the
moment due to a resource conflict, it will pick the second insn and
issue it.

This patch changes schedule_block to earlier get rid of insns which
cannot be issued in the current cycle, before target_sched_reorder is
called.

Bootstrapped and regression tested on i686-linux.  It appears to cause
no changes to generated code.  Ok?


Bernd
* haifa-sched.c (delay_ready_insns_with_resource_conflict): New
	function.
	(schedule_block): Use it whenever we add insns to the ready list.
	Remove code that was moved into the new function.

Patch

Index: haifa-sched.c
===================================================================
--- haifa-sched.c	(revision 163516)
+++ haifa-sched.c	(working copy)
@@ -2761,6 +2762,59 @@  choose_ready (struct ready_list *ready, 
     }
 }
 
+/* Examine all insns on the ready list and queue those which can't be
+   issued in this cycle.  TEMP_STATE is temporary scheduler state we
+   can use as scratch space.  If FIRST_CYCLE_INSN_P is true, no insns
+   have been issued for the current cycle, which means it is valid to
+   issue an asm statement.  Return the number of cycles we must
+   advance to find the next ready instruction, or zero if there remain
+   insns on the ready list.  */
+
+static int
+delay_ready_insns_with_resource_conflict (state_t temp_state,
+					  bool first_cycle_insn_p)
+{
+  int min_cost = INT_MAX;
+  int i;
+
+ restart:
+  for (i = 0; i < ready.n_ready; i++)
+    {
+      rtx insn = ready_element (&ready, i);
+      int cost = 0;
+      
+      if (recog_memoized (insn) < 0)
+	{
+	  if (!first_cycle_insn_p
+	      && (GET_CODE (PATTERN (insn)) == ASM_INPUT
+		  || asm_noperands (PATTERN (insn)) >= 0))
+	    cost = 1;
+	}
+      else if (sched_pressure_p)
+	cost = 0;
+      else
+	{
+	  memcpy (temp_state, curr_state, dfa_state_size);
+	  cost = state_transition (temp_state, insn);
+	  if (cost < 0)
+	    cost = 0;
+	  else if (cost == 0)
+	    cost = 1;
+	}
+      if (cost >= 1)
+	{
+	  if (cost < min_cost)
+	    min_cost = cost;
+	  ready_remove (&ready, i);
+	  queue_insn (insn, cost);
+	  goto restart;
+	}
+    }
+  if (ready.n_ready == 0)
+    return min_cost;
+  return 0;
+}
+
 /* Use forward list scheduling to rearrange insns of block pointed to by
    TARGET_BB, possibly bringing insns from subsequent blocks in the same
    region.  */
@@ -2768,7 +2822,7 @@  choose_ready (struct ready_list *ready, 
 void
 schedule_block (basic_block *target_bb)
 {
-  int i, first_cycle_insn_p;
+  int i;
   int can_issue_more;
   state_t temp_state = NULL;  /* It is used for multipass scheduling.  */
   int sort_p, advance, start_clock_var;
@@ -2907,6 +2961,10 @@  schedule_block (basic_block *target_bb)
 	      debug_ready_list (&ready);
 	    }
 	  advance -= clock_var - start_clock_var;
+
+	  if (advance <= 0)
+	    advance = delay_ready_insns_with_resource_conflict (temp_state,
+								true);		
 	}
       while (advance > 0);
 
@@ -2974,7 +3032,6 @@  schedule_block (basic_block *target_bb)
       else
 	can_issue_more = issue_rate;
 
-      first_cycle_insn_p = 1;
       cycle_issued_insns = 0;
       for (;;)
 	{
@@ -3059,44 +3116,6 @@  schedule_block (basic_block *target_bb)
 	    }
 
 	  sort_p = TRUE;
-	  memcpy (temp_state, curr_state, dfa_state_size);
-	  if (recog_memoized (insn) < 0)
-	    {
-	      asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT
-		       || asm_noperands (PATTERN (insn)) >= 0);
-	      if (!first_cycle_insn_p && asm_p)
-		/* This is asm insn which is tried to be issued on the
-		   cycle not first.  Issue it on the next cycle.  */
-		cost = 1;
-	      else
-		/* A USE insn, or something else we don't need to
-		   understand.  We can't pass these directly to
-		   state_transition because it will trigger a
-		   fatal error for unrecognizable insns.  */
-		cost = 0;
-	    }
-	  else if (sched_pressure_p)
-	    cost = 0;
-	  else
-	    {
-	      cost = state_transition (temp_state, insn);
-	      if (cost < 0)
-		cost = 0;
-	      else if (cost == 0)
-		cost = 1;
-	    }
-
-	  if (cost >= 1)
-	    {
-	      queue_insn (insn, cost);
- 	      if (SCHED_GROUP_P (insn))
- 		{
- 		  advance = cost;
- 		  break;
- 		}
-
-	      continue;
-	    }
 
 	  if (current_sched_info->can_schedule_ready_p
 	      && ! (*current_sched_info->can_schedule_ready_p) (insn))
@@ -3143,11 +3162,18 @@  schedule_block (basic_block *target_bb)
 	  reemit_notes (insn);
 	  last_scheduled_insn = insn;
 
-	  if (memcmp (curr_state, temp_state, dfa_state_size) != 0)
-            {
-              cycle_issued_insns++;
-              memcpy (curr_state, temp_state, dfa_state_size);
+	  if (recog_memoized (insn) >= 0)
+	    {
+	      if (!sched_pressure_p)
+		{
+		  cost = state_transition (curr_state, insn);
+		  gcc_assert (cost < 0);
+		  cycle_issued_insns++;
+		}
             }
+	  else
+	    asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT
+		     || asm_noperands (PATTERN (insn)) >= 0);
 
 	  if (targetm.sched.variable_issue)
 	    can_issue_more =
@@ -3163,11 +3189,12 @@  schedule_block (basic_block *target_bb)
 	  /* After issuing an asm insn we should start a new cycle.  */
 	  if (advance == 0 && asm_p)
 	    advance = 1;
+	  else if (advance == 0 && ready.n_ready > 0)
+	    advance = delay_ready_insns_with_resource_conflict (temp_state, false);
+
 	  if (advance != 0)
 	    break;
 
-	  first_cycle_insn_p = 0;
-
 	  /* Sort the ready list based on priority.  This must be
 	     redone here, as schedule_insn may have readied additional
 	     insns that will not be sorted correctly.  */