2003-01-09 Vladimir Makarov <vmakarov@redhat.com>

	Merging changes from itanium-sched-branch:


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

1 files changed, 220 insertions, 120 deletions

diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
index 5a0c208b219..046abc34423 100644
--- a/gcc/haifa-sched.c
+++ b/gcc/haifa-sched.c
@@ -320,6 +320,7 @@ static int rank_for_schedule PARAMS ((const PTR, const PTR));
 static void swap_sort PARAMS ((rtx *, int));
 static void queue_insn PARAMS ((rtx, int));
 static void schedule_insn PARAMS ((rtx, struct ready_list *, int));
+static int find_set_reg_weight PARAMS ((rtx));
 static void find_insn_reg_weight PARAMS ((int));
 static void adjust_priority PARAMS ((rtx));
 static void advance_one_cycle PARAMS ((void));
@@ -366,7 +367,7 @@ static rtx move_insn PARAMS ((rtx, rtx));
    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 int max_issue PARAMS ((struct ready_list *, int *));
 
 static rtx choose_ready PARAMS ((struct ready_list *));
 
@@ -853,6 +854,7 @@ rank_for_schedule (x, y)
 
   /* Prefer insn with higher priority.  */
   priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
+
   if (priority_val)
     return priority_val;
 
@@ -1017,8 +1019,10 @@ ready_element (ready, index)
      struct ready_list *ready;
      int index;
 {
+#ifdef ENABLE_CHECKING
   if (ready->n_ready == 0 || index >= ready->n_ready)
     abort ();
+#endif
   return ready->vec[ready->first - index];
 }
 
@@ -1195,11 +1199,12 @@ 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 (issue_rate > 1
       && GET_CODE (PATTERN (insn)) != USE
       && GET_CODE (PATTERN (insn)) != CLOBBER)
     {
-      PUT_MODE (insn, clock > last_clock_var ? TImode : VOIDmode);
+      if (reload_completed)
+	PUT_MODE (insn, clock > last_clock_var ? TImode : VOIDmode);
       last_clock_var = clock;
     }
 }
@@ -1536,6 +1541,32 @@ rm_other_notes (head, tail)
 
 /* Functions for computation of registers live/usage info.  */
 
+/* This function looks for a new register being defined.
+   If the destination register is already used by the source,
+   a new register is not needed. */
+
+static int
+find_set_reg_weight (x)
+    rtx x;
+{
+  if (GET_CODE (x) == CLOBBER
+      && register_operand (SET_DEST (x), VOIDmode))
+    return 1;
+  if (GET_CODE (x) == SET
+      && register_operand (SET_DEST (x), VOIDmode))
+    {
+      if (GET_CODE (SET_DEST (x)) == REG)
+	{
+	  if (!reg_mentioned_p (SET_DEST (x), SET_SRC (x)))
+	    return 1;
+	  else
+	    return 0;
+	}
+      return 1;
+    }
+  return 0;
+}
+
 /* Calculate INSN_REG_WEIGHT for all insns of a block.  */
 
 static void
@@ -1558,21 +1589,16 @@ find_insn_reg_weight (b)
 
       /* Increment weight for each register born here.  */
       x = PATTERN (insn);
-      if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
-	  && register_operand (SET_DEST (x), VOIDmode))
-	reg_weight++;
-      else if (GET_CODE (x) == PARALLEL)
-	{
-	  int j;
-	  for (j = XVECLEN (x, 0) - 1; j >= 0; j--)
-	    {
-	      x = XVECEXP (PATTERN (insn), 0, j);
-	      if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
-		  && register_operand (SET_DEST (x), VOIDmode))
-		reg_weight++;
-	    }
-	}
-
+      reg_weight += find_set_reg_weight (x);
+      if (GET_CODE (x) == PARALLEL)
+ 	{
+ 	  int j;
+ 	  for (j = XVECLEN (x, 0) - 1; j >= 0; j--)
+ 	    {
+ 	      x = XVECEXP (PATTERN (insn), 0, j);
+	      reg_weight += find_set_reg_weight (x);
+ 	    }
+ 	}
       /* Decrement weight for each register that dies here.  */
       for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
 	{
@@ -1743,25 +1769,6 @@ move_insn (insn, last)
 {
   rtx retval = NULL;
 
-  /* If INSN has SCHED_GROUP_P set, then issue it and any other
-     insns with SCHED_GROUP_P set first.  */
-  while (SCHED_GROUP_P (insn))
-    {
-      rtx prev = PREV_INSN (insn);
-
-      /* Move a SCHED_GROUP_P insn.  */
-      move_insn1 (insn, last);
-      /* If this is the first call to reemit_notes, then record
-	 its return value.  */
-      if (retval == NULL_RTX)
-	retval = reemit_notes (insn, insn);
-      else
-	reemit_notes (insn, insn);
-      /* Consume SCHED_GROUP_P flag.  */
-      SCHED_GROUP_P (insn) = 0;
-      insn = prev;
-    }
-
   /* Now move the first non SCHED_GROUP_P insn.  */
   move_insn1 (insn, last);
 
@@ -1772,90 +1779,109 @@ move_insn (insn, last)
   else
     reemit_notes (insn, insn);
 
+  SCHED_GROUP_P (insn) = 0;
+
   return retval;
 }
 
+/* The following structure describe an entry of the stack of choices.  */
+struct choice_entry
+{
+  /* Ordinal number of the issued insn in the ready queue.  */
+  int index;
+  /* The number of the rest insns whose issues we should try.  */
+  int rest;
+  /* The number of issued essential insns.  */
+  int n;
+  /* State after issuing the insn.  */
+  state_t state;
+};
+
+/* The following array is used to implement a stack of choices used in
+   function max_issue.  */
+static struct choice_entry *choice_stack;
+
+/* The following variable value is number of essential insns issued on
+   the current cycle.  An insn is essential one if it changes the
+   processors state.  */
+static int cycle_issued_insns;
+
 /* 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
+   insns is insns with the best rank (the first 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
+   insns are already issued in this try.  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;
+max_issue (ready, index)
+  struct ready_list *ready;
+  int *index;
 {
-  int i, best, n, temp_index, delay;
-  state_t temp_state;
+  int n, i, all, n_ready, lookahead, best, delay;
+  struct choice_entry *top;
   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);
+  lookahead = (*targetm.sched.first_cycle_multipass_dfa_lookahead) ();
   best = 0;
-  
-  for (i = 0; i < ready->n_ready; i++)
+  memcpy (choice_stack->state, curr_state, dfa_state_size);
+  top = choice_stack;
+  top->rest = lookahead;
+  top->n = 0;
+  n_ready = ready->n_ready;
+  for (all = i = 0; i < 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;
-      }
-  
+      all++;
+  i = 0;
+  for (;;)
+    {
+      if (top->rest == 0 || i >= n_ready)
+	{
+	  if (top == choice_stack)
+	    break;
+	  if (best < top - choice_stack && ready_try [0])
+	    {
+	      best = top - choice_stack;
+	      *index = choice_stack [1].index;
+	      if (top->n == issue_rate - cycle_issued_insns || best == all)
+		break;
+	    }
+	  i = top->index;
+	  ready_try [i] = 0;
+	  top--;
+	  memcpy (curr_state, top->state, dfa_state_size);
+	}
+      else if (!ready_try [i])
+	{
+	  insn = ready_element (ready, i);
+	  delay = state_transition (curr_state, insn);
+	  if (delay < 0)
+	    {
+	      if (state_dead_lock_p (curr_state))
+		top->rest = 0;
+	      else
+		top->rest--;
+	      n = top->n;
+	      if (memcmp (top->state, curr_state, dfa_state_size) != 0)
+		n++;
+	      top++;
+	      top->rest = lookahead;
+	      top->index = i;
+	      top->n = n;
+	      memcpy (top->state, curr_state, dfa_state_size);
+	      ready_try [i] = 1;
+	      i = -1;
+	    }
+	}
+      i++;
+    }
+  while (top != choice_stack)
+    {
+      ready_try [top->index] = 0;
+      top--;
+    }
+  memcpy (curr_state, choice_stack->state, dfa_state_size);
   return best;
 }
 
@@ -1873,9 +1899,21 @@ choose_ready (ready)
   else
     {
       /* Try to choose the better insn.  */
-      int index;
+      int index, i;
+      rtx insn;
 
-      if (max_issue (ready, curr_state, &index) == 0)
+      insn = ready_element (ready, 0);
+      if (INSN_CODE (insn) < 0)
+	return ready_remove_first (ready);
+      for (i = 1; i < ready->n_ready; i++)
+	{
+	  insn = ready_element (ready, i);
+	  ready_try [i]
+	    = (INSN_CODE (insn) < 0
+	       || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard
+		   && !(*targetm.sched.first_cycle_multipass_dfa_lookahead_guard) (insn)));
+	}
+      if (max_issue (ready, &index) == 0)
 	return ready_remove_first (ready);
       else
 	return ready_remove (ready, index);
@@ -1903,9 +1941,10 @@ schedule_block (b, rgn_n_insns)
      int rgn_n_insns;
 {
   struct ready_list ready;
-  int first_cycle_insn_p;
+  int i, first_cycle_insn_p;
   int can_issue_more;
   state_t temp_state = NULL;  /* It is used for multipass scheduling.  */
+  int sort_p;
 
   /* Head/tail info for this block.  */
   rtx prev_head = current_sched_info->prev_head;
@@ -1957,6 +1996,11 @@ schedule_block (b, rgn_n_insns)
       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));
+      choice_stack
+	= (struct choice_entry *) xmalloc ((rgn_n_insns + 1)
+					   * sizeof (struct choice_entry));
+      for (i = 0; i <= rgn_n_insns; i++)
+	choice_stack[i].state = (state_t) xmalloc (dfa_state_size);
     }
 
   (*current_sched_info->init_ready_list) (&ready);
@@ -1985,6 +2029,7 @@ schedule_block (b, rgn_n_insns)
   /* Start just before the beginning of time.  */
   clock_var = -1;
 
+  sort_p = TRUE;
   /* Loop until all the insns in BB are scheduled.  */
   while ((*current_sched_info->schedule_more_p) ())
     {
@@ -2007,8 +2052,17 @@ schedule_block (b, rgn_n_insns)
 	  debug_ready_list (&ready);
 	}
 
-      /* Sort the ready list based on priority.  */
-      ready_sort (&ready);
+      if (sort_p)
+	{
+	  /* Sort the ready list based on priority.  */
+	  ready_sort (&ready);
+	  
+	  if (sched_verbose >= 2)
+	    {
+	      fprintf (sched_dump, ";;\t\tReady list after ready_sort:  ");
+	      debug_ready_list (&ready);
+	    }
+	}
 
       /* Allow the target to reorder the list, typically for
 	 better instruction bundling.  */
@@ -2021,6 +2075,7 @@ schedule_block (b, rgn_n_insns)
 	can_issue_more = issue_rate;
 
       first_cycle_insn_p = 1;
+      cycle_issued_insns = 0;
       for (;;)
 	{
 	  rtx insn;
@@ -2050,8 +2105,21 @@ schedule_block (b, rgn_n_insns)
 		break;
 	      
 	      /* Select and remove the insn from the ready list.  */
-	      insn = choose_ready (&ready);
+	      if (sort_p)
+		insn = choose_ready (&ready);
+	      else
+		insn = ready_remove_first (&ready);
 	      
+	      if (targetm.sched.dfa_new_cycle
+		  && (*targetm.sched.dfa_new_cycle) (sched_dump, sched_verbose,
+						     insn, last_clock_var,
+						     clock_var, &sort_p))
+		{
+		  ready_add (&ready, insn);
+		  break;
+		}
+	    
+	      sort_p = TRUE;
 	      memcpy (temp_state, curr_state, dfa_state_size);
 	      if (recog_memoized (insn) < 0)
 		{
@@ -2155,7 +2223,11 @@ schedule_block (b, rgn_n_insns)
 
 	  if (targetm.sched.use_dfa_pipeline_interface
 	      && (*targetm.sched.use_dfa_pipeline_interface) ())
-	    memcpy (curr_state, temp_state, dfa_state_size);
+	    {
+	      if (memcmp (curr_state, temp_state, dfa_state_size) != 0)
+		cycle_issued_insns++;
+	      memcpy (curr_state, temp_state, dfa_state_size);
+	    }
 	    
 	  if (targetm.sched.variable_issue)
 	    can_issue_more =
@@ -2172,13 +2244,16 @@ schedule_block (b, rgn_n_insns)
 	next:
 	  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. */
+	  if (ready.n_ready > 0)
+	    ready_sort (&ready);
+
 	  if (targetm.sched.reorder2)
 	    {
-	      /* Sort the ready list based on priority.  */
-	      if (ready.n_ready > 0)
-		ready_sort (&ready);
 	      can_issue_more =
-		(*targetm.sched.reorder2) (sched_dump,sched_verbose,
+		(*targetm.sched.reorder2) (sched_dump, sched_verbose,
 					   ready.n_ready
 					   ? ready_lastpos (&ready) : NULL,
 					   &ready.n_ready, clock_var);
@@ -2214,6 +2289,27 @@ schedule_block (b, rgn_n_insns)
   head = NEXT_INSN (prev_head);
   tail = last_scheduled_insn;
 
+  if (!reload_completed)
+    {
+      rtx insn, link, next;
+      
+      /* INSN_TICK (minimum clock tick at which the insn becomes
+         ready) may be not correct for the insn in the subsequent
+         blocks of the region.  We should use a correct value of
+         `clock_var' or modify INSN_TICK.  It is better to keep
+         clock_var value equal to 0 at the start of a basic block.
+         Therefore we modify INSN_TICK here.  */
+      for (insn = head; insn != tail; insn = NEXT_INSN (insn))
+	if (INSN_P (insn))
+	  {
+	    for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
+	      {
+		next = XEXP (link, 0);
+		INSN_TICK (next) -= clock_var;
+	      }
+	  }
+    }
+
   /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
      previously found among the insns.  Insert them at the beginning
      of the insns.  */
@@ -2250,7 +2346,12 @@ schedule_block (b, rgn_n_insns)
 
   if (targetm.sched.use_dfa_pipeline_interface
       && (*targetm.sched.use_dfa_pipeline_interface) ())
-    free (ready_try);
+    {
+      free (ready_try);
+      for (i = 0; i <= rgn_n_insns; i++)
+	free (choice_stack [i].state);
+      free (choice_stack);
+    }
 }
 
 /* Set_priorities: compute priority of each insn in the block.  */
@@ -2275,8 +2376,7 @@ set_priorities (head, tail)
       if (GET_CODE (insn) == NOTE)
 	continue;
 
-      if (!(SCHED_GROUP_P (insn)))
-	n_insn++;
+      n_insn++;
       (void) priority (insn);
     }