2 files changed, 234 insertions, 178 deletions

diff --git a/lld/COFF/Symbols.cpp b/lld/COFF/Symbols.cpp
index 6bc9e4ada03a..77cc82820b2d 100644
--- a/lld/COFF/Symbols.cpp
+++ b/lld/COFF/Symbols.cpp
@@ -21,112 +21,170 @@ using llvm::sys::fs::file_magic;
 namespace lld {
 namespace coff {
 
+StringRef SymbolBody::getName() {
+  // DefinedCOFF names are read lazily for a performance reason.
+  // Non-external symbol names are never used by the linker except for logging
+  // or debugging. Their internal references are resolved not by name but by
+  // symbol index. And because they are not external, no one can refer them by
+  // name. Object files contain lots of non-external symbols, and creating
+  // StringRefs for them (which involves lots of strlen() on the string table)
+  // is a waste of time.
+  if (Name.empty()) {
+    auto *D = cast<DefinedCOFF>(this);
+    D->File->getCOFFObj()->getSymbolName(D->Sym, Name);
+  }
+  return Name;
+}
+
 // Returns 1, 0 or -1 if this symbol should take precedence
 // over the Other, tie or lose, respectively.
-int DefinedRegular::compare(SymbolBody *Other) {
-  if (Other->kind() < kind())
+int SymbolBody::compare(SymbolBody *Other) {
+  Kind LK = kind(), RK = Other->kind();
+
+  // Normalize so that the smaller kind is on the left.
+  if (LK > RK)
     return -Other->compare(this);
-  if (auto *D = dyn_cast<DefinedRegular>(Other)) {
-    if (isCOMDAT() && D->isCOMDAT())
+
+  // First handle comparisons between two different kinds.
+  if (LK != RK) {
+
+    if (RK > LastDefinedKind) {
+      if (LK == LazyKind && cast<Undefined>(Other)->getWeakAlias())
+        return -1;
+
+      // The LHS is either defined or lazy and so it wins.
+      assert((LK <= LastDefinedKind || LK == LazyKind) && "Bad kind!");
+      return 1;
+    }
+
+    // Bitcode has special complexities.
+    if (RK == DefinedBitcodeKind) {
+      auto *RHS = cast<DefinedBitcode>(Other);
+
+      switch (LK) {
+      case DefinedCommonKind:
+        return 1;
+
+      case DefinedRegularKind:
+        // As an approximation, regular symbols win over bitcode symbols,
+        // but we definitely have a conflict if the regular symbol is not
+        // replaceable and neither is the bitcode symbol. We do not
+        // replicate the rest of the symbol resolution logic here; symbol
+        // resolution will be done accurately after lowering bitcode symbols
+        // to regular symbols in addCombinedLTOObject().
+        if (cast<DefinedRegular>(this)->isCOMDAT() || RHS->IsReplaceable)
+          return 1;
+
+        // Fallthrough to the default of a tie otherwise.
+      default:
+        return 0;
+      }
+    }
+
+    // Either of the object file kind will trump a higher kind.
+    if (LK <= LastDefinedCOFFKind)
       return 1;
+
+    // The remaining kind pairs are ties amongst defined symbols.
     return 0;
   }
-  return 1;
-}
-
-int DefinedCommon::compare(SymbolBody *Other) {
-  if (Other->kind() < kind())
-    return -Other->compare(this);
-  if (auto *D = dyn_cast<DefinedCommon>(Other))
-    return getSize() > D->getSize() ? 1 : -1;
-  if (isa<Lazy>(Other) || isa<Undefined>(Other))
-    return 1;
-  return -1;
-}
-
-int DefinedBitcode::compare(SymbolBody *Other) {
-  assert(Other->kind() >= kind());
-  if (!isa<Defined>(Other))
-    return 1;
 
-  if (auto *B = dyn_cast<DefinedBitcode>(Other)) {
-    if (!Replaceable && !B->Replaceable)
-      return 0;
-    // Non-replaceable symbols win.
-    return Replaceable ? -1 : 1;
+  // Now handle the case where the kinds are the same.
+  switch (LK) {
+  case DefinedRegularKind: {
+    auto *LHS = cast<DefinedRegular>(this);
+    auto *RHS = cast<DefinedRegular>(Other);
+    return (LHS->isCOMDAT() && RHS->isCOMDAT()) ? 1 : 0;
   }
 
-  // As an approximation, regular symbols win over bitcode symbols,
-  // but we definitely have a conflict if the regular symbol is not
-  // replaceable and neither is the bitcode symbol. We do not
-  // replicate the rest of the symbol resolution logic here; symbol
-  // resolution will be done accurately after lowering bitcode symbols
-  // to regular symbols in addCombinedLTOObject().
-  if (auto *D = dyn_cast<DefinedRegular>(Other)) {
-    if (Replaceable || D->isCOMDAT())
-      return -1;
-    return 0;
+  case DefinedCommonKind: {
+    auto *LHS = cast<DefinedCommon>(this);
+    auto *RHS = cast<DefinedCommon>(Other);
+    return LHS->getSize() > RHS->getSize() ? 1 : -1;
   }
-  if (isa<DefinedCommon>(Other))
-    return -1;
-  return 0;
-}
 
-int Defined::compare(SymbolBody *Other) {
-  if (Other->kind() < kind())
-    return -Other->compare(this);
-  if (isa<Defined>(Other))
-    return 0;
-  return 1;
-}
+  case DefinedBitcodeKind: {
+    auto *LHS = cast<DefinedBitcode>(this);
+    auto *RHS = cast<DefinedBitcode>(Other);
+    // If both are non-replaceable, we have a tie.
+    if (!LHS->IsReplaceable && !RHS->IsReplaceable)
+      return 0;
 
-int Lazy::compare(SymbolBody *Other) {
-  if (Other->kind() < kind())
-    return -Other->compare(this);
+    // Non-replaceable symbols win, but even two replaceable symboles don't
+    // tie.
+    return LHS->IsReplaceable ? -1 : 1;
+  }
 
-  // Undefined symbols with weak aliases will turn into defined
-  // symbols if they remain undefined, so we don't need to resolve
-  // such symbols.
-  if (auto *U = dyn_cast<Undefined>(Other))
-    if (U->getWeakAlias())
-      return -1;
-  return 1;
-}
+  case LazyKind:
+    // Don't tie, just pick the LHS.
+    return 1;
 
-int Undefined::compare(SymbolBody *Other) {
-  if (Other->kind() < kind())
-    return -Other->compare(this);
-  if (cast<Undefined>(Other)->getWeakAlias())
-    return -1;
-  return 1;
-}
+  case UndefinedKind:
+    // Don't tie, just pick the LHS unless the RHS has a weak alias.
+    return cast<Undefined>(Other)->getWeakAlias() ? -1 : 1;
 
-StringRef DefinedRegular::getName() {
-  // DefinedSymbol's name is read lazily for a performance reason.
-  // Non-external symbol names are never used by the linker
-  // except for logging or debugging.
-  // Their internal references are resolved not by name but by symbol index.
-  // And because they are not external, no one can refer them by name.
-  // Object files contain lots of non-external symbols, and creating
-  // StringRefs for them (which involves lots of strlen() on the string table)
-  // is a waste of time.
-  if (Name.empty())
-    File->getCOFFObj()->getSymbolName(Sym, Name);
-  return Name;
+  case DefinedLocalImportKind:
+  case DefinedImportThunkKind:
+  case DefinedImportDataKind:
+  case DefinedAbsoluteKind:
+    // These all simply tie.
+    return 0;
+  }
 }
 
-StringRef DefinedCommon::getName() {
-  if (Name.empty())
-    File->getCOFFObj()->getSymbolName(Sym, Name);
-  return Name;
+std::string SymbolBody::getDebugName() {
+  std::string N = getName().str();
+  if (auto *D = dyn_cast<DefinedCOFF>(this)) {
+    N += " ";
+    N += D->File->getShortName();
+  }
+  return N;
 }
 
-std::string DefinedRegular::getDebugName() {
-  return (getName() + " " + File->getShortName()).str();
+uint64_t Defined::getRVA() {
+  switch (kind()) {
+  case DefinedAbsoluteKind:
+    return cast<DefinedAbsolute>(this)->getRVA();
+  case DefinedImportDataKind:
+    return cast<DefinedImportData>(this)->getRVA();
+  case DefinedImportThunkKind:
+    return cast<DefinedImportThunk>(this)->getRVA();
+  case DefinedLocalImportKind:
+    return cast<DefinedLocalImport>(this)->getRVA();
+  case DefinedCommonKind:
+    return cast<DefinedCommon>(this)->getRVA();
+  case DefinedRegularKind:
+    return cast<DefinedRegular>(this)->getRVA();
+
+  case DefinedBitcodeKind:
+    llvm_unreachable("There is no address for a bitcode symbol.");
+  case LazyKind:
+  case UndefinedKind:
+    llvm_unreachable("Cannot get the address for an undefined symbol.");
+  }
 }
 
-std::string DefinedCommon::getDebugName() {
-  return (getName() + " " + File->getShortName()).str();
+uint64_t Defined::getFileOff() {
+  switch (kind()) {
+  case DefinedImportDataKind:
+    return cast<DefinedImportData>(this)->getFileOff();
+  case DefinedImportThunkKind:
+    return cast<DefinedImportThunk>(this)->getFileOff();
+  case DefinedLocalImportKind:
+    return cast<DefinedLocalImport>(this)->getFileOff();
+  case DefinedCommonKind:
+    return cast<DefinedCommon>(this)->getFileOff();
+  case DefinedRegularKind:
+    return cast<DefinedRegular>(this)->getFileOff();
+
+  case DefinedBitcodeKind:
+    llvm_unreachable("There is no file offset for a bitcode symbol.");
+  case DefinedAbsoluteKind:
+    llvm_unreachable("Cannot get a file offset for an absolute symbol.");
+  case LazyKind:
+  case UndefinedKind:
+    llvm_unreachable("Cannot get a file offset for an undefined symbol.");
+  }
 }
 
 ErrorOr<std::unique_ptr<InputFile>> Lazy::getMember() {
diff --git a/lld/COFF/Symbols.h b/lld/COFF/Symbols.h
index 4825bd7f97c4..db2aa1eb32b8 100644
--- a/lld/COFF/Symbols.h
+++ b/lld/COFF/Symbols.h
@@ -43,27 +43,33 @@ struct Symbol {
 class SymbolBody {
 public:
   enum Kind {
-    DefinedFirst,
-    DefinedBitcodeKind,
-    DefinedAbsoluteKind,
-    DefinedImportDataKind,
-    DefinedImportThunkKind,
-    DefinedLocalImportKind,
+    // The order of these is significant. We start with the regular defined
+    // symbols as those are the most prevelant and the zero tag is the cheapest
+    // to set. Among the defined kinds, the lower the kind is preferred over
+    // the higher kind when testing wether one symbol should take precedence
+    // over another.
+    DefinedRegularKind = 0,
     DefinedCommonKind,
-    DefinedRegularKind,
-    DefinedLast,
+    DefinedLocalImportKind,
+    DefinedImportThunkKind,
+    DefinedImportDataKind,
+    DefinedAbsoluteKind,
+    DefinedBitcodeKind,
+
     LazyKind,
     UndefinedKind,
+
+    LastDefinedCOFFKind = DefinedCommonKind,
+    LastDefinedKind = DefinedBitcodeKind,
   };
 
-  Kind kind() const { return SymbolKind; }
-  virtual ~SymbolBody() {}
+  Kind kind() const { return static_cast<Kind>(SymbolKind); }
 
   // Returns true if this is an external symbol.
-  virtual bool isExternal() { return true; }
+  bool isExternal() { return IsExternal; }
 
   // Returns the symbol name.
-  virtual StringRef getName() = 0;
+  StringRef getName();
 
   // A SymbolBody has a backreference to a Symbol. Originally they are
   // doubly-linked. A backreference will never change. But the pointer
@@ -77,17 +83,27 @@ public:
   // Decides which symbol should "win" in the symbol table, this or
   // the Other. Returns 1 if this wins, -1 if the Other wins, or 0 if
   // they are duplicate (conflicting) symbols.
-  virtual int compare(SymbolBody *Other) = 0;
+  int compare(SymbolBody *Other);
 
   // Returns a name of this symbol including source file name.
   // Used only for debugging and logging.
-  virtual std::string getDebugName() { return getName(); }
+  std::string getDebugName();
 
 protected:
-  SymbolBody(Kind K) : SymbolKind(K) {}
+  explicit SymbolBody(Kind K, StringRef N = "")
+      : SymbolKind(K), IsExternal(true), IsCOMDAT(false),
+        IsReplaceable(false), Name(N) {}
 
-private:
-  const Kind SymbolKind;
+  const unsigned SymbolKind : 8;
+  unsigned IsExternal : 1;
+
+  // This bit is used by the \c DefinedRegular subclass.
+  unsigned IsCOMDAT : 1;
+
+  // This bit is used by the \c DefinedBitcode subclass.
+  unsigned IsReplaceable : 1;
+
+  StringRef Name;
   Symbol *Backref = nullptr;
 };
 
@@ -95,44 +111,55 @@ private:
 // etc.
 class Defined : public SymbolBody {
 public:
-  Defined(Kind K) : SymbolBody(K) {}
+  Defined(Kind K, StringRef N = "") : SymbolBody(K, N) {}
 
   static bool classof(const SymbolBody *S) {
-    Kind K = S->kind();
-    return DefinedFirst <= K && K <= DefinedLast;
+    return S->kind() <= LastDefinedKind;
   }
 
   // Returns the RVA (relative virtual address) of this symbol. The
   // writer sets and uses RVAs.
-  virtual uint64_t getRVA() = 0;
+  uint64_t getRVA();
 
   // Returns the file offset of this symbol in the final executable.
   // The writer uses this information to apply relocations.
-  virtual uint64_t getFileOff() = 0;
+  uint64_t getFileOff();
+};
 
-  int compare(SymbolBody *Other) override;
+// Symbols defined via a COFF object file.
+class DefinedCOFF : public Defined {
+  friend SymbolBody;
+public:
+  DefinedCOFF(Kind K, ObjectFile *F, COFFSymbolRef S)
+      : Defined(K), File(F), Sym(S) {}
+
+  static bool classof(const SymbolBody *S) {
+    return S->kind() <= LastDefinedCOFFKind;
+  }
+
+protected:
+  ObjectFile *File;
+  COFFSymbolRef Sym;
 };
 
 // Regular defined symbols read from object file symbol tables.
-class DefinedRegular : public Defined {
+class DefinedRegular : public DefinedCOFF {
 public:
   DefinedRegular(ObjectFile *F, COFFSymbolRef S, SectionChunk *C)
-      : Defined(DefinedRegularKind), File(F), Sym(S), Data(&C->Ptr),
-        IsCOMDAT(C->isCOMDAT()) {}
+      : DefinedCOFF(DefinedRegularKind, F, S), Data(&C->Ptr) {
+    IsExternal = Sym.isExternal();
+    IsCOMDAT = C->isCOMDAT();
+  }
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == DefinedRegularKind;
   }
 
-  uint64_t getFileOff() override {
+  uint64_t getFileOff() {
     return (*Data)->getFileOff() + Sym.getValue();
   }
 
-  StringRef getName() override;
-  uint64_t getRVA() override { return (*Data)->getRVA() + Sym.getValue(); }
-  bool isExternal() override { return Sym.isExternal(); }
-  int compare(SymbolBody *Other) override;
-  std::string getDebugName() override;
+  uint64_t getRVA() { return (*Data)->getRVA() + Sym.getValue(); }
   bool isCOMDAT() { return IsCOMDAT; }
   bool isLive() const { return (*Data)->isLive(); }
   void markLive() { (*Data)->markLive(); }
@@ -140,35 +167,28 @@ public:
   uint64_t getValue() { return Sym.getValue(); }
 
 private:
-  StringRef Name;
-  ObjectFile *File;
-  COFFSymbolRef Sym;
   SectionChunk **Data;
-  bool IsCOMDAT;
 };
 
-class DefinedCommon : public Defined {
+class DefinedCommon : public DefinedCOFF {
 public:
   DefinedCommon(ObjectFile *F, COFFSymbolRef S, CommonChunk *C)
-      : Defined(DefinedCommonKind), File(F), Sym(S), Data(C) {}
+      : DefinedCOFF(DefinedCommonKind, F, S), Data(C) {
+    IsExternal = Sym.isExternal();
+  }
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == DefinedCommonKind;
   }
 
-  StringRef getName() override;
-  uint64_t getRVA() override { return Data->getRVA(); }
-  bool isExternal() override { return Sym.isExternal(); }
-  uint64_t getFileOff() override { return Data->getFileOff(); }
-  int compare(SymbolBody *Other) override;
-  std::string getDebugName() override;
+  uint64_t getRVA() { return Data->getRVA(); }
+  uint64_t getFileOff() { return Data->getFileOff(); }
 
 private:
+  friend SymbolBody;
+
   uint64_t getSize() { return Sym.getValue(); }
 
-  StringRef Name;
-  ObjectFile *File;
-  COFFSymbolRef Sym;
   CommonChunk *Data;
 };
 
@@ -176,25 +196,21 @@ private:
 class DefinedAbsolute : public Defined {
 public:
   DefinedAbsolute(StringRef N, COFFSymbolRef S)
-      : Defined(DefinedAbsoluteKind), Name(N), VA(S.getValue()),
-        External(S.isExternal()) {}
+      : Defined(DefinedAbsoluteKind, N), VA(S.getValue()) {
+    IsExternal = S.isExternal();
+  }
 
   DefinedAbsolute(StringRef N, uint64_t V)
-      : Defined(DefinedAbsoluteKind), Name(N), VA(V) {}
+      : Defined(DefinedAbsoluteKind, N), VA(V) {}
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == DefinedAbsoluteKind;
   }
 
-  StringRef getName() override { return Name; }
-  uint64_t getRVA() override { return VA - Config->ImageBase; }
-  uint64_t getFileOff() override { llvm_unreachable("internal error"); }
-  bool isExternal() override { return External; }
+  uint64_t getRVA() { return VA - Config->ImageBase; }
 
 private:
-  StringRef Name;
   uint64_t VA;
-  bool External = true;
 };
 
 // This class represents a symbol defined in an archive file. It is
@@ -205,19 +221,15 @@ private:
 class Lazy : public SymbolBody {
 public:
   Lazy(ArchiveFile *F, const Archive::Symbol S)
-      : SymbolBody(LazyKind), Name(S.getName()), File(F), Sym(S) {}
+      : SymbolBody(LazyKind, S.getName()), File(F), Sym(S) {}
 
   static bool classof(const SymbolBody *S) { return S->kind() == LazyKind; }
-  StringRef getName() override { return Name; }
 
   // Returns an object file for this symbol, or a nullptr if the file
   // was already returned.
   ErrorOr<std::unique_ptr<InputFile>> getMember();
 
-  int compare(SymbolBody *Other) override;
-
 private:
-  StringRef Name;
   ArchiveFile *File;
   const Archive::Symbol Sym;
 };
@@ -226,12 +238,11 @@ private:
 class Undefined : public SymbolBody {
 public:
   explicit Undefined(StringRef N, SymbolBody **S = nullptr)
-      : SymbolBody(UndefinedKind), Name(N), Alias(S) {}
+      : SymbolBody(UndefinedKind, N), Alias(S) {}
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == UndefinedKind;
   }
-  StringRef getName() override { return Name; }
 
   // An undefined symbol can have a fallback symbol which gives an
   // undefined symbol a second chance if it would remain undefined.
@@ -239,10 +250,7 @@ public:
   // Alias pointer points to.
   SymbolBody *getWeakAlias() { return Alias ? *Alias : nullptr; }
 
-  int compare(SymbolBody *Other) override;
-
 private:
-  StringRef Name;
   SymbolBody **Alias;
 };
 
@@ -256,23 +264,22 @@ class DefinedImportData : public Defined {
 public:
   DefinedImportData(StringRef D, StringRef N, StringRef E,
                     const coff_import_header *H)
-      : Defined(DefinedImportDataKind), Name(N), DLLName(D), ExternalName(E),
-        Hdr(H) {}
+      : Defined(DefinedImportDataKind, N), DLLName(D), ExternalName(E), Hdr(H) {
+  }
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == DefinedImportDataKind;
   }
 
-  StringRef getName() override { return Name; }
-  uint64_t getRVA() override { return Location->getRVA(); }
-  uint64_t getFileOff() override { return Location->getFileOff(); }
+  uint64_t getRVA() { return Location->getRVA(); }
+  uint64_t getFileOff() { return Location->getFileOff(); }
+
   StringRef getDLLName() { return DLLName; }
   StringRef getExternalName() { return ExternalName; }
   void setLocation(Chunk *AddressTable) { Location = AddressTable; }
   uint16_t getOrdinal() { return Hdr->OrdinalHint; }
 
 private:
-  StringRef Name;
   StringRef DLLName;
   StringRef ExternalName;
   const coff_import_header *Hdr;
@@ -287,19 +294,18 @@ private:
 class DefinedImportThunk : public Defined {
 public:
   DefinedImportThunk(StringRef N, DefinedImportData *S)
-      : Defined(DefinedImportThunkKind), Name(N), Data(S) {}
+      : Defined(DefinedImportThunkKind, N), Data(S) {}
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == DefinedImportThunkKind;
   }
 
-  StringRef getName() override { return Name; }
-  uint64_t getRVA() override { return Data.getRVA(); }
-  uint64_t getFileOff() override { return Data.getFileOff(); }
+  uint64_t getRVA() { return Data.getRVA(); }
+  uint64_t getFileOff() { return Data.getFileOff(); }
+
   Chunk *getChunk() { return &Data; }
 
 private:
-  StringRef Name;
   ImportThunkChunk Data;
 };
 
@@ -311,39 +317,31 @@ private:
 class DefinedLocalImport : public Defined {
 public:
   DefinedLocalImport(StringRef N, Defined *S)
-      : Defined(DefinedLocalImportKind), Name(N), Data(S) {}
+      : Defined(DefinedLocalImportKind, N), Data(S) {}
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == DefinedLocalImportKind;
   }
 
-  StringRef getName() override { return Name; }
-  uint64_t getRVA() override { return Data.getRVA(); }
-  uint64_t getFileOff() override { return Data.getFileOff(); }
+  uint64_t getRVA() { return Data.getRVA(); }
+  uint64_t getFileOff() { return Data.getFileOff(); }
+
   Chunk *getChunk() { return &Data; }
 
 private:
-  StringRef Name;
   LocalImportChunk Data;
 };
 
 class DefinedBitcode : public Defined {
 public:
-  DefinedBitcode(StringRef N, bool R)
-      : Defined(DefinedBitcodeKind), Name(N), Replaceable(R) {}
+  DefinedBitcode(StringRef N, bool IsReplaceable)
+      : Defined(DefinedBitcodeKind, N) {
+    this->IsReplaceable = IsReplaceable;
+  }
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == DefinedBitcodeKind;
   }
-
-  StringRef getName() override { return Name; }
-  uint64_t getRVA() override { llvm_unreachable("bitcode reached writer"); }
-  uint64_t getFileOff() override { llvm_unreachable("bitcode reached writer"); }
-  int compare(SymbolBody *Other) override;
-
-private:
-  StringRef Name;
-  bool Replaceable;
 };
 
 } // namespace coff