PATCH: libgcc2/frame.c

[Nathan Sidwell <nathan at acm dot org>]

Hi,
here's a patch to frame.c which fixes the bug report at
http://egcs.cygnus.com/ml/gcc-bugs/1999-08/msg00918.html. fde_split
makes use of the gcc variable sized array extension to hold a chain of
linear FDE's. This can make the stack frame rather large, which is bad,
and doubly so for multithreaded applications. The patch makes use of
the erratic array to hold this chain, during its generation, and then
fills the erratic array with unordered FDE's in a final pass. The
splitting algorithm is otherwise unchanged. Static variable, MARKER, is
used in place of (size_t)-1. The patch relys on a `struct fde **'
having the same size as a `struct fde *'. During chain generation, the
erratic array holds the former type, which point into the LINEAR array.
During the splitting phase it is filled with the latter. The algorithm
is type-based alias safe because at the split pass, we look at an entry
as a `struct fde **', to determine whether we have an erratic or linear
entry. For the former, we write a `struct fde *' into the erratic
array, which, in the worst case (when the original LINEAR array begins
with an erratic sequence), will be the entry we just peeked at. These
two accesses can't be reordered, as that would violate causality.

ok?

nathan
-- 
Dr Nathan Sidwell :: Computer Science Department :: Bristol University
Never hand someone a gun unless you are sure where they will point it
nathan@acm.org  http://www.cs.bris.ac.uk/~nathan/  nathan@cs.bris.ac.uk
1999-11-29  Nathan Sidwell  <nathan@acm.org>

	* frame.c (fde_split): Reimplement to avoid variable sized array.

Index: frame.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/frame.c,v
retrieving revision 1.26
diff -c -3 -p -r1.26 frame.c
*** frame.c	1999/10/05 19:41:35	1.26
--- frame.c	1999/11/29 10:19:24
*************** fde_insert (fde_accumulator *accu, fde *
*** 300,332 ****
  
  /* Split LINEAR into a linear sequence with low values and an erratic
     sequence with high values, put the linear one (of longest possible
!    length) into LINEAR and the erratic one into ERRATIC. This is O(N).  */
  static inline void
  fde_split (fde_vector *linear, fde_vector *erratic)
  {
    size_t count = linear->count;
!   size_t linear_max = (size_t) -1;
!   size_t previous_max[count];
!   size_t i, j;
  
    for (i = 0; i < count; i++)
      {
!       for (j = linear_max;
!            j != (size_t) -1
!            && fde_compare (linear->array[i], linear->array[j]) < 0;
!            j = previous_max[j])
          {
!           erratic->array[erratic->count++] = linear->array[j];
!           linear->array[j] = (fde *) NULL;
          }
!       previous_max[i] = j;
!       linear_max = i;
      }
  
!   for (i = 0, j = 0; i < count; i++)
!     if (linear->array[i] != (fde *) NULL)
        linear->array[j++] = linear->array[i];
    linear->count = j;
  }
  
  /* This is O(n log(n)).  BSD/OS defines heapsort in stdlib.h, so we must
--- 300,354 ----
  
  /* Split LINEAR into a linear sequence with low values and an erratic
     sequence with high values, put the linear one (of longest possible
!    length) into LINEAR and the erratic one into ERRATIC. This is O(N).
!    
!    Because the longest linear sequence we are trying to locate can be
!    scattered within the incoming LINEAR array, we need to construct a
!    chain indicating this list.  To avoid having to allocate this chain,
!    we use the ERRATIC array during construction, to hold it.  A final
!    pass iterates over the chain to determine what should be placed
!    in the ERRATIC array, and what is the linear sequence.  This reuse
!    is safe from aliasing.  */
  static inline void
  fde_split (fde_vector *linear, fde_vector *erratic)
  {
+   static fde *marker;
    size_t count = linear->count;
!   fde **chain_end = &marker;
!   fde ***chain = (fde ***)erratic->array;
!   size_t i, j, k;
  
+   /* This should optimize out, but it is wise to make sure this assumption
+      is correct. Should these have different sizes, then the chain and
+      erratic can overtake eachother.  */
+   if (sizeof (fde *) != sizeof (fde **))
+     abort ();
+   
    for (i = 0; i < count; i++)
+     chain[i] = NULL;
+   
+   for (i = 0; i < count; i++)
      {
!       fde **probe;
!       
!       for (probe = chain_end;
!            probe != &marker && fde_compare (linear->array[i], *probe) < 0;
!            probe = chain_end)
          {
!           chain_end = chain[probe - linear->array];
!           chain[probe - linear->array] = NULL;
          }
!       chain[i] = chain_end;
!       chain_end = &linear->array[i];
      }
  
!   for (i = j = k = 0; i < count; i++)
!     if (chain[i])
        linear->array[j++] = linear->array[i];
+     else
+       erratic->array[k++] = linear->array[i];
    linear->count = j;
+   erratic->count = k;
  }
  
  /* This is O(n log(n)).  BSD/OS defines heapsort in stdlib.h, so we must