[opt] Devirtualize the SymbolBody type hierarchy and start compacting its members into the base class.

[chandlerc]

Summary

First, to help motivate this kind of change, understand that in
a self-link, LLD creates 5.5 million defined regular symbol bodies (and
6 million symbol bodies total). A significant portion of its time is
spent allocating the memory for these symbols, and befor ethis patch
the defined regular symbol body objects alone consumed some 420mb of
memory during the self link.

As a consequence, I think it is worth expending considerable effort to
make these objects as memory efficient as possible. This is the first of
several components of that. This change starts with the goal of removing
the virtual functins from SymbolBody so that it can avoid having a vptr
embedded in it when it already contains a "kind" member, and that member
can be much more compact than a vptr.

The primary way of doing this is to sink as much of the logic that we
would have to dispatch for into data in the base class. As part of this,
I made the various flags bits that will pack into a bitfield with the
kind tag. I also sank the Name down to eliminate the dispatch for that,
and used LLVM's RTTI-style dispatch for everything else (most of which
is cold and so doesn't matter terribly if we get minutely worse lowering
than a vtable dispatch).

As I was doing this, I wanted to make the RTTI-dispatch (which would
become much hotter than before) as efficient as possible, so I've
re-organized the tags somewhat. Notably, the common case (regular
defined symbols) is now zero which we can test for faster.

I also needed to rewrite the comparison routine used during resolving
symbols. This proved to be quite complex as the semantics of the
existing one were very subtle due to the back-and-forth virtual dispatch
caused by re-dispatching with reversed operands. I've consolidated it to
a single function and tried to comment it quite a bit more to help
explain what is going on. However, this may need more comments or other
explanations. It at least passes all the regression tests. I'm not
working on Windows, so I can't fully test it.

With all of these changes, the size of a DefinedRegular symbol on
a 64-bit build goes from 80 bytes to 64 bytes, and we save approximately
84mb or 20% of the memory consumed by these symbol bodies during the
link.

The link time appears marginally faster as well, and the profile hotness
of the memory allocation subsystem got a bit better, but there is still
a lot of allocation traffic.

[ruiu]

COFF/Symbols.cpp

46–48 ↗

(On Diff #28628)

Move this before "if (LK != RK)" to reduce nesting level a bit.

145–146 ↗

(On Diff #28628)

getRVA should never be called for bitcode symbols. You can remove this "case" and DefinedBitcode::getRVA.

168–169 ↗

(On Diff #28628)

Ditto

170–171 ↗

(On Diff #28628)

This can also be removed.

COFF/Symbols.h

97–104 ↗

(On Diff #28628)

Does the use of bitfield here save space? I guess StringRef is 8 byte aligned on 64 bit platform, so we have 8 bytes for attributes. We have four fields, so we can use 1 byte for each.

98 ↗

(On Diff #28628)

Can you use C++11 initializer?

unsigned IsExternal : 1 = true;

114 ↗

(On Diff #28628)

Add explicit.

130 ↗

(On Diff #28628)

All other classes starts with Defined, so name this DefinedObject, DefinedFile or DefinedCOFF.

131 ↗

(On Diff #28628)

Why do you need this?

163 ↗

(On Diff #28628)

Remove blank line.

188 ↗

(On Diff #28628)

Do we need this?

[chandlerc]

Updating to reflect changes from code review.

[chandlerc]

I think I've addressed everything. PTAL.

COFF/Symbols.cpp

46–48 ↗

(On Diff #28628)

Done.

145–146 ↗

(On Diff #28628)

Sure, I was letting the inliner do it, I'll do it directly and give a better message.

168–169 ↗

(On Diff #28628)

Done.

170–171 ↗

(On Diff #28628)

Similar to the above, done.

COFF/Symbols.h

97–104 ↗

(On Diff #28628)

The very next flag added would push us over 4 bytes though, and that would waste space on a 32-bit system. I'd like to pick a design that makes it easy to extend without having dramatic changes in efficiency.

98 ↗

(On Diff #28628)

I tried and it didn't compile. =/

114 ↗

(On Diff #28628)

Done.

130 ↗

(On Diff #28628)

Done.

131 ↗

(On Diff #28628)

To implement lazy getName and getDebugName.

163 ↗

(On Diff #28628)

Sure.

188 ↗

(On Diff #28628)

Yes, it's used to implement compare.

[ruiu]

LGTM

lld/trunk/COFF/Symbols.h

struct Symbol {
   explicit Symbol(SymbolBody *P) : Body(P) {}
   SymbolBody *Body;
 };
 
 // The base class for real symbol classes.
 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
   // in the Symbol may be mutated by the resolver. If you have a
   // pointer P to a SymbolBody and are not sure whether the resolver
   // has chosen the object among other objects having the same name,
   // you can access P->Backref->Body to get the resolver's result.
   void setBackref(Symbol *P) { Backref = P; }
   SymbolBody *getReplacement() { return Backref ? Backref->Body : this; }
 
   // 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;
 };
 
 // The base class for any defined symbols, including absolute symbols,
 // 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(); }
   SectionChunk *getChunk() { return *Data; }
   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;
 };
 
 // Absolute symbols.
 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
 // created from an archive file header, and it knows how to load an
 // object file from an archive to replace itself with a defined
 // symbol. If the resolver finds both Undefined and Lazy for
 // the same name, it will ask the Lazy to load a file.
 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;
 };
 
 // Undefined symbols.
 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.
   // If it remains undefined, it'll be replaced with whatever the
   // Alias pointer points to.
   SymbolBody *getWeakAlias() { return Alias ? *Alias : nullptr; }
 
-  int compare(SymbolBody *Other) override;
-
 private:
-  StringRef Name;
   SymbolBody **Alias;
 };
 
 // Windows-specific classes.
 
 // This class represents a symbol imported from a DLL. This has two
 // names for internal use and external use. The former is used for
 // name resolution, and the latter is used for the import descriptor
 // table in an output. The former has "__imp_" prefix.
 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;
   Chunk *Location = nullptr;
 };
 
 // This class represents a symbol for a jump table entry which jumps
 // to a function in a DLL. Linker are supposed to create such symbols
 // without "__imp_" prefix for all function symbols exported from
 // DLLs, so that you can call DLL functions as regular functions with
 // a regular name. A function pointer is given as a DefinedImportData.
 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;
 };
 
 // If you have a symbol "__imp_foo" in your object file, a symbol name
 // "foo" becomes automatically available as a pointer to "__imp_foo".
 // This class is for such automatically-created symbols.
 // Yes, this is an odd feature. We didn't intend to implement that.
 // This is here just for compatibility with MSVC.
 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
 } // namespace lld
 
 #endif

lld/trunk/COFF/Symbols.cpp

 
 using namespace llvm::object;
 using llvm::sys::fs::identify_magic;
 using llvm::sys::fs::file_magic;
 
 namespace lld {
 namespace coff {
 
-// 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())
-    return -Other->compare(this);
-  if (auto *D = dyn_cast<DefinedRegular>(Other)) {
-    if (isCOMDAT() && D->isCOMDAT())
-      return 1;
-    return 0;
+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 1;
+  return Name;
 }
 
-int DefinedCommon::compare(SymbolBody *Other) {
-  if (Other->kind() < kind())
+// Returns 1, 0 or -1 if this symbol should take precedence
+// over the Other, tie or lose, respectively.
+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<DefinedCommon>(Other))
-    return getSize() > D->getSize() ? 1 : -1;
-  if (isa<Lazy>(Other) || isa<Undefined>(Other))
-    return 1;
+
+  // First handle comparisons between two different kinds.
+  if (LK != RK) {
+
+    if (RK > LastDefinedKind) {
+      if (LK == LazyKind && cast<Undefined>(Other)->getWeakAlias())
         return -1;
-}
 
-int DefinedBitcode::compare(SymbolBody *Other) {
-  assert(Other->kind() >= kind());
-  if (!isa<Defined>(Other))
+      // The LHS is either defined or lazy and so it wins.
+      assert((LK <= LastDefinedKind || LK == LazyKind) && "Bad kind!");
       return 1;
-
-  if (auto *B = dyn_cast<DefinedBitcode>(Other)) {
-    if (!Replaceable && !B->Replaceable)
-      return 0;
-    // Non-replaceable symbols win.
-    return Replaceable ? -1 : 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 (auto *D = dyn_cast<DefinedRegular>(Other)) {
-    if (Replaceable || D->isCOMDAT())
-      return -1;
+        if (cast<DefinedRegular>(this)->isCOMDAT() || RHS->IsReplaceable)
+          return 1;
+
+        // Fallthrough to the default of a tie otherwise.
+      default:
         return 0;
       }
-  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;
+    // 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;
   }
 
-int Lazy::compare(SymbolBody *Other) {
-  if (Other->kind() < kind())
-    return -Other->compare(this);
+  // 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;
+  }
+
+  case DefinedCommonKind: {
+    auto *LHS = cast<DefinedCommon>(this);
+    auto *RHS = cast<DefinedCommon>(Other);
+    return LHS->getSize() > RHS->getSize() ? 1 : -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;
 
-  // 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;
+    // Non-replaceable symbols win, but even two replaceable symboles don't
+    // tie.
+    return LHS->IsReplaceable ? -1 : 1;
   }
 
-int Undefined::compare(SymbolBody *Other) {
-  if (Other->kind() < kind())
-    return -Other->compare(this);
-  if (cast<Undefined>(Other)->getWeakAlias())
-    return -1;
+  case LazyKind:
+    // Don't tie, just pick the LHS.
     return 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 UndefinedKind:
+    // Don't tie, just pick the LHS unless the RHS has a weak alias.
+    return cast<Undefined>(Other)->getWeakAlias() ? -1 : 1;
 
-StringRef DefinedCommon::getName() {
-  if (Name.empty())
-    File->getCOFFObj()->getSymbolName(Sym, Name);
-  return Name;
+  case DefinedLocalImportKind:
+  case DefinedImportThunkKind:
+  case DefinedImportDataKind:
+  case DefinedAbsoluteKind:
+    // These all simply tie.
+    return 0;
+  }
 }
 
-std::string DefinedRegular::getDebugName() {
-  return (getName() + " " + File->getShortName()).str();
+std::string SymbolBody::getDebugName() {
+  std::string N = getName().str();
+  if (auto *D = dyn_cast<DefinedCOFF>(this)) {
+    N += " ";
+    N += D->File->getShortName();
+  }
+  return N;
+}
+
+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() {
   auto MBRefOrErr = File->getMember(&Sym);
   if (auto EC = MBRefOrErr.getError())
     return EC;
   MemoryBufferRef MBRef = MBRefOrErr.get();