Add support for comdats.

The implementation is a direct translation to c++ of the rules in the ELF spec.

llvm-svn: 249881

10 files changed, 191 insertions, 26 deletions

diff --git a/lld/ELF/InputFiles.cpp b/lld/ELF/InputFiles.cpp
index fb70fcca439..78aaa8f4b67 100644
--- a/lld/ELF/InputFiles.cpp
+++ b/lld/ELF/InputFiles.cpp
@@ -95,19 +95,65 @@ typename ObjectFile<ELFT>::Elf_Sym_Range ObjectFile<ELFT>::getLocalSymbols() {
   return this->getSymbolsHelper(true);
 }
 
-template <class ELFT> void elf2::ObjectFile<ELFT>::parse() {
+template <class ELFT>
+void elf2::ObjectFile<ELFT>::parse(DenseSet<StringRef> &Comdats) {
   // Read section and symbol tables.
-  initializeSections();
+  initializeSections(Comdats);
   initializeSymbols();
 }
 
-template <class ELFT> void elf2::ObjectFile<ELFT>::initializeSections() {
+template <class ELFT>
+StringRef ObjectFile<ELFT>::getShtGroupSignature(const Elf_Shdr &Sec) {
+  const ELFFile<ELFT> &Obj = this->ELFObj;
+  uint32_t SymtabdSectionIndex = Sec.sh_link;
+  ErrorOr<const Elf_Shdr *> SecOrErr = Obj.getSection(SymtabdSectionIndex);
+  error(SecOrErr);
+  const Elf_Shdr *SymtabSec = *SecOrErr;
+  uint32_t SymIndex = Sec.sh_info;
+  const Elf_Sym *Sym = Obj.getSymbol(SymtabSec, SymIndex);
+  ErrorOr<StringRef> StringTableOrErr = Obj.getStringTableForSymtab(*SymtabSec);
+  error(StringTableOrErr);
+  ErrorOr<StringRef> SignatureOrErr = Sym->getName(*StringTableOrErr);
+  error(SignatureOrErr);
+  return *SignatureOrErr;
+}
+
+template <class ELFT>
+ArrayRef<typename ObjectFile<ELFT>::GroupEntryType>
+ObjectFile<ELFT>::getShtGroupEntries(const Elf_Shdr &Sec) {
+  const ELFFile<ELFT> &Obj = this->ELFObj;
+  ErrorOr<ArrayRef<GroupEntryType>> EntriesOrErr =
+      Obj.template getSectionContentsAsArray<GroupEntryType>(&Sec);
+  error(EntriesOrErr.getError());
+  ArrayRef<GroupEntryType> Entries = *EntriesOrErr;
+  if (Entries.empty() || Entries[0] != GRP_COMDAT)
+    error("Unsupported SHT_GROUP format");
+  return Entries.slice(1);
+}
+
+template <class ELFT>
+void elf2::ObjectFile<ELFT>::initializeSections(DenseSet<StringRef> &Comdats) {
   uint64_t Size = this->ELFObj.getNumSections();
   Sections.resize(Size);
-  unsigned I = 0;
+  unsigned I = -1;
   const ELFFile<ELFT> &Obj = this->ELFObj;
   for (const Elf_Shdr &Sec : Obj.sections()) {
+    ++I;
+    if (Sections[I] == &InputSection<ELFT>::Discarded)
+      continue;
+
     switch (Sec.sh_type) {
+    case SHT_GROUP:
+      Sections[I] = &InputSection<ELFT>::Discarded;
+      if (Comdats.insert(getShtGroupSignature(Sec)).second)
+        continue;
+      for (GroupEntryType E : getShtGroupEntries(Sec)) {
+        uint32_t SecIndex = E;
+        if (SecIndex >= Size)
+          error("Invalid section index in group");
+        Sections[SecIndex] = &InputSection<ELFT>::Discarded;
+      }
+      break;
     case SHT_SYMTAB:
       this->Symtab = &Sec;
       break;
@@ -135,7 +181,6 @@ template <class ELFT> void elf2::ObjectFile<ELFT>::initializeSections() {
       Sections[I] = new (Alloc) InputSection<ELFT>(this, &Sec);
       break;
     }
-    ++I;
   }
 }
 
@@ -177,8 +222,12 @@ SymbolBody *elf2::ObjectFile<ELFT>::createSymbolBody(StringRef StringTable,
     error("unexpected binding");
   case STB_GLOBAL:
   case STB_WEAK:
-  case STB_GNU_UNIQUE:
-    return new (Alloc) DefinedRegular<ELFT>(Name, *Sym, *Sections[SecIndex]);
+  case STB_GNU_UNIQUE: {
+    InputSection<ELFT> *Sec = Sections[SecIndex];
+    if (Sec == &InputSection<ELFT>::Discarded)
+      return new (Alloc) Undefined<ELFT>(Name, *Sym);
+    return new (Alloc) DefinedRegular<ELFT>(Name, *Sym, *Sec);
+  }
   }
 }
 
diff --git a/lld/ELF/InputFiles.h b/lld/ELF/InputFiles.h
index dfb0f21ba15..2798c7ba9e7 100644
--- a/lld/ELF/InputFiles.h
+++ b/lld/ELF/InputFiles.h
@@ -37,9 +37,6 @@ public:
   Kind kind() const { return FileKind; }
   virtual ~InputFile() {}
 
-  // Reads a file (constructors don't do that).
-  virtual void parse() = 0;
-
   StringRef getName() const { return MB.getBufferIdentifier(); }
 
 protected:
@@ -75,6 +72,7 @@ public:
   static bool classof(const InputFile *F) { return F->kind() == ObjectKind; }
 
   ArrayRef<SymbolBody *> getSymbols() { return SymbolBodies; }
+  virtual void parse(llvm::DenseSet<StringRef> &Comdats) = 0;
 
 protected:
   // List of all symbols referenced or defined by this file.
@@ -126,6 +124,11 @@ class ObjectFile : public ObjectFileBase, public ELFData<ELFT> {
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym_Range Elf_Sym_Range;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Word Elf_Word;
 
+  typedef llvm::support::detail::packed_endian_specific_integral<
+      uint32_t, ELFT::TargetEndianness, 2> GroupEntryType;
+  StringRef getShtGroupSignature(const Elf_Shdr &Sec);
+  ArrayRef<GroupEntryType> getShtGroupEntries(const Elf_Shdr &Sec);
+
 public:
   using ELFData<ELFT>::getEMachine;
 
@@ -135,7 +138,7 @@ public:
   }
 
   explicit ObjectFile(MemoryBufferRef M);
-  void parse() override;
+  void parse(llvm::DenseSet<StringRef> &Comdats) override;
 
   ArrayRef<InputSection<ELFT> *> getSections() const { return Sections; }
 
@@ -152,7 +155,7 @@ public:
   ArrayRef<Elf_Word> getSymbolTableShndx() const { return SymtabSHNDX; };
 
 private:
-  void initializeSections();
+  void initializeSections(llvm::DenseSet<StringRef> &Comdats);
   void initializeSymbols();
 
   SymbolBody *createSymbolBody(StringRef StringTable, const Elf_Sym *Sym);
@@ -167,7 +170,7 @@ class ArchiveFile : public InputFile {
 public:
   explicit ArchiveFile(MemoryBufferRef M) : InputFile(ArchiveKind, M) {}
   static bool classof(const InputFile *F) { return F->kind() == ArchiveKind; }
-  void parse() override;
+  void parse();
 
   // Returns a memory buffer for a given symbol. An empty memory buffer
   // is returned if we have already returned the same memory buffer.
@@ -194,6 +197,7 @@ public:
   static bool classof(const InputFile *F) { return F->kind() == SharedKind; }
   StringRef getSoName() const { return SoName; }
   virtual void parseSoName() = 0;
+  virtual void parse() = 0;
 };
 
 template <class ELFT>
diff --git a/lld/ELF/InputSection.h b/lld/ELF/InputSection.h
index 53e0f9f9678..038c659d144 100644
--- a/lld/ELF/InputSection.h
+++ b/lld/ELF/InputSection.h
@@ -56,6 +56,8 @@ public:
   // Relocation sections that refer to this one.
   SmallVector<const Elf_Shdr *, 1> RelocSections;
 
+  static InputSection<ELFT> Discarded;
+
 private:
   template <bool isRela>
   void relocate(uint8_t *Buf,
@@ -75,6 +77,9 @@ private:
   const Elf_Shdr *Header;
 };
 
+template <class ELFT>
+InputSection<ELFT> InputSection<ELFT>::Discarded(nullptr, nullptr);
+
 } // namespace elf2
 } // namespace lld
 
diff --git a/lld/ELF/OutputSections.cpp b/lld/ELF/OutputSections.cpp
index 852ba6b89fe..3b089a58430 100644
--- a/lld/ELF/OutputSections.cpp
+++ b/lld/ELF/OutputSections.cpp
@@ -475,6 +475,14 @@ lld::elf2::getLocalSymVA(const typename ELFFile<ELFT>::Elf_Sym *Sym,
         Sym, File.getSymbolTable(), File.getSymbolTableShndx());
   ArrayRef<InputSection<ELFT> *> Sections = File.getSections();
   InputSection<ELFT> *Section = Sections[SecIndex];
+
+  // According to the ELF spec reference to a local symbol from outside
+  // the group are not allowed. Unfortunately .eh_frame breaks that rule
+  // and must be treated specially. For now we just replace the symbol with
+  // 0.
+  if (Section == &InputSection<ELFT>::Discarded)
+    return 0;
+
   OutputSection<ELFT> *OutSec = Section->getOutputSection();
   return OutSec->getVA() + Section->getOutputSectionOff() + Sym->st_value;
 }
@@ -534,11 +542,24 @@ bool lld::elf2::includeInDynamicSymtab(const SymbolBody &B) {
 }
 
 template <class ELFT>
-bool lld::elf2::shouldKeepInSymtab(StringRef SymName,
+bool lld::elf2::shouldKeepInSymtab(const ObjectFile<ELFT> &File,
+                                   StringRef SymName,
                                    const typename ELFFile<ELFT>::Elf_Sym &Sym) {
   if (Sym.getType() == STT_SECTION)
     return false;
 
+  // If sym references a section in a discarded group, don't keep it.
+  uint32_t SecIndex = Sym.st_shndx;
+  if (SecIndex != SHN_ABS) {
+    if (SecIndex == SHN_XINDEX)
+      SecIndex = File.getObj().getExtendedSymbolTableIndex(
+          &Sym, File.getSymbolTable(), File.getSymbolTableShndx());
+    ArrayRef<InputSection<ELFT> *> Sections = File.getSections();
+    const InputSection<ELFT> *Section = Sections[SecIndex];
+    if (Section == &InputSection<ELFT>::Discarded)
+      return false;
+  }
+
   if (Config->DiscardNone)
     return true;
 
@@ -597,8 +618,9 @@ void SymbolTableSection<ELFT>::writeLocalSymbols(uint8_t *&Buf) {
       ErrorOr<StringRef> SymNameOrErr = Sym.getName(File.getStringTable());
       error(SymNameOrErr);
       StringRef SymName = *SymNameOrErr;
-      if (!shouldKeepInSymtab<ELFT>(SymName, Sym))
+      if (!shouldKeepInSymtab<ELFT>(File, SymName, Sym))
         continue;
+
       auto *ESym = reinterpret_cast<Elf_Sym *>(Buf);
       Buf += sizeof(*ESym);
       ESym->st_name = StrTabSec.getFileOff(SymName);
@@ -774,13 +796,17 @@ template bool includeInSymtab<ELF32BE>(const SymbolBody &);
 template bool includeInSymtab<ELF64LE>(const SymbolBody &);
 template bool includeInSymtab<ELF64BE>(const SymbolBody &);
 
-template bool shouldKeepInSymtab<ELF32LE>(StringRef,
+template bool shouldKeepInSymtab<ELF32LE>(const ObjectFile<ELF32LE> &,
+                                          StringRef,
                                           const ELFFile<ELF32LE>::Elf_Sym &);
-template bool shouldKeepInSymtab<ELF32BE>(StringRef,
+template bool shouldKeepInSymtab<ELF32BE>(const ObjectFile<ELF32BE> &,
+                                          StringRef,
                                           const ELFFile<ELF32BE>::Elf_Sym &);
-template bool shouldKeepInSymtab<ELF64LE>(StringRef,
+template bool shouldKeepInSymtab<ELF64LE>(const ObjectFile<ELF64LE> &,
+                                          StringRef,
                                           const ELFFile<ELF64LE>::Elf_Sym &);
-template bool shouldKeepInSymtab<ELF64BE>(StringRef,
+template bool shouldKeepInSymtab<ELF64BE>(const ObjectFile<ELF64BE> &,
+                                          StringRef,
                                           const ELFFile<ELF64BE>::Elf_Sym &);
 }
 }
diff --git a/lld/ELF/OutputSections.h b/lld/ELF/OutputSections.h
index 8e789566e2f..a5cdeca19c2 100644
--- a/lld/ELF/OutputSections.h
+++ b/lld/ELF/OutputSections.h
@@ -46,7 +46,8 @@ bool includeInDynamicSymtab(const SymbolBody &B);
 
 template <class ELFT>
 bool shouldKeepInSymtab(
-    StringRef Name, const typename llvm::object::ELFFile<ELFT>::Elf_Sym &Sym);
+    const ObjectFile<ELFT> &File, StringRef Name,
+    const typename llvm::object::ELFFile<ELFT>::Elf_Sym &Sym);
 
 // This represents a section in an output file.
 // Different sub classes represent different types of sections. Some contain
diff --git a/lld/ELF/SymbolTable.cpp b/lld/ELF/SymbolTable.cpp
index cef2b916b94..4be047200d5 100644
--- a/lld/ELF/SymbolTable.cpp
+++ b/lld/ELF/SymbolTable.cpp
@@ -45,8 +45,10 @@ void SymbolTable::addFile(std::unique_ptr<InputFile> File) {
     S->parseSoName();
     if (!IncludedSoNames.insert(S->getSoName()).second)
       return;
+    S->parse();
+  } else {
+    cast<ObjectFileBase>(File.get())->parse(Comdats);
   }
-  File->parse();
   addELFFile(cast<ELFFileBase>(File.release()));
 }
 
diff --git a/lld/ELF/SymbolTable.h b/lld/ELF/SymbolTable.h
index f33a36c7a9b..890fa391db4 100644
--- a/lld/ELF/SymbolTable.h
+++ b/lld/ELF/SymbolTable.h
@@ -95,6 +95,8 @@ private:
   llvm::MapVector<StringRef, Symbol *> Symtab;
   llvm::BumpPtrAllocator Alloc;
 
+  llvm::DenseSet<StringRef> Comdats;
+
   // The writer needs to infer the machine type from the object files.
   std::vector<std::unique_ptr<ObjectFileBase>> ObjectFiles;
 
diff --git a/lld/ELF/Writer.cpp b/lld/ELF/Writer.cpp
index c3fd6886ac1..85fa54a3f07 100644
--- a/lld/ELF/Writer.cpp
+++ b/lld/ELF/Writer.cpp
@@ -295,8 +295,9 @@ template <class ELFT> void Writer<ELFT>::copyLocalSymbols() {
       ErrorOr<StringRef> SymNameOrErr = Sym.getName(File.getStringTable());
       error(SymNameOrErr);
       StringRef SymName = *SymNameOrErr;
-      if (shouldKeepInSymtab<ELFT>(SymName, Sym))
-        Out<ELFT>::SymTab->addSymbol(SymName, true);
+      if (!shouldKeepInSymtab<ELFT>(File, SymName, Sym))
+        continue;
+      Out<ELFT>::SymTab->addSymbol(SymName, true);
     }
   }
 }
@@ -398,11 +399,11 @@ template <class ELFT> void Writer<ELFT>::createSections() {
   for (const std::unique_ptr<ObjectFileBase> &FileB : Symtab.getObjectFiles()) {
     auto &File = cast<ObjectFile<ELFT>>(*FileB);
     for (InputSection<ELFT> *C : File.getSections()) {
-      if (!C)
+      if (!C || C == &InputSection<ELFT>::Discarded)
         continue;
       const Elf_Shdr *H = C->getSectionHdr();
-      SectionKey<ELFT::Is64Bits> Key{C->getSectionName(), H->sh_type,
-                                     H->sh_flags};
+      uintX_t OutFlags = H->sh_flags & ~SHF_GROUP;
+      SectionKey<ELFT::Is64Bits> Key{C->getSectionName(), H->sh_type, OutFlags};
       OutputSection<ELFT> *&Sec = Map[Key];
       if (!Sec) {
         Sec = new (CAlloc.Allocate())
diff --git a/lld/test/elf2/Inputs/comdat.s b/lld/test/elf2/Inputs/comdat.s
new file mode 100644
index 00000000000..467bfa4b8da
--- /dev/null
+++ b/lld/test/elf2/Inputs/comdat.s
@@ -0,0 +1,3 @@
+        .section .text3,"axG",@progbits,zed,comdat,unique,0
+        .global abc
+abc:
diff --git a/lld/test/elf2/comdat.s b/lld/test/elf2/comdat.s
new file mode 100644
index 00000000000..61435298fdd
--- /dev/null
+++ b/lld/test/elf2/comdat.s
@@ -0,0 +1,72 @@
+// RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
+// RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %p/Inputs/comdat.s -o %t2.o
+// RUN: ld.lld2 -shared %t.o %t.o %t2.o -o %t
+// RUN: llvm-objdump -d %t | FileCheck %s
+// RUN: llvm-readobj -s -t %t | FileCheck --check-prefix=READ %s
+// REQUIRES: x86
+
+        .section	.text2,"axG",@progbits,foo,comdat,unique,0
+foo:
+        nop
+
+// CHECK: Disassembly of section .text2:
+// CHECK-NEXT: foo:
+// CHECK-NEXT:   2000: {{.*}}  nop
+// CHECK-NOT: nop
+
+        .section bar, "ax"
+        call foo
+
+// CHECK: Disassembly of section bar:
+// CHECK-NEXT: bar:
+// 0x2000 - 0x2001 - 5 = -6
+// 0      - 0x2006 - 5 = -8203
+// CHECK-NEXT:   2001:	{{.*}}  callq  -6
+// CHECK-NEXT:   2006:	{{.*}}  callq  -8203
+
+        .section .text3,"axG",@progbits,zed,comdat,unique,0
+
+
+// READ:      Name: .text2
+// READ-NEXT: Type: SHT_PROGBITS
+// READ-NEXT: Flags [
+// READ-NEXT:   SHF_ALLOC
+// READ-NEXT:   SHF_EXECINSTR
+// READ-NEXT: ]
+
+// READ:      Name: .text3
+// READ-NEXT: Type: SHT_PROGBITS
+// READ-NEXT: Flags [
+// READ-NEXT:   SHF_ALLOC
+// READ-NEXT:   SHF_EXECINSTR
+// READ-NEXT: ]
+
+// READ:      Symbols [
+// READ-NEXT:   Symbol {
+// READ-NEXT:     Name:  (0)
+// READ-NEXT:     Value: 0x0
+// READ-NEXT:     Size: 0
+// READ-NEXT:     Binding: Local
+// READ-NEXT:     Type: None
+// READ-NEXT:     Other: 0
+// READ-NEXT:     Section: Undefined
+// READ-NEXT:   }
+// READ-NEXT:   Symbol {
+// READ-NEXT:     Name: foo
+// READ-NEXT:     Value
+// READ-NEXT:     Size: 0
+// READ-NEXT:     Binding: Local
+// READ-NEXT:     Type: None
+// READ-NEXT:     Other: 0
+// READ-NEXT:     Section: .text
+// READ-NEXT:   }
+// READ-NEXT:   Symbol {
+// READ-NEXT:     Name: abc
+// READ-NEXT:     Value: 0x0
+// READ-NEXT:     Size: 0
+// READ-NEXT:     Binding: Global
+// READ-NEXT:     Type: None
+// READ-NEXT:     Other: 0
+// READ-NEXT:     Section: Undefined
+// READ-NEXT:   }
+// READ-NEXT: ]