2002-04-29 Vladimir Makarov <vmakarov@redhat.com>

	Merging code from dfa-branch:


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@52915 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 565 insertions, 106 deletions

diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
index 686369d418f..2ac8121801f 100644
--- a/gcc/haifa-sched.c
+++ b/gcc/haifa-sched.c
@@ -158,6 +158,12 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 
 static int issue_rate;
 
+/* If the following variable value is non zero, the scheduler inserts
+   bubbles (nop insns).  The value of variable affects on scheduler
+   behavior only if automaton pipeline interface with multipass
+   scheduling is used and hook dfa_bubble is defined.  */
+int insert_schedule_bubbles_p = 0;
+
 /* sched-verbose controls the amount of debugging output the
    scheduler prints.  It is controlled by -fsched-verbose=N:
    N>0 and no -DSR : the output is directed to stderr.
@@ -254,14 +260,39 @@ static rtx note_list;
    passes or stalls are introduced.  */
 
 /* Implement a circular buffer to delay instructions until sufficient
-   time has passed.  INSN_QUEUE_SIZE is a power of two larger than
-   MAX_BLOCKAGE and MAX_READY_COST computed by genattr.c.  This is the
-   longest time an isnsn may be queued.  */
-static rtx insn_queue[INSN_QUEUE_SIZE];
+   time has passed.  For the old pipeline description interface,
+   INSN_QUEUE_SIZE is a power of two larger than MAX_BLOCKAGE and
+   MAX_READY_COST computed by genattr.c.  For the new pipeline
+   description interface, MAX_INSN_QUEUE_INDEX is a power of two minus
+   one which is larger than maximal time of instruction execution
+   computed by genattr.c on the base maximal time of functional unit
+   reservations and geting a result.  This is the longest time an
+   insn may be queued.  */
+
+#define MAX_INSN_QUEUE_INDEX max_insn_queue_index_macro_value
+
+static rtx *insn_queue;
 static int q_ptr = 0;
 static int q_size = 0;
-#define NEXT_Q(X) (((X)+1) & (INSN_QUEUE_SIZE-1))
-#define NEXT_Q_AFTER(X, C) (((X)+C) & (INSN_QUEUE_SIZE-1))
+#define NEXT_Q(X) (((X)+1) & MAX_INSN_QUEUE_INDEX)
+#define NEXT_Q_AFTER(X, C) (((X)+C) & MAX_INSN_QUEUE_INDEX)
+
+/* The following variable defines value for macro
+   MAX_INSN_QUEUE_INDEX.  */
+static int max_insn_queue_index_macro_value;
+
+/* The following variable value refers for all current and future
+   reservations of the processor units.  */
+state_t curr_state;
+
+/* The following variable value is size of memory representing all
+   current and future reservations of the processor units.  It is used
+   only by DFA based scheduler.  */
+static size_t dfa_state_size;
+
+/* The following array is used to find the best insn from ready when
+   the automaton pipeline interface is used.  */
+static char *ready_try;
 
 /* Describe the ready list of the scheduler.
    VEC holds space enough for all insns in the current region.  VECLEN
@@ -280,11 +311,15 @@ struct ready_list
 };
 
 /* Forward declarations.  */
+
+/* The scheduler using only DFA description should never use the
+   following five functions:  */
 static unsigned int blockage_range PARAMS ((int, rtx));
 static void clear_units PARAMS ((void));
 static void schedule_unit PARAMS ((int, rtx, int));
 static int actual_hazard PARAMS ((int, rtx, int, int));
 static int potential_hazard PARAMS ((int, rtx, int));
+
 static int priority PARAMS ((rtx));
 static int rank_for_schedule PARAMS ((const PTR, const PTR));
 static void swap_sort PARAMS ((rtx *, int));
@@ -292,6 +327,7 @@ static void queue_insn PARAMS ((rtx, int));
 static void schedule_insn PARAMS ((rtx, struct ready_list *, int));
 static void find_insn_reg_weight PARAMS ((int));
 static void adjust_priority PARAMS ((rtx));
+static void advance_one_cycle PARAMS ((void));
 
 /* Notes handling mechanism:
    =========================
@@ -331,6 +367,14 @@ static void debug_ready_list PARAMS ((struct ready_list *));
 static rtx move_insn1 PARAMS ((rtx, rtx));
 static rtx move_insn PARAMS ((rtx, rtx));
 
+/* The following functions are used to implement multi-pass scheduling
+   on the first cycle.  It is used only for DFA based scheduler.  */
+static rtx ready_element PARAMS ((struct ready_list *, int));
+static rtx ready_remove PARAMS ((struct ready_list *, int));
+static int max_issue PARAMS ((struct ready_list *, state_t, int *));
+
+static rtx choose_ready PARAMS ((struct ready_list *));
+
 #endif /* INSN_SCHEDULING */
 
 /* Point to state used for the current scheduling pass.  */
@@ -354,7 +398,8 @@ static rtx last_scheduled_insn;
    returned by function_units_used.  A function unit is encoded as the
    unit number if the value is non-negative and the compliment of a
    mask if the value is negative.  A function unit index is the
-   non-negative encoding.  */
+   non-negative encoding.  The scheduler using only DFA description
+   should never use the following function.  */
 
 HAIFA_INLINE int
 insn_unit (insn)
@@ -391,7 +436,9 @@ insn_unit (insn)
 /* Compute the blockage range for executing INSN on UNIT.  This caches
    the value returned by the blockage_range_function for the unit.
    These values are encoded in an int where the upper half gives the
-   minimum value and the lower half gives the maximum value.  */
+   minimum value and the lower half gives the maximum value.  The
+   scheduler using only DFA description should never use the following
+   function.  */
 
 HAIFA_INLINE static unsigned int
 blockage_range (unit, insn)
@@ -415,20 +462,38 @@ blockage_range (unit, insn)
   return range;
 }
 
-/* A vector indexed by function unit instance giving the last insn to use
-   the unit.  The value of the function unit instance index for unit U
-   instance I is (U + I * FUNCTION_UNITS_SIZE).  */
+/* A vector indexed by function unit instance giving the last insn to
+   use the unit.  The value of the function unit instance index for
+   unit U instance I is (U + I * FUNCTION_UNITS_SIZE).  The scheduler
+   using only DFA description should never use the following variable.  */
+#if FUNCTION_UNITS_SIZE
 static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
+#else
+static rtx unit_last_insn[1];
+#endif
 
-/* A vector indexed by function unit instance giving the minimum time when
-   the unit will unblock based on the maximum blockage cost.  */
+/* A vector indexed by function unit instance giving the minimum time
+   when the unit will unblock based on the maximum blockage cost.  The
+   scheduler using only DFA description should never use the following
+   variable.  */
+#if FUNCTION_UNITS_SIZE
 static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
+#else
+static int unit_tick[1];
+#endif
 
 /* A vector indexed by function unit number giving the number of insns
-   that remain to use the unit.  */
+   that remain to use the unit.  The scheduler using only DFA
+   description should never use the following variable.  */
+#if FUNCTION_UNITS_SIZE
 static int unit_n_insns[FUNCTION_UNITS_SIZE];
+#else
+static int unit_n_insns[1];
+#endif
 
-/* Access the unit_last_insn array.  Used by the visualization code.  */
+/* Access the unit_last_insn array.  Used by the visualization code.
+   The scheduler using only DFA description should never use the
+   following function.  */
 
 rtx
 get_unit_last_insn (instance)
@@ -447,7 +512,8 @@ clear_units ()
   memset ((char *) unit_n_insns, 0, sizeof (unit_n_insns));
 }
 
-/* Return the issue-delay of an insn.  */
+/* Return the issue-delay of an insn.  The scheduler using only DFA
+   description should never use the following function.  */
 
 HAIFA_INLINE int
 insn_issue_delay (insn)
@@ -477,7 +543,8 @@ insn_issue_delay (insn)
 
 /* Return the actual hazard cost of executing INSN on the unit UNIT,
    instance INSTANCE at time CLOCK if the previous actual hazard cost
-   was COST.  */
+   was COST.  The scheduler using only DFA description should never
+   use the following function.  */
 
 HAIFA_INLINE int
 actual_hazard_this_instance (unit, instance, insn, clock, cost)
@@ -513,8 +580,9 @@ actual_hazard_this_instance (unit, instance, insn, clock, cost)
   return cost;
 }
 
-/* Record INSN as having begun execution on the units encoded by UNIT at
-   time CLOCK.  */
+/* Record INSN as having begun execution on the units encoded by UNIT
+   at time CLOCK.  The scheduler using only DFA description should
+   never use the following function.  */
 
 HAIFA_INLINE static void
 schedule_unit (unit, insn, clock)
@@ -545,8 +613,10 @@ schedule_unit (unit, insn, clock)
 	schedule_unit (i, insn, clock);
 }
 
-/* Return the actual hazard cost of executing INSN on the units encoded by
-   UNIT at time CLOCK if the previous actual hazard cost was COST.  */
+/* Return the actual hazard cost of executing INSN on the units
+   encoded by UNIT at time CLOCK if the previous actual hazard cost
+   was COST.  The scheduler using only DFA description should never
+   use the following function.  */
 
 HAIFA_INLINE static int
 actual_hazard (unit, insn, clock, cost)
@@ -591,11 +661,13 @@ actual_hazard (unit, insn, clock, cost)
 }
 
 /* Return the potential hazard cost of executing an instruction on the
-   units encoded by UNIT if the previous potential hazard cost was COST.
-   An insn with a large blockage time is chosen in preference to one
-   with a smaller time; an insn that uses a unit that is more likely
-   to be used is chosen in preference to one with a unit that is less
-   used.  We are trying to minimize a subsequent actual hazard.  */
+   units encoded by UNIT if the previous potential hazard cost was
+   COST.  An insn with a large blockage time is chosen in preference
+   to one with a smaller time; an insn that uses a unit that is more
+   likely to be used is chosen in preference to one with a unit that
+   is less used.  We are trying to minimize a subsequent actual
+   hazard.  The scheduler using only DFA description should never use
+   the following function.  */
 
 HAIFA_INLINE static int
 potential_hazard (unit, insn, cost)
@@ -648,62 +720,69 @@ insn_cost (insn, link, used)
 {
   int cost = INSN_COST (insn);
 
-  if (cost == 0)
+  if (cost < 0)
     {
-      recog_memoized (insn);
-
-      /* A USE insn, or something else we don't need to understand.
-         We can't pass these directly to result_ready_cost because it will
-         trigger a fatal error for unrecognizable insns.  */
-      if (INSN_CODE (insn) < 0)
+      /* A USE insn, or something else we don't need to
+	 understand.  We can't pass these directly to
+	 result_ready_cost or insn_default_latency because it will
+	 trigger a fatal error for unrecognizable insns.  */
+      if (recog_memoized (insn) < 0)
 	{
-	  INSN_COST (insn) = 1;
-	  return 1;
+	  INSN_COST (insn) = 0;
+	  return 0;
 	}
       else
 	{
-	  cost = result_ready_cost (insn);
-
-	  if (cost < 1)
-	    cost = 1;
-
+	  if (targetm.sched.use_dfa_pipeline_interface
+	      && (*targetm.sched.use_dfa_pipeline_interface) ())
+	    cost = insn_default_latency (insn);
+	  else
+	    cost = result_ready_cost (insn);
+	  
+	  if (cost < 0)
+	    cost = 0;
+	  
 	  INSN_COST (insn) = cost;
 	}
     }
 
   /* In this case estimate cost without caring how insn is used.  */
-  if (link == 0 && used == 0)
+  if (link == 0 || used == 0)
     return cost;
 
-  /* A USE insn should never require the value used to be computed.  This
-     allows the computation of a function's result and parameter values to
-     overlap the return and call.  */
-  recog_memoized (used);
-  if (INSN_CODE (used) < 0)
-    LINK_COST_FREE (link) = 1;
-
-  /* If some dependencies vary the cost, compute the adjustment.  Most
-     commonly, the adjustment is complete: either the cost is ignored
-     (in the case of an output- or anti-dependence), or the cost is
-     unchanged.  These values are cached in the link as LINK_COST_FREE
-     and LINK_COST_ZERO.  */
-
-  if (LINK_COST_FREE (link))
+  /* A USE insn should never require the value used to be computed.
+     This allows the computation of a function's result and parameter
+     values to overlap the return and call.  */
+  if (recog_memoized (used) < 0)
     cost = 0;
-  else if (!LINK_COST_ZERO (link) && targetm.sched.adjust_cost)
+  else
     {
-      int ncost = (*targetm.sched.adjust_cost) (used, link, insn, cost);
-
-      if (ncost < 1)
+      if (targetm.sched.use_dfa_pipeline_interface
+	  && (*targetm.sched.use_dfa_pipeline_interface) ())
 	{
-	  LINK_COST_FREE (link) = 1;
-	  ncost = 0;
+	  if (INSN_CODE (insn) >= 0)
+	    {
+	      if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
+		cost = 0;
+	      else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
+		{
+		  cost = (insn_default_latency (insn)
+			  - insn_default_latency (used));
+		  if (cost <= 0)
+		    cost = 1;
+		}
+	      else if (bypass_p (insn))
+		cost = insn_latency (insn, used);
+	    }
 	}
-      if (cost == ncost)
-	LINK_COST_ZERO (link) = 1;
-      cost = ncost;
-    }
 
+      if (targetm.sched.adjust_cost)
+	cost = (*targetm.sched.adjust_cost) (used, link, insn, cost);
+
+      if (cost < 0)
+	cost = 0;
+    }
+  
   return cost;
 }
 
@@ -930,6 +1009,48 @@ ready_remove_first (ready)
   return t;
 }
 
+/* The following code implements multi-pass scheduling for the first
+   cycle.  In other words, we will try to choose ready insn which
+   permits to start maximum number of insns on the same cycle.  */
+
+/* Return a pointer to the element INDEX from the ready.  INDEX for
+   insn with the highest priority is 0, and the lowest priority has
+   N_READY - 1.  */
+
+HAIFA_INLINE static rtx
+ready_element (ready, index)
+     struct ready_list *ready;
+     int index;
+{
+  if (ready->n_ready == 0 || index >= ready->n_ready)
+    abort ();
+  return ready->vec[ready->first - index];
+}
+
+/* Remove the element INDEX from the ready list and return it.  INDEX
+   for insn with the highest priority is 0, and the lowest priority
+   has N_READY - 1.  */
+
+HAIFA_INLINE static rtx
+ready_remove (ready, index)
+     struct ready_list *ready;
+     int index;
+{
+  rtx t;
+  int i;
+
+  if (index == 0)
+    return ready_remove_first (ready);
+  if (ready->n_ready == 0 || index >= ready->n_ready)
+    abort ();
+  t = ready->vec[ready->first - index];
+  ready->n_ready--;
+  for (i = index; i < ready->n_ready; i++)
+    ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
+  return t;
+}
+
+
 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
    macro.  */
 
@@ -961,6 +1082,25 @@ adjust_priority (prev)
       (*targetm.sched.adjust_priority) (prev, INSN_PRIORITY (prev));
 }
 
+/* Advance time on one cycle.  */
+HAIFA_INLINE static void
+advance_one_cycle ()
+{
+  if (targetm.sched.use_dfa_pipeline_interface
+      && (*targetm.sched.use_dfa_pipeline_interface) ())
+    {
+      if (targetm.sched.dfa_pre_cycle_insn)
+	state_transition (curr_state,
+			  (*targetm.sched.dfa_pre_cycle_insn) ());
+
+      state_transition (curr_state, NULL);
+
+      if (targetm.sched.dfa_post_cycle_insn)
+	state_transition (curr_state,
+			  (*targetm.sched.dfa_post_cycle_insn) ());
+    }
+}
+
 /* Clock at which the previous instruction was issued.  */
 static int last_clock_var;
 
@@ -976,26 +1116,50 @@ schedule_insn (insn, ready, clock)
      int clock;
 {
   rtx link;
-  int unit;
+  int unit = 0;
 
-  unit = insn_unit (insn);
+  if (!targetm.sched.use_dfa_pipeline_interface
+      || !(*targetm.sched.use_dfa_pipeline_interface) ())
+    unit = insn_unit (insn);
 
   if (sched_verbose >= 2)
     {
-      fprintf (sched_dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ",
-	       INSN_UID (insn));
-      insn_print_units (insn);
+
+      if (targetm.sched.use_dfa_pipeline_interface
+	  && (*targetm.sched.use_dfa_pipeline_interface) ())
+	{
+	  fprintf (sched_dump,
+		   ";;\t\t--> scheduling insn <<<%d>>>:reservation ",
+		   INSN_UID (insn));
+	  
+	  if (recog_memoized (insn) < 0)
+	    fprintf (sched_dump, "nothing");
+	  else
+	    print_reservation (sched_dump, insn);
+	}
+      else
+	{
+	  fprintf (sched_dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ",
+		   INSN_UID (insn));
+	  insn_print_units (insn);
+	}
+
       fprintf (sched_dump, "\n");
     }
 
-  if (sched_verbose && unit == -1)
-    visualize_no_unit (insn);
+  if (!targetm.sched.use_dfa_pipeline_interface
+      || !(*targetm.sched.use_dfa_pipeline_interface) ())
+    {
+      if (sched_verbose && unit == -1)
+	visualize_no_unit (insn);
 
-  if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose)
-    schedule_unit (unit, insn, clock);
 
-  if (INSN_DEPEND (insn) == 0)
-    return;
+      if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose)
+	schedule_unit (unit, insn, clock);
+      
+      if (INSN_DEPEND (insn) == 0)
+	return;
+    }
 
   for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
     {
@@ -1037,7 +1201,9 @@ schedule_insn (insn, ready, clock)
      to issue on the same cycle as the previous insn.  A machine
      may use this information to decide how the instruction should
      be aligned.  */
-  if (reload_completed && issue_rate > 1)
+  if (reload_completed && issue_rate > 1
+      && GET_CODE (PATTERN (insn)) != USE
+      && GET_CODE (PATTERN (insn)) != CLOBBER)
     {
       PUT_MODE (insn, clock > last_clock_var ? TImode : VOIDmode);
       last_clock_var = clock;
@@ -1464,7 +1630,7 @@ queue_to_ready (ready)
     {
       int stalls;
 
-      for (stalls = 1; stalls < INSN_QUEUE_SIZE; stalls++)
+      for (stalls = 1; stalls <= MAX_INSN_QUEUE_INDEX; stalls++)
 	{
 	  if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
 	    {
@@ -1483,13 +1649,19 @@ queue_to_ready (ready)
 		}
 	      insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
 
-	      if (ready->n_ready)
-		break;
+	      advance_one_cycle ();
+
+	      break;
 	    }
+
+	  advance_one_cycle ();
 	}
 
-      if (sched_verbose && stalls)
+      if ((!targetm.sched.use_dfa_pipeline_interface
+	   || !(*targetm.sched.use_dfa_pipeline_interface) ())
+	  && sched_verbose && stalls)
 	visualize_stall_cycles (stalls);
+
       q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
       clock_var += stalls;
     }
@@ -1505,7 +1677,10 @@ debug_ready_list (ready)
   int i;
 
   if (ready->n_ready == 0)
-    return;
+    {
+      fprintf (sched_dump, "\n");
+      return;
+    }
 
   p = ready_lastpos (ready);
   for (i = 0; i < ready->n_ready; i++)
@@ -1617,6 +1792,113 @@ move_insn (insn, last)
   return retval;
 }
 
+/* The following function returns maximal (or close to maximal) number
+   of insns which can be issued on the same cycle and one of which
+   insns is insns with the best rank (the last insn in READY).  To
+   make this function tries different samples of ready insns.  READY
+   is current queue `ready'.  Global array READY_TRY reflects what
+   insns are already issued in this try.  STATE is current processor
+   state.  If the function returns nonzero, INDEX will contain index
+   of the best insn in READY.  The following function is used only for
+   first cycle multipass scheduling.  */
+
+static int
+max_issue (ready, state, index)
+     struct ready_list *ready;
+     state_t state;
+     int *index;
+{
+  int i, best, n, temp_index, delay;
+  state_t temp_state;
+  rtx insn;
+  int max_lookahead = (*targetm.sched.first_cycle_multipass_dfa_lookahead) ();
+
+  if (state_dead_lock_p (state))
+    return 0;
+
+  temp_state = alloca (dfa_state_size);
+  best = 0;
+  
+  for (i = 0; i < ready->n_ready; i++)
+    if (!ready_try [i])
+      {
+	insn = ready_element (ready, i);
+	
+	if (INSN_CODE (insn) < 0)
+	  continue;
+	
+	memcpy (temp_state, state, dfa_state_size);
+	
+	delay = state_transition (temp_state, insn);
+	
+	if (delay == 0)
+	  {
+	    if (!targetm.sched.dfa_bubble)
+	      continue;
+	    else
+	      {
+		int j;
+		rtx bubble;
+		
+		for (j = 0;
+		     (bubble = (*targetm.sched.dfa_bubble) (j)) != NULL_RTX;
+		     j++)
+		  if (state_transition (temp_state, bubble) < 0
+		      && state_transition (temp_state, insn) < 0)
+		    break;
+		
+		if (bubble == NULL_RTX)
+		  continue;
+	      }
+	  }
+	else if (delay > 0)
+	  continue;
+	
+	--max_lookahead;
+	
+	if (max_lookahead < 0)
+	  break;
+	
+	ready_try [i] = 1;
+
+	n = max_issue (ready, temp_state, &temp_index);
+	if (n > 0 || ready_try[0])
+	  n += 1;
+
+	if (best < n)
+	  {
+	    best = n;
+	    *index = i;
+	  }
+	ready_try [i] = 0;
+      }
+  
+  return best;
+}
+
+/* The following function chooses insn from READY and modifies
+   *N_READY and READY.  The following function is used only for first
+   cycle multipass scheduling.  */
+
+static rtx
+choose_ready (ready)
+     struct ready_list *ready;
+{
+  if (!targetm.sched.first_cycle_multipass_dfa_lookahead
+      || (*targetm.sched.first_cycle_multipass_dfa_lookahead) () <= 0)
+    return ready_remove_first (ready);
+  else
+    {
+      /* Try to choose the better insn.  */
+      int index;
+
+      if (max_issue (ready, curr_state, &index) == 0)
+	return ready_remove_first (ready);
+      else
+	return ready_remove (ready, index);
+    }
+}
+
 /* Called from backends from targetm.sched.reorder to emit stuff into
    the instruction stream.  */
 
@@ -1638,7 +1920,9 @@ schedule_block (b, rgn_n_insns)
      int rgn_n_insns;
 {
   struct ready_list ready;
+  int first_cycle_insn_p;
   int can_issue_more;
+  state_t temp_state = NULL;  /* It is used for multipass scheduling.  */
 
   /* Head/tail info for this block.  */
   rtx prev_head = current_sched_info->prev_head;
@@ -1671,7 +1955,11 @@ schedule_block (b, rgn_n_insns)
       init_block_visualization ();
     }
 
-  clear_units ();
+  if (targetm.sched.use_dfa_pipeline_interface
+      && (*targetm.sched.use_dfa_pipeline_interface) ())
+    state_reset (curr_state);
+  else
+    clear_units ();
 
   /* Allocate the ready list.  */
   ready.veclen = rgn_n_insns + 1 + issue_rate;
@@ -1679,6 +1967,15 @@ schedule_block (b, rgn_n_insns)
   ready.vec = (rtx *) xmalloc (ready.veclen * sizeof (rtx));
   ready.n_ready = 0;
 
+  if (targetm.sched.use_dfa_pipeline_interface
+      && (*targetm.sched.use_dfa_pipeline_interface) ())
+    {
+      /* It is used for first cycle multipass scheduling.  */
+      temp_state = alloca (dfa_state_size);
+      ready_try = (char *) xmalloc ((rgn_n_insns + 1) * sizeof (char));
+      memset (ready_try, 0, (rgn_n_insns + 1) * sizeof (char));
+    }
+
   (*current_sched_info->init_ready_list) (&ready);
 
   if (targetm.sched.md_init)
@@ -1691,8 +1988,16 @@ schedule_block (b, rgn_n_insns)
      queue.  */
   q_ptr = 0;
   q_size = 0;
-  last_clock_var = 0;
-  memset ((char *) insn_queue, 0, sizeof (insn_queue));
+
+  if (!targetm.sched.use_dfa_pipeline_interface
+      || !(*targetm.sched.use_dfa_pipeline_interface) ())
+    max_insn_queue_index_macro_value = INSN_QUEUE_SIZE - 1;
+  else
+    max_insn_queue_index_macro_value = max_insn_queue_index;
+
+  insn_queue = (rtx *) alloca ((MAX_INSN_QUEUE_INDEX + 1) * sizeof (rtx));
+  memset ((char *) insn_queue, 0, (MAX_INSN_QUEUE_INDEX + 1) * sizeof (rtx));
+  last_clock_var = -1;
 
   /* Start just before the beginning of time.  */
   clock_var = -1;
@@ -1702,12 +2007,18 @@ schedule_block (b, rgn_n_insns)
     {
       clock_var++;
 
+      advance_one_cycle ();
+
       /* Add to the ready list all pending insns that can be issued now.
          If there are no ready insns, increment clock until one
          is ready and add all pending insns at that point to the ready
          list.  */
       queue_to_ready (&ready);
 
+      if (sched_verbose && targetm.sched.cycle_display)
+	last_scheduled_insn
+	  = (*targetm.sched.cycle_display) (clock_var, last_scheduled_insn);
+
       if (ready.n_ready == 0)
 	abort ();
 
@@ -1730,24 +2041,127 @@ schedule_block (b, rgn_n_insns)
       else
 	can_issue_more = issue_rate;
 
-      if (sched_verbose && targetm.sched.cycle_display)
-	last_scheduled_insn
-	  = (*targetm.sched.cycle_display) (clock_var, last_scheduled_insn);
-
-      if (sched_verbose)
+      first_cycle_insn_p = 1;
+      for (;;)
 	{
-	  fprintf (sched_dump, "\n;;\tReady list (t =%3d):  ", clock_var);
-	  debug_ready_list (&ready);
-	}
+	  rtx insn;
+	  int cost;
+
+	  if (sched_verbose)
+	    {
+	      fprintf (sched_dump, ";;\tReady list (t =%3d):  ",
+		       clock_var);
+	      debug_ready_list (&ready);
+	    }
+
+	  if (!targetm.sched.use_dfa_pipeline_interface
+	      || !(*targetm.sched.use_dfa_pipeline_interface) ())
+	    {
+	      if (ready.n_ready == 0 || !can_issue_more
+		  || !(*current_sched_info->schedule_more_p) ())
+		break;
+	      insn = choose_ready (&ready);
+	      cost = actual_hazard (insn_unit (insn), insn, clock_var, 0);
+	    }
+	  else
+	    {
+	      if (ready.n_ready == 0 || !can_issue_more
+		  || state_dead_lock_p (curr_state)
+		  || !(*current_sched_info->schedule_more_p) ())
+		break;
+	      
+	      /* Select and remove the insn from the ready list.  */
+	      insn = choose_ready (&ready);
+	      
+	      memcpy (temp_state, curr_state, dfa_state_size);
+	      if (recog_memoized (insn) < 0)
+		{
+		  if (!first_cycle_insn_p
+		      && (GET_CODE (PATTERN (insn)) == ASM_INPUT
+			  || asm_noperands (PATTERN (insn)) >= 0))
+		    /* This is asm insn which is tryed 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
+		{
+		  cost = state_transition (temp_state, insn);
+
+		  if (targetm.sched.first_cycle_multipass_dfa_lookahead
+		      && targetm.sched.dfa_bubble)
+		    {
+		      if (cost == 0)
+			{
+			  int j;
+			  rtx bubble;
+			  
+			  for (j = 0;
+			       (bubble = (*targetm.sched.dfa_bubble) (j))
+				 != NULL_RTX;
+			       j++)
+			    {
+			      memcpy (temp_state, curr_state, dfa_state_size);
+			      
+			      if (state_transition (temp_state, bubble) < 0
+				  && state_transition (temp_state, insn) < 0)
+				break;
+			    }
+			  
+			  if (bubble != NULL_RTX)
+			    {
+			      if (insert_schedule_bubbles_p)
+				{
+				  rtx copy;
+				  
+				  copy = copy_rtx (PATTERN (bubble));
+				  emit_insn_after (copy, last_scheduled_insn);
+				  last_scheduled_insn
+				    = NEXT_INSN (last_scheduled_insn);
+				  INSN_CODE (last_scheduled_insn)
+				    = INSN_CODE (bubble);
+				  
+				  /* Annotate the same for the first insns
+				     scheduling by using mode.  */
+				  PUT_MODE (last_scheduled_insn,
+					    (clock_var > last_clock_var
+					     ? clock_var - last_clock_var
+					     : VOIDmode));
+				  last_clock_var = clock_var;
+				  
+				  if (sched_verbose >= 2)
+				    {
+				      fprintf (sched_dump,
+					       ";;\t\t--> scheduling bubble insn <<<%d>>>:reservation ",
+					       INSN_UID (last_scheduled_insn));
+				      
+				      if (recog_memoized (last_scheduled_insn)
+					  < 0)
+					fprintf (sched_dump, "nothing");
+				      else
+					print_reservation
+					  (sched_dump, last_scheduled_insn);
+				      
+				      fprintf (sched_dump, "\n");
+				    }
+				}
+			      cost = -1;
+			    }
+			}
+		    }
+
+		  if (cost < 0)
+		    cost = 0;
+		  else if (cost == 0)
+		    cost = 1;
+		}
+	    }
 
-      /* Issue insns from ready list.  */
-      while (ready.n_ready != 0
-	     && can_issue_more
-	     && (*current_sched_info->schedule_more_p) ())
-	{
-	  /* Select and remove the insn from the ready list.  */
-	  rtx insn = ready_remove_first (&ready);
-	  int cost = actual_hazard (insn_unit (insn), insn, clock_var, 0);
 
 	  if (cost >= 1)
 	    {
@@ -1760,6 +2174,10 @@ schedule_block (b, rgn_n_insns)
 
 	  last_scheduled_insn = move_insn (insn, last_scheduled_insn);
 
+	  if (targetm.sched.use_dfa_pipeline_interface
+	      && (*targetm.sched.use_dfa_pipeline_interface) ())
+	    memcpy (curr_state, temp_state, dfa_state_size);
+	    
 	  if (targetm.sched.variable_issue)
 	    can_issue_more =
 	      (*targetm.sched.variable_issue) (sched_dump, sched_verbose,
@@ -1770,6 +2188,8 @@ schedule_block (b, rgn_n_insns)
 	  schedule_insn (insn, &ready, clock_var);
 
 	next:
+	  first_cycle_insn_p = 0;
+
 	  if (targetm.sched.reorder2)
 	    {
 	      /* Sort the ready list based on priority.  */
@@ -1783,8 +2203,10 @@ schedule_block (b, rgn_n_insns)
 	    }
 	}
 
-      /* Debug info.  */
-      if (sched_verbose)
+      if ((!targetm.sched.use_dfa_pipeline_interface
+	   || !(*targetm.sched.use_dfa_pipeline_interface) ())
+	  && sched_verbose)
+	/* Debug info.  */
 	visualize_scheduled_insns (clock_var);
     }
 
@@ -1796,7 +2218,9 @@ schedule_block (b, rgn_n_insns)
     {
       fprintf (sched_dump, ";;\tReady list (final):  ");
       debug_ready_list (&ready);
-      print_block_visualization ("");
+      if (!targetm.sched.use_dfa_pipeline_interface
+	  || !(*targetm.sched.use_dfa_pipeline_interface) ())
+	print_block_visualization ("");
     }
 
   /* Sanity check -- queue must be empty now.  Meaningless if region has
@@ -1841,6 +2265,10 @@ schedule_block (b, rgn_n_insns)
   current_sched_info->tail = tail;
 
   free (ready.vec);
+
+  if (targetm.sched.use_dfa_pipeline_interface
+      && (*targetm.sched.use_dfa_pipeline_interface) ())
+    free (ready_try);
 }
 
 /* Set_priorities: compute priority of each insn in the block.  */
@@ -1882,6 +2310,7 @@ sched_init (dump_file)
 {
   int luid, b;
   rtx insn;
+  int i;
 
   /* Disable speculative loads in their presence if cc0 defined.  */
 #ifdef HAVE_cc0
@@ -1909,6 +2338,27 @@ sched_init (dump_file)
 
   h_i_d = (struct haifa_insn_data *) xcalloc (old_max_uid, sizeof (*h_i_d));
 
+  for (i = 0; i < old_max_uid; i++)
+    h_i_d [i].cost = -1;
+
+  if (targetm.sched.use_dfa_pipeline_interface
+      && (*targetm.sched.use_dfa_pipeline_interface) ())
+    {
+      if (targetm.sched.init_dfa_pre_cycle_insn)
+	(*targetm.sched.init_dfa_pre_cycle_insn) ();
+      
+      if (targetm.sched.init_dfa_post_cycle_insn)
+	(*targetm.sched.init_dfa_post_cycle_insn) ();
+      
+      if (targetm.sched.first_cycle_multipass_dfa_lookahead
+	  && targetm.sched.init_dfa_bubbles)
+	(*targetm.sched.init_dfa_bubbles) ();
+      
+      dfa_start ();
+      dfa_state_size = state_size ();
+      curr_state = xmalloc (dfa_state_size);
+    }
+
   h_i_d[0].luid = 0;
   luid = 1;
   for (b = 0; b < n_basic_blocks; b++)
@@ -1966,8 +2416,10 @@ sched_init (dump_file)
 	}
     }
 
-  /* Find units used in this function, for visualization.  */
-  if (sched_verbose)
+  if ((!targetm.sched.use_dfa_pipeline_interface
+       || !(*targetm.sched.use_dfa_pipeline_interface) ())
+      && sched_verbose)
+    /* Find units used in this function, for visualization.  */
     init_target_units ();
 
   /* ??? Add a NOTE after the last insn of the last basic block.  It is not
@@ -1997,6 +2449,13 @@ void
 sched_finish ()
 {
   free (h_i_d);
+
+  if (targetm.sched.use_dfa_pipeline_interface
+      && (*targetm.sched.use_dfa_pipeline_interface) ())
+    {
+      free (curr_state);
+      dfa_finish ();
+    }
   free_dependency_caches ();
   end_alias_analysis ();
   if (write_symbols != NO_DEBUG)