RFA: Patch to constrain maximal number of tries for incomplete dfa descriptions.

[Vladimir Makarov <vmakarov at redhat dot com>]

  The following patch solves PR/10160 for the main line reported by
Eric Botcazou.  The description of the problem is in comments for
max_lookahead_tries.

  The patch has been tested for hypersparc and itanium.  Is it ok to
commit?

Vlad


2003-06-05  Vladimir Makarov  <vmakarov@redhat.com>

        * haifa-sched.c (max_lookahead_tries): New variable.
        (max_issue): Check the number of tries.
        (sched_init): Calculate value of max_lookahead_tries.

Index: haifa-sched.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/haifa-sched.c,v
retrieving revision 1.222
diff -c -p -r1.222 haifa-sched.c
*** haifa-sched.c	15 Mar 2003 13:43:29 -0000	1.222
--- haifa-sched.c	5 Jun 2003 18:52:43 -0000
*************** static struct choice_entry *choice_stack
*** 1982,1987 ****
--- 1982,1998 ----
     processors state.  */
  static int cycle_issued_insns;
  
+ /* The following variable value is maximal number of tries of issuing
+    insns for the first cycle multipass insn scheduling.  We define
+    this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE).  We would not
+    need this constraint if all real insns (with non-negative codes)
+    had reservations because in this case the algorithm complexity is
+    O(DFA_LOOKAHEAD**ISSUE_RATE).  Unfortunately, the dfa descriptions
+    might be incomplete and such insn might occur.  For such
+    descriptions, the complexity of algorithm (without the constraint)
+    could achieve DFA_LOOKAHEAD ** N , where N is the queue length.  */
+ static int max_lookahead_tries;
+ 
  /* 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 first insn in READY).  To
*************** max_issue (ready, index)
*** 1995,2001 ****
    struct ready_list *ready;
    int *index;
  {
!   int n, i, all, n_ready, lookahead, best, delay;
    struct choice_entry *top;
    rtx insn;
  
--- 2006,2012 ----
    struct ready_list *ready;
    int *index;
  {
!   int n, i, all, n_ready, lookahead, best, delay, tries_num;
    struct choice_entry *top;
    rtx insn;
  
*************** max_issue (ready, index)
*** 2010,2015 ****
--- 2021,2027 ----
      if (!ready_try [i])
        all++;
    i = 0;
+   tries_num = 0;
    for (;;)
      {
        if (top->rest == 0 || i >= n_ready)
*************** max_issue (ready, index)
*** 2030,2035 ****
--- 2042,2050 ----
  	}
        else if (!ready_try [i])
  	{
+ 	  tries_num++;
+ 	  if (tries_num > max_lookahead_tries)
+ 	    break;
  	  insn = ready_element (ready, i);
  	  delay = state_transition (curr_state, insn);
  	  if (delay < 0)
*************** sched_init (dump_file)
*** 2631,2636 ****
--- 2646,2659 ----
        dfa_start ();
        dfa_state_size = state_size ();
        curr_state = xmalloc (dfa_state_size);
+       if (targetm.sched.first_cycle_multipass_dfa_lookahead
+ 	  && (*targetm.sched.first_cycle_multipass_dfa_lookahead) () > 0)
+ 	{
+ 	  max_lookahead_tries = 100;
+ 	  for (i = 0; i < issue_rate; i++)
+ 	    max_lookahead_tries
+ 	      *= (*targetm.sched.first_cycle_multipass_dfa_lookahead) ();
+ 	}
      }
  
    h_i_d[0].luid = 0;