haifa tweak

[Jeffrey A Law <law at cygnus dot com>]

See recent discussion on the main list.  Avoid unnecessary work/memory
allocation when the cache is unlikely to be effective.


        * haifa-sched.c (add_dependence): Only check/update the cache
        if it exists.
        (remove_dependence): Likewise.
        (schedule_insns): Only create the true_dependency_cache if the
        average number of instructions in a basic block is very large.

Index: haifa-sched.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/haifa-sched.c,v
retrieving revision 1.117
diff -c -3 -p -r1.117 haifa-sched.c
*** haifa-sched.c	1999/10/17 06:28:22	1.117
--- haifa-sched.c	1999/10/17 21:25:55
*************** static int *insn_luid;
*** 248,255 ****
  #define INSN_LUID(INSN) (insn_luid[INSN_UID (INSN)])
  
  /* To speed up the test for duplicate dependency links we keep a record
!    of true dependencies created by add_dependence.
  
     Each insn has an associated bitmap for its dependencies.  Each bitmap
     has enough entries to represent a dependency on any other insn in the
     insn chain.  */
--- 248,261 ----
  #define INSN_LUID(INSN) (insn_luid[INSN_UID (INSN)])
  
  /* To speed up the test for duplicate dependency links we keep a record
!    of true dependencies created by add_dependence when the average number
!    of instructions in a basic block is very large.
  
+    Studies have shown that there is typically around 5 instructions between
+    branches for typical C code.  So we can make a guess that the average
+    basic block is approximately 5 instructions long; we will choose 100X
+    the average size as a very large basic block.
+   
     Each insn has an associated bitmap for its dependencies.  Each bitmap
     has enough entries to represent a dependency on any other insn in the
     insn chain.  */
*************** add_dependence (insn, elem, dep_type)
*** 794,800 ****
    /* If we already have a true dependency for ELEM, then we do not
       need to do anything.  Avoiding the list walk below can cut
       compile times dramatically for some code.  */
!   if (TEST_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)))
      return;
  
    /* Check that we don't already have this dependence.  */
--- 800,807 ----
    /* If we already have a true dependency for ELEM, then we do not
       need to do anything.  Avoiding the list walk below can cut
       compile times dramatically for some code.  */
!   if (true_dependency_cache
!       && TEST_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID 
(elem)))
      return;
  
    /* Check that we don't already have this dependence.  */
*************** add_dependence (insn, elem, dep_type)
*** 808,814 ****
  
  	/* If we are adding a true dependency to INSN's LOG_LINKs, then
  	   note that in the bitmap cache of true dependency information.  */
! 	if ((int)dep_type == 0)
  	  SET_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
  	return;
        }
--- 815,821 ----
  
  	/* If we are adding a true dependency to INSN's LOG_LINKs, then
  	   note that in the bitmap cache of true dependency information.  */
! 	if ((int)dep_type == 0 && true_dependency_cache)
  	  SET_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
  	return;
        }
*************** remove_dependence (insn, elem)
*** 844,850 ****
  
  	  /* If we are removing a true dependency from the LOG_LINKS list,
  	     make sure to remove it from the cache too.  */
! 	  if (REG_NOTE_KIND (link) == 0)
  	    RESET_BIT (true_dependency_cache[INSN_LUID (insn)],
  		       INSN_LUID (elem));
  
--- 851,857 ----
  
  	  /* If we are removing a true dependency from the LOG_LINKS list,
  	     make sure to remove it from the cache too.  */
! 	  if (REG_NOTE_KIND (link) == 0 && true_dependency_cache)
  	    RESET_BIT (true_dependency_cache[INSN_LUID (insn)],
  		       INSN_LUID (elem));
  
*************** schedule_insns (dump_file)
*** 6876,6884 ****
    
    /* ?!? We could save some memory by computing a per-region luid mapping
       which could reduce both the number of vectors in the cache and the size
!      of each vector.  */
!   true_dependency_cache = sbitmap_vector_alloc (luid, luid);
!   sbitmap_vector_zero (true_dependency_cache, luid);
  
    nr_regions = 0;
    rgn_table = (region *) alloca ((n_basic_blocks) * sizeof (region));
--- 6883,6897 ----
    
    /* ?!? We could save some memory by computing a per-region luid mapping
       which could reduce both the number of vectors in the cache and the size
!      of each vector.  Instead we just avoid the cache entirely unless the
!      average number of instructions in a basic block is very high.  See
!      the comment before the declaration of true_dependency_cache for
!      what we consider "very high".  */
!   if (luid / n_basic_blocks > 100 * 5)
!     {
!       true_dependency_cache = sbitmap_vector_alloc (luid, luid);
!       sbitmap_vector_zero (true_dependency_cache, luid);
!     }
  
    nr_regions = 0;
    rgn_table = (region *) alloca ((n_basic_blocks) * sizeof (region));
*************** schedule_insns (dump_file)
*** 7047,7053 ****
        fprintf (dump, "\n\n");
      }
  
!   free (true_dependency_cache);
    free (cant_move);
    free (fed_by_spec_load);
    free (is_load_insn);
--- 7060,7070 ----
        fprintf (dump, "\n\n");
      }
  
!   if (true_dependency_cache)
!     {
!       free (true_dependency_cache);
!       true_depdency_cache = NULL;
!     }
    free (cant_move);
    free (fed_by_spec_load);
    free (is_load_insn);