[dsymutil] Generate Apple accelerator tables

[JDevlieghere]

Summary

This patch adds support for generating accelerator tables in dsymutil.
This feature was already present in our internal repository but not yet
upstreamed because it requires changes to the Apple accelerator table
implementation.

[aprantl]

Looks mostly good, the test coverage could probably be a little better.

tools/dsymutil/CMakeLists.txt

4 ↗

(On Diff #131333)

What's the dependency that makes this necessary?

tools/dsymutil/DwarfLinker.cpp

918 ↗

(On Diff #131333)

This comment should be on the declaration instead.

1311 ↗

(On Diff #131333)

The + 1 is for a \NUL? And it's guaranteed to exist?

1569 ↗

(On Diff #131333)

.

2038 ↗

(On Diff #131333)

Is there a PR/radar about this?

[JDevlieghere]

In D42501#987033, @aprantl wrote:

Looks mostly good, the test coverage could probably be a little better.

Thanks for having a look, Adrian! I'm planning on extending the existing test with the other .apple_* sections. A bunch more tests will be added when upstreaming the -update functionality as well, but that's for another diff.

tools/dsymutil/CMakeLists.txt

4 ↗

(On Diff #131333)

The call to dwarf::djbHash()

tools/dsymutil/DwarfLinker.cpp

1311 ↗

(On Diff #131333)

I'll double check!

[labath]

tools/dsymutil/DwarfLinker.cpp

10–11 ↗

(On Diff #131333)

This seems a bit dodgy. Shouldn't the header be moved to the include folder if you want to access it outside codegen ?

631 ↗

(On Diff #131333)

There's no Offset in this function

[JDevlieghere]

Feedback @aprantl and @labath

[aprantl]

tools/dsymutil/DwarfLinker.cpp

104 ↗

(On Diff #131420)

It seems odd to have this implementation live in DwarfLinker. I would have expected this to be part of AsmPrinter. Out of curiosity: Why is it not needed there? Is there something else that is only on opensource.apple.com and should really be on llvm.org?

465 ↗

(On Diff #131420)

.

642 ↗

(On Diff #131420)

These comments are not strictly necessary and basically just repeat the function name :-)

1597 ↗

(On Diff #131420)

Does moving this field improve the layout somehow?

tools/dsymutil/dsymutil.h

43 ↗

(On Diff #131420)

It looks like this option is entirely untested?

[JDevlieghere]

Thanks Adrian, I'll address your comments before committing this tomorrow morning.

tools/dsymutil/DwarfLinker.cpp

104 ↗

(On Diff #131420)

I left it here as it was only used by the DwarfLinker, but happy to move it.

I'm not sure what you mean by your last two questions? The AppleAccelTableStaticOffsetData is the template argument for the new accelerator tables. Dsymutil generates different tables from the AsmPrinter; both have static offsets (the implementation in AsmPrinter queries the DIE for it's offset) and for types we emit two more atoms (QualifiedNameHash and whether it's a ObjCClassIsImplementation).

1597 ↗

(On Diff #131420)

No, this seems unintentional. Actually it makes things worse :(

tools/dsymutil/dsymutil.h

43 ↗

(On Diff #131420)

Because the value is always false actually it *is* tested, as this implies we always generate the pubnames and pubtypes section. I added it so I didn't have to remove the output, only to add it again once I implement the command line flag that will control this. When doing so I will also add a test that check the output for when the value is set to true.

[JDevlieghere]

@adrian: looks like I was mistaken and you didn't accept yet, so updating the patch to address your comments.

[aprantl]

Almost there. Thanks for bearing with me!

include/llvm/CodeGen/AccelTable.h

453 ↗

(On Diff #131518)

Doesn't need to happen in this commit, but I think we should move the implementation of the print functions into the cpp file.

tools/dsymutil/CMakeLists.txt

4 ↗

(On Diff #131333)

That is silly :-) and dsymutil is already huge.

MD5 is in Support, so let's this function to Support too, and remove it from the dwarf namespace.

tools/dsymutil/DwarfLinker.cpp

1311 ↗

(On Diff #131333)

Is there no EmitInt8() or EmitByte() ?

[JDevlieghere]

include/llvm/CodeGen/AccelTable.h

453 ↗

(On Diff #131518)

Agree. I’ll do that in a follow-up commit.

tools/dsymutil/CMakeLists.txt

4 ↗

(On Diff #131333)

Yesterday I noticed that there’s another use that needed this. Anyway, it will trigger a linker error and I’ll see if I can move that into support too.

tools/dsymutil/DwarfLinker.cpp

1311 ↗

(On Diff #131333)

Makes more sense indeed. I mindlessly copied this from somewhere else...

[aprantl]

copied it from somewhere else

Could you fix it there, too? :-)

[JDevlieghere]

tools/dsymutil/CMakeLists.txt

4 ↗

(On Diff #131333)

D42594: Move DJB hash to support.

[aprantl]

LGTM with the dependency on BinaryFormat removed.

llvm/trunk/include/llvm/CodeGen/AccelTable.h

 #ifndef NDEBUG
   void print(raw_ostream &OS) const override {
     OS << "  Offset: " << Die->getOffset() << "\n";
     OS << "  Tag: " << dwarf::TagString(Die->getTag()) << "\n";
   }
 #endif
 };
 
+/// Accelerator table data implementation for simple accelerator tables with
+/// a DIE offset but no actual DIE pointer.
+class AppleAccelTableStaticOffsetData : public AppleAccelTableData {
+public:
+  AppleAccelTableStaticOffsetData(uint32_t Offset) : Offset(Offset) {}
+
+  void emit(AsmPrinter *Asm) const override;
+
+  static constexpr AppleAccelTableHeader::Atom Atoms[] = {
+      AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_offset,
+                                  dwarf::DW_FORM_data4)};
+
+#ifndef NDEBUG
+  void print(raw_ostream &OS) const override {
+    OS << "  Static Offset: " << Offset << "\n";
+  }
+
+#endif
+protected:
+  uint64_t order() const override { return Offset; }
+
+  uint32_t Offset;
+};
+
+/// Accelerator table data implementation for type accelerator tables with
+/// a DIE offset but no actual DIE pointer.
+class AppleAccelTableStaticTypeData : public AppleAccelTableStaticOffsetData {
+public:
+  AppleAccelTableStaticTypeData(uint32_t Offset, uint16_t Tag,
+                                bool ObjCClassIsImplementation,
+                                uint32_t QualifiedNameHash)
+      : AppleAccelTableStaticOffsetData(Offset),
+        QualifiedNameHash(QualifiedNameHash), Tag(Tag),
+        ObjCClassIsImplementation(ObjCClassIsImplementation) {}
+
+  void emit(AsmPrinter *Asm) const override;
+
+  static constexpr AppleAccelTableHeader::Atom Atoms[] = {
+      AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_offset,
+                                  dwarf::DW_FORM_data4),
+      AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
+      AppleAccelTableHeader::Atom(5, dwarf::DW_FORM_data1),
+      AppleAccelTableHeader::Atom(6, dwarf::DW_FORM_data4)};
+
+#ifndef NDEBUG
+  void print(raw_ostream &OS) const override {
+    OS << "  Static Offset: " << Offset << "\n";
+    OS << "  QualifiedNameHash: " << format("%x\n", QualifiedNameHash) << "\n";
+    OS << "  Tag: " << dwarf::TagString(Tag) << "\n";
+    OS << "  ObjCClassIsImplementation: "
+       << (ObjCClassIsImplementation ? "true" : "false");
+    OS << "\n";
+  }
+#endif
+protected:
+  uint64_t order() const override { return Offset; }
+
+  uint32_t QualifiedNameHash;
+  uint16_t Tag;
+  bool ObjCClassIsImplementation;
+};
+
 } // end namespace llvm
 
 #endif // LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H

llvm/trunk/lib/CodeGen/AsmPrinter/AccelTable.cpp

void AppleAccelTableHeader::setBucketAndHashCount(uint32_t HashCount) {
   else
     Header.BucketCount = HashCount > 0 ? HashCount : 1;
 
   Header.HashCount = HashCount;
 }
 
 constexpr AppleAccelTableHeader::Atom AppleAccelTableTypeData::Atoms[];
 constexpr AppleAccelTableHeader::Atom AppleAccelTableOffsetData::Atoms[];
+constexpr AppleAccelTableHeader::Atom AppleAccelTableStaticOffsetData::Atoms[];
+constexpr AppleAccelTableHeader::Atom AppleAccelTableStaticTypeData::Atoms[];
 
 void AppleAccelTableBase::emitHeader(AsmPrinter *Asm) { Header.emit(Asm); }
 
 void AppleAccelTableBase::emitBuckets(AsmPrinter *Asm) {
   unsigned index = 0;
   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
     Asm->OutStreamer->AddComment("Bucket " + Twine(i));
     if (!Buckets[i].empty())
void AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const {
   Asm->EmitInt32(Die->getDebugSectionOffset());
 }
 
 void AppleAccelTableTypeData::emit(AsmPrinter *Asm) const {
   Asm->EmitInt32(Die->getDebugSectionOffset());
   Asm->EmitInt16(Die->getTag());
   Asm->EmitInt8(0);
 }
+
+void AppleAccelTableStaticOffsetData::emit(AsmPrinter *Asm) const {
+  Asm->EmitInt32(Offset);
+}
+
+void AppleAccelTableStaticTypeData::emit(AsmPrinter *Asm) const {
+  Asm->EmitInt32(Offset);
+  Asm->EmitInt16(Tag);
+  Asm->EmitInt8(ObjCClassIsImplementation ? dwarf::DW_FLAG_type_implementation
+                                          : 0);
+  Asm->EmitInt32(QualifiedNameHash);
+}

llvm/trunk/test/tools/dsymutil/X86/basic-lto-linking-x86.test

 CHECK:      DW_AT_low_pc (0x0000000100000f50)
 CHECK:      DW_AT_high_pc (0x0000000100000f89)
 CHECK:      DW_AT_frame_base (DW_OP_reg6 RBP)
 CHECK:      DW_TAG_formal_parameter
 CHECK:        DW_AT_name ("arg")
 CHECK:        DW_AT_type (0x0000000000000063
 CHECK:        DW_AT_location (0x00000000
 CHECK:          [0x0000000000000000, 0x000000000000000e): DW_OP_reg5 RDI, DW_OP_piece 0x4)
-CHECK:      DW_TAG_inlined_subroutine
+CHECK:[[INC1:0x[0-9a-f]*]]{{.*}}DW_TAG_inlined_subroutine
 CHECK:        DW_AT_abstract_origin (cu + 0x00a7 "inc")
 CHECK:        DW_AT_low_pc (0x0000000100000f63)
 CHECK:        DW_AT_high_pc (0x0000000100000f72)
 CHECK:        DW_AT_call_line (20)
 CHECK:      NULL
 CHECK:    DW_TAG_subprogram
 CHECK:      DW_AT_name ("inc")
 CHECK:      DW_AT_type (0x0000000000000063

 CHECK:        DW_AT_name ("arg")
 CHECK:        DW_AT_type (0x0000000000000063
 CHECK:        DW_AT_location (0x00000025
 CHECK:          [0x0000000000000000, 0x000000000000000f): DW_OP_reg5 RDI, DW_OP_piece 0x4
 CHECK:          [0x0000000000000019, 0x000000000000001d): DW_OP_reg5 RDI, DW_OP_piece 0x4)
 CHECK:      DW_TAG_lexical_block
 CHECK:        DW_AT_low_pc (0x0000000100000f94)
 CHECK:        DW_AT_high_pc (0x0000000100000fa7)
-CHECK:        DW_TAG_inlined_subroutine
+CHECK:[[INC2:0x[0-9a-f]*]]{{.*}}DW_TAG_inlined_subroutine
 CHECK:          DW_AT_abstract_origin (cu + 0x009a "inc")
 CHECK:          DW_AT_ranges (0x00000000
 CHECK:             [0x0000000100000f94, 0x0000000100000f9a)
 CHECK:             [0x0000000100000f9f, 0x0000000100000fa7))
 CHECK:        NULL
 CHECK:      NULL
 CHECK:    DW_TAG_subprogram
 CHECK:      DW_AT_name ("inc")

 CHECK-NEXT: 0x00000026 "val"
 CHECK-NEXT: 0x00000045 "bar"
 
 CHECK: .debug_pubtypes contents:
 CHECK-NEXT: length = 0x0000001f version = 0x0002 unit_offset = 0x00000000 unit_size = 0x00000081
 CHECK-NEXT: Offset     Name
 CHECK-NEXT: 0x00000063 "int"
 CHECK-NEXT: 0x00000079 "char"
+
+CHECK: .apple_names contents:
+CHECK-NEXT: Header {
+CHECK-NEXT:   Magic: 0x48415348
+CHECK-NEXT:   Version: 0x1
+CHECK-NEXT:   Hash function: 0x0
+CHECK-NEXT:   Bucket count: 7
+CHECK-NEXT:   Hashes count: 7
+CHECK-NEXT:   HeaderData length: 12
+CHECK-NEXT: }
+CHECK-NEXT: DIE offset base: 0
+CHECK-NEXT: Number of atoms: 1
+CHECK-NEXT: Atoms [
+CHECK-NEXT:   Atom 0 {
+CHECK-NEXT:     Type: DW_ATOM_die_offset
+CHECK-NEXT:     Form: DW_FORM_data4
+CHECK-NEXT:   }
+CHECK-NEXT: ]
+CHECK-NEXT: Bucket 0 [
+CHECK-NEXT:   Hash 0xb8860c2 [
+CHECK-NEXT:     Name@0x74 {
+CHECK-NEXT:       String: 0x0000007e "baz"
+CHECK-NEXT:       Data 0 [
+CHECK-NEXT:         Atom[0]: 0x000000c0
+CHECK-NEXT:       ]
+CHECK-NEXT:     }
+CHECK-NEXT:   ]
+CHECK-NEXT:   Hash 0xb88801f [
+CHECK-NEXT:     Name@0x84 {
+CHECK-NEXT:       String: 0x0000008a "inc"
+CHECK-NEXT:       Data 0 [
+CHECK-NEXT:         Atom[0]: 0x00000110
+CHECK-NEXT:       ]
+CHECK-NEXT:       Data 1 [
+CHECK-NEXT:         Atom[0]: 0x000001c7
+CHECK-NEXT:       ]
+CHECK-NEXT:     }
+CHECK-NEXT:   ]
+CHECK-NEXT: ]
+CHECK-NEXT: Bucket 1 [
+CHECK-NEXT:   EMPTY
+CHECK-NEXT: ]
+CHECK-NEXT: Bucket 2 [
+CHECK-NEXT:   Hash 0xfed12c6a [
+CHECK-NEXT:     Name@0x98 {
+CHECK-NEXT:       String: 0x00000072 "private_int"
+CHECK-NEXT:       Data 0 [
+CHECK-NEXT:         Atom[0]: 0x000000a7
+CHECK-NEXT:       ]
+CHECK-NEXT:     }
+CHECK-NEXT:   ]
+CHECK-NEXT: ]
+CHECK-NEXT: Bucket 3 [
+CHECK-NEXT:   Hash 0xb88b5c8 [
+CHECK-NEXT:     Name@0xa8 {
+CHECK-NEXT:       String: 0x00000097 "val"
+CHECK-NEXT:       Data 0 [
+CHECK-NEXT:         Atom[0]: 0x00000160
+CHECK-NEXT:       ]
+CHECK-NEXT:     }
+CHECK-NEXT:   ]
+CHECK-NEXT:   Hash 0x7c9a7f6a [
+CHECK-NEXT:     Name@0xb8 {
+CHECK-NEXT:       String: 0x00000051 "main"
+CHECK-NEXT:       Data 0 [
+CHECK-NEXT:         Atom[0]: 0x00000026
+CHECK-NEXT:       ]
+CHECK-NEXT:     }
+CHECK-NEXT:   ]
+CHECK-NEXT: ]
+CHECK-NEXT: Bucket 4 [
+CHECK-NEXT:   EMPTY
+CHECK-NEXT: ]
+CHECK-NEXT: Bucket 5 [
+CHECK-NEXT:   Hash 0xb887389 [
+CHECK-NEXT:     Name@0xc8 {
+CHECK-NEXT:       String: 0x00000082 "foo"
+CHECK-NEXT:       Data 0 [
+CHECK-NEXT:         Atom[0]: 0x000000d9
+CHECK-NEXT:       ]
+CHECK-NEXT:     }
+CHECK-NEXT:   ]
+CHECK-NEXT: ]
+CHECK-NEXT: Bucket 6 [
+CHECK-NEXT:   Hash 0xb8860ba [
+CHECK-NEXT:     Name@0xd8 {
+CHECK-NEXT:       String: 0x0000009b "bar"
+CHECK-NEXT:       Data 0 [
+CHECK-NEXT:         Atom[0]: 0x0000017f
+CHECK-NEXT:       ]
+CHECK-NEXT:     }
+CHECK-NEXT:   ]
+CHECK-NEXT: ]
+
+CHECK: apple_types contents:
+CHECK-NEXT: Header {
+CHECK-NEXT:   Magic: 0x48415348
+CHECK-NEXT:   Version: 0x1
+CHECK-NEXT:   Hash function: 0x0
+CHECK-NEXT:   Bucket count: 2
+CHECK-NEXT:   Hashes count: 2
+CHECK-NEXT:   HeaderData length: 24
+CHECK-NEXT: }
+CHECK-NEXT: DIE offset base: 0
+CHECK-NEXT: Number of atoms: 4
+CHECK-NEXT: Atoms [
+CHECK-NEXT:   Atom 0 {
+CHECK-NEXT:     Type: DW_ATOM_die_offset
+CHECK-NEXT:     Form: DW_FORM_data4
+CHECK-NEXT:   }
+CHECK-NEXT:   Atom 1 {
+CHECK-NEXT:     Type: DW_ATOM_die_tag
+CHECK-NEXT:     Form: DW_FORM_data2
+CHECK-NEXT:   }
+CHECK-NEXT:   Atom 2 {
+CHECK-NEXT:     Type: DW_ATOM_type_flags
+CHECK-NEXT:     Form: DW_FORM_data1
+CHECK-NEXT:   }
+CHECK-NEXT:   Atom 3 {
+CHECK-NEXT:     Type: DW_ATOM_qual_name_hash
+CHECK-NEXT:     Form: DW_FORM_data4
+CHECK-NEXT:   }
+CHECK-NEXT: ]
+CHECK-NEXT: Bucket 0 [
+CHECK-NEXT:   Hash 0xb888030 [
+CHECK-NEXT:     Name@0x44 {
+CHECK-NEXT:       String: 0x00000060 "int"
+CHECK-NEXT:       Data 0 [
+CHECK-NEXT:         Atom[0]: 0x00000063
+CHECK-NEXT:         Atom[1]: 0x0024
+CHECK-NEXT:         Atom[2]: 0x00
+CHECK-NEXT:         Atom[3]: 0x0c3a28a4
+CHECK-NEXT:       ]
+CHECK-NEXT:     }
+CHECK-NEXT:   ]
+CHECK-NEXT: ]
+CHECK-NEXT: Bucket 1 [
+CHECK-NEXT:   Hash 0x7c952063 [
+CHECK-NEXT:     Name@0x5b {
+CHECK-NEXT:       String: 0x00000064 "char"
+CHECK-NEXT:       Data 0 [
+CHECK-NEXT:         Atom[0]: 0x00000079
+CHECK-NEXT:         Atom[1]: 0x0024
+CHECK-NEXT:         Atom[2]: 0x00
+CHECK-NEXT:         Atom[3]: 0x937bd757
+CHECK-NEXT:       ]
+CHECK-NEXT:     }
+CHECK-NEXT:   ]
+CHECK-NEXT: ]
+
+CHECK: .apple_namespaces contents:
+CHECK-NEXT: Header {
+CHECK-NEXT:   Magic: 0x48415348
+CHECK-NEXT:   Version: 0x1
+CHECK-NEXT:   Hash function: 0x0
+CHECK-NEXT:   Bucket count: 1
+CHECK-NEXT:   Hashes count: 0
+CHECK-NEXT:   HeaderData length: 12
+CHECK-NEXT: }
+CHECK-NEXT: DIE offset base: 0
+CHECK-NEXT: Number of atoms: 1
+CHECK-NEXT: Atoms [
+CHECK-NEXT:   Atom 0 {
+CHECK-NEXT:     Type: DW_ATOM_die_offset
+CHECK-NEXT:     Form: DW_FORM_data4
+CHECK-NEXT:   }
+CHECK-NEXT: ]
+CHECK-NEXT: Bucket 0 [
+CHECK-NEXT:   EMPTY
+CHECK-NEXT: ]
+
+CHECK: .apple_objc contents:
+CHECK-NEXT: Header {
+CHECK-NEXT:   Magic: 0x48415348
+CHECK-NEXT:   Version: 0x1
+CHECK-NEXT:   Hash function: 0x0
+CHECK-NEXT:   Bucket count: 1
+CHECK-NEXT:   Hashes count: 0
+CHECK-NEXT:   HeaderData length: 12
+CHECK-NEXT: }
+CHECK-NEXT: DIE offset base: 0
+CHECK-NEXT: Number of atoms: 1
+CHECK-NEXT: Atoms [
+CHECK-NEXT:   Atom 0 {
+CHECK-NEXT:     Type: DW_ATOM_die_offset
+CHECK-NEXT:     Form: DW_FORM_data4
+CHECK-NEXT:   }
+CHECK-NEXT: ]
+CHECK-NEXT: Bucket 0 [
+CHECK-NEXT:   EMPTY
+CHECK-NEXT: ]

llvm/trunk/test/tools/dsymutil/X86/objc.test

+RUN: llvm-dsymutil -f -oso-prepend-path=%p/.. %p/../Inputs/objc.macho.x86_64 -o - \
+RUN:   | llvm-dwarfdump -apple-types -apple-objc - | FileCheck %s
+
+CHECK: .apple_types contents:
+CHECK: String: 0x00000066 "A"
+CHECK-NEXT: Data 0 [
+CHECK-NEXT:   Atom[0]: 0x0000012d
+CHECK-NEXT:   Atom[1]: 0x0013
+CHECK-NEXT:   Atom[2]: 0x02
+CHECK-NEXT:   Atom[3]: 0x0b87b15a
+CHECK-NEXT: ]
+
+CHECK: .apple_objc contents:
+CHECK-NEXT: Header {
+CHECK-NEXT:   Magic: 0x48415348
+CHECK-NEXT:   Version: 0x1
+CHECK-NEXT:   Hash function: 0x0
+CHECK-NEXT:   Bucket count: 2
+CHECK-NEXT:   Hashes count: 2
+CHECK-NEXT:   HeaderData length: 12
+CHECK-NEXT: }
+CHECK-NEXT: DIE offset base: 0
+CHECK-NEXT: Number of atoms: 1
+CHECK-NEXT: Atoms [
+CHECK-NEXT:   Atom 0 {
+CHECK-NEXT:     Type: DW_ATOM_die_offset
+CHECK-NEXT:     Form: DW_FORM_data4
+CHECK-NEXT:   }
+CHECK-NEXT: ]
+CHECK-NEXT: Bucket 0 [
+CHECK-NEXT:   Hash 0x2b5e6 [
+CHECK-NEXT:     Name@0x38 {
+CHECK-NEXT:       String: 0x00000066 "A"
+CHECK-NEXT:       Data 0 [
+CHECK-NEXT:         Atom[0]: 0x00000027
+CHECK-NEXT:       ]
+CHECK-NEXT:       Data 1 [
+CHECK-NEXT:         Atom[0]: 0x0000007a
+CHECK-NEXT:       ]
+CHECK-NEXT:     }
+CHECK-NEXT:   ]
+CHECK-NEXT: ]
+CHECK-NEXT: Bucket 1 [
+CHECK-NEXT:   Hash 0x3fa0f4b5 [
+CHECK-NEXT:     Name@0x4c {
+CHECK-NEXT:       String: 0x0000009d "A(Category)"
+CHECK-NEXT:       Data 0 [
+CHECK-NEXT:         Atom[0]: 0x0000007a
+CHECK-NEXT:       ]
+CHECK-NEXT:     }
+CHECK-NEXT:   ]
+CHECK-NEXT: ]

llvm/trunk/tools/dsymutil/DwarfLinker.cpp

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/BinaryFormat/MachO.h"
+#include "llvm/CodeGen/AccelTable.h"
 #include "llvm/CodeGen/AsmPrinter.h"
 #include "llvm/CodeGen/DIE.h"
 #include "llvm/Config/config.h"
 #include "llvm/DebugInfo/DIContext.h"
 #include "llvm/DebugInfo/DWARF/DWARFAbbreviationDeclaration.h"
 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
 #include "llvm/DebugInfo/DWARF/DWARFDataExtractor.h"
 #include "llvm/DebugInfo/DWARF/DWARFDebugLine.h"

 #include "llvm/MC/MCTargetOptions.h"
 #include "llvm/MC/MCTargetOptionsCommandFlags.def"
 #include "llvm/Object/MachO.h"
 #include "llvm/Object/ObjectFile.h"
 #include "llvm/Object/SymbolicFile.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Compiler.h"
+#include "llvm/Support/DJB.h"
 #include "llvm/Support/DataExtractor.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/LEB128.h"
 #include "llvm/Support/MathExtras.h"
public:
 
   /// Keep track of a DW_AT_range attribute that we will need to patch up later.
   void noteRangeAttribute(const DIE &Die, PatchLocation Attr);
 
   /// Keep track of a location attribute pointing to a location list in the
   /// debug_loc section.
   void noteLocationAttribute(PatchLocation Attr, int64_t PcOffset);
 
-  /// Add a name accelerator entry for \p Die with \p Name which is stored in
-  /// the string table at \p Offset.
-  void addNameAccelerator(const DIE *Die, const char *Name, uint32_t Offset,
+  /// Add a name accelerator entry for \a Die with \a Name.
+  void addNamespaceAccelerator(const DIE *Die, DwarfStringPoolEntryRef Name);
+
+  /// Add a name accelerator entry for \a Die with \a Name.
+  void addNameAccelerator(const DIE *Die, DwarfStringPoolEntryRef Name,
+                          bool SkipPubnamesSection = false);
+
+  /// Add various accelerator entries for \p Die with \p Name which is stored
+  /// in the string table at \p Offset. \p Name must be an Objective-C
+  /// selector.
+  void addObjCAccelerator(const DIE *Die, DwarfStringPoolEntryRef Name,
                           bool SkipPubnamesSection = false);
 
   /// Add a type accelerator entry for \p Die with \p Name which is stored in
   /// the string table at \p Offset.
-  void addTypeAccelerator(const DIE *Die, const char *Name, uint32_t Offset);
+  void addTypeAccelerator(const DIE *Die, DwarfStringPoolEntryRef Name,
+                          bool ObjcClassImplementation,
+                          uint32_t QualifiedNameHash);
 
   struct AccelInfo {
-    StringRef Name;      ///< Name of the entry.
-    const DIE *Die;      ///< DIE this entry describes.
-    uint32_t NameOffset; ///< Offset of Name in the string pool.
-    bool SkipPubSection; ///< Emit this entry only in the apple_* sections.
+    /// Name of the entry.
+    DwarfStringPoolEntryRef Name;
+
+    /// DIE this entry describes.
+    const DIE *Die;
+
+    /// Hash of the fully qualified name.
+    uint32_t QualifiedNameHash;
+
+    /// Emit this entry only in the apple_* sections.
+    bool SkipPubSection;
+
+    /// Is this an ObjC class implem?
+    bool ObjcClassImplementation;
 
-    AccelInfo(StringRef Name, const DIE *Die, uint32_t NameOffset,
+    AccelInfo(DwarfStringPoolEntryRef Name, const DIE *Die,
               bool SkipPubSection = false)
-        : Name(Name), Die(Die), NameOffset(NameOffset),
-          SkipPubSection(SkipPubSection) {}
+        : Name(Name), Die(Die), SkipPubSection(SkipPubSection) {}
+
+    AccelInfo(DwarfStringPoolEntryRef Name, const DIE *Die,
+              uint32_t QualifiedNameHash, bool ObjCClassIsImplementation)
+        : Name(Name), Die(Die), QualifiedNameHash(QualifiedNameHash),
+          SkipPubSection(false),
+          ObjcClassImplementation(ObjCClassIsImplementation) {}
   };
 
   const std::vector<AccelInfo> &getPubnames() const { return Pubnames; }
   const std::vector<AccelInfo> &getPubtypes() const { return Pubtypes; }
+  const std::vector<AccelInfo> &getNamespaces() const { return Namespaces; }
+  const std::vector<AccelInfo> &getObjC() const { return ObjC; }
 
   /// Get the full path for file \a FileNum in the line table
   StringRef getResolvedPath(unsigned FileNum) {
     if (FileNum >= ResolvedPaths.size())
       return StringRef();
     return ResolvedPaths[FileNum];
   }
 
private:
   /// function's address.
   std::vector<std::pair<PatchLocation, int64_t>> LocationAttributes;
 
   /// Accelerator entries for the unit, both for the pub*
   /// sections and the apple* ones.
   /// @{
   std::vector<AccelInfo> Pubnames;
   std::vector<AccelInfo> Pubtypes;
+  std::vector<AccelInfo> Namespaces;
+  std::vector<AccelInfo> ObjC;
   /// @}
 
   /// Cached resolved paths from the line table.
   /// Note, the StringRefs here point in to the intern (uniquing) string pool.
   /// This means that a StringRef returned here doesn't need to then be uniqued
   /// for the purposes of getting a unique address for each string.
   std::vector<StringRef> ResolvedPaths;
 
void CompileUnit::noteRangeAttribute(const DIE &Die, PatchLocation Attr) {
   else
     UnitRangeAttribute = Attr;
 }
 
 void CompileUnit::noteLocationAttribute(PatchLocation Attr, int64_t PcOffset) {
   LocationAttributes.emplace_back(Attr, PcOffset);
 }
 
-/// Add a name accelerator entry for \p Die with \p Name
-/// which is stored in the string table at \p Offset.
-void CompileUnit::addNameAccelerator(const DIE *Die, const char *Name,
-                                     uint32_t Offset, bool SkipPubSection) {
-  Pubnames.emplace_back(Name, Die, Offset, SkipPubSection);
+void CompileUnit::addNamespaceAccelerator(const DIE *Die,
+                                          DwarfStringPoolEntryRef Name) {
+  Namespaces.emplace_back(Name, Die);
+}
+
+void CompileUnit::addObjCAccelerator(const DIE *Die,
+                                     DwarfStringPoolEntryRef Name,
+                                     bool SkipPubSection) {
+  ObjC.emplace_back(Name, Die, SkipPubSection);
+}
+
+void CompileUnit::addNameAccelerator(const DIE *Die,
+                                     DwarfStringPoolEntryRef Name,
+                                     bool SkipPubSection) {
+  Pubnames.emplace_back(Name, Die, SkipPubSection);
 }
 
-/// Add a type accelerator entry for \p Die with \p Name
-/// which is stored in the string table at \p Offset.
-void CompileUnit::addTypeAccelerator(const DIE *Die, const char *Name,
-                                     uint32_t Offset) {
-  Pubtypes.emplace_back(Name, Die, Offset, false);
+void CompileUnit::addTypeAccelerator(const DIE *Die,
+                                     DwarfStringPoolEntryRef Name,
+                                     bool ObjcClassImplementation,
+                                     uint32_t QualifiedNameHash) {
+  Pubtypes.emplace_back(Name, Die, QualifiedNameHash, ObjcClassImplementation);
 }
 
 namespace {
 
 /// The Dwarf streaming logic
 ///
 /// All interactions with the MC layer that is used to build the debug
 /// information binary representation are handled in this class.
public:
 
   /// Emit a CIE.
   void emitCIE(StringRef CIEBytes);
 
   /// Emit an FDE with data \p Bytes.
   void emitFDE(uint32_t CIEOffset, uint32_t AddreSize, uint32_t Address,
                StringRef Bytes);
 
+  /// Emit Apple namespaces accelerator table.
+  void
+  emitAppleNamespaces(AppleAccelTable<AppleAccelTableStaticOffsetData> &Table);
+
+  /// Emit Apple names accelerator table.
+  void emitAppleNames(AppleAccelTable<AppleAccelTableStaticOffsetData> &Table);
+
+  /// Emit Apple Objective-C accelerator table.
+  void emitAppleObjc(AppleAccelTable<AppleAccelTableStaticOffsetData> &Table);
+
+  /// Emit Apple type accelerator table.
+  void emitAppleTypes(AppleAccelTable<AppleAccelTableStaticTypeData> &Table);
+
   uint32_t getFrameSectionSize() const { return FrameSectionSize; }
 };
 
 } // end anonymous namespace
 
 bool DwarfStreamer::init(Triple TheTriple) {
   std::string ErrorStr;
   std::string TripleName;

 
 /// Emit the debug_str section stored in \p Pool.
 void DwarfStreamer::emitStrings(const NonRelocatableStringpool &Pool) {
   Asm->OutStreamer->SwitchSection(MOFI->getDwarfStrSection());
   std::vector<DwarfStringPoolEntryRef> Entries = Pool.getEntries();
   for (auto Entry : Entries) {
     if (Entry.getIndex() == -1U)
       break;
-    Asm->OutStreamer->EmitBytes(
-        StringRef(Entry.getString().data(), Entry.getString().size() + 1));
+    // Emit the string itself.
+    Asm->OutStreamer->EmitBytes(Entry.getString());
+    // Emit a null terminator.
+    Asm->EmitInt8(0);
   }
 }
 
+void DwarfStreamer::emitAppleNamespaces(
+    AppleAccelTable<AppleAccelTableStaticOffsetData> &Table) {
+  Asm->OutStreamer->SwitchSection(MOFI->getDwarfAccelNamespaceSection());
+  Table.finalizeTable(Asm.get(), "namespac");
+  auto *SectionBegin = Asm->createTempSymbol("namespac_begin");
+  Asm->OutStreamer->EmitLabel(SectionBegin);
+  Table.emit(Asm.get(), SectionBegin);
+}
+
+void DwarfStreamer::emitAppleNames(
+    AppleAccelTable<AppleAccelTableStaticOffsetData> &Table) {
+  Asm->OutStreamer->SwitchSection(MOFI->getDwarfAccelNamesSection());
+  Table.finalizeTable(Asm.get(), "names");
+  auto *SectionBegin = Asm->createTempSymbol("names_begin");
+  Asm->OutStreamer->EmitLabel(SectionBegin);
+  Table.emit(Asm.get(), SectionBegin);
+}
+
+void DwarfStreamer::emitAppleObjc(
+    AppleAccelTable<AppleAccelTableStaticOffsetData> &Table) {
+  Asm->OutStreamer->SwitchSection(MOFI->getDwarfAccelObjCSection());
+  Table.finalizeTable(Asm.get(), "objc");
+  auto *SectionBegin = Asm->createTempSymbol("objc_begin");
+  Asm->OutStreamer->EmitLabel(SectionBegin);
+  Table.emit(Asm.get(), SectionBegin);
+}
+
+void DwarfStreamer::emitAppleTypes(
+    AppleAccelTable<AppleAccelTableStaticTypeData> &Table) {
+  Asm->OutStreamer->SwitchSection(MOFI->getDwarfAccelTypesSection());
+  Table.finalizeTable(Asm.get(), "types");
+  auto *SectionBegin = Asm->createTempSymbol("types_begin");
+  Asm->OutStreamer->EmitLabel(SectionBegin);
+  Table.emit(Asm.get(), SectionBegin);
+}
+
 /// Emit the swift_ast section stored in \p Buffers.
 void DwarfStreamer::emitSwiftAST(StringRef Buffer) {
   MCSection *SwiftASTSection = MOFI->getDwarfSwiftASTSection();
   SwiftASTSection->setAlignment(1 << 5);
   MS->SwitchSection(SwiftASTSection);
   MS->EmitBytes(Buffer);
 }
 
if (!HeaderEmitted) {
       Asm->EmitLabelDifference(EndLabel, BeginLabel, 4); // Length
       Asm->OutStreamer->EmitLabel(BeginLabel);
       Asm->EmitInt16(dwarf::DW_PUBNAMES_VERSION); // Version
       Asm->EmitInt32(Unit.getStartOffset());      // Unit offset
       Asm->EmitInt32(Unit.getNextUnitOffset() - Unit.getStartOffset()); // Size
       HeaderEmitted = true;
     }
     Asm->EmitInt32(Name.Die->getOffset());
-    Asm->OutStreamer->EmitBytes(
-        StringRef(Name.Name.data(), Name.Name.size() + 1));
+
+    // Emit the string itself.
+    Asm->OutStreamer->EmitBytes(Name.Name.getString());
+    // Emit a null terminator.
+    Asm->EmitInt8(0);
   }
 
   if (!HeaderEmitted)
     return;
   Asm->EmitInt32(0); // End marker.
   Asm->OutStreamer->EmitLabel(EndLabel);
 }
 
private:
 
   private:
     using AttributeSpec = DWARFAbbreviationDeclaration::AttributeSpec;
 
     /// Information gathered and exchanged between the various
     /// clone*Attributes helpers about the attributes of a particular DIE.
     struct AttributesInfo {
       /// Names.
-      const char *Name = nullptr;
-      const char *MangledName = nullptr;
+      DwarfStringPoolEntryRef Name, MangledName, NameWithoutTemplate;
 
       /// Offsets in the string pool.
       uint32_t NameOffset = 0;
       uint32_t MangledNameOffset = 0;
 
       /// Value of AT_low_pc in the input DIE
       uint64_t OrigLowPc = std::numeric_limits<uint64_t>::max();
 
       /// Value of AT_high_pc in the input DIE
       uint64_t OrigHighPc = 0;
 
       /// Offset to apply to PC addresses inside a function.
       int64_t PCOffset = 0;
 
       /// Does the DIE have a low_pc attribute?
       bool HasLowPc = false;
 
+      /// Does the DIE have a ranges attribute?
+      bool HasRanges = false;
+
       /// Is this DIE only a declaration?
       bool IsDeclaration = false;
 
       AttributesInfo() = default;
     };
 
     /// Helper for cloneDIE.
     unsigned cloneAttribute(DIE &Die,
unsigned cloneScalarAttribute(DIE &Die,
                                   CompileUnit &U, AttributeSpec AttrSpec,
                                   const DWARFFormValue &Val, unsigned AttrSize,
                                   AttributesInfo &Info);
 
     /// Get the potential name and mangled name for the entity
     /// described by \p Die and store them in \Info if they are not
     /// already there.
     /// \returns is a name was found.
-    bool getDIENames(const DWARFDie &Die, AttributesInfo &Info);
+    bool getDIENames(const DWARFDie &Die, AttributesInfo &Info,
+                     bool StripTemplate = false);
 
     /// Create a copy of abbreviation Abbrev.
     void copyAbbrev(const DWARFAbbreviationDeclaration &Abbrev, bool hasODR);
+
+    uint32_t hashFullyQualifiedName(DWARFDie DIE, CompileUnit &U,
+                                    int RecurseDepth = 0);
+
+    /// Helper for cloneDIE.
+    void addObjCAccelerator(CompileUnit &Unit, const DIE *Die,
+                            DwarfStringPoolEntryRef Name, bool SkipPubSection);
   };
 
   /// Assign an abbreviation number to \p Abbrev
   void AssignAbbrev(DIEAbbrev &Abbrev);
 
   /// Compute and emit debug_ranges section for \p Unit, and
   /// patch the attributes referencing it.
   void patchRangesForUnit(const CompileUnit &Unit, DWARFContext &Dwarf) const;
private:
   /// this takes care of comparing the semantics of CIEs defined in
   /// different object files.
   StringMap<uint32_t> EmittedCIEs;
 
   /// Offset of the last CIE that has been emitted in the output
   /// debug_frame section.
   uint32_t LastCIEOffset = 0;
 
+  /// Apple accelerator tables.
+  AppleAccelTable<AppleAccelTableStaticOffsetData> AppleNames;
+  AppleAccelTable<AppleAccelTableStaticOffsetData> AppleNamespaces;
+  AppleAccelTable<AppleAccelTableStaticOffsetData> AppleObjc;
+  AppleAccelTable<AppleAccelTableStaticTypeData> AppleTypes;
+
   /// Mapping the PCM filename to the DwoId.
   StringMap<uint64_t> ClangModules;
 
   bool ModuleCacheHintDisplayed = false;
   bool ArchiveHintDisplayed = false;
 };
 
 } // end anonymous namespace
if ((Tag == dwarf::DW_TAG_subprogram &&
        Context.getTag() != dwarf::DW_TAG_class_type) ||
       (Tag == dwarf::DW_TAG_union_type))
     return PointerIntPair<DeclContext *, 1>(*ContextIter, /* Invalid= */ 1);
 
   return PointerIntPair<DeclContext *, 1>(*ContextIter);
 }
 
 bool DwarfLinker::DIECloner::getDIENames(const DWARFDie &Die,
-                                         AttributesInfo &Info) {
+                                         AttributesInfo &Info,
+                                         bool StripTemplate) {
+  // This function will be called on DIEs having low_pcs and
+  // ranges. As getting the name might be more expansive, filter out
+  // blocks directly.
+  if (Die.getTag() == dwarf::DW_TAG_lexical_block)
+    return false;
+
   // FIXME: a bit wasteful as the first getName might return the
   // short name.
-  if (!Info.MangledName &&
-      (Info.MangledName = Die.getName(DINameKind::LinkageName)))
-    Info.MangledNameOffset =
-        Linker.StringPool.getStringOffset(Info.MangledName);
-
-  if (!Info.Name && (Info.Name = Die.getName(DINameKind::ShortName)))
-    Info.NameOffset = Linker.StringPool.getStringOffset(Info.Name);
+  if (!Info.MangledName)
+    if (const char *MangledName = Die.getName(DINameKind::LinkageName))
+      Info.MangledName = Linker.StringPool.getEntry(MangledName);
+
+  if (!Info.Name)
+    if (const char *Name = Die.getName(DINameKind::ShortName))
+      Info.Name = Linker.StringPool.getEntry(Name);
+
+  if (StripTemplate && Info.Name && Info.MangledName != Info.Name) {
+    // FIXME: dsymutil compatibility. This is wrong for operator<
+    auto Split = Info.Name.getString().split('<');
+    if (!Split.second.empty())
+      Info.NameWithoutTemplate = Linker.StringPool.getEntry(Split.first);
+  }
 
   return Info.Name || Info.MangledName;
 }
 
 /// Report a warning to the user, optionaly including
 /// information about a specific \p DIE related to the warning.
 void DwarfLinker::reportWarning(const Twine &Warning,
                                 const DWARFDie *DIE) const {
unsigned DwarfLinker::DIECloner::cloneBlockAttribute(DIE &Die,
   Die.addValue(DIEAlloc, Value);
   return AttrSize;
 }
 
 unsigned DwarfLinker::DIECloner::cloneAddressAttribute(
     DIE &Die, AttributeSpec AttrSpec, const DWARFFormValue &Val,
     const CompileUnit &Unit, AttributesInfo &Info) {
   uint64_t Addr = *Val.getAsAddress();
+
   if (AttrSpec.Attr == dwarf::DW_AT_low_pc) {
     if (Die.getTag() == dwarf::DW_TAG_inlined_subroutine ||
         Die.getTag() == dwarf::DW_TAG_lexical_block)
       // The low_pc of a block or inline subroutine might get
       // relocated because it happens to match the low_pc of the
       // enclosing subprogram. To prevent issues with that, always use
       // the low_pc from the input DIE if relocations have been applied.
       Addr = (Info.OrigLowPc != std::numeric_limits<uint64_t>::max()
else {
     Linker.reportWarning(
         "Unsupported scalar attribute form. Dropping attribute.",
         &InputDIE);
     return 0;
   }
   PatchLocation Patch =
       Die.addValue(DIEAlloc, dwarf::Attribute(AttrSpec.Attr),
                    dwarf::Form(AttrSpec.Form), DIEInteger(Value));
-  if (AttrSpec.Attr == dwarf::DW_AT_ranges)
+  if (AttrSpec.Attr == dwarf::DW_AT_ranges) {
     Unit.noteRangeAttribute(Die, Patch);
+    Info.HasRanges = true;
+  }
 
   // A more generic way to check for location attributes would be
   // nice, but it's very unlikely that any other attribute needs a
   // location list.
   else if (AttrSpec.Attr == dwarf::DW_AT_location ||
            AttrSpec.Attr == dwarf::DW_AT_frame_base)
     Unit.noteLocationAttribute(Patch, Info.PCOffset);
   else if (AttrSpec.Attr == dwarf::DW_AT_declaration && Value)
static bool isTypeTag(uint16_t Tag) {
   case dwarf::DW_TAG_shared_type:
     return true;
   default:
     break;
   }
   return false;
 }
 
+static bool isObjCSelector(StringRef Name) {
+  return Name.size() > 2 && (Name[0] == '-' || Name[0] == '+') &&
+         (Name[1] == '[');
+}
+
+void DwarfLinker::DIECloner::addObjCAccelerator(CompileUnit &Unit,
+                                                const DIE *Die,
+                                                DwarfStringPoolEntryRef Name,
+                                                bool SkipPubSection) {
+  assert(isObjCSelector(Name.getString()) && "not an objc selector");
+  // Objective C method or class function.
+  // "- [Class(Category) selector :withArg ...]"
+  StringRef ClassNameStart(Name.getString().drop_front(2));
+  size_t FirstSpace = ClassNameStart.find(' ');
+  if (FirstSpace == StringRef::npos)
+    return;
+
+  StringRef SelectorStart(ClassNameStart.data() + FirstSpace + 1);
+  if (!SelectorStart.size())
+    return;
+
+  StringRef Selector(SelectorStart.data(), SelectorStart.size() - 1);
+  Unit.addNameAccelerator(Die, Linker.StringPool.getEntry(Selector),
+                          SkipPubSection);
+
+  // Add an entry for the class name that points to this
+  // method/class function.
+  StringRef ClassName(ClassNameStart.data(), FirstSpace);
+  Unit.addObjCAccelerator(Die, Linker.StringPool.getEntry(ClassName),
+                          SkipPubSection);
+
+  if (ClassName[ClassName.size() - 1] == ')') {
+    size_t OpenParens = ClassName.find('(');
+    if (OpenParens != StringRef::npos) {
+      StringRef ClassNameNoCategory(ClassName.data(), OpenParens);
+      Unit.addObjCAccelerator(
+          Die, Linker.StringPool.getEntry(ClassNameNoCategory), SkipPubSection);
+
+      std::string MethodNameNoCategory(Name.getString().data(), OpenParens + 2);
+      // FIXME: The missing space here may be a bug, but
+      //        dsymutil-classic also does it this way.
+      MethodNameNoCategory.append(SelectorStart);
+      Unit.addNameAccelerator(Die,
+                              Linker.StringPool.getEntry(MethodNameNoCategory),
+                              SkipPubSection);
+    }
+  }
+}
+
 static bool
 shouldSkipAttribute(DWARFAbbreviationDeclaration::AttributeSpec AttrSpec,
                     uint16_t Tag, bool InDebugMap, bool SkipPC,
                     bool InFunctionScope) {
   switch (AttrSpec.Attr) {
   default:
     return false;
   case dwarf::DW_AT_low_pc:
OutOffset +=
         cloneAttribute(*Die, InputDIE, Unit, Val, AttrSpec, AttrSize, AttrInfo);
   }
 
   // Look for accelerator entries.
   uint16_t Tag = InputDIE.getTag();
   // FIXME: This is slightly wrong. An inline_subroutine without a
   // low_pc, but with AT_ranges might be interesting to get into the
   // accelerator tables too. For now stick with dsymutil's behavior.
-  if ((Info.InDebugMap || AttrInfo.HasLowPc) &&
+  if ((Info.InDebugMap || AttrInfo.HasLowPc || AttrInfo.HasRanges) &&
       Tag != dwarf::DW_TAG_compile_unit &&
-      getDIENames(InputDIE, AttrInfo)) {
+      getDIENames(InputDIE, AttrInfo,
+                  Tag != dwarf::DW_TAG_inlined_subroutine)) {
     if (AttrInfo.MangledName && AttrInfo.MangledName != AttrInfo.Name)
       Unit.addNameAccelerator(Die, AttrInfo.MangledName,
-                              AttrInfo.MangledNameOffset,
                               Tag == dwarf::DW_TAG_inlined_subroutine);
-    if (AttrInfo.Name)
-      Unit.addNameAccelerator(Die, AttrInfo.Name, AttrInfo.NameOffset,
+    if (AttrInfo.Name) {
+      if (AttrInfo.NameWithoutTemplate)
+        Unit.addNameAccelerator(Die, AttrInfo.NameWithoutTemplate,
+                                /* SkipPubSection */ true);
+      Unit.addNameAccelerator(Die, AttrInfo.Name,
                               Tag == dwarf::DW_TAG_inlined_subroutine);
+    }
+    if (AttrInfo.Name && isObjCSelector(AttrInfo.Name.getString()))
+      addObjCAccelerator(Unit, Die, AttrInfo.Name, /* SkipPubSection =*/true);
+
+  } else if (Tag == dwarf::DW_TAG_namespace) {
+    if (!AttrInfo.Name)
+      AttrInfo.Name = Linker.StringPool.getEntry("(anonymous namespace)");
+    Unit.addNamespaceAccelerator(Die, AttrInfo.Name);
   } else if (isTypeTag(Tag) && !AttrInfo.IsDeclaration &&
-             getDIENames(InputDIE, AttrInfo)) {
-    if (AttrInfo.Name)
-      Unit.addTypeAccelerator(Die, AttrInfo.Name, AttrInfo.NameOffset);
+             getDIENames(InputDIE, AttrInfo) && AttrInfo.Name &&
+             AttrInfo.Name.getString()[0]) {
+    uint32_t Hash = hashFullyQualifiedName(InputDIE, Unit);
+    uint64_t RuntimeLang =
+        dwarf::toUnsigned(InputDIE.find(dwarf::DW_AT_APPLE_runtime_class))
+            .getValueOr(0);
+    bool ObjCClassIsImplementation =
+        (RuntimeLang == dwarf::DW_LANG_ObjC ||
+         RuntimeLang == dwarf::DW_LANG_ObjC_plus_plus) &&
+        dwarf::toUnsigned(InputDIE.find(dwarf::DW_AT_APPLE_objc_complete_type))
+            .getValueOr(0);
+    Unit.addTypeAccelerator(Die, AttrInfo.Name, ObjCClassIsImplementation,
+                            Hash);
   }
 
   // Determine whether there are any children that we want to keep.
   bool HasChildren = false;
-  for (auto Child: InputDIE.children()) {
+  for (auto Child : InputDIE.children()) {
     unsigned Idx = U.getDIEIndex(Child);
     if (Unit.getInfo(Idx).Keep) {
       HasChildren = true;
       break;
     }
   }
 
   DIEAbbrev NewAbbrev = Die->generateAbbrev();
else {
     Streamer->emitLineTableForUnit(Params,
                                    LineData.slice(*StmtList + 4, PrologueEnd),
                                    LineTable.Prologue.MinInstLength, NewRows,
                                    Unit.getOrigUnit().getAddressByteSize());
   }
 }
 
 void DwarfLinker::emitAcceleratorEntriesForUnit(CompileUnit &Unit) {
+  // Add namespaces.
+  for (const auto &Namespace : Unit.getNamespaces())
+    AppleNamespaces.addName(Namespace.Name,
+                            Namespace.Die->getOffset() + Unit.getStartOffset());
+
+  /// Add names.
+  if (!Options.Minimize)
     Streamer->emitPubNamesForUnit(Unit);
+  for (const auto &Pubname : Unit.getPubnames())
+    AppleNames.addName(Pubname.Name,
+                       Pubname.Die->getOffset() + Unit.getStartOffset());
+
+  /// Add types.
+  if (!Options.Minimize)
     Streamer->emitPubTypesForUnit(Unit);
+  for (const auto &Pubtype : Unit.getPubtypes())
+    AppleTypes.addName(
+        Pubtype.Name, Pubtype.Die->getOffset() + Unit.getStartOffset(),
+        Pubtype.Die->getTag(),
+        Pubtype.ObjcClassImplementation ? dwarf::DW_FLAG_type_implementation
+                                        : 0,
+        Pubtype.QualifiedNameHash);
+
+  /// Add ObjC names.
+  for (const auto &ObjC : Unit.getObjC())
+    AppleObjc.addName(ObjC.Name, ObjC.Die->getOffset() + Unit.getStartOffset());
 }
 
 /// Read the frame info stored in the object, and emit the
 /// patched frame descriptions for the linked binary.
 ///
 /// This is actually pretty easy as the data of the CIEs and FDEs can
 /// be considered as black boxes and moved as is. The only thing to do
 /// is to patch the addresses in the headers.
for (const auto &Attr : Abbrev.attributes()) {
     if (hasODR && isODRAttribute(Attr.Attr))
       Form = dwarf::DW_FORM_ref_addr;
     Copy.AddAttribute(dwarf::Attribute(Attr.Attr), dwarf::Form(Form));
   }
 
   Linker.AssignAbbrev(Copy);
 }
 
+uint32_t DwarfLinker::DIECloner::hashFullyQualifiedName(DWARFDie DIE,
+                                                        CompileUnit &U,
+                                                        int RecurseDepth) {
+  const char *Name = nullptr;
+  DWARFUnit *OrigUnit = &U.getOrigUnit();
+  CompileUnit *CU = &U;
+  Optional<DWARFFormValue> Ref;
+
+  while (1) {
+    if (const char *CurrentName = DIE.getName(DINameKind::ShortName))
+      Name = CurrentName;
+
+    if (!(Ref = DIE.find(dwarf::DW_AT_specification)) &&
+        !(Ref = DIE.find(dwarf::DW_AT_abstract_origin)))
+      break;
+
+    if (!Ref->isFormClass(DWARFFormValue::FC_Reference))
+      break;
+
+    CompileUnit *RefCU;
+    if (auto RefDIE = resolveDIEReference(Linker, CompileUnits, *Ref,
+                                          U.getOrigUnit(), DIE, RefCU)) {
+      CU = RefCU;
+      OrigUnit = &RefCU->getOrigUnit();
+      DIE = RefDIE;
+    }
+  }
+
+  unsigned Idx = OrigUnit->getDIEIndex(DIE);
+  if (!Name && DIE.getTag() == dwarf::DW_TAG_namespace)
+    Name = "(anonymous namespace)";
+
+  if (CU->getInfo(Idx).ParentIdx == 0 ||
+      // FIXME: dsymutil-classic compatibility. Ignore modules.
+      CU->getOrigUnit().getDIEAtIndex(CU->getInfo(Idx).ParentIdx).getTag() ==
+          dwarf::DW_TAG_module)
+    return djbHash(Name ? Name : "", djbHash(RecurseDepth ? "" : "::"));
+
+  DWARFDie Die = OrigUnit->getDIEAtIndex(CU->getInfo(Idx).ParentIdx);
+  return djbHash((Name ? Name : ""),
+                 djbHash((Name ? "::" : ""),
+                         hashFullyQualifiedName(Die, *CU, ++RecurseDepth)));
+}
+
 static uint64_t getDwoId(const DWARFDie &CUDie,
                          const DWARFUnit &Unit) {
   auto DwoId = dwarf::toUnsigned(CUDie.find({dwarf::DW_AT_dwo_id,
                                              dwarf::DW_AT_GNU_dwo_id}));
   if (DwoId)
     return *DwoId;
   return 0;
 }
for (auto &CurrentUnit : CompileUnits) {
     }
     Linker.OutputDebugInfoSize = CurrentUnit->computeNextUnitOffset();
     if (Linker.Options.NoOutput)
       continue;
     // FIXME: for compatibility with the classic dsymutil, we emit
     // an empty line table for the unit, even if the unit doesn't
     // actually exist in the DIE tree.
     Linker.patchLineTableForUnit(*CurrentUnit, DwarfContext);
+    Linker.emitAcceleratorEntriesForUnit(*CurrentUnit);
     Linker.patchRangesForUnit(*CurrentUnit, DwarfContext);
     Linker.Streamer->emitLocationsForUnit(*CurrentUnit, DwarfContext);
-    Linker.emitAcceleratorEntriesForUnit(*CurrentUnit);
   }
 
   if (Linker.Options.NoOutput)
     return;
 
   // Emit all the compile unit's debug information.
   for (auto &CurrentUnit : CompileUnits) {
     Linker.generateUnitRanges(*CurrentUnit);
for (const auto &Obj : Map.objects()) {
     // Clean-up before starting working on the next object.
     endDebugObject();
   }
 
   // Emit everything that's global.
   if (!Options.NoOutput) {
     Streamer->emitAbbrevs(Abbreviations, MaxDwarfVersion);
     Streamer->emitStrings(StringPool);
+    Streamer->emitAppleNames(AppleNames);
+    Streamer->emitAppleNamespaces(AppleNamespaces);
+    Streamer->emitAppleTypes(AppleTypes);
+    Streamer->emitAppleObjc(AppleObjc);
   }
 
   return Options.NoOutput ? true : Streamer->finish(Map);
 }
 
 DwarfStringPoolEntryRef NonRelocatableStringpool::getEntry(StringRef S) {
   if (S.empty() && !Strings.empty())
     return EmptyString;

llvm/trunk/tools/dsymutil/dsymutil.h

struct LinkOptions {
   bool Verbose = false;
 
   /// Skip emitting output
   bool NoOutput = false;
 
   /// Do not unique types according to ODR
   bool NoODR;
 
+  /// Minimize
+  bool Minimize = false;
+
   /// Do not check swiftmodule timestamp
   bool NoTimestamp = false;
 
   /// -oso-prepend-path
   std::string PrependPath;
 
   LinkOptions() = default;
 };