8 files changed, 111 insertions, 69 deletions
diff --git a/COFF/ICF.cpp b/COFF/ICF.cpp
index 3b7cc424f0a2..da8ca360542a 100644
--- a/COFF/ICF.cpp
+++ b/COFF/ICF.cpp
@@ -56,7 +56,6 @@ private:
 
   std::vector<SectionChunk *> Chunks;
   int Cnt = 0;
-  std::atomic<uint32_t> NextId = {1};
   std::atomic<bool> Repeat = {false};
 };
 
@@ -98,10 +97,10 @@ void ICF::segregate(size_t Begin, size_t End, bool Constant) {
         });
     size_t Mid = Bound - Chunks.begin();
 
-    // Split [Begin, End) into [Begin, Mid) and [Mid, End).
-    uint32_t Id = NextId++;
+    // Split [Begin, End) into [Begin, Mid) and [Mid, End). We use Mid as an
+    // equivalence class ID because every group ends with a unique index.
     for (size_t I = Begin; I < Mid; ++I)
-      Chunks[I]->Class[(Cnt + 1) % 2] = Id;
+      Chunks[I]->Class[(Cnt + 1) % 2] = Mid;
 
     // If we created a group, we need to iterate the main loop again.
     if (Mid != End)
@@ -186,6 +185,7 @@ void ICF::forEachClass(std::function<void(size_t, size_t)> Fn) {
   // call Fn sequentially.
   if (Chunks.size() < 1024) {
     forEachClassRange(0, Chunks.size(), Fn);
+    ++Cnt;
     return;
   }
 
@@ -193,9 +193,10 @@ void ICF::forEachClass(std::function<void(size_t, size_t)> Fn) {
   size_t NumShards = 256;
   size_t Step = Chunks.size() / NumShards;
   for_each_n(parallel::par, size_t(0), NumShards, [&](size_t I) {
-    forEachClassRange(I * Step, (I + 1) * Step, Fn);
+    size_t End = (I == NumShards - 1) ? Chunks.size() : (I + 1) * Step;
+    forEachClassRange(I * Step, End, Fn);
   });
-  forEachClassRange(Step * NumShards, Chunks.size(), Fn);
+  ++Cnt;
 }
 
 // Merge identical COMDAT sections.
@@ -203,22 +204,20 @@ void ICF::forEachClass(std::function<void(size_t, size_t)> Fn) {
 // contents and relocations are all the same.
 void ICF::run(const std::vector<Chunk *> &Vec) {
   // Collect only mergeable sections and group by hash value.
+  uint32_t NextId = 1;
   for (Chunk *C : Vec) {
-    auto *SC = dyn_cast<SectionChunk>(C);
-    if (!SC)
-      continue;
-
-    if (isEligible(SC)) {
-      // Set MSB to 1 to avoid collisions with non-hash classs.
-      SC->Class[0] = getHash(SC) | (1 << 31);
-      Chunks.push_back(SC);
-    } else {
-      SC->Class[0] = NextId++;
+    if (auto *SC = dyn_cast<SectionChunk>(C)) {
+      if (isEligible(SC))
+        Chunks.push_back(SC);
+      else
+        SC->Class[0] = NextId++;
     }
   }
 
-  if (Chunks.empty())
-    return;
+  // Initially, we use hash values to partition sections.
+  for (SectionChunk *SC : Chunks)
+    // Set MSB to 1 to avoid collisions with non-hash classs.
+    SC->Class[0] = getHash(SC) | (1 << 31);
 
   // From now on, sections in Chunks are ordered so that sections in
   // the same group are consecutive in the vector.
@@ -229,14 +228,12 @@ void ICF::run(const std::vector<Chunk *> &Vec) {
 
   // Compare static contents and assign unique IDs for each static content.
   forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
-  ++Cnt;
 
   // Split groups by comparing relocations until convergence is obtained.
   do {
     Repeat = false;
     forEachClass(
         [&](size_t Begin, size_t End) { segregate(Begin, End, false); });
-    ++Cnt;
   } while (Repeat);
 
   log("ICF needed " + Twine(Cnt) + " iterations");
diff --git a/COFF/InputFiles.cpp b/COFF/InputFiles.cpp
index 6e6465cd5d62..258d9fd74b4d 100644
--- a/COFF/InputFiles.cpp
+++ b/COFF/InputFiles.cpp
@@ -48,13 +48,11 @@ namespace coff {
 /// alias to Target.
 static void checkAndSetWeakAlias(SymbolTable *Symtab, InputFile *F,
                                  SymbolBody *Source, SymbolBody *Target) {
-  auto *U = dyn_cast<Undefined>(Source);
-  if (!U)
-    return;
-  else if (!U->WeakAlias)
+  if (auto *U = dyn_cast<Undefined>(Source)) {
+    if (U->WeakAlias && U->WeakAlias != Target)
+      Symtab->reportDuplicate(Source->symbol(), F);
     U->WeakAlias = Target;
-  else if (U->WeakAlias != Target)
-    Symtab->reportDuplicate(Source->symbol(), F);
+  }
 }
 
 ArchiveFile::ArchiveFile(MemoryBufferRef M) : InputFile(ArchiveKind, M) {}
@@ -153,8 +151,10 @@ void ObjectFile::initializeSymbols() {
   uint32_t NumSymbols = COFFObj->getNumberOfSymbols();
   SymbolBodies.reserve(NumSymbols);
   SparseSymbolBodies.resize(NumSymbols);
+
   SmallVector<std::pair<SymbolBody *, uint32_t>, 8> WeakAliases;
   int32_t LastSectionNumber = 0;
+
   for (uint32_t I = 0; I < NumSymbols; ++I) {
     // Get a COFFSymbolRef object.
     ErrorOr<COFFSymbolRef> SymOrErr = COFFObj->getSymbol(I);
@@ -185,9 +185,12 @@ void ObjectFile::initializeSymbols() {
     I += Sym.getNumberOfAuxSymbols();
     LastSectionNumber = Sym.getSectionNumber();
   }
-  for (auto WeakAlias : WeakAliases)
-    checkAndSetWeakAlias(Symtab, this, WeakAlias.first,
-                         SparseSymbolBodies[WeakAlias.second]);
+
+  for (auto &KV : WeakAliases) {
+    SymbolBody *Sym = KV.first;
+    uint32_t Idx = KV.second;
+    checkAndSetWeakAlias(Symtab, this, Sym, SparseSymbolBodies[Idx]);
+  }
 }
 
 SymbolBody *ObjectFile::createUndefined(COFFSymbolRef Sym) {
diff --git a/COFF/InputFiles.h b/COFF/InputFiles.h
index 9e32b3b9f9d6..9449f24ac241 100644
--- a/COFF/InputFiles.h
+++ b/COFF/InputFiles.h
@@ -10,6 +10,7 @@
 #ifndef LLD_COFF_INPUT_FILES_H
 #define LLD_COFF_INPUT_FILES_H
 
+#include "Config.h"
 #include "lld/Core/LLVM.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseSet.h"
@@ -161,7 +162,9 @@ private:
 // for details about the format.
 class ImportFile : public InputFile {
 public:
-  explicit ImportFile(MemoryBufferRef M) : InputFile(ImportKind, M) {}
+  explicit ImportFile(MemoryBufferRef M)
+      : InputFile(ImportKind, M), Live(!Config->DoGC) {}
+
   static bool classof(const InputFile *F) { return F->kind() == ImportKind; }
 
   DefinedImportData *ImpSym = nullptr;
@@ -176,6 +179,14 @@ public:
   StringRef ExternalName;
   const coff_import_header *Hdr;
   Chunk *Location = nullptr;
+
+  // We want to eliminate dllimported symbols if no one actually refers them.
+  // This "Live" bit is used to keep track of which import library members
+  // are actually in use.
+  //
+  // If the Live bit is turned off by MarkLive, Writer will ignore dllimported
+  // symbols provided by this import library member.
+  bool Live;
 };
 
 // Used for LTO.
diff --git a/COFF/MarkLive.cpp b/COFF/MarkLive.cpp
index 0156d238b672..25e5cc350673 100644
--- a/COFF/MarkLive.cpp
+++ b/COFF/MarkLive.cpp
@@ -37,19 +37,26 @@ void markLive(const std::vector<Chunk *> &Chunks) {
     Worklist.push_back(C);
   };
 
+  auto AddSym = [&](SymbolBody *B) {
+    if (auto *Sym = dyn_cast<DefinedRegular>(B))
+      Enqueue(Sym->getChunk());
+    else if (auto *Sym = dyn_cast<DefinedImportData>(B))
+      Sym->File->Live = true;
+    else if (auto *Sym = dyn_cast<DefinedImportThunk>(B))
+      Sym->WrappedSym->File->Live = true;
+  };
+
   // Add GC root chunks.
   for (SymbolBody *B : Config->GCRoot)
-    if (auto *D = dyn_cast<DefinedRegular>(B))
-      Enqueue(D->getChunk());
+    AddSym(B);
 
   while (!Worklist.empty()) {
     SectionChunk *SC = Worklist.pop_back_val();
     assert(SC->isLive() && "We mark as live when pushing onto the worklist!");
 
     // Mark all symbols listed in the relocation table for this section.
-    for (SymbolBody *S : SC->symbols())
-      if (auto *D = dyn_cast<DefinedRegular>(S))
-        Enqueue(D->getChunk());
+    for (SymbolBody *B : SC->symbols())
+      AddSym(B);
 
     // Mark associative sections if any.
     for (SectionChunk *C : SC->children())
diff --git a/COFF/PDB.cpp b/COFF/PDB.cpp
index 0266148cc6c9..a3b3ab7bbab0 100644
--- a/COFF/PDB.cpp
+++ b/COFF/PDB.cpp
@@ -99,6 +99,12 @@ static void addTypeInfo(pdb::TpiStreamBuilder &TpiBuilder,
 static void mergeDebugT(SymbolTable *Symtab, pdb::PDBFileBuilder &Builder,
                         codeview::TypeTableBuilder &TypeTable,
                         codeview::TypeTableBuilder &IDTable) {
+  // Follow type servers.  If the same type server is encountered more than
+  // once for this instance of `PDBTypeServerHandler` (for example if many
+  // object files reference the same TypeServer), the types from the
+  // TypeServer will only be visited once.
+  pdb::PDBTypeServerHandler Handler;
+
   // Visit all .debug$T sections to add them to Builder.
   for (ObjectFile *File : Symtab->ObjectFiles) {
     ArrayRef<uint8_t> Data = getDebugSection(File, ".debug$T");
@@ -109,16 +115,11 @@ static void mergeDebugT(SymbolTable *Symtab, pdb::PDBFileBuilder &Builder,
     codeview::CVTypeArray Types;
     BinaryStreamReader Reader(Stream);
     SmallVector<TypeIndex, 128> SourceToDest;
-    // Follow type servers.  If the same type server is encountered more than
-    // once for this instance of `PDBTypeServerHandler` (for example if many
-    // object files reference the same TypeServer), the types from the
-    // TypeServer will only be visited once.
-    pdb::PDBTypeServerHandler Handler;
     Handler.addSearchPath(llvm::sys::path::parent_path(File->getName()));
     if (auto EC = Reader.readArray(Types, Reader.getLength()))
       fatal(EC, "Reader::readArray failed");
-    if (auto Err = codeview::mergeTypeStreams(IDTable, TypeTable, SourceToDest,
-                                              &Handler, Types))
+    if (auto Err = codeview::mergeTypeAndIdRecords(
+            IDTable, TypeTable, SourceToDest, &Handler, Types))
       fatal(Err, "codeview::mergeTypeStreams failed");
   }
 
diff --git a/COFF/Symbols.cpp b/COFF/Symbols.cpp
index 993e920ce7f7..5c185a511dd7 100644
--- a/COFF/Symbols.cpp
+++ b/COFF/Symbols.cpp
@@ -61,16 +61,19 @@ COFFSymbolRef DefinedCOFF::getCOFFSymbol() {
   return COFFSymbolRef(reinterpret_cast<const coff_symbol32 *>(Sym));
 }
 
+static Chunk *makeImportThunk(DefinedImportData *S, uint16_t Machine) {
+  if (Machine == AMD64)
+    return make<ImportThunkChunkX64>(S);
+  if (Machine == I386)
+    return make<ImportThunkChunkX86>(S);
+  assert(Machine == ARMNT);
+  return make<ImportThunkChunkARM>(S);
+}
+
 DefinedImportThunk::DefinedImportThunk(StringRef Name, DefinedImportData *S,
                                        uint16_t Machine)
-    : Defined(DefinedImportThunkKind, Name) {
-  switch (Machine) {
-  case AMD64: Data = make<ImportThunkChunkX64>(S); return;
-  case I386:  Data = make<ImportThunkChunkX86>(S); return;
-  case ARMNT: Data = make<ImportThunkChunkARM>(S); return;
-  default:    llvm_unreachable("unknown machine type");
-  }
-}
+    : Defined(DefinedImportThunkKind, Name), WrappedSym(S),
+      Data(makeImportThunk(S, Machine)) {}
 
 Defined *Undefined::getWeakAlias() {
   // A weak alias may be a weak alias to another symbol, so check recursively.
diff --git a/COFF/Symbols.h b/COFF/Symbols.h
index 1b83f73ff20c..801fc87f91d9 100644
--- a/COFF/Symbols.h
+++ b/COFF/Symbols.h
@@ -300,7 +300,6 @@ public:
   void setLocation(Chunk *AddressTable) { File->Location = AddressTable; }
   uint16_t getOrdinal() { return File->Hdr->OrdinalHint; }
 
-private:
   ImportFile *File;
 };
 
@@ -320,6 +319,8 @@ public:
   uint64_t getRVA() { return Data->getRVA(); }
   Chunk *getChunk() { return Data; }
 
+  DefinedImportData *WrappedSym;
+
 private:
   Chunk *Data;
 };
diff --git a/COFF/Writer.cpp b/COFF/Writer.cpp
index cf3ad7ef045c..fb1f3cae5bb2 100644
--- a/COFF/Writer.cpp
+++ b/COFF/Writer.cpp
@@ -365,6 +365,9 @@ void Writer::createImportTables() {
   // the same order as in the command line. (That affects DLL
   // initialization order, and this ordering is MSVC-compatible.)
   for (ImportFile *File : Symtab->ImportFiles) {
+    if (!File->Live)
+      continue;
+
     std::string DLL = StringRef(File->DLLName).lower();
     if (Config->DLLOrder.count(DLL) == 0)
       Config->DLLOrder[DLL] = Config->DLLOrder.size();
@@ -372,19 +375,28 @@ void Writer::createImportTables() {
 
   OutputSection *Text = createSection(".text");
   for (ImportFile *File : Symtab->ImportFiles) {
+    if (!File->Live)
+      continue;
+
     if (DefinedImportThunk *Thunk = File->ThunkSym)
       Text->addChunk(Thunk->getChunk());
+
     if (Config->DelayLoads.count(StringRef(File->DLLName).lower())) {
+      if (!File->ThunkSym)
+        fatal("cannot delay-load " + toString(File) +
+              " due to import of data: " + toString(*File->ImpSym));
       DelayIdata.add(File->ImpSym);
     } else {
       Idata.add(File->ImpSym);
     }
   }
+
   if (!Idata.empty()) {
     OutputSection *Sec = createSection(".idata");
     for (Chunk *C : Idata.getChunks())
       Sec->addChunk(C);
   }
+
   if (!DelayIdata.empty()) {
     Defined *Helper = cast<Defined>(Config->DelayLoadHelper);
     DelayIdata.create(Helper);
@@ -437,6 +449,14 @@ Optional<coff_symbol16> Writer::createSymbol(Defined *Def) {
     if (!D->getChunk()->isLive())
       return None;
 
+  if (auto *Sym = dyn_cast<DefinedImportData>(Def))
+    if (!Sym->File->Live)
+      return None;
+
+  if (auto *Sym = dyn_cast<DefinedImportThunk>(Def))
+    if (!Sym->WrappedSym->File->Live)
+      return None;
+
   coff_symbol16 Sym;
   StringRef Name = Def->getName();
   if (Name.size() > COFF::NameSize) {
@@ -491,14 +511,17 @@ void Writer::createSymbolAndStringTable() {
     Sec->setStringTableOff(addEntryToStringTable(Name));
   }
 
-  for (lld::coff::ObjectFile *File : Symtab->ObjectFiles)
-    for (SymbolBody *B : File->getSymbols())
-      if (auto *D = dyn_cast<Defined>(B))
-        if (!D->WrittenToSymtab) {
-          D->WrittenToSymtab = true;
-          if (Optional<coff_symbol16> Sym = createSymbol(D))
-            OutputSymtab.push_back(*Sym);
-        }
+  for (lld::coff::ObjectFile *File : Symtab->ObjectFiles) {
+    for (SymbolBody *B : File->getSymbols()) {
+      auto *D = dyn_cast<Defined>(B);
+      if (!D || D->WrittenToSymtab)
+        continue;
+      D->WrittenToSymtab = true;
+
+      if (Optional<coff_symbol16> Sym = createSymbol(D))
+        OutputSymtab.push_back(*Sym);
+    }
+  }
 
   OutputSection *LastSection = OutputSections.back();
   // We position the symbol table to be adjacent to the end of the last section.
@@ -782,19 +805,15 @@ void Writer::writeBuildId() {
   if (BuildId == nullptr)
     return;
 
-  MD5 Hash;
-  MD5::MD5Result Res;
-
-  Hash.update(ArrayRef<uint8_t>{Buffer->getBufferStart(),
-                                Buffer->getBufferEnd()});
-  Hash.final(Res);
-
   assert(BuildId->DI->Signature.CVSignature == OMF::Signature::PDB70 &&
          "only PDB 7.0 is supported");
-  assert(sizeof(Res) == sizeof(BuildId->DI->PDB70.Signature) &&
+  assert(sizeof(BuildId->DI->PDB70.Signature) == 16 &&
          "signature size mismatch");
-  memcpy(BuildId->DI->PDB70.Signature, Res.Bytes.data(),
-         sizeof(codeview::PDB70DebugInfo::Signature));
+
+  // Compute an MD5 hash.
+  ArrayRef<uint8_t> Buf(Buffer->getBufferStart(), Buffer->getBufferEnd());
+  memcpy(BuildId->DI->PDB70.Signature, MD5::hash(Buf).data(), 16);
+
   // TODO(compnerd) track the Age
   BuildId->DI->PDB70.Age = 1;
 }