haifa bug, band-aid

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

As some of you know, haifa implemented (poorly) a number of basic concepts
that were missing from GCC (or which haifa was unaware of).  One of those
concepts was a general bitset implementation.

haifa got a number of bitset things wrong over the years that I've corrected
and this one is the final straw.  I've got changes (untested) that remove all
broken haifa bitset code that I'll be submitting soon.  Until then this
fixes non-deterministic behavior in the scheduler.

Basically it it rare for the number of items in a bitset to be precisely the
size of a HOST_WIDE_INT.  As a result there are usually bits on the end of
the bitset which have uninitialized values.

Most of the time those values are zero or the nonzero value is not important;
however, haifa wants to turn a bitset into a bitlist for certain operations.

The conversion from bitset to bitlist was examining those uninitialized
values, finding some bits were set and adding bogus members to the generated
bit list.

Those bogus members on the bitlist caused major problems in this code:

         for (j = 0; j < el.nr_members; bblst_last++, j++)
            bblst_table[bblst_last] =
              TO_BLOCK (rgn_edges[el.first_member[j]]);

First, el.nr_members was way too high -- this caused a series of out of bounds
reads in the TO_BLOCK (rgn_edges[el.first_member[j]]]) expression.  One of the
was so out of bounds it caused segfaults :(

The testcase wasn't really reducible to anything useful.  No great surprise
given the nature of this bug.

	* Band-aid until haifa's bitset implementation is nuked.
	* haifa-sched.c (extract_bitlst): New parameter for size of the
	bitset in bits.  All callers changed.  Avoid looking at undefined
	bits in the bitset.
	(edgeset_bitsize): New variable.
	(schedule_region): Initialize edgeset_bitsize.
       
Index: haifa-sched.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/haifa-sched.c,v
retrieving revision 1.136
diff -c -3 -p -r1.136 haifa-sched.c
*** haifa-sched.c	2000/01/10 23:48:02	1.136
--- haifa-sched.c	2000/01/11 12:40:36
*************** static int bitlst_table_size;
*** 594,600 ****
  static int *bitlst_table;
  
  static char bitset_member PROTO ((bitset, int, int));
! static void extract_bitlst PROTO ((bitset, int, bitlst *));
  
  /* Target info declarations.
  
--- 594,600 ----
  static int *bitlst_table;
  
  static char bitset_member PROTO ((bitset, int, int));
! static void extract_bitlst PROTO ((bitset, int, int, bitlst *));
  
  /* Target info declarations.
  
*************** static int *rgn_edges;
*** 680,685 ****
--- 680,688 ----
  /* Number of words in an edgeset.  */
  static int edgeset_size;
  
+ /* Number of bits in an edgeset.  */
+ static int edgeset_bitsize;
+ 
  /* Mapping from each edge in the graph to its number in the rgn.  */
  static int *edge_to_bit;
  #define EDGE_TO_BIT(edge) (edge_to_bit[edge])
*************** bitset_member (set, index, len)
*** 1216,1222 ****
  /* Translate a bit-set SET to a list BL of the bit-set members.  */
  
  static void
! extract_bitlst (set, len, bl)
       bitset set;
       int len;
       bitlst *bl;
--- 1219,1225 ----
  /* Translate a bit-set SET to a list BL of the bit-set members.  */
  
  static void
! extract_bitlst (set, len, bitlen, bl)
       bitset set;
       int len;
       bitlst *bl;
*************** extract_bitlst (set, len, bl)
*** 1230,1240 ****
    bl->first_member = &bitlst_table[bitlst_table_last];
    bl->nr_members = 0;
  
    for (i = 0; i < len; i++)
      {
        word = set[i];
        offset = i * HOST_BITS_PER_WIDE_INT;
!       for (j = 0; word; j++)
  	{
  	  if (word & 1)
  	    {
--- 1233,1247 ----
    bl->first_member = &bitlst_table[bitlst_table_last];
    bl->nr_members = 0;
  
+   /* Iterate over each word in the bitset.  */
    for (i = 0; i < len; i++)
      {
        word = set[i];
        offset = i * HOST_BITS_PER_WIDE_INT;
! 
!       /* Iterate over each bit in the word, but do not
! 	 go beyond the end of the defined bits.  */
!       for (j = 0; offset < bitlen && word; j++)
  	{
  	  if (word & 1)
  	    {
*************** split_edges (bb_src, bb_trg, bl)
*** 1884,1895 ****
       edgelst *bl;
  {
    int es = edgeset_size;
!   edgeset src = (edgeset) xmalloc (es * sizeof (HOST_WIDE_INT));
  
    while (es--)
      src[es] = (pot_split[bb_src])[es];
    BITSET_DIFFER (src, pot_split[bb_trg], edgeset_size);
!   extract_bitlst (src, edgeset_size, bl);
    free (src);
  }
  
--- 1891,1902 ----
       edgelst *bl;
  {
    int es = edgeset_size;
!   edgeset src = (edgeset) xcalloc (es, sizeof (HOST_WIDE_INT));
  
    while (es--)
      src[es] = (pot_split[bb_src])[es];
    BITSET_DIFFER (src, pot_split[bb_trg], edgeset_size);
!   extract_bitlst (src, es, edgeset_bitsize, bl);
    free (src);
  }
  
*************** schedule_region (rgn)
*** 6673,6678 ****
--- 6680,6686 ----
  
        /* Split edges.  */
        edgeset_size = rgn_nr_edges / HOST_BITS_PER_WIDE_INT + 1;
+       edgeset_bitsize = rgn_nr_edges;
        pot_split = (edgeset *) xmalloc (current_nr_blocks * sizeof (edgeset));
        ancestor_edges 
  	= (edgeset *) xmalloc (current_nr_blocks * sizeof (edgeset));