[PATCH] Rework description of DFA scheduler's max_issue()

[Eric Botcazou <ebotcazou at libertysurf dot fr>]

Hi again Vlad,

In the process of investigating PR bootstrap/10835 (which I've narrowed down 
to an overly optimistic DFA scheduler description for HyperSPARC), I've 
stumbled upon max_issue(), which is a very interesting beast :-)

(And now I remember that you indirectly mentioned it in the course of the 
discussion of PR optimization/10160, the infamous compile time explosion bug 
caused by the tree inliner on SPARC).

The in-file description of max_issue() is a bit terse and, more importantly, 
it doesn't mention that the function can exhibit exponential behaviour in 
case of a broken scheduler description. Therefore I've reworked it. And in 
the process I've also renamed the 'best' variable into 'max' because 'best' 
is really misleading (it has nothing to do with the best insn).

(Of course, PR bootstrap/10835 is an example of the exponential behaviour 
with MAX_LOOKAHEAD==3 and n==20).

Compiled on i586-redhat-linux-gnu. I'm requesting approval for mainline and 
3.3 branch as the first part of the fix for the aforementioned PR which is 
of course a regression from GCC 3.2.x.

-- 
Eric Botcazou


2003-05-31  Eric Botcazou  <ebotcazou@libertysurf.fr>

	PR bootstrap/10835
	* haifa-sched.c (max_issue): Rework description and mention
	worst case behaviour. Rename 'best' automatic variable into 'max'.

Index: haifa-sched.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/haifa-sched.c,v
retrieving revision 1.213
diff -u -p -r1.213 haifa-sched.c
--- haifa-sched.c	28 Sep 2002 15:29:34 -0000	1.213
+++ haifa-sched.c	31 May 2003 12:32:47 -0000
@@ -1773,15 +1773,26 @@ 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.  */
+/* Return the maximal (or close to maximal) number of insns that can be
+   issued on the same cycle as the highest priority insn in the current
+   processor state and the index of an insn that will allow to reach
+   this maximal number if issued first.
+
+   We perform an exhaustive search of sequences of insns containing the
+   highest priority insn by using a recursive algorithm, looking at each
+   step into at most MAX_LOOKAHEAD insns past the highest priority insn
+   that have not been included in the sequence currently being built.
+   The algorithm is therefore O(MAX_LOOKAHEAD**(n-MAX_LOOKAHEAD)), for
+   n the number of insns ready to be issued, in the worst case which
+   corresponds to the unrealistic situation of n insns that cost nothing.
+
+   READY is the current queue of insns ready to be issued.  STATE is the
+   current processor state.  If the function returns nonzero, INDEX will
+   contain the index of an insn that has the property mentioned above.
+   We use the global array READY_TRY to record which insns have already
+   been included in the sequence currently being built.
+
+   This function is used only for first cycle multipass scheduling.  */
 
 static int
 max_issue (ready, state, index)
@@ -1789,7 +1800,7 @@ max_issue (ready, state, index)
      state_t state;
      int *index;
 {
-  int i, best, n, temp_index, delay;
+  int i, max, n, temp_index, delay;
   state_t temp_state;
   rtx insn;
   int max_lookahead = (*targetm.sched.first_cycle_multipass_dfa_lookahead) ();
@@ -1798,7 +1809,7 @@ max_issue (ready, state, index)
     return 0;
 
   temp_state = alloca (dfa_state_size);
-  best = 0;
+  max = 0;
   
   for (i = 0; i < ready->n_ready; i++)
     if (!ready_try [i])
@@ -1846,15 +1857,15 @@ max_issue (ready, state, index)
 	if (n > 0 || ready_try[0])
 	  n += 1;
 
-	if (best < n)
+	if (max < n)
 	  {
-	    best = n;
+	    max = n;
 	    *index = i;
 	  }
 	ready_try [i] = 0;
       }
   
-  return best;
+  return max;
 }
 
 /* The following function chooses insn from READY and modifies