* except.c (eh_data_format_name): Move to ...

	* dwarf2asm.c: ... here.  Use designated initializers if available.
	(dw2_asm_output_encoded_addr_rtx): Accept varargs commentary.
	* dwarf2asm.h: Update declarations.
	* dwarf2out.c (output_cfi) [DW_CFA_set_loc]: If for_eh, mind
	ASM_PREFERRED_EH_DATA_FORMAT.
	(output_call_frame_info): Likewise.  Use 'L' augmentation for
	the LSDA encoding.

	* unwind-dw2-fde.h (struct fde_vector): New.
	(struct old_object): Rename from struct object.
	(struct object): New.
	(__register_frame_info_bases): Declare.
	(__register_frame_info_table_bases): Declare.
	(struct dwarf_fde): Remove explicit pc_begin/pc_range members.
	* unwind-dw2-fde.c (objects): Remove.
	(unseen_objects, seen_objects): New.
	(__register_frame_info_bases): New.
	(__register_frame_info): Use it.
	(__register_frame_info_table_bases): New.
	(__register_frame_info_table): Use it.
	(__deregister_frame_info): Rewrite for changed object struct.
	(base_from_object, get_cie_encoding, get_fde_encoding): New.
	(fde_unencoded_compare): Rename from fde_compare; uninline.
	(fde_single_encoding_compare, fde_mixed_encoding_compare): New.
	(start_fde_sort): Adjust for new definition of fde_vector.
	(fde_insert): Likewise.
	(end_fde_sort): Likewise.  Select comparison function based
	on properties of the object.
	(fde_split): Take object and fde_compare_t arguments.
	(frame_heapsort, fde_merge): Likewise.
	(classify_object_over_fdes): Rename from count_fdes.  Handle
	encoded pointers.  Collect encoding, mixed_encoding, and pc_begin
	for the object.
	(add_fdes): Handle encoded pointers.
	(init_object): Rename from frame_init.  Update for new struct object.
	(linear_search_fdes): Rename from search_fdes.  Handle encoded
	pointers.
	(binary_search_unencoded_fdes): Broken out from _Unwind_Find_FDE.
	(binary_search_single_encoding_fdes): New.
	(binary_search_mixed_encoding_fdes): New.
	(search_object): New.
	(_Unwind_Find_FDE): Update for new struct object.  Fill in
	the dwarf_eh_bases.
	* unwind-dw2.c: Include unwind-pe.h.  Constify all pointers
	iterating over EH data.
	(_Unwind_FrameState): Remove saw_lsda, addr_encoding.  Add
	fde_encoding, lsda_encoding.
	(read_uleb128, read_sleb128): Remove.
	(read_encoded_pointer): Remove.  All callers use read_encoded_value.
	(extract_cie_info): Set lsda_encoding from 'L' augmentation.
	(uw_frame_state_for): Don't set bases.func.  Handle encoded fde
	pointers.
	* unwind-pe.h: Add "struct" to _Unwind_Context references.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@42176 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 621 insertions, 195 deletions

diff --git a/gcc/unwind-dw2-fde.c b/gcc/unwind-dw2-fde.c
index 7b6b44a5873..3a42f29a6ce 100644
--- a/gcc/unwind-dw2-fde.c
+++ b/gcc/unwind-dw2-fde.c
@@ -30,10 +30,18 @@ Boston, MA 02111-1307, USA.  */
 
 #include "tconfig.h"
 #include "tsystem.h"
+#include "dwarf2.h"
+#include "unwind.h"
+#include "unwind-pe.h"
 #include "unwind-dw2-fde.h"
 #include "gthr.h"
 
-static struct object *objects;
+/* The unseen_objects list contains objects that have been registered
+   but not yet categorized in any way.  The seen_objects list has had
+   it's pc_begin and count fields initialized at minimum, and is sorted
+   by decreasing value of pc_begin.  */
+static struct object *unseen_objects;
+static struct object *seen_objects;
 
 #ifdef __GTHREAD_MUTEX_INIT
 static __gthread_mutex_t object_mutex = __GTHREAD_MUTEX_INIT;
@@ -61,23 +69,32 @@ init_object_mutex_once (void)
 /* Called from crtbegin.o to register the unwind info for an object.  */
 
 void
-__register_frame_info (void *begin, struct object *ob)
+__register_frame_info_bases (void *begin, struct object *ob,
+			     void *tbase, void *dbase)
 {
-  ob->pc_begin = ob->pc_end = 0;
-  ob->fde_begin = begin;
-  ob->fde_array = 0;
-  ob->count = 0;
+  ob->pc_begin = (void *)-1;
+  ob->tbase = tbase;
+  ob->dbase = dbase;
+  ob->u.single = begin;
+  ob->s.i = 0;
+  ob->s.b.encoding = DW_EH_PE_omit;
 
   init_object_mutex_once ();
   __gthread_mutex_lock (&object_mutex);
 
-  ob->next = objects;
-  objects = ob;
+  ob->next = unseen_objects;
+  unseen_objects = ob;
 
   __gthread_mutex_unlock (&object_mutex);
 }
 
 void
+__register_frame_info (void *begin, struct object *ob)
+{
+  __register_frame_info_bases (begin, ob, 0, 0);
+}
+
+void
 __register_frame (void *begin)
 {
   struct object *ob = (struct object *) malloc (sizeof (struct object));
@@ -89,23 +106,33 @@ __register_frame (void *begin)
    collect2.  */
 
 void
-__register_frame_info_table (void *begin, struct object *ob)
+__register_frame_info_table_bases (void *begin, struct object *ob,
+				   void *tbase, void *dbase)
 {
-  ob->pc_begin = ob->pc_end = 0;
-  ob->fde_begin = begin;
-  ob->fde_array = begin;
-  ob->count = 0;
+  ob->pc_begin = (void *)-1;
+  ob->tbase = tbase;
+  ob->dbase = dbase;
+  ob->u.array = begin;
+  ob->s.i = 0;
+  ob->s.b.from_array = 1;
+  ob->s.b.encoding = DW_EH_PE_omit;
 
   init_object_mutex_once ();
   __gthread_mutex_lock (&object_mutex);
 
-  ob->next = objects;
-  objects = ob;
+  ob->next = unseen_objects;
+  unseen_objects = ob;
 
   __gthread_mutex_unlock (&object_mutex);
 }
 
 void
+__register_frame_info_table (void *begin, struct object *ob)
+{
+  __register_frame_info_table_bases (begin, ob, 0, 0);
+}
+
+void
 __register_frame_table (void *begin)
 {
   struct object *ob = (struct object *) malloc (sizeof (struct object));
@@ -118,30 +145,46 @@ void *
 __deregister_frame_info (void *begin)
 {
   struct object **p;
+  struct object *ob = 0;
 
   init_object_mutex_once ();
   __gthread_mutex_lock (&object_mutex);
 
-  p = &objects;
-  while (*p)
-    {
-      if ((*p)->fde_begin == begin)
-	{
-	  struct object *ob = *p;
-	  *p = (*p)->next;
-
-	  /* If we've run init_frame for this object, free the FDE array.  */
-	  if (ob->fde_array && ob->fde_array != begin)
-	    free (ob->fde_array);
-
-	  __gthread_mutex_unlock (&object_mutex);
-	  return (void *) ob;
-	}
-      p = &((*p)->next);
-    }
+  for (p = &unseen_objects; *p ; p = &(*p)->next)
+    if ((*p)->u.single == begin)
+      {
+	ob = *p;
+	*p = ob->next;
+	goto out;
+      }
+
+  for (p = &seen_objects; *p ; p = &(*p)->next)
+    if ((*p)->s.b.sorted)
+      {
+	if ((*p)->u.sort->orig_data == begin)
+	  {
+	    ob = *p;
+	    *p = ob->next;
+	    free (ob->u.sort);
+	    goto out;
+	  }
+      }
+    else
+      {
+	if ((*p)->u.single == begin)
+	  {
+	    ob = *p;
+	    *p = ob->next;
+	    goto out;
+	  }
+      }
 
   __gthread_mutex_unlock (&object_mutex);
   abort ();
+
+ out:
+  __gthread_mutex_unlock (&object_mutex);
+  return (void *) ob;
 }
 
 void
@@ -151,10 +194,119 @@ __deregister_frame (void *begin)
 }
 
 
+/* Like base_of_encoded_value, but take the base from a struct object
+   instead of an _Unwind_Context.  */
+
+static _Unwind_Ptr
+base_from_object (unsigned char encoding, struct object *ob)
+{
+  if (encoding == DW_EH_PE_omit)
+    return 0;
+
+  switch (encoding & 0x70)
+    {
+    case DW_EH_PE_absptr:
+    case DW_EH_PE_pcrel:
+      return 0;
+
+    case DW_EH_PE_textrel:
+      return (_Unwind_Ptr) ob->tbase;
+    case DW_EH_PE_datarel:
+      return (_Unwind_Ptr) ob->dbase;
+    }
+  abort ();
+}
+
+/* Return the FDE pointer encoding from the CIE.  */
+/* ??? This is a subset of extract_cie_info from unwind-dw2.c.  */
+
+static int
+get_cie_encoding (struct dwarf_cie *cie)
+{
+  const unsigned char *aug, *p;
+  _Unwind_Ptr dummy;
+
+  aug = cie->augmentation;
+  if (aug[0] != 'z')
+    return DW_EH_PE_absptr;
+
+  p = aug + strlen (aug) + 1;		/* Skip the augmentation string.  */
+  p = read_uleb128 (p, &dummy);		/* Skip code alignment.  */
+  p = read_sleb128 (p, &dummy);		/* Skip data alignment.  */
+  p++;					/* Skip return address column.  */
+
+  aug++;				/* Skip 'z' */
+  p = read_uleb128 (p, &dummy);		/* Skip augmentation length.  */
+  while (1)
+    {
+      /* This is what we're looking for.  */
+      if (*aug == 'R')
+	return *p;
+      /* Personality encoding and pointer.  */
+      else if (*aug == 'P')
+	p = read_encoded_value_with_base (*p & 0xF, 0, p + 1, &dummy);
+      /* LSDA encoding.  */
+      else if (*aug == 'L')
+	p++;
+      /* Otherwise end of string, or unknown augmentation.  */
+      else
+	return DW_EH_PE_absptr;
+      aug++;
+    }
+}
+
+static inline int
+get_fde_encoding (struct dwarf_fde *f)
+{
+  return get_cie_encoding (get_cie (f));
+}
+
+
 /* Sorting an array of FDEs by address.
    (Ideally we would have the linker sort the FDEs so we don't have to do
    it at run time. But the linkers are not yet prepared for this.)  */
 
+/* Comparison routines.  Three variants of increasing complexity.  */
+
+static saddr
+fde_unencoded_compare (struct object *ob __attribute__((unused)),
+		       fde *x, fde *y)
+{
+  return *(saddr *)x->pc_begin - *(saddr *)y->pc_begin;
+}
+
+static saddr
+fde_single_encoding_compare (struct object *ob, fde *x, fde *y)
+{
+  _Unwind_Ptr base, x_ptr, y_ptr;
+
+  base = base_from_object (ob->s.b.encoding, ob);
+  read_encoded_value_with_base (ob->s.b.encoding, base, x->pc_begin, &x_ptr);
+  read_encoded_value_with_base (ob->s.b.encoding, base, y->pc_begin, &y_ptr);
+
+  return x_ptr - y_ptr;
+}
+
+static saddr
+fde_mixed_encoding_compare (struct object *ob, fde *x, fde *y)
+{
+  int x_encoding, y_encoding;
+  _Unwind_Ptr x_ptr, y_ptr;
+
+  x_encoding = get_fde_encoding (x);
+  read_encoded_value_with_base (x_encoding, base_from_object (x_encoding, ob),
+				x->pc_begin, &x_ptr);
+
+  y_encoding = get_fde_encoding (y);
+  read_encoded_value_with_base (y_encoding, base_from_object (y_encoding, ob),
+				y->pc_begin, &y_ptr);
+
+  return x_ptr - y_ptr;
+}
+
+typedef saddr (*fde_compare_t) (struct object *, fde *, fde *);
+
+
 /* This is a special mix of insertion sort and heap sort, optimized for
    the data sets that actually occur. They look like
    101 102 103 127 128 105 108 110 190 111 115 119 125 160 126 129 130.
@@ -166,41 +318,36 @@ __deregister_frame (void *begin)
    The worst-case total run time is O(N) + O(n log (n)), where N is the
    total number of FDEs and n is the number of erratic ones.  */
 
-typedef struct fde_vector
-{
-  fde **array;
-  size_t count;
-} fde_vector;
-
-typedef struct fde_accumulator
+struct fde_accumulator
 {
-  fde_vector linear;
-  fde_vector erratic;
-} fde_accumulator;
-
-static inline saddr
-fde_compare (fde *x, fde *y)
-{
-  return (saddr)x->pc_begin - (saddr)y->pc_begin;
-}
+  struct fde_vector *linear;
+  struct fde_vector *erratic;
+};
 
 static inline int
-start_fde_sort (fde_accumulator *accu, size_t count)
+start_fde_sort (struct fde_accumulator *accu, size_t count)
 {
-  accu->linear.array = count ? (fde **) malloc (sizeof (fde *) * count) : NULL;
-  accu->erratic.array = accu->linear.array ?
-      (fde **) malloc (sizeof (fde *) * count) : NULL;
-  accu->linear.count = 0;
-  accu->erratic.count = 0;
-  
-  return accu->linear.array != NULL;
+  size_t size;
+  if (! count)
+    return 0;
+
+  size = sizeof (struct fde_vector) + sizeof (fde *) * count;
+  if ((accu->linear = (struct fde_vector *) malloc (size)))
+    {
+      accu->linear->count = 0;
+      if ((accu->erratic = (struct fde_vector *) malloc (size)))
+	accu->erratic->count = 0;
+      return 1;
+    }
+  else
+    return 0;  
 }
 
 static inline void
-fde_insert (fde_accumulator *accu, fde *this_fde)
+fde_insert (struct fde_accumulator *accu, fde *this_fde)
 {
-  if (accu->linear.array)
-    accu->linear.array[accu->linear.count++] = this_fde;
+  if (accu->linear)
+    accu->linear->array[accu->linear->count++] = this_fde;
 }
 
 /* Split LINEAR into a linear sequence with low values and an erratic
@@ -214,8 +361,10 @@ fde_insert (fde_accumulator *accu, fde *this_fde)
    the ERRATIC array during construction.  A final pass iterates over the
    chain to determine what should be placed in the ERRATIC array, and
    what is the linear sequence.  This overlay is safe from aliasing.  */
+
 static inline void
-fde_split (fde_vector *linear, fde_vector *erratic)
+fde_split (struct object *ob, fde_compare_t fde_compare,
+	   struct fde_vector *linear, struct fde_vector *erratic)
 {
   static fde *marker;
   size_t count = linear->count;
@@ -233,7 +382,7 @@ fde_split (fde_vector *linear, fde_vector *erratic)
       fde **probe;
       
       for (probe = chain_end;
-           probe != &marker && fde_compare (linear->array[i], *probe) < 0;
+           probe != &marker && fde_compare (ob, linear->array[i], *probe) < 0;
            probe = chain_end)
         {
           chain_end = (fde **)erratic->array[probe - linear->array];
@@ -257,8 +406,10 @@ fde_split (fde_vector *linear, fde_vector *erratic)
 
 /* This is O(n log(n)).  BSD/OS defines heapsort in stdlib.h, so we must
    use a name that does not conflict.  */
-static inline void
-frame_heapsort (fde_vector *erratic)
+
+static void
+frame_heapsort (struct object *ob, fde_compare_t fde_compare,
+		struct fde_vector *erratic)
 {
   /* For a description of this algorithm, see:
      Samuel P. Harbison, Guy L. Steele Jr.: C, a reference manual, 2nd ed.,
@@ -279,13 +430,13 @@ frame_heapsort (fde_vector *erratic)
       for (i = m; 2*i+1 < n; )
         {
           if (2*i+2 < n
-              && fde_compare (a[2*i+2], a[2*i+1]) > 0
-              && fde_compare (a[2*i+2], a[i]) > 0)
+              && fde_compare (ob, a[2*i+2], a[2*i+1]) > 0
+              && fde_compare (ob, a[2*i+2], a[i]) > 0)
             {
               SWAP (a[i], a[2*i+2]);
               i = 2*i+2;
             }
-          else if (fde_compare (a[2*i+1], a[i]) > 0)
+          else if (fde_compare (ob, a[2*i+1], a[i]) > 0)
             {
               SWAP (a[i], a[2*i+1]);
               i = 2*i+1;
@@ -302,13 +453,13 @@ frame_heapsort (fde_vector *erratic)
       for (i = 0; 2*i+1 < n; )
         {
           if (2*i+2 < n
-              && fde_compare (a[2*i+2], a[2*i+1]) > 0
-              && fde_compare (a[2*i+2], a[i]) > 0)
+              && fde_compare (ob, a[2*i+2], a[2*i+1]) > 0
+              && fde_compare (ob, a[2*i+2], a[i]) > 0)
             {
               SWAP (a[i], a[2*i+2]);
               i = 2*i+2;
             }
-          else if (fde_compare (a[2*i+1], a[i]) > 0)
+          else if (fde_compare (ob, a[2*i+1], a[i]) > 0)
             {
               SWAP (a[i], a[2*i+1]);
               i = 2*i+1;
@@ -321,8 +472,9 @@ frame_heapsort (fde_vector *erratic)
 }
 
 /* Merge V1 and V2, both sorted, and put the result into V1. */
-static void
-fde_merge (fde_vector *v1, const fde_vector *v2)
+static inline void
+fde_merge (struct object *ob, fde_compare_t fde_compare,
+	   struct fde_vector *v1, struct fde_vector *v2)
 {
   size_t i1, i2;
   fde * fde2;
@@ -334,7 +486,7 @@ fde_merge (fde_vector *v1, const fde_vector *v2)
       do {
         i2--;
         fde2 = v2->array[i2];
-        while (i1 > 0 && fde_compare (v1->array[i1-1], fde2) > 0)
+        while (i1 > 0 && fde_compare (ob, v1->array[i1-1], fde2) > 0)
           {
             v1->array[i1+i2] = v1->array[i1-1];
             i1--;
@@ -345,81 +497,154 @@ fde_merge (fde_vector *v1, const fde_vector *v2)
     }
 }
 
-static fde **
-end_fde_sort (fde_accumulator *accu, size_t count)
+static inline void
+end_fde_sort (struct object *ob, struct fde_accumulator *accu, size_t count)
 {
-  if (accu->linear.array && accu->linear.count != count)
+  fde_compare_t fde_compare;
+
+  if (accu->linear && accu->linear->count != count)
     abort ();
-  
-  if (accu->erratic.array)
+
+  if (ob->s.b.mixed_encoding)
+    fde_compare = fde_mixed_encoding_compare;
+  else if (ob->s.b.encoding == DW_EH_PE_absptr)
+    fde_compare = fde_unencoded_compare;
+  else
+    fde_compare = fde_single_encoding_compare;
+
+  if (accu->erratic)
     {
-      fde_split (&accu->linear, &accu->erratic);
-      if (accu->linear.count + accu->erratic.count != count)
+      fde_split (ob, fde_compare, accu->linear, accu->erratic);
+      if (accu->linear->count + accu->erratic->count != count)
 	abort ();
-      frame_heapsort (&accu->erratic);
-      fde_merge (&accu->linear, &accu->erratic);
-      free (accu->erratic.array);
+      frame_heapsort (ob, fde_compare, accu->erratic);
+      fde_merge (ob, fde_compare, accu->linear, accu->erratic);
+      free (accu->erratic);
     }
   else
     {
-      /* We've not managed to malloc an erratic array, so heap sort in the
-         linear one.  */
-      frame_heapsort (&accu->linear);
+      /* We've not managed to malloc an erratic array,
+	 so heap sort in the linear one.  */
+      frame_heapsort (ob, fde_compare, accu->linear);
     }
-  return accu->linear.array;
 }
 
 
+/* Update encoding, mixed_encoding, and pc_begin for OB for the 
+   fde array beginning at THIS_FDE.  Return the number of fdes
+   encountered along the way.  */
+
 static size_t
-count_fdes (fde *this_fde)
+classify_object_over_fdes (struct object *ob, fde *this_fde)
 {
-  size_t count;
+  struct dwarf_cie *last_cie = 0;
+  size_t count = 0;
+  int encoding = DW_EH_PE_absptr;
+  _Unwind_Ptr base = 0;
 
-  for (count = 0; this_fde->length != 0; this_fde = next_fde (this_fde))
-    /* Skip CIEs and omitted link-once FDE entries.  */
-    if (this_fde->CIE_delta != 0 && this_fde->pc_begin != 0)
-      ++count;
+  for (; this_fde->length != 0; this_fde = next_fde (this_fde))
+    {
+      struct dwarf_cie *this_cie;
+      _Unwind_Ptr mask, pc_begin;
 
-  return count;
-}
+      /* Skip CIEs.  */
+      if (this_fde->CIE_delta == 0)
+	continue;
 
-static void
-add_fdes (fde *this_fde, fde_accumulator *accu, void **beg_ptr, void **end_ptr)
-{
-  void *pc_begin = *beg_ptr;
-  void *pc_end = *end_ptr;
+      /* Determine the encoding for this FDE.  Note mixed encoded
+	 objects for later.  */
+      this_cie = get_cie (this_fde);
+      if (this_cie != last_cie)
+	{
+	  last_cie = this_cie;
+	  encoding = get_cie_encoding (this_cie);
+	  base = base_from_object (encoding, ob);
+	  if (ob->s.b.encoding == DW_EH_PE_omit)
+	    ob->s.b.encoding = encoding;
+	  else if (ob->s.b.encoding != encoding)
+	    ob->s.b.mixed_encoding = 1;
+	}
 
-  for (; this_fde->length != 0; this_fde = next_fde (this_fde))
-    {
-      /* Skip CIEs and linked once FDE entries.  */
-      if (this_fde->CIE_delta == 0 || this_fde->pc_begin == 0)
-        continue;
+      read_encoded_value_with_base (encoding, base, this_fde->pc_begin,
+				    &pc_begin);
 
-      fde_insert (accu, this_fde);
+      /* Take care to ignore link-once functions that were removed.
+	 In these cases, the function address will be NULL, but if
+	 the encoding is smaller than a pointer a true NULL may not
+	 be representable.  Assume 0 in the representable bits is NULL.  */
+      mask = size_of_encoded_value (encoding);
+      if (mask < sizeof (void *))
+	mask = (1L << (mask << 3)) - 1;
+      else
+	mask = -1;
+
+      if ((pc_begin & mask) == 0)
+	continue;
 
-      if (this_fde->pc_begin < pc_begin)
-        pc_begin = this_fde->pc_begin;
-      if (this_fde->pc_begin + this_fde->pc_range > pc_end)
-        pc_end = this_fde->pc_begin + this_fde->pc_range;
+      count += 1;
+      if ((void *)pc_begin < ob->pc_begin)
+	ob->pc_begin = (void *)pc_begin;
     }
 
-  *beg_ptr = pc_begin;
-  *end_ptr = pc_end;
+  return count;
 }
 
-static fde *
-search_fdes (fde *this_fde, void *pc)
+static void
+add_fdes (struct object *ob, struct fde_accumulator *accu, fde *this_fde)
 {
+  struct dwarf_cie *last_cie = 0;
+  int encoding = ob->s.b.encoding;
+  _Unwind_Ptr base = base_from_object (ob->s.b.encoding, ob);
+
   for (; this_fde->length != 0; this_fde = next_fde (this_fde))
     {
-      /* Skip CIEs and linked once FDE entries.  */
-      if (this_fde->CIE_delta == 0 || this_fde->pc_begin == 0)
-        continue;
+      struct dwarf_cie *this_cie;
 
-      if ((uaddr)((char *)pc - (char *)this_fde->pc_begin) < this_fde->pc_range)
-        return this_fde;
+      /* Skip CIEs.  */
+      if (this_fde->CIE_delta == 0)
+	continue;
+
+      if (ob->s.b.mixed_encoding)
+	{
+	  /* Determine the encoding for this FDE.  Note mixed encoded
+	     objects for later.  */
+	  this_cie = get_cie (this_fde);
+	  if (this_cie != last_cie)
+	    {
+	      last_cie = this_cie;
+	      encoding = get_cie_encoding (this_cie);
+	      base = base_from_object (encoding, ob);
+	    }
+	}
+
+      if (encoding == DW_EH_PE_absptr)
+	{
+	  if (*(_Unwind_Ptr *)this_fde->pc_begin == 0)
+	    continue;
+	}
+      else
+	{
+	  _Unwind_Ptr pc_begin, mask;
+
+	  read_encoded_value_with_base (encoding, base, this_fde->pc_begin,
+					&pc_begin);
+
+	  /* Take care to ignore link-once functions that were removed.
+	     In these cases, the function address will be NULL, but if
+	     the encoding is smaller than a pointer a true NULL may not
+	     be representable.  Assume 0 in the representable bits is NULL.  */
+	  mask = size_of_encoded_value (encoding);
+	  if (mask < sizeof (void *))
+	    mask = (1L << (mask << 3)) - 1;
+	  else
+	    mask = -1;
+
+	  if ((pc_begin & mask) == 0)
+	    continue;
+	}
+
+      fde_insert (accu, this_fde);
     }
-  return NULL;
 }
 
 /* Set up a sorted array of pointers to FDEs for a loaded object.  We
@@ -427,116 +652,317 @@ search_fdes (fde *this_fde, void *pc)
    be faster.  We can be called multiple times, should we have failed to
    allocate a sorted fde array on a previous occasion.  */
 
-static void
-frame_init (struct object* ob)
+static inline void
+init_object (struct object* ob)
 {
+  struct fde_accumulator accu;
   size_t count;
-  fde_accumulator accu;
-  void *pc_begin, *pc_end;
-  fde **array;
 
-  if (ob->pc_begin)
-    count = ob->count;
-  else if (ob->fde_array)
+  count = ob->s.b.count;
+  if (count == 0)
     {
-      fde **p = ob->fde_array;
-      for (count = 0; *p; ++p)
-        count += count_fdes (*p);
+      if (ob->s.b.from_array)
+	{
+	  fde **p = ob->u.array;
+	  for (count = 0; *p; ++p)
+	    count += classify_object_over_fdes (ob, *p);
+	}
+      else
+	count = classify_object_over_fdes (ob, ob->u.single);
+
+      /* The count field we have in the main struct object is somewhat
+	 limited, but should suffice for virtually all cases.  If the
+	 counted value doesn't fit, re-write a zero.  The worst that
+	 happens is that we re-count next time -- admittedly non-trivial
+	 in that this implies some 2M fdes, but at least we function.  */
+      ob->s.b.count = count;
+      if (ob->s.b.count != count)
+	ob->s.b.count = 0;
     }
-  else
-    count = count_fdes (ob->fde_begin);
-  ob->count = count;
 
-  if (!start_fde_sort (&accu, count) && ob->pc_begin)
+  if (!start_fde_sort (&accu, count))
     return;
 
-  pc_begin = (void*)(uaddr)-1;
-  pc_end = 0;
-
-  if (ob->fde_array)
+  if (ob->s.b.from_array)
     {
-      fde **p = ob->fde_array;
-      for (; *p; ++p)
-        add_fdes (*p, &accu, &pc_begin, &pc_end);
+      fde **p;
+      for (p = ob->u.array; *p; ++p)
+        add_fdes (ob, &accu, *p);
     }
   else
-    add_fdes (ob->fde_begin, &accu, &pc_begin, &pc_end);
-  array = end_fde_sort (&accu, count);
-  if (array)
-    ob->fde_array = array;
-  ob->pc_begin = pc_begin;
-  ob->pc_end = pc_end;
+    add_fdes (ob, &accu, ob->u.single);
+
+  end_fde_sort (ob, &accu, count);
+
+  /* Save the original fde pointer, since this is the key by which the
+     DSO will deregister the object.  */
+  accu.linear->orig_data = ob->u.single;
+  ob->u.sort = accu.linear;
+
+  ob->s.b.sorted = 1;
 }
 
-fde *
-_Unwind_Find_FDE (void *pc, struct dwarf_eh_bases *bases ATTRIBUTE_UNUSED)
+/* A linear search through a set of FDEs for the given PC.  This is
+   used when there was insufficient memory to allocate and sort an
+   array.  */
+
+static fde *
+linear_search_fdes (struct object *ob, fde *this_fde, void *pc)
 {
-  struct object *ob;
+  struct dwarf_cie *last_cie = 0;
+  int encoding = ob->s.b.encoding;
+  _Unwind_Ptr base = base_from_object (ob->s.b.encoding, ob);
+
+  for (; this_fde->length != 0; this_fde = next_fde (this_fde))
+    {
+      struct dwarf_cie *this_cie;
+      _Unwind_Ptr pc_begin, pc_range;
+
+      /* Skip CIEs.  */
+      if (this_fde->CIE_delta == 0)
+	continue;
+
+      if (ob->s.b.mixed_encoding)
+	{
+	  /* Determine the encoding for this FDE.  Note mixed encoded
+	     objects for later.  */
+	  this_cie = get_cie (this_fde);
+	  if (this_cie != last_cie)
+	    {
+	      last_cie = this_cie;
+	      encoding = get_cie_encoding (this_cie);
+	      base = base_from_object (encoding, ob);
+	    }
+	}
+
+      if (encoding == DW_EH_PE_absptr)
+	{
+	  pc_begin = ((_Unwind_Ptr *)this_fde->pc_begin)[0];
+	  pc_range = ((_Unwind_Ptr *)this_fde->pc_begin)[1];
+	  if (pc_begin == 0)
+	    continue;
+	}
+      else
+	{
+	  _Unwind_Ptr mask;
+	  const char *p;
+
+	  p = read_encoded_value_with_base (encoding, base,
+					    this_fde->pc_begin, &pc_begin);
+	  read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range);
+
+	  /* Take care to ignore link-once functions that were removed.
+	     In these cases, the function address will be NULL, but if
+	     the encoding is smaller than a pointer a true NULL may not
+	     be representable.  Assume 0 in the representable bits is NULL.  */
+	  mask = size_of_encoded_value (encoding);
+	  if (mask < sizeof (void *))
+	    mask = (1L << (mask << 3)) - 1;
+	  else
+	    mask = -1;
+
+	  if ((pc_begin & mask) == 0)
+	    continue;
+	}
+
+      if ((_Unwind_Ptr)pc - pc_begin < pc_range)
+        return this_fde;
+    }
+
+  return NULL;
+}
+
+/* Binary search for an FDE containing the given PC.  Here are three
+   implementations of increasing complexity.  */
+
+static inline fde *
+binary_search_unencoded_fdes (struct object *ob, void *pc)
+{
+  struct fde_vector *vec = ob->u.sort;
   size_t lo, hi;
+      
+  for (lo = 0, hi = vec->count; lo < hi; )
+    {
+      size_t i = (lo + hi) / 2;
+      fde *f = vec->array[i];
+      void *pc_begin;
+      uaddr pc_range;
+
+      pc_begin = ((void **)f->pc_begin)[0];
+      pc_range = ((uaddr *)f->pc_begin)[1];
+
+      if (pc < pc_begin)
+	hi = i;
+      else if (pc >= pc_begin + pc_range)
+	lo = i + 1;
+      else
+	return f;
+    }
 
-  init_object_mutex_once ();
-  __gthread_mutex_lock (&object_mutex);
+  return NULL;
+}
 
-  /* Linear search through the objects, to find the one containing the pc. */
-  for (ob = objects; ob; ob = ob->next)
+static inline fde *
+binary_search_single_encoding_fdes (struct object *ob, void *pc)
+{
+  struct fde_vector *vec = ob->u.sort;
+  int encoding = ob->s.b.encoding;
+  _Unwind_Ptr base = base_from_object (encoding, ob);
+  size_t lo, hi;
+      
+  for (lo = 0, hi = vec->count; lo < hi; )
     {
-      if (ob->pc_begin == 0)
-        frame_init (ob);
-      if (pc >= ob->pc_begin && pc < ob->pc_end)
-        break;
+      size_t i = (lo + hi) / 2;
+      fde *f = vec->array[i];
+      _Unwind_Ptr pc_begin, pc_range;
+      const char *p;
+
+      p = read_encoded_value_with_base (encoding, base, f->pc_begin,
+					&pc_begin);
+      read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range);
+
+      if ((_Unwind_Ptr)pc < pc_begin)
+	hi = i;
+      else if ((_Unwind_Ptr)pc >= pc_begin + pc_range)
+	lo = i + 1;
+      else
+	return f;
     }
 
-  if (ob == 0)
+  return NULL;
+}
+
+static inline fde *
+binary_search_mixed_encoding_fdes (struct object *ob, void *pc)
+{
+  struct fde_vector *vec = ob->u.sort;
+  size_t lo, hi;
+      
+  for (lo = 0, hi = vec->count; lo < hi; )
     {
-      __gthread_mutex_unlock (&object_mutex);
-      return 0;
+      size_t i = (lo + hi) / 2;
+      fde *f = vec->array[i];
+      _Unwind_Ptr pc_begin, pc_range;
+      const char *p;
+      int encoding;
+
+      encoding = get_fde_encoding (f);
+      p = read_encoded_value_with_base (encoding,
+					base_from_object (encoding, ob),
+					f->pc_begin, &pc_begin);
+      read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range);
+
+      if ((_Unwind_Ptr)pc < pc_begin)
+	hi = i;
+      else if ((_Unwind_Ptr)pc >= pc_begin + pc_range)
+	lo = i + 1;
+      else
+	return f;
     }
 
-  if (!ob->fde_array || (void *)ob->fde_array == (void *)ob->fde_begin)
-    frame_init (ob);
+  return NULL;
+}
 
-  if (ob->fde_array && (void *)ob->fde_array != (void *)ob->fde_begin)
+static fde *
+search_object (struct object* ob, void *pc)
+{
+  /* If the data hasn't been sorted, try to do this now.  We may have
+     more memory available than last time we tried.  */
+  if (! ob->s.b.sorted)
     {
-      __gthread_mutex_unlock (&object_mutex);
-      
-      /* Standard binary search algorithm.  */
-      for (lo = 0, hi = ob->count; lo < hi; )
-        {
-          size_t i = (lo + hi) / 2;
-          fde *f = ob->fde_array[i];
+      init_object (ob);
 
-          if (pc < f->pc_begin)
-            hi = i;
-          else if (pc >= f->pc_begin + f->pc_range)
-            lo = i + 1;
-          else
-            return f;
-        }
+      /* Despite the above comment, the normal reason to get here is
+	 that we've not processed this object before.  A quick range
+	 check is in order.  */
+      if (pc < ob->pc_begin)
+	return NULL;
+    }
+
+  if (ob->s.b.sorted)
+    {
+      if (ob->s.b.mixed_encoding)
+	return binary_search_mixed_encoding_fdes (ob, pc);
+      else if (ob->s.b.encoding == DW_EH_PE_absptr)
+	return binary_search_unencoded_fdes (ob, pc);
+      else
+	return binary_search_single_encoding_fdes (ob, pc);
     }
   else
     {
-      /* Long slow labourious linear search, cos we've no memory. */
-      fde *f;
-      
-      if (ob->fde_array)
+      /* Long slow labourious linear search, cos we've no memory.  */
+      if (ob->s.b.from_array)
         {
-          fde **p = ob->fde_array;
-          
-          do
-            {
-              f = search_fdes (*p, pc);
+          fde **p;
+	  for (p = ob->u.array; *p ; p++)
+	    {
+	      fde *f = linear_search_fdes (ob, *p, pc);
               if (f)
-                break;
-              p++;
+		return f;
             }
-          while (*p);
-        }
+	  return NULL;
+	}
       else
-        f = search_fdes (ob->fde_begin, pc);
+	return linear_search_fdes (ob, ob->u.single, pc);
+    }
+}
+
+fde *
+_Unwind_Find_FDE (void *pc, struct dwarf_eh_bases *bases)
+{
+  struct object *ob;
+  fde *f = NULL;
+
+  init_object_mutex_once ();
+  __gthread_mutex_lock (&object_mutex);
+
+  /* Linear search through the classified objects, to find the one
+     containing the pc.  Note that pc_begin is sorted decending, and
+     we expect objects to be non-overlapping.  */
+  for (ob = seen_objects; ob; ob = ob->next)
+    if (pc >= ob->pc_begin)
+      {
+	f = search_object (ob, pc);
+	if (f)
+	  goto fini;
+	break;
+      }
+
+  /* Classify and search the objects we've not yet processed.  */
+  while ((ob = unseen_objects))
+    {
+      struct object **p;
+
+      unseen_objects = ob->next;
+      f = search_object (ob, pc);
+
+      /* Insert the object into the classified list.  */
+      for (p = &seen_objects; *p ; p = &(*p)->next)
+	if ((*p)->pc_begin < ob->pc_begin)
+	  break;
+      ob->next = *p;
+      *p = ob;
+
+      if (f)
+	goto fini;
+    }
+
+ fini:
+  __gthread_mutex_unlock (&object_mutex);
+
+  if (f)
+    {
+      int encoding;
+
+      bases->tbase = ob->tbase;
+      bases->dbase = ob->dbase;
 
-      __gthread_mutex_unlock (&object_mutex);
-      return f;
+      encoding = ob->s.b.encoding;
+      if (ob->s.b.mixed_encoding)
+	encoding = get_fde_encoding (f);
+      read_encoded_value_with_base (encoding, base_from_object (encoding, ob),
+				    f->pc_begin, (_Unwind_Ptr *)&bases->func);
     }
 
-  return 0;
+  return f;
 }