scheduling patch

[amacleod at cygnus dot com]

This patch limits the number of elements that last_pending_memory_flush
can have. Without this, large functions with few calls or 
barriers can generate lists containing many 1000's of anti dependancies
in when using the extended basic block scheduler.

Generally the compiler either uses all available memory, or runs for 
way too long without this patch.

This cleans up the timeout in testcase gcc.c-torture/compile/20001226-1.c
on ia64, and bootstraps.

OK to check in?, and should it also go to the 3.0 branch?

Andrew

	* params.def (PARAM_MAX_PENDING_MEMORY_FLUSH): Add parameter to 
	limit length of pending memory flush list.
	* sched-int.h  (struct deps): Add pending_flush_length field.
	* sched-deps.c (flush_pending_lists): last_pending_memory_flush now
	has 1 element in it.
	(sched_analyze): After a jump, if the pending memory flush list is too
	large, flush the pending lists.
	(init_deps): Initialize pending_flush_length to 0.

Index: params.def
===================================================================
RCS file: /cvs/cvsfiles/devo/gcc/params.def,v
retrieving revision 1.2
diff -c -p -r1.2 params.def
*** params.def	2001/04/30 22:37:03	1.2
--- params.def	2001/07/19 14:04:37
*************** DEFPARAM(PARAM_MAX_GCSE_MEMORY,
*** 73,78 ****
--- 73,88 ----
  	 "The maximum amount of memory to be allocated by GCSE",
  	 50 * 1024 * 1024)
  
+ /* This parameter limits the number of branch elements that the 
+    scheduler will track anti-dependancies through without resetting
+    the tracking mechanism.  Large functions with few calls or barriers 
+    can generate lists containing many 1000's of dependancies.  Generally 
+    the compiler either uses all available memory, or runs for far too long.  */
+ DEFPARAM(PARAM_MAX_PENDING_MEMORY_FLUSH,
+ 	 "max-pending-memory-flush",
+ 	 "The number of branches to track anti-dependancies through",
+ 	 12)
+ 
  /*
  Local variables:
  mode:c
Index: sched-int.h
===================================================================
RCS file: /cvs/cvsfiles/devo/gcc/sched-int.h,v
retrieving revision 1.6.20.1
diff -c -p -r1.6.20.1 sched-int.h
*** sched-int.h	2001/06/19 04:43:10	1.6.20.1
--- sched-int.h	2001/07/19 14:04:38
*************** struct deps
*** 107,112 ****
--- 107,116 ----
       a function of the length of these pending lists.  */
    int pending_lists_length;
  
+   /* Length of the pending memory flush list. Large functions with no
+      calls may build up extremely large lists.  */
+   int pending_flush_length;
+ 
    /* The last insn upon which all memory references must depend.
       This is an insn which flushed the pending lists, creating a dependency
       between it and all previously pending memory references.  This creates
Index: sched-deps.c
===================================================================
RCS file: /cvs/cvsfiles/devo/gcc/sched-deps.c,v
retrieving revision 1.5
diff -c -p -r1.5 sched-deps.c
*** sched-deps.c	2001/05/23 12:45:40	1.5
--- sched-deps.c	2001/07/19 14:04:39
*************** the Free Software Foundation, 59 Temple 
*** 38,43 ****
--- 38,44 ----
  #include "toplev.h"
  #include "recog.h"
  #include "sched-int.h"
+ #include "params.h"
  
  extern char *reg_known_equiv_p;
  extern rtx *reg_known_value;
*************** flush_pending_lists (deps, insn, only_wr
*** 532,537 ****
--- 533,539 ----
  
    free_INSN_LIST_list (&deps->last_pending_memory_flush);
    deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
+   deps->pending_flush_length = 1;
  }
  
  /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
*************** sched_analyze (deps, head, tail)
*** 1242,1249 ****
  	  /* Make each JUMP_INSN a scheduling barrier for memory
               references.  */
  	  if (GET_CODE (insn) == JUMP_INSN)
! 	    deps->last_pending_memory_flush
! 	      = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
  	  sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
  	  loop_notes = 0;
  	}
--- 1244,1257 ----
  	  /* Make each JUMP_INSN a scheduling barrier for memory
               references.  */
  	  if (GET_CODE (insn) == JUMP_INSN)
! 	    {
! 	      /* Keep the list a reasonable size.  */
! 	      if (deps->pending_flush_length++ > PARAM_MAX_PENDING_MEMORY_FLUSH)
! 		flush_pending_lists (deps, insn, 0);
! 	      else
! 		deps->last_pending_memory_flush
! 		  = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
! 	    }
  	  sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
  	  loop_notes = 0;
  	}
*************** init_deps (deps)
*** 1469,1474 ****
--- 1477,1483 ----
    deps->pending_write_insns = 0;
    deps->pending_write_mems = 0;
    deps->pending_lists_length = 0;
+   deps->pending_flush_length = 0;
    deps->last_pending_memory_flush = 0;
    deps->last_function_call = 0;
    deps->in_post_call_group_p = 0;