2012-03-21 Cary Coutant <ccoutant@google.com>

	* Makefile.am: Add gdb-index.cc, gdb-index.h.
	* Makefile.in: Regenerate.
	* dwarf_reader.cc (Sized_elf_reloc_mapper::do_initialize): New function.
	(Sized_elf_reloc_mapper::symbol_section): New function.
	(Sized_elf_reloc_mapper::do_get_reloc_target): New function.
	(make_elf_reloc_mapper): New function.
	(Dwarf_abbrev_table::clear_abbrev_codes): New function.
	(Dwarf_abbrev_table::do_read_abbrevs): New function.
	(Dwarf_abbrev_table::do_get_abbrev): New function.
	(Dwarf_ranges_table::read_ranges_table): New function.
	(Dwarf_ranges_table::read_range_list): New function.
	(Dwarf_pubnames_table::read_section): New function.
	(Dwarf_pubnames_table::read_header): New function.
	(Dwarf_pubnames_table::next_name): New function.
	(Dwarf_die::Dwarf_die): New function.
	(Dwarf_die::read_attributes): New function.
	(Dwarf_die::skip_attributes): New function.
	(Dwarf_die::set_name): New function.
	(Dwarf_die::set_linkage_name): New function.
	(Dwarf_die::attribute): New function.
	(Dwarf_die::string_attribute): New function.
	(Dwarf_die::int_attribute): New function.
	(Dwarf_die::uint_attribute): New function.
	(Dwarf_die::ref_attribute): New function.
	(Dwarf_die::child_offset): New function.
	(Dwarf_die::sibling_offset): New function.
	(Dwarf_info_reader::check_buffer): New function.
	(Dwarf_info_reader::parse): New function.
	(Dwarf_info_reader::do_parse): New function.
	(Dwarf_info_reader::do_read_string_table): New function.
	(Dwarf_info_reader::lookup_reloc): New function.
	(Dwarf_info_reader::get_string): New function.
	(Dwarf_info_reader::visit_compilation_unit): New function.
	(Dwarf_info_reader::visit_type_unit): New function.
	(Sized_dwarf_line_info::Sized_dwarf_line_info): Use
	Sized_elf_reloc_mapper.
	(Sized_dwarf_line_info::symbol_section): Remove function.
	(Sized_dwarf_line_info::read_relocs): Use Sized_elf_reloc_mapper.
	(Sized_dwarf_line_info::read_line_mappings): Remove object
	parameter, adjust callers.
	(Sized_dwarf_line_info::format_file_lineno): Fix type of cast.
	* dwarf_reader.h: Include <sys/types.h>.
	(class Track_relocs): Remove forward declaration.
	(class Elf_reloc_mapper): New class.
	(class Sized_elf_reloc_mapper): New class.
	(class Dwarf_abbrev_table): New class.
	(class Dwarf_range_list): New class.
	(class Dwarf_ranges_table): New class.
	(class Dwarf_pubnames_table): New class.
	(class Dwarf_die): New class.
	(class Dwarf_info_reader): New class.
	(Sized_dwarf_line_info::read_line_mappings): Remove object parameter.
	(Sized_dwarf_line_info::symbol_section): Remove member function.
	* dynobj.h (Sized_dynobj::do_section_contents): Refactor code from
	base class.
	* gdb-index.cc: New source file.
	* gdb-index.h: New source file.
	* incremental.cc (Sized_relobj_incr::do_layout): Track .debug_info
	and .debug_types sections, call Layout::add_to_gdb_index.
	(Sized_relobj_incr::do_section_name): Implement.
	(Sized_relobj_incr::do_section_contents): Adjust parameter list and
	return type; Implement.
	(Sized_incr_dynobj::do_section_contents): Adjust parameter list and
	return type.
	* incremental.h (Sized_relobj_incr::do_section_contents): Adjust
	parameter list and return type.
	(Sized_incr_dynobj::do_section_contents): Likewise.
	* layout.cc: Include gdb-index.h.
	(Layout::Layout): Initialize gdb_index_data_.
	(Layout::init_fixed_output_section): Check for .gdb_index section.
	(Layout::add_to_gdb_index): New function. Instantiate.
	* layout.h: Add forward declaration for class Gdb_index.
	(Layout::add_to_gdb_index): New member function.
	(Layout::gdb_index_data_): New data member.
	* main.cc: Include gdb-index.h.
	(main): Print statistics for gdb index.
	* object.cc (Object::section_contents): Move code into
	do_section_contents.
	(need_decompressed_section): Check for sections needed when building
	gdb index.
	(build_compressed_section_map): Likewise.
	(Sized_relobj_file::do_read_symbols): Need local symbols when building
	gdb index.
	(Sized_relobj_file::do_layout): Track .debug_info and .debug_types
	sections; call Layout::add_to_gdb_index.
	(Sized_relobj_file::do_decompressed_section_contents): Call
	do_section_contents directly.
	* object.h (Object::do_section_contents): Adjust parameter list and
	return type.
	(Object::do_decompressed_section_contents): Call do_section_contents
	directly.
	(Sized_relobj_file::do_section_contents): Adjust parameter list and
	return type.
	* options.h (class General_options): Add --gdb-index option.
	* plugin.cc (Sized_pluginobj::do_section_contents): Adjust parameter
	list and return type.
	* plugin.h (Sized_pluginobj::do_section_contents): Likewise.
	* reloc.h (Track_relocs::checkpoint): New function.
	(Track_relocs::reset): New function.

	* testsuite/Makefile.am (gdb_index_test_1.sh, gdb_index_test_2.sh):
	New test cases.
	* testsuite/Makefile.in: Regenerate.
	* testsuite/gdb_index_test.cc: New test source file.
	* testsuite/gdb_index_test_1.sh: New test source file.
	* testsuite/gdb_index_test_2.sh: New test source file.

1 files changed, 1229 insertions, 0 deletions

diff --git a/gold/gdb-index.cc b/gold/gdb-index.cc
new file mode 100644
index 0000000000..11b732a21c
--- /dev/null
+++ b/gold/gdb-index.cc
@@ -0,0 +1,1229 @@
+// gdb-index.cc -- generate .gdb_index section for fast debug lookup
+
+// Copyright 2012 Free Software Foundation, Inc.
+// Written by Cary Coutant <ccoutant@google.com>.
+
+// This file is part of gold.
+
+// This program 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 of the License, or
+// (at your option) any later version.
+
+// This program 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.
+
+// You should have received a copy of the GNU General Public License
+// along with this program; if not, write to the Free Software
+// Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
+// MA 02110-1301, USA.
+
+#include "gold.h"
+
+#include "gdb-index.h"
+#include "dwarf_reader.h"
+#include "dwarf.h"
+#include "object.h"
+#include "output.h"
+#include "demangle.h"
+
+namespace gold
+{
+
+const int gdb_index_version = 5;
+
+// Sizes of various records in the .gdb_index section.
+const int gdb_index_offset_size = 4;
+const int gdb_index_hdr_size = 6 * gdb_index_offset_size;
+const int gdb_index_cu_size = 16;
+const int gdb_index_tu_size = 24;
+const int gdb_index_addr_size = 16 + gdb_index_offset_size;
+const int gdb_index_sym_size = 2 * gdb_index_offset_size;
+
+// This class manages the hashed symbol table for the .gdb_index section.
+// It is essentially equivalent to the hashtab implementation in libiberty,
+// but is copied into gdb sources and here for compatibility because its
+// data structure is exposed on disk.
+
+template <typename T>
+class Gdb_hashtab
+{
+ public:
+  Gdb_hashtab()
+    : size_(0), capacity_(0), hashtab_(NULL)
+  { }
+
+  ~Gdb_hashtab()
+  {
+    for (size_t i = 0; i < this->capacity_; ++i)
+      if (this->hashtab_[i] != NULL)
+	delete this->hashtab_[i];
+    delete[] this->hashtab_;
+  }
+
+  // Add a symbol.
+  T*
+  add(T* symbol)
+  {
+    // Resize the hash table if necessary.
+    if (4 * this->size_ / 3 >= this->capacity_)
+      this->expand();
+
+    T** slot = this->find_slot(symbol);
+    if (*slot == NULL)
+      {
+	++this->size_;
+	*slot = symbol;
+      }
+
+    return *slot;
+  }
+
+  // Return the current size.
+  size_t
+  size() const
+  { return this->size_; }
+
+  // Return the current capacity.
+  size_t
+  capacity() const
+  { return this->capacity_; }
+
+  // Return the contents of slot N.
+  T*
+  operator[](size_t n)
+  { return this->hashtab_[n]; }
+
+ private:
+  // Find a symbol in the hash table, or return an empty slot if
+  // the symbol is not in the table.
+  T**
+  find_slot(T* symbol)
+  {
+    unsigned int index = symbol->hash() & (this->capacity_ - 1);
+    unsigned int step = ((symbol->hash() * 17) & (this->capacity_ - 1)) | 1;
+
+    for (;;)
+      {
+	if (this->hashtab_[index] == NULL
+	    || this->hashtab_[index]->equal(symbol))
+	  return &this->hashtab_[index];
+	index = (index + step) & (this->capacity_ - 1);
+      }
+  }
+
+  // Expand the hash table.
+  void
+  expand()
+  {
+    if (this->capacity_ == 0)
+      {
+	// Allocate the hash table for the first time.
+	this->capacity_ = Gdb_hashtab::initial_size;
+	this->hashtab_ = new T*[this->capacity_];
+	memset(this->hashtab_, 0, this->capacity_ * sizeof(T*));
+      }
+    else
+      {
+	// Expand and rehash.
+	unsigned int old_cap = this->capacity_;
+	T** old_hashtab = this->hashtab_;
+	this->capacity_ *= 2;
+	this->hashtab_ = new T*[this->capacity_];
+	memset(this->hashtab_, 0, this->capacity_ * sizeof(T*));
+	for (size_t i = 0; i < old_cap; ++i)
+	  {
+	    if (old_hashtab[i] != NULL)
+	      {
+		T** slot = this->find_slot(old_hashtab[i]);
+		*slot = old_hashtab[i];
+	      }
+	  }
+	delete[] old_hashtab;
+      }
+  }
+
+  // Initial size of the hash table; must be a power of 2.
+  static const int initial_size = 1024;
+  size_t size_;
+  size_t capacity_;
+  T** hashtab_;
+};
+
+// The hash function for strings in the mapped index.  This is copied
+// directly from gdb/dwarf2read.c.
+
+static unsigned int
+mapped_index_string_hash(const unsigned char* str)
+{
+  unsigned int r = 0;
+  unsigned char c;
+
+  while ((c = *str++) != 0)
+    {
+      if (gdb_index_version >= 5)
+	c = tolower (c);
+      r = r * 67 + c - 113;
+    }
+
+  return r;
+}
+
+// A specialization of Dwarf_info_reader, for building the .gdb_index.
+
+class Gdb_index_info_reader : public Dwarf_info_reader
+{
+ public:
+  Gdb_index_info_reader(bool is_type_unit,
+			Relobj* object,
+			const unsigned char* symbols,
+			off_t symbols_size,
+			unsigned int shndx,
+			unsigned int reloc_shndx,
+			unsigned int reloc_type,
+			Gdb_index* gdb_index)
+    : Dwarf_info_reader(is_type_unit, object, symbols, symbols_size, shndx,
+			reloc_shndx, reloc_type),
+      gdb_index_(gdb_index), cu_index_(0), cu_language_(0)
+  { }
+
+  ~Gdb_index_info_reader()
+  { this->clear_declarations(); }
+
+  // Print usage statistics.
+  static void
+  print_stats();
+
+ protected:
+  // Visit a compilation unit.
+  virtual void
+  visit_compilation_unit(off_t cu_offset, off_t cu_length, Dwarf_die*);
+
+  // Visit a type unit.
+  virtual void
+  visit_type_unit(off_t tu_offset, off_t type_offset, uint64_t signature,
+		  Dwarf_die*);
+
+ private:
+  // A map for recording DIEs we've seen that may be referred to be
+  // later DIEs (via DW_AT_specification or DW_AT_abstract_origin).
+  // The map is indexed by a DIE offset within the compile unit.
+  // PARENT_OFFSET_ is the offset of the DIE that represents the
+  // outer context, and NAME_ is a pointer to a component of the
+  // fully-qualified name.
+  // Normally, the names we point to are in a string table, so we don't
+  // have to manage them, but when we have a fully-qualified name
+  // computed, we put it in the table, and set PARENT_OFFSET_ to -1
+  // indicate a string that we are managing.
+  struct Declaration_pair
+  {
+    Declaration_pair(off_t parent_offset, const char* name)
+      : parent_offset_(parent_offset), name_(name)
+    { }
+
+    off_t parent_offset_;
+    const char* name_; 
+  };
+  typedef Unordered_map<off_t, Declaration_pair> Declaration_map;
+
+  // Visit a top-level DIE.
+  void
+  visit_top_die(Dwarf_die* die);
+
+  // Visit the children of a DIE.
+  void
+  visit_children(Dwarf_die* die, Dwarf_die* context);
+
+  // Visit a DIE.
+  void
+  visit_die(Dwarf_die* die, Dwarf_die* context);
+
+  // Visit the children of a DIE.
+  void
+  visit_children_for_decls(Dwarf_die* die);
+
+  // Visit a DIE.
+  void
+  visit_die_for_decls(Dwarf_die* die, Dwarf_die* context);
+
+  // Guess a fully-qualified name for a class type, based on member function
+  // linkage names.
+  std::string
+  guess_full_class_name(Dwarf_die* die);
+
+  // Add a declaration DIE to the table of declarations.
+  void
+  add_declaration(Dwarf_die* die, Dwarf_die* context);
+
+  // Add a declaration whose fully-qualified name is already known.
+  void
+  add_declaration_with_full_name(Dwarf_die* die, const char* full_name);
+
+  // Return the context for a DIE whose parent is at DIE_OFFSET.
+  std::string
+  get_context(off_t die_offset);
+
+  // Construct a fully-qualified name for DIE.
+  std::string
+  get_qualified_name(Dwarf_die* die, Dwarf_die* context);
+
+  // Record the address ranges for a compilation unit.
+  void
+  record_cu_ranges(Dwarf_die* die);
+
+  // Read the .debug_pubnames and .debug_pubtypes tables.
+  bool
+  read_pubnames_and_pubtypes(Dwarf_die* die);
+
+  // Clear the declarations map.
+  void
+  clear_declarations();
+
+  // The Gdb_index section.
+  Gdb_index* gdb_index_;
+  // The current CU index (negative for a TU).
+  int cu_index_;
+  // The language of the current CU or TU.
+  unsigned int cu_language_;
+  // Map from DIE offset to (parent offset, name) pair,
+  // for DW_AT_specification.
+  Declaration_map declarations_;
+
+  // Statistics.
+  // Total number of DWARF compilation units processed.
+  static unsigned int dwarf_cu_count;
+  // Number of DWARF compilation units with pubnames/pubtypes.
+  static unsigned int dwarf_cu_nopubnames_count;
+  // Total number of DWARF type units processed.
+  static unsigned int dwarf_tu_count;
+  // Number of DWARF type units with pubnames/pubtypes.
+  static unsigned int dwarf_tu_nopubnames_count;
+};
+
+// Total number of DWARF compilation units processed.
+unsigned int Gdb_index_info_reader::dwarf_cu_count = 0;
+// Number of DWARF compilation units without pubnames/pubtypes.
+unsigned int Gdb_index_info_reader::dwarf_cu_nopubnames_count = 0;
+// Total number of DWARF type units processed.
+unsigned int Gdb_index_info_reader::dwarf_tu_count = 0;
+// Number of DWARF type units without pubnames/pubtypes.
+unsigned int Gdb_index_info_reader::dwarf_tu_nopubnames_count = 0;
+
+// Process a compilation unit and parse its child DIE.
+
+void
+Gdb_index_info_reader::visit_compilation_unit(off_t cu_offset, off_t cu_length,
+					      Dwarf_die* root_die)
+{
+  ++Gdb_index_info_reader::dwarf_cu_count;
+  this->cu_index_ = this->gdb_index_->add_comp_unit(cu_offset, cu_length);
+  this->visit_top_die(root_die);
+}
+
+// Process a type unit and parse its child DIE.
+
+void
+Gdb_index_info_reader::visit_type_unit(off_t tu_offset, off_t type_offset,
+				       uint64_t signature, Dwarf_die* root_die)
+{
+  ++Gdb_index_info_reader::dwarf_tu_count;
+  // Use a negative index to flag this as a TU instead of a CU.
+  this->cu_index_ = -1 - this->gdb_index_->add_type_unit(tu_offset, type_offset,
+							 signature);
+  this->visit_top_die(root_die);
+}
+
+// Process a top-level DIE.
+// For compile_unit DIEs, record the address ranges.  For all
+// interesting tags, add qualified names to the symbol table
+// and process interesting children.  We may need to process
+// certain children just for saving declarations that might be
+// referenced by later DIEs with a DW_AT_specification attribute.
+
+void
+Gdb_index_info_reader::visit_top_die(Dwarf_die* die)
+{
+  this->clear_declarations();
+
+  switch (die->tag())
+    {
+      case elfcpp::DW_TAG_compile_unit:
+      case elfcpp::DW_TAG_type_unit:
+	this->cu_language_ = die->int_attribute(elfcpp::DW_AT_language);
+	// Check for languages that require specialized knowledge to
+	// construct fully-qualified names, that we don't yet support.
+	if (this->cu_language_ == elfcpp::DW_LANG_Ada83
+	    || this->cu_language_ == elfcpp::DW_LANG_Fortran77
+	    || this->cu_language_ == elfcpp::DW_LANG_Fortran90
+	    || this->cu_language_ == elfcpp::DW_LANG_Java
+	    || this->cu_language_ == elfcpp::DW_LANG_Ada95
+	    || this->cu_language_ == elfcpp::DW_LANG_Fortran95)
+	  {
+	    gold_warning(_("%s: --gdb-index currently supports "
+			   "only C and C++ languages"),
+			 this->object()->name().c_str());
+	    return;
+	  }
+	if (die->tag() == elfcpp::DW_TAG_compile_unit)
+	  this->record_cu_ranges(die);
+	// If there is a pubnames and/or pubtypes section for this
+	// compilation unit, use those; otherwise, parse the DWARF
+	// info to extract the names.
+	if (!this->read_pubnames_and_pubtypes(die))
+	  {
+	    if (die->tag() == elfcpp::DW_TAG_compile_unit)
+	      ++Gdb_index_info_reader::dwarf_cu_nopubnames_count;
+	    else
+	      ++Gdb_index_info_reader::dwarf_tu_nopubnames_count;
+	    this->visit_children(die, NULL);
+	  }
+	break;
+      default:
+	// The top level DIE should be one of the above.
+	gold_warning(_("%s: top level DIE is not DW_TAG_compile_unit "
+		       "or DW_TAG_type_unit"),
+		     this->object()->name().c_str());
+	return;
+    }
+
+}
+
+// Visit the children of PARENT, looking for symbols to add to the index.
+// CONTEXT points to the DIE to use for constructing the qualified name --
+// NULL if PARENT is the top-level DIE; otherwise it is the same as PARENT.
+
+void
+Gdb_index_info_reader::visit_children(Dwarf_die* parent, Dwarf_die* context)
+{
+  off_t next_offset = 0;
+  for (off_t die_offset = parent->child_offset();
+       die_offset != 0;
+       die_offset = next_offset)
+    {
+      Dwarf_die die(this, die_offset, parent);
+      if (die.tag() == 0)
+	break;
+      this->visit_die(&die, context);
+      next_offset = die.sibling_offset();
+    }
+}
+
+// Visit a child DIE, looking for symbols to add to the index.
+// CONTEXT is the parent DIE, used for constructing the qualified name;
+// it is NULL if the parent DIE is the top-level DIE.
+
+void
+Gdb_index_info_reader::visit_die(Dwarf_die* die, Dwarf_die* context)
+{
+  switch (die->tag())
+    {
+      case elfcpp::DW_TAG_subprogram:
+      case elfcpp::DW_TAG_constant:
+      case elfcpp::DW_TAG_variable:
+      case elfcpp::DW_TAG_enumerator:
+      case elfcpp::DW_TAG_base_type:
+	if (die->is_declaration())
+	  this->add_declaration(die, context);
+	else
+	  {
+	    // If the DIE is not a declaration, add it to the index.
+	    std::string full_name = this->get_qualified_name(die, context);
+	    if (!full_name.empty())
+	      this->gdb_index_->add_symbol(this->cu_index_, full_name.c_str());
+	  }
+	break;
+      case elfcpp::DW_TAG_typedef:
+      case elfcpp::DW_TAG_union_type:
+      case elfcpp::DW_TAG_class_type:
+      case elfcpp::DW_TAG_interface_type:
+      case elfcpp::DW_TAG_structure_type:
+      case elfcpp::DW_TAG_enumeration_type:
+      case elfcpp::DW_TAG_subrange_type:
+      case elfcpp::DW_TAG_namespace:
+	{
+	  std::string full_name;
+	  
+	  // For classes at the top level, we need to look for a
+	  // member function with a linkage name in order to get
+	  // the properly-canonicalized name.
+	  if (context == NULL
+	      && (die->tag() == elfcpp::DW_TAG_class_type
+		  || die->tag() == elfcpp::DW_TAG_structure_type
+		  || die->tag() == elfcpp::DW_TAG_union_type))
+	    full_name.assign(this->guess_full_class_name(die));
+
+	  // Because we will visit the children, we need to add this DIE
+	  // to the declarations table.
+	  if (full_name.empty())
+	    this->add_declaration(die, context);
+	  else
+	    this->add_declaration_with_full_name(die, full_name.c_str());
+
+	  // If the DIE is not a declaration, add it to the index.
+	  // Gdb stores a namespace in the index even when it is
+	  // a declaration.
+	  if (die->tag() == elfcpp::DW_TAG_namespace
+	      || !die->is_declaration())
+	    {
+	      if (full_name.empty())
+		full_name = this->get_qualified_name(die, context);
+	      if (!full_name.empty())
+		this->gdb_index_->add_symbol(this->cu_index_,
+					     full_name.c_str());
+	    }
+
+	  // We're interested in the children only for namespaces and
+	  // enumeration types.  For enumeration types, we do not include
+	  // the enumeration tag as part of the full name.  For other tags,
+	  // visit the children only to collect declarations.
+	  if (die->tag() == elfcpp::DW_TAG_namespace
+	      || die->tag() == elfcpp::DW_TAG_enumeration_type)
+	    this->visit_children(die, die);
+	  else
+	    this->visit_children_for_decls(die);
+	}
+	break;
+      default:
+	break;
+    }
+}
+
+// Visit the children of PARENT, looking only for declarations that
+// may be referenced by later specification DIEs.
+
+void
+Gdb_index_info_reader::visit_children_for_decls(Dwarf_die* parent)
+{
+  off_t next_offset = 0;
+  for (off_t die_offset = parent->child_offset();
+       die_offset != 0;
+       die_offset = next_offset)
+    {
+      Dwarf_die die(this, die_offset, parent);
+      if (die.tag() == 0)
+	break;
+      this->visit_die_for_decls(&die, parent);
+      next_offset = die.sibling_offset();
+    }
+}
+
+// Visit a child DIE, looking only for declarations that
+// may be referenced by later specification DIEs.
+
+void
+Gdb_index_info_reader::visit_die_for_decls(Dwarf_die* die, Dwarf_die* context)
+{
+  switch (die->tag())
+    {
+      case elfcpp::DW_TAG_subprogram:
+      case elfcpp::DW_TAG_constant:
+      case elfcpp::DW_TAG_variable:
+      case elfcpp::DW_TAG_enumerator:
+      case elfcpp::DW_TAG_base_type:
+	{
+	  if (die->is_declaration())
+	    this->add_declaration(die, context);
+	}
+	break;
+      case elfcpp::DW_TAG_typedef:
+      case elfcpp::DW_TAG_union_type:
+      case elfcpp::DW_TAG_class_type:
+      case elfcpp::DW_TAG_interface_type:
+      case elfcpp::DW_TAG_structure_type:
+      case elfcpp::DW_TAG_enumeration_type:
+      case elfcpp::DW_TAG_subrange_type:
+      case elfcpp::DW_TAG_namespace:
+	{
+	  if (die->is_declaration())
+	    this->add_declaration(die, context);
+	  this->visit_children_for_decls(die);
+	}
+	break;
+      default:
+	break;
+    }
+}
+
+// Extract the class name from the linkage name of a member function.
+// This code is adapted from ../gdb/cp-support.c.
+
+#define d_left(dc) (dc)->u.s_binary.left
+#define d_right(dc) (dc)->u.s_binary.right
+
+static char*
+class_name_from_linkage_name(const char* linkage_name)
+{
+  void* storage;
+  struct demangle_component* tree =
+      cplus_demangle_v3_components(linkage_name, DMGL_NO_OPTS, &storage);
+  if (tree == NULL)
+    return NULL;
+
+  int done = 0;
+
+  // First strip off any qualifiers, if we have a function or
+  // method.
+  while (!done)
+    switch (tree->type)
+      {
+	case DEMANGLE_COMPONENT_CONST:
+	case DEMANGLE_COMPONENT_RESTRICT:
+	case DEMANGLE_COMPONENT_VOLATILE:
+	case DEMANGLE_COMPONENT_CONST_THIS:
+	case DEMANGLE_COMPONENT_RESTRICT_THIS:
+	case DEMANGLE_COMPONENT_VOLATILE_THIS:
+	case DEMANGLE_COMPONENT_VENDOR_TYPE_QUAL:
+	  tree = d_left(tree);
+	  break;
+	default:
+	  done = 1;
+	  break;
+      }
+
+  // If what we have now is a function, discard the argument list.
+  if (tree->type == DEMANGLE_COMPONENT_TYPED_NAME)
+    tree = d_left(tree);
+
+  // If what we have now is a template, strip off the template
+  // arguments.  The left subtree may be a qualified name.
+  if (tree->type == DEMANGLE_COMPONENT_TEMPLATE)
+    tree = d_left(tree);
+
+  // What we have now should be a name, possibly qualified.
+  // Additional qualifiers could live in the left subtree or the right
+  // subtree.  Find the last piece.
+  done = 0;
+  struct demangle_component* prev_comp = NULL;
+  struct demangle_component* cur_comp = tree;
+  while (!done)
+    switch (cur_comp->type)
+      {
+	case DEMANGLE_COMPONENT_QUAL_NAME:
+	case DEMANGLE_COMPONENT_LOCAL_NAME:
+	  prev_comp = cur_comp;
+	  cur_comp = d_right(cur_comp);
+	  break;
+	case DEMANGLE_COMPONENT_TEMPLATE:
+	case DEMANGLE_COMPONENT_NAME:
+	case DEMANGLE_COMPONENT_CTOR:
+	case DEMANGLE_COMPONENT_DTOR:
+	case DEMANGLE_COMPONENT_OPERATOR:
+	case DEMANGLE_COMPONENT_EXTENDED_OPERATOR:
+	  done = 1;
+	  break;
+	default:
+	  done = 1;
+	  cur_comp = NULL;
+	  break;
+      }
+
+  char* ret = NULL;
+  if (cur_comp != NULL && prev_comp != NULL)
+    {
+      // We want to discard the rightmost child of PREV_COMP.
+      *prev_comp = *d_left(prev_comp);
+      size_t allocated_size;
+      ret = cplus_demangle_print(DMGL_NO_OPTS, tree, 30, &allocated_size);
+    }
+
+  free(storage);
+  return ret;
+}
+
+// Guess a fully-qualified name for a class type, based on member function
+// linkage names.  This is needed for class/struct/union types at the
+// top level, because GCC does not always properly embed them within
+// the namespace.  As in gdb, we look for a member function with a linkage
+// name and extract the qualified name from the demangled name.
+
+std::string
+Gdb_index_info_reader::guess_full_class_name(Dwarf_die* die)
+{
+  std::string full_name;
+  off_t next_offset = 0;
+  
+  // This routine scans ahead in the DIE structure, possibly advancing
+  // the relocation tracker beyond the current DIE.  We need to checkpoint
+  // the tracker and reset it when we're done.
+  uint64_t checkpoint = this->get_reloc_checkpoint();
+
+  for (off_t child_offset = die->child_offset();
+       child_offset != 0;
+       child_offset = next_offset)
+    {
+      Dwarf_die child(this, child_offset, die);
+      if (child.tag() == 0)
+	break;
+      if (child.tag() == elfcpp::DW_TAG_subprogram)
+        {
+          const char* linkage_name = child.linkage_name();
+	  if (linkage_name != NULL)
+	    {
+	      char* guess = class_name_from_linkage_name(linkage_name);
+	      if (guess != NULL)
+	        {
+		  full_name.assign(guess);
+		  free(guess);
+		  break;
+	        }
+	    }
+        }
+      next_offset = child.sibling_offset();
+    }
+
+  this->reset_relocs(checkpoint);
+  return full_name;
+}
+
+// Add a declaration DIE to the table of declarations.
+
+void
+Gdb_index_info_reader::add_declaration(Dwarf_die* die, Dwarf_die* context)
+{
+  const char* name = die->name();
+
+  off_t parent_offset = context != NULL ? context->offset() : 0;
+
+  // If this DIE has a DW_AT_specification or DW_AT_abstract_origin
+  // attribute, use the parent and name from the earlier declaration.
+  off_t spec = die->specification();
+  if (spec == 0)
+    spec = die->abstract_origin();
+  if (spec > 0)
+    {
+      Declaration_map::iterator it = this->declarations_.find(spec);
+      if (it != this->declarations_.end())
+        {
+	  parent_offset = it->second.parent_offset_;
+	  name = it->second.name_;
+        }
+    }
+
+  if (name == NULL)
+    {
+      if (die->tag() == elfcpp::DW_TAG_namespace)
+        name = "(anonymous namespace)";
+      else if (die->tag() == elfcpp::DW_TAG_union_type)
+        name = "(anonymous union)";
+      else
+        name = "(unknown)";
+    }
+
+  Declaration_pair decl(parent_offset, name);
+  this->declarations_.insert(std::make_pair(die->offset(), decl));
+}
+
+// Add a declaration whose fully-qualified name is already known.
+// In the case where we had to get the canonical name by demangling
+// a linkage name, this ensures we use that name instead of the one
+// provided in DW_AT_name.
+
+void
+Gdb_index_info_reader::add_declaration_with_full_name(
+    Dwarf_die* die,
+    const char* full_name)
+{
+  // We need to copy the name.
+  int len = strlen(full_name);
+  char* copy = new char[len + 1];
+  memcpy(copy, full_name, len + 1);
+
+  // Flag that we now manage the memory this points to.
+  Declaration_pair decl(-1, copy);
+  this->declarations_.insert(std::make_pair(die->offset(), decl));
+}
+
+// Return the context for a DIE whose parent is at DIE_OFFSET.
+
+std::string
+Gdb_index_info_reader::get_context(off_t die_offset)
+{
+  std::string context;
+  Declaration_map::iterator it = this->declarations_.find(die_offset);
+  if (it != this->declarations_.end())
+    {
+      off_t parent_offset = it->second.parent_offset_;
+      if (parent_offset > 0)
+	{
+	  context = get_context(parent_offset);
+	  context.append("::");
+	}
+      if (it->second.name_ != NULL)
+        context.append(it->second.name_);
+    }
+  return context;
+}
+
+// Construct the fully-qualified name for DIE.
+
+std::string
+Gdb_index_info_reader::get_qualified_name(Dwarf_die* die, Dwarf_die* context)
+{
+  std::string full_name;
+  const char* name = die->name();
+
+  off_t parent_offset = context != NULL ? context->offset() : 0;
+
+  // If this DIE has a DW_AT_specification or DW_AT_abstract_origin
+  // attribute, use the parent and name from the earlier declaration.
+  off_t spec = die->specification();
+  if (spec == 0)
+    spec = die->abstract_origin();
+  if (spec > 0)
+    {
+      Declaration_map::iterator it = this->declarations_.find(spec);
+      if (it != this->declarations_.end())
+        {
+	  parent_offset = it->second.parent_offset_;
+	  name = it->second.name_;
+        }
+    }
+
+  if (name == NULL && die->tag() == elfcpp::DW_TAG_namespace)
+    name = "(anonymous namespace)";
+  else if (name == NULL)
+    return full_name;
+
+  // If this is an enumerator constant, skip the immediate parent,
+  // which is the enumeration tag.
+  if (die->tag() == elfcpp::DW_TAG_enumerator)
+    {
+      Declaration_map::iterator it = this->declarations_.find(parent_offset);
+      if (it != this->declarations_.end())
+	parent_offset = it->second.parent_offset_;
+    }
+
+  if (parent_offset > 0)
+    {
+      full_name.assign(this->get_context(parent_offset));
+      full_name.append("::");
+    }
+  full_name.append(name);
+
+  return full_name;
+}
+
+// Record the address ranges for a compilation unit.
+
+void
+Gdb_index_info_reader::record_cu_ranges(Dwarf_die* die)
+{
+  unsigned int shndx;
+  unsigned int shndx2;
+
+  off_t ranges_offset = die->ref_attribute(elfcpp::DW_AT_ranges, &shndx);
+  if (ranges_offset != -1)
+    {
+      Dwarf_range_list* ranges = this->read_range_list(shndx, ranges_offset);
+      if (ranges != NULL)
+	this->gdb_index_->add_address_range_list(this->object(),
+						 this->cu_index_, ranges);
+      return;
+    }
+
+  off_t low_pc = die->ref_attribute(elfcpp::DW_AT_low_pc, &shndx);
+  off_t high_pc = die->ref_attribute(elfcpp::DW_AT_high_pc, &shndx2);
+  if (low_pc != 0 && high_pc != 0 && low_pc != -1 && high_pc != -1)
+    {
+      if (shndx != shndx2)
+        {
+	  gold_warning(_("%s: DWARF info may be corrupt; low_pc and high_pc "
+			 "are in different sections"),
+		       this->object()->name().c_str());
+	  return;
+	}
+      if (shndx == 0 || this->object()->is_section_included(shndx))
+        {
+	  Dwarf_range_list* ranges = new Dwarf_range_list();
+	  ranges->add(shndx, low_pc, high_pc);
+	  this->gdb_index_->add_address_range_list(this->object(),
+						   this->cu_index_, ranges);
+        }
+    }
+}
+
+// Read the .debug_pubnames and .debug_pubtypes tables for the CU or TU.
+// Returns TRUE if either a pubnames or pubtypes section was found.
+
+bool
+Gdb_index_info_reader::read_pubnames_and_pubtypes(Dwarf_die* die)
+{
+  bool ret = false;
+
+  // If we find a DW_AT_GNU_pubnames attribute, read the pubnames table.
+  unsigned int pubnames_shndx;
+  off_t pubnames_offset = die->ref_attribute(elfcpp::DW_AT_GNU_pubnames,
+					     &pubnames_shndx);
+  if (pubnames_offset != -1)
+    {
+      if (this->gdb_index_->pubnames_read(pubnames_shndx, pubnames_offset))
+	ret = true;
+      else
+	{
+	  Dwarf_pubnames_table pubnames(false);
+	  if (!pubnames.read_section(this->object(), pubnames_shndx))
+	    return false;
+	  if (!pubnames.read_header(pubnames_offset))
+	    return false;
+	  while (true)
+	    {
+	      const char* name = pubnames.next_name();
+	      if (name == NULL)
+		break;
+	      this->gdb_index_->add_symbol(this->cu_index_, name);
+	    }
+	  ret = true;
+	}
+    }
+
+  // If we find a DW_AT_GNU_pubtypes attribute, read the pubtypes table.
+  unsigned int pubtypes_shndx;
+  off_t pubtypes_offset = die->ref_attribute(elfcpp::DW_AT_GNU_pubtypes,
+					     &pubtypes_shndx);
+  if (pubtypes_offset != -1)
+    {
+      if (this->gdb_index_->pubtypes_read(pubtypes_shndx, pubtypes_offset))
+	ret = true;
+      else
+	{
+	  Dwarf_pubnames_table pubtypes(true);
+	  if (!pubtypes.read_section(this->object(), pubtypes_shndx))
+	    return false;
+	  if (!pubtypes.read_header(pubtypes_offset))
+	    return false;
+	  while (true)
+	    {
+	      const char* name = pubtypes.next_name();
+	      if (name == NULL)
+		break;
+	      this->gdb_index_->add_symbol(this->cu_index_, name);
+	    }
+	  ret = true;
+	}
+    }
+
+  return ret;
+}
+
+// Clear the declarations map.
+void
+Gdb_index_info_reader::clear_declarations()
+{
+  // Free strings in memory we manage.
+  for (Declaration_map::iterator it = this->declarations_.begin();
+       it != this->declarations_.end();
+       ++it)
+    {
+      if (it->second.parent_offset_ == -1)
+	delete[] it->second.name_;
+    }
+
+  this->declarations_.clear();
+}
+
+// Print usage statistics.
+void
+Gdb_index_info_reader::print_stats()
+{
+  fprintf(stderr, _("%s: DWARF CUs: %u\n"),
+          program_name, Gdb_index_info_reader::dwarf_cu_count);
+  fprintf(stderr, _("%s: DWARF CUs without pubnames/pubtypes: %u\n"),
+          program_name, Gdb_index_info_reader::dwarf_cu_nopubnames_count);
+  fprintf(stderr, _("%s: DWARF TUs: %u\n"),
+          program_name, Gdb_index_info_reader::dwarf_tu_count);
+  fprintf(stderr, _("%s: DWARF TUs without pubnames/pubtypes: %u\n"),
+          program_name, Gdb_index_info_reader::dwarf_tu_nopubnames_count);
+}
+
+// Class Gdb_index.
+
+// Construct the .gdb_index section.
+
+Gdb_index::Gdb_index(Output_section* gdb_index_section)
+  : Output_section_data(4),
+    gdb_index_section_(gdb_index_section),
+    comp_units_(),
+    type_units_(),
+    ranges_(),
+    cu_vector_list_(),
+    cu_vector_offsets_(NULL),
+    stringpool_(),
+    tu_offset_(0),
+    addr_offset_(0),
+    symtab_offset_(0),
+    cu_pool_offset_(0),
+    stringpool_offset_(0),
+    pubnames_shndx_(0),
+    pubnames_offset_(0),
+    pubtypes_shndx_(0),
+    pubtypes_offset_(0)
+{
+  this->gdb_symtab_ = new Gdb_hashtab<Gdb_symbol>();
+}
+
+Gdb_index::~Gdb_index()
+{
+  // Free the memory used by the symbol table.
+  delete this->gdb_symtab_;
+  // Free the memory used by the CU vectors.
+  for (unsigned int i = 0; i < this->cu_vector_list_.size(); ++i)
+    delete this->cu_vector_list_[i];
+}
+
+// Scan a .debug_info or .debug_types input section.
+
+void
+Gdb_index::scan_debug_info(bool is_type_unit,
+			   Relobj* object,
+			   const unsigned char* symbols,
+			   off_t symbols_size,
+			   unsigned int shndx,
+			   unsigned int reloc_shndx,
+			   unsigned int reloc_type)
+{
+  Gdb_index_info_reader dwinfo(is_type_unit, object,
+			       symbols, symbols_size,
+			       shndx, reloc_shndx,
+			       reloc_type, this);
+  dwinfo.parse();
+}
+
+// Add a symbol.
+
+void
+Gdb_index::add_symbol(int cu_index, const char* sym_name)
+{
+  unsigned int hash = mapped_index_string_hash(
+      reinterpret_cast<const unsigned char*>(sym_name));
+  Gdb_symbol* sym = new Gdb_symbol();
+  this->stringpool_.add(sym_name, true, &sym->name_key);
+  sym->hashval = hash;
+  sym->cu_vector_index = 0;
+
+  Gdb_symbol* found = this->gdb_symtab_->add(sym);
+  if (found == sym)
+    {
+      // New symbol -- allocate a new CU index vector.
+      found->cu_vector_index = this->cu_vector_list_.size();
+      this->cu_vector_list_.push_back(new Cu_vector());
+    }
+  else
+    {
+      // Found an existing symbol -- append to the existing
+      // CU index vector.
+      delete sym;
+    }
+
+  // Add the CU index to the vector list for this symbol,
+  // if it's not already on the list.  We only need to
+  // check the last added entry.
+  Cu_vector* cu_vec = this->cu_vector_list_[found->cu_vector_index];
+  if (cu_vec->size() == 0 || cu_vec->back() != cu_index)
+    cu_vec->push_back(cu_index);
+}
+
+// Return TRUE if we have already processed the pubnames set at
+// OFFSET in section SHNDX
+
+bool
+Gdb_index::pubnames_read(unsigned int shndx, off_t offset)
+{
+  bool ret = (this->pubnames_shndx_ == shndx
+	      && this->pubnames_offset_ == offset);
+  this->pubnames_shndx_ = shndx;
+  this->pubnames_offset_ = offset;
+  return ret;
+}
+
+// Return TRUE if we have already processed the pubtypes set at
+// OFFSET in section SHNDX
+
+bool
+Gdb_index::pubtypes_read(unsigned int shndx, off_t offset)
+{
+  bool ret = (this->pubtypes_shndx_ == shndx
+	      && this->pubtypes_offset_ == offset);
+  this->pubtypes_shndx_ = shndx;
+  this->pubtypes_offset_ = offset;
+  return ret;
+}
+
+// Set the size of the .gdb_index section.
+
+void
+Gdb_index::set_final_data_size()
+{
+  // Finalize the string pool.
+  this->stringpool_.set_string_offsets();
+
+  // Compute the total size of the CU vectors.
+  // For each CU vector, include one entry for the count at the
+  // beginning of the vector.
+  unsigned int cu_vector_count = this->cu_vector_list_.size();
+  unsigned int cu_vector_size = 0;
+  this->cu_vector_offsets_ = new off_t[cu_vector_count];
+  for (unsigned int i = 0; i < cu_vector_count; ++i)
+    {
+      Cu_vector* cu_vec = this->cu_vector_list_[i];
+      cu_vector_offsets_[i] = cu_vector_size;
+      cu_vector_size += gdb_index_offset_size * (cu_vec->size() + 1);
+    }
+
+  // Assign relative offsets to each portion of the index,
+  // and find the total size of the section.
+  section_size_type data_size = gdb_index_hdr_size;
+  data_size += this->comp_units_.size() * gdb_index_cu_size;
+  this->tu_offset_ = data_size;
+  data_size += this->type_units_.size() * gdb_index_tu_size;
+  this->addr_offset_ = data_size;
+  for (unsigned int i = 0; i < this->ranges_.size(); ++i)
+    data_size += this->ranges_[i].ranges->size() * gdb_index_addr_size;
+  this->symtab_offset_ = data_size;
+  data_size += this->gdb_symtab_->capacity() * gdb_index_sym_size;
+  this->cu_pool_offset_ = data_size;
+  data_size += cu_vector_size;
+  this->stringpool_offset_ = data_size;
+  data_size += this->stringpool_.get_strtab_size();
+
+  this->set_data_size(data_size);
+}
+
+// Write the data to the file.
+
+void
+Gdb_index::do_write(Output_file* of)
+{
+  const off_t off = this->offset();
+  const off_t oview_size = this->data_size();
+  unsigned char* const oview = of->get_output_view(off, oview_size);
+  unsigned char* pov = oview;
+
+  // Write the file header.
+  // (1) Version number.
+  elfcpp::Swap<32, false>::writeval(pov, gdb_index_version);
+  pov += 4;
+  // (2) Offset of the CU list.
+  elfcpp::Swap<32, false>::writeval(pov, gdb_index_hdr_size);
+  pov += 4;
+  // (3) Offset of the types CU list.
+  elfcpp::Swap<32, false>::writeval(pov, this->tu_offset_);
+  pov += 4;
+  // (4) Offset of the address area.
+  elfcpp::Swap<32, false>::writeval(pov, this->addr_offset_);
+  pov += 4;
+  // (5) Offset of the symbol table.
+  elfcpp::Swap<32, false>::writeval(pov, this->symtab_offset_);
+  pov += 4;
+  // (6) Offset of the constant pool.
+  elfcpp::Swap<32, false>::writeval(pov, this->cu_pool_offset_);
+  pov += 4;
+
+  gold_assert(pov - oview == gdb_index_hdr_size);
+
+  // Write the CU list.
+  unsigned int comp_units_count = this->comp_units_.size();
+  for (unsigned int i = 0; i < comp_units_count; ++i)
+    {
+      const Comp_unit& cu = this->comp_units_[i];
+      elfcpp::Swap<64, false>::writeval(pov, cu.cu_offset);
+      elfcpp::Swap<64, false>::writeval(pov + 8, cu.cu_length);
+      pov += 16;
+    }
+
+  gold_assert(pov - oview == this->tu_offset_);
+
+  // Write the types CU list.
+  for (unsigned int i = 0; i < this->type_units_.size(); ++i)
+    {
+      const Type_unit& tu = this->type_units_[i];
+      elfcpp::Swap<64, false>::writeval(pov, tu.tu_offset);
+      elfcpp::Swap<64, false>::writeval(pov + 8, tu.type_offset);
+      elfcpp::Swap<64, false>::writeval(pov + 16, tu.type_signature);
+      pov += 24;
+    }
+
+  gold_assert(pov - oview == this->addr_offset_);
+
+  // Write the address area.
+  for (unsigned int i = 0; i < this->ranges_.size(); ++i)
+    {
+      int cu_index = this->ranges_[i].cu_index;
+      // Translate negative indexes, which refer to a TU, to a
+      // logical index into a concatenated CU/TU list.
+      if (cu_index < 0)
+        cu_index = comp_units_count + (-1 - cu_index);
+      Relobj* object = this->ranges_[i].object;
+      const Dwarf_range_list& ranges = *this->ranges_[i].ranges;
+      for (unsigned int j = 0; j < ranges.size(); ++j)
+        {
+	  const Dwarf_range_list::Range& range = ranges[j];
+	  uint64_t base = 0;
+	  if (range.shndx > 0)
+	    {
+	      const Output_section* os = object->output_section(range.shndx);
+	      base = (os->address()
+		      + object->output_section_offset(range.shndx));
+	    }
+	  elfcpp::Swap<64, false>::writeval(pov, base + range.start);
+	  elfcpp::Swap<64, false>::writeval(pov + 8, base + range.end);
+	  elfcpp::Swap<32, false>::writeval(pov + 16, cu_index);
+	  pov += 20;
+	}
+    }
+
+  gold_assert(pov - oview == this->symtab_offset_);
+
+  // Write the symbol table.
+  for (unsigned int i = 0; i < this->gdb_symtab_->capacity(); ++i)
+    {
+      const Gdb_symbol* sym = (*this->gdb_symtab_)[i];
+      section_offset_type name_offset = 0;
+      unsigned int cu_vector_offset = 0;
+      if (sym != NULL)
+	{
+	  name_offset = (this->stringpool_.get_offset_from_key(sym->name_key)
+			 + this->stringpool_offset_ - this->cu_pool_offset_);
+	  cu_vector_offset = this->cu_vector_offsets_[sym->cu_vector_index];
+	}
+      elfcpp::Swap<32, false>::writeval(pov, name_offset);
+      elfcpp::Swap<32, false>::writeval(pov + 4, cu_vector_offset);
+      pov += 8;
+    }
+
+  gold_assert(pov - oview == this->cu_pool_offset_);
+
+  // Write the CU vectors into the constant pool.
+  for (unsigned int i = 0; i < this->cu_vector_list_.size(); ++i)
+    {
+      Cu_vector* cu_vec = this->cu_vector_list_[i];
+      elfcpp::Swap<32, false>::writeval(pov, cu_vec->size());
+      pov += 4;
+      for (unsigned int j = 0; j < cu_vec->size(); ++j)
+	{
+	  int cu_index = (*cu_vec)[j];
+	  if (cu_index < 0)
+	    cu_index = comp_units_count + (-1 - cu_index);
+	  elfcpp::Swap<32, false>::writeval(pov, cu_index);
+	  pov += 4;
+	}
+    }
+
+  gold_assert(pov - oview == this->stringpool_offset_);
+
+  // Write the strings into the constant pool.
+  this->stringpool_.write_to_buffer(pov, oview_size - this->stringpool_offset_);
+
+  of->write_output_view(off, oview_size, oview);
+}
+
+// Print usage statistics.
+void
+Gdb_index::print_stats()
+{
+  if (parameters->options().gdb_index())
+    Gdb_index_info_reader::print_stats();
+}
+
+} // End namespace gold.