Makefile.in (UNWIND_H): Remove.

	gcc:
	* Makefile.in (UNWIND_H): Remove.
	(LIB2ADDEH, LIB2ADDEHSTATIC, LIB2ADDEHSHARED): Move to
	../libgcc/Makefile.in.
	(LIBUNWIND, SHLIBUNWIND_LINK, SHLIBUNWIND_INSTALL): Likewise.
	(LIBUNWINDDEP): Remove.
	(libgcc-support): Remove LIB2ADDEH, $(srcdir)/emutls.c dependencies.
	(libgcc.mvars): Remove LIB2ADDEH, LIB2ADDEHSTATIC, LIB2ADDEHSHARED,
	LIBUNWIND, SHLIBUNWIND_LINK, SHLIBUNWIND_INSTALL.
	(stmp-int-hdrs): Remove $(UNWIND_H) dependency.
	Don't copy $(UNWIND_H).
	* config.gcc (ia64*-*-linux*): Remove with_system_libunwind
	handling.
	* configure.ac (GCC_CHECK_UNWIND_GETIPINFO): Remove.
	* aclocal.m4: Regenerate.
	* configure: Regenerate.
	* emutls.c, unwind-c.c, unwind-compat.c, unwind-compat.h,
	unwind-dw2-fde-compat.c, unwind-dw2-fde-glibc.c, unwind-dw2-fde.c,
	unwind-dw2-fde.h, unwind-dw2.c, unwind-dw2.h, unwind-generic.h,
	unwind-pe.h, unwind-sjlj.c, unwind.inc: Move to ../libgcc.
	* unwind-dw2-fde-darwin.c: Move to ../libgcc/config.
	* config/arm/libunwind.S, config/arm/pr-support.c,
	config/arm/unwind-arm.c, config/arm/unwind-arm.h: Move to
	../libgcc/config/arm.
	* config/arm/t-bpabi (UNWIND_H, LIB2ADDEH): Remove.
	* config/arm/t-symbian (UNWIND_H, LIB2ADDEH): Remove.
	* config/frv/t-frv ($(T)frvbegin$(objext)): Use
	$(srcdir)/../libgcc to refer to unwind-dw2-fde.h.
	($(T)frvend$(objext)): Likewise.
	* config/ia64/t-glibc (LIB2ADDEH): Remove.
	* config/ia64/t-glibc-libunwind: Move to ../libgcc/config/ia64.
	* config/ia64/fde-glibc.c, config/ia64/fde-vms.c,
	config/ia64/unwind-ia64.c, config/ia64/unwind-ia64.h: Move to
	../libgcc/config/ia64.
	* config/ia64/t-hpux (LIB2ADDEH): Remove.
	* config/ia64/t-ia64 (LIB2ADDEH): Remove.
	* config/ia64/t-vms (LIB2ADDEH): Remove.
	* config/ia64/vms.h (UNW_IVMS_MODE,
	MD_UNW_COMPATIBLE_PERSONALITY_P): Remove.
	* config/picochip/t-picochip (LIB2ADDEH): Remove.
	* config/rs6000/aix.h (R_LR, MD_FROB_UPDATE_CONTEXT): Remove.
	* config/rs6000/t-darwin (LIB2ADDEH): Remove.
	* config/rs6000/darwin-fallback.c: Move to ../libgcc/config/rs6000.
	* config/sh/t-sh ($(T)unwind-dw2-Os-4-200.o): Use
	$(srcdir)/../libgcc to refer to unwinder sources.
	* config/spu/t-spu-elf (LIB2ADDEH): Remove.
	* config/t-darwin (LIB2ADDEH): Remove.
	* config/t-freebsd (LIB2ADDEH): Remove.
	* config/t-libunwind (LIB2ADDEH, LIB2ADDEHSTATIC): Remove.
	* config/t-libunwind-elf: Move to ../libgcc/config.
	* config/t-linux (LIB2ADDEH): Remove.
	* config/t-sol2 (LIB2ADDEH): Remove.
	* config/xtensa/t-xtensa (LIB2ADDEH): Remove.
	* system.h (MD_FROB_UPDATE_CONTEXT): Poison.

	gcc/po:
	* EXCLUDES (unwind-c.c, unwind-dw2-fde-darwin.c)
	(unwind-dw2-fde-glibc.c, unwind-dw2-fde.c, unwind-dw2-fde.h)
	(unwind-dw2.c, unwind-pe.h, unwind-sjlj.c, unwind.h): Remove.

	libgcc:
	* Makefile.in (LIB2ADDEH, LIB2ADDEHSTATIC, LIB2ADDEHSHARED): New
	variables.
	(LIBUNWIND, SHLIBUNWIND_LINK, SHLIBUNWIND_INSTALL): New variables.
	(LIB2ADDEH, LIB2ADDEHSTATIC, LIB2ADDEHSHARED): Add $(srcdir)/emutls.c.
	(install-unwind_h): New target.
	(all): Depend on it.
	* config.host (unwind_header): New variable.
	(*-*-freebsd*): Set tmake_file to t-eh-dw2-dip.
	(*-*-linux*, frv-*-*linux*, *-*-kfreebsd*-gnu, *-*-knetbsd*-gnu,
	*-*-gnu*): Likewise, also for *-*-kopensolaris*-gnu.
	(*-*-solaris2*): Add t-eh-dw2-dip to tmake_file.
	(arm*-*-linux*): Add arm/t-bpabi for arm*-*-linux-*eabi.
	Set unwind_header.
	(arm*-*-uclinux*): Add arm/t-bpabi for arm*-*-uclinux*eabi.
	Set unwind_header.
	(arm*-*-eabi*, arm*-*-symbianelf*): Add arm/t-bpabi for
	arm*-*-eabi*.
	Add arm/t-symbian to tmake_file for arm*-*-symbianelf*.
	Set unwind_header.
	(ia64*-*-elf*): Add ia64/t-eh-ia64 to tmake_file.
	(ia64*-*-freebsd*): Likewise.
	(ia64*-*-linux*): Add ia64/t-glibc, ia64/t-eh-ia64, t-libunwind to
	tmake_file.
	Add t-libunwind-elf, ia64/t-glibc-libunwind unless
	$with_system_libunwind.
	(ia64*-*-hpux*): Set tmake_file.
	(ia64-hp-*vms*): Add ia64/t-eh-ia64 to tmake_file.
	(picochip-*-*): Set tmake_file.
	(rs6000-ibm-aix4.[3456789]*, powerpc-ibm-aix4.[3456789]*): Set
	md_unwind_header.
	(rs6000-ibm-aix5.1.*, powerpc-ibm-aix5.1.*): Likewise.
	(rs6000-ibm-aix[56789].*, powerpc-ibm-aix[56789].*): Likewise.
	(s390x-ibm-tpf*): Add t-eh-dw2-dip to tmake_file.
	(xtensa*-*-elf*): Set tmake_file.
	(xtensa*-*-linux*): Likewise.
	* configure.ac: Include ../config/unwind_ipinfo.m4.
	Call GCC_CHECK_UNWIND_GETIPINFO.
	Link unwind.h to $unwind_header.
	* configure: Regenerate.
	* emutls.c, unwind-c.c, unwind-compat.c, unwind-compat.h,
	unwind-dw2-fde-compat.c, unwind-dw2-fde-dip.c, unwind-dw2-fde.c,
	unwind-dw2-fde.h, unwind-dw2.c, unwind-dw2.h, unwind-generic.h,
	unwind-pe.h, unwind-sjlj.c, unwind.inc: New files.
	* config/unwind-dw2-fde-darwin.c: New file.
	* config/arm/libunwind.S, config/arm/pr-support.c,
	config/arm/t-bpabi, config/arm/t-symbian, config/arm/unwind-arm.c,
	config/arm/unwind-arm.h,: New files.
	* config/ia64/fde-glibc.c, config/ia64/fde-vms.c,
	config/ia64/t-eh-ia64, config/ia64/t-glibc,
	config/ia64/t-glibc-libunwind, config/ia64/t-hpux,
	config/ia64/t-vms, config/ia64/unwind-ia64.c,
	config/ia64/unwind-ia64.h: New files.
	* config/picochip/t-picochip: New file.
	* config/rs6000/aix-unwind.h, config/rs6000/darwin-fallback.c: New
	files.
	* config/rs6000/t-darwin (LIB2ADDEH): Set.
	* config/s390/t-tpf (LIB2ADDEH): Remove.
	* config/t-darwin (LIB2ADDEH): Set.
	* config/t-eh-dw2-dip: New file.
	* config/t-libunwind, config/t-libunwind-elf: New files.
	* config/t-sol2 (LIB2ADDEH): Remove.
	* config/xtensa/t-xtensa: New file.

	gcc/ada:
	* gcc-interface/Makefile.in (raise-gcc.o): Search
	$(srcdir)/../libgcc.

	libgo:
	* Makefile.am (AM_CFLAGS): Search $(srcdir)/../libgcc.
	* Makefile.in: Regenerate.

	libjava:
	* configure.ac (GCC_UNWIND_INCLUDE): Rename to
	LIBGCC_UNWIND_INCLUDE.
	Point to $(multi_basedir)/./libjava/../libgcc.
	* configure: Regenerate.
	* Makefile.am (GCC_UNWIND_INCLUDE): Reflect this.
	* Makefile.in: Regenerate.

	libobjc:
	* Makefile.in (INCLUDES): Search
	$(srcdir)/$(MULTISRCTOP)../libgcc.

	libstdc++-v3:
	* acinclude.m4 (GLIBCXX_EXPORT_INCLUDES): Point TOPLEVEL_INCLUDES
	to $(toplevel_srcdir)/libgcc.
	* configure: Regenerate.

From-SVN: r177447

1 files changed, 1054 insertions, 0 deletions

diff --git a/libgcc/unwind-dw2-fde.c b/libgcc/unwind-dw2-fde.c
new file mode 100644
index 0000000..93d4271
--- /dev/null
+++ b/libgcc/unwind-dw2-fde.c
@@ -0,0 +1,1054 @@
+/* Subroutines needed for unwinding stack frames for exception handling.  */
+/* Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2008,
+   2009, 2010  Free Software Foundation, Inc.
+   Contributed by Jason Merrill <jason@cygnus.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+Under Section 7 of GPL version 3, you are granted additional
+permissions described in the GCC Runtime Library Exception, version
+3.1, as published by the Free Software Foundation.
+
+You should have received a copy of the GNU General Public License and
+a copy of the GCC Runtime Library Exception along with this program;
+see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef _Unwind_Find_FDE
+#include "tconfig.h"
+#include "tsystem.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "dwarf2.h"
+#include "unwind.h"
+#define NO_BASE_OF_ENCODED_VALUE
+#include "unwind-pe.h"
+#include "unwind-dw2-fde.h"
+#include "gthr.h"
+#endif
+
+/* The unseen_objects list contains objects that have been registered
+   but not yet categorized in any way.  The seen_objects list has had
+   its 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;
+#else
+static __gthread_mutex_t object_mutex;
+#endif
+
+#ifdef __GTHREAD_MUTEX_INIT_FUNCTION
+static void
+init_object_mutex (void)
+{
+  __GTHREAD_MUTEX_INIT_FUNCTION (&object_mutex);
+}
+
+static void
+init_object_mutex_once (void)
+{
+  static __gthread_once_t once = __GTHREAD_ONCE_INIT;
+  __gthread_once (&once, init_object_mutex);
+}
+#else
+#define init_object_mutex_once()
+#endif
+
+/* Called from crtbegin.o to register the unwind info for an object.  */
+
+void
+__register_frame_info_bases (const void *begin, struct object *ob,
+			     void *tbase, void *dbase)
+{
+  /* If .eh_frame is empty, don't register at all.  */
+  if ((const uword *) begin == 0 || *(const uword *) begin == 0)
+    return;
+
+  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;
+#ifdef DWARF2_OBJECT_END_PTR_EXTENSION
+  ob->fde_end = NULL;
+#endif
+
+  init_object_mutex_once ();
+  __gthread_mutex_lock (&object_mutex);
+
+  ob->next = unseen_objects;
+  unseen_objects = ob;
+
+  __gthread_mutex_unlock (&object_mutex);
+}
+
+void
+__register_frame_info (const void *begin, struct object *ob)
+{
+  __register_frame_info_bases (begin, ob, 0, 0);
+}
+
+void
+__register_frame (void *begin)
+{
+  struct object *ob;
+
+  /* If .eh_frame is empty, don't register at all.  */
+  if (*(uword *) begin == 0)
+    return;
+
+  ob = malloc (sizeof (struct object));
+  __register_frame_info (begin, ob);
+}
+
+/* Similar, but BEGIN is actually a pointer to a table of unwind entries
+   for different translation units.  Called from the file generated by
+   collect2.  */
+
+void
+__register_frame_info_table_bases (void *begin, struct object *ob,
+				   void *tbase, void *dbase)
+{
+  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 = 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 = malloc (sizeof (struct object));
+  __register_frame_info_table (begin, ob);
+}
+
+/* Called from crtbegin.o to deregister the unwind info for an object.  */
+/* ??? Glibc has for a while now exported __register_frame_info and
+   __deregister_frame_info.  If we call __register_frame_info_bases
+   from crtbegin (wherein it is declared weak), and this object does
+   not get pulled from libgcc.a for other reasons, then the
+   invocation of __deregister_frame_info will be resolved from glibc.
+   Since the registration did not happen there, we'll die.
+
+   Therefore, declare a new deregistration entry point that does the
+   exact same thing, but will resolve to the same library as
+   implements __register_frame_info_bases.  */
+
+void *
+__deregister_frame_info_bases (const void *begin)
+{
+  struct object **p;
+  struct object *ob = 0;
+
+  /* If .eh_frame is empty, we haven't registered.  */
+  if ((const uword *) begin == 0 || *(const uword *) begin == 0)
+    return ob;
+
+  init_object_mutex_once ();
+  __gthread_mutex_lock (&object_mutex);
+
+  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;
+	  }
+      }
+
+ out:
+  __gthread_mutex_unlock (&object_mutex);
+  gcc_assert (ob);
+  return (void *) ob;
+}
+
+void *
+__deregister_frame_info (const void *begin)
+{
+  return __deregister_frame_info_bases (begin);
+}
+
+void
+__deregister_frame (void *begin)
+{
+  /* If .eh_frame is empty, we haven't registered.  */
+  if (*(uword *) begin != 0)
+    free (__deregister_frame_info (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:
+    case DW_EH_PE_aligned:
+      return 0;
+
+    case DW_EH_PE_textrel:
+      return (_Unwind_Ptr) ob->tbase;
+    case DW_EH_PE_datarel:
+      return (_Unwind_Ptr) ob->dbase;
+    default:
+      gcc_unreachable ();
+    }
+}
+
+/* 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 (const struct dwarf_cie *cie)
+{
+  const unsigned char *aug, *p;
+  _Unwind_Ptr dummy;
+  _uleb128_t utmp;
+  _sleb128_t stmp;
+
+  aug = cie->augmentation;
+  p = aug + strlen ((const char *)aug) + 1; /* Skip the augmentation string.  */
+  if (__builtin_expect (cie->version >= 4, 0))
+    {
+      if (p[0] != sizeof (void *) || p[1] != 0)
+	return DW_EH_PE_omit;		/* We are not prepared to handle unexpected
+					   address sizes or segment selectors.  */
+      p += 2;				/* Skip address size and segment size.  */
+    }
+
+  if (aug[0] != 'z')
+    return DW_EH_PE_absptr;
+
+  p = read_uleb128 (p, &utmp);		/* Skip code alignment.  */
+  p = read_sleb128 (p, &stmp);		/* Skip data alignment.  */
+  if (cie->version == 1)		/* Skip return address column.  */
+    p++;
+  else
+    p = read_uleb128 (p, &utmp);
+
+  aug++;				/* Skip 'z' */
+  p = read_uleb128 (p, &utmp);		/* 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')
+	{
+	  /* ??? Avoid dereferencing indirect pointers, since we're
+	     faking the base address.  Gotta keep DW_EH_PE_aligned
+	     intact, however.  */
+	  p = read_encoded_value_with_base (*p & 0x7F, 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 (const 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 int
+fde_unencoded_compare (struct object *ob __attribute__((unused)),
+		       const fde *x, const fde *y)
+{
+  _Unwind_Ptr x_ptr, y_ptr;
+  memcpy (&x_ptr, x->pc_begin, sizeof (_Unwind_Ptr));
+  memcpy (&y_ptr, y->pc_begin, sizeof (_Unwind_Ptr));
+
+  if (x_ptr > y_ptr)
+    return 1;
+  if (x_ptr < y_ptr)
+    return -1;
+  return 0;
+}
+
+static int
+fde_single_encoding_compare (struct object *ob, const fde *x, const 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);
+
+  if (x_ptr > y_ptr)
+    return 1;
+  if (x_ptr < y_ptr)
+    return -1;
+  return 0;
+}
+
+static int
+fde_mixed_encoding_compare (struct object *ob, const fde *x, const 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);
+
+  if (x_ptr > y_ptr)
+    return 1;
+  if (x_ptr < y_ptr)
+    return -1;
+  return 0;
+}
+
+typedef int (*fde_compare_t) (struct object *, const fde *, const 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.
+   I.e. a linearly increasing sequence (coming from functions in the text
+   section), with additionally a few unordered elements (coming from functions
+   in gnu_linkonce sections) whose values are higher than the values in the
+   surrounding linear sequence (but not necessarily higher than the values
+   at the end of the linear sequence!).
+   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.  */
+
+struct fde_accumulator
+{
+  struct fde_vector *linear;
+  struct fde_vector *erratic;
+};
+
+static inline int
+start_fde_sort (struct fde_accumulator *accu, size_t count)
+{
+  size_t size;
+  if (! count)
+    return 0;
+
+  size = sizeof (struct fde_vector) + sizeof (const fde *) * count;
+  if ((accu->linear = malloc (size)))
+    {
+      accu->linear->count = 0;
+      if ((accu->erratic = malloc (size)))
+	accu->erratic->count = 0;
+      return 1;
+    }
+  else
+    return 0;
+}
+
+static inline void
+fde_insert (struct fde_accumulator *accu, const fde *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
+   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 within the
+   incoming LINEAR array can be interspersed with (high valued) erratic
+   entries.  We construct a chain indicating the sequenced entries.
+   To avoid having to allocate this chain, we overlay it onto the space of
+   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 (struct object *ob, fde_compare_t fde_compare,
+	   struct fde_vector *linear, struct fde_vector *erratic)
+{
+  static const fde *marker;
+  size_t count = linear->count;
+  const fde *const *chain_end = &marker;
+  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, we cannot cast between
+     them and the overlaying onto ERRATIC will not work.  */
+  gcc_assert (sizeof (const fde *) == sizeof (const fde **));
+
+  for (i = 0; i < count; i++)
+    {
+      const fde *const *probe;
+
+      for (probe = chain_end;
+	   probe != &marker && fde_compare (ob, linear->array[i], *probe) < 0;
+	   probe = chain_end)
+	{
+	  chain_end = (const fde *const*) erratic->array[probe - linear->array];
+	  erratic->array[probe - linear->array] = NULL;
+	}
+      erratic->array[i] = (const fde *) chain_end;
+      chain_end = &linear->array[i];
+    }
+
+  /* Each entry in LINEAR which is part of the linear sequence we have
+     discovered will correspond to a non-NULL entry in the chain we built in
+     the ERRATIC array.  */
+  for (i = j = k = 0; i < count; i++)
+    if (erratic->array[i])
+      linear->array[j++] = linear->array[i];
+    else
+      erratic->array[k++] = linear->array[i];
+  linear->count = j;
+  erratic->count = k;
+}
+
+#define SWAP(x,y) do { const fde * tmp = x; x = y; y = tmp; } while (0)
+
+/* Convert a semi-heap to a heap.  A semi-heap is a heap except possibly
+   for the first (root) node; push it down to its rightful place.  */
+
+static void
+frame_downheap (struct object *ob, fde_compare_t fde_compare, const fde **a,
+		int lo, int hi)
+{
+  int i, j;
+
+  for (i = lo, j = 2*i+1;
+       j < hi;
+       j = 2*i+1)
+    {
+      if (j+1 < hi && fde_compare (ob, a[j], a[j+1]) < 0)
+	++j;
+
+      if (fde_compare (ob, a[i], a[j]) < 0)
+	{
+	  SWAP (a[i], a[j]);
+	  i = j;
+	}
+      else
+	break;
+    }
+}
+
+/* This is O(n log(n)).  BSD/OS defines heapsort in stdlib.h, so we must
+   use a name that does not conflict.  */
+
+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.,
+     p. 60-61.  */
+  const fde ** a = erratic->array;
+  /* A portion of the array is called a "heap" if for all i>=0:
+     If i and 2i+1 are valid indices, then a[i] >= a[2i+1].
+     If i and 2i+2 are valid indices, then a[i] >= a[2i+2].  */
+  size_t n = erratic->count;
+  int m;
+
+  /* Expand our heap incrementally from the end of the array, heapifying
+     each resulting semi-heap as we go.  After each step, a[m] is the top
+     of a heap.  */
+  for (m = n/2-1; m >= 0; --m)
+    frame_downheap (ob, fde_compare, a, m, n);
+
+  /* Shrink our heap incrementally from the end of the array, first
+     swapping out the largest element a[0] and then re-heapifying the
+     resulting semi-heap.  After each step, a[0..m) is a heap.  */
+  for (m = n-1; m >= 1; --m)
+    {
+      SWAP (a[0], a[m]);
+      frame_downheap (ob, fde_compare, a, 0, m);
+    }
+#undef SWAP
+}
+
+/* Merge V1 and V2, both sorted, and put the result into V1.  */
+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;
+  const fde * fde2;
+
+  i2 = v2->count;
+  if (i2 > 0)
+    {
+      i1 = v1->count;
+      do
+	{
+	  i2--;
+	  fde2 = v2->array[i2];
+	  while (i1 > 0 && fde_compare (ob, v1->array[i1-1], fde2) > 0)
+	    {
+	      v1->array[i1+i2] = v1->array[i1-1];
+	      i1--;
+	    }
+	  v1->array[i1+i2] = fde2;
+	}
+      while (i2 > 0);
+      v1->count += v2->count;
+    }
+}
+
+static inline void
+end_fde_sort (struct object *ob, struct fde_accumulator *accu, size_t count)
+{
+  fde_compare_t fde_compare;
+
+  gcc_assert (!accu->linear || accu->linear->count == count);
+
+  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 (ob, fde_compare, accu->linear, accu->erratic);
+      gcc_assert (accu->linear->count + accu->erratic->count == count);
+      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 (ob, fde_compare, accu->linear);
+    }
+}
+
+
+/* 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
+classify_object_over_fdes (struct object *ob, const fde *this_fde)
+{
+  const struct dwarf_cie *last_cie = 0;
+  size_t count = 0;
+  int encoding = DW_EH_PE_absptr;
+  _Unwind_Ptr base = 0;
+
+  for (; ! last_fde (ob, this_fde); this_fde = next_fde (this_fde))
+    {
+      const struct dwarf_cie *this_cie;
+      _Unwind_Ptr mask, pc_begin;
+
+      /* Skip CIEs.  */
+      if (this_fde->CIE_delta == 0)
+	continue;
+
+      /* 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);
+	  if (encoding == DW_EH_PE_omit)
+	    return -1;
+	  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;
+	}
+
+      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 = (((_Unwind_Ptr) 1) << (mask << 3)) - 1;
+      else
+	mask = -1;
+
+      if ((pc_begin & mask) == 0)
+	continue;
+
+      count += 1;
+      if ((void *) pc_begin < ob->pc_begin)
+	ob->pc_begin = (void *) pc_begin;
+    }
+
+  return count;
+}
+
+static void
+add_fdes (struct object *ob, struct fde_accumulator *accu, const fde *this_fde)
+{
+  const struct dwarf_cie *last_cie = 0;
+  int encoding = ob->s.b.encoding;
+  _Unwind_Ptr base = base_from_object (ob->s.b.encoding, ob);
+
+  for (; ! last_fde (ob, this_fde); this_fde = next_fde (this_fde))
+    {
+      const struct dwarf_cie *this_cie;
+
+      /* 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)
+	{
+	  _Unwind_Ptr ptr;
+	  memcpy (&ptr, this_fde->pc_begin, sizeof (_Unwind_Ptr));
+	  if (ptr == 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 = (((_Unwind_Ptr) 1) << (mask << 3)) - 1;
+	  else
+	    mask = -1;
+
+	  if ((pc_begin & mask) == 0)
+	    continue;
+	}
+
+      fde_insert (accu, this_fde);
+    }
+}
+
+/* Set up a sorted array of pointers to FDEs for a loaded object.  We
+   count up the entries before allocating the array because it's likely to
+   be faster.  We can be called multiple times, should we have failed to
+   allocate a sorted fde array on a previous occasion.  */
+
+static inline void
+init_object (struct object* ob)
+{
+  struct fde_accumulator accu;
+  size_t count;
+
+  count = ob->s.b.count;
+  if (count == 0)
+    {
+      if (ob->s.b.from_array)
+	{
+	  fde **p = ob->u.array;
+	  for (count = 0; *p; ++p)
+	    {
+	      size_t cur_count = classify_object_over_fdes (ob, *p);
+	      if (cur_count == (size_t) -1)
+		goto unhandled_fdes;
+	      count += cur_count;
+	    }
+	}
+      else
+	{
+	  count = classify_object_over_fdes (ob, ob->u.single);
+	  if (count == (size_t) -1)
+	    {
+	      static const fde terminator;
+	    unhandled_fdes:
+	      ob->s.i = 0;
+	      ob->s.b.encoding = DW_EH_PE_omit;
+	      ob->u.single = &terminator;
+	      return;
+	    }
+	}
+
+      /* 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;
+    }
+
+  if (!start_fde_sort (&accu, count))
+    return;
+
+  if (ob->s.b.from_array)
+    {
+      fde **p;
+      for (p = ob->u.array; *p; ++p)
+	add_fdes (ob, &accu, *p);
+    }
+  else
+    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;
+}
+
+/* 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 const fde *
+linear_search_fdes (struct object *ob, const fde *this_fde, void *pc)
+{
+  const struct dwarf_cie *last_cie = 0;
+  int encoding = ob->s.b.encoding;
+  _Unwind_Ptr base = base_from_object (ob->s.b.encoding, ob);
+
+  for (; ! last_fde (ob, this_fde); this_fde = next_fde (this_fde))
+    {
+      const 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)
+	{
+	  const _Unwind_Ptr *pc_array = (const _Unwind_Ptr *) this_fde->pc_begin;
+	  pc_begin = pc_array[0];
+	  pc_range = pc_array[1];
+	  if (pc_begin == 0)
+	    continue;
+	}
+      else
+	{
+	  _Unwind_Ptr mask;
+	  const unsigned 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 = (((_Unwind_Ptr) 1) << (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 const 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;
+      const fde *const f = vec->array[i];
+      void *pc_begin;
+      uaddr pc_range;
+      memcpy (&pc_begin, (const void * const *) f->pc_begin, sizeof (void *));
+      memcpy (&pc_range, (const uaddr *) f->pc_begin + 1, sizeof (uaddr));
+
+      if (pc < pc_begin)
+	hi = i;
+      else if (pc >= pc_begin + pc_range)
+	lo = i + 1;
+      else
+	return f;
+    }
+
+  return NULL;
+}
+
+static inline const 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; )
+    {
+      size_t i = (lo + hi) / 2;
+      const fde *f = vec->array[i];
+      _Unwind_Ptr pc_begin, pc_range;
+      const unsigned 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;
+    }
+
+  return NULL;
+}
+
+static inline const 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; )
+    {
+      size_t i = (lo + hi) / 2;
+      const fde *f = vec->array[i];
+      _Unwind_Ptr pc_begin, pc_range;
+      const unsigned 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;
+    }
+
+  return NULL;
+}
+
+static const 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)
+    {
+      init_object (ob);
+
+      /* 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 laborious linear search, cos we've no memory.  */
+      if (ob->s.b.from_array)
+	{
+	  fde **p;
+	  for (p = ob->u.array; *p ; p++)
+	    {
+	      const fde *f = linear_search_fdes (ob, *p, pc);
+	      if (f)
+		return f;
+	    }
+	  return NULL;
+	}
+      else
+	return linear_search_fdes (ob, ob->u.single, pc);
+    }
+}
+
+const fde *
+_Unwind_Find_FDE (void *pc, struct dwarf_eh_bases *bases)
+{
+  struct object *ob;
+  const 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 descending, 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;
+      _Unwind_Ptr func;
+
+      bases->tbase = ob->tbase;
+      bases->dbase = ob->dbase;
+
+      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, &func);
+      bases->func = (void *) func;
+    }
+
+  return f;
+}