haifa-sched.c (ok_for_early_schedule): New function.

        * haifa-sched.c (ok_for_early_schedule): New function.
        (early_queue_to_ready): New function.
        (schedule_block): Allow early removal of insns from Q.
        (schedule_insn): Update INSN_TICK in case of premature
        issue.
        * common.opt (sched_stalled_insns): New flag.
        (sched_stalled_insns_dep): New flag.
        * flags.h: Same above flags.
        * opts.c: Same as above.
        * toplev.c: Same as above.
        * target.h (targetm.sched.is_costly_dependence): New
        hook.
        * target-def.h: Same as above.
        * config/rs6000/rs6000.h: (rs6000_sched_costly_dep):
        Support new flag -msched-costly-dep.
        (DEFAULT_SCHED_COSTLY_DEP): Define.
        * config/rs6000/rs6000.c:
        (rs6000_is_costly_dependence): New function.
        (is_load_insn, is_store_insn): New functions.
        (is_load_insn1, is_store_insn1, is_mem_ref): New
        functions.
        * doc/invoke.texi (-fsched-stalled-insns-dep)
        (-fsched-stalled-insns, -msched-costly-dep): Document
        options.
        * doc/tm.texi (is_costly_dependence): Define new
        scheduler target hook.

From-SVN: r72261

12 files changed, 514 insertions, 3 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index cd3b6d9..bfbdbcf 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,32 @@
+2003-10-09  Dorit Naishlos  <dorit@il.ibm.com>
+
+	* haifa-sched.c (ok_for_early_schedule): New function.
+	(early_queue_to_ready): New function. 
+	(schedule_block): Allow early removal of insns from Q.
+	(schedule_insn): Update INSN_TICK in case of premature
+	issue.
+	* common.opt (sched_stalled_insns): New flag.
+	(sched_stalled_insns_dep): New flag.
+	* flags.h: Same above flags.
+	* opts.c: Same as above.
+	* toplev.c: Same as above.
+	* target.h (targetm.sched.is_costly_dependence): New
+	hook.
+	* target-def.h: Same as above.
+	* config/rs6000/rs6000.h: (rs6000_sched_costly_dep):
+	Support new flag -msched-costly-dep.
+	(DEFAULT_SCHED_COSTLY_DEP): Define.
+	* config/rs6000/rs6000.c: 	
+	(rs6000_is_costly_dependence): New function.
+	(is_load_insn, is_store_insn): New functions.
+	(is_load_insn1, is_store_insn1, is_mem_ref): New 
+	functions.
+	* doc/invoke.texi (-fsched-stalled-insns-dep)
+	(-fsched-stalled-insns, -msched-costly-dep): Document
+	options.
+	* doc/tm.texi (is_costly_dependence): Define new 
+	scheduler target hook.
+
 2003-10-09  Jason Merrill  <jason@redhat.com>
 
 	PR c++/6392
diff --git a/gcc/common.opt b/gcc/common.opt
index 68c37b0..ab1a69d 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -592,6 +592,22 @@ fschedule-insns2
 Common
 Reschedule instructions after register allocation
 
+fsched-stalled-insns
+Common
+Allow premature scheduling of queued insns
+
+fsched-stalled-insns=
+Common RejectNegative Joined UInteger 
+-fsched-stalled-insns=<number>       Set number of queued insns that can be prematurely scheduled
+
+fsched-stalled-insns-dep
+Common
+Set dependence distance checking in premature scheduling of queued insns
+
+fsched-stalled-insns-dep=
+Common RejectNegative Joined UInteger
+-fsched-stalled-insns-dep=<number>   Set dependence distance checking in premature scheduling of queued insns
+
 fshared-data
 Common
 Mark data as shared rather than private
diff --git a/gcc/config/rs6000/rs6000.c b/gcc/config/rs6000/rs6000.c
index af31de5..669f6ac 100644
--- a/gcc/config/rs6000/rs6000.c
+++ b/gcc/config/rs6000/rs6000.c
@@ -86,6 +86,10 @@ struct rs6000_cpu_select rs6000_select[3] =
 const char *rs6000_sched_restricted_insns_priority_str;
 int rs6000_sched_restricted_insns_priority;
 
+/* Support for -msched-costly-dep option.  */
+const char *rs6000_sched_costly_dep_str;
+enum rs6000_dependence_cost rs6000_sched_costly_dep;
+
 /* Size of long double */
 const char *rs6000_long_double_size_string;
 int rs6000_long_double_type_size;
@@ -278,6 +282,7 @@ static int rs6000_adjust_cost (rtx, rtx, rtx, int);
 static int is_dispatch_slot_restricted (rtx);
 static int rs6000_adjust_priority (rtx, int);
 static int rs6000_issue_rate (void);
+static bool rs6000_is_costly_dependence (rtx, rtx, rtx, int, int);
 static int rs6000_use_sched_lookahead (void);
 
 static void rs6000_init_builtins (void);
@@ -469,6 +474,8 @@ static const char alt_reg_names[][8] =
 #define TARGET_SCHED_ADJUST_COST rs6000_adjust_cost
 #undef TARGET_SCHED_ADJUST_PRIORITY
 #define TARGET_SCHED_ADJUST_PRIORITY rs6000_adjust_priority
+#undef TARGET_SCHED_IS_COSTLY_DEPENDENCE      
+#define TARGET_SCHED_IS_COSTLY_DEPENDENCE rs6000_is_costly_dependence
 
 #undef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DFA_LOOKAHEAD
 #define TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DFA_LOOKAHEAD rs6000_use_sched_lookahead
@@ -864,6 +871,21 @@ rs6000_override_options (const char *default_cpu)
     rs6000_sched_restricted_insns_priority =
       atoi (rs6000_sched_restricted_insns_priority_str);
 
+  /* Handle -msched-costly-dep option.  */
+  rs6000_sched_costly_dep = DEFAULT_SCHED_COSTLY_DEP;
+  if (rs6000_sched_costly_dep_str)
+    {
+      if (! strcmp (rs6000_sched_costly_dep_str, "no"))  
+        rs6000_sched_costly_dep = no_dep_costly;
+      else if (! strcmp (rs6000_sched_costly_dep_str, "all"))
+        rs6000_sched_costly_dep = all_deps_costly;
+      else if (! strcmp (rs6000_sched_costly_dep_str, "true_store_to_load"))
+        rs6000_sched_costly_dep = true_store_to_load_dep_costly;
+      else if (! strcmp (rs6000_sched_costly_dep_str, "store_to_load"))
+        rs6000_sched_costly_dep = store_to_load_dep_costly;
+      else rs6000_sched_costly_dep = atoi (rs6000_sched_costly_dep_str);
+    }
+
 #ifdef TARGET_REGNAMES
   /* If the user desires alternate register names, copy in the
      alternate names now.  */
@@ -13383,6 +13405,145 @@ rs6000_use_sched_lookahead (void)
   return 0;
 }
 
+/* Determine is PAT refers to memory.  */
+
+static bool
+is_mem_ref (rtx pat)
+{
+  const char * fmt;
+  int i, j;
+  bool ret = false;
+
+  if (GET_CODE (pat) == MEM)
+    return true;
+
+  /* Recursively process the pattern.  */
+  fmt = GET_RTX_FORMAT (GET_CODE (pat));
+
+  for (i = GET_RTX_LENGTH (GET_CODE (pat)) - 1; i >= 0 && !ret; i--)
+    {
+      if (fmt[i] == 'e')
+	ret |= is_mem_ref (XEXP (pat, i));
+      else if (fmt[i] == 'E')
+	for (j = XVECLEN (pat, i) - 1; j >= 0; j--)
+	  ret |= is_mem_ref (XVECEXP (pat, i, j));
+    }
+
+  return ret;
+}
+
+/* Determine if PAT is a PATTERN of a load insn.  */
+ 
+static bool
+is_load_insn1 (rtx pat)
+{
+  if (!pat || pat == NULL_RTX)
+    return false;
+
+  if (GET_CODE (pat) == SET)
+    return is_mem_ref (SET_SRC (pat));
+
+  if (GET_CODE (pat) == PARALLEL)
+    {
+      int i;
+
+      for (i = 0; i < XVECLEN (pat, 0); i++)
+	if (is_load_insn1 (XVECEXP (pat, 0, i)))
+	  return true;
+    }
+
+  return false;
+}
+
+/* Determine if INSN loads from memory.  */
+
+static bool
+is_load_insn (rtx insn)
+{
+  if (!insn || !INSN_P (insn))
+    return false;
+
+  if (GET_CODE (insn) == CALL_INSN)
+    return false;
+
+  return is_load_insn1 (PATTERN (insn));
+}
+
+/* Determine if PAT is a PATTERN of a store insn.  */
+
+static bool
+is_store_insn1 (rtx pat)
+{
+  if (!pat || pat == NULL_RTX)
+    return false;
+
+  if (GET_CODE (pat) == SET)
+    return is_mem_ref (SET_DEST (pat));
+
+  if (GET_CODE (pat) == PARALLEL)
+    {
+      int i;
+
+      for (i = 0; i < XVECLEN (pat, 0); i++)
+	if (is_store_insn1 (XVECEXP (pat, 0, i)))
+	  return true;
+    }
+
+  return false;
+}
+
+/* Determine if INSN stores to memory.  */
+
+static bool
+is_store_insn (rtx insn)
+{
+  if (!insn || !INSN_P (insn))
+    return false;
+
+  return is_store_insn1 (PATTERN (insn));
+}
+
+/* Returns whether the dependence between INSN and NEXT is considered
+   costly by the given target.  */
+
+static bool
+rs6000_is_costly_dependence (rtx insn, rtx next, rtx link, int cost, int distance)
+{      
+  /* If the flag is not enbled - no dependence is considered costly;
+     allow all dependent insns in the same group. 
+     This is the most aggressive option.  */
+  if (rs6000_sched_costly_dep == no_dep_costly)
+    return false;
+
+  /* If the flag is set to 1 - a dependence is always considered costly; 
+     do not allow dependent instructions in the same group.
+     This is the most conservative option.  */
+  if (rs6000_sched_costly_dep == all_deps_costly)
+    return true;       
+
+  if (rs6000_sched_costly_dep == store_to_load_dep_costly 
+      && is_load_insn (next) 
+      && is_store_insn (insn))
+    /* Prevent load after store in the same group.  */
+    return true;
+
+  if (rs6000_sched_costly_dep == true_store_to_load_dep_costly
+      && is_load_insn (next) 
+      && is_store_insn (insn)
+      && (!link || (int) REG_NOTE_KIND (link) == 0))
+     /* Prevent load after store in the same group if it is a true dependence.  */
+     return true;
+    
+  /* The flag is set to X; dependences with latency >= X are considered costly, 
+     and will not be scheduled in the same group.  */
+  if (rs6000_sched_costly_dep <= max_dep_latency
+      && ((cost - distance) >= (int)rs6000_sched_costly_dep))
+    return true;
+
+  return false;
+}
+
+
 
 /* Length in units of the trampoline for entering a nested function.  */
 
diff --git a/gcc/config/rs6000/rs6000.h b/gcc/config/rs6000/rs6000.h
index 5d7e2e7..fbdb6a5 100644
--- a/gcc/config/rs6000/rs6000.h
+++ b/gcc/config/rs6000/rs6000.h
@@ -376,6 +376,16 @@ extern enum processor_type rs6000_cpu;
    and the old mnemonics are dialect zero.  */
 #define ASSEMBLER_DIALECT (TARGET_NEW_MNEMONICS ? 1 : 0)
 
+/* Types of costly dependences.  */
+enum rs6000_dependence_cost
+ {
+   max_dep_latency = 1000,
+   no_dep_costly,
+   all_deps_costly,
+   true_store_to_load_dep_costly,
+   store_to_load_dep_costly
+ };
+
 /* This is meant to be overridden in target specific files.  */
 #define	SUBTARGET_OPTIONS
 
@@ -402,6 +412,8 @@ extern enum processor_type rs6000_cpu;
    {"longcall", &rs6000_longcall_switch,				\
     N_("Avoid all range limits on call instructions"), 0},		\
    {"no-longcall", &rs6000_longcall_switch, "", 0},			\
+   {"sched-costly-dep=", &rs6000_sched_costly_dep_str,                  \
+    N_("determine which dependences between insns are considered costly"), 0}, \
    {"align-", &rs6000_alignment_string,					\
     N_("Specify alignment of structure fields default/natural"), 0},	\
    {"prioritize-restricted-insns=", &rs6000_sched_restricted_insns_priority_str, \
@@ -461,6 +473,8 @@ extern const char* rs6000_alignment_string;
 extern int rs6000_alignment_flags;
 extern const char *rs6000_sched_restricted_insns_priority_str;
 extern int rs6000_sched_restricted_insns_priority;
+extern const char *rs6000_sched_costly_dep_str;
+extern enum rs6000_dependence_cost rs6000_sched_costly_dep;
 
 /* Alignment options for fields in structures for sub-targets following
    AIX-like ABI.
@@ -479,6 +493,11 @@ extern int rs6000_sched_restricted_insns_priority;
 #define TARGET_ALIGN_NATURAL 0
 #endif
 
+/* Set a default value for DEFAULT_SCHED_COSTLY_DEP used by target hook
+   is_costly_dependence.  */ 
+#define DEFAULT_SCHED_COSTLY_DEP                           \
+  (rs6000_cpu == PROCESSOR_POWER4 ? store_to_load_dep_costly : no_dep_costly)
+
 /* Define if the target has restricted dispatch slot instructions.  */
 #define DEFAULT_RESTRICTED_INSNS_PRIORITY (rs6000_cpu == PROCESSOR_POWER4 ? 1 : 0)
 
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index b943146..20ef67f 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -287,7 +287,9 @@ in the following sections.
 -frerun-cse-after-loop  -frerun-loop-opt @gol
 -frounding-math -fschedule-insns  -fschedule-insns2 @gol
 -fno-sched-interblock  -fno-sched-spec  -fsched-spec-load @gol
--fsched-spec-load-dangerous  -fsched2-use-superblocks @gol
+-fsched-spec-load-dangerous  @gol
+-fsched-stalled-insns=@var{n} -sched-stalled-insns-dep=@var{n} @gol
+-fsched2-use-superblocks @gol
 -fsched2-use-traces  -fsignaling-nans @gol
 -fsingle-precision-constant  -fssa  -fssa-ccp  -fssa-dce @gol
 -fstrength-reduce  -fstrict-aliasing  -ftracer  -fthread-jumps @gol
@@ -432,6 +434,7 @@ in the following sections.
 -mtoc  -mno-toc  -mlittle  -mlittle-endian  -mbig  -mbig-endian @gol
 -mdynamic-no-pic @gol
 -mprioritize-restricted-insns=@var{priority} @gol
+-msched-costly-dep=@var{dependence_type} @gol
 -mcall-sysv  -mcall-netbsd @gol
 -maix-struct-return  -msvr4-struct-return @gol
 -mabi=altivec  -mabi=no-altivec @gol
@@ -4115,6 +4118,18 @@ Allow speculative motion of more load instructions.  This only makes
 sense when scheduling before register allocation, i.e.@: with
 @option{-fschedule-insns} or at @option{-O2} or higher.
 
+@item -fsched-stalled-insns=@var{n}
+@opindex fsched-stalled-insns
+Define how many insns (if any) can be moved prematurely from the queue
+of stalled insns into the ready list, during the second scheduling pass.
+
+@item -fsched-stalled-insns-dep=@var{n}
+@opindex fsched-stalled-insns-dep
+Define how many insn groups (cycles) will be examined for a dependency 
+on a stalled insn that is candidate for premature removal from the queue 
+of stalled insns.  Has an effect only during the second scheduling pass, 
+and only if @option{-fsched-stalled-insns} is used and its value is not zero.
+
 @item -fsched2-use-superblocks
 @opindex fsched2-use-superblocks
 When scheduling after register allocation, do use superblock scheduling
@@ -7535,6 +7550,17 @@ pass.  The argument @var{priority} takes the value @var{0/1/2} to assign
 @var{no/highest/second-highest} priority to dispatch slot restricted 
 instructions.
 
+@item -msched-costly-dep=@var{dependence_type}
+@opindex msched-costly-dep
+This option controls which dependences are considered costly
+by the target during instruction scheduling.  The argument
+@var{dependence_type} takes one of the following values:
+@var{no}: no dependence is costly, 
+@var{all}: all dependences are costly, 
+@var{true_store_to_load}: a true dependence from store to load is costly,
+@var{store_to_load}: any dependence from store to load is costly,
+@var{number}: any dependence which latency >= @var{number} is costly.
+ 
 @item -mcall-sysv
 @opindex mcall-sysv
 On System V.4 and embedded PowerPC systems compile code using calling
diff --git a/gcc/doc/tm.texi b/gcc/doc/tm.texi
index 2fa6fbd..1645319 100644
--- a/gcc/doc/tm.texi
+++ b/gcc/doc/tm.texi
@@ -5668,6 +5668,28 @@ zero.  The hook should return @code{NULL} if there are no more nop
 insns with indexes greater than given index.
 @end deftypefn
 
+@deftypefn {Target Hook} bool IS_COSTLY_DEPENDENCE (rtx @var{insn1}, rtx @var{insn2}, rtx @var{dep_link}, int @var{dep_cost}, int @var{distance})
+This hook is used to define which dependences are considered costly by
+the target, so costly that it is not advisable to schedule the insns that 
+are involved in the dependence too close to one another.  The parameters
+to this hook are as follows:  The second parameter @var{insn2} is dependent 
+upon the first parameter @var{insn1}.  The dependence between @var{insn1} 
+and @var{insn2} is represented by the third parameter @var{dep_link}.  The 
+fourth parameter @var{cost} is the cost of the dependence, and the fifth 
+parameter @var{distance} is the distance in cycles between the two insns. 
+The hook returns @code{true} if considering the distance between the two
+insns the dependence between them is considered costly by the target,
+and @code{false} otherwise.
+
+Defining this hook can be useful in multiple-issue out-of-order machines,
+where (a) it's practically hopeless to predict the actual data/resource 
+delays, however: (b) there's a better chance to predict the actual grouping
+that will be formed, and (c) correctly emulating the grouping can be very 
+important.  In such targets one may want to allow issuing dependent insns
+closer to one another - i.e, closer than the dependence distance;  however, 
+not in cases of "costly dependences", which this hooks allows to define.
+@end deftypefn
+
 Macros in the following table are generated by the program
 @file{genattr} and can be useful for writing the hooks.
 
diff --git a/gcc/flags.h b/gcc/flags.h
index 4d6ea07..f345b49 100644
--- a/gcc/flags.h
+++ b/gcc/flags.h
@@ -439,6 +439,20 @@ extern int flag_schedule_speculative;
 extern int flag_schedule_speculative_load;
 extern int flag_schedule_speculative_load_dangerous;
 
+/* The following flags have an effect during scheduling after register
+   allocation:   
+
+   sched_stalled_insns means that insns can be moved prematurely from the queue
+   of stalled insns into the ready list.
+
+   sched_stalled_insns_dep controls how many recently scheduled cycles will 
+   be examined for a dependency on a stalled insn that is candidate for
+   premature removal from the queue of stalled insns into the ready list (has 
+   an effect only if the flag 'sched_stalled_insns' is set).  */
+
+extern int flag_sched_stalled_insns;
+extern int flag_sched_stalled_insns_dep;
+
 /* flag_branch_on_count_reg means try to replace add-1,compare,branch tupple
    by a cheaper branch, on a count register.  */
 extern int flag_branch_on_count_reg;
diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
index 652ad18..40a0a76 100644
--- a/gcc/haifa-sched.c
+++ b/gcc/haifa-sched.c
@@ -517,6 +517,7 @@ static void ready_sort (struct ready_list *);
 static rtx ready_remove_first (struct ready_list *);
 
 static void queue_to_ready (struct ready_list *);
+static int early_queue_to_ready (state_t, struct ready_list *);
 
 static void debug_ready_list (struct ready_list *);
 
@@ -1247,6 +1248,7 @@ schedule_insn (rtx insn, struct ready_list *ready, int clock)
   rtx link;
   int advance = 0;
   int unit = 0;
+  int premature_issue = 0;
 
   if (!targetm.sched.use_dfa_pipeline_interface
       || !(*targetm.sched.use_dfa_pipeline_interface) ())
@@ -1290,12 +1292,19 @@ schedule_insn (rtx insn, struct ready_list *ready, int clock)
 	return 0;
     }
 
+  if (INSN_TICK (insn) > clock)
+    {
+      /* 'insn' has been prematurely moved from the queue to the
+	 ready list.  */
+      premature_issue = INSN_TICK (insn) - clock;
+    }
+
   for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
     {
       rtx next = XEXP (link, 0);
       int cost = insn_cost (insn, link, next);
 
-      INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost);
+      INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost + premature_issue);
 
       if ((INSN_DEP_COUNT (next) -= 1) == 0)
 	{
@@ -1809,6 +1818,159 @@ queue_to_ready (struct ready_list *ready)
     }
 }
 
+/* Used by early_queue_to_ready.  Determines whether it is "ok" to
+   prematurely move INSN from the queue to the ready list.  Currently, 
+   if a target defines the hook 'is_costly_dependence', this function 
+   uses the hook to check whether there exist any dependences which are
+   considered costly by the target, between INSN and other insns that 
+   have already been scheduled.  Dependences are checked up to Y cycles
+   back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
+   controlling this value. 
+   (Other considerations could be taken into account instead (or in 
+   addition) depending on user flags and target hooks.  */
+
+static bool 
+ok_for_early_queue_removal (rtx insn)
+{
+  int n_cycles;
+  rtx prev_insn = last_scheduled_insn;
+
+  if (targetm.sched.is_costly_dependence)
+    {
+      for (n_cycles = flag_sched_stalled_insns_dep; n_cycles; n_cycles--)
+	{
+	  for ( ; prev_insn; prev_insn = PREV_INSN (prev_insn))
+	    {
+	      rtx dep_link = 0;
+	      int dep_cost;
+
+	      if (GET_CODE (prev_insn) != NOTE)
+		{
+		  dep_link = find_insn_list (insn, INSN_DEPEND (prev_insn));
+		  if (dep_link)
+		    {
+		      dep_cost = insn_cost (prev_insn, dep_link, insn) ;
+		      if (targetm.sched.is_costly_dependence (prev_insn, insn, 
+				dep_link, dep_cost, 
+				flag_sched_stalled_insns_dep - n_cycles))
+			return false;
+		    }
+		}
+
+	      if (GET_MODE (prev_insn) == TImode) /* end of dispatch group */
+		break;
+	    }
+
+	  if (!prev_insn) 
+	    break;
+	  prev_insn = PREV_INSN (prev_insn);     
+	}
+    }
+
+  return true;
+}
+
+
+/* Remove insns from the queue, before they become "ready" with respect
+   to FU latency considerations.   */
+
+static int 
+early_queue_to_ready (state_t state, struct ready_list *ready)
+{
+  rtx insn;
+  rtx link;
+  rtx next_link;
+  rtx prev_link;
+  bool move_to_ready;
+  int cost;
+  state_t temp_state = alloca (dfa_state_size);
+  int stalls;
+  int insns_removed = 0;
+
+  /*
+     Flag '-fsched-stalled-insns=X' determines the aggressiveness of this 
+     function: 
+
+     X == 0: There is no limit on how many queued insns can be removed          
+             prematurely.  (flag_sched_stalled_insns = -1).
+
+     X >= 1: Only X queued insns can be removed prematurely in each 
+	     invocation.  (flag_sched_stalled_insns = X).
+
+     Otherwise: Early queue removal is disabled.
+         (flag_sched_stalled_insns = 0)
+  */
+
+  if (! flag_sched_stalled_insns)   
+    return 0;
+
+  for (stalls = 0; stalls <= MAX_INSN_QUEUE_INDEX; stalls++)
+    {
+      if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
+	{
+	  if (sched_verbose > 6)
+	    fprintf (sched_dump, ";; look at index %d + %d\n", q_ptr, stalls);
+
+	  prev_link = 0;
+	  while (link)
+	    {
+	      next_link = XEXP (link, 1);
+	      insn = XEXP (link, 0);
+	      if (insn && sched_verbose > 6)
+		print_rtl_single (sched_dump, insn);
+
+	      memcpy (temp_state, state, dfa_state_size);
+	      if (recog_memoized (insn) < 0) 
+		/* non-negative to indicate that it's not ready
+		   to avoid infinite Q->R->Q->R... */
+		cost = 0;
+	      else
+		cost = state_transition (temp_state, insn);
+
+	      if (sched_verbose >= 6)
+		fprintf (sched_dump, "transition cost = %d\n", cost);
+
+	      move_to_ready = false;
+	      if (cost < 0) 
+		{
+		  move_to_ready = ok_for_early_queue_removal (insn);
+		  if (move_to_ready == true)
+		    {
+		      /* move from Q to R */
+		      q_size -= 1;
+		      ready_add (ready, insn);
+
+		      if (prev_link)   
+			XEXP (prev_link, 1) = next_link;
+		      else
+			insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = next_link;
+
+		      free_INSN_LIST_node (link);
+
+		      if (sched_verbose >= 2)
+			fprintf (sched_dump, ";;\t\tEarly Q-->Ready: insn %s\n",
+				 (*current_sched_info->print_insn) (insn, 0));
+
+		      insns_removed++;
+		      if (insns_removed == flag_sched_stalled_insns)
+			/* remove only one insn from Q at a time */
+			return insns_removed;
+		    }
+		}
+
+	      if (move_to_ready == false)
+		prev_link = link;
+
+	      link = next_link;
+	    } /* while link */
+	} /* if link */    
+
+    } /* for stalls.. */
+
+  return insns_removed; 
+}
+
+
 /* Print the ready list for debugging purposes.  Callable from debugger.  */
 
 static void
@@ -2251,6 +2413,20 @@ schedule_block (int b, int rgn_n_insns)
 	    }
 	  else
 	    {
+	      if (ready.n_ready == 0 
+		  && can_issue_more 
+		  && reload_completed) 
+		{
+		  /* Allow scheduling insns directly from the queue in case
+		     there's nothing better to do (ready list is empty) but
+		     there are still vacant dispatch slots in the current cycle.  */
+		  if (sched_verbose >= 6)
+		    fprintf(sched_dump,";;\t\tSecond chance\n");
+		  memcpy (temp_state, curr_state, dfa_state_size);
+		  if (early_queue_to_ready (temp_state, &ready))
+		    ready_sort (&ready);
+		}
+
 	      if (ready.n_ready == 0 || !can_issue_more
 		  || state_dead_lock_p (curr_state)
 		  || !(*current_sched_info->schedule_more_p) ())
diff --git a/gcc/opts.c b/gcc/opts.c
index c4c5b9f..dc489e1 100644
--- a/gcc/opts.c
+++ b/gcc/opts.c
@@ -1264,6 +1264,24 @@ common_handle_option (size_t scode, const char *arg,
       flag_schedule_insns_after_reload = value;
       break;
 
+    case OPT_fsched_stalled_insns:
+      flag_sched_stalled_insns = value;
+      break;
+
+    case OPT_fsched_stalled_insns_:
+      flag_sched_stalled_insns = value;
+      if (flag_sched_stalled_insns == 0)
+	flag_sched_stalled_insns = -1;
+      break;
+
+    case OPT_fsched_stalled_insns_dep:
+      flag_sched_stalled_insns_dep = 1;
+      break;
+
+    case OPT_fsched_stalled_insns_dep_:
+      flag_sched_stalled_insns_dep = value;
+      break;
+
     case OPT_fshared_data:
       flag_shared_data = value;
       break;
diff --git a/gcc/target-def.h b/gcc/target-def.h
index e5606a3..3f35e2e 100644
--- a/gcc/target-def.h
+++ b/gcc/target-def.h
@@ -230,6 +230,7 @@ Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 #define TARGET_SCHED_DFA_NEW_CYCLE 0
 #define TARGET_SCHED_INIT_DFA_BUBBLES 0
 #define TARGET_SCHED_DFA_BUBBLE 0
+#define TARGET_SCHED_IS_COSTLY_DEPENDENCE 0
 
 #define TARGET_SCHED						\
   {TARGET_SCHED_ADJUST_COST,					\
@@ -250,7 +251,8 @@ Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
    TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DFA_LOOKAHEAD_GUARD,	\
    TARGET_SCHED_DFA_NEW_CYCLE,					\
    TARGET_SCHED_INIT_DFA_BUBBLES,				\
-   TARGET_SCHED_DFA_BUBBLE}
+   TARGET_SCHED_DFA_BUBBLE,                                     \
+   TARGET_SCHED_IS_COSTLY_DEPENDENCE}
 
 /* In tree.c.  */
 #define TARGET_MERGE_DECL_ATTRIBUTES merge_decl_attributes
diff --git a/gcc/target.h b/gcc/target.h
index 15d7233..8d77dfd 100644
--- a/gcc/target.h
+++ b/gcc/target.h
@@ -251,6 +251,18 @@ struct gcc_target
        scheduling.  */
     void (* init_dfa_bubbles) (void);
     rtx (* dfa_bubble) (int);
+    /* The following member value is a pointer to a function called
+       by the insn scheduler.  It should return true if there exists a
+       dependence which is considered costly by the target, between 
+       the insn passed as the first parameter, and the insn passed as 
+       the second parameter.  The third parameter is the INSN_DEPEND 
+       link that represents the dependence between the two insns.  The
+       fourth argument is the cost of the dependence as estimated by
+       the scheduler.  The last argument is the distance in cycles 
+       between the already scheduled insn (first parameter) and the
+       the second insn (second parameter).
+    */
+    bool (* is_costly_dependence) PARAMS ((rtx, rtx, rtx, int, int));
   } sched;
 
   /* Given two decls, merge their attributes and return the result.  */
diff --git a/gcc/toplev.c b/gcc/toplev.c
index 425a0259..bc96c64 100644
--- a/gcc/toplev.c
+++ b/gcc/toplev.c
@@ -826,6 +826,20 @@ int flag_schedule_speculative = 1;
 int flag_schedule_speculative_load = 0;
 int flag_schedule_speculative_load_dangerous = 0;
 
+/* The following flags have an effect during scheduling after register
+   allocation:
+
+   flag_sched_stalled_insns means that insns can be moved prematurely from the queue
+   of stalled insns into the ready list.
+  
+   flag_sched_stalled_insns_dep controls how many insn groups will be examined
+   for a dependency on a stalled insn that is candidate for premature removal
+   from the queue of stalled insns into the ready list (has an effect only if
+   the flag 'sched_stalled_insns' is set).  */ 
+
+int flag_sched_stalled_insns = 0;
+int flag_sched_stalled_insns_dep = 1;
+
 int flag_single_precision_constant;
 
 /* flag_branch_on_count_reg means try to replace add-1,compare,branch tupple
@@ -1069,6 +1083,8 @@ static const lang_independent_options f_options[] =
   {"sched-spec",&flag_schedule_speculative, 1 },
   {"sched-spec-load",&flag_schedule_speculative_load, 1 },
   {"sched-spec-load-dangerous",&flag_schedule_speculative_load_dangerous, 1 },
+  {"sched-stalled-insns", &flag_sched_stalled_insns, 0 },
+  {"sched-stalled-insns-dep", &flag_sched_stalled_insns_dep, 1 },
   {"sched2-use-superblocks", &flag_sched2_use_superblocks, 1 },
   {"sched2-use-traces", &flag_sched2_use_traces, 1 },
   {"branch-count-reg",&flag_branch_on_count_reg, 1 },